Subversion Repositories Kolibri OS

// Components for manipulating sequences of characters -*- C++ -*-

// Copyright (C) 1997-2013 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// .

/** @file bits/basic_string.h

 *  This is an internal header file, included by other library headers.

 *  Do not attempt to use it directly. @headername{string}

 */

//

// ISO C++ 14882: 21 Strings library

//

#ifndef _BASIC_STRING_H

#define _BASIC_STRING_H 1

#pragma GCC system_header

#include 

#include 

#if __cplusplus >= 201103L

#include 

#endif

namespace std _GLIBCXX_VISIBILITY(default)

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

  /**

   *  @class basic_string basic_string.h 

   *  @brief  Managing sequences of characters and character-like objects.

   *

   *  @ingroup strings

   *  @ingroup sequences

   *

   *  @tparam _CharT  Type of character

   *  @tparam _Traits  Traits for character type, defaults to

   *                   char_traits<_CharT>.

   *  @tparam _Alloc  Allocator type, defaults to allocator<_CharT>.

   *

   *  Meets the requirements of a container, a

   *  reversible container, and a

   *  sequence.  Of the

   *  optional sequence requirements, only

   *  @c push_back, @c at, and @c %array access are supported.

   *

   *  @doctodo

   *

   *

   *  Documentation?  What's that?

   *  Nathan Myers .

   *

   *  A string looks like this:

   *

   *  @code

   *                                        [_Rep]

   *                                        _M_length

   *   [basic_string]            _M_capacity

   *   _M_dataplus                          _M_refcount

   *   _M_p ---------------->               unnamed array of char_type

   *  @endcode

   *

   *  Where the _M_p points to the first character in the string, and

   *  you cast it to a pointer-to-_Rep and subtract 1 to get a

   *  pointer to the header.

   *

   *  This approach has the enormous advantage that a string object

   *  requires only one allocation.  All the ugliness is confined

   *  within a single %pair of inline functions, which each compile to

   *  a single @a add instruction: _Rep::_M_data(), and

   *  string::_M_rep(); and the allocation function which gets a

   *  block of raw bytes and with room enough and constructs a _Rep

   *  object at the front.

   *

   *  The reason you want _M_data pointing to the character %array and

   *  not the _Rep is so that the debugger can see the string

   *  contents. (Probably we should add a non-inline member to get

   *  the _Rep for the debugger to use, so users can check the actual

   *  string length.)

   *

   *  Note that the _Rep object is a POD so that you can have a

   *  static empty string _Rep object already @a constructed before

   *  static constructors have run.  The reference-count encoding is

   *  chosen so that a 0 indicates one reference, so you never try to

   *  destroy the empty-string _Rep object.

   *

   *  All but the last paragraph is considered pretty conventional

   *  for a C++ string implementation.

  */

  // 21.3  Template class basic_string

  template

    class basic_string

    {

      typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;

      // Types:

    public:

      typedef _Traits					    traits_type;

      typedef typename _Traits::char_type		    value_type;

      typedef _Alloc					    allocator_type;

      typedef typename _CharT_alloc_type::size_type	    size_type;

      typedef typename _CharT_alloc_type::difference_type   difference_type;

      typedef typename _CharT_alloc_type::reference	    reference;

      typedef typename _CharT_alloc_type::const_reference   const_reference;

      typedef typename _CharT_alloc_type::pointer	    pointer;

      typedef typename _CharT_alloc_type::const_pointer	    const_pointer;

      typedef __gnu_cxx::__normal_iterator  iterator;

      typedef __gnu_cxx::__normal_iterator

                                                            const_iterator;

      typedef std::reverse_iterator	const_reverse_iterator;

      typedef std::reverse_iterator		    reverse_iterator;

    private:

      // _Rep: string representation

      //   Invariants:

      //   1. String really contains _M_length + 1 characters: due to 21.3.4

      //      must be kept null-terminated.

      //   2. _M_capacity >= _M_length

      //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).

      //   3. _M_refcount has three states:

      //      -1: leaked, one reference, no ref-copies allowed, non-const.

      //       0: one reference, non-const.

      //     n>0: n + 1 references, operations require a lock, const.

      //   4. All fields==0 is an empty string, given the extra storage

      //      beyond-the-end for a null terminator; thus, the shared

      //      empty string representation needs no constructor.

      struct _Rep_base

      {

	size_type		_M_length;

	size_type		_M_capacity;

	_Atomic_word		_M_refcount;

      };

      struct _Rep : _Rep_base

      {

	// Types:

	typedef typename _Alloc::template rebind::other _Raw_bytes_alloc;

	// (Public) Data members:

	// The maximum number of individual char_type elements of an

	// individual string is determined by _S_max_size. This is the

	// value that will be returned by max_size().  (Whereas npos

	// is the maximum number of bytes the allocator can allocate.)

	// If one was to divvy up the theoretical largest size string,

	// with a terminating character and m _CharT elements, it'd

	// look like this:

	// npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)

	// Solving for m:

	// m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1

	// In addition, this implementation quarters this amount.

	static const size_type	_S_max_size;

	static const _CharT	_S_terminal;

	// The following storage is init'd to 0 by the linker, resulting

        // (carefully) in an empty string with one reference.

        static size_type _S_empty_rep_storage[];

        static _Rep&

        _S_empty_rep()

        {

	  // NB: Mild hack to avoid strict-aliasing warnings.  Note that

	  // _S_empty_rep_storage is never modified and the punning should

	  // be reasonably safe in this case.

	  void* __p = reinterpret_cast(&_S_empty_rep_storage);

	  return *reinterpret_cast<_Rep*>(__p);

	}

        bool

	_M_is_leaked() const

        { return this->_M_refcount < 0; }

        bool

	_M_is_shared() const

        { return this->_M_refcount > 0; }

        void

	_M_set_leaked()

        { this->_M_refcount = -1; }

        void

	_M_set_sharable()

        { this->_M_refcount = 0; }

	void

	_M_set_length_and_sharable(size_type __n)

	{

#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0

	  if (__builtin_expect(this != &_S_empty_rep(), false))

#endif

	    {

	      this->_M_set_sharable();  // One reference.

	      this->_M_length = __n;

	      traits_type::assign(this->_M_refdata()[__n], _S_terminal);

	      // grrr. (per 21.3.4)

	      // You cannot leave those LWG people alone for a second.

	    }

	}

	_CharT*

	_M_refdata() throw()

	{ return reinterpret_cast<_CharT*>(this + 1); }

	_CharT*

	_M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)

	{

	  return (!_M_is_leaked() && __alloc1 == __alloc2)

	          ? _M_refcopy() : _M_clone(__alloc1);

	}

	// Create & Destroy

	static _Rep*

	_S_create(size_type, size_type, const _Alloc&);

	void

	_M_dispose(const _Alloc& __a)

	{

#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0

	  if (__builtin_expect(this != &_S_empty_rep(), false))

#endif

	    {

	      // Be race-detector-friendly.  For more info see bits/c++config.

	      _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this->_M_refcount);

	      if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,

							 -1) <= 0)

		{

		  _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);

		  _M_destroy(__a);

		}

	    }

	}  // XXX MT

	void

	_M_destroy(const _Alloc&) throw();

	_CharT*

	_M_refcopy() throw()

	{

#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0

	  if (__builtin_expect(this != &_S_empty_rep(), false))

#endif

            __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);

	  return _M_refdata();

	}  // XXX MT

	_CharT*

	_M_clone(const _Alloc&, size_type __res = 0);

      };

      // Use empty-base optimization: http://www.cantrip.org/emptyopt.html

      struct _Alloc_hider : _Alloc

      {

	_Alloc_hider(_CharT* __dat, const _Alloc& __a)

	: _Alloc(__a), _M_p(__dat) { }

	_CharT* _M_p; // The actual data.

      };

    public:

      // Data Members (public):

      // NB: This is an unsigned type, and thus represents the maximum

      // size that the allocator can hold.

      ///  Value returned by various member functions when they fail.

      static const size_type	npos = static_cast(-1);

    private:

      // Data Members (private):

      mutable _Alloc_hider	_M_dataplus;

      _CharT*

      _M_data() const

      { return  _M_dataplus._M_p; }

      _CharT*

      _M_data(_CharT* __p)

      { return (_M_dataplus._M_p = __p); }

      _Rep*

      _M_rep() const

      { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }

      // For the internal use we have functions similar to `begin'/`end'

      // but they do not call _M_leak.

      iterator

      _M_ibegin() const

      { return iterator(_M_data()); }

      iterator

      _M_iend() const

      { return iterator(_M_data() + this->size()); }

      void

      _M_leak()    // for use in begin() & non-const op[]

      {

	if (!_M_rep()->_M_is_leaked())

	  _M_leak_hard();

      }

      size_type

      _M_check(size_type __pos, const char* __s) const

      {

	if (__pos > this->size())

	  __throw_out_of_range(__N(__s));

	return __pos;

      }

      void

      _M_check_length(size_type __n1, size_type __n2, const char* __s) const

      {

	if (this->max_size() - (this->size() - __n1) < __n2)

	  __throw_length_error(__N(__s));

      }

      // NB: _M_limit doesn't check for a bad __pos value.

      size_type

      _M_limit(size_type __pos, size_type __off) const

      {

	const bool __testoff =  __off < this->size() - __pos;

	return __testoff ? __off : this->size() - __pos;

      }

      // True if _Rep and source do not overlap.

      bool

      _M_disjunct(const _CharT* __s) const

      {

	return (less()(__s, _M_data())

		|| less()(_M_data() + this->size(), __s));

      }

      // When __n = 1 way faster than the general multichar

      // traits_type::copy/move/assign.

      static void

      _M_copy(_CharT* __d, const _CharT* __s, size_type __n)

      {

	if (__n == 1)

	  traits_type::assign(*__d, *__s);

	else

	  traits_type::copy(__d, __s, __n);

      }

      static void

      _M_move(_CharT* __d, const _CharT* __s, size_type __n)

      {

	if (__n == 1)

	  traits_type::assign(*__d, *__s);

	else

	  traits_type::move(__d, __s, __n);

      }

      static void

      _M_assign(_CharT* __d, size_type __n, _CharT __c)

      {

	if (__n == 1)

	  traits_type::assign(*__d, __c);

	else

	  traits_type::assign(__d, __n, __c);

      }

      // _S_copy_chars is a separate template to permit specialization

      // to optimize for the common case of pointers as iterators.

      template

        static void

        _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)

        {

	  for (; __k1 != __k2; ++__k1, ++__p)

	    traits_type::assign(*__p, *__k1); // These types are off.

	}

      static void

      _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2)

      { _S_copy_chars(__p, __k1.base(), __k2.base()); }

      static void

      _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)

      { _S_copy_chars(__p, __k1.base(), __k2.base()); }

      static void

      _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2)

      { _M_copy(__p, __k1, __k2 - __k1); }

      static void

      _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)

      { _M_copy(__p, __k1, __k2 - __k1); }

      static int

      _S_compare(size_type __n1, size_type __n2)

      {

	const difference_type __d = difference_type(__n1 - __n2);

	if (__d > __gnu_cxx::__numeric_traits::__max)

	  return __gnu_cxx::__numeric_traits::__max;

	else if (__d < __gnu_cxx::__numeric_traits::__min)

	  return __gnu_cxx::__numeric_traits::__min;

	else

	  return int(__d);

      }

      void

      _M_mutate(size_type __pos, size_type __len1, size_type __len2);

      void

      _M_leak_hard();

      static _Rep&

      _S_empty_rep()

      { return _Rep::_S_empty_rep(); }

    public:

      // Construct/copy/destroy:

      // NB: We overload ctors in some cases instead of using default

      // arguments, per 17.4.4.4 para. 2 item 2.

      /**

       *  @brief  Default constructor creates an empty string.

       */

      basic_string()

#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0

      : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }

#else

      : _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()){ }

#endif

      /**

       *  @brief  Construct an empty string using allocator @a a.

       */

      explicit

      basic_string(const _Alloc& __a);

      // NB: per LWG issue 42, semantics different from IS:

      /**

       *  @brief  Construct string with copy of value of @a str.

       *  @param  __str  Source string.

       */

      basic_string(const basic_string& __str);

      /**

       *  @brief  Construct string as copy of a substring.

       *  @param  __str  Source string.

       *  @param  __pos  Index of first character to copy from.

       *  @param  __n  Number of characters to copy (default remainder).

       */

      basic_string(const basic_string& __str, size_type __pos,

		   size_type __n = npos);

      /**

       *  @brief  Construct string as copy of a substring.

       *  @param  __str  Source string.

       *  @param  __pos  Index of first character to copy from.

       *  @param  __n  Number of characters to copy.

       *  @param  __a  Allocator to use.

       */

      basic_string(const basic_string& __str, size_type __pos,

		   size_type __n, const _Alloc& __a);

      /**

       *  @brief  Construct string initialized by a character %array.

       *  @param  __s  Source character %array.

       *  @param  __n  Number of characters to copy.

       *  @param  __a  Allocator to use (default is default allocator).

       *

       *  NB: @a __s must have at least @a __n characters, '\\0'

       *  has no special meaning.

       */

      basic_string(const _CharT* __s, size_type __n,

		   const _Alloc& __a = _Alloc());

      /**

       *  @brief  Construct string as copy of a C string.

       *  @param  __s  Source C string.

       *  @param  __a  Allocator to use (default is default allocator).

       */

      basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());

      /**

       *  @brief  Construct string as multiple characters.

       *  @param  __n  Number of characters.

       *  @param  __c  Character to use.

       *  @param  __a  Allocator to use (default is default allocator).

       */

      basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());

#if __cplusplus >= 201103L

      /**

       *  @brief  Move construct string.

       *  @param  __str  Source string.

       *

       *  The newly-created string contains the exact contents of @a __str.

       *  @a __str is a valid, but unspecified string.

       **/

      basic_string(basic_string&& __str) noexcept

      : _M_dataplus(__str._M_dataplus)

      {

#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0

	__str._M_data(_S_empty_rep()._M_refdata());

#else

	__str._M_data(_S_construct(size_type(), _CharT(), get_allocator()));

#endif

      }

      /**

       *  @brief  Construct string from an initializer %list.

       *  @param  __l  std::initializer_list of characters.

       *  @param  __a  Allocator to use (default is default allocator).

       */

      basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc());

#endif // C++11

      /**

       *  @brief  Construct string as copy of a range.

       *  @param  __beg  Start of range.

       *  @param  __end  End of range.

       *  @param  __a  Allocator to use (default is default allocator).

       */

      template

        basic_string(_InputIterator __beg, _InputIterator __end,

		     const _Alloc& __a = _Alloc());

      /**

       *  @brief  Destroy the string instance.

       */

      ~basic_string() _GLIBCXX_NOEXCEPT

      { _M_rep()->_M_dispose(this->get_allocator()); }

      /**

       *  @brief  Assign the value of @a str to this string.

       *  @param  __str  Source string.

       */

      basic_string&

      operator=(const basic_string& __str)

      { return this->assign(__str); }

      /**

       *  @brief  Copy contents of @a s into this string.

       *  @param  __s  Source null-terminated string.

       */

      basic_string&

      operator=(const _CharT* __s)

      { return this->assign(__s); }

      /**

       *  @brief  Set value to string of length 1.

       *  @param  __c  Source character.

       *

       *  Assigning to a character makes this string length 1 and

       *  (*this)[0] == @a c.

       */

      basic_string&

      operator=(_CharT __c)

      {

	this->assign(1, __c);

	return *this;

      }

#if __cplusplus >= 201103L

      /**

       *  @brief  Move assign the value of @a str to this string.

       *  @param  __str  Source string.

       *

       *  The contents of @a str are moved into this string (without copying).

       *  @a str is a valid, but unspecified string.

       **/

      basic_string&

      operator=(basic_string&& __str)

      {

	// NB: DR 1204.

	this->swap(__str);

	return *this;

      }

      /**

       *  @brief  Set value to string constructed from initializer %list.

       *  @param  __l  std::initializer_list.

       */

      basic_string&

      operator=(initializer_list<_CharT> __l)

      {

	this->assign(__l.begin(), __l.size());

	return *this;

      }

#endif // C++11

      // Iterators:

      /**

       *  Returns a read/write iterator that points to the first character in

       *  the %string.  Unshares the string.

       */

      iterator

      begin() _GLIBCXX_NOEXCEPT

      {

	_M_leak();

	return iterator(_M_data());

      }

      /**

       *  Returns a read-only (constant) iterator that points to the first

       *  character in the %string.

       */

      const_iterator

      begin() const _GLIBCXX_NOEXCEPT

      { return const_iterator(_M_data()); }

      /**

       *  Returns a read/write iterator that points one past the last

       *  character in the %string.  Unshares the string.

       */

      iterator

      end() _GLIBCXX_NOEXCEPT

      {

	_M_leak();

	return iterator(_M_data() + this->size());

      }

      /**

       *  Returns a read-only (constant) iterator that points one past the

       *  last character in the %string.

       */

      const_iterator

      end() const _GLIBCXX_NOEXCEPT

      { return const_iterator(_M_data() + this->size()); }

      /**

       *  Returns a read/write reverse iterator that points to the last

       *  character in the %string.  Iteration is done in reverse element

       *  order.  Unshares the string.

       */

      reverse_iterator

      rbegin() _GLIBCXX_NOEXCEPT

      { return reverse_iterator(this->end()); }

      /**

       *  Returns a read-only (constant) reverse iterator that points

       *  to the last character in the %string.  Iteration is done in

       *  reverse element order.

       */

      const_reverse_iterator

      rbegin() const _GLIBCXX_NOEXCEPT

      { return const_reverse_iterator(this->end()); }

      /**

       *  Returns a read/write reverse iterator that points to one before the

       *  first character in the %string.  Iteration is done in reverse

       *  element order.  Unshares the string.

       */

      reverse_iterator

      rend() _GLIBCXX_NOEXCEPT

      { return reverse_iterator(this->begin()); }

      /**

       *  Returns a read-only (constant) reverse iterator that points

       *  to one before the first character in the %string.  Iteration

       *  is done in reverse element order.

       */

      const_reverse_iterator

      rend() const _GLIBCXX_NOEXCEPT

      { return const_reverse_iterator(this->begin()); }

#if __cplusplus >= 201103L

      /**

       *  Returns a read-only (constant) iterator that points to the first

       *  character in the %string.

       */

      const_iterator

      cbegin() const noexcept

      { return const_iterator(this->_M_data()); }

      /**

       *  Returns a read-only (constant) iterator that points one past the

       *  last character in the %string.

       */

      const_iterator

      cend() const noexcept

      { return const_iterator(this->_M_data() + this->size()); }

      /**

       *  Returns a read-only (constant) reverse iterator that points

       *  to the last character in the %string.  Iteration is done in

       *  reverse element order.

       */

      const_reverse_iterator

      crbegin() const noexcept

      { return const_reverse_iterator(this->end()); }

      /**

       *  Returns a read-only (constant) reverse iterator that points

       *  to one before the first character in the %string.  Iteration

       *  is done in reverse element order.

       */

      const_reverse_iterator

      crend() const noexcept

      { return const_reverse_iterator(this->begin()); }

#endif

    public:

      // Capacity:

      ///  Returns the number of characters in the string, not including any

      ///  null-termination.

      size_type

      size() const _GLIBCXX_NOEXCEPT

      { return _M_rep()->_M_length; }

      ///  Returns the number of characters in the string, not including any

      ///  null-termination.

      size_type

      length() const _GLIBCXX_NOEXCEPT

      { return _M_rep()->_M_length; }

      ///  Returns the size() of the largest possible %string.

      size_type

      max_size() const _GLIBCXX_NOEXCEPT

      { return _Rep::_S_max_size; }

      /**

       *  @brief  Resizes the %string to the specified number of characters.

       *  @param  __n  Number of characters the %string should contain.

       *  @param  __c  Character to fill any new elements.

       *

       *  This function will %resize the %string to the specified

       *  number of characters.  If the number is smaller than the

       *  %string's current size the %string is truncated, otherwise

       *  the %string is extended and new elements are %set to @a __c.

       */

      void

      resize(size_type __n, _CharT __c);

      /**

       *  @brief  Resizes the %string to the specified number of characters.

       *  @param  __n  Number of characters the %string should contain.

       *

       *  This function will resize the %string to the specified length.  If

       *  the new size is smaller than the %string's current size the %string

       *  is truncated, otherwise the %string is extended and new characters

       *  are default-constructed.  For basic types such as char, this means

       *  setting them to 0.

       */

      void

      resize(size_type __n)

      { this->resize(__n, _CharT()); }

#if __cplusplus >= 201103L

      ///  A non-binding request to reduce capacity() to size().

      void

      shrink_to_fit()

      {

	if (capacity() > size())

	  {

	    __try

	      { reserve(0); }

	    __catch(...)

	      { }

	  }

      }

#endif

      /**

       *  Returns the total number of characters that the %string can hold

       *  before needing to allocate more memory.

       */

      size_type

      capacity() const _GLIBCXX_NOEXCEPT

      { return _M_rep()->_M_capacity; }

      /**

       *  @brief  Attempt to preallocate enough memory for specified number of

       *          characters.

       *  @param  __res_arg  Number of characters required.

       *  @throw  std::length_error  If @a __res_arg exceeds @c max_size().

       *

       *  This function attempts to reserve enough memory for the

       *  %string to hold the specified number of characters.  If the

       *  number requested is more than max_size(), length_error is

       *  thrown.

       *

       *  The advantage of this function is that if optimal code is a

       *  necessity and the user can determine the string length that will be

       *  required, the user can reserve the memory in %advance, and thus

       *  prevent a possible reallocation of memory and copying of %string

       *  data.

       */

      void

      reserve(size_type __res_arg = 0);

      /**

       *  Erases the string, making it empty.

       */

      void

      clear() _GLIBCXX_NOEXCEPT

      { _M_mutate(0, this->size(), 0); }

      /**

       *  Returns true if the %string is empty.  Equivalent to

       *  *this == "".

       */

      bool

      empty() const _GLIBCXX_NOEXCEPT

      { return this->size() == 0; }

      // Element access:

      /**

       *  @brief  Subscript access to the data contained in the %string.

       *  @param  __pos  The index of the character to access.

       *  @return  Read-only (constant) reference to the character.

       *

       *  This operator allows for easy, array-style, data access.

       *  Note that data access with this operator is unchecked and

       *  out_of_range lookups are not defined. (For checked lookups

       *  see at().)

       */

      const_reference

      operator[] (size_type __pos) const

      {

	_GLIBCXX_DEBUG_ASSERT(__pos <= size());

	return _M_data()[__pos];

      }

      /**

       *  @brief  Subscript access to the data contained in the %string.

       *  @param  __pos  The index of the character to access.

       *  @return  Read/write reference to the character.

       *

       *  This operator allows for easy, array-style, data access.

       *  Note that data access with this operator is unchecked and

       *  out_of_range lookups are not defined. (For checked lookups

       *  see at().)  Unshares the string.

       */

      reference

      operator[](size_type __pos)

      {

        // allow pos == size() as v3 extension:

	_GLIBCXX_DEBUG_ASSERT(__pos <= size());

        // but be strict in pedantic mode:

	_GLIBCXX_DEBUG_PEDASSERT(__pos < size());

	_M_leak();

	return _M_data()[__pos];

      }

      /**

       *  @brief  Provides access to the data contained in the %string.

       *  @param __n The index of the character to access.

       *  @return  Read-only (const) reference to the character.

       *  @throw  std::out_of_range  If @a n is an invalid index.

       *

       *  This function provides for safer data access.  The parameter is

       *  first checked that it is in the range of the string.  The function

       *  throws out_of_range if the check fails.

       */

      const_reference

      at(size_type __n) const

      {

	if (__n >= this->size())

	  __throw_out_of_range(__N("basic_string::at"));

	return _M_data()[__n];

      }

      /**

       *  @brief  Provides access to the data contained in the %string.

       *  @param __n The index of the character to access.

       *  @return  Read/write reference to the character.

       *  @throw  std::out_of_range  If @a n is an invalid index.

       *

       *  This function provides for safer data access.  The parameter is

       *  first checked that it is in the range of the string.  The function

       *  throws out_of_range if the check fails.  Success results in

       *  unsharing the string.

       */

      reference

      at(size_type __n)

      {

	if (__n >= size())

	  __throw_out_of_range(__N("basic_string::at"));

	_M_leak();

	return _M_data()[__n];

      }

#if __cplusplus >= 201103L

      /**

       *  Returns a read/write reference to the data at the first

       *  element of the %string.

       */

      reference

      front()

      { return operator[](0); }

      /**

       *  Returns a read-only (constant) reference to the data at the first

       *  element of the %string.

       */

      const_reference

      front() const

      { return operator[](0); }

      /**

       *  Returns a read/write reference to the data at the last

       *  element of the %string.

       */

      reference

      back()

      { return operator[](this->size() - 1); }

      /**

       *  Returns a read-only (constant) reference to the data at the

       *  last element of the %string.

       */

      const_reference

      back() const

      { return operator[](this->size() - 1); }

#endif

      // Modifiers:

      /**

       *  @brief  Append a string to this string.

       *  @param __str  The string to append.

       *  @return  Reference to this string.

       */

      basic_string&

      operator+=(const basic_string& __str)

      { return this->append(__str); }

      /**

       *  @brief  Append a C string.

       *  @param __s  The C string to append.

       *  @return  Reference to this string.

       */

      basic_string&

      operator+=(const _CharT* __s)

      { return this->append(__s); }

      /**

       *  @brief  Append a character.

       *  @param __c  The character to append.

       *  @return  Reference to this string.

       */

      basic_string&

      operator+=(_CharT __c)

      {

	this->push_back(__c);

	return *this;

      }

#if __cplusplus >= 201103L

      /**

       *  @brief  Append an initializer_list of characters.

       *  @param __l  The initializer_list of characters to be appended.

       *  @return  Reference to this string.

       */

      basic_string&

      operator+=(initializer_list<_CharT> __l)

      { return this->append(__l.begin(), __l.size()); }

#endif // C++11

      /**

       *  @brief  Append a string to this string.

       *  @param __str  The string to append.

       *  @return  Reference to this string.

       */

      basic_string&

      append(const basic_string& __str);

      /**

       *  @brief  Append a substring.

       *  @param __str  The string to append.

       *  @param __pos  Index of the first character of str to append.

       *  @param __n  The number of characters to append.

       *  @return  Reference to this string.

       *  @throw  std::out_of_range if @a __pos is not a valid index.

       *

       *  This function appends @a __n characters from @a __str

       *  starting at @a __pos to this string.  If @a __n is is larger

       *  than the number of available characters in @a __str, the

       *  remainder of @a __str is appended.

       */

      basic_string&

      append(const basic_string& __str, size_type __pos, size_type __n);

      /**

       *  @brief  Append a C substring.

       *  @param __s  The C string to append.

       *  @param __n  The number of characters to append.

       *  @return  Reference to this string.

       */

      basic_string&

      append(const _CharT* __s, size_type __n);

      /**

       *  @brief  Append a C string.

       *  @param __s  The C string to append.

       *  @return  Reference to this string.

       */

      basic_string&

      append(const _CharT* __s)

      {

	__glibcxx_requires_string(__s);

	return this->append(__s, traits_type::length(__s));

      }

      /**

       *  @brief  Append multiple characters.

       *  @param __n  The number of characters to append.

       *  @param __c  The character to use.

       *  @return  Reference to this string.

       *

       *  Appends __n copies of __c to this string.

       */

      basic_string&

      append(size_type __n, _CharT __c);

#if __cplusplus >= 201103L

      /**

       *  @brief  Append an initializer_list of characters.

       *  @param __l  The initializer_list of characters to append.

       *  @return  Reference to this string.

       */

      basic_string&

      append(initializer_list<_CharT> __l)

      { return this->append(__l.begin(), __l.size()); }

#endif // C++11

      /**

       *  @brief  Append a range of characters.

       *  @param __first  Iterator referencing the first character to append.

       *  @param __last  Iterator marking the end of the range.

       *  @return  Reference to this string.

       *

       *  Appends characters in the range [__first,__last) to this string.

       */

      template

        basic_string&

        append(_InputIterator __first, _InputIterator __last)

        { return this->replace(_M_iend(), _M_iend(), __first, __last); }

      /**

       *  @brief  Append a single character.

       *  @param __c  Character to append.

       */

      void

      push_back(_CharT __c)

      {

	const size_type __len = 1 + this->size();

	if (__len > this->capacity() || _M_rep()->_M_is_shared())

	  this->reserve(__len);

	traits_type::assign(_M_data()[this->size()], __c);

	_M_rep()->_M_set_length_and_sharable(__len);

      }

      /**

       *  @brief  Set value to contents of another string.

       *  @param  __str  Source string to use.

       *  @return  Reference to this string.

       */

      basic_string&

      assign(const basic_string& __str);

#if __cplusplus >= 201103L

      /**

       *  @brief  Set value to contents of another string.

       *  @param  __str  Source string to use.

       *  @return  Reference to this string.

       *

       *  This function sets this string to the exact contents of @a __str.

       *  @a __str is a valid, but unspecified string.

       */

      basic_string&

      assign(basic_string&& __str)

      {

	this->swap(__str);

	return *this;

      }

#endif // C++11

      /**

       *  @brief  Set value to a substring of a string.

       *  @param __str  The string to use.

       *  @param __pos  Index of the first character of str.

       *  @param __n  Number of characters to use.

       *  @return  Reference to this string.

       *  @throw  std::out_of_range if @a pos is not a valid index.

       *

       *  This function sets this string to the substring of @a __str

       *  consisting of @a __n characters at @a __pos.  If @a __n is

       *  is larger than the number of available characters in @a

       *  __str, the remainder of @a __str is used.

       */

      basic_string&

      assign(const basic_string& __str, size_type __pos, size_type __n)

      { return this->assign(__str._M_data()

			    + __str._M_check(__pos, "basic_string::assign"),

			    __str._M_limit(__pos, __n)); }

      /**

       *  @brief  Set value to a C substring.

       *  @param __s  The C string to use.

       *  @param __n  Number of characters to use.

       *  @return  Reference to this string.

       *

       *  This function sets the value of this string to the first @a __n

       *  characters of @a __s.  If @a __n is is larger than the number of

       *  available characters in @a __s, the remainder of @a __s is used.

       */

      basic_string&

      assign(const _CharT* __s, size_type __n);

      /**

       *  @brief  Set value to contents of a C string.

       *  @param __s  The C string to use.

       *  @return  Reference to this string.

       *

       *  This function sets the value of this string to the value of @a __s.

       *  The data is copied, so there is no dependence on @a __s once the

       *  function returns.