/storage/packages/gcc/5.3.0/include/c++/5.3.0/bits/basic_string.h

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

// Copyright (C) 1997-2015 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

// <http://www.gnu.org/licenses/>.

/** @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 <ext/atomicity.h>

#include <ext/alloc_traits.h>

#include <debug/debug.h>

#if __cplusplus >= 201103L

#include <initializer_list>

#endif

namespace std _GLIBCXX_VISIBILITY(default)

{

_GLIBCXX_BEGIN_NAMESPACE_VERSION

#if _GLIBCXX_USE_CXX11_ABI

_GLIBCXX_BEGIN_NAMESPACE_CXX11

  /**

   *  @class basic_string basic_string.h <string>

   *  @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 <a href="tables.html#65">container</a>, a

   *  <a href="tables.html#66">reversible container</a>, and a

   *  <a href="tables.html#67">sequence</a>.  Of the

   *  <a href="tables.html#68">optional sequence requirements</a>, only

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

   */

  template<typename _CharT, typename _Traits, typename _Alloc>

    class basic_string

    {

      typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template

	rebind<_CharT>::other _Char_alloc_type;

      typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;

      // Types:

    public:

      typedef _Traits					traits_type;

      typedef typename _Traits::char_type		value_type;

      typedef _Char_alloc_type				allocator_type;

      typedef typename _Alloc_traits::size_type		size_type;

      typedef typename _Alloc_traits::difference_type	difference_type;

      typedef typename _Alloc_traits::reference		reference;

      typedef typename _Alloc_traits::const_reference	const_reference;

      typedef typename _Alloc_traits::pointer		pointer;

      typedef typename _Alloc_traits::const_pointer	const_pointer;

      typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;

      typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>

							const_iterator;

      typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;

      typedef std::reverse_iterator<iterator>		reverse_iterator;

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

      static const size_type	npos = static_cast<size_type>(-1);

    private:

      // type used for positions in insert, erase etc.

#if __cplusplus < 201103L

      typedef iterator __const_iterator;

#else

      typedef const_iterator __const_iterator;

#endif

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

      struct _Alloc_hider : allocator_type // TODO check __is_final

      {

	_Alloc_hider(pointer __dat, const _Alloc& __a = _Alloc())

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

	pointer _M_p; // The actual data.

      };

      _Alloc_hider	_M_dataplus;

      size_type		_M_string_length;

      enum { _S_local_capacity = 15 / sizeof(_CharT) };

      union

      {

	_CharT           _M_local_buf[_S_local_capacity + 1];

	size_type        _M_allocated_capacity;

      };

      void

      _M_data(pointer __p)

      { _M_dataplus._M_p = __p; }

      void

      _M_length(size_type __length)

      { _M_string_length = __length; }

      pointer

      _M_data() const

      { return _M_dataplus._M_p; }

      pointer

      _M_local_data()

      {

#if __cplusplus >= 201103L

	return std::pointer_traits<pointer>::pointer_to(*_M_local_buf);

#else

	return pointer(_M_local_buf);

#endif

      }

      const_pointer

      _M_local_data() const

      {

#if __cplusplus >= 201103L

	return std::pointer_traits<const_pointer>::pointer_to(*_M_local_buf);

#else

	return const_pointer(_M_local_buf);

#endif

      }

      void

      _M_capacity(size_type __capacity)

      { _M_allocated_capacity = __capacity; }

      void

      _M_set_length(size_type __n)

      {

	_M_length(__n);

	traits_type::assign(_M_data()[__n], _CharT());

      }

      bool

      _M_is_local() const

      { return _M_data() == _M_local_data(); }

      // Create & Destroy

      pointer

      _M_create(size_type&, size_type);

      void

      _M_dispose()

      {

	if (!_M_is_local())

	  _M_destroy(_M_allocated_capacity);

      }

      void

      _M_destroy(size_type __size) throw()

      { _Alloc_traits::deallocate(_M_get_allocator(), _M_data(), __size + 1); }

      // _M_construct_aux is used to implement the 21.3.1 para 15 which

      // requires special behaviour if _InIterator is an integral type

      template<typename _InIterator>

        void

        _M_construct_aux(_InIterator __beg, _InIterator __end,

			 std::__false_type)

	{

          typedef typename iterator_traits<_InIterator>::iterator_category _Tag;

          _M_construct(__beg, __end, _Tag());

	}

      // _GLIBCXX_RESOLVE_LIB_DEFECTS

      // 438. Ambiguity in the "do the right thing" clause

      template<typename _Integer>

        void

        _M_construct_aux(_Integer __beg, _Integer __end, std::__true_type)

	{ _M_construct_aux_2(static_cast<size_type>(__beg), __end); }

      void

      _M_construct_aux_2(size_type __req, _CharT __c)

      { _M_construct(__req, __c); }

      template<typename _InIterator>

        void

        _M_construct(_InIterator __beg, _InIterator __end)

	{

	  typedef typename std::__is_integer<_InIterator>::__type _Integral;

	  _M_construct_aux(__beg, __end, _Integral());

        }

      // For Input Iterators, used in istreambuf_iterators, etc.

      template<typename _InIterator>

        void

        _M_construct(_InIterator __beg, _InIterator __end,

		     std::input_iterator_tag);

      // For forward_iterators up to random_access_iterators, used for

      // string::iterator, _CharT*, etc.

      template<typename _FwdIterator>

        void

        _M_construct(_FwdIterator __beg, _FwdIterator __end,

		     std::forward_iterator_tag);

      void

      _M_construct(size_type __req, _CharT __c);

      allocator_type&

      _M_get_allocator()

      { return _M_dataplus; }

      const allocator_type&

      _M_get_allocator() const

      { return _M_dataplus; }

    private:

#ifdef _GLIBCXX_DISAMBIGUATE_REPLACE_INST

      // The explicit instantiations in misc-inst.cc require this due to

      // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64063

      template<typename _Tp, bool _Requires =

	       !__are_same<_Tp, _CharT*>::__value

	       && !__are_same<_Tp, const _CharT*>::__value

	       && !__are_same<_Tp, iterator>::__value

	       && !__are_same<_Tp, const_iterator>::__value>

	struct __enable_if_not_native_iterator

	{ typedef basic_string& __type; };

      template<typename _Tp>

	struct __enable_if_not_native_iterator<_Tp, false> { };

#endif

      size_type

      _M_check(size_type __pos, const char* __s) const

      {

	if (__pos > this->size())

	  __throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "

				       "this->size() (which is %zu)"),

				   __s, __pos, this->size());

	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 _GLIBCXX_NOEXCEPT

      {

	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 _GLIBCXX_NOEXCEPT

      {

	return (less<const _CharT*>()(__s, _M_data())

		|| less<const _CharT*>()(_M_data() + this->size(), __s));

      }

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

      // traits_type::copy/move/assign.

      static void

      _S_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

      _S_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

      _S_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<class _Iterator>

        static void

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

	_GLIBCXX_NOEXCEPT

        {

	  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) _GLIBCXX_NOEXCEPT

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

      static void

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

      _GLIBCXX_NOEXCEPT

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

      static void

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

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

      static void

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

      _GLIBCXX_NOEXCEPT

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

      static int

      _S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPT

      {

	const difference_type __d = difference_type(__n1 - __n2);

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

	  return __gnu_cxx::__numeric_traits<int>::__max;

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

	  return __gnu_cxx::__numeric_traits<int>::__min;

	else

	  return int(__d);

      }

      void

      _M_assign(const basic_string& __rcs);

      void

      _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,

		size_type __len2);

      void

      _M_erase(size_type __pos, size_type __n);

    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 __cplusplus >= 201103L

      noexcept(is_nothrow_default_constructible<_Alloc>::value)

#endif

      : _M_dataplus(_M_local_data())

      { _M_set_length(0); }

      /**

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

       */

      explicit

      basic_string(const _Alloc& __a)

      : _M_dataplus(_M_local_data(), __a)

      { _M_set_length(0); }

      /**

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

       *  @param  __str  Source string.

       */

      basic_string(const basic_string& __str)

      : _M_dataplus(_M_local_data(), __str._M_get_allocator()) // TODO A traits

      { _M_construct(__str._M_data(), __str._M_data() + __str.length()); }

      /**

       *  @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).

       */

      // _GLIBCXX_RESOLVE_LIB_DEFECTS

      // 2402. [this constructor] shouldn't use Allocator()

      basic_string(const basic_string& __str, size_type __pos,

		   size_type __n = npos)

      : _M_dataplus(_M_local_data())

      {

	const _CharT* __start = __str._M_data()

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

	_M_construct(__start, __start + __str._M_limit(__pos, __n));

      }

      /**

       *  @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).

       *  @param  __a  Allocator to use.

       */

      basic_string(const basic_string& __str, size_type __pos,

		   size_type __n, const _Alloc& __a)

      : _M_dataplus(_M_local_data(), __a)

      {

	const _CharT* __start

	  = __str._M_data() + __str._M_check(__pos, "string::string");

	_M_construct(__start, __start + __str._M_limit(__pos, __n));

      }

      /**

       *  @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())

      : _M_dataplus(_M_local_data(), __a)

      { _M_construct(__s, __s + __n); }

      /**

       *  @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())

      : _M_dataplus(_M_local_data(), __a)

      { _M_construct(__s, __s ? __s + traits_type::length(__s) : __s+npos); }

      /**

       *  @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())

      : _M_dataplus(_M_local_data(), __a)

      { _M_construct(__n, __c); }

#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(_M_local_data(), std::move(__str._M_get_allocator()))

      {

	if (__str._M_is_local())

	  {

	    traits_type::copy(_M_local_buf, __str._M_local_buf,

			      _S_local_capacity + 1);

	  }

	else

	  {

	    _M_data(__str._M_data());

	    _M_capacity(__str._M_allocated_capacity);

	  }

	// Must use _M_length() here not _M_set_length() because

	// basic_stringbuf relies on writing into unallocated capacity so

	// we mess up the contents if we put a '\0' in the string.

	_M_length(__str.length());

	__str._M_data(__str._M_local_data());

	__str._M_set_length(0);

      }

      /**

       *  @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())

      : _M_dataplus(_M_local_data(), __a)

      { _M_construct(__l.begin(), __l.end()); }

      basic_string(const basic_string& __str, const _Alloc& __a)

      : _M_dataplus(_M_local_data(), __a)

      { _M_construct(__str.begin(), __str.end()); }

      basic_string(basic_string&& __str, const _Alloc& __a)

      : _M_dataplus(_M_local_data(), __a)

      {

	if (__str.get_allocator() == __a)

	  *this = std::move(__str);

	else

	  _M_construct(__str.begin(), __str.end());

      }

#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).

       */

#if __cplusplus >= 201103L

      template<typename _InputIterator,

	       typename = std::_RequireInputIter<_InputIterator>>

#else

      template<typename _InputIterator>

#endif

        basic_string(_InputIterator __beg, _InputIterator __end,

		     const _Alloc& __a = _Alloc())

	: _M_dataplus(_M_local_data(), __a)

	{ _M_construct(__beg, __end); }

      /**

       *  @brief  Destroy the string instance.

       */

      ~basic_string()

      { _M_dispose(); }

      /**

       *  @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.

       **/

      // PR 58265, this should be noexcept.

      // _GLIBCXX_RESOLVE_LIB_DEFECTS

      // 2063. Contradictory requirements for string move assignment

      basic_string&

      operator=(basic_string&& __str)

      {

	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.

       */

      iterator

      begin() _GLIBCXX_NOEXCEPT

      { 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.

       */

      iterator

      end() _GLIBCXX_NOEXCEPT

      { 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.

       */

      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.

       */

      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_string_length; }

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

      ///  null-termination.

      size_type

      length() const _GLIBCXX_NOEXCEPT

      { return _M_string_length; }

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

      size_type

      max_size() const _GLIBCXX_NOEXCEPT

      { return (_Alloc_traits::max_size(_M_get_allocator()) - 1) / 2; }

      /**

       *  @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() noexcept

      {

#if __cpp_exceptions

	if (capacity() > size())

	  {

	    try

	      { reserve(0); }

	    catch(...)

	      { }

	  }

#endif

      }

#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_is_local() ? size_type(_S_local_capacity)

	                     : _M_allocated_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_set_length(0); }

      /**

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

       *  <code>*this == ""</code>.

       */

      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_NOEXCEPT

      {

	_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().)

       */

      reference

      operator[](size_type __pos)

      {

        // Allow pos == size() both in C++98 mode, as v3 extension,

	// and in C++11 mode.

	_GLIBCXX_DEBUG_ASSERT(__pos <= size());

        // In pedantic mode be strict in C++98 mode.

	_GLIBCXX_DEBUG_PEDASSERT(__cplusplus >= 201103L || __pos < size());

	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_fmt(__N("basic_string::at: __n "

				       "(which is %zu) >= this->size() "

				       "(which is %zu)"),

				   __n, this->size());

	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.

       */

      reference

      at(size_type __n)

      {

	if (__n >= size())

	  __throw_out_of_range_fmt(__N("basic_string::at: __n "

				       "(which is %zu) >= this->size() "

				       "(which is %zu)"),

				   __n, this->size());

	return _M_data()[__n];

      }

#if __cplusplus >= 201103L

      /**

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

       *  element of the %string.

       */

      reference

      front() noexcept

      { return operator[](0); }

      /**

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

       *  element of the %string.

       */

      const_reference

      front() const noexcept

      { return operator[](0); }

      /**

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

       *  element of the %string.

       */

      reference

      back() noexcept

      { 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 noexcept

      { 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)

      { return _M_append(__str._M_data(), __str.size()); }

      /**

       *  @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)

      { return _M_append(__str._M_data()

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

			 __str._M_limit(__pos, __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)

      {

	__glibcxx_requires_string_len(__s, __n);

	_M_check_length(size_type(0), __n, "basic_string::append");

	return _M_append(__s, __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);

	const size_type __n = traits_type::length(__s);

	_M_check_length(size_type(0), __n, "basic_string::append");

	return _M_append(__s, __n);

      }

      /**

       *  @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)

      { return _M_replace_aux(this->size(), size_type(0), __n, __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.

       */

#if __cplusplus >= 201103L

      template<class _InputIterator,

	       typename = std::_RequireInputIter<_InputIterator>>

#else

      template<class _InputIterator>

#endif

        basic_string&

        append(_InputIterator __first, _InputIterator __last)

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

      /**

       *  @brief  Append a single character.

       *  @param __c  Character to append.

       */

      void

      push_back(_CharT __c)

      {

	const size_type __size = this->size();

	if (__size + 1 > this->capacity())

	  this->_M_mutate(__size, size_type(0), 0, size_type(1));

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

	this->_M_set_length(__size + 1);

      }

      /**

       *  @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)

      {

	this->_M_assign(__str);

	return *this;

      }

#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)

      {

	// _GLIBCXX_RESOLVE_LIB_DEFECTS

	// 2063. Contradictory requirements for string move assignment

	return *this = std::move(__str);

      }

#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 _M_replace(size_type(0), this->size(), __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)

      {

	__glibcxx_requires_string_len(__s, __n);

	return _M_replace(size_type(0), this->size(), __s, __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.

       */

      basic_string&

      assign(const _CharT* __s)

      {

	__glibcxx_requires_string(__s);

	return _M_replace(size_type(0), this->size(), __s,

			  traits_type::length(__s));

      }

      /**

       *  @brief  Set value to multiple characters.

       *  @param __n  Length of the resulting string.

       *  @param __c  The character to use.

       *  @return  Reference to this string.

       *

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

       *  character @a __c.

       */

      basic_string&

      assign(size_type __n, _CharT __c)

      { return _M_replace_aux(size_type(0), this->size(), __n, __c); }

      /**

       *  @brief  Set value to 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.

       *

       *  Sets value of string to characters in the range [__first,__last).

      */

#if __cplusplus >= 201103L

      template<class _InputIterator,

	       typename = std::_RequireInputIter<_InputIterator>>

#else

      template<class _InputIterator>

#endif

        basic_string&

        assign(_InputIterator __first, _InputIterator __last)

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

#if __cplusplus >= 201103L

      /**

       *  @brief  Set value to an initializer_list of characters.

       *  @param __l  The initializer_list of characters to assign.

       *  @return  Reference to this string.

       */

      basic_string&

      assign(initializer_list<_CharT> __l)

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

#endif // C++11

#if __cplusplus >= 201103L

      /**

       *  @brief  Insert multiple characters.

       *  @param __p  Const_iterator referencing location in string to

       *              insert at.

       *  @param __n  Number of characters to insert

       *  @param __c  The character to insert.

       *  @return  Iterator referencing the first inserted char.

       *  @throw  std::length_error  If new length exceeds @c max_size().

       *

       *  Inserts @a __n copies of character @a __c starting at the

       *  position referenced by iterator @a __p.  If adding

       *  characters causes the length to exceed max_size(),

       *  length_error is thrown.  The value of the string doesn't

       *  change if an error is thrown.

      */

      iterator

      insert(const_iterator __p, size_type __n, _CharT __c)

      {

	_GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());

	const size_type __pos = __p - begin();

	this->replace(__p, __p, __n, __c);

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

      }

#else

      /**

       *  @brief  Insert multiple characters.

       *  @param __p  Iterator referencing location in string to insert at.

       *  @param __n  Number of characters to insert

       *  @param __c  The character to insert.

       *  @throw  std::length_error  If new length exceeds @c max_size().

       *

       *  Inserts @a __n copies of character @a __c starting at the

       *  position referenced by iterator @a __p.  If adding

       *  characters causes the length to exceed max_size(),

       *  length_error is thrown.  The value of the string doesn't

       *  change if an error is thrown.

      */

      void

      insert(iterator __p, size_type __n, _CharT __c)

      {	this->replace(__p, __p, __n, __c);  }

#endif

#if __cplusplus >= 201103L

      /**

       *  @brief  Insert a range of characters.

       *  @param __p  Const_iterator referencing location in string to

       *              insert at.

       *  @param __beg  Start of range.

       *  @param __end  End of range.

       *  @return  Iterator referencing the first inserted char.

       *  @throw  std::length_error  If new length exceeds @c max_size().

       *

       *  Inserts characters in range [beg,end).  If adding characters

       *  causes the length to exceed max_size(), length_error is

       *  thrown.  The value of the string doesn't change if an error

       *  is thrown.

      */

      template<class _InputIterator,

	       typename = std::_RequireInputIter<_InputIterator>>

	iterator

        insert(const_iterator __p, _InputIterator __beg, _InputIterator __end)

        {

	  _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());

	  const size_type __pos = __p - begin();

	  this->replace(__p, __p, __beg, __end);

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

	}

#else

      /**

       *  @brief  Insert a range of characters.

       *  @param __p  Iterator referencing location in string to insert at.

       *  @param __beg  Start of range.

       *  @param __end  End of range.

       *  @throw  std::length_error  If new length exceeds @c max_size().

       *

       *  Inserts characters in range [__beg,__end).  If adding

       *  characters causes the length to exceed max_size(),

       *  length_error is thrown.  The value of the string doesn't

       *  change if an error is thrown.

      */

      template<class _InputIterator>

        void

        insert(iterator __p, _InputIterator __beg, _InputIterator __end)

        { this->replace(__p, __p, __beg, __end); }

#endif

#if __cplusplus >= 201103L

      /**

       *  @brief  Insert an initializer_list of characters.

       *  @param __p  Iterator referencing location in string to insert at.

       *  @param __l  The initializer_list of characters to insert.

       *  @throw  std::length_error  If new length exceeds @c max_size().

       */

      void

      insert(iterator __p, initializer_list<_CharT> __l)

      {

	_GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());

	this->insert(__p - begin(), __l.begin(), __l.size());

      }

#endif // C++11

      /**

       *  @brief  Insert value of a string.

       *  @param __pos1  Iterator referencing location in string to insert at.

       *  @param __str  The string to insert.

       *  @return  Reference to this string.

       *  @throw  std::length_error  If new length exceeds @c max_size().

       *

       *  Inserts value of @a __str starting at @a __pos1.  If adding

       *  characters causes the length to exceed max_size(),

       *  length_error is thrown.  The value of the string doesn't

       *  change if an error is thrown.

      */

      basic_string&

      insert(size_type __pos1, const basic_string& __str)

      { return this->replace(__pos1, size_type(0),

			     __str._M_data(), __str.size()); }

      /**