The C and C++ Include Header Files

/usr/include/c++/11/bits/basic_string.tcc


$ cat -n /usr/include/c++/11/bits/basic_string.tcc

     1	// Components for manipulating sequences of characters -*- C++ -*-
     2	
     3	// Copyright (C) 1997-2021 Free Software Foundation, Inc.
     4	//
     5	// This file is part of the GNU ISO C++ Library.  This library is free
     6	// software; you can redistribute it and/or modify it under the
     7	// terms of the GNU General Public License as published by the
     8	// Free Software Foundation; either version 3, or (at your option)
     9	// any later version.
    10	
    11	// This library is distributed in the hope that it will be useful,
    12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
    13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    14	// GNU General Public License for more details.
    15	
    16	// Under Section 7 of GPL version 3, you are granted additional
    17	// permissions described in the GCC Runtime Library Exception, version
    18	// 3.1, as published by the Free Software Foundation.
    19	
    20	// You should have received a copy of the GNU General Public License and
    21	// a copy of the GCC Runtime Library Exception along with this program;
    22	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
    23	// <http://www.gnu.org/licenses/>.
    24	
    25	/** @file bits/basic_string.tcc
    26	 *  This is an internal header file, included by other library headers.
    27	 *  Do not attempt to use it directly. @headername{string}
    28	 */
    29	
    30	//
    31	// ISO C++ 14882: 21  Strings library
    32	//
    33	
    34	// Written by Jason Merrill based upon the specification by Takanori Adachi
    35	// in ANSI X3J16/94-0013R2.  Rewritten by Nathan Myers to ISO-14882.
    36	// Non-reference-counted implementation written by Paolo Carlini and
    37	// updated by Jonathan Wakely for ISO-14882-2011.
    38	
    39	#ifndef _BASIC_STRING_TCC
    40	#define _BASIC_STRING_TCC 1
    41	
    42	#pragma GCC system_header
    43	
    44	#include <bits/cxxabi_forced.h>
    45	
    46	namespace std _GLIBCXX_VISIBILITY(default)
    47	{
    48	_GLIBCXX_BEGIN_NAMESPACE_VERSION
    49	
    50	#if _GLIBCXX_USE_CXX11_ABI
    51	
    52	  template<typename _CharT, typename _Traits, typename _Alloc>
    53	    const typename basic_string<_CharT, _Traits, _Alloc>::size_type
    54	    basic_string<_CharT, _Traits, _Alloc>::npos;
    55	
    56	  template<typename _CharT, typename _Traits, typename _Alloc>
    57	    void
    58	    basic_string<_CharT, _Traits, _Alloc>::
    59	    swap(basic_string& __s) _GLIBCXX_NOEXCEPT
    60	    {
    61	      if (this == &__s)
    62		return;
    63	
    64	      _Alloc_traits::_S_on_swap(_M_get_allocator(), __s._M_get_allocator());
    65	
    66	      if (_M_is_local())
    67		if (__s._M_is_local())
    68		  {
    69		    if (length() && __s.length())
    70		      {
    71			_CharT __tmp_data[_S_local_capacity + 1];
    72			traits_type::copy(__tmp_data, __s._M_local_buf,
    73					  _S_local_capacity + 1);
    74			traits_type::copy(__s._M_local_buf, _M_local_buf,
    75					  _S_local_capacity + 1);
    76			traits_type::copy(_M_local_buf, __tmp_data,
    77					  _S_local_capacity + 1);
    78		      }
    79		    else if (__s.length())
    80		      {
    81			traits_type::copy(_M_local_buf, __s._M_local_buf,
    82					  _S_local_capacity + 1);
    83			_M_length(__s.length());
    84			__s._M_set_length(0);
    85			return;
    86		      }
    87		    else if (length())
    88		      {
    89			traits_type::copy(__s._M_local_buf, _M_local_buf,
    90					  _S_local_capacity + 1);
    91			__s._M_length(length());
    92			_M_set_length(0);
    93			return;
    94		      }
    95		  }
    96		else
    97		  {
    98		    const size_type __tmp_capacity = __s._M_allocated_capacity;
    99		    traits_type::copy(__s._M_local_buf, _M_local_buf,
   100				      _S_local_capacity + 1);
   101		    _M_data(__s._M_data());
   102		    __s._M_data(__s._M_local_buf);
   103		    _M_capacity(__tmp_capacity);
   104		  }
   105	      else
   106		{
   107		  const size_type __tmp_capacity = _M_allocated_capacity;
   108		  if (__s._M_is_local())
   109		    {
   110		      traits_type::copy(_M_local_buf, __s._M_local_buf,
   111					_S_local_capacity + 1);
   112		      __s._M_data(_M_data());
   113		      _M_data(_M_local_buf);
   114		    }
   115		  else
   116		    {
   117		      pointer __tmp_ptr = _M_data();
   118		      _M_data(__s._M_data());
   119		      __s._M_data(__tmp_ptr);
   120		      _M_capacity(__s._M_allocated_capacity);
   121		    }
   122		  __s._M_capacity(__tmp_capacity);
   123		}
   124	
   125	      const size_type __tmp_length = length();
   126	      _M_length(__s.length());
   127	      __s._M_length(__tmp_length);
   128	    }
   129	
   130	  template<typename _CharT, typename _Traits, typename _Alloc>
   131	    typename basic_string<_CharT, _Traits, _Alloc>::pointer
   132	    basic_string<_CharT, _Traits, _Alloc>::
   133	    _M_create(size_type& __capacity, size_type __old_capacity)
   134	    {
   135	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
   136	      // 83.  String::npos vs. string::max_size()
   137	      if (__capacity > max_size())
   138		std::__throw_length_error(__N("basic_string::_M_create"));
   139	
   140	      // The below implements an exponential growth policy, necessary to
   141	      // meet amortized linear time requirements of the library: see
   142	      // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
   143	      if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
   144		{
   145		  __capacity = 2 * __old_capacity;
   146		  // Never allocate a string bigger than max_size.
   147		  if (__capacity > max_size())
   148		    __capacity = max_size();
   149		}
   150	
   151	      // NB: Need an array of char_type[__capacity], plus a terminating
   152	      // null char_type() element.
   153	      return _Alloc_traits::allocate(_M_get_allocator(), __capacity + 1);
   154	    }
   155	
   156	  // NB: This is the special case for Input Iterators, used in
   157	  // istreambuf_iterators, etc.
   158	  // Input Iterators have a cost structure very different from
   159	  // pointers, calling for a different coding style.
   160	  template<typename _CharT, typename _Traits, typename _Alloc>
   161	    template<typename _InIterator>
   162	      void
   163	      basic_string<_CharT, _Traits, _Alloc>::
   164	      _M_construct(_InIterator __beg, _InIterator __end,
   165			   std::input_iterator_tag)
   166	      {
   167		size_type __len = 0;
   168		size_type __capacity = size_type(_S_local_capacity);
   169	
   170		while (__beg != __end && __len < __capacity)
   171		  {
   172		    _M_data()[__len++] = *__beg;
   173		    ++__beg;
   174		  }
   175	
   176		__try
   177		  {
   178		    while (__beg != __end)
   179		      {
   180			if (__len == __capacity)
   181			  {
   182			    // Allocate more space.
   183			    __capacity = __len + 1;
   184			    pointer __another = _M_create(__capacity, __len);
   185			    this->_S_copy(__another, _M_data(), __len);
   186			    _M_dispose();
   187			    _M_data(__another);
   188			    _M_capacity(__capacity);
   189			  }
   190			_M_data()[__len++] = *__beg;
   191			++__beg;
   192		      }
   193		  }
   194		__catch(...)
   195		  {
   196		    _M_dispose();
   197		    __throw_exception_again;
   198		  }
   199	
   200		_M_set_length(__len);
   201	      }
   202	
   203	  template<typename _CharT, typename _Traits, typename _Alloc>
   204	    template<typename _InIterator>
   205	      void
   206	      basic_string<_CharT, _Traits, _Alloc>::
   207	      _M_construct(_InIterator __beg, _InIterator __end,
   208			   std::forward_iterator_tag)
   209	      {
   210		// NB: Not required, but considered best practice.
   211		if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
   212		  std::__throw_logic_error(__N("basic_string::"
   213					       "_M_construct null not valid"));
   214	
   215		size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
   216	
   217		if (__dnew > size_type(_S_local_capacity))
   218		  {
   219		    _M_data(_M_create(__dnew, size_type(0)));
   220		    _M_capacity(__dnew);
   221		  }
   222	
   223		// Check for out_of_range and length_error exceptions.
   224		__try
   225		  { this->_S_copy_chars(_M_data(), __beg, __end); }
   226		__catch(...)
   227		  {
   228		    _M_dispose();
   229		    __throw_exception_again;
   230		  }
   231	
   232		_M_set_length(__dnew);
   233	      }
   234	
   235	  template<typename _CharT, typename _Traits, typename _Alloc>
   236	    void
   237	    basic_string<_CharT, _Traits, _Alloc>::
   238	    _M_construct(size_type __n, _CharT __c)
   239	    {
   240	      if (__n > size_type(_S_local_capacity))
   241		{
   242		  _M_data(_M_create(__n, size_type(0)));
   243		  _M_capacity(__n);
   244		}
   245	
   246	      if (__n)
   247		this->_S_assign(_M_data(), __n, __c);
   248	
   249	      _M_set_length(__n);
   250	    }
   251	
   252	  template<typename _CharT, typename _Traits, typename _Alloc>
   253	    void
   254	    basic_string<_CharT, _Traits, _Alloc>::
   255	    _M_assign(const basic_string& __str)
   256	    {
   257	      if (this != &__str)
   258		{
   259		  const size_type __rsize = __str.length();
   260		  const size_type __capacity = capacity();
   261	
   262		  if (__rsize > __capacity)
   263		    {
   264		      size_type __new_capacity = __rsize;
   265		      pointer __tmp = _M_create(__new_capacity, __capacity);
   266		      _M_dispose();
   267		      _M_data(__tmp);
   268		      _M_capacity(__new_capacity);
   269		    }
   270	
   271		  if (__rsize)
   272		    this->_S_copy(_M_data(), __str._M_data(), __rsize);
   273	
   274		  _M_set_length(__rsize);
   275		}
   276	    }
   277	
   278	  template<typename _CharT, typename _Traits, typename _Alloc>
   279	    void
   280	    basic_string<_CharT, _Traits, _Alloc>::
   281	    reserve(size_type __res)
   282	    {
   283	      const size_type __capacity = capacity();
   284	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
   285	      // 2968. Inconsistencies between basic_string reserve and
   286	      // vector/unordered_map/unordered_set reserve functions
   287	      // P0966 reserve should not shrink
   288	      if (__res <= __capacity)
   289		return;
   290	
   291	      pointer __tmp = _M_create(__res, __capacity);
   292	      this->_S_copy(__tmp, _M_data(), length() + 1);
   293	      _M_dispose();
   294	      _M_data(__tmp);
   295	      _M_capacity(__res);
   296	    }
   297	
   298	  template<typename _CharT, typename _Traits, typename _Alloc>
   299	    void
   300	    basic_string<_CharT, _Traits, _Alloc>::
   301	    _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
   302		      size_type __len2)
   303	    {
   304	      const size_type __how_much = length() - __pos - __len1;
   305	
   306	      size_type __new_capacity = length() + __len2 - __len1;
   307	      pointer __r = _M_create(__new_capacity, capacity());
   308	
   309	      if (__pos)
   310		this->_S_copy(__r, _M_data(), __pos);
   311	      if (__s && __len2)
   312		this->_S_copy(__r + __pos, __s, __len2);
   313	      if (__how_much)
   314		this->_S_copy(__r + __pos + __len2,
   315			      _M_data() + __pos + __len1, __how_much);
   316	
   317	      _M_dispose();
   318	      _M_data(__r);
   319	      _M_capacity(__new_capacity);
   320	    }
   321	
   322	  template<typename _CharT, typename _Traits, typename _Alloc>
   323	    void
   324	    basic_string<_CharT, _Traits, _Alloc>::
   325	    _M_erase(size_type __pos, size_type __n)
   326	    {
   327	      const size_type __how_much = length() - __pos - __n;
   328	
   329	      if (__how_much && __n)
   330		this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much);
   331	
   332	      _M_set_length(length() - __n);
   333	    }
   334	
   335	  template<typename _CharT, typename _Traits, typename _Alloc>
   336	    void
   337	    basic_string<_CharT, _Traits, _Alloc>::
   338	    reserve()
   339	    {
   340	      if (_M_is_local())
   341		return;
   342	
   343	      const size_type __length = length();
   344	      const size_type __capacity = _M_allocated_capacity;
   345	
   346	      if (__length <= size_type(_S_local_capacity))
   347		{
   348		  this->_S_copy(_M_local_data(), _M_data(), __length + 1);
   349		  _M_destroy(__capacity);
   350		  _M_data(_M_local_data());
   351		}
   352	#if __cpp_exceptions
   353	      else if (__length < __capacity)
   354		try
   355		  {
   356		    pointer __tmp
   357		      = _Alloc_traits::allocate(_M_get_allocator(), __length + 1);
   358		    this->_S_copy(__tmp, _M_data(), __length + 1);
   359		    _M_dispose();
   360		    _M_data(__tmp);
   361		    _M_capacity(__length);
   362		  }
   363		catch (const __cxxabiv1::__forced_unwind&)
   364		  { throw; }
   365		catch (...)
   366		  { /* swallow the exception */ }
   367	#endif
   368	    }
   369	
   370	  template<typename _CharT, typename _Traits, typename _Alloc>
   371	    void
   372	    basic_string<_CharT, _Traits, _Alloc>::
   373	    resize(size_type __n, _CharT __c)
   374	    {
   375	      const size_type __size = this->size();
   376	      if (__size < __n)
   377		this->append(__n - __size, __c);
   378	      else if (__n < __size)
   379		this->_M_set_length(__n);
   380	    }
   381	
   382	  template<typename _CharT, typename _Traits, typename _Alloc>
   383	    basic_string<_CharT, _Traits, _Alloc>&
   384	    basic_string<_CharT, _Traits, _Alloc>::
   385	    _M_append(const _CharT* __s, size_type __n)
   386	    {
   387	      const size_type __len = __n + this->size();
   388	
   389	      if (__len <= this->capacity())
   390		{
   391		  if (__n)
   392		    this->_S_copy(this->_M_data() + this->size(), __s, __n);
   393		}
   394	      else
   395		this->_M_mutate(this->size(), size_type(0), __s, __n);
   396	
   397	      this->_M_set_length(__len);
   398	      return *this;
   399	    }
   400	
   401	  template<typename _CharT, typename _Traits, typename _Alloc>
   402	    template<typename _InputIterator>
   403	      basic_string<_CharT, _Traits, _Alloc>&
   404	      basic_string<_CharT, _Traits, _Alloc>::
   405	      _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
   406				  _InputIterator __k1, _InputIterator __k2,
   407				  std::__false_type)
   408	      {
   409		// _GLIBCXX_RESOLVE_LIB_DEFECTS
   410		// 2788. unintentionally require a default constructible allocator
   411		const basic_string __s(__k1, __k2, this->get_allocator());
   412		const size_type __n1 = __i2 - __i1;
   413		return _M_replace(__i1 - begin(), __n1, __s._M_data(),
   414				  __s.size());
   415	      }
   416	
   417	  template<typename _CharT, typename _Traits, typename _Alloc>
   418	    basic_string<_CharT, _Traits, _Alloc>&
   419	    basic_string<_CharT, _Traits, _Alloc>::
   420	    _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
   421			   _CharT __c)
   422	    {
   423	      _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
   424	
   425	      const size_type __old_size = this->size();
   426	      const size_type __new_size = __old_size + __n2 - __n1;
   427	
   428	      if (__new_size <= this->capacity())
   429		{
   430		  pointer __p = this->_M_data() + __pos1;
   431	
   432		  const size_type __how_much = __old_size - __pos1 - __n1;
   433		  if (__how_much && __n1 != __n2)
   434		    this->_S_move(__p + __n2, __p + __n1, __how_much);
   435		}
   436	      else
   437		this->_M_mutate(__pos1, __n1, 0, __n2);
   438	
   439	      if (__n2)
   440		this->_S_assign(this->_M_data() + __pos1, __n2, __c);
   441	
   442	      this->_M_set_length(__new_size);
   443	      return *this;
   444	    }
   445	
   446	  template<typename _CharT, typename _Traits, typename _Alloc>
   447	    basic_string<_CharT, _Traits, _Alloc>&
   448	    basic_string<_CharT, _Traits, _Alloc>::
   449	    _M_replace(size_type __pos, size_type __len1, const _CharT* __s,
   450		       const size_type __len2)
   451	    {
   452	      _M_check_length(__len1, __len2, "basic_string::_M_replace");
   453	
   454	      const size_type __old_size = this->size();
   455	      const size_type __new_size = __old_size + __len2 - __len1;
   456	
   457	      if (__new_size <= this->capacity())
   458		{
   459		  pointer __p = this->_M_data() + __pos;
   460	
   461		  const size_type __how_much = __old_size - __pos - __len1;
   462		  if (_M_disjunct(__s))
   463		    {
   464		      if (__how_much && __len1 != __len2)
   465			this->_S_move(__p + __len2, __p + __len1, __how_much);
   466		      if (__len2)
   467			this->_S_copy(__p, __s, __len2);
   468		    }
   469		  else
   470		    {
   471		      // Work in-place.
   472		      if (__len2 && __len2 <= __len1)
   473			this->_S_move(__p, __s, __len2);
   474		      if (__how_much && __len1 != __len2)
   475			this->_S_move(__p + __len2, __p + __len1, __how_much);
   476		      if (__len2 > __len1)
   477			{
   478			  if (__s + __len2 <= __p + __len1)
   479			    this->_S_move(__p, __s, __len2);
   480			  else if (__s >= __p + __len1)
   481			    {
   482			      // Hint to middle end that __p and __s overlap
   483			      // (PR 98465).
   484			      const size_type __poff = (__s - __p) + (__len2 - __len1);
   485			      this->_S_copy(__p, __p + __poff, __len2);
   486			    }
   487			  else
   488			    {
   489			      const size_type __nleft = (__p + __len1) - __s;
   490			      this->_S_move(__p, __s, __nleft);
   491			      this->_S_copy(__p + __nleft, __p + __len2,
   492					    __len2 - __nleft);
   493			    }
   494			}
   495		    }
   496		}
   497	      else
   498		this->_M_mutate(__pos, __len1, __s, __len2);
   499	
   500	      this->_M_set_length(__new_size);
   501	      return *this;
   502	    }
   503	
   504	  template<typename _CharT, typename _Traits, typename _Alloc>
   505	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
   506	    basic_string<_CharT, _Traits, _Alloc>::
   507	    copy(_CharT* __s, size_type __n, size_type __pos) const
   508	    {
   509	      _M_check(__pos, "basic_string::copy");
   510	      __n = _M_limit(__pos, __n);
   511	      __glibcxx_requires_string_len(__s, __n);
   512	      if (__n)
   513		_S_copy(__s, _M_data() + __pos, __n);
   514	      // 21.3.5.7 par 3: do not append null.  (good.)
   515	      return __n;
   516	    }
   517	
   518	#else  // !_GLIBCXX_USE_CXX11_ABI
   519	
   520	  template<typename _CharT, typename _Traits, typename _Alloc>
   521	    const typename basic_string<_CharT, _Traits, _Alloc>::size_type
   522	    basic_string<_CharT, _Traits, _Alloc>::
   523	    _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;
   524	
   525	  template<typename _CharT, typename _Traits, typename _Alloc>
   526	    const _CharT
   527	    basic_string<_CharT, _Traits, _Alloc>::
   528	    _Rep::_S_terminal = _CharT();
   529	
   530	  template<typename _CharT, typename _Traits, typename _Alloc>
   531	    const typename basic_string<_CharT, _Traits, _Alloc>::size_type
   532	    basic_string<_CharT, _Traits, _Alloc>::npos;
   533	
   534	  // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
   535	  // at static init time (before static ctors are run).
   536	  template<typename _CharT, typename _Traits, typename _Alloc>
   537	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
   538	    basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[
   539	    (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /
   540	      sizeof(size_type)];
   541	
   542	  // NB: This is the special case for Input Iterators, used in
   543	  // istreambuf_iterators, etc.
   544	  // Input Iterators have a cost structure very different from
   545	  // pointers, calling for a different coding style.
   546	  template<typename _CharT, typename _Traits, typename _Alloc>
   547	    template<typename _InIterator>
   548	      _CharT*
   549	      basic_string<_CharT, _Traits, _Alloc>::
   550	      _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
   551			   input_iterator_tag)
   552	      {
   553	#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
   554		if (__beg == __end && __a == _Alloc())
   555		  return _S_empty_rep()._M_refdata();
   556	#endif
   557		// Avoid reallocation for common case.
   558		_CharT __buf[128];
   559		size_type __len = 0;
   560		while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
   561		  {
   562		    __buf[__len++] = *__beg;
   563		    ++__beg;
   564		  }
   565		_Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
   566		_M_copy(__r->_M_refdata(), __buf, __len);
   567		__try
   568		  {
   569		    while (__beg != __end)
   570		      {
   571			if (__len == __r->_M_capacity)
   572			  {
   573			    // Allocate more space.
   574			    _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
   575			    _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
   576			    __r->_M_destroy(__a);
   577			    __r = __another;
   578			  }
   579			__r->_M_refdata()[__len++] = *__beg;
   580			++__beg;
   581		      }
   582		  }
   583		__catch(...)
   584		  {
   585		    __r->_M_destroy(__a);
   586		    __throw_exception_again;
   587		  }
   588		__r->_M_set_length_and_sharable(__len);
   589		return __r->_M_refdata();
   590	      }
   591	
   592	  template<typename _CharT, typename _Traits, typename _Alloc>
   593	    template <typename _InIterator>
   594	      _CharT*
   595	      basic_string<_CharT, _Traits, _Alloc>::
   596	      _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
   597			   forward_iterator_tag)
   598	      {
   599	#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
   600		if (__beg == __end && __a == _Alloc())
   601		  return _S_empty_rep()._M_refdata();
   602	#endif
   603		// NB: Not required, but considered best practice.
   604		if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
   605		  __throw_logic_error(__N("basic_string::_S_construct null not valid"));
   606	
   607		const size_type __dnew = static_cast<size_type>(std::distance(__beg,
   608									      __end));
   609		// Check for out_of_range and length_error exceptions.
   610		_Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
   611		__try
   612		  { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
   613		__catch(...)
   614		  {
   615		    __r->_M_destroy(__a);
   616		    __throw_exception_again;
   617		  }
   618		__r->_M_set_length_and_sharable(__dnew);
   619		return __r->_M_refdata();
   620	      }
   621	
   622	  template<typename _CharT, typename _Traits, typename _Alloc>
   623	    _CharT*
   624	    basic_string<_CharT, _Traits, _Alloc>::
   625	    _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
   626	    {
   627	#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
   628	      if (__n == 0 && __a == _Alloc())
   629		return _S_empty_rep()._M_refdata();
   630	#endif
   631	      // Check for out_of_range and length_error exceptions.
   632	      _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
   633	      if (__n)
   634		_M_assign(__r->_M_refdata(), __n, __c);
   635	
   636	      __r->_M_set_length_and_sharable(__n);
   637	      return __r->_M_refdata();
   638	    }
   639	
   640	  template<typename _CharT, typename _Traits, typename _Alloc>
   641	    basic_string<_CharT, _Traits, _Alloc>::
   642	    basic_string(const basic_string& __str, size_type __pos, const _Alloc& __a)
   643	    : _M_dataplus(_S_construct(__str._M_data()
   644				       + __str._M_check(__pos,
   645							"basic_string::basic_string"),
   646				       __str._M_data() + __str._M_limit(__pos, npos)
   647				       + __pos, __a), __a)
   648	    { }
   649	
   650	  template<typename _CharT, typename _Traits, typename _Alloc>
   651	    basic_string<_CharT, _Traits, _Alloc>::
   652	    basic_string(const basic_string& __str, size_type __pos, size_type __n)
   653	    : _M_dataplus(_S_construct(__str._M_data()
   654				       + __str._M_check(__pos,
   655							"basic_string::basic_string"),
   656				       __str._M_data() + __str._M_limit(__pos, __n)
   657				       + __pos, _Alloc()), _Alloc())
   658	    { }
   659	
   660	  template<typename _CharT, typename _Traits, typename _Alloc>
   661	    basic_string<_CharT, _Traits, _Alloc>::
   662	    basic_string(const basic_string& __str, size_type __pos,
   663			 size_type __n, const _Alloc& __a)
   664	    : _M_dataplus(_S_construct(__str._M_data()
   665				       + __str._M_check(__pos,
   666							"basic_string::basic_string"),
   667				       __str._M_data() + __str._M_limit(__pos, __n)
   668				       + __pos, __a), __a)
   669	    { }
   670	
   671	  template<typename _CharT, typename _Traits, typename _Alloc>
   672	    basic_string<_CharT, _Traits, _Alloc>&
   673	    basic_string<_CharT, _Traits, _Alloc>::
   674	    assign(const basic_string& __str)
   675	    {
   676	      if (_M_rep() != __str._M_rep())
   677		{
   678		  // XXX MT
   679		  const allocator_type __a = this->get_allocator();
   680		  _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
   681		  _M_rep()->_M_dispose(__a);
   682		  _M_data(__tmp);
   683		}
   684	      return *this;
   685	    }
   686	
   687	  template<typename _CharT, typename _Traits, typename _Alloc>
   688	    basic_string<_CharT, _Traits, _Alloc>&
   689	    basic_string<_CharT, _Traits, _Alloc>::
   690	    assign(const _CharT* __s, size_type __n)
   691	    {
   692	      __glibcxx_requires_string_len(__s, __n);
   693	      _M_check_length(this->size(), __n, "basic_string::assign");
   694	      if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
   695		return _M_replace_safe(size_type(0), this->size(), __s, __n);
   696	      else
   697		{
   698		  // Work in-place.
   699		  const size_type __pos = __s - _M_data();
   700		  if (__pos >= __n)
   701		    _M_copy(_M_data(), __s, __n);
   702		  else if (__pos)
   703		    _M_move(_M_data(), __s, __n);
   704		  _M_rep()->_M_set_length_and_sharable(__n);
   705		  return *this;
   706		}
   707	     }
   708	
   709	  template<typename _CharT, typename _Traits, typename _Alloc>
   710	    basic_string<_CharT, _Traits, _Alloc>&
   711	    basic_string<_CharT, _Traits, _Alloc>::
   712	    append(size_type __n, _CharT __c)
   713	    {
   714	      if (__n)
   715		{
   716		  _M_check_length(size_type(0), __n, "basic_string::append");	  
   717		  const size_type __len = __n + this->size();
   718		  if (__len > this->capacity() || _M_rep()->_M_is_shared())
   719		    this->reserve(__len);
   720		  _M_assign(_M_data() + this->size(), __n, __c);
   721		  _M_rep()->_M_set_length_and_sharable(__len);
   722		}
   723	      return *this;
   724	    }
   725	
   726	  template<typename _CharT, typename _Traits, typename _Alloc>
   727	    basic_string<_CharT, _Traits, _Alloc>&
   728	    basic_string<_CharT, _Traits, _Alloc>::
   729	    append(const _CharT* __s, size_type __n)
   730	    {
   731	      __glibcxx_requires_string_len(__s, __n);
   732	      if (__n)
   733		{
   734		  _M_check_length(size_type(0), __n, "basic_string::append");
   735		  const size_type __len = __n + this->size();
   736		  if (__len > this->capacity() || _M_rep()->_M_is_shared())
   737		    {
   738		      if (_M_disjunct(__s))
   739			this->reserve(__len);
   740		      else
   741			{
   742			  const size_type __off = __s - _M_data();
   743			  this->reserve(__len);
   744			  __s = _M_data() + __off;
   745			}
   746		    }
   747		  _M_copy(_M_data() + this->size(), __s, __n);
   748		  _M_rep()->_M_set_length_and_sharable(__len);
   749		}
   750	      return *this;
   751	    }
   752	
   753	  template<typename _CharT, typename _Traits, typename _Alloc>
   754	    basic_string<_CharT, _Traits, _Alloc>&
   755	    basic_string<_CharT, _Traits, _Alloc>::
   756	    append(const basic_string& __str)
   757	    {
   758	      const size_type __size = __str.size();
   759	      if (__size)
   760		{
   761		  const size_type __len = __size + this->size();
   762		  if (__len > this->capacity() || _M_rep()->_M_is_shared())
   763		    this->reserve(__len);
   764		  _M_copy(_M_data() + this->size(), __str._M_data(), __size);
   765		  _M_rep()->_M_set_length_and_sharable(__len);
   766		}
   767	      return *this;
   768	    }    
   769	
   770	  template<typename _CharT, typename _Traits, typename _Alloc>
   771	    basic_string<_CharT, _Traits, _Alloc>&
   772	    basic_string<_CharT, _Traits, _Alloc>::
   773	    append(const basic_string& __str, size_type __pos, size_type __n)
   774	    {
   775	      __str._M_check(__pos, "basic_string::append");
   776	      __n = __str._M_limit(__pos, __n);
   777	      if (__n)
   778		{
   779		  const size_type __len = __n + this->size();
   780		  if (__len > this->capacity() || _M_rep()->_M_is_shared())
   781		    this->reserve(__len);
   782		  _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n);
   783		  _M_rep()->_M_set_length_and_sharable(__len);	  
   784		}
   785	      return *this;
   786	    }
   787	
   788	   template<typename _CharT, typename _Traits, typename _Alloc>
   789	     basic_string<_CharT, _Traits, _Alloc>&
   790	     basic_string<_CharT, _Traits, _Alloc>::
   791	     insert(size_type __pos, const _CharT* __s, size_type __n)
   792	     {
   793	       __glibcxx_requires_string_len(__s, __n);
   794	       _M_check(__pos, "basic_string::insert");
   795	       _M_check_length(size_type(0), __n, "basic_string::insert");
   796	       if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
   797	         return _M_replace_safe(__pos, size_type(0), __s, __n);
   798	       else
   799	         {
   800	           // Work in-place.
   801	           const size_type __off = __s - _M_data();
   802	           _M_mutate(__pos, 0, __n);
   803	           __s = _M_data() + __off;
   804	           _CharT* __p = _M_data() + __pos;
   805	           if (__s  + __n <= __p)
   806	             _M_copy(__p, __s, __n);
   807	           else if (__s >= __p)
   808	             _M_copy(__p, __s + __n, __n);
   809	           else
   810	             {
   811		       const size_type __nleft = __p - __s;
   812	               _M_copy(__p, __s, __nleft);
   813	               _M_copy(__p + __nleft, __p + __n, __n - __nleft);
   814	             }
   815	           return *this;
   816	         }
   817	     }
   818	
   819	   template<typename _CharT, typename _Traits, typename _Alloc>
   820	     typename basic_string<_CharT, _Traits, _Alloc>::iterator
   821	     basic_string<_CharT, _Traits, _Alloc>::
   822	     erase(iterator __first, iterator __last)
   823	     {
   824	       _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
   825					&& __last <= _M_iend());
   826	
   827	       // NB: This isn't just an optimization (bail out early when
   828	       // there is nothing to do, really), it's also a correctness
   829	       // issue vs MT, see libstdc++/40518.
   830	       const size_type __size = __last - __first;
   831	       if (__size)
   832		 {
   833		   const size_type __pos = __first - _M_ibegin();
   834		   _M_mutate(__pos, __size, size_type(0));
   835		   _M_rep()->_M_set_leaked();
   836		   return iterator(_M_data() + __pos);
   837		 }
   838	       else
   839		 return __first;
   840	     }
   841	
   842	   template<typename _CharT, typename _Traits, typename _Alloc>
   843	     basic_string<_CharT, _Traits, _Alloc>&
   844	     basic_string<_CharT, _Traits, _Alloc>::
   845	     replace(size_type __pos, size_type __n1, const _CharT* __s,
   846		     size_type __n2)
   847	     {
   848	       __glibcxx_requires_string_len(__s, __n2);
   849	       _M_check(__pos, "basic_string::replace");
   850	       __n1 = _M_limit(__pos, __n1);
   851	       _M_check_length(__n1, __n2, "basic_string::replace");
   852	       bool __left;
   853	       if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
   854	         return _M_replace_safe(__pos, __n1, __s, __n2);
   855	       else if ((__left = __s + __n2 <= _M_data() + __pos)
   856			|| _M_data() + __pos + __n1 <= __s)
   857		 {
   858		   // Work in-place: non-overlapping case.
   859		   size_type __off = __s - _M_data();
   860		   __left ? __off : (__off += __n2 - __n1);
   861		   _M_mutate(__pos, __n1, __n2);
   862		   _M_copy(_M_data() + __pos, _M_data() + __off, __n2);
   863		   return *this;
   864		 }
   865	       else
   866		 {
   867		   // Todo: overlapping case.
   868		   const basic_string __tmp(__s, __n2);
   869		   return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
   870		 }
   871	     }
   872	
   873	  template<typename _CharT, typename _Traits, typename _Alloc>
   874	    void
   875	    basic_string<_CharT, _Traits, _Alloc>::_Rep::
   876	    _M_destroy(const _Alloc& __a) throw ()
   877	    {
   878	      const size_type __size = sizeof(_Rep_base) +
   879		                       (this->_M_capacity + 1) * sizeof(_CharT);
   880	      _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
   881	    }
   882	
   883	  template<typename _CharT, typename _Traits, typename _Alloc>
   884	    void
   885	    basic_string<_CharT, _Traits, _Alloc>::
   886	    _M_leak_hard()
   887	    {
   888	#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
   889	      if (_M_rep() == &_S_empty_rep())
   890		return;
   891	#endif
   892	      if (_M_rep()->_M_is_shared())
   893		_M_mutate(0, 0, 0);
   894	      _M_rep()->_M_set_leaked();
   895	    }
   896	
   897	  template<typename _CharT, typename _Traits, typename _Alloc>
   898	    void
   899	    basic_string<_CharT, _Traits, _Alloc>::
   900	    _M_mutate(size_type __pos, size_type __len1, size_type __len2)
   901	    {
   902	      const size_type __old_size = this->size();
   903	      const size_type __new_size = __old_size + __len2 - __len1;
   904	      const size_type __how_much = __old_size - __pos - __len1;
   905	
   906	      if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
   907		{
   908		  // Must reallocate.
   909		  const allocator_type __a = get_allocator();
   910		  _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
   911	
   912		  if (__pos)
   913		    _M_copy(__r->_M_refdata(), _M_data(), __pos);
   914		  if (__how_much)
   915		    _M_copy(__r->_M_refdata() + __pos + __len2,
   916			    _M_data() + __pos + __len1, __how_much);
   917	
   918		  _M_rep()->_M_dispose(__a);
   919		  _M_data(__r->_M_refdata());
   920		}
   921	      else if (__how_much && __len1 != __len2)
   922		{
   923		  // Work in-place.
   924		  _M_move(_M_data() + __pos + __len2,
   925			  _M_data() + __pos + __len1, __how_much);
   926		}
   927	      _M_rep()->_M_set_length_and_sharable(__new_size);
   928	    }
   929	
   930	  template<typename _CharT, typename _Traits, typename _Alloc>
   931	    void
   932	    basic_string<_CharT, _Traits, _Alloc>::
   933	    reserve(size_type __res)
   934	    {
   935	      const size_type __capacity = capacity();
   936	
   937	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
   938	      // 2968. Inconsistencies between basic_string reserve and
   939	      // vector/unordered_map/unordered_set reserve functions
   940	      // P0966 reserve should not shrink
   941	      if (__res <= __capacity)
   942		{
   943		  if (!_M_rep()->_M_is_shared())
   944		    return;
   945	
   946		  // unshare, but keep same capacity
   947		  __res = __capacity;
   948		}
   949	
   950	      const allocator_type __a = get_allocator();
   951	      _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
   952	      _M_rep()->_M_dispose(__a);
   953	      _M_data(__tmp);
   954	    }
   955	
   956	  template<typename _CharT, typename _Traits, typename _Alloc>
   957	    void
   958	    basic_string<_CharT, _Traits, _Alloc>::
   959	    swap(basic_string& __s)
   960	    _GLIBCXX_NOEXCEPT_IF(allocator_traits<_Alloc>::is_always_equal::value)
   961	    {
   962	      if (_M_rep()->_M_is_leaked())
   963		_M_rep()->_M_set_sharable();
   964	      if (__s._M_rep()->_M_is_leaked())
   965		__s._M_rep()->_M_set_sharable();
   966	      if (this->get_allocator() == __s.get_allocator())
   967		{
   968		  _CharT* __tmp = _M_data();
   969		  _M_data(__s._M_data());
   970		  __s._M_data(__tmp);
   971		}
   972	      // The code below can usually be optimized away.
   973	      else
   974		{
   975		  const basic_string __tmp1(_M_ibegin(), _M_iend(),
   976					    __s.get_allocator());
   977		  const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
   978					    this->get_allocator());
   979		  *this = __tmp2;
   980		  __s = __tmp1;
   981		}
   982	    }
   983	
   984	  template<typename _CharT, typename _Traits, typename _Alloc>
   985	    typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
   986	    basic_string<_CharT, _Traits, _Alloc>::_Rep::
   987	    _S_create(size_type __capacity, size_type __old_capacity,
   988		      const _Alloc& __alloc)
   989	    {
   990	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
   991	      // 83.  String::npos vs. string::max_size()
   992	      if (__capacity > _S_max_size)
   993		__throw_length_error(__N("basic_string::_S_create"));
   994	
   995	      // The standard places no restriction on allocating more memory
   996	      // than is strictly needed within this layer at the moment or as
   997	      // requested by an explicit application call to reserve(n).
   998	
   999	      // Many malloc implementations perform quite poorly when an
  1000	      // application attempts to allocate memory in a stepwise fashion
  1001	      // growing each allocation size by only 1 char.  Additionally,
  1002	      // it makes little sense to allocate less linear memory than the
  1003	      // natural blocking size of the malloc implementation.
  1004	      // Unfortunately, we would need a somewhat low-level calculation
  1005	      // with tuned parameters to get this perfect for any particular
  1006	      // malloc implementation.  Fortunately, generalizations about
  1007	      // common features seen among implementations seems to suffice.
  1008	
  1009	      // __pagesize need not match the actual VM page size for good
  1010	      // results in practice, thus we pick a common value on the low
  1011	      // side.  __malloc_header_size is an estimate of the amount of
  1012	      // overhead per memory allocation (in practice seen N * sizeof
  1013	      // (void*) where N is 0, 2 or 4).  According to folklore,
  1014	      // picking this value on the high side is better than
  1015	      // low-balling it (especially when this algorithm is used with
  1016	      // malloc implementations that allocate memory blocks rounded up
  1017	      // to a size which is a power of 2).
  1018	      const size_type __pagesize = 4096;
  1019	      const size_type __malloc_header_size = 4 * sizeof(void*);
  1020	
  1021	      // The below implements an exponential growth policy, necessary to
  1022	      // meet amortized linear time requirements of the library: see
  1023	      // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
  1024	      // It's active for allocations requiring an amount of memory above
  1025	      // system pagesize. This is consistent with the requirements of the
  1026	      // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
  1027	      if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
  1028		__capacity = 2 * __old_capacity;
  1029	
  1030	      // NB: Need an array of char_type[__capacity], plus a terminating
  1031	      // null char_type() element, plus enough for the _Rep data structure.
  1032	      // Whew. Seemingly so needy, yet so elemental.
  1033	      size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
  1034	
  1035	      const size_type __adj_size = __size + __malloc_header_size;
  1036	      if (__adj_size > __pagesize && __capacity > __old_capacity)
  1037		{
  1038		  const size_type __extra = __pagesize - __adj_size % __pagesize;
  1039		  __capacity += __extra / sizeof(_CharT);
  1040		  // Never allocate a string bigger than _S_max_size.
  1041		  if (__capacity > _S_max_size)
  1042		    __capacity = _S_max_size;
  1043		  __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
  1044		}
  1045	
  1046	      // NB: Might throw, but no worries about a leak, mate: _Rep()
  1047	      // does not throw.
  1048	      void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
  1049	      _Rep *__p = new (__place) _Rep;
  1050	      __p->_M_capacity = __capacity;
  1051	      // ABI compatibility - 3.4.x set in _S_create both
  1052	      // _M_refcount and _M_length.  All callers of _S_create
  1053	      // in basic_string.tcc then set just _M_length.
  1054	      // In 4.0.x and later both _M_refcount and _M_length
  1055	      // are initialized in the callers, unfortunately we can
  1056	      // have 3.4.x compiled code with _S_create callers inlined
  1057	      // calling 4.0.x+ _S_create.
  1058	      __p->_M_set_sharable();
  1059	      return __p;
  1060	    }
  1061	
  1062	  template<typename _CharT, typename _Traits, typename _Alloc>
  1063	    _CharT*
  1064	    basic_string<_CharT, _Traits, _Alloc>::_Rep::
  1065	    _M_clone(const _Alloc& __alloc, size_type __res)
  1066	    {
  1067	      // Requested capacity of the clone.
  1068	      const size_type __requested_cap = this->_M_length + __res;
  1069	      _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
  1070					  __alloc);
  1071	      if (this->_M_length)
  1072		_M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
  1073	
  1074	      __r->_M_set_length_and_sharable(this->_M_length);
  1075	      return __r->_M_refdata();
  1076	    }
  1077	
  1078	  template<typename _CharT, typename _Traits, typename _Alloc>
  1079	    void
  1080	    basic_string<_CharT, _Traits, _Alloc>::
  1081	    resize(size_type __n, _CharT __c)
  1082	    {
  1083	      const size_type __size = this->size();
  1084	      _M_check_length(__size, __n, "basic_string::resize");
  1085	      if (__size < __n)
  1086		this->append(__n - __size, __c);
  1087	      else if (__n < __size)
  1088		this->erase(__n);
  1089	      // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
  1090	    }
  1091	
  1092	  template<typename _CharT, typename _Traits, typename _Alloc>
  1093	    template<typename _InputIterator>
  1094	      basic_string<_CharT, _Traits, _Alloc>&
  1095	      basic_string<_CharT, _Traits, _Alloc>::
  1096	      _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
  1097				  _InputIterator __k2, __false_type)
  1098	      {
  1099		const basic_string __s(__k1, __k2);
  1100		const size_type __n1 = __i2 - __i1;
  1101		_M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
  1102		return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
  1103				       __s.size());
  1104	      }
  1105	
  1106	  template<typename _CharT, typename _Traits, typename _Alloc>
  1107	    basic_string<_CharT, _Traits, _Alloc>&
  1108	    basic_string<_CharT, _Traits, _Alloc>::
  1109	    _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
  1110			   _CharT __c)
  1111	    {
  1112	      _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
  1113	      _M_mutate(__pos1, __n1, __n2);
  1114	      if (__n2)
  1115		_M_assign(_M_data() + __pos1, __n2, __c);
  1116	      return *this;
  1117	    }
  1118	
  1119	  template<typename _CharT, typename _Traits, typename _Alloc>
  1120	    basic_string<_CharT, _Traits, _Alloc>&
  1121	    basic_string<_CharT, _Traits, _Alloc>::
  1122	    _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
  1123			    size_type __n2)
  1124	    {
  1125	      _M_mutate(__pos1, __n1, __n2);
  1126	      if (__n2)
  1127		_M_copy(_M_data() + __pos1, __s, __n2);
  1128	      return *this;
  1129	    }
  1130	
  1131	  template<typename _CharT, typename _Traits, typename _Alloc>
  1132	    void
  1133	    basic_string<_CharT, _Traits, _Alloc>::
  1134	    reserve()
  1135	    {
  1136	#if __cpp_exceptions
  1137	      if (length() < capacity() || _M_rep()->_M_is_shared())
  1138		try
  1139		  {
  1140		    const allocator_type __a = get_allocator();
  1141		    _CharT* __tmp = _M_rep()->_M_clone(__a);
  1142		    _M_rep()->_M_dispose(__a);
  1143		    _M_data(__tmp);
  1144		  }
  1145		catch (const __cxxabiv1::__forced_unwind&)
  1146		  { throw; }
  1147		catch (...)
  1148		  { /* swallow the exception */ }
  1149	#endif
  1150	    }
  1151	
  1152	    template<typename _CharT, typename _Traits, typename _Alloc>
  1153	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
  1154	    basic_string<_CharT, _Traits, _Alloc>::
  1155	    copy(_CharT* __s, size_type __n, size_type __pos) const
  1156	    {
  1157	      _M_check(__pos, "basic_string::copy");
  1158	      __n = _M_limit(__pos, __n);
  1159	      __glibcxx_requires_string_len(__s, __n);
  1160	      if (__n)
  1161		_M_copy(__s, _M_data() + __pos, __n);
  1162	      // 21.3.5.7 par 3: do not append null.  (good.)
  1163	      return __n;
  1164	    }
  1165	#endif  // !_GLIBCXX_USE_CXX11_ABI
  1166	   
  1167	  template<typename _CharT, typename _Traits, typename _Alloc>
  1168	    basic_string<_CharT, _Traits, _Alloc>
  1169	    operator+(const _CharT* __lhs,
  1170		      const basic_string<_CharT, _Traits, _Alloc>& __rhs)
  1171	    {
  1172	      __glibcxx_requires_string(__lhs);
  1173	      typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
  1174	      typedef typename __string_type::size_type	  __size_type;
  1175	      typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
  1176		rebind<_CharT>::other _Char_alloc_type;
  1177	      typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
  1178	      const __size_type __len = _Traits::length(__lhs);
  1179	      __string_type __str(_Alloc_traits::_S_select_on_copy(
  1180	          __rhs.get_allocator()));
  1181	      __str.reserve(__len + __rhs.size());
  1182	      __str.append(__lhs, __len);
  1183	      __str.append(__rhs);
  1184	      return __str;
  1185	    }
  1186	
  1187	  template<typename _CharT, typename _Traits, typename _Alloc>
  1188	    basic_string<_CharT, _Traits, _Alloc>
  1189	    operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
  1190	    {
  1191	      typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
  1192	      typedef typename __string_type::size_type	  __size_type;
  1193	      typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
  1194		rebind<_CharT>::other _Char_alloc_type;
  1195	      typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
  1196	      __string_type __str(_Alloc_traits::_S_select_on_copy(
  1197	          __rhs.get_allocator()));
  1198	      const __size_type __len = __rhs.size();
  1199	      __str.reserve(__len + 1);
  1200	      __str.append(__size_type(1), __lhs);
  1201	      __str.append(__rhs);
  1202	      return __str;
  1203	    }
  1204	
  1205	  template<typename _CharT, typename _Traits, typename _Alloc>
  1206	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
  1207	    basic_string<_CharT, _Traits, _Alloc>::
  1208	    find(const _CharT* __s, size_type __pos, size_type __n) const
  1209	    _GLIBCXX_NOEXCEPT
  1210	    {
  1211	      __glibcxx_requires_string_len(__s, __n);
  1212	      const size_type __size = this->size();
  1213	
  1214	      if (__n == 0)
  1215		return __pos <= __size ? __pos : npos;
  1216	      if (__pos >= __size)
  1217		return npos;
  1218	
  1219	      const _CharT __elem0 = __s[0];
  1220	      const _CharT* const __data = data();
  1221	      const _CharT* __first = __data + __pos;
  1222	      const _CharT* const __last = __data + __size;
  1223	      size_type __len = __size - __pos;
  1224	
  1225	      while (__len >= __n)
  1226		{
  1227		  // Find the first occurrence of __elem0:
  1228		  __first = traits_type::find(__first, __len - __n + 1, __elem0);
  1229		  if (!__first)
  1230		    return npos;
  1231		  // Compare the full strings from the first occurrence of __elem0.
  1232		  // We already know that __first[0] == __s[0] but compare them again
  1233		  // anyway because __s is probably aligned, which helps memcmp.
  1234		  if (traits_type::compare(__first, __s, __n) == 0)
  1235		    return __first - __data;
  1236		  __len = __last - ++__first;
  1237		}
  1238	      return npos;
  1239	    }
  1240	
  1241	  template<typename _CharT, typename _Traits, typename _Alloc>
  1242	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
  1243	    basic_string<_CharT, _Traits, _Alloc>::
  1244	    find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
  1245	    {
  1246	      size_type __ret = npos;
  1247	      const size_type __size = this->size();
  1248	      if (__pos < __size)
  1249		{
  1250		  const _CharT* __data = _M_data();
  1251		  const size_type __n = __size - __pos;
  1252		  const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
  1253		  if (__p)
  1254		    __ret = __p - __data;
  1255		}
  1256	      return __ret;
  1257	    }
  1258	
  1259	  template<typename _CharT, typename _Traits, typename _Alloc>
  1260	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
  1261	    basic_string<_CharT, _Traits, _Alloc>::
  1262	    rfind(const _CharT* __s, size_type __pos, size_type __n) const
  1263	    _GLIBCXX_NOEXCEPT
  1264	    {
  1265	      __glibcxx_requires_string_len(__s, __n);
  1266	      const size_type __size = this->size();
  1267	      if (__n <= __size)
  1268		{
  1269		  __pos = std::min(size_type(__size - __n), __pos);
  1270		  const _CharT* __data = _M_data();
  1271		  do
  1272		    {
  1273		      if (traits_type::compare(__data + __pos, __s, __n) == 0)
  1274			return __pos;
  1275		    }
  1276		  while (__pos-- > 0);
  1277		}
  1278	      return npos;
  1279	    }
  1280	
  1281	  template<typename _CharT, typename _Traits, typename _Alloc>
  1282	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
  1283	    basic_string<_CharT, _Traits, _Alloc>::
  1284	    rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
  1285	    {
  1286	      size_type __size = this->size();
  1287	      if (__size)
  1288		{
  1289		  if (--__size > __pos)
  1290		    __size = __pos;
  1291		  for (++__size; __size-- > 0; )
  1292		    if (traits_type::eq(_M_data()[__size], __c))
  1293		      return __size;
  1294		}
  1295	      return npos;
  1296	    }
  1297	
  1298	  template<typename _CharT, typename _Traits, typename _Alloc>
  1299	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
  1300	    basic_string<_CharT, _Traits, _Alloc>::
  1301	    find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
  1302	    _GLIBCXX_NOEXCEPT
  1303	    {
  1304	      __glibcxx_requires_string_len(__s, __n);
  1305	      for (; __n && __pos < this->size(); ++__pos)
  1306		{
  1307		  const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
  1308		  if (__p)
  1309		    return __pos;
  1310		}
  1311	      return npos;
  1312	    }
  1313	
  1314	  template<typename _CharT, typename _Traits, typename _Alloc>
  1315	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
  1316	    basic_string<_CharT, _Traits, _Alloc>::
  1317	    find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
  1318	    _GLIBCXX_NOEXCEPT
  1319	    {
  1320	      __glibcxx_requires_string_len(__s, __n);
  1321	      size_type __size = this->size();
  1322	      if (__size && __n)
  1323		{
  1324		  if (--__size > __pos)
  1325		    __size = __pos;
  1326		  do
  1327		    {
  1328		      if (traits_type::find(__s, __n, _M_data()[__size]))
  1329			return __size;
  1330		    }
  1331		  while (__size-- != 0);
  1332		}
  1333	      return npos;
  1334	    }
  1335	
  1336	  template<typename _CharT, typename _Traits, typename _Alloc>
  1337	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
  1338	    basic_string<_CharT, _Traits, _Alloc>::
  1339	    find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
  1340	    _GLIBCXX_NOEXCEPT
  1341	    {
  1342	      __glibcxx_requires_string_len(__s, __n);
  1343	      for (; __pos < this->size(); ++__pos)
  1344		if (!traits_type::find(__s, __n, _M_data()[__pos]))
  1345		  return __pos;
  1346	      return npos;
  1347	    }
  1348	
  1349	  template<typename _CharT, typename _Traits, typename _Alloc>
  1350	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
  1351	    basic_string<_CharT, _Traits, _Alloc>::
  1352	    find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
  1353	    {
  1354	      for (; __pos < this->size(); ++__pos)
  1355		if (!traits_type::eq(_M_data()[__pos], __c))
  1356		  return __pos;
  1357	      return npos;
  1358	    }
  1359	
  1360	  template<typename _CharT, typename _Traits, typename _Alloc>
  1361	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
  1362	    basic_string<_CharT, _Traits, _Alloc>::
  1363	    find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
  1364	    _GLIBCXX_NOEXCEPT
  1365	    {
  1366	      __glibcxx_requires_string_len(__s, __n);
  1367	      size_type __size = this->size();
  1368	      if (__size)
  1369		{
  1370		  if (--__size > __pos)
  1371		    __size = __pos;
  1372		  do
  1373		    {
  1374		      if (!traits_type::find(__s, __n, _M_data()[__size]))
  1375			return __size;
  1376		    }
  1377		  while (__size--);
  1378		}
  1379	      return npos;
  1380	    }
  1381	
  1382	  template<typename _CharT, typename _Traits, typename _Alloc>
  1383	    typename basic_string<_CharT, _Traits, _Alloc>::size_type
  1384	    basic_string<_CharT, _Traits, _Alloc>::
  1385	    find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
  1386	    {
  1387	      size_type __size = this->size();
  1388	      if (__size)
  1389		{
  1390		  if (--__size > __pos)
  1391		    __size = __pos;
  1392		  do
  1393		    {
  1394		      if (!traits_type::eq(_M_data()[__size], __c))
  1395			return __size;
  1396		    }
  1397		  while (__size--);
  1398		}
  1399	      return npos;
  1400	    }
  1401	
  1402	  template<typename _CharT, typename _Traits, typename _Alloc>
  1403	    int
  1404	    basic_string<_CharT, _Traits, _Alloc>::
  1405	    compare(size_type __pos, size_type __n, const basic_string& __str) const
  1406	    {
  1407	      _M_check(__pos, "basic_string::compare");
  1408	      __n = _M_limit(__pos, __n);
  1409	      const size_type __osize = __str.size();
  1410	      const size_type __len = std::min(__n, __osize);
  1411	      int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
  1412	      if (!__r)
  1413		__r = _S_compare(__n, __osize);
  1414	      return __r;
  1415	    }
  1416	
  1417	  template<typename _CharT, typename _Traits, typename _Alloc>
  1418	    int
  1419	    basic_string<_CharT, _Traits, _Alloc>::
  1420	    compare(size_type __pos1, size_type __n1, const basic_string& __str,
  1421		    size_type __pos2, size_type __n2) const
  1422	    {
  1423	      _M_check(__pos1, "basic_string::compare");
  1424	      __str._M_check(__pos2, "basic_string::compare");
  1425	      __n1 = _M_limit(__pos1, __n1);
  1426	      __n2 = __str._M_limit(__pos2, __n2);
  1427	      const size_type __len = std::min(__n1, __n2);
  1428	      int __r = traits_type::compare(_M_data() + __pos1,
  1429					     __str.data() + __pos2, __len);
  1430	      if (!__r)
  1431		__r = _S_compare(__n1, __n2);
  1432	      return __r;
  1433	    }
  1434	
  1435	  template<typename _CharT, typename _Traits, typename _Alloc>
  1436	    int
  1437	    basic_string<_CharT, _Traits, _Alloc>::
  1438	    compare(const _CharT* __s) const _GLIBCXX_NOEXCEPT
  1439	    {
  1440	      __glibcxx_requires_string(__s);
  1441	      const size_type __size = this->size();
  1442	      const size_type __osize = traits_type::length(__s);
  1443	      const size_type __len = std::min(__size, __osize);
  1444	      int __r = traits_type::compare(_M_data(), __s, __len);
  1445	      if (!__r)
  1446		__r = _S_compare(__size, __osize);
  1447	      return __r;
  1448	    }
  1449	
  1450	  template<typename _CharT, typename _Traits, typename _Alloc>
  1451	    int
  1452	    basic_string <_CharT, _Traits, _Alloc>::
  1453	    compare(size_type __pos, size_type __n1, const _CharT* __s) const
  1454	    {
  1455	      __glibcxx_requires_string(__s);
  1456	      _M_check(__pos, "basic_string::compare");
  1457	      __n1 = _M_limit(__pos, __n1);
  1458	      const size_type __osize = traits_type::length(__s);
  1459	      const size_type __len = std::min(__n1, __osize);
  1460	      int __r = traits_type::compare(_M_data() + __pos, __s, __len);
  1461	      if (!__r)
  1462		__r = _S_compare(__n1, __osize);
  1463	      return __r;
  1464	    }
  1465	
  1466	  template<typename _CharT, typename _Traits, typename _Alloc>
  1467	    int
  1468	    basic_string <_CharT, _Traits, _Alloc>::
  1469	    compare(size_type __pos, size_type __n1, const _CharT* __s,
  1470		    size_type __n2) const
  1471	    {
  1472	      __glibcxx_requires_string_len(__s, __n2);
  1473	      _M_check(__pos, "basic_string::compare");
  1474	      __n1 = _M_limit(__pos, __n1);
  1475	      const size_type __len = std::min(__n1, __n2);
  1476	      int __r = traits_type::compare(_M_data() + __pos, __s, __len);
  1477	      if (!__r)
  1478		__r = _S_compare(__n1, __n2);
  1479	      return __r;
  1480	    }
  1481	
  1482	  // 21.3.7.9 basic_string::getline and operators
  1483	  template<typename _CharT, typename _Traits, typename _Alloc>
  1484	    basic_istream<_CharT, _Traits>&
  1485	    operator>>(basic_istream<_CharT, _Traits>& __in,
  1486		       basic_string<_CharT, _Traits, _Alloc>& __str)
  1487	    {
  1488	      typedef basic_istream<_CharT, _Traits>		__istream_type;
  1489	      typedef basic_string<_CharT, _Traits, _Alloc>	__string_type;
  1490	      typedef typename __istream_type::ios_base         __ios_base;
  1491	      typedef typename __istream_type::int_type		__int_type;
  1492	      typedef typename __string_type::size_type		__size_type;
  1493	      typedef ctype<_CharT>				__ctype_type;
  1494	      typedef typename __ctype_type::ctype_base         __ctype_base;
  1495	
  1496	      __size_type __extracted = 0;
  1497	      typename __ios_base::iostate __err = __ios_base::goodbit;
  1498	      typename __istream_type::sentry __cerb(__in, false);
  1499	      if (__cerb)
  1500		{
  1501		  __try
  1502		    {
  1503		      // Avoid reallocation for common case.
  1504		      __str.erase();
  1505		      _CharT __buf[128];
  1506		      __size_type __len = 0;	      
  1507		      const streamsize __w = __in.width();
  1508		      const __size_type __n = __w > 0 ? static_cast<__size_type>(__w)
  1509			                              : __str.max_size();
  1510		      const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc());
  1511		      const __int_type __eof = _Traits::eof();
  1512		      __int_type __c = __in.rdbuf()->sgetc();
  1513	
  1514		      while (__extracted < __n
  1515			     && !_Traits::eq_int_type(__c, __eof)
  1516			     && !__ct.is(__ctype_base::space,
  1517					 _Traits::to_char_type(__c)))
  1518			{
  1519			  if (__len == sizeof(__buf) / sizeof(_CharT))
  1520			    {
  1521			      __str.append(__buf, sizeof(__buf) / sizeof(_CharT));
  1522			      __len = 0;
  1523			    }
  1524			  __buf[__len++] = _Traits::to_char_type(__c);
  1525			  ++__extracted;
  1526			  __c = __in.rdbuf()->snextc();
  1527			}
  1528		      __str.append(__buf, __len);
  1529	
  1530		      if (__extracted < __n && _Traits::eq_int_type(__c, __eof))
  1531			__err |= __ios_base::eofbit;
  1532		      __in.width(0);
  1533		    }
  1534		  __catch(__cxxabiv1::__forced_unwind&)
  1535		    {
  1536		      __in._M_setstate(__ios_base::badbit);
  1537		      __throw_exception_again;
  1538		    }
  1539		  __catch(...)
  1540		    {
  1541		      // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1542		      // 91. Description of operator>> and getline() for string<>
  1543		      // might cause endless loop
  1544		      __in._M_setstate(__ios_base::badbit);
  1545		    }
  1546		}
  1547	      // 211.  operator>>(istream&, string&) doesn't set failbit
  1548	      if (!__extracted)
  1549		__err |= __ios_base::failbit;
  1550	      if (__err)
  1551		__in.setstate(__err);
  1552	      return __in;
  1553	    }
  1554	
  1555	  template<typename _CharT, typename _Traits, typename _Alloc>
  1556	    basic_istream<_CharT, _Traits>&
  1557	    getline(basic_istream<_CharT, _Traits>& __in,
  1558		    basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
  1559	    {
  1560	      typedef basic_istream<_CharT, _Traits>		__istream_type;
  1561	      typedef basic_string<_CharT, _Traits, _Alloc>	__string_type;
  1562	      typedef typename __istream_type::ios_base         __ios_base;
  1563	      typedef typename __istream_type::int_type		__int_type;
  1564	      typedef typename __string_type::size_type		__size_type;
  1565	
  1566	      __size_type __extracted = 0;
  1567	      const __size_type __n = __str.max_size();
  1568	      typename __ios_base::iostate __err = __ios_base::goodbit;
  1569	      typename __istream_type::sentry __cerb(__in, true);
  1570	      if (__cerb)
  1571		{
  1572		  __try
  1573		    {
  1574		      __str.erase();
  1575		      const __int_type __idelim = _Traits::to_int_type(__delim);
  1576		      const __int_type __eof = _Traits::eof();
  1577		      __int_type __c = __in.rdbuf()->sgetc();
  1578	
  1579		      while (__extracted < __n
  1580			     && !_Traits::eq_int_type(__c, __eof)
  1581			     && !_Traits::eq_int_type(__c, __idelim))
  1582			{
  1583			  __str += _Traits::to_char_type(__c);
  1584			  ++__extracted;
  1585			  __c = __in.rdbuf()->snextc();
  1586			}
  1587	
  1588		      if (_Traits::eq_int_type(__c, __eof))
  1589			__err |= __ios_base::eofbit;
  1590		      else if (_Traits::eq_int_type(__c, __idelim))
  1591			{
  1592			  ++__extracted;		  
  1593			  __in.rdbuf()->sbumpc();
  1594			}
  1595		      else
  1596			__err |= __ios_base::failbit;
  1597		    }
  1598		  __catch(__cxxabiv1::__forced_unwind&)
  1599		    {
  1600		      __in._M_setstate(__ios_base::badbit);
  1601		      __throw_exception_again;
  1602		    }
  1603		  __catch(...)
  1604		    {
  1605		      // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1606		      // 91. Description of operator>> and getline() for string<>
  1607		      // might cause endless loop
  1608		      __in._M_setstate(__ios_base::badbit);
  1609		    }
  1610		}
  1611	      if (!__extracted)
  1612		__err |= __ios_base::failbit;
  1613	      if (__err)
  1614		__in.setstate(__err);
  1615	      return __in;
  1616	    }
  1617	
  1618	  // Inhibit implicit instantiations for required instantiations,
  1619	  // which are defined via explicit instantiations elsewhere.
  1620	#if _GLIBCXX_EXTERN_TEMPLATE
  1621	  // The explicit instantiation definitions in src/c++11/string-inst.cc and
  1622	  // src/c++17/string-inst.cc only instantiate the members required for C++17
  1623	  // and earlier standards (so not C++20's starts_with and ends_with).
  1624	  // Suppress the explicit instantiation declarations for C++20, so C++20
  1625	  // code will implicitly instantiate std::string and std::wstring as needed.
  1626	# if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0
  1627	  extern template class basic_string<char>;
  1628	# elif ! _GLIBCXX_USE_CXX11_ABI
  1629	  // Still need to prevent implicit instantiation of the COW empty rep,
  1630	  // to ensure the definition in libstdc++.so is unique (PR 86138).
  1631	  extern template basic_string<char>::size_type
  1632	    basic_string<char>::_Rep::_S_empty_rep_storage[];
  1633	# endif
  1634	
  1635	  extern template
  1636	    basic_istream<char>&
  1637	    operator>>(basic_istream<char>&, string&);
  1638	  extern template
  1639	    basic_ostream<char>&
  1640	    operator<<(basic_ostream<char>&, const string&);
  1641	  extern template
  1642	    basic_istream<char>&
  1643	    getline(basic_istream<char>&, string&, char);
  1644	  extern template
  1645	    basic_istream<char>&
  1646	    getline(basic_istream<char>&, string&);
  1647	
  1648	#ifdef _GLIBCXX_USE_WCHAR_T
  1649	# if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0
  1650	  extern template class basic_string<wchar_t>;
  1651	# elif ! _GLIBCXX_USE_CXX11_ABI
  1652	  extern template basic_string<wchar_t>::size_type
  1653	    basic_string<wchar_t>::_Rep::_S_empty_rep_storage[];
  1654	# endif
  1655	
  1656	  extern template
  1657	    basic_istream<wchar_t>&
  1658	    operator>>(basic_istream<wchar_t>&, wstring&);
  1659	  extern template
  1660	    basic_ostream<wchar_t>&
  1661	    operator<<(basic_ostream<wchar_t>&, const wstring&);
  1662	  extern template
  1663	    basic_istream<wchar_t>&
  1664	    getline(basic_istream<wchar_t>&, wstring&, wchar_t);
  1665	  extern template
  1666	    basic_istream<wchar_t>&
  1667	    getline(basic_istream<wchar_t>&, wstring&);
  1668	#endif // _GLIBCXX_USE_WCHAR_T
  1669	#endif // _GLIBCXX_EXTERN_TEMPLATE
  1670	
  1671	_GLIBCXX_END_NAMESPACE_VERSION
  1672	} // namespace std
  1673	
  1674	#endif