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