1 // Components for manipulating sequences of characters -*- C++ -*-
2 
3 // Copyright (C) 1997-2018 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 > 0 && __cplusplus <= 201402L
1601   extern template class basic_string<char>;
1602   extern template
1603     basic_istream<char>&
1604     operator>>(basic_istream<char>&, string&);
1605   extern template
1606     basic_ostream<char>&
1607     operator<<(basic_ostream<char>&, const string&);
1608   extern template
1609     basic_istream<char>&
1610     getline(basic_istream<char>&, string&, char);
1611   extern template
1612     basic_istream<char>&
1613     getline(basic_istream<char>&, string&);
1614 
1615 #ifdef _GLIBCXX_USE_WCHAR_T
1616   extern template class basic_string<wchar_t>;
1617   extern template
1618     basic_istream<wchar_t>&
1619     operator>>(basic_istream<wchar_t>&, wstring&);
1620   extern template
1621     basic_ostream<wchar_t>&
1622     operator<<(basic_ostream<wchar_t>&, const wstring&);
1623   extern template
1624     basic_istream<wchar_t>&
1625     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1626   extern template
1627     basic_istream<wchar_t>&
1628     getline(basic_istream<wchar_t>&, wstring&);
1629 #endif
1630 #endif
1631 
1632 _GLIBCXX_END_NAMESPACE_VERSION
1633 } // namespace std
1634 
1635 #endif
1636