libstdc++
basic_string.h
Go to the documentation of this file.
1 // Components for manipulating sequences of characters -*- C++ -*-
2 
3 // Copyright (C) 1997-2015 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.h
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 #ifndef _BASIC_STRING_H
35 #define _BASIC_STRING_H 1
36 
37 #pragma GCC system_header
38 
39 #include <ext/atomicity.h>
40 #include <ext/alloc_traits.h>
41 #include <debug/debug.h>
42 #if __cplusplus >= 201103L
43 #include <initializer_list>
44 #endif
45 
46 namespace std _GLIBCXX_VISIBILITY(default)
47 {
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
49 
50 #if _GLIBCXX_USE_CXX11_ABI
51 _GLIBCXX_BEGIN_NAMESPACE_CXX11
52  /**
53  * @class basic_string basic_string.h <string>
54  * @brief Managing sequences of characters and character-like objects.
55  *
56  * @ingroup strings
57  * @ingroup sequences
58  *
59  * @tparam _CharT Type of character
60  * @tparam _Traits Traits for character type, defaults to
61  * char_traits<_CharT>.
62  * @tparam _Alloc Allocator type, defaults to allocator<_CharT>.
63  *
64  * Meets the requirements of a <a href="tables.html#65">container</a>, a
65  * <a href="tables.html#66">reversible container</a>, and a
66  * <a href="tables.html#67">sequence</a>. Of the
67  * <a href="tables.html#68">optional sequence requirements</a>, only
68  * @c push_back, @c at, and @c %array access are supported.
69  */
70  template<typename _CharT, typename _Traits, typename _Alloc>
71  class basic_string
72  {
74  rebind<_CharT>::other _Char_alloc_type;
75  typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
76 
77  // Types:
78  public:
79  typedef _Traits traits_type;
80  typedef typename _Traits::char_type value_type;
81  typedef _Char_alloc_type allocator_type;
82  typedef typename _Alloc_traits::size_type size_type;
83  typedef typename _Alloc_traits::difference_type difference_type;
84  typedef typename _Alloc_traits::reference reference;
85  typedef typename _Alloc_traits::const_reference const_reference;
86  typedef typename _Alloc_traits::pointer pointer;
87  typedef typename _Alloc_traits::const_pointer const_pointer;
88  typedef __gnu_cxx::__normal_iterator<pointer, basic_string> iterator;
89  typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
90  const_iterator;
91  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
92  typedef std::reverse_iterator<iterator> reverse_iterator;
93 
94  /// Value returned by various member functions when they fail.
95  static const size_type npos = static_cast<size_type>(-1);
96 
97  private:
98  // type used for positions in insert, erase etc.
99 #if __cplusplus < 201103L
100  typedef iterator __const_iterator;
101 #else
102  typedef const_iterator __const_iterator;
103 #endif
104 
105  // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
106  struct _Alloc_hider : allocator_type // TODO check __is_final
107  {
108  _Alloc_hider(pointer __dat, const _Alloc& __a = _Alloc())
109  : allocator_type(__a), _M_p(__dat) { }
110 
111  pointer _M_p; // The actual data.
112  };
113 
114  _Alloc_hider _M_dataplus;
115  size_type _M_string_length;
116 
117  enum { _S_local_capacity = 15 / sizeof(_CharT) };
118 
119  union
120  {
121  _CharT _M_local_buf[_S_local_capacity + 1];
122  size_type _M_allocated_capacity;
123  };
124 
125  void
126  _M_data(pointer __p)
127  { _M_dataplus._M_p = __p; }
128 
129  void
130  _M_length(size_type __length)
131  { _M_string_length = __length; }
132 
133  pointer
134  _M_data() const
135  { return _M_dataplus._M_p; }
136 
137  pointer
138  _M_local_data()
139  {
140 #if __cplusplus >= 201103L
141  return std::pointer_traits<pointer>::pointer_to(*_M_local_buf);
142 #else
143  return pointer(_M_local_buf);
144 #endif
145  }
146 
147  const_pointer
148  _M_local_data() const
149  {
150 #if __cplusplus >= 201103L
152 #else
153  return const_pointer(_M_local_buf);
154 #endif
155  }
156 
157  void
158  _M_capacity(size_type __capacity)
159  { _M_allocated_capacity = __capacity; }
160 
161  void
162  _M_set_length(size_type __n)
163  {
164  _M_length(__n);
165  traits_type::assign(_M_data()[__n], _CharT());
166  }
167 
168  bool
169  _M_is_local() const
170  { return _M_data() == _M_local_data(); }
171 
172  // Create & Destroy
173  pointer
174  _M_create(size_type&, size_type);
175 
176  void
177  _M_dispose()
178  {
179  if (!_M_is_local())
180  _M_destroy(_M_allocated_capacity);
181  }
182 
183  void
184  _M_destroy(size_type __size) throw()
185  { _Alloc_traits::deallocate(_M_get_allocator(), _M_data(), __size + 1); }
186 
187  // _M_construct_aux is used to implement the 21.3.1 para 15 which
188  // requires special behaviour if _InIterator is an integral type
189  template<typename _InIterator>
190  void
191  _M_construct_aux(_InIterator __beg, _InIterator __end,
192  std::__false_type)
193  {
194  typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
195  _M_construct(__beg, __end, _Tag());
196  }
197 
198  // _GLIBCXX_RESOLVE_LIB_DEFECTS
199  // 438. Ambiguity in the "do the right thing" clause
200  template<typename _Integer>
201  void
202  _M_construct_aux(_Integer __beg, _Integer __end, std::__true_type)
203  { _M_construct_aux_2(static_cast<size_type>(__beg), __end); }
204 
205  void
206  _M_construct_aux_2(size_type __req, _CharT __c)
207  { _M_construct(__req, __c); }
208 
209  template<typename _InIterator>
210  void
211  _M_construct(_InIterator __beg, _InIterator __end)
212  {
213  typedef typename std::__is_integer<_InIterator>::__type _Integral;
214  _M_construct_aux(__beg, __end, _Integral());
215  }
216 
217  // For Input Iterators, used in istreambuf_iterators, etc.
218  template<typename _InIterator>
219  void
220  _M_construct(_InIterator __beg, _InIterator __end,
222 
223  // For forward_iterators up to random_access_iterators, used for
224  // string::iterator, _CharT*, etc.
225  template<typename _FwdIterator>
226  void
227  _M_construct(_FwdIterator __beg, _FwdIterator __end,
229 
230  void
231  _M_construct(size_type __req, _CharT __c);
232 
233  allocator_type&
234  _M_get_allocator()
235  { return _M_dataplus; }
236 
237  const allocator_type&
238  _M_get_allocator() const
239  { return _M_dataplus; }
240 
241  private:
242 
243 #ifdef _GLIBCXX_DISAMBIGUATE_REPLACE_INST
244  // The explicit instantiations in misc-inst.cc require this due to
245  // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64063
246  template<typename _Tp, bool _Requires =
247  !__are_same<_Tp, _CharT*>::__value
248  && !__are_same<_Tp, const _CharT*>::__value
249  && !__are_same<_Tp, iterator>::__value
250  && !__are_same<_Tp, const_iterator>::__value>
251  struct __enable_if_not_native_iterator
252  { typedef basic_string& __type; };
253  template<typename _Tp>
254  struct __enable_if_not_native_iterator<_Tp, false> { };
255 #endif
256 
257  size_type
258  _M_check(size_type __pos, const char* __s) const
259  {
260  if (__pos > this->size())
261  __throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "
262  "this->size() (which is %zu)"),
263  __s, __pos, this->size());
264  return __pos;
265  }
266 
267  void
268  _M_check_length(size_type __n1, size_type __n2, const char* __s) const
269  {
270  if (this->max_size() - (this->size() - __n1) < __n2)
271  __throw_length_error(__N(__s));
272  }
273 
274 
275  // NB: _M_limit doesn't check for a bad __pos value.
276  size_type
277  _M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPT
278  {
279  const bool __testoff = __off < this->size() - __pos;
280  return __testoff ? __off : this->size() - __pos;
281  }
282 
283  // True if _Rep and source do not overlap.
284  bool
285  _M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPT
286  {
287  return (less<const _CharT*>()(__s, _M_data())
288  || less<const _CharT*>()(_M_data() + this->size(), __s));
289  }
290 
291  // When __n = 1 way faster than the general multichar
292  // traits_type::copy/move/assign.
293  static void
294  _S_copy(_CharT* __d, const _CharT* __s, size_type __n)
295  {
296  if (__n == 1)
297  traits_type::assign(*__d, *__s);
298  else
299  traits_type::copy(__d, __s, __n);
300  }
301 
302  static void
303  _S_move(_CharT* __d, const _CharT* __s, size_type __n)
304  {
305  if (__n == 1)
306  traits_type::assign(*__d, *__s);
307  else
308  traits_type::move(__d, __s, __n);
309  }
310 
311  static void
312  _S_assign(_CharT* __d, size_type __n, _CharT __c)
313  {
314  if (__n == 1)
315  traits_type::assign(*__d, __c);
316  else
317  traits_type::assign(__d, __n, __c);
318  }
319 
320  // _S_copy_chars is a separate template to permit specialization
321  // to optimize for the common case of pointers as iterators.
322  template<class _Iterator>
323  static void
324  _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
325  {
326  for (; __k1 != __k2; ++__k1, ++__p)
327  traits_type::assign(*__p, *__k1); // These types are off.
328  }
329 
330  static void
331  _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) _GLIBCXX_NOEXCEPT
332  { _S_copy_chars(__p, __k1.base(), __k2.base()); }
333 
334  static void
335  _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
336  _GLIBCXX_NOEXCEPT
337  { _S_copy_chars(__p, __k1.base(), __k2.base()); }
338 
339  static void
340  _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) _GLIBCXX_NOEXCEPT
341  { _S_copy(__p, __k1, __k2 - __k1); }
342 
343  static void
344  _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
345  _GLIBCXX_NOEXCEPT
346  { _S_copy(__p, __k1, __k2 - __k1); }
347 
348  static int
349  _S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPT
350  {
351  const difference_type __d = difference_type(__n1 - __n2);
352 
353  if (__d > __gnu_cxx::__numeric_traits<int>::__max)
354  return __gnu_cxx::__numeric_traits<int>::__max;
355  else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
356  return __gnu_cxx::__numeric_traits<int>::__min;
357  else
358  return int(__d);
359  }
360 
361  void
362  _M_assign(const basic_string& __rcs);
363 
364  void
365  _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
366  size_type __len2);
367 
368  void
369  _M_erase(size_type __pos, size_type __n);
370 
371  public:
372  // Construct/copy/destroy:
373  // NB: We overload ctors in some cases instead of using default
374  // arguments, per 17.4.4.4 para. 2 item 2.
375 
376  /**
377  * @brief Default constructor creates an empty string.
378  */
379  basic_string()
380 #if __cplusplus >= 201103L
381  noexcept(is_nothrow_default_constructible<_Alloc>::value)
382 #endif
383  : _M_dataplus(_M_local_data())
384  { _M_set_length(0); }
385 
386  /**
387  * @brief Construct an empty string using allocator @a a.
388  */
389  explicit
390  basic_string(const _Alloc& __a) _GLIBCXX_NOEXCEPT
391  : _M_dataplus(_M_local_data(), __a)
392  { _M_set_length(0); }
393 
394  /**
395  * @brief Construct string with copy of value of @a __str.
396  * @param __str Source string.
397  */
398  basic_string(const basic_string& __str)
399  : _M_dataplus(_M_local_data(),
400  _Alloc_traits::_S_select_on_copy(__str._M_get_allocator()))
401  { _M_construct(__str._M_data(), __str._M_data() + __str.length()); }
402 
403  /**
404  * @brief Construct string as copy of a substring.
405  * @param __str Source string.
406  * @param __pos Index of first character to copy from.
407  * @param __n Number of characters to copy (default remainder).
408  */
409  // _GLIBCXX_RESOLVE_LIB_DEFECTS
410  // 2402. [this constructor] shouldn't use Allocator()
411  basic_string(const basic_string& __str, size_type __pos,
412  size_type __n = npos)
413  : _M_dataplus(_M_local_data())
414  {
415  const _CharT* __start = __str._M_data()
416  + __str._M_check(__pos, "basic_string::basic_string");
417  _M_construct(__start, __start + __str._M_limit(__pos, __n));
418  }
419 
420  /**
421  * @brief Construct string as copy of a substring.
422  * @param __str Source string.
423  * @param __pos Index of first character to copy from.
424  * @param __n Number of characters to copy (default remainder).
425  * @param __a Allocator to use.
426  */
427  basic_string(const basic_string& __str, size_type __pos,
428  size_type __n, const _Alloc& __a)
429  : _M_dataplus(_M_local_data(), __a)
430  {
431  const _CharT* __start
432  = __str._M_data() + __str._M_check(__pos, "string::string");
433  _M_construct(__start, __start + __str._M_limit(__pos, __n));
434  }
435 
436  /**
437  * @brief Construct string initialized by a character %array.
438  * @param __s Source character %array.
439  * @param __n Number of characters to copy.
440  * @param __a Allocator to use (default is default allocator).
441  *
442  * NB: @a __s must have at least @a __n characters, &apos;\\0&apos;
443  * has no special meaning.
444  */
445  basic_string(const _CharT* __s, size_type __n,
446  const _Alloc& __a = _Alloc())
447  : _M_dataplus(_M_local_data(), __a)
448  { _M_construct(__s, __s + __n); }
449 
450  /**
451  * @brief Construct string as copy of a C string.
452  * @param __s Source C string.
453  * @param __a Allocator to use (default is default allocator).
454  */
455  basic_string(const _CharT* __s, const _Alloc& __a = _Alloc())
456  : _M_dataplus(_M_local_data(), __a)
457  { _M_construct(__s, __s ? __s + traits_type::length(__s) : __s+npos); }
458 
459  /**
460  * @brief Construct string as multiple characters.
461  * @param __n Number of characters.
462  * @param __c Character to use.
463  * @param __a Allocator to use (default is default allocator).
464  */
465  basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc())
466  : _M_dataplus(_M_local_data(), __a)
467  { _M_construct(__n, __c); }
468 
469 #if __cplusplus >= 201103L
470  /**
471  * @brief Move construct string.
472  * @param __str Source string.
473  *
474  * The newly-created string contains the exact contents of @a __str.
475  * @a __str is a valid, but unspecified string.
476  **/
477  basic_string(basic_string&& __str) noexcept
478  : _M_dataplus(_M_local_data(), std::move(__str._M_get_allocator()))
479  {
480  if (__str._M_is_local())
481  {
482  traits_type::copy(_M_local_buf, __str._M_local_buf,
483  _S_local_capacity + 1);
484  }
485  else
486  {
487  _M_data(__str._M_data());
488  _M_capacity(__str._M_allocated_capacity);
489  }
490 
491  // Must use _M_length() here not _M_set_length() because
492  // basic_stringbuf relies on writing into unallocated capacity so
493  // we mess up the contents if we put a '\0' in the string.
494  _M_length(__str.length());
495  __str._M_data(__str._M_local_data());
496  __str._M_set_length(0);
497  }
498 
499  /**
500  * @brief Construct string from an initializer %list.
501  * @param __l std::initializer_list of characters.
502  * @param __a Allocator to use (default is default allocator).
503  */
504  basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc())
505  : _M_dataplus(_M_local_data(), __a)
506  { _M_construct(__l.begin(), __l.end()); }
507 
508  basic_string(const basic_string& __str, const _Alloc& __a)
509  : _M_dataplus(_M_local_data(), __a)
510  { _M_construct(__str.begin(), __str.end()); }
511 
512  basic_string(basic_string&& __str, const _Alloc& __a)
513  noexcept(_Alloc_traits::_S_always_equal())
514  : _M_dataplus(_M_local_data(), __a)
515  {
516  if (__str._M_is_local())
517  {
518  traits_type::copy(_M_local_buf, __str._M_local_buf,
519  _S_local_capacity + 1);
520  _M_length(__str.length());
521  __str._M_set_length(0);
522  }
523  else if (_Alloc_traits::_S_always_equal()
524  || __str.get_allocator() == __a)
525  {
526  _M_data(__str._M_data());
527  _M_length(__str.length());
528  _M_capacity(__str._M_allocated_capacity);
529  __str._M_data(__str._M_local_buf);
530  __str._M_set_length(0);
531  }
532  else
533  _M_construct(__str.begin(), __str.end());
534  }
535 
536 #endif // C++11
537 
538  /**
539  * @brief Construct string as copy of a range.
540  * @param __beg Start of range.
541  * @param __end End of range.
542  * @param __a Allocator to use (default is default allocator).
543  */
544 #if __cplusplus >= 201103L
545  template<typename _InputIterator,
546  typename = std::_RequireInputIter<_InputIterator>>
547 #else
548  template<typename _InputIterator>
549 #endif
550  basic_string(_InputIterator __beg, _InputIterator __end,
551  const _Alloc& __a = _Alloc())
552  : _M_dataplus(_M_local_data(), __a)
553  { _M_construct(__beg, __end); }
554 
555  /**
556  * @brief Destroy the string instance.
557  */
558  ~basic_string()
559  { _M_dispose(); }
560 
561  /**
562  * @brief Assign the value of @a str to this string.
563  * @param __str Source string.
564  */
565  basic_string&
566  operator=(const basic_string& __str)
567  {
568 #if __cplusplus >= 201103L
569  if (_Alloc_traits::_S_propagate_on_copy_assign())
570  {
571  if (!_Alloc_traits::_S_always_equal() && !_M_is_local()
572  && _M_get_allocator() != __str._M_get_allocator())
573  {
574  // Propagating allocator cannot free existing storage so must
575  // deallocate it before replacing current allocator.
576  if (__str.size() <= _S_local_capacity)
577  {
578  _M_destroy(_M_allocated_capacity);
579  _M_data(_M_local_data());
580  _M_set_length(0);
581  }
582  else
583  {
584  const auto __len = __str.size();
585  auto __alloc = __str._M_get_allocator();
586  // If this allocation throws there are no effects:
587  auto __ptr = _Alloc_traits::allocate(__alloc, __len + 1);
588  _M_destroy(_M_allocated_capacity);
589  _M_data(__ptr);
590  _M_capacity(__len);
591  _M_set_length(__len);
592  }
593  }
594  std::__alloc_on_copy(_M_get_allocator(), __str._M_get_allocator());
595  }
596 #endif
597  return this->assign(__str);
598  }
599 
600  /**
601  * @brief Copy contents of @a s into this string.
602  * @param __s Source null-terminated string.
603  */
604  basic_string&
605  operator=(const _CharT* __s)
606  { return this->assign(__s); }
607 
608  /**
609  * @brief Set value to string of length 1.
610  * @param __c Source character.
611  *
612  * Assigning to a character makes this string length 1 and
613  * (*this)[0] == @a c.
614  */
615  basic_string&
616  operator=(_CharT __c)
617  {
618  this->assign(1, __c);
619  return *this;
620  }
621 
622 #if __cplusplus >= 201103L
623  /**
624  * @brief Move assign the value of @a str to this string.
625  * @param __str Source string.
626  *
627  * The contents of @a str are moved into this string (without copying).
628  * @a str is a valid, but unspecified string.
629  **/
630  // PR 58265, this should be noexcept.
631  // _GLIBCXX_RESOLVE_LIB_DEFECTS
632  // 2063. Contradictory requirements for string move assignment
633  basic_string&
634  operator=(basic_string&& __str)
635  noexcept(_Alloc_traits::_S_nothrow_move())
636  {
637  if (!_M_is_local() && _Alloc_traits::_S_propagate_on_move_assign()
638  && !_Alloc_traits::_S_always_equal()
639  && _M_get_allocator() != __str._M_get_allocator())
640  {
641  // Destroy existing storage before replacing allocator.
642  _M_destroy(_M_allocated_capacity);
643  _M_data(_M_local_data());
644  _M_set_length(0);
645  }
646  // Replace allocator if POCMA is true.
647  std::__alloc_on_move(_M_get_allocator(), __str._M_get_allocator());
648 
649  if (!__str._M_is_local()
650  && (_Alloc_traits::_S_propagate_on_move_assign()
651  || _Alloc_traits::_S_always_equal()))
652  {
653  pointer __data = nullptr;
654  size_type __capacity;
655  if (!_M_is_local())
656  {
657  if (_Alloc_traits::_S_always_equal())
658  {
659  __data = _M_data();
660  __capacity = _M_allocated_capacity;
661  }
662  else
663  _M_destroy(_M_allocated_capacity);
664  }
665 
666  _M_data(__str._M_data());
667  _M_length(__str.length());
668  _M_capacity(__str._M_allocated_capacity);
669  if (__data)
670  {
671  __str._M_data(__data);
672  __str._M_capacity(__capacity);
673  }
674  else
675  __str._M_data(__str._M_local_buf);
676  }
677  else
678  assign(__str);
679  __str.clear();
680  return *this;
681  }
682 
683  /**
684  * @brief Set value to string constructed from initializer %list.
685  * @param __l std::initializer_list.
686  */
687  basic_string&
688  operator=(initializer_list<_CharT> __l)
689  {
690  this->assign(__l.begin(), __l.size());
691  return *this;
692  }
693 #endif // C++11
694 
695  // Iterators:
696  /**
697  * Returns a read/write iterator that points to the first character in
698  * the %string.
699  */
700  iterator
701  begin() _GLIBCXX_NOEXCEPT
702  { return iterator(_M_data()); }
703 
704  /**
705  * Returns a read-only (constant) iterator that points to the first
706  * character in the %string.
707  */
708  const_iterator
709  begin() const _GLIBCXX_NOEXCEPT
710  { return const_iterator(_M_data()); }
711 
712  /**
713  * Returns a read/write iterator that points one past the last
714  * character in the %string.
715  */
716  iterator
717  end() _GLIBCXX_NOEXCEPT
718  { return iterator(_M_data() + this->size()); }
719 
720  /**
721  * Returns a read-only (constant) iterator that points one past the
722  * last character in the %string.
723  */
724  const_iterator
725  end() const _GLIBCXX_NOEXCEPT
726  { return const_iterator(_M_data() + this->size()); }
727 
728  /**
729  * Returns a read/write reverse iterator that points to the last
730  * character in the %string. Iteration is done in reverse element
731  * order.
732  */
733  reverse_iterator
734  rbegin() _GLIBCXX_NOEXCEPT
735  { return reverse_iterator(this->end()); }
736 
737  /**
738  * Returns a read-only (constant) reverse iterator that points
739  * to the last character in the %string. Iteration is done in
740  * reverse element order.
741  */
742  const_reverse_iterator
743  rbegin() const _GLIBCXX_NOEXCEPT
744  { return const_reverse_iterator(this->end()); }
745 
746  /**
747  * Returns a read/write reverse iterator that points to one before the
748  * first character in the %string. Iteration is done in reverse
749  * element order.
750  */
751  reverse_iterator
752  rend() _GLIBCXX_NOEXCEPT
753  { return reverse_iterator(this->begin()); }
754 
755  /**
756  * Returns a read-only (constant) reverse iterator that points
757  * to one before the first character in the %string. Iteration
758  * is done in reverse element order.
759  */
760  const_reverse_iterator
761  rend() const _GLIBCXX_NOEXCEPT
762  { return const_reverse_iterator(this->begin()); }
763 
764 #if __cplusplus >= 201103L
765  /**
766  * Returns a read-only (constant) iterator that points to the first
767  * character in the %string.
768  */
769  const_iterator
770  cbegin() const noexcept
771  { return const_iterator(this->_M_data()); }
772 
773  /**
774  * Returns a read-only (constant) iterator that points one past the
775  * last character in the %string.
776  */
777  const_iterator
778  cend() const noexcept
779  { return const_iterator(this->_M_data() + this->size()); }
780 
781  /**
782  * Returns a read-only (constant) reverse iterator that points
783  * to the last character in the %string. Iteration is done in
784  * reverse element order.
785  */
786  const_reverse_iterator
787  crbegin() const noexcept
788  { return const_reverse_iterator(this->end()); }
789 
790  /**
791  * Returns a read-only (constant) reverse iterator that points
792  * to one before the first character in the %string. Iteration
793  * is done in reverse element order.
794  */
795  const_reverse_iterator
796  crend() const noexcept
797  { return const_reverse_iterator(this->begin()); }
798 #endif
799 
800  public:
801  // Capacity:
802  /// Returns the number of characters in the string, not including any
803  /// null-termination.
804  size_type
805  size() const _GLIBCXX_NOEXCEPT
806  { return _M_string_length; }
807 
808  /// Returns the number of characters in the string, not including any
809  /// null-termination.
810  size_type
811  length() const _GLIBCXX_NOEXCEPT
812  { return _M_string_length; }
813 
814  /// Returns the size() of the largest possible %string.
815  size_type
816  max_size() const _GLIBCXX_NOEXCEPT
817  { return (_Alloc_traits::max_size(_M_get_allocator()) - 1) / 2; }
818 
819  /**
820  * @brief Resizes the %string to the specified number of characters.
821  * @param __n Number of characters the %string should contain.
822  * @param __c Character to fill any new elements.
823  *
824  * This function will %resize the %string to the specified
825  * number of characters. If the number is smaller than the
826  * %string's current size the %string is truncated, otherwise
827  * the %string is extended and new elements are %set to @a __c.
828  */
829  void
830  resize(size_type __n, _CharT __c);
831 
832  /**
833  * @brief Resizes the %string to the specified number of characters.
834  * @param __n Number of characters the %string should contain.
835  *
836  * This function will resize the %string to the specified length. If
837  * the new size is smaller than the %string's current size the %string
838  * is truncated, otherwise the %string is extended and new characters
839  * are default-constructed. For basic types such as char, this means
840  * setting them to 0.
841  */
842  void
843  resize(size_type __n)
844  { this->resize(__n, _CharT()); }
845 
846 #if __cplusplus >= 201103L
847  /// A non-binding request to reduce capacity() to size().
848  void
849  shrink_to_fit() noexcept
850  {
851 #if __cpp_exceptions
852  if (capacity() > size())
853  {
854  try
855  { reserve(0); }
856  catch(...)
857  { }
858  }
859 #endif
860  }
861 #endif
862 
863  /**
864  * Returns the total number of characters that the %string can hold
865  * before needing to allocate more memory.
866  */
867  size_type
868  capacity() const _GLIBCXX_NOEXCEPT
869  {
870  return _M_is_local() ? size_type(_S_local_capacity)
871  : _M_allocated_capacity;
872  }
873 
874  /**
875  * @brief Attempt to preallocate enough memory for specified number of
876  * characters.
877  * @param __res_arg Number of characters required.
878  * @throw std::length_error If @a __res_arg exceeds @c max_size().
879  *
880  * This function attempts to reserve enough memory for the
881  * %string to hold the specified number of characters. If the
882  * number requested is more than max_size(), length_error is
883  * thrown.
884  *
885  * The advantage of this function is that if optimal code is a
886  * necessity and the user can determine the string length that will be
887  * required, the user can reserve the memory in %advance, and thus
888  * prevent a possible reallocation of memory and copying of %string
889  * data.
890  */
891  void
892  reserve(size_type __res_arg = 0);
893 
894  /**
895  * Erases the string, making it empty.
896  */
897  void
898  clear() _GLIBCXX_NOEXCEPT
899  { _M_set_length(0); }
900 
901  /**
902  * Returns true if the %string is empty. Equivalent to
903  * <code>*this == ""</code>.
904  */
905  bool
906  empty() const _GLIBCXX_NOEXCEPT
907  { return this->size() == 0; }
908 
909  // Element access:
910  /**
911  * @brief Subscript access to the data contained in the %string.
912  * @param __pos The index of the character to access.
913  * @return Read-only (constant) reference to the character.
914  *
915  * This operator allows for easy, array-style, data access.
916  * Note that data access with this operator is unchecked and
917  * out_of_range lookups are not defined. (For checked lookups
918  * see at().)
919  */
920  const_reference
921  operator[] (size_type __pos) const _GLIBCXX_NOEXCEPT
922  {
923  _GLIBCXX_DEBUG_ASSERT(__pos <= size());
924  return _M_data()[__pos];
925  }
926 
927  /**
928  * @brief Subscript access to the data contained in the %string.
929  * @param __pos The index of the character to access.
930  * @return Read/write reference to the character.
931  *
932  * This operator allows for easy, array-style, data access.
933  * Note that data access with this operator is unchecked and
934  * out_of_range lookups are not defined. (For checked lookups
935  * see at().)
936  */
937  reference
938  operator[](size_type __pos)
939  {
940  // Allow pos == size() both in C++98 mode, as v3 extension,
941  // and in C++11 mode.
942  _GLIBCXX_DEBUG_ASSERT(__pos <= size());
943  // In pedantic mode be strict in C++98 mode.
944  _GLIBCXX_DEBUG_PEDASSERT(__cplusplus >= 201103L || __pos < size());
945  return _M_data()[__pos];
946  }
947 
948  /**
949  * @brief Provides access to the data contained in the %string.
950  * @param __n The index of the character to access.
951  * @return Read-only (const) reference to the character.
952  * @throw std::out_of_range If @a n is an invalid index.
953  *
954  * This function provides for safer data access. The parameter is
955  * first checked that it is in the range of the string. The function
956  * throws out_of_range if the check fails.
957  */
958  const_reference
959  at(size_type __n) const
960  {
961  if (__n >= this->size())
962  __throw_out_of_range_fmt(__N("basic_string::at: __n "
963  "(which is %zu) >= this->size() "
964  "(which is %zu)"),
965  __n, this->size());
966  return _M_data()[__n];
967  }
968 
969  /**
970  * @brief Provides access to the data contained in the %string.
971  * @param __n The index of the character to access.
972  * @return Read/write reference to the character.
973  * @throw std::out_of_range If @a n is an invalid index.
974  *
975  * This function provides for safer data access. The parameter is
976  * first checked that it is in the range of the string. The function
977  * throws out_of_range if the check fails.
978  */
979  reference
980  at(size_type __n)
981  {
982  if (__n >= size())
983  __throw_out_of_range_fmt(__N("basic_string::at: __n "
984  "(which is %zu) >= this->size() "
985  "(which is %zu)"),
986  __n, this->size());
987  return _M_data()[__n];
988  }
989 
990 #if __cplusplus >= 201103L
991  /**
992  * Returns a read/write reference to the data at the first
993  * element of the %string.
994  */
995  reference
996  front() noexcept
997  { return operator[](0); }
998 
999  /**
1000  * Returns a read-only (constant) reference to the data at the first
1001  * element of the %string.
1002  */
1003  const_reference
1004  front() const noexcept
1005  { return operator[](0); }
1006 
1007  /**
1008  * Returns a read/write reference to the data at the last
1009  * element of the %string.
1010  */
1011  reference
1012  back() noexcept
1013  { return operator[](this->size() - 1); }
1014 
1015  /**
1016  * Returns a read-only (constant) reference to the data at the
1017  * last element of the %string.
1018  */
1019  const_reference
1020  back() const noexcept
1021  { return operator[](this->size() - 1); }
1022 #endif
1023 
1024  // Modifiers:
1025  /**
1026  * @brief Append a string to this string.
1027  * @param __str The string to append.
1028  * @return Reference to this string.
1029  */
1030  basic_string&
1031  operator+=(const basic_string& __str)
1032  { return this->append(__str); }
1033 
1034  /**
1035  * @brief Append a C string.
1036  * @param __s The C string to append.
1037  * @return Reference to this string.
1038  */
1039  basic_string&
1040  operator+=(const _CharT* __s)
1041  { return this->append(__s); }
1042 
1043  /**
1044  * @brief Append a character.
1045  * @param __c The character to append.
1046  * @return Reference to this string.
1047  */
1048  basic_string&
1049  operator+=(_CharT __c)
1050  {
1051  this->push_back(__c);
1052  return *this;
1053  }
1054 
1055 #if __cplusplus >= 201103L
1056  /**
1057  * @brief Append an initializer_list of characters.
1058  * @param __l The initializer_list of characters to be appended.
1059  * @return Reference to this string.
1060  */
1061  basic_string&
1062  operator+=(initializer_list<_CharT> __l)
1063  { return this->append(__l.begin(), __l.size()); }
1064 #endif // C++11
1065 
1066  /**
1067  * @brief Append a string to this string.
1068  * @param __str The string to append.
1069  * @return Reference to this string.
1070  */
1071  basic_string&
1072  append(const basic_string& __str)
1073  { return _M_append(__str._M_data(), __str.size()); }
1074 
1075  /**
1076  * @brief Append a substring.
1077  * @param __str The string to append.
1078  * @param __pos Index of the first character of str to append.
1079  * @param __n The number of characters to append.
1080  * @return Reference to this string.
1081  * @throw std::out_of_range if @a __pos is not a valid index.
1082  *
1083  * This function appends @a __n characters from @a __str
1084  * starting at @a __pos to this string. If @a __n is is larger
1085  * than the number of available characters in @a __str, the
1086  * remainder of @a __str is appended.
1087  */
1088  basic_string&
1089  append(const basic_string& __str, size_type __pos, size_type __n)
1090  { return _M_append(__str._M_data()
1091  + __str._M_check(__pos, "basic_string::append"),
1092  __str._M_limit(__pos, __n)); }
1093 
1094  /**
1095  * @brief Append a C substring.
1096  * @param __s The C string to append.
1097  * @param __n The number of characters to append.
1098  * @return Reference to this string.
1099  */
1100  basic_string&
1101  append(const _CharT* __s, size_type __n)
1102  {
1103  __glibcxx_requires_string_len(__s, __n);
1104  _M_check_length(size_type(0), __n, "basic_string::append");
1105  return _M_append(__s, __n);
1106  }
1107 
1108  /**
1109  * @brief Append a C string.
1110  * @param __s The C string to append.
1111  * @return Reference to this string.
1112  */
1113  basic_string&
1114  append(const _CharT* __s)
1115  {
1116  __glibcxx_requires_string(__s);
1117  const size_type __n = traits_type::length(__s);
1118  _M_check_length(size_type(0), __n, "basic_string::append");
1119  return _M_append(__s, __n);
1120  }
1121 
1122  /**
1123  * @brief Append multiple characters.
1124  * @param __n The number of characters to append.
1125  * @param __c The character to use.
1126  * @return Reference to this string.
1127  *
1128  * Appends __n copies of __c to this string.
1129  */
1130  basic_string&
1131  append(size_type __n, _CharT __c)
1132  { return _M_replace_aux(this->size(), size_type(0), __n, __c); }
1133 
1134 #if __cplusplus >= 201103L
1135  /**
1136  * @brief Append an initializer_list of characters.
1137  * @param __l The initializer_list of characters to append.
1138  * @return Reference to this string.
1139  */
1140  basic_string&
1141  append(initializer_list<_CharT> __l)
1142  { return this->append(__l.begin(), __l.size()); }
1143 #endif // C++11
1144 
1145  /**
1146  * @brief Append a range of characters.
1147  * @param __first Iterator referencing the first character to append.
1148  * @param __last Iterator marking the end of the range.
1149  * @return Reference to this string.
1150  *
1151  * Appends characters in the range [__first,__last) to this string.
1152  */
1153 #if __cplusplus >= 201103L
1154  template<class _InputIterator,
1155  typename = std::_RequireInputIter<_InputIterator>>
1156 #else
1157  template<class _InputIterator>
1158 #endif
1159  basic_string&
1160  append(_InputIterator __first, _InputIterator __last)
1161  { return this->replace(end(), end(), __first, __last); }
1162 
1163  /**
1164  * @brief Append a single character.
1165  * @param __c Character to append.
1166  */
1167  void
1168  push_back(_CharT __c)
1169  {
1170  const size_type __size = this->size();
1171  if (__size + 1 > this->capacity())
1172  this->_M_mutate(__size, size_type(0), 0, size_type(1));
1173  traits_type::assign(this->_M_data()[__size], __c);
1174  this->_M_set_length(__size + 1);
1175  }
1176 
1177  /**
1178  * @brief Set value to contents of another string.
1179  * @param __str Source string to use.
1180  * @return Reference to this string.
1181  */
1182  basic_string&
1183  assign(const basic_string& __str)
1184  {
1185  this->_M_assign(__str);
1186  return *this;
1187  }
1188 
1189 #if __cplusplus >= 201103L
1190  /**
1191  * @brief Set value to contents of another string.
1192  * @param __str Source string to use.
1193  * @return Reference to this string.
1194  *
1195  * This function sets this string to the exact contents of @a __str.
1196  * @a __str is a valid, but unspecified string.
1197  */
1198  basic_string&
1199  assign(basic_string&& __str)
1200  noexcept(_Alloc_traits::_S_nothrow_move())
1201  {
1202  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1203  // 2063. Contradictory requirements for string move assignment
1204  return *this = std::move(__str);
1205  }
1206 #endif // C++11
1207 
1208  /**
1209  * @brief Set value to a substring of a string.
1210  * @param __str The string to use.
1211  * @param __pos Index of the first character of str.
1212  * @param __n Number of characters to use.
1213  * @return Reference to this string.
1214  * @throw std::out_of_range if @a pos is not a valid index.
1215  *
1216  * This function sets this string to the substring of @a __str
1217  * consisting of @a __n characters at @a __pos. If @a __n is
1218  * is larger than the number of available characters in @a
1219  * __str, the remainder of @a __str is used.
1220  */
1221  basic_string&
1222  assign(const basic_string& __str, size_type __pos, size_type __n)
1223  { return _M_replace(size_type(0), this->size(), __str._M_data()
1224  + __str._M_check(__pos, "basic_string::assign"),
1225  __str._M_limit(__pos, __n)); }
1226 
1227  /**
1228  * @brief Set value to a C substring.
1229  * @param __s The C string to use.
1230  * @param __n Number of characters to use.
1231  * @return Reference to this string.
1232  *
1233  * This function sets the value of this string to the first @a __n
1234  * characters of @a __s. If @a __n is is larger than the number of
1235  * available characters in @a __s, the remainder of @a __s is used.
1236  */
1237  basic_string&
1238  assign(const _CharT* __s, size_type __n)
1239  {
1240  __glibcxx_requires_string_len(__s, __n);
1241  return _M_replace(size_type(0), this->size(), __s, __n);
1242  }
1243 
1244  /**
1245  * @brief Set value to contents of a C string.
1246  * @param __s The C string to use.
1247  * @return Reference to this string.
1248  *
1249  * This function sets the value of this string to the value of @a __s.
1250  * The data is copied, so there is no dependence on @a __s once the
1251  * function returns.
1252  */
1253  basic_string&
1254  assign(const _CharT* __s)
1255  {
1256  __glibcxx_requires_string(__s);
1257  return _M_replace(size_type(0), this->size(), __s,
1258  traits_type::length(__s));
1259  }
1260 
1261  /**
1262  * @brief Set value to multiple characters.
1263  * @param __n Length of the resulting string.
1264  * @param __c The character to use.
1265  * @return Reference to this string.
1266  *
1267  * This function sets the value of this string to @a __n copies of
1268  * character @a __c.
1269  */
1270  basic_string&
1271  assign(size_type __n, _CharT __c)
1272  { return _M_replace_aux(size_type(0), this->size(), __n, __c); }
1273 
1274  /**
1275  * @brief Set value to a range of characters.
1276  * @param __first Iterator referencing the first character to append.
1277  * @param __last Iterator marking the end of the range.
1278  * @return Reference to this string.
1279  *
1280  * Sets value of string to characters in the range [__first,__last).
1281  */
1282 #if __cplusplus >= 201103L
1283  template<class _InputIterator,
1284  typename = std::_RequireInputIter<_InputIterator>>
1285 #else
1286  template<class _InputIterator>
1287 #endif
1288  basic_string&
1289  assign(_InputIterator __first, _InputIterator __last)
1290  { return this->replace(begin(), end(), __first, __last); }
1291 
1292 #if __cplusplus >= 201103L
1293  /**
1294  * @brief Set value to an initializer_list of characters.
1295  * @param __l The initializer_list of characters to assign.
1296  * @return Reference to this string.
1297  */
1298  basic_string&
1299  assign(initializer_list<_CharT> __l)
1300  { return this->assign(__l.begin(), __l.size()); }
1301 #endif // C++11
1302 
1303 #if __cplusplus >= 201103L
1304  /**
1305  * @brief Insert multiple characters.
1306  * @param __p Const_iterator referencing location in string to
1307  * insert at.
1308  * @param __n Number of characters to insert
1309  * @param __c The character to insert.
1310  * @return Iterator referencing the first inserted char.
1311  * @throw std::length_error If new length exceeds @c max_size().
1312  *
1313  * Inserts @a __n copies of character @a __c starting at the
1314  * position referenced by iterator @a __p. If adding
1315  * characters causes the length to exceed max_size(),
1316  * length_error is thrown. The value of the string doesn't
1317  * change if an error is thrown.
1318  */
1319  iterator
1320  insert(const_iterator __p, size_type __n, _CharT __c)
1321  {
1322  _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1323  const size_type __pos = __p - begin();
1324  this->replace(__p, __p, __n, __c);
1325  return iterator(this->_M_data() + __pos);
1326  }
1327 #else
1328  /**
1329  * @brief Insert multiple characters.
1330  * @param __p Iterator referencing location in string to insert at.
1331  * @param __n Number of characters to insert
1332  * @param __c The character to insert.
1333  * @throw std::length_error If new length exceeds @c max_size().
1334  *
1335  * Inserts @a __n copies of character @a __c starting at the
1336  * position referenced by iterator @a __p. If adding
1337  * characters causes the length to exceed max_size(),
1338  * length_error is thrown. The value of the string doesn't
1339  * change if an error is thrown.
1340  */
1341  void
1342  insert(iterator __p, size_type __n, _CharT __c)
1343  { this->replace(__p, __p, __n, __c); }
1344 #endif
1345 
1346 #if __cplusplus >= 201103L
1347  /**
1348  * @brief Insert a range of characters.
1349  * @param __p Const_iterator referencing location in string to
1350  * insert at.
1351  * @param __beg Start of range.
1352  * @param __end End of range.
1353  * @return Iterator referencing the first inserted char.
1354  * @throw std::length_error If new length exceeds @c max_size().
1355  *
1356  * Inserts characters in range [beg,end). If adding characters
1357  * causes the length to exceed max_size(), length_error is
1358  * thrown. The value of the string doesn't change if an error
1359  * is thrown.
1360  */
1361  template<class _InputIterator,
1362  typename = std::_RequireInputIter<_InputIterator>>
1363  iterator
1364  insert(const_iterator __p, _InputIterator __beg, _InputIterator __end)
1365  {
1366  _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1367  const size_type __pos = __p - begin();
1368  this->replace(__p, __p, __beg, __end);
1369  return iterator(this->_M_data() + __pos);
1370  }
1371 #else
1372  /**
1373  * @brief Insert a range of characters.
1374  * @param __p Iterator referencing location in string to insert at.
1375  * @param __beg Start of range.
1376  * @param __end End of range.
1377  * @throw std::length_error If new length exceeds @c max_size().
1378  *
1379  * Inserts characters in range [__beg,__end). If adding
1380  * characters causes the length to exceed max_size(),
1381  * length_error is thrown. The value of the string doesn't
1382  * change if an error is thrown.
1383  */
1384  template<class _InputIterator>
1385  void
1386  insert(iterator __p, _InputIterator __beg, _InputIterator __end)
1387  { this->replace(__p, __p, __beg, __end); }
1388 #endif
1389 
1390 #if __cplusplus >= 201103L
1391  /**
1392  * @brief Insert an initializer_list of characters.
1393  * @param __p Iterator referencing location in string to insert at.
1394  * @param __l The initializer_list of characters to insert.
1395  * @throw std::length_error If new length exceeds @c max_size().
1396  */
1397  void
1398  insert(iterator __p, initializer_list<_CharT> __l)
1399  {
1400  _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1401  this->insert(__p - begin(), __l.begin(), __l.size());
1402  }
1403 #endif // C++11
1404 
1405  /**
1406  * @brief Insert value of a string.
1407  * @param __pos1 Iterator referencing location in string to insert at.
1408  * @param __str The string to insert.
1409  * @return Reference to this string.
1410  * @throw std::length_error If new length exceeds @c max_size().
1411  *
1412  * Inserts value of @a __str starting at @a __pos1. If adding
1413  * characters causes the length to exceed max_size(),
1414  * length_error is thrown. The value of the string doesn't
1415  * change if an error is thrown.
1416  */
1417  basic_string&
1418  insert(size_type __pos1, const basic_string& __str)
1419  { return this->replace(__pos1, size_type(0),
1420  __str._M_data(), __str.size()); }
1421 
1422  /**
1423  * @brief Insert a substring.
1424  * @param __pos1 Iterator referencing location in string to insert at.
1425  * @param __str The string to insert.
1426  * @param __pos2 Start of characters in str to insert.
1427  * @param __n Number of characters to insert.
1428  * @return Reference to this string.
1429  * @throw std::length_error If new length exceeds @c max_size().
1430  * @throw std::out_of_range If @a pos1 > size() or
1431  * @a __pos2 > @a str.size().
1432  *
1433  * Starting at @a pos1, insert @a __n character of @a __str
1434  * beginning with @a __pos2. If adding characters causes the
1435  * length to exceed max_size(), length_error is thrown. If @a
1436  * __pos1 is beyond the end of this string or @a __pos2 is
1437  * beyond the end of @a __str, out_of_range is thrown. The
1438  * value of the string doesn't change if an error is thrown.
1439  */
1440  basic_string&
1441  insert(size_type __pos1, const basic_string& __str,
1442  size_type __pos2, size_type __n)
1443  { return this->replace(__pos1, size_type(0), __str._M_data()
1444  + __str._M_check(__pos2, "basic_string::insert"),
1445  __str._M_limit(__pos2, __n)); }
1446 
1447  /**
1448  * @brief Insert a C substring.
1449  * @param __pos Iterator referencing location in string to insert at.
1450  * @param __s The C string to insert.
1451  * @param __n The number of characters to insert.
1452  * @return Reference to this string.
1453  * @throw std::length_error If new length exceeds @c max_size().
1454  * @throw std::out_of_range If @a __pos is beyond the end of this
1455  * string.
1456  *
1457  * Inserts the first @a __n characters of @a __s starting at @a
1458  * __pos. If adding characters causes the length to exceed
1459  * max_size(), length_error is thrown. If @a __pos is beyond
1460  * end(), out_of_range is thrown. The value of the string
1461  * doesn't change if an error is thrown.
1462  */
1463  basic_string&
1464  insert(size_type __pos, const _CharT* __s, size_type __n)
1465  { return this->replace(__pos, size_type(0), __s, __n); }
1466 
1467  /**
1468  * @brief Insert a C string.
1469  * @param __pos Iterator referencing location in string to insert at.
1470  * @param __s The C string to insert.
1471  * @return Reference to this string.
1472  * @throw std::length_error If new length exceeds @c max_size().
1473  * @throw std::out_of_range If @a pos is beyond the end of this
1474  * string.
1475  *
1476  * Inserts the first @a n characters of @a __s starting at @a __pos. If
1477  * adding characters causes the length to exceed max_size(),
1478  * length_error is thrown. If @a __pos is beyond end(), out_of_range is
1479  * thrown. The value of the string doesn't change if an error is
1480  * thrown.
1481  */
1482  basic_string&
1483  insert(size_type __pos, const _CharT* __s)
1484  {
1485  __glibcxx_requires_string(__s);
1486  return this->replace(__pos, size_type(0), __s,
1487  traits_type::length(__s));
1488  }
1489 
1490  /**
1491  * @brief Insert multiple characters.
1492  * @param __pos Index in string to insert at.
1493  * @param __n Number of characters to insert
1494  * @param __c The character to insert.
1495  * @return Reference to this string.
1496  * @throw std::length_error If new length exceeds @c max_size().
1497  * @throw std::out_of_range If @a __pos is beyond the end of this
1498  * string.
1499  *
1500  * Inserts @a __n copies of character @a __c starting at index
1501  * @a __pos. If adding characters causes the length to exceed
1502  * max_size(), length_error is thrown. If @a __pos > length(),
1503  * out_of_range is thrown. The value of the string doesn't
1504  * change if an error is thrown.
1505  */
1506  basic_string&
1507  insert(size_type __pos, size_type __n, _CharT __c)
1508  { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
1509  size_type(0), __n, __c); }
1510 
1511  /**
1512  * @brief Insert one character.
1513  * @param __p Iterator referencing position in string to insert at.
1514  * @param __c The character to insert.
1515  * @return Iterator referencing newly inserted char.
1516  * @throw std::length_error If new length exceeds @c max_size().
1517  *
1518  * Inserts character @a __c at position referenced by @a __p.
1519  * If adding character causes the length to exceed max_size(),
1520  * length_error is thrown. If @a __p is beyond end of string,
1521  * out_of_range is thrown. The value of the string doesn't
1522  * change if an error is thrown.
1523  */
1524  iterator
1525  insert(__const_iterator __p, _CharT __c)
1526  {
1527  _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1528  const size_type __pos = __p - begin();
1529  _M_replace_aux(__pos, size_type(0), size_type(1), __c);
1530  return iterator(_M_data() + __pos);
1531  }
1532 
1533  /**
1534  * @brief Remove characters.
1535  * @param __pos Index of first character to remove (default 0).
1536  * @param __n Number of characters to remove (default remainder).
1537  * @return Reference to this string.
1538  * @throw std::out_of_range If @a pos is beyond the end of this
1539  * string.
1540  *
1541  * Removes @a __n characters from this string starting at @a
1542  * __pos. The length of the string is reduced by @a __n. If
1543  * there are < @a __n characters to remove, the remainder of
1544  * the string is truncated. If @a __p is beyond end of string,
1545  * out_of_range is thrown. The value of the string doesn't
1546  * change if an error is thrown.
1547  */
1548  basic_string&
1549  erase(size_type __pos = 0, size_type __n = npos)
1550  {
1551  this->_M_erase(_M_check(__pos, "basic_string::erase"),
1552  _M_limit(__pos, __n));
1553  return *this;
1554  }
1555 
1556  /**
1557  * @brief Remove one character.
1558  * @param __position Iterator referencing the character to remove.
1559  * @return iterator referencing same location after removal.
1560  *
1561  * Removes the character at @a __position from this string. The value
1562  * of the string doesn't change if an error is thrown.
1563  */
1564  iterator
1565  erase(__const_iterator __position)
1566  {
1567  _GLIBCXX_DEBUG_PEDASSERT(__position >= begin()
1568  && __position < end());
1569  const size_type __pos = __position - begin();
1570  this->_M_erase(__pos, size_type(1));
1571  return iterator(_M_data() + __pos);
1572  }
1573 
1574  /**
1575  * @brief Remove a range of characters.
1576  * @param __first Iterator referencing the first character to remove.
1577  * @param __last Iterator referencing the end of the range.
1578  * @return Iterator referencing location of first after removal.
1579  *
1580  * Removes the characters in the range [first,last) from this string.
1581  * The value of the string doesn't change if an error is thrown.
1582  */
1583  iterator
1584  erase(__const_iterator __first, __const_iterator __last)
1585  {
1586  _GLIBCXX_DEBUG_PEDASSERT(__first >= begin() && __first <= __last
1587  && __last <= end());
1588  const size_type __pos = __first - begin();
1589  this->_M_erase(__pos, __last - __first);
1590  return iterator(this->_M_data() + __pos);
1591  }
1592 
1593 #if __cplusplus >= 201103L
1594  /**
1595  * @brief Remove the last character.
1596  *
1597  * The string must be non-empty.
1598  */
1599  void
1600  pop_back() noexcept
1601  { _M_erase(size()-1, 1); }
1602 #endif // C++11
1603 
1604  /**
1605  * @brief Replace characters with value from another string.
1606  * @param __pos Index of first character to replace.
1607  * @param __n Number of characters to be replaced.
1608  * @param __str String to insert.
1609  * @return Reference to this string.
1610  * @throw std::out_of_range If @a pos is beyond the end of this
1611  * string.
1612  * @throw std::length_error If new length exceeds @c max_size().
1613  *
1614  * Removes the characters in the range [__pos,__pos+__n) from
1615  * this string. In place, the value of @a __str is inserted.
1616  * If @a __pos is beyond end of string, out_of_range is thrown.
1617  * If the length of the result exceeds max_size(), length_error
1618  * is thrown. The value of the string doesn't change if an
1619  * error is thrown.
1620  */
1621  basic_string&
1622  replace(size_type __pos, size_type __n, const basic_string& __str)
1623  { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
1624 
1625  /**
1626  * @brief Replace characters with value from another string.
1627  * @param __pos1 Index of first character to replace.
1628  * @param __n1 Number of characters to be replaced.
1629  * @param __str String to insert.
1630  * @param __pos2 Index of first character of str to use.
1631  * @param __n2 Number of characters from str to use.
1632  * @return Reference to this string.
1633  * @throw std::out_of_range If @a __pos1 > size() or @a __pos2 >
1634  * __str.size().
1635  * @throw std::length_error If new length exceeds @c max_size().
1636  *
1637  * Removes the characters in the range [__pos1,__pos1 + n) from this
1638  * string. In place, the value of @a __str is inserted. If @a __pos is
1639  * beyond end of string, out_of_range is thrown. If the length of the
1640  * result exceeds max_size(), length_error is thrown. The value of the
1641  * string doesn't change if an error is thrown.
1642  */
1643  basic_string&
1644  replace(size_type __pos1, size_type __n1, const basic_string& __str,
1645  size_type __pos2, size_type __n2)
1646  { return this->replace(__pos1, __n1, __str._M_data()
1647  + __str._M_check(__pos2, "basic_string::replace"),
1648  __str._M_limit(__pos2, __n2)); }
1649 
1650  /**
1651  * @brief Replace characters with value of a C substring.
1652  * @param __pos Index of first character to replace.
1653  * @param __n1 Number of characters to be replaced.
1654  * @param __s C string to insert.
1655  * @param __n2 Number of characters from @a s to use.
1656  * @return Reference to this string.
1657  * @throw std::out_of_range If @a pos1 > size().
1658  * @throw std::length_error If new length exceeds @c max_size().
1659  *
1660  * Removes the characters in the range [__pos,__pos + __n1)
1661  * from this string. In place, the first @a __n2 characters of
1662  * @a __s are inserted, or all of @a __s if @a __n2 is too large. If
1663  * @a __pos is beyond end of string, out_of_range is thrown. If
1664  * the length of result exceeds max_size(), length_error is
1665  * thrown. The value of the string doesn't change if an error
1666  * is thrown.
1667  */
1668  basic_string&
1669  replace(size_type __pos, size_type __n1, const _CharT* __s,
1670  size_type __n2)
1671  {
1672  __glibcxx_requires_string_len(__s, __n2);
1673  return _M_replace(_M_check(__pos, "basic_string::replace"),
1674  _M_limit(__pos, __n1), __s, __n2);
1675  }
1676 
1677  /**
1678  * @brief Replace characters with value of a C string.
1679  * @param __pos Index of first character to replace.
1680  * @param __n1 Number of characters to be replaced.
1681  * @param __s C string to insert.
1682  * @return Reference to this string.
1683  * @throw std::out_of_range If @a pos > size().
1684  * @throw std::length_error If new length exceeds @c max_size().
1685  *
1686  * Removes the characters in the range [__pos,__pos + __n1)
1687  * from this string. In place, the characters of @a __s are
1688  * inserted. If @a __pos is beyond end of string, out_of_range
1689  * is thrown. If the length of result exceeds max_size(),
1690  * length_error is thrown. The value of the string doesn't
1691  * change if an error is thrown.
1692  */
1693  basic_string&
1694  replace(size_type __pos, size_type __n1, const _CharT* __s)
1695  {
1696  __glibcxx_requires_string(__s);
1697  return this->replace(__pos, __n1, __s, traits_type::length(__s));
1698  }
1699 
1700  /**
1701  * @brief Replace characters with multiple characters.
1702  * @param __pos Index of first character to replace.
1703  * @param __n1 Number of characters to be replaced.
1704  * @param __n2 Number of characters to insert.
1705  * @param __c Character to insert.
1706  * @return Reference to this string.
1707  * @throw std::out_of_range If @a __pos > size().
1708  * @throw std::length_error If new length exceeds @c max_size().
1709  *
1710  * Removes the characters in the range [pos,pos + n1) from this
1711  * string. In place, @a __n2 copies of @a __c are inserted.
1712  * If @a __pos is beyond end of string, out_of_range is thrown.
1713  * If the length of result exceeds max_size(), length_error is
1714  * thrown. The value of the string doesn't change if an error
1715  * is thrown.
1716  */
1717  basic_string&
1718  replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
1719  { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
1720  _M_limit(__pos, __n1), __n2, __c); }
1721 
1722  /**
1723  * @brief Replace range of characters with string.
1724  * @param __i1 Iterator referencing start of range to replace.
1725  * @param __i2 Iterator referencing end of range to replace.
1726  * @param __str String value to insert.
1727  * @return Reference to this string.
1728  * @throw std::length_error If new length exceeds @c max_size().
1729  *
1730  * Removes the characters in the range [__i1,__i2). In place,
1731  * the value of @a __str is inserted. If the length of result
1732  * exceeds max_size(), length_error is thrown. The value of
1733  * the string doesn't change if an error is thrown.
1734  */
1735  basic_string&
1736  replace(__const_iterator __i1, __const_iterator __i2,
1737  const basic_string& __str)
1738  { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
1739 
1740  /**
1741  * @brief Replace range of characters with C substring.
1742  * @param __i1 Iterator referencing start of range to replace.
1743  * @param __i2 Iterator referencing end of range to replace.
1744  * @param __s C string value to insert.
1745  * @param __n Number of characters from s to insert.
1746  * @return Reference to this string.
1747  * @throw std::length_error If new length exceeds @c max_size().
1748  *
1749  * Removes the characters in the range [__i1,__i2). In place,
1750  * the first @a __n characters of @a __s are inserted. If the
1751  * length of result exceeds max_size(), length_error is thrown.
1752  * The value of the string doesn't change if an error is
1753  * thrown.
1754  */
1755  basic_string&
1756  replace(__const_iterator __i1, __const_iterator __i2,
1757  const _CharT* __s, size_type __n)
1758  {
1759  _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1760  && __i2 <= end());
1761  return this->replace(__i1 - begin(), __i2 - __i1, __s, __n);
1762  }
1763 
1764  /**
1765  * @brief Replace range of characters with C string.
1766  * @param __i1 Iterator referencing start of range to replace.
1767  * @param __i2 Iterator referencing end of range to replace.
1768  * @param __s C string value to insert.
1769  * @return Reference to this string.
1770  * @throw std::length_error If new length exceeds @c max_size().
1771  *
1772  * Removes the characters in the range [__i1,__i2). In place,
1773  * the characters of @a __s are inserted. If the length of
1774  * result exceeds max_size(), length_error is thrown. The
1775  * value of the string doesn't change if an error is thrown.
1776  */
1777  basic_string&
1778  replace(__const_iterator __i1, __const_iterator __i2, const _CharT* __s)
1779  {
1780  __glibcxx_requires_string(__s);
1781  return this->replace(__i1, __i2, __s, traits_type::length(__s));
1782  }
1783 
1784  /**
1785  * @brief Replace range of characters with multiple characters
1786  * @param __i1 Iterator referencing start of range to replace.
1787  * @param __i2 Iterator referencing end of range to replace.
1788  * @param __n Number of characters to insert.
1789  * @param __c Character to insert.
1790  * @return Reference to this string.
1791  * @throw std::length_error If new length exceeds @c max_size().
1792  *
1793  * Removes the characters in the range [__i1,__i2). In place,
1794  * @a __n copies of @a __c are inserted. If the length of
1795  * result exceeds max_size(), length_error is thrown. The
1796  * value of the string doesn't change if an error is thrown.
1797  */
1798  basic_string&
1799  replace(__const_iterator __i1, __const_iterator __i2, size_type __n,
1800  _CharT __c)
1801  {
1802  _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1803  && __i2 <= end());
1804  return _M_replace_aux(__i1 - begin(), __i2 - __i1, __n, __c);
1805  }
1806 
1807  /**
1808  * @brief Replace range of characters with range.
1809  * @param __i1 Iterator referencing start of range to replace.
1810  * @param __i2 Iterator referencing end of range to replace.
1811  * @param __k1 Iterator referencing start of range to insert.
1812  * @param __k2 Iterator referencing end of range to insert.
1813  * @return Reference to this string.
1814  * @throw std::length_error If new length exceeds @c max_size().
1815  *
1816  * Removes the characters in the range [__i1,__i2). In place,
1817  * characters in the range [__k1,__k2) are inserted. If the
1818  * length of result exceeds max_size(), length_error is thrown.
1819  * The value of the string doesn't change if an error is
1820  * thrown.
1821  */
1822 #if __cplusplus >= 201103L
1823  template<class _InputIterator,
1824  typename = std::_RequireInputIter<_InputIterator>>
1825  basic_string&
1826  replace(const_iterator __i1, const_iterator __i2,
1827  _InputIterator __k1, _InputIterator __k2)
1828  {
1829  _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1830  && __i2 <= end());
1831  __glibcxx_requires_valid_range(__k1, __k2);
1832  return this->_M_replace_dispatch(__i1, __i2, __k1, __k2,
1833  std::__false_type());
1834  }
1835 #else
1836  template<class _InputIterator>
1837 #ifdef _GLIBCXX_DISAMBIGUATE_REPLACE_INST
1838  typename __enable_if_not_native_iterator<_InputIterator>::__type
1839 #else
1840  basic_string&
1841 #endif
1842  replace(iterator __i1, iterator __i2,
1843  _InputIterator __k1, _InputIterator __k2)
1844  {
1845  _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1846  && __i2 <= end());
1847  __glibcxx_requires_valid_range(__k1, __k2);
1848  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1849  return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
1850  }
1851 #endif
1852 
1853  // Specializations for the common case of pointer and iterator:
1854  // useful to avoid the overhead of temporary buffering in _M_replace.
1855  basic_string&
1856  replace(__const_iterator __i1, __const_iterator __i2,
1857  _CharT* __k1, _CharT* __k2)
1858  {
1859  _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1860  && __i2 <= end());
1861  __glibcxx_requires_valid_range(__k1, __k2);
1862  return this->replace(__i1 - begin(), __i2 - __i1,
1863  __k1, __k2 - __k1);
1864  }
1865 
1866  basic_string&
1867  replace(__const_iterator __i1, __const_iterator __i2,
1868  const _CharT* __k1, const _CharT* __k2)
1869  {
1870  _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1871  && __i2 <= end());
1872  __glibcxx_requires_valid_range(__k1, __k2);
1873  return this->replace(__i1 - begin(), __i2 - __i1,
1874  __k1, __k2 - __k1);
1875  }
1876 
1877  basic_string&
1878  replace(__const_iterator __i1, __const_iterator __i2,
1879  iterator __k1, iterator __k2)
1880  {
1881  _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1882  && __i2 <= end());
1883  __glibcxx_requires_valid_range(__k1, __k2);
1884  return this->replace(__i1 - begin(), __i2 - __i1,
1885  __k1.base(), __k2 - __k1);
1886  }
1887 
1888  basic_string&
1889  replace(__const_iterator __i1, __const_iterator __i2,
1890  const_iterator __k1, const_iterator __k2)
1891  {
1892  _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1893  && __i2 <= end());
1894  __glibcxx_requires_valid_range(__k1, __k2);
1895  return this->replace(__i1 - begin(), __i2 - __i1,
1896  __k1.base(), __k2 - __k1);
1897  }
1898 
1899 #if __cplusplus >= 201103L
1900  /**
1901  * @brief Replace range of characters with initializer_list.
1902  * @param __i1 Iterator referencing start of range to replace.
1903  * @param __i2 Iterator referencing end of range to replace.
1904  * @param __l The initializer_list of characters to insert.
1905  * @return Reference to this string.
1906  * @throw std::length_error If new length exceeds @c max_size().
1907  *
1908  * Removes the characters in the range [__i1,__i2). In place,
1909  * characters in the range [__k1,__k2) are inserted. If the
1910  * length of result exceeds max_size(), length_error is thrown.
1911  * The value of the string doesn't change if an error is
1912  * thrown.
1913  */
1914  basic_string& replace(const_iterator __i1, const_iterator __i2,
1915  initializer_list<_CharT> __l)
1916  { return this->replace(__i1, __i2, __l.begin(), __l.end()); }
1917 #endif // C++11
1918 
1919  private:
1920  template<class _Integer>
1921  basic_string&
1922  _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
1923  _Integer __n, _Integer __val, __true_type)
1924  { return _M_replace_aux(__i1 - begin(), __i2 - __i1, __n, __val); }
1925 
1926  template<class _InputIterator>
1927  basic_string&
1928  _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
1929  _InputIterator __k1, _InputIterator __k2,
1930  __false_type);
1931 
1932  basic_string&
1933  _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
1934  _CharT __c);
1935 
1936  basic_string&
1937  _M_replace(size_type __pos, size_type __len1, const _CharT* __s,
1938  const size_type __len2);
1939 
1940  basic_string&
1941  _M_append(const _CharT* __s, size_type __n);
1942 
1943  public:
1944 
1945  /**
1946  * @brief Copy substring into C string.
1947  * @param __s C string to copy value into.
1948  * @param __n Number of characters to copy.
1949  * @param __pos Index of first character to copy.
1950  * @return Number of characters actually copied
1951  * @throw std::out_of_range If __pos > size().
1952  *
1953  * Copies up to @a __n characters starting at @a __pos into the
1954  * C string @a __s. If @a __pos is %greater than size(),
1955  * out_of_range is thrown.
1956  */
1957  size_type
1958  copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
1959 
1960  /**
1961  * @brief Swap contents with another string.
1962  * @param __s String to swap with.
1963  *
1964  * Exchanges the contents of this string with that of @a __s in constant
1965  * time.
1966  */
1967  void
1968  swap(basic_string& __s) _GLIBCXX_NOEXCEPT;
1969 
1970  // String operations:
1971  /**
1972  * @brief Return const pointer to null-terminated contents.
1973  *
1974  * This is a handle to internal data. Do not modify or dire things may
1975  * happen.
1976  */
1977  const _CharT*
1978  c_str() const _GLIBCXX_NOEXCEPT
1979  { return _M_data(); }
1980 
1981  /**
1982  * @brief Return const pointer to contents.
1983  *
1984  * This is a handle to internal data. Do not modify or dire things may
1985  * happen.
1986  */
1987  const _CharT*
1988  data() const _GLIBCXX_NOEXCEPT
1989  { return _M_data(); }
1990 
1991  /**
1992  * @brief Return copy of allocator used to construct this string.
1993  */
1994  allocator_type
1995  get_allocator() const _GLIBCXX_NOEXCEPT
1996  { return _M_get_allocator(); }
1997 
1998  /**
1999  * @brief Find position of a C substring.
2000  * @param __s C string to locate.
2001  * @param __pos Index of character to search from.
2002  * @param __n Number of characters from @a s to search for.
2003  * @return Index of start of first occurrence.
2004  *
2005  * Starting from @a __pos, searches forward for the first @a
2006  * __n characters in @a __s within this string. If found,
2007  * returns the index where it begins. If not found, returns
2008  * npos.
2009  */
2010  size_type
2011  find(const _CharT* __s, size_type __pos, size_type __n) const;
2012 
2013  /**
2014  * @brief Find position of a string.
2015  * @param __str String to locate.
2016  * @param __pos Index of character to search from (default 0).
2017  * @return Index of start of first occurrence.
2018  *
2019  * Starting from @a __pos, searches forward for value of @a __str within
2020  * this string. If found, returns the index where it begins. If not
2021  * found, returns npos.
2022  */
2023  size_type
2024  find(const basic_string& __str, size_type __pos = 0) const
2025  _GLIBCXX_NOEXCEPT
2026  { return this->find(__str.data(), __pos, __str.size()); }
2027 
2028  /**
2029  * @brief Find position of a C string.
2030  * @param __s C string to locate.
2031  * @param __pos Index of character to search from (default 0).
2032  * @return Index of start of first occurrence.
2033  *
2034  * Starting from @a __pos, searches forward for the value of @a
2035  * __s within this string. If found, returns the index where
2036  * it begins. If not found, returns npos.
2037  */
2038  size_type
2039  find(const _CharT* __s, size_type __pos = 0) const
2040  {
2041  __glibcxx_requires_string(__s);
2042  return this->find(__s, __pos, traits_type::length(__s));
2043  }
2044 
2045  /**
2046  * @brief Find position of a character.
2047  * @param __c Character to locate.
2048  * @param __pos Index of character to search from (default 0).
2049  * @return Index of first occurrence.
2050  *
2051  * Starting from @a __pos, searches forward for @a __c within
2052  * this string. If found, returns the index where it was
2053  * found. If not found, returns npos.
2054  */
2055  size_type
2056  find(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT;
2057 
2058  /**
2059  * @brief Find last position of a string.
2060  * @param __str String to locate.
2061  * @param __pos Index of character to search back from (default end).
2062  * @return Index of start of last occurrence.
2063  *
2064  * Starting from @a __pos, searches backward for value of @a
2065  * __str within this string. If found, returns the index where
2066  * it begins. If not found, returns npos.
2067  */
2068  size_type
2069  rfind(const basic_string& __str, size_type __pos = npos) const
2070  _GLIBCXX_NOEXCEPT
2071  { return this->rfind(__str.data(), __pos, __str.size()); }
2072 
2073  /**
2074  * @brief Find last position of a C substring.
2075  * @param __s C string to locate.
2076  * @param __pos Index of character to search back from.
2077  * @param __n Number of characters from s to search for.
2078  * @return Index of start of last occurrence.
2079  *
2080  * Starting from @a __pos, searches backward for the first @a
2081  * __n characters in @a __s within this string. If found,
2082  * returns the index where it begins. If not found, returns
2083  * npos.
2084  */
2085  size_type
2086  rfind(const _CharT* __s, size_type __pos, size_type __n) const;
2087 
2088  /**
2089  * @brief Find last position of a C string.
2090  * @param __s C string to locate.
2091  * @param __pos Index of character to start search at (default end).
2092  * @return Index of start of last occurrence.
2093  *
2094  * Starting from @a __pos, searches backward for the value of
2095  * @a __s within this string. If found, returns the index
2096  * where it begins. If not found, returns npos.
2097  */
2098  size_type
2099  rfind(const _CharT* __s, size_type __pos = npos) const
2100  {
2101  __glibcxx_requires_string(__s);
2102  return this->rfind(__s, __pos, traits_type::length(__s));
2103  }
2104 
2105  /**
2106  * @brief Find last position of a character.
2107  * @param __c Character to locate.
2108  * @param __pos Index of character to search back from (default end).
2109  * @return Index of last occurrence.
2110  *
2111  * Starting from @a __pos, searches backward for @a __c within
2112  * this string. If found, returns the index where it was
2113  * found. If not found, returns npos.
2114  */
2115  size_type
2116  rfind(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT;
2117 
2118  /**
2119  * @brief Find position of a character of string.
2120  * @param __str String containing characters to locate.
2121  * @param __pos Index of character to search from (default 0).
2122  * @return Index of first occurrence.
2123  *
2124  * Starting from @a __pos, searches forward for one of the
2125  * characters of @a __str within this string. If found,
2126  * returns the index where it was found. If not found, returns
2127  * npos.
2128  */
2129  size_type
2130  find_first_of(const basic_string& __str, size_type __pos = 0) const
2131  _GLIBCXX_NOEXCEPT
2132  { return this->find_first_of(__str.data(), __pos, __str.size()); }
2133 
2134  /**
2135  * @brief Find position of a character of C substring.
2136  * @param __s String containing characters to locate.
2137  * @param __pos Index of character to search from.
2138  * @param __n Number of characters from s to search for.
2139  * @return Index of first occurrence.
2140  *
2141  * Starting from @a __pos, searches forward for one of the
2142  * first @a __n characters of @a __s within this string. If
2143  * found, returns the index where it was found. If not found,
2144  * returns npos.
2145  */
2146  size_type
2147  find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
2148 
2149  /**
2150  * @brief Find position of a character of C string.
2151  * @param __s String containing characters to locate.
2152  * @param __pos Index of character to search from (default 0).
2153  * @return Index of first occurrence.
2154  *
2155  * Starting from @a __pos, searches forward for one of the
2156  * characters of @a __s within this string. If found, returns
2157  * the index where it was found. If not found, returns npos.
2158  */
2159  size_type
2160  find_first_of(const _CharT* __s, size_type __pos = 0) const
2161  {
2162  __glibcxx_requires_string(__s);
2163  return this->find_first_of(__s, __pos, traits_type::length(__s));
2164  }
2165 
2166  /**
2167  * @brief Find position of a character.
2168  * @param __c Character to locate.
2169  * @param __pos Index of character to search from (default 0).
2170  * @return Index of first occurrence.
2171  *
2172  * Starting from @a __pos, searches forward for the character
2173  * @a __c within this string. If found, returns the index
2174  * where it was found. If not found, returns npos.
2175  *
2176  * Note: equivalent to find(__c, __pos).
2177  */
2178  size_type
2179  find_first_of(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT
2180  { return this->find(__c, __pos); }
2181 
2182  /**
2183  * @brief Find last position of a character of string.
2184  * @param __str String containing characters to locate.
2185  * @param __pos Index of character to search back from (default end).
2186  * @return Index of last occurrence.
2187  *
2188  * Starting from @a __pos, searches backward for one of the
2189  * characters of @a __str within this string. If found,
2190  * returns the index where it was found. If not found, returns
2191  * npos.
2192  */
2193  size_type
2194  find_last_of(const basic_string& __str, size_type __pos = npos) const
2195  _GLIBCXX_NOEXCEPT
2196  { return this->find_last_of(__str.data(), __pos, __str.size()); }
2197 
2198  /**
2199  * @brief Find last position of a character of C substring.
2200  * @param __s C string containing characters to locate.
2201  * @param __pos Index of character to search back from.
2202  * @param __n Number of characters from s to search for.
2203  * @return Index of last occurrence.
2204  *
2205  * Starting from @a __pos, searches backward for one of the
2206  * first @a __n characters of @a __s within this string. If
2207  * found, returns the index where it was found. If not found,
2208  * returns npos.
2209  */
2210  size_type
2211  find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
2212 
2213  /**
2214  * @brief Find last position of a character of C string.
2215  * @param __s C string containing characters to locate.
2216  * @param __pos Index of character to search back from (default end).
2217  * @return Index of last occurrence.
2218  *
2219  * Starting from @a __pos, searches backward for one of the
2220  * characters of @a __s within this string. If found, returns
2221  * the index where it was found. If not found, returns npos.
2222  */
2223  size_type
2224  find_last_of(const _CharT* __s, size_type __pos = npos) const
2225  {
2226  __glibcxx_requires_string(__s);
2227  return this->find_last_of(__s, __pos, traits_type::length(__s));
2228  }
2229 
2230  /**
2231  * @brief Find last position of a character.
2232  * @param __c Character to locate.
2233  * @param __pos Index of character to search back from (default end).
2234  * @return Index of last occurrence.
2235  *
2236  * Starting from @a __pos, searches backward for @a __c within
2237  * this string. If found, returns the index where it was
2238  * found. If not found, returns npos.
2239  *
2240  * Note: equivalent to rfind(__c, __pos).
2241  */
2242  size_type
2243  find_last_of(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT
2244  { return this->rfind(__c, __pos); }
2245 
2246  /**
2247  * @brief Find position of a character not in string.
2248  * @param __str String containing characters to avoid.
2249  * @param __pos Index of character to search from (default 0).
2250  * @return Index of first occurrence.
2251  *
2252  * Starting from @a __pos, searches forward for a character not contained
2253  * in @a __str within this string. If found, returns the index where it
2254  * was found. If not found, returns npos.
2255  */
2256  size_type
2257  find_first_not_of(const basic_string& __str, size_type __pos = 0) const
2258  _GLIBCXX_NOEXCEPT
2259  { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
2260 
2261  /**
2262  * @brief Find position of a character not in C substring.
2263  * @param __s C string containing characters to avoid.
2264  * @param __pos Index of character to search from.
2265  * @param __n Number of characters from __s to consider.
2266  * @return Index of first occurrence.
2267  *
2268  * Starting from @a __pos, searches forward for a character not
2269  * contained in the first @a __n characters of @a __s within
2270  * this string. If found, returns the index where it was
2271  * found. If not found, returns npos.
2272  */
2273  size_type
2274  find_first_not_of(const _CharT* __s, size_type __pos,
2275  size_type __n) const;
2276 
2277  /**
2278  * @brief Find position of a character not in C string.
2279  * @param __s C string containing characters to avoid.
2280  * @param __pos Index of character to search from (default 0).
2281  * @return Index of first occurrence.
2282  *
2283  * Starting from @a __pos, searches forward for a character not
2284  * contained in @a __s within this string. If found, returns
2285  * the index where it was found. If not found, returns npos.
2286  */
2287  size_type
2288  find_first_not_of(const _CharT* __s, size_type __pos = 0) const
2289  {
2290  __glibcxx_requires_string(__s);
2291  return this->find_first_not_of(__s, __pos, traits_type::length(__s));
2292  }
2293 
2294  /**
2295  * @brief Find position of a different character.
2296  * @param __c Character to avoid.
2297  * @param __pos Index of character to search from (default 0).
2298  * @return Index of first occurrence.
2299  *
2300  * Starting from @a __pos, searches forward for a character
2301  * other than @a __c within this string. If found, returns the
2302  * index where it was found. If not found, returns npos.
2303  */
2304  size_type
2305  find_first_not_of(_CharT __c, size_type __pos = 0) const
2306  _GLIBCXX_NOEXCEPT;
2307 
2308  /**
2309  * @brief Find last position of a character not in string.
2310  * @param __str String containing characters to avoid.
2311  * @param __pos Index of character to search back from (default end).
2312  * @return Index of last occurrence.
2313  *
2314  * Starting from @a __pos, searches backward for a character
2315  * not contained in @a __str within this string. If found,
2316  * returns the index where it was found. If not found, returns
2317  * npos.
2318  */
2319  size_type
2320  find_last_not_of(const basic_string& __str, size_type __pos = npos) const
2321  _GLIBCXX_NOEXCEPT
2322  { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
2323 
2324  /**
2325  * @brief Find last position of a character not in C substring.
2326  * @param __s C string containing characters to avoid.
2327  * @param __pos Index of character to search back from.
2328  * @param __n Number of characters from s to consider.
2329  * @return Index of last occurrence.
2330  *
2331  * Starting from @a __pos, searches backward for a character not
2332  * contained in the first @a __n characters of @a __s within this string.
2333  * If found, returns the index where it was found. If not found,
2334  * returns npos.
2335  */
2336  size_type
2337  find_last_not_of(const _CharT* __s, size_type __pos,
2338  size_type __n) const;
2339  /**
2340  * @brief Find last position of a character not in C string.
2341  * @param __s C string containing characters to avoid.
2342  * @param __pos Index of character to search back from (default end).
2343  * @return Index of last occurrence.
2344  *
2345  * Starting from @a __pos, searches backward for a character
2346  * not contained in @a __s within this string. If found,
2347  * returns the index where it was found. If not found, returns
2348  * npos.
2349  */
2350  size_type
2351  find_last_not_of(const _CharT* __s, size_type __pos = npos) const
2352  {
2353  __glibcxx_requires_string(__s);
2354  return this->find_last_not_of(__s, __pos, traits_type::length(__s));
2355  }
2356 
2357  /**
2358  * @brief Find last position of a different character.
2359  * @param __c Character to avoid.
2360  * @param __pos Index of character to search back from (default end).
2361  * @return Index of last occurrence.
2362  *
2363  * Starting from @a __pos, searches backward for a character other than
2364  * @a __c within this string. If found, returns the index where it was
2365  * found. If not found, returns npos.
2366  */
2367  size_type
2368  find_last_not_of(_CharT __c, size_type __pos = npos) const
2369  _GLIBCXX_NOEXCEPT;
2370 
2371  /**
2372  * @brief Get a substring.
2373  * @param __pos Index of first character (default 0).
2374  * @param __n Number of characters in substring (default remainder).
2375  * @return The new string.
2376  * @throw std::out_of_range If __pos > size().
2377  *
2378  * Construct and return a new string using the @a __n
2379  * characters starting at @a __pos. If the string is too
2380  * short, use the remainder of the characters. If @a __pos is
2381  * beyond the end of the string, out_of_range is thrown.
2382  */
2383  basic_string
2384  substr(size_type __pos = 0, size_type __n = npos) const
2385  { return basic_string(*this,
2386  _M_check(__pos, "basic_string::substr"), __n); }
2387 
2388  /**
2389  * @brief Compare to a string.
2390  * @param __str String to compare against.
2391  * @return Integer < 0, 0, or > 0.
2392  *
2393  * Returns an integer < 0 if this string is ordered before @a
2394  * __str, 0 if their values are equivalent, or > 0 if this
2395  * string is ordered after @a __str. Determines the effective
2396  * length rlen of the strings to compare as the smallest of
2397  * size() and str.size(). The function then compares the two
2398  * strings by calling traits::compare(data(), str.data(),rlen).
2399  * If the result of the comparison is nonzero returns it,
2400  * otherwise the shorter one is ordered first.
2401  */
2402  int
2403  compare(const basic_string& __str) const
2404  {
2405  const size_type __size = this->size();
2406  const size_type __osize = __str.size();
2407  const size_type __len = std::min(__size, __osize);
2408 
2409  int __r = traits_type::compare(_M_data(), __str.data(), __len);
2410  if (!__r)
2411  __r = _S_compare(__size, __osize);
2412  return __r;
2413  }
2414 
2415  /**
2416  * @brief Compare substring to a string.
2417  * @param __pos Index of first character of substring.
2418  * @param __n Number of characters in substring.
2419  * @param __str String to compare against.
2420  * @return Integer < 0, 0, or > 0.
2421  *
2422  * Form the substring of this string from the @a __n characters
2423  * starting at @a __pos. Returns an integer < 0 if the
2424  * substring is ordered before @a __str, 0 if their values are
2425  * equivalent, or > 0 if the substring is ordered after @a
2426  * __str. Determines the effective length rlen of the strings
2427  * to compare as the smallest of the length of the substring
2428  * and @a __str.size(). The function then compares the two
2429  * strings by calling
2430  * traits::compare(substring.data(),str.data(),rlen). If the
2431  * result of the comparison is nonzero returns it, otherwise
2432  * the shorter one is ordered first.
2433  */
2434  int
2435  compare(size_type __pos, size_type __n, const basic_string& __str) const;
2436 
2437  /**
2438  * @brief Compare substring to a substring.
2439  * @param __pos1 Index of first character of substring.
2440  * @param __n1 Number of characters in substring.
2441  * @param __str String to compare against.
2442  * @param __pos2 Index of first character of substring of str.
2443  * @param __n2 Number of characters in substring of str.
2444  * @return Integer < 0, 0, or > 0.
2445  *
2446  * Form the substring of this string from the @a __n1
2447  * characters starting at @a __pos1. Form the substring of @a
2448  * __str from the @a __n2 characters starting at @a __pos2.
2449  * Returns an integer < 0 if this substring is ordered before
2450  * the substring of @a __str, 0 if their values are equivalent,
2451  * or > 0 if this substring is ordered after the substring of
2452  * @a __str. Determines the effective length rlen of the
2453  * strings to compare as the smallest of the lengths of the
2454  * substrings. The function then compares the two strings by
2455  * calling
2456  * traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
2457  * If the result of the comparison is nonzero returns it,
2458  * otherwise the shorter one is ordered first.
2459  */
2460  int
2461  compare(size_type __pos1, size_type __n1, const basic_string& __str,
2462  size_type __pos2, size_type __n2) const;
2463 
2464  /**
2465  * @brief Compare to a C string.
2466  * @param __s C string to compare against.
2467  * @return Integer < 0, 0, or > 0.
2468  *
2469  * Returns an integer < 0 if this string is ordered before @a __s, 0 if
2470  * their values are equivalent, or > 0 if this string is ordered after
2471  * @a __s. Determines the effective length rlen of the strings to
2472  * compare as the smallest of size() and the length of a string
2473  * constructed from @a __s. The function then compares the two strings
2474  * by calling traits::compare(data(),s,rlen). If the result of the
2475  * comparison is nonzero returns it, otherwise the shorter one is
2476  * ordered first.
2477  */
2478  int
2479  compare(const _CharT* __s) const;
2480 
2481  // _GLIBCXX_RESOLVE_LIB_DEFECTS
2482  // 5 String::compare specification questionable
2483  /**
2484  * @brief Compare substring to a C string.
2485  * @param __pos Index of first character of substring.
2486  * @param __n1 Number of characters in substring.
2487  * @param __s C string to compare against.
2488  * @return Integer < 0, 0, or > 0.
2489  *
2490  * Form the substring of this string from the @a __n1
2491  * characters starting at @a pos. Returns an integer < 0 if
2492  * the substring is ordered before @a __s, 0 if their values
2493  * are equivalent, or > 0 if the substring is ordered after @a
2494  * __s. Determines the effective length rlen of the strings to
2495  * compare as the smallest of the length of the substring and
2496  * the length of a string constructed from @a __s. The
2497  * function then compares the two string by calling
2498  * traits::compare(substring.data(),__s,rlen). If the result of
2499  * the comparison is nonzero returns it, otherwise the shorter
2500  * one is ordered first.
2501  */
2502  int
2503  compare(size_type __pos, size_type __n1, const _CharT* __s) const;
2504 
2505  /**
2506  * @brief Compare substring against a character %array.
2507  * @param __pos Index of first character of substring.
2508  * @param __n1 Number of characters in substring.
2509  * @param __s character %array to compare against.
2510  * @param __n2 Number of characters of s.
2511  * @return Integer < 0, 0, or > 0.
2512  *
2513  * Form the substring of this string from the @a __n1
2514  * characters starting at @a __pos. Form a string from the
2515  * first @a __n2 characters of @a __s. Returns an integer < 0
2516  * if this substring is ordered before the string from @a __s,
2517  * 0 if their values are equivalent, or > 0 if this substring
2518  * is ordered after the string from @a __s. Determines the
2519  * effective length rlen of the strings to compare as the
2520  * smallest of the length of the substring and @a __n2. The
2521  * function then compares the two strings by calling
2522  * traits::compare(substring.data(),s,rlen). If the result of
2523  * the comparison is nonzero returns it, otherwise the shorter
2524  * one is ordered first.
2525  *
2526  * NB: s must have at least n2 characters, &apos;\\0&apos; has
2527  * no special meaning.
2528  */
2529  int
2530  compare(size_type __pos, size_type __n1, const _CharT* __s,
2531  size_type __n2) const;
2532 
2533  // Allow basic_stringbuf::__xfer_bufptrs to call _M_length:
2534  template<typename, typename, typename> friend class basic_stringbuf;
2535  };
2536 _GLIBCXX_END_NAMESPACE_CXX11
2537 #else // !_GLIBCXX_USE_CXX11_ABI
2538  // Reference-counted COW string implentation
2539 
2540  /**
2541  * @class basic_string basic_string.h <string>
2542  * @brief Managing sequences of characters and character-like objects.
2543  *
2544  * @ingroup strings
2545  * @ingroup sequences
2546  *
2547  * @tparam _CharT Type of character
2548  * @tparam _Traits Traits for character type, defaults to
2549  * char_traits<_CharT>.
2550  * @tparam _Alloc Allocator type, defaults to allocator<_CharT>.
2551  *
2552  * Meets the requirements of a <a href="tables.html#65">container</a>, a
2553  * <a href="tables.html#66">reversible container</a>, and a
2554  * <a href="tables.html#67">sequence</a>. Of the
2555  * <a href="tables.html#68">optional sequence requirements</a>, only
2556  * @c push_back, @c at, and @c %array access are supported.
2557  *
2558  * @doctodo
2559  *
2560  *
2561  * Documentation? What's that?
2562  * Nathan Myers <ncm@cantrip.org>.
2563  *
2564  * A string looks like this:
2565  *
2566  * @code
2567  * [_Rep]
2568  * _M_length
2569  * [basic_string<char_type>] _M_capacity
2570  * _M_dataplus _M_refcount
2571  * _M_p ----------------> unnamed array of char_type
2572  * @endcode
2573  *
2574  * Where the _M_p points to the first character in the string, and
2575  * you cast it to a pointer-to-_Rep and subtract 1 to get a
2576  * pointer to the header.
2577  *
2578  * This approach has the enormous advantage that a string object
2579  * requires only one allocation. All the ugliness is confined
2580  * within a single %pair of inline functions, which each compile to
2581  * a single @a add instruction: _Rep::_M_data(), and
2582  * string::_M_rep(); and the allocation function which gets a
2583  * block of raw bytes and with room enough and constructs a _Rep
2584  * object at the front.
2585  *
2586  * The reason you want _M_data pointing to the character %array and
2587  * not the _Rep is so that the debugger can see the string
2588  * contents. (Probably we should add a non-inline member to get
2589  * the _Rep for the debugger to use, so users can check the actual
2590  * string length.)
2591  *
2592  * Note that the _Rep object is a POD so that you can have a
2593  * static <em>empty string</em> _Rep object already @a constructed before
2594  * static constructors have run. The reference-count encoding is
2595  * chosen so that a 0 indicates one reference, so you never try to
2596  * destroy the empty-string _Rep object.
2597  *
2598  * All but the last paragraph is considered pretty conventional
2599  * for a C++ string implementation.
2600  */
2601  // 21.3 Template class basic_string
2602  template<typename _CharT, typename _Traits, typename _Alloc>
2603  class basic_string
2604  {
2605  typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;
2606 
2607  // Types:
2608  public:
2609  typedef _Traits traits_type;
2610  typedef typename _Traits::char_type value_type;
2611  typedef _Alloc allocator_type;
2612  typedef typename _CharT_alloc_type::size_type size_type;
2613  typedef typename _CharT_alloc_type::difference_type difference_type;
2614  typedef typename _CharT_alloc_type::reference reference;
2615  typedef typename _CharT_alloc_type::const_reference const_reference;
2616  typedef typename _CharT_alloc_type::pointer pointer;
2617  typedef typename _CharT_alloc_type::const_pointer const_pointer;
2618  typedef __gnu_cxx::__normal_iterator<pointer, basic_string> iterator;
2619  typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
2620  const_iterator;
2621  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
2622  typedef std::reverse_iterator<iterator> reverse_iterator;
2623 
2624  private:
2625  // _Rep: string representation
2626  // Invariants:
2627  // 1. String really contains _M_length + 1 characters: due to 21.3.4
2628  // must be kept null-terminated.
2629  // 2. _M_capacity >= _M_length
2630  // Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).
2631  // 3. _M_refcount has three states:
2632  // -1: leaked, one reference, no ref-copies allowed, non-const.
2633  // 0: one reference, non-const.
2634  // n>0: n + 1 references, operations require a lock, const.
2635  // 4. All fields==0 is an empty string, given the extra storage
2636  // beyond-the-end for a null terminator; thus, the shared
2637  // empty string representation needs no constructor.
2638 
2639  struct _Rep_base
2640  {
2641  size_type _M_length;
2642  size_type _M_capacity;
2643  _Atomic_word _M_refcount;
2644  };
2645 
2646  struct _Rep : _Rep_base
2647  {
2648  // Types:
2649  typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
2650 
2651  // (Public) Data members:
2652 
2653  // The maximum number of individual char_type elements of an
2654  // individual string is determined by _S_max_size. This is the
2655  // value that will be returned by max_size(). (Whereas npos
2656  // is the maximum number of bytes the allocator can allocate.)
2657  // If one was to divvy up the theoretical largest size string,
2658  // with a terminating character and m _CharT elements, it'd
2659  // look like this:
2660  // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
2661  // Solving for m:
2662  // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
2663  // In addition, this implementation quarters this amount.
2664  static const size_type _S_max_size;
2665  static const _CharT _S_terminal;
2666 
2667  // The following storage is init'd to 0 by the linker, resulting
2668  // (carefully) in an empty string with one reference.
2669  static size_type _S_empty_rep_storage[];
2670 
2671  static _Rep&
2672  _S_empty_rep() _GLIBCXX_NOEXCEPT
2673  {
2674  // NB: Mild hack to avoid strict-aliasing warnings. Note that
2675  // _S_empty_rep_storage is never modified and the punning should
2676  // be reasonably safe in this case.
2677  void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);
2678  return *reinterpret_cast<_Rep*>(__p);
2679  }
2680 
2681  bool
2682  _M_is_leaked() const _GLIBCXX_NOEXCEPT
2683  { return this->_M_refcount < 0; }
2684 
2685  bool
2686  _M_is_shared() const _GLIBCXX_NOEXCEPT
2687  { return this->_M_refcount > 0; }
2688 
2689  void
2690  _M_set_leaked() _GLIBCXX_NOEXCEPT
2691  { this->_M_refcount = -1; }
2692 
2693  void
2694  _M_set_sharable() _GLIBCXX_NOEXCEPT
2695  { this->_M_refcount = 0; }
2696 
2697  void
2698  _M_set_length_and_sharable(size_type __n) _GLIBCXX_NOEXCEPT
2699  {
2700 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2701  if (__builtin_expect(this != &_S_empty_rep(), false))
2702 #endif
2703  {
2704  this->_M_set_sharable(); // One reference.
2705  this->_M_length = __n;
2706  traits_type::assign(this->_M_refdata()[__n], _S_terminal);
2707  // grrr. (per 21.3.4)
2708  // You cannot leave those LWG people alone for a second.
2709  }
2710  }
2711 
2712  _CharT*
2713  _M_refdata() throw()
2714  { return reinterpret_cast<_CharT*>(this + 1); }
2715 
2716  _CharT*
2717  _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
2718  {
2719  return (!_M_is_leaked() && __alloc1 == __alloc2)
2720  ? _M_refcopy() : _M_clone(__alloc1);
2721  }
2722 
2723  // Create & Destroy
2724  static _Rep*
2725  _S_create(size_type, size_type, const _Alloc&);
2726 
2727  void
2728  _M_dispose(const _Alloc& __a) _GLIBCXX_NOEXCEPT
2729  {
2730 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2731  if (__builtin_expect(this != &_S_empty_rep(), false))
2732 #endif
2733  {
2734  // Be race-detector-friendly. For more info see bits/c++config.
2735  _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this->_M_refcount);
2736  if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
2737  -1) <= 0)
2738  {
2739  _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);
2740  _M_destroy(__a);
2741  }
2742  }
2743  } // XXX MT
2744 
2745  void
2746  _M_destroy(const _Alloc&) throw();
2747 
2748  _CharT*
2749  _M_refcopy() throw()
2750  {
2751 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2752  if (__builtin_expect(this != &_S_empty_rep(), false))
2753 #endif
2754  __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
2755  return _M_refdata();
2756  } // XXX MT
2757 
2758  _CharT*
2759  _M_clone(const _Alloc&, size_type __res = 0);
2760  };
2761 
2762  // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
2763  struct _Alloc_hider : _Alloc
2764  {
2765  _Alloc_hider(_CharT* __dat, const _Alloc& __a) _GLIBCXX_NOEXCEPT
2766  : _Alloc(__a), _M_p(__dat) { }
2767 
2768  _CharT* _M_p; // The actual data.
2769  };
2770 
2771  public:
2772  // Data Members (public):
2773  // NB: This is an unsigned type, and thus represents the maximum
2774  // size that the allocator can hold.
2775  /// Value returned by various member functions when they fail.
2776  static const size_type npos = static_cast<size_type>(-1);
2777 
2778  private:
2779  // Data Members (private):
2780  mutable _Alloc_hider _M_dataplus;
2781 
2782  _CharT*
2783  _M_data() const _GLIBCXX_NOEXCEPT
2784  { return _M_dataplus._M_p; }
2785 
2786  _CharT*
2787  _M_data(_CharT* __p) _GLIBCXX_NOEXCEPT
2788  { return (_M_dataplus._M_p = __p); }
2789 
2790  _Rep*
2791  _M_rep() const _GLIBCXX_NOEXCEPT
2792  { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
2793 
2794  // For the internal use we have functions similar to `begin'/`end'
2795  // but they do not call _M_leak.
2796  iterator
2797  _M_ibegin() const _GLIBCXX_NOEXCEPT
2798  { return iterator(_M_data()); }
2799 
2800  iterator
2801  _M_iend() const _GLIBCXX_NOEXCEPT
2802  { return iterator(_M_data() + this->size()); }
2803 
2804  void
2805  _M_leak() // for use in begin() & non-const op[]
2806  {
2807  if (!_M_rep()->_M_is_leaked())
2808  _M_leak_hard();
2809  }
2810 
2811  size_type
2812  _M_check(size_type __pos, const char* __s) const
2813  {
2814  if (__pos > this->size())
2815  __throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "
2816  "this->size() (which is %zu)"),
2817  __s, __pos, this->size());
2818  return __pos;
2819  }
2820 
2821  void
2822  _M_check_length(size_type __n1, size_type __n2, const char* __s) const
2823  {
2824  if (this->max_size() - (this->size() - __n1) < __n2)
2825  __throw_length_error(__N(__s));
2826  }
2827 
2828  // NB: _M_limit doesn't check for a bad __pos value.
2829  size_type
2830  _M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPT
2831  {
2832  const bool __testoff = __off < this->size() - __pos;
2833  return __testoff ? __off : this->size() - __pos;
2834  }
2835 
2836  // True if _Rep and source do not overlap.
2837  bool
2838  _M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPT
2839  {
2840  return (less<const _CharT*>()(__s, _M_data())
2841  || less<const _CharT*>()(_M_data() + this->size(), __s));
2842  }
2843 
2844  // When __n = 1 way faster than the general multichar
2845  // traits_type::copy/move/assign.
2846  static void
2847  _M_copy(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT
2848  {
2849  if (__n == 1)
2850  traits_type::assign(*__d, *__s);
2851  else
2852  traits_type::copy(__d, __s, __n);
2853  }
2854 
2855  static void
2856  _M_move(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT
2857  {
2858  if (__n == 1)
2859  traits_type::assign(*__d, *__s);
2860  else
2861  traits_type::move(__d, __s, __n);
2862  }
2863 
2864  static void
2865  _M_assign(_CharT* __d, size_type __n, _CharT __c) _GLIBCXX_NOEXCEPT
2866  {
2867  if (__n == 1)
2868  traits_type::assign(*__d, __c);
2869  else
2870  traits_type::assign(__d, __n, __c);
2871  }
2872 
2873  // _S_copy_chars is a separate template to permit specialization
2874  // to optimize for the common case of pointers as iterators.
2875  template<class _Iterator>
2876  static void
2877  _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
2878  {
2879  for (; __k1 != __k2; ++__k1, ++__p)
2880  traits_type::assign(*__p, *__k1); // These types are off.
2881  }
2882 
2883  static void
2884  _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) _GLIBCXX_NOEXCEPT
2885  { _S_copy_chars(__p, __k1.base(), __k2.base()); }
2886 
2887  static void
2888  _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
2889  _GLIBCXX_NOEXCEPT
2890  { _S_copy_chars(__p, __k1.base(), __k2.base()); }
2891 
2892  static void
2893  _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) _GLIBCXX_NOEXCEPT
2894  { _M_copy(__p, __k1, __k2 - __k1); }
2895 
2896  static void
2897  _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
2898  _GLIBCXX_NOEXCEPT
2899  { _M_copy(__p, __k1, __k2 - __k1); }
2900 
2901  static int
2902  _S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPT
2903  {
2904  const difference_type __d = difference_type(__n1 - __n2);
2905 
2906  if (__d > __gnu_cxx::__numeric_traits<int>::__max)
2907  return __gnu_cxx::__numeric_traits<int>::__max;
2908  else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
2909  return __gnu_cxx::__numeric_traits<int>::__min;
2910  else
2911  return int(__d);
2912  }
2913 
2914  void
2915  _M_mutate(size_type __pos, size_type __len1, size_type __len2);
2916 
2917  void
2918  _M_leak_hard();
2919 
2920  static _Rep&
2921  _S_empty_rep() _GLIBCXX_NOEXCEPT
2922  { return _Rep::_S_empty_rep(); }
2923 
2924  public:
2925  // Construct/copy/destroy:
2926  // NB: We overload ctors in some cases instead of using default
2927  // arguments, per 17.4.4.4 para. 2 item 2.
2928 
2929  /**
2930  * @brief Default constructor creates an empty string.
2931  */
2933 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2934  : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
2935 #else
2936  : _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()){ }
2937 #endif
2938 
2939  /**
2940  * @brief Construct an empty string using allocator @a a.
2941  */
2942  explicit
2943  basic_string(const _Alloc& __a);
2944 
2945  // NB: per LWG issue 42, semantics different from IS:
2946  /**
2947  * @brief Construct string with copy of value of @a str.
2948  * @param __str Source string.
2949  */
2950  basic_string(const basic_string& __str);
2951  /**
2952  * @brief Construct string as copy of a substring.
2953  * @param __str Source string.
2954  * @param __pos Index of first character to copy from.
2955  * @param __n Number of characters to copy (default remainder).
2956  */
2957  basic_string(const basic_string& __str, size_type __pos,
2958  size_type __n = npos);
2959  /**
2960  * @brief Construct string as copy of a substring.
2961  * @param __str Source string.
2962  * @param __pos Index of first character to copy from.
2963  * @param __n Number of characters to copy.
2964  * @param __a Allocator to use.
2965  */
2966  basic_string(const basic_string& __str, size_type __pos,
2967  size_type __n, const _Alloc& __a);
2968 
2969  /**
2970  * @brief Construct string initialized by a character %array.
2971  * @param __s Source character %array.
2972  * @param __n Number of characters to copy.
2973  * @param __a Allocator to use (default is default allocator).
2974  *
2975  * NB: @a __s must have at least @a __n characters, &apos;\\0&apos;
2976  * has no special meaning.
2977  */
2978  basic_string(const _CharT* __s, size_type __n,
2979  const _Alloc& __a = _Alloc());
2980  /**
2981  * @brief Construct string as copy of a C string.
2982  * @param __s Source C string.
2983  * @param __a Allocator to use (default is default allocator).
2984  */
2985  basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
2986  /**
2987  * @brief Construct string as multiple characters.
2988  * @param __n Number of characters.
2989  * @param __c Character to use.
2990  * @param __a Allocator to use (default is default allocator).
2991  */
2992  basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
2993 
2994 #if __cplusplus >= 201103L
2995  /**
2996  * @brief Move construct string.
2997  * @param __str Source string.
2998  *
2999  * The newly-created string contains the exact contents of @a __str.
3000  * @a __str is a valid, but unspecified string.
3001  **/
3002  basic_string(basic_string&& __str)
3003 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
3004  noexcept // FIXME C++11: should always be noexcept.
3005 #endif
3006  : _M_dataplus(__str._M_dataplus)
3007  {
3008 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
3009  __str._M_data(_S_empty_rep()._M_refdata());
3010 #else
3011  __str._M_data(_S_construct(size_type(), _CharT(), get_allocator()));
3012 #endif
3013  }
3014 
3015  /**
3016  * @brief Construct string from an initializer %list.
3017  * @param __l std::initializer_list of characters.
3018  * @param __a Allocator to use (default is default allocator).
3019  */
3020  basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc());
3021 #endif // C++11
3022 
3023  /**
3024  * @brief Construct string as copy of a range.
3025  * @param __beg Start of range.
3026  * @param __end End of range.
3027  * @param __a Allocator to use (default is default allocator).
3028  */
3029  template<class _InputIterator>
3030  basic_string(_InputIterator __beg, _InputIterator __end,
3031  const _Alloc& __a = _Alloc());
3032 
3033  /**
3034  * @brief Destroy the string instance.
3035  */
3036  ~basic_string() _GLIBCXX_NOEXCEPT
3037  { _M_rep()->_M_dispose(this->get_allocator()); }
3038 
3039  /**
3040  * @brief Assign the value of @a str to this string.
3041  * @param __str Source string.
3042  */
3043  basic_string&
3044  operator=(const basic_string& __str)
3045  { return this->assign(__str); }
3046 
3047  /**
3048  * @brief Copy contents of @a s into this string.
3049  * @param __s Source null-terminated string.
3050  */
3051  basic_string&
3052  operator=(const _CharT* __s)
3053  { return this->assign(__s); }
3054 
3055  /**
3056  * @brief Set value to string of length 1.
3057  * @param __c Source character.
3058  *
3059  * Assigning to a character makes this string length 1 and
3060  * (*this)[0] == @a c.
3061  */
3062  basic_string&
3063  operator=(_CharT __c)
3064  {
3065  this->assign(1, __c);
3066  return *this;
3067  }
3068 
3069 #if __cplusplus >= 201103L
3070  /**
3071  * @brief Move assign the value of @a str to this string.
3072  * @param __str Source string.
3073  *
3074  * The contents of @a str are moved into this string (without copying).
3075  * @a str is a valid, but unspecified string.
3076  **/
3077  // PR 58265, this should be noexcept.
3078  basic_string&
3079  operator=(basic_string&& __str)
3080  {
3081  // NB: DR 1204.
3082  this->swap(__str);
3083  return *this;
3084  }
3085 
3086  /**
3087  * @brief Set value to string constructed from initializer %list.
3088  * @param __l std::initializer_list.
3089  */
3090  basic_string&
3092  {
3093  this->assign(__l.begin(), __l.size());
3094  return *this;
3095  }
3096 #endif // C++11
3097 
3098  // Iterators:
3099  /**
3100  * Returns a read/write iterator that points to the first character in
3101  * the %string. Unshares the string.
3102  */
3103  iterator
3104  begin() // FIXME C++11: should be noexcept.
3105  {
3106  _M_leak();
3107  return iterator(_M_data());
3108  }
3109 
3110  /**
3111  * Returns a read-only (constant) iterator that points to the first
3112  * character in the %string.
3113  */
3114  const_iterator
3115  begin() const _GLIBCXX_NOEXCEPT
3116  { return const_iterator(_M_data()); }
3117 
3118  /**
3119  * Returns a read/write iterator that points one past the last
3120  * character in the %string. Unshares the string.
3121  */
3122  iterator
3123  end() // FIXME C++11: should be noexcept.
3124  {
3125  _M_leak();
3126  return iterator(_M_data() + this->size());
3127  }
3128 
3129  /**
3130  * Returns a read-only (constant) iterator that points one past the
3131  * last character in the %string.
3132  */
3133  const_iterator
3134  end() const _GLIBCXX_NOEXCEPT
3135  { return const_iterator(_M_data() + this->size()); }
3136 
3137  /**
3138  * Returns a read/write reverse iterator that points to the last
3139  * character in the %string. Iteration is done in reverse element
3140  * order. Unshares the string.
3141  */
3142  reverse_iterator
3143  rbegin() // FIXME C++11: should be noexcept.
3144  { return reverse_iterator(this->end()); }
3145 
3146  /**
3147  * Returns a read-only (constant) reverse iterator that points
3148  * to the last character in the %string. Iteration is done in
3149  * reverse element order.
3150  */
3151  const_reverse_iterator
3152  rbegin() const _GLIBCXX_NOEXCEPT
3153  { return const_reverse_iterator(this->end()); }
3154 
3155  /**
3156  * Returns a read/write reverse iterator that points to one before the
3157  * first character in the %string. Iteration is done in reverse
3158  * element order. Unshares the string.
3159  */
3160  reverse_iterator
3161  rend() // FIXME C++11: should be noexcept.
3162  { return reverse_iterator(this->begin()); }
3163 
3164  /**
3165  * Returns a read-only (constant) reverse iterator that points
3166  * to one before the first character in the %string. Iteration
3167  * is done in reverse element order.
3168  */
3169  const_reverse_iterator
3170  rend() const _GLIBCXX_NOEXCEPT
3171  { return const_reverse_iterator(this->begin()); }
3172 
3173 #if __cplusplus >= 201103L
3174  /**
3175  * Returns a read-only (constant) iterator that points to the first
3176  * character in the %string.
3177  */
3178  const_iterator
3179  cbegin() const noexcept
3180  { return const_iterator(this->_M_data()); }
3181 
3182  /**
3183  * Returns a read-only (constant) iterator that points one past the
3184  * last character in the %string.
3185  */
3186  const_iterator
3187  cend() const noexcept
3188  { return const_iterator(this->_M_data() + this->size()); }
3189 
3190  /**
3191  * Returns a read-only (constant) reverse iterator that points
3192  * to the last character in the %string. Iteration is done in
3193  * reverse element order.
3194  */
3195  const_reverse_iterator
3196  crbegin() const noexcept
3197  { return const_reverse_iterator(this->end()); }
3198 
3199  /**
3200  * Returns a read-only (constant) reverse iterator that points
3201  * to one before the first character in the %string. Iteration
3202  * is done in reverse element order.
3203  */
3204  const_reverse_iterator
3205  crend() const noexcept
3206  { return const_reverse_iterator(this->begin()); }
3207 #endif
3208 
3209  public:
3210  // Capacity:
3211  /// Returns the number of characters in the string, not including any
3212  /// null-termination.
3213  size_type
3214  size() const _GLIBCXX_NOEXCEPT
3215  { return _M_rep()->_M_length; }
3216 
3217  /// Returns the number of characters in the string, not including any
3218  /// null-termination.
3219  size_type
3220  length() const _GLIBCXX_NOEXCEPT
3221  { return _M_rep()->_M_length; }
3222 
3223  /// Returns the size() of the largest possible %string.
3224  size_type
3225  max_size() const _GLIBCXX_NOEXCEPT
3226  { return _Rep::_S_max_size; }
3227 
3228  /**
3229  * @brief Resizes the %string to the specified number of characters.
3230  * @param __n Number of characters the %string should contain.
3231  * @param __c Character to fill any new elements.
3232  *
3233  * This function will %resize the %string to the specified
3234  * number of characters. If the number is smaller than the
3235  * %string's current size the %string is truncated, otherwise
3236  * the %string is extended and new elements are %set to @a __c.
3237  */
3238  void
3239  resize(size_type __n, _CharT __c);
3240 
3241  /**
3242  * @brief Resizes the %string to the specified number of characters.
3243  * @param __n Number of characters the %string should contain.
3244  *
3245  * This function will resize the %string to the specified length. If
3246  * the new size is smaller than the %string's current size the %string
3247  * is truncated, otherwise the %string is extended and new characters
3248  * are default-constructed. For basic types such as char, this means
3249  * setting them to 0.
3250  */
3251  void
3252  resize(size_type __n)
3253  { this->resize(__n, _CharT()); }
3254 
3255 #if __cplusplus >= 201103L
3256  /// A non-binding request to reduce capacity() to size().
3257  void
3258  shrink_to_fit() _GLIBCXX_NOEXCEPT
3259  {
3260 #if __cpp_exceptions
3261  if (capacity() > size())
3262  {
3263  try
3264  { reserve(0); }
3265  catch(...)
3266  { }
3267  }
3268 #endif
3269  }
3270 #endif
3271 
3272  /**
3273  * Returns the total number of characters that the %string can hold
3274  * before needing to allocate more memory.
3275  */
3276  size_type
3277  capacity() const _GLIBCXX_NOEXCEPT
3278  { return _M_rep()->_M_capacity; }
3279 
3280  /**
3281  * @brief Attempt to preallocate enough memory for specified number of
3282  * characters.
3283  * @param __res_arg Number of characters required.
3284  * @throw std::length_error If @a __res_arg exceeds @c max_size().
3285  *
3286  * This function attempts to reserve enough memory for the
3287  * %string to hold the specified number of characters. If the
3288  * number requested is more than max_size(), length_error is
3289  * thrown.
3290  *
3291  * The advantage of this function is that if optimal code is a
3292  * necessity and the user can determine the string length that will be
3293  * required, the user can reserve the memory in %advance, and thus
3294  * prevent a possible reallocation of memory and copying of %string
3295  * data.
3296  */
3297  void
3298  reserve(size_type __res_arg = 0);
3299 
3300  /**
3301  * Erases the string, making it empty.
3302  */
3303  // PR 56166: this should not throw.
3304  void
3306  { _M_mutate(0, this->size(), 0); }
3307 
3308  /**
3309  * Returns true if the %string is empty. Equivalent to
3310  * <code>*this == ""</code>.
3311  */
3312  bool
3313  empty() const _GLIBCXX_NOEXCEPT
3314  { return this->size() == 0; }
3315 
3316  // Element access:
3317  /**
3318  * @brief Subscript access to the data contained in the %string.
3319  * @param __pos The index of the character to access.
3320  * @return Read-only (constant) reference to the character.
3321  *
3322  * This operator allows for easy, array-style, data access.
3323  * Note that data access with this operator is unchecked and
3324  * out_of_range lookups are not defined. (For checked lookups
3325  * see at().)
3326  */
3327  const_reference
3328  operator[] (size_type __pos) const _GLIBCXX_NOEXCEPT
3329  {
3330  _GLIBCXX_DEBUG_ASSERT(__pos <= size());
3331  return _M_data()[__pos];
3332  }
3333 
3334  /**
3335  * @brief Subscript access to the data contained in the %string.
3336  * @param __pos The index of the character to access.
3337  * @return Read/write reference to the character.
3338  *
3339  * This operator allows for easy, array-style, data access.
3340  * Note that data access with this operator is unchecked and
3341  * out_of_range lookups are not defined. (For checked lookups
3342  * see at().) Unshares the string.
3343  */
3344  reference
3345  operator[](size_type __pos)
3346  {
3347  // Allow pos == size() both in C++98 mode, as v3 extension,
3348  // and in C++11 mode.
3349  _GLIBCXX_DEBUG_ASSERT(__pos <= size());
3350  // In pedantic mode be strict in C++98 mode.
3351  _GLIBCXX_DEBUG_PEDASSERT(__cplusplus >= 201103L || __pos < size());
3352  _M_leak();
3353  return _M_data()[__pos];
3354  }
3355 
3356  /**
3357  * @brief Provides access to the data contained in the %string.
3358  * @param __n The index of the character to access.
3359  * @return Read-only (const) reference to the character.
3360  * @throw std::out_of_range If @a n is an invalid index.
3361  *
3362  * This function provides for safer data access. The parameter is
3363  * first checked that it is in the range of the string. The function
3364  * throws out_of_range if the check fails.
3365  */
3366  const_reference
3367  at(size_type __n) const
3368  {
3369  if (__n >= this->size())
3370  __throw_out_of_range_fmt(__N("basic_string::at: __n "
3371  "(which is %zu) >= this->size() "
3372  "(which is %zu)"),
3373  __n, this->size());
3374  return _M_data()[__n];
3375  }
3376 
3377  /**
3378  * @brief Provides access to the data contained in the %string.
3379  * @param __n The index of the character to access.
3380  * @return Read/write reference to the character.
3381  * @throw std::out_of_range If @a n is an invalid index.
3382  *
3383  * This function provides for safer data access. The parameter is
3384  * first checked that it is in the range of the string. The function
3385  * throws out_of_range if the check fails. Success results in
3386  * unsharing the string.
3387  */
3388  reference
3389  at(size_type __n)
3390  {
3391  if (__n >= size())
3392  __throw_out_of_range_fmt(__N("basic_string::at: __n "
3393  "(which is %zu) >= this->size() "
3394  "(which is %zu)"),
3395  __n, this->size());
3396  _M_leak();
3397  return _M_data()[__n];
3398  }
3399 
3400 #if __cplusplus >= 201103L
3401  /**
3402  * Returns a read/write reference to the data at the first
3403  * element of the %string.
3404  */
3405  reference
3407  { return operator[](0); }
3408 
3409  /**
3410  * Returns a read-only (constant) reference to the data at the first
3411  * element of the %string.
3412  */
3413  const_reference
3414  front() const _GLIBCXX_NOEXCEPT
3415  { return operator[](0); }
3416 
3417  /**
3418  * Returns a read/write reference to the data at the last
3419  * element of the %string.
3420  */
3421  reference
3423  { return operator[](this->size() - 1); }
3424 
3425  /**
3426  * Returns a read-only (constant) reference to the data at the
3427  * last element of the %string.
3428  */
3429  const_reference
3430  back() const _GLIBCXX_NOEXCEPT
3431  { return operator[](this->size() - 1); }
3432 #endif
3433 
3434  // Modifiers:
3435  /**
3436  * @brief Append a string to this string.
3437  * @param __str The string to append.
3438  * @return Reference to this string.
3439  */
3440  basic_string&
3441  operator+=(const basic_string& __str)
3442  { return this->append(__str); }
3443 
3444  /**
3445  * @brief Append a C string.
3446  * @param __s The C string to append.
3447  * @return Reference to this string.
3448  */
3449  basic_string&
3450  operator+=(const _CharT* __s)
3451  { return this->append(__s); }
3452 
3453  /**
3454  * @brief Append a character.
3455  * @param __c The character to append.
3456  * @return Reference to this string.
3457  */
3458  basic_string&
3459  operator+=(_CharT __c)
3460  {
3461  this->push_back(__c);
3462  return *this;
3463  }
3464 
3465 #if __cplusplus >= 201103L
3466  /**
3467  * @brief Append an initializer_list of characters.
3468  * @param __l The initializer_list of characters to be appended.
3469  * @return Reference to this string.
3470  */
3471  basic_string&
3473  { return this->append(__l.begin(), __l.size()); }
3474 #endif // C++11
3475 
3476  /**
3477  * @brief Append a string to this string.
3478  * @param __str The string to append.
3479  * @return Reference to this string.
3480  */
3481  basic_string&
3482  append(const basic_string& __str);
3483 
3484  /**
3485  * @brief Append a substring.
3486  * @param __str The string to append.
3487  * @param __pos Index of the first character of str to append.
3488  * @param __n The number of characters to append.
3489  * @return Reference to this string.
3490  * @throw std::out_of_range if @a __pos is not a valid index.
3491  *
3492  * This function appends @a __n characters from @a __str
3493  * starting at @a __pos to this string. If @a __n is is larger
3494  * than the number of available characters in @a __str, the
3495  * remainder of @a __str is appended.
3496  */
3497  basic_string&
3498  append(const basic_string& __str, size_type __pos, size_type __n);
3499 
3500  /**
3501  * @brief Append a C substring.
3502  * @param __s The C string to append.
3503  * @param __n The number of characters to append.
3504  * @return Reference to this string.
3505  */
3506  basic_string&
3507  append(const _CharT* __s, size_type __n);
3508 
3509  /**
3510  * @brief Append a C string.
3511  * @param __s The C string to append.
3512  * @return Reference to this string.
3513  */
3514  basic_string&
3515  append(const _CharT* __s)
3516  {
3517  __glibcxx_requires_string(__s);
3518  return this->append(__s, traits_type::length(__s));
3519  }
3520 
3521  /**
3522  * @brief Append multiple characters.
3523  * @param __n The number of characters to append.
3524  * @param __c The character to use.
3525  * @return Reference to this string.
3526  *
3527  * Appends __n copies of __c to this string.
3528  */
3529  basic_string&
3530  append(size_type __n, _CharT __c);
3531 
3532 #if __cplusplus >= 201103L
3533  /**
3534  * @brief Append an initializer_list of characters.
3535  * @param __l The initializer_list of characters to append.
3536  * @return Reference to this string.
3537  */
3538  basic_string&
3540  { return this->append(__l.begin(), __l.size()); }
3541 #endif // C++11
3542 
3543  /**
3544  * @brief Append a range of characters.
3545  * @param __first Iterator referencing the first character to append.
3546  * @param __last Iterator marking the end of the range.
3547  * @return Reference to this string.
3548  *
3549  * Appends characters in the range [__first,__last) to this string.
3550  */
3551  template<class _InputIterator>
3552  basic_string&
3553  append(_InputIterator __first, _InputIterator __last)
3554  { return this->replace(_M_iend(), _M_iend(), __first, __last); }
3555 
3556  /**
3557  * @brief Append a single character.
3558  * @param __c Character to append.
3559  */
3560  void
3561  push_back(_CharT __c)
3562  {
3563  const size_type __len = 1 + this->size();
3564  if (__len > this->capacity() || _M_rep()->_M_is_shared())
3565  this->reserve(__len);
3566  traits_type::assign(_M_data()[this->size()], __c);
3567  _M_rep()->_M_set_length_and_sharable(__len);
3568  }
3569 
3570  /**
3571  * @brief Set value to contents of another string.
3572  * @param __str Source string to use.
3573  * @return Reference to this string.
3574  */
3575  basic_string&
3576  assign(const basic_string& __str);
3577 
3578 #if __cplusplus >= 201103L
3579  /**
3580  * @brief Set value to contents of another string.
3581  * @param __str Source string to use.
3582  * @return Reference to this string.
3583  *
3584  * This function sets this string to the exact contents of @a __str.
3585  * @a __str is a valid, but unspecified string.
3586  */
3587  // PR 58265, this should be noexcept.
3588  basic_string&
3589  assign(basic_string&& __str)
3590  {
3591  this->swap(__str);
3592  return *this;
3593  }
3594 #endif // C++11
3595 
3596  /**
3597  * @brief Set value to a substring of a string.
3598  * @param __str The string to use.
3599  * @param __pos Index of the first character of str.
3600  * @param __n Number of characters to use.
3601  * @return Reference to this string.
3602  * @throw std::out_of_range if @a pos is not a valid index.
3603  *
3604  * This function sets this string to the substring of @a __str
3605  * consisting of @a __n characters at @a __pos. If @a __n is
3606  * is larger than the number of available characters in @a
3607  * __str, the remainder of @a __str is used.
3608  */
3609  basic_string&
3610  assign(const basic_string& __str, size_type __pos, size_type __n)
3611  { return this->assign(__str._M_data()
3612  + __str._M_check(__pos, "basic_string::assign"),
3613  __str._M_limit(__pos, __n)); }
3614 
3615  /**
3616  * @brief Set value to a C substring.
3617  * @param __s The C string to use.
3618  * @param __n Number of characters to use.
3619  * @return Reference to this string.
3620  *
3621  * This function sets the value of this string to the first @a __n
3622  * characters of @a __s. If @a __n is is larger than the number of
3623  * available characters in @a __s, the remainder of @a __s is used.
3624  */
3625  basic_string&
3626  assign(const _CharT* __s, size_type __n);
3627 
3628  /**
3629  * @brief Set value to contents of a C string.
3630  * @param __s The C string to use.
3631  * @return Reference to this string.
3632  *
3633  * This function sets the value of this string to the value of @a __s.
3634  * The data is copied, so there is no dependence on @a __s once the
3635  * function returns.
3636  */
3637  basic_string&
3638  assign(const _CharT* __s)
3639  {
3640  __glibcxx_requires_string(__s);
3641  return this->assign(__s, traits_type::length(__s));
3642  }
3643 
3644  /**
3645  * @brief Set value to multiple characters.
3646  * @param __n Length of the resulting string.
3647  * @param __c The character to use.
3648  * @return Reference to this string.
3649  *
3650  * This function sets the value of this string to @a __n copies of
3651  * character @a __c.
3652  */
3653  basic_string&
3654  assign(size_type __n, _CharT __c)
3655  { return _M_replace_aux(size_type(0), this->size(), __n, __c); }
3656 
3657  /**
3658  * @brief Set value to a range of characters.
3659  * @param __first Iterator referencing the first character to append.
3660  * @param __last Iterator marking the end of the range.
3661  * @return Reference to this string.
3662  *
3663  * Sets value of string to characters in the range [__first,__last).
3664  */
3665  template<class _InputIterator>
3666  basic_string&
3667  assign(_InputIterator __first, _InputIterator __last)
3668  { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
3669 
3670 #if __cplusplus >= 201103L
3671  /**
3672  * @brief Set value to an initializer_list of characters.
3673  * @param __l The initializer_list of characters to assign.
3674  * @return Reference to this string.
3675  */
3676  basic_string&
3678  { return this->assign(__l.begin(), __l.size()); }
3679 #endif // C++11
3680 
3681  /**
3682  * @brief Insert multiple characters.
3683  * @param __p Iterator referencing location in string to insert at.
3684  * @param __n Number of characters to insert
3685  * @param __c The character to insert.
3686  * @throw std::length_error If new length exceeds @c max_size().
3687  *
3688  * Inserts @a __n copies of character @a __c starting at the
3689  * position referenced by iterator @a __p. If adding
3690  * characters causes the length to exceed max_size(),
3691  * length_error is thrown. The value of the string doesn't
3692  * change if an error is thrown.
3693  */
3694  void
3695  insert(iterator __p, size_type __n, _CharT __c)
3696  { this->replace(__p, __p, __n, __c); }
3697 
3698  /**
3699  * @brief Insert a range of characters.
3700  * @param __p Iterator referencing location in string to insert at.
3701  * @param __beg Start of range.
3702  * @param __end End of range.
3703  * @throw std::length_error If new length exceeds @c max_size().
3704  *
3705  * Inserts characters in range [__beg,__end). If adding
3706  * characters causes the length to exceed max_size(),
3707  * length_error is thrown. The value of the string doesn't
3708  * change if an error is thrown.
3709  */
3710  template<class _InputIterator>
3711  void
3712  insert(iterator __p, _InputIterator __beg, _InputIterator __end)
3713  { this->replace(__p, __p, __beg, __end); }
3714 
3715 #if __cplusplus >= 201103L
3716  /**
3717  * @brief Insert an initializer_list of characters.
3718  * @param __p Iterator referencing location in string to insert at.
3719  * @param __l The initializer_list of characters to insert.
3720  * @throw std::length_error If new length exceeds @c max_size().
3721  */
3722  void
3724  {
3725  _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
3726  this->insert(__p - _M_ibegin(), __l.begin(), __l.size());
3727  }
3728 #endif // C++11
3729 
3730  /**
3731  * @brief Insert value of a string.
3732  * @param __pos1 Iterator referencing location in string to insert at.
3733  * @param __str The string to insert.
3734  * @return Reference to this string.
3735  * @throw std::length_error If new length exceeds @c max_size().
3736  *
3737  * Inserts value of @a __str starting at @a __pos1. If adding
3738  * characters causes the length to exceed max_size(),
3739  * length_error is thrown. The value of the string doesn't
3740  * change if an error is thrown.
3741  */
3742  basic_string&
3743  insert(size_type __pos1, const basic_string& __str)
3744  { return this->insert(__pos1, __str, size_type(0), __str.size()); }
3745 
3746  /**
3747  * @brief Insert a substring.
3748  * @param __pos1 Iterator referencing location in string to insert at.
3749  * @param __str The string to insert.
3750  * @param __pos2 Start of characters in str to insert.
3751  * @param __n Number of characters to insert.
3752  * @return Reference to this string.
3753  * @throw std::length_error If new length exceeds @c max_size().
3754  * @throw std::out_of_range If @a pos1 > size() or
3755  * @a __pos2 > @a str.size().
3756  *
3757  * Starting at @a pos1, insert @a __n character of @a __str
3758  * beginning with @a __pos2. If adding characters causes the
3759  * length to exceed max_size(), length_error is thrown. If @a
3760  * __pos1 is beyond the end of this string or @a __pos2 is
3761  * beyond the end of @a __str, out_of_range is thrown. The
3762  * value of the string doesn't change if an error is thrown.
3763  */
3764  basic_string&
3765  insert(size_type __pos1, const basic_string& __str,
3766  size_type __pos2, size_type __n)
3767  { return this->insert(__pos1, __str._M_data()
3768  + __str._M_check(__pos2, "basic_string::insert"),
3769  __str._M_limit(__pos2, __n)); }
3770 
3771  /**
3772  * @brief Insert a C substring.
3773  * @param __pos Iterator referencing location in string to insert at.
3774  * @param __s The C string to insert.
3775  * @param __n The number of characters to insert.
3776  * @return Reference to this string.
3777  * @throw std::length_error If new length exceeds @c max_size().
3778  * @throw std::out_of_range If @a __pos is beyond the end of this
3779  * string.
3780  *
3781  * Inserts the first @a __n characters of @a __s starting at @a
3782  * __pos. If adding characters causes the length to exceed
3783  * max_size(), length_error is thrown. If @a __pos is beyond
3784  * end(), out_of_range is thrown. The value of the string
3785  * doesn't change if an error is thrown.
3786  */
3787  basic_string&
3788  insert(size_type __pos, const _CharT* __s, size_type __n);
3789 
3790  /**
3791  * @brief Insert a C string.
3792  * @param __pos Iterator referencing location in string to insert at.
3793  * @param __s The C string to insert.
3794  * @return Reference to this string.
3795  * @throw std::length_error If new length exceeds @c max_size().
3796  * @throw std::out_of_range If @a pos is beyond the end of this
3797  * string.
3798  *
3799  * Inserts the first @a n characters of @a __s starting at @a __pos. If
3800  * adding characters causes the length to exceed max_size(),
3801  * length_error is thrown. If @a __pos is beyond end(), out_of_range is
3802  * thrown. The value of the string doesn't change if an error is
3803  * thrown.
3804  */
3805  basic_string&
3806  insert(size_type __pos, const _CharT* __s)
3807  {
3808  __glibcxx_requires_string(__s);
3809  return this->insert(__pos, __s, traits_type::length(__s));
3810  }
3811 
3812  /**
3813  * @brief Insert multiple characters.
3814  * @param __pos Index in string to insert at.
3815  * @param __n Number of characters to insert
3816  * @param __c The character to insert.
3817  * @return Reference to this string.
3818  * @throw std::length_error If new length exceeds @c max_size().
3819  * @throw std::out_of_range If @a __pos is beyond the end of this
3820  * string.
3821  *
3822  * Inserts @a __n copies of character @a __c starting at index
3823  * @a __pos. If adding characters causes the length to exceed
3824  * max_size(), length_error is thrown. If @a __pos > length(),
3825  * out_of_range is thrown. The value of the string doesn't
3826  * change if an error is thrown.
3827  */
3828  basic_string&
3829  insert(size_type __pos, size_type __n, _CharT __c)
3830  { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
3831  size_type(0), __n, __c); }
3832 
3833  /**
3834  * @brief Insert one character.
3835  * @param __p Iterator referencing position in string to insert at.
3836  * @param __c The character to insert.
3837  * @return Iterator referencing newly inserted char.
3838  * @throw std::length_error If new length exceeds @c max_size().
3839  *
3840  * Inserts character @a __c at position referenced by @a __p.
3841  * If adding character causes the length to exceed max_size(),
3842  * length_error is thrown. If @a __p is beyond end of string,
3843  * out_of_range is thrown. The value of the string doesn't
3844  * change if an error is thrown.
3845  */
3846  iterator
3847  insert(iterator __p, _CharT __c)
3848  {
3849  _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
3850  const size_type __pos = __p - _M_ibegin();
3851  _M_replace_aux(__pos, size_type(0), size_type(1), __c);
3852  _M_rep()->_M_set_leaked();
3853  return iterator(_M_data() + __pos);
3854  }
3855 
3856  /**
3857  * @brief Remove characters.
3858  * @param __pos Index of first character to remove (default 0).
3859  * @param __n Number of characters to remove (default remainder).
3860  * @return Reference to this string.
3861  * @throw std::out_of_range If @a pos is beyond the end of this
3862  * string.
3863  *
3864  * Removes @a __n characters from this string starting at @a
3865  * __pos. The length of the string is reduced by @a __n. If
3866  * there are < @a __n characters to remove, the remainder of
3867  * the string is truncated. If @a __p is beyond end of string,
3868  * out_of_range is thrown. The value of the string doesn't
3869  * change if an error is thrown.
3870  */
3871  basic_string&
3872  erase(size_type __pos = 0, size_type __n = npos)
3873  {
3874  _M_mutate(_M_check(__pos, "basic_string::erase"),
3875  _M_limit(__pos, __n), size_type(0));
3876  return *this;
3877  }
3878 
3879  /**
3880  * @brief Remove one character.
3881  * @param __position Iterator referencing the character to remove.
3882  * @return iterator referencing same location after removal.
3883  *
3884  * Removes the character at @a __position from this string. The value
3885  * of the string doesn't change if an error is thrown.
3886  */
3887  iterator
3888  erase(iterator __position)
3889  {
3890  _GLIBCXX_DEBUG_PEDASSERT(__position >= _M_ibegin()
3891  && __position < _M_iend());
3892  const size_type __pos = __position - _M_ibegin();
3893  _M_mutate(__pos, size_type(1), size_type(0));
3894  _M_rep()->_M_set_leaked();
3895  return iterator(_M_data() + __pos);
3896  }
3897 
3898  /**
3899  * @brief Remove a range of characters.
3900  * @param __first Iterator referencing the first character to remove.
3901  * @param __last Iterator referencing the end of the range.
3902  * @return Iterator referencing location of first after removal.
3903  *
3904  * Removes the characters in the range [first,last) from this string.
3905  * The value of the string doesn't change if an error is thrown.
3906  */
3907  iterator
3908  erase(iterator __first, iterator __last);
3909 
3910 #if __cplusplus >= 201103L
3911  /**
3912  * @brief Remove the last character.
3913  *
3914  * The string must be non-empty.
3915  */
3916  void
3917  pop_back() // FIXME C++11: should be noexcept.
3918  { erase(size()-1, 1); }
3919 #endif // C++11
3920 
3921  /**
3922  * @brief Replace characters with value from another string.
3923  * @param __pos Index of first character to replace.
3924  * @param __n Number of characters to be replaced.
3925  * @param __str String to insert.
3926  * @return Reference to this string.
3927  * @throw std::out_of_range If @a pos is beyond the end of this
3928  * string.
3929  * @throw std::length_error If new length exceeds @c max_size().
3930  *
3931  * Removes the characters in the range [__pos,__pos+__n) from
3932  * this string. In place, the value of @a __str is inserted.
3933  * If @a __pos is beyond end of string, out_of_range is thrown.
3934  * If the length of the result exceeds max_size(), length_error
3935  * is thrown. The value of the string doesn't change if an
3936  * error is thrown.
3937  */
3938  basic_string&
3939  replace(size_type __pos, size_type __n, const basic_string& __str)
3940  { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
3941 
3942  /**
3943  * @brief Replace characters with value from another string.
3944  * @param __pos1 Index of first character to replace.
3945  * @param __n1 Number of characters to be replaced.
3946  * @param __str String to insert.
3947  * @param __pos2 Index of first character of str to use.
3948  * @param __n2 Number of characters from str to use.
3949  * @return Reference to this string.
3950  * @throw std::out_of_range If @a __pos1 > size() or @a __pos2 >
3951  * __str.size().
3952  * @throw std::length_error If new length exceeds @c max_size().
3953  *
3954  * Removes the characters in the range [__pos1,__pos1 + n) from this
3955  * string. In place, the value of @a __str is inserted. If @a __pos is
3956  * beyond end of string, out_of_range is thrown. If the length of the
3957  * result exceeds max_size(), length_error is thrown. The value of the
3958  * string doesn't change if an error is thrown.
3959  */
3960  basic_string&
3961  replace(size_type __pos1, size_type __n1, const basic_string& __str,
3962  size_type __pos2, size_type __n2)
3963  { return this->replace(__pos1, __n1, __str._M_data()
3964  + __str._M_check(__pos2, "basic_string::replace"),
3965  __str._M_limit(__pos2, __n2)); }
3966 
3967  /**
3968  * @brief Replace characters with value of a C substring.
3969  * @param __pos Index of first character to replace.
3970  * @param __n1 Number of characters to be replaced.
3971  * @param __s C string to insert.
3972  * @param __n2 Number of characters from @a s to use.
3973  * @return Reference to this string.
3974  * @throw std::out_of_range If @a pos1 > size().
3975  * @throw std::length_error If new length exceeds @c max_size().
3976  *
3977  * Removes the characters in the range [__pos,__pos + __n1)
3978  * from this string. In place, the first @a __n2 characters of
3979  * @a __s are inserted, or all of @a __s if @a __n2 is too large. If
3980  * @a __pos is beyond end of string, out_of_range is thrown. If
3981  * the length of result exceeds max_size(), length_error is
3982  * thrown. The value of the string doesn't change if an error
3983  * is thrown.
3984  */
3985  basic_string&
3986  replace(size_type __pos, size_type __n1, const _CharT* __s,
3987  size_type __n2);
3988 
3989  /**
3990  * @brief Replace characters with value of a C string.
3991  * @param __pos Index of first character to replace.
3992  * @param __n1 Number of characters to be replaced.
3993  * @param __s C string to insert.
3994  * @return Reference to this string.
3995  * @throw std::out_of_range If @a pos > size().
3996  * @throw std::length_error If new length exceeds @c max_size().
3997  *
3998  * Removes the characters in the range [__pos,__pos + __n1)
3999  * from this string. In place, the characters of @a __s are
4000  * inserted. If @a __pos is beyond end of string, out_of_range
4001  * is thrown. If the length of result exceeds max_size(),
4002  * length_error is thrown. The value of the string doesn't
4003  * change if an error is thrown.
4004  */
4005  basic_string&
4006  replace(size_type __pos, size_type __n1, const _CharT* __s)
4007  {
4008  __glibcxx_requires_string(__s);
4009  return this->replace(__pos, __n1, __s, traits_type::length(__s));
4010  }
4011 
4012  /**
4013  * @brief Replace characters with multiple characters.
4014  * @param __pos Index of first character to replace.
4015  * @param __n1 Number of characters to be replaced.
4016  * @param __n2 Number of characters to insert.
4017  * @param __c Character to insert.
4018  * @return Reference to this string.
4019  * @throw std::out_of_range If @a __pos > size().
4020  * @throw std::length_error If new length exceeds @c max_size().
4021  *
4022  * Removes the characters in the range [pos,pos + n1) from this
4023  * string. In place, @a __n2 copies of @a __c are inserted.
4024  * If @a __pos is beyond end of string, out_of_range is thrown.
4025  * If the length of result exceeds max_size(), length_error is
4026  * thrown. The value of the string doesn't change if an error
4027  * is thrown.
4028  */
4029  basic_string&
4030  replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
4031  { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
4032  _M_limit(__pos, __n1), __n2, __c); }
4033 
4034  /**
4035  * @brief Replace range of characters with string.
4036  * @param __i1 Iterator referencing start of range to replace.
4037  * @param __i2 Iterator referencing end of range to replace.
4038  * @param __str String value to insert.
4039  * @return Reference to this string.
4040  * @throw std::length_error If new length exceeds @c max_size().
4041  *
4042  * Removes the characters in the range [__i1,__i2). In place,
4043  * the value of @a __str is inserted. If the length of result
4044  * exceeds max_size(), length_error is thrown. The value of
4045  * the string doesn't change if an error is thrown.
4046  */
4047  basic_string&
4048  replace(iterator __i1, iterator __i2, const basic_string& __str)
4049  { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
4050 
4051  /**
4052  * @brief Replace range of characters with C substring.
4053  * @param __i1 Iterator referencing start of range to replace.
4054  * @param __i2 Iterator referencing end of range to replace.
4055  * @param __s C string value to insert.
4056  * @param __n Number of characters from s to insert.
4057  * @return Reference to this string.
4058  * @throw std::length_error If new length exceeds @c max_size().
4059  *
4060  * Removes the characters in the range [__i1,__i2). In place,
4061  * the first @a __n characters of @a __s are inserted. If the
4062  * length of result exceeds max_size(), length_error is thrown.
4063  * The value of the string doesn't change if an error is
4064  * thrown.
4065  */
4066  basic_string&
4067  replace(iterator __i1, iterator __i2, const _CharT* __s, size_type __n)
4068  {
4069  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4070  && __i2 <= _M_iend());
4071  return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n);
4072  }
4073 
4074  /**
4075  * @brief Replace range of characters with C string.
4076  * @param __i1 Iterator referencing start of range to replace.
4077  * @param __i2 Iterator referencing end of range to replace.
4078  * @param __s C string value to insert.
4079  * @return Reference to this string.
4080  * @throw std::length_error If new length exceeds @c max_size().
4081  *
4082  * Removes the characters in the range [__i1,__i2). In place,
4083  * the characters of @a __s are inserted. If the length of
4084  * result exceeds max_size(), length_error is thrown. The
4085  * value of the string doesn't change if an error is thrown.
4086  */
4087  basic_string&
4088  replace(iterator __i1, iterator __i2, const _CharT* __s)
4089  {
4090  __glibcxx_requires_string(__s);
4091  return this->replace(__i1, __i2, __s, traits_type::length(__s));
4092  }
4093 
4094  /**
4095  * @brief Replace range of characters with multiple characters
4096  * @param __i1 Iterator referencing start of range to replace.
4097  * @param __i2 Iterator referencing end of range to replace.
4098  * @param __n Number of characters to insert.
4099  * @param __c Character to insert.
4100  * @return Reference to this string.
4101  * @throw std::length_error If new length exceeds @c max_size().
4102  *
4103  * Removes the characters in the range [__i1,__i2). In place,
4104  * @a __n copies of @a __c are inserted. If the length of
4105  * result exceeds max_size(), length_error is thrown. The
4106  * value of the string doesn't change if an error is thrown.
4107  */
4108  basic_string&
4109  replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
4110  {
4111  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4112  && __i2 <= _M_iend());
4113  return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __c);
4114  }
4115 
4116  /**
4117  * @brief Replace range of characters with range.
4118  * @param __i1 Iterator referencing start of range to replace.
4119  * @param __i2 Iterator referencing end of range to replace.
4120  * @param __k1 Iterator referencing start of range to insert.
4121  * @param __k2 Iterator referencing end of range to insert.
4122  * @return Reference to this string.
4123  * @throw std::length_error If new length exceeds @c max_size().
4124  *
4125  * Removes the characters in the range [__i1,__i2). In place,
4126  * characters in the range [__k1,__k2) are inserted. If the
4127  * length of result exceeds max_size(), length_error is thrown.
4128  * The value of the string doesn't change if an error is
4129  * thrown.
4130  */
4131  template<class _InputIterator>
4132  basic_string&
4133  replace(iterator __i1, iterator __i2,
4134  _InputIterator __k1, _InputIterator __k2)
4135  {
4136  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4137  && __i2 <= _M_iend());
4138  __glibcxx_requires_valid_range(__k1, __k2);
4139  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
4140  return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
4141  }
4142 
4143  // Specializations for the common case of pointer and iterator:
4144  // useful to avoid the overhead of temporary buffering in _M_replace.
4145  basic_string&
4146  replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
4147  {
4148  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4149  && __i2 <= _M_iend());
4150  __glibcxx_requires_valid_range(__k1, __k2);
4151  return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4152  __k1, __k2 - __k1);
4153  }
4154 
4155  basic_string&
4156  replace(iterator __i1, iterator __i2,
4157  const _CharT* __k1, const _CharT* __k2)
4158  {
4159  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4160  && __i2 <= _M_iend());
4161  __glibcxx_requires_valid_range(__k1, __k2);
4162  return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4163  __k1, __k2 - __k1);
4164  }
4165 
4166  basic_string&
4167  replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
4168  {
4169  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4170  && __i2 <= _M_iend());
4171  __glibcxx_requires_valid_range(__k1, __k2);
4172  return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4173  __k1.base(), __k2 - __k1);
4174  }
4175 
4176  basic_string&
4177  replace(iterator __i1, iterator __i2,
4178  const_iterator __k1, const_iterator __k2)
4179  {
4180  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4181  && __i2 <= _M_iend());
4182  __glibcxx_requires_valid_range(__k1, __k2);
4183  return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4184  __k1.base(), __k2 - __k1);
4185  }
4186 
4187 #if __cplusplus >= 201103L
4188  /**
4189  * @brief Replace range of characters with initializer_list.
4190  * @param __i1 Iterator referencing start of range to replace.
4191  * @param __i2 Iterator referencing end of range to replace.
4192  * @param __l The initializer_list of characters to insert.
4193  * @return Reference to this string.
4194  * @throw std::length_error If new length exceeds @c max_size().
4195  *
4196  * Removes the characters in the range [__i1,__i2). In place,
4197  * characters in the range [__k1,__k2) are inserted. If the
4198  * length of result exceeds max_size(), length_error is thrown.
4199  * The value of the string doesn't change if an error is
4200  * thrown.
4201  */
4202  basic_string& replace(iterator __i1, iterator __i2,
4204  { return this->replace(__i1, __i2, __l.begin(), __l.end()); }
4205 #endif // C++11
4206 
4207  private:
4208  template<class _Integer>
4209  basic_string&
4210  _M_replace_dispatch(iterator __i1, iterator __i2, _Integer __n,
4211  _Integer __val, __true_type)
4212  { return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __val); }
4213 
4214  template<class _InputIterator>
4215  basic_string&
4216  _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
4217  _InputIterator __k2, __false_type);
4218 
4219  basic_string&
4220  _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
4221  _CharT __c);
4222 
4223  basic_string&
4224  _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
4225  size_type __n2);
4226 
4227  // _S_construct_aux is used to implement the 21.3.1 para 15 which
4228  // requires special behaviour if _InIter is an integral type
4229  template<class _InIterator>
4230  static _CharT*
4231  _S_construct_aux(_InIterator __beg, _InIterator __end,
4232  const _Alloc& __a, __false_type)
4233  {
4234  typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
4235  return _S_construct(__beg, __end, __a, _Tag());
4236  }
4237 
4238  // _GLIBCXX_RESOLVE_LIB_DEFECTS
4239  // 438. Ambiguity in the "do the right thing" clause
4240  template<class _Integer>
4241  static _CharT*
4242  _S_construct_aux(_Integer __beg, _Integer __end,
4243  const _Alloc& __a, __true_type)
4244  { return _S_construct_aux_2(static_cast<size_type>(__beg),
4245  __end, __a); }
4246 
4247  static _CharT*
4248  _S_construct_aux_2(size_type __req, _CharT __c, const _Alloc& __a)
4249  { return _S_construct(__req, __c, __a); }
4250 
4251  template<class _InIterator>
4252  static _CharT*
4253  _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
4254  {
4255  typedef typename std::__is_integer<_InIterator>::__type _Integral;
4256  return _S_construct_aux(__beg, __end, __a, _Integral());
4257  }
4258 
4259  // For Input Iterators, used in istreambuf_iterators, etc.
4260  template<class _InIterator>
4261  static _CharT*
4262  _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
4264 
4265  // For forward_iterators up to random_access_iterators, used for
4266  // string::iterator, _CharT*, etc.
4267  template<class _FwdIterator>
4268  static _CharT*
4269  _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
4271 
4272  static _CharT*
4273  _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
4274 
4275  public:
4276 
4277  /**
4278  * @brief Copy substring into C string.
4279  * @param __s C string to copy value into.
4280  * @param __n Number of characters to copy.
4281  * @param __pos Index of first character to copy.
4282  * @return Number of characters actually copied
4283  * @throw std::out_of_range If __pos > size().
4284  *
4285  * Copies up to @a __n characters starting at @a __pos into the
4286  * C string @a __s. If @a __pos is %greater than size(),
4287  * out_of_range is thrown.
4288  */
4289  size_type
4290  copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
4291 
4292  /**
4293  * @brief Swap contents with another string.
4294  * @param __s String to swap with.
4295  *
4296  * Exchanges the contents of this string with that of @a __s in constant
4297  * time.
4298  */
4299  // PR 58265, this should be noexcept.
4300  void
4301  swap(basic_string& __s);
4302 
4303  // String operations:
4304  /**
4305  * @brief Return const pointer to null-terminated contents.
4306  *
4307  * This is a handle to internal data. Do not modify or dire things may
4308  * happen.
4309  */
4310  const _CharT*
4311  c_str() const _GLIBCXX_NOEXCEPT
4312  { return _M_data(); }
4313 
4314  /**
4315  * @brief Return const pointer to contents.
4316  *
4317  * This is a handle to internal data. Do not modify or dire things may
4318  * happen.
4319  */
4320  const _CharT*
4321  data() const _GLIBCXX_NOEXCEPT
4322  { return _M_data(); }
4323 
4324  /**
4325  * @brief Return copy of allocator used to construct this string.
4326  */
4327  allocator_type
4328  get_allocator() const _GLIBCXX_NOEXCEPT
4329  { return _M_dataplus; }
4330 
4331  /**
4332  * @brief Find position of a C substring.
4333  * @param __s C string to locate.
4334  * @param __pos Index of character to search from.
4335  * @param __n Number of characters from @a s to search for.
4336  * @return Index of start of first occurrence.
4337  *
4338  * Starting from @a __pos, searches forward for the first @a
4339  * __n characters in @a __s within this string. If found,
4340  * returns the index where it begins. If not found, returns
4341  * npos.
4342  */
4343  size_type
4344  find(const _CharT* __s, size_type __pos, size_type __n) const;
4345 
4346  /**
4347  * @brief Find position of a string.
4348  * @param __str String to locate.
4349  * @param __pos Index of character to search from (default 0).
4350  * @return Index of start of first occurrence.
4351  *
4352  * Starting from @a __pos, searches forward for value of @a __str within
4353  * this string. If found, returns the index where it begins. If not
4354  * found, returns npos.
4355  */
4356  size_type
4357  find(const basic_string& __str, size_type __pos = 0) const
4358  _GLIBCXX_NOEXCEPT
4359  { return this->find(__str.data(), __pos, __str.size()); }
4360 
4361  /**
4362  * @brief Find position of a C string.
4363  * @param __s C string to locate.
4364  * @param __pos Index of character to search from (default 0).
4365  * @return Index of start of first occurrence.
4366  *
4367  * Starting from @a __pos, searches forward for the value of @a
4368  * __s within this string. If found, returns the index where
4369  * it begins. If not found, returns npos.
4370  */
4371  size_type
4372  find(const _CharT* __s, size_type __pos = 0) const
4373  {
4374  __glibcxx_requires_string(__s);
4375  return this->find(__s, __pos, traits_type::length(__s));
4376  }
4377 
4378  /**
4379  * @brief Find position of a character.
4380  * @param __c Character to locate.
4381  * @param __pos Index of character to search from (default 0).
4382  * @return Index of first occurrence.
4383  *
4384  * Starting from @a __pos, searches forward for @a __c within
4385  * this string. If found, returns the index where it was
4386  * found. If not found, returns npos.
4387  */
4388  size_type
4389  find(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT;
4390 
4391  /**
4392  * @brief Find last position of a string.
4393  * @param __str String to locate.
4394  * @param __pos Index of character to search back from (default end).
4395  * @return Index of start of last occurrence.
4396  *
4397  * Starting from @a __pos, searches backward for value of @a
4398  * __str within this string. If found, returns the index where
4399  * it begins. If not found, returns npos.
4400  */
4401  size_type
4402  rfind(const basic_string& __str, size_type __pos = npos) const
4403  _GLIBCXX_NOEXCEPT
4404  { return this->rfind(__str.data(), __pos, __str.size()); }
4405 
4406  /**
4407  * @brief Find last position of a C substring.
4408  * @param __s C string to locate.
4409  * @param __pos Index of character to search back from.
4410  * @param __n Number of characters from s to search for.
4411  * @return Index of start of last occurrence.
4412  *
4413  * Starting from @a __pos, searches backward for the first @a
4414  * __n characters in @a __s within this string. If found,
4415  * returns the index where it begins. If not found, returns
4416  * npos.
4417  */
4418  size_type
4419  rfind(const _CharT* __s, size_type __pos, size_type __n) const;
4420 
4421  /**
4422  * @brief Find last position of a C string.
4423  * @param __s C string to locate.
4424  * @param __pos Index of character to start search at (default end).
4425  * @return Index of start of last occurrence.
4426  *
4427  * Starting from @a __pos, searches backward for the value of
4428  * @a __s within this string. If found, returns the index
4429  * where it begins. If not found, returns npos.
4430  */
4431  size_type
4432  rfind(const _CharT* __s, size_type __pos = npos) const
4433  {
4434  __glibcxx_requires_string(__s);
4435  return this->rfind(__s, __pos, traits_type::length(__s));
4436  }
4437 
4438  /**
4439  * @brief Find last position of a character.
4440  * @param __c Character to locate.
4441  * @param __pos Index of character to search back from (default end).
4442  * @return Index of last occurrence.
4443  *
4444  * Starting from @a __pos, searches backward for @a __c within
4445  * this string. If found, returns the index where it was
4446  * found. If not found, returns npos.
4447  */
4448  size_type
4449  rfind(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT;
4450 
4451  /**
4452  * @brief Find position of a character of string.
4453  * @param __str String containing characters to locate.
4454  * @param __pos Index of character to search from (default 0).
4455  * @return Index of first occurrence.
4456  *
4457  * Starting from @a __pos, searches forward for one of the
4458  * characters of @a __str within this string. If found,
4459  * returns the index where it was found. If not found, returns
4460  * npos.
4461  */
4462  size_type
4463  find_first_of(const basic_string& __str, size_type __pos = 0) const
4464  _GLIBCXX_NOEXCEPT
4465  { return this->find_first_of(__str.data(), __pos, __str.size()); }
4466 
4467  /**
4468  * @brief Find position of a character of C substring.
4469  * @param __s String containing characters to locate.
4470  * @param __pos Index of character to search from.
4471  * @param __n Number of characters from s to search for.
4472  * @return Index of first occurrence.
4473  *
4474  * Starting from @a __pos, searches forward for one of the
4475  * first @a __n characters of @a __s within this string. If
4476  * found, returns the index where it was found. If not found,
4477  * returns npos.
4478  */
4479  size_type
4480  find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
4481 
4482  /**
4483  * @brief Find position of a character of C string.
4484  * @param __s String containing characters to locate.
4485  * @param __pos Index of character to search from (default 0).
4486  * @return Index of first occurrence.
4487  *
4488  * Starting from @a __pos, searches forward for one of the
4489  * characters of @a __s within this string. If found, returns
4490  * the index where it was found. If not found, returns npos.
4491  */
4492  size_type
4493  find_first_of(const _CharT* __s, size_type __pos = 0) const
4494  {
4495  __glibcxx_requires_string(__s);
4496  return this->find_first_of(__s, __pos, traits_type::length(__s));
4497  }
4498 
4499  /**
4500  * @brief Find position of a character.
4501  * @param __c Character to locate.
4502  * @param __pos Index of character to search from (default 0).
4503  * @return Index of first occurrence.
4504  *
4505  * Starting from @a __pos, searches forward for the character
4506  * @a __c within this string. If found, returns the index
4507  * where it was found. If not found, returns npos.
4508  *
4509  * Note: equivalent to find(__c, __pos).
4510  */
4511  size_type
4512  find_first_of(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT
4513  { return this->find(__c, __pos); }
4514 
4515  /**
4516  * @brief Find last position of a character of string.
4517  * @param __str String containing characters to locate.
4518  * @param __pos Index of character to search back from (default end).
4519  * @return Index of last occurrence.
4520  *
4521  * Starting from @a __pos, searches backward for one of the
4522  * characters of @a __str within this string. If found,
4523  * returns the index where it was found. If not found, returns
4524  * npos.
4525  */
4526  size_type
4527  find_last_of(const basic_string& __str, size_type __pos = npos) const
4528  _GLIBCXX_NOEXCEPT
4529  { return this->find_last_of(__str.data(), __pos, __str.size()); }
4530 
4531  /**
4532  * @brief Find last position of a character of C substring.
4533  * @param __s C string containing characters to locate.
4534  * @param __pos Index of character to search back from.
4535  * @param __n Number of characters from s to search for.
4536  * @return Index of last occurrence.
4537  *
4538  * Starting from @a __pos, searches backward for one of the
4539  * first @a __n characters of @a __s within this string. If
4540  * found, returns the index where it was found. If not found,
4541  * returns npos.
4542  */
4543  size_type
4544  find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
4545 
4546  /**
4547  * @brief Find last position of a character of C string.
4548  * @param __s C string containing characters to locate.
4549  * @param __pos Index of character to search back from (default end).
4550  * @return Index of last occurrence.
4551  *
4552  * Starting from @a __pos, searches backward for one of the
4553  * characters of @a __s within this string. If found, returns
4554  * the index where it was found. If not found, returns npos.
4555  */
4556  size_type
4557  find_last_of(const _CharT* __s, size_type __pos = npos) const
4558  {
4559  __glibcxx_requires_string(__s);
4560  return this->find_last_of(__s, __pos, traits_type::length(__s));
4561  }
4562 
4563  /**
4564  * @brief Find last position of a character.
4565  * @param __c Character to locate.
4566  * @param __pos Index of character to search back from (default end).
4567  * @return Index of last occurrence.
4568  *
4569  * Starting from @a __pos, searches backward for @a __c within
4570  * this string. If found, returns the index where it was
4571  * found. If not found, returns npos.
4572  *
4573  * Note: equivalent to rfind(__c, __pos).
4574  */
4575  size_type
4576  find_last_of(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT
4577  { return this->rfind(__c, __pos); }
4578 
4579  /**
4580  * @brief Find position of a character not in string.
4581  * @param __str String containing characters to avoid.
4582  * @param __pos Index of character to search from (default 0).
4583  * @return Index of first occurrence.
4584  *
4585  * Starting from @a __pos, searches forward for a character not contained
4586  * in @a __str within this string. If found, returns the index where it
4587  * was found. If not found, returns npos.
4588  */
4589  size_type
4590  find_first_not_of(const basic_string& __str, size_type __pos = 0) const
4591  _GLIBCXX_NOEXCEPT
4592  { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
4593 
4594  /**
4595  * @brief Find position of a character not in C substring.
4596  * @param __s C string containing characters to avoid.
4597  * @param __pos Index of character to search from.
4598  * @param __n Number of characters from __s to consider.
4599  * @return Index of first occurrence.
4600  *
4601  * Starting from @a __pos, searches forward for a character not
4602  * contained in the first @a __n characters of @a __s within
4603  * this string. If found, returns the index where it was
4604  * found. If not found, returns npos.
4605  */
4606  size_type
4607  find_first_not_of(const _CharT* __s, size_type __pos,
4608  size_type __n) const;
4609 
4610  /**
4611  * @brief Find position of a character not in C string.
4612  * @param __s C string containing characters to avoid.
4613  * @param __pos Index of character to search from (default 0).
4614  * @return Index of first occurrence.
4615  *
4616  * Starting from @a __pos, searches forward for a character not
4617  * contained in @a __s within this string. If found, returns
4618  * the index where it was found. If not found, returns npos.
4619  */
4620  size_type
4621  find_first_not_of(const _CharT* __s, size_type __pos = 0) const
4622  {
4623  __glibcxx_requires_string(__s);
4624  return this->find_first_not_of(__s, __pos, traits_type::length(__s));
4625  }
4626 
4627  /**
4628  * @brief Find position of a different character.
4629  * @param __c Character to avoid.
4630  * @param __pos Index of character to search from (default 0).
4631  * @return Index of first occurrence.
4632  *
4633  * Starting from @a __pos, searches forward for a character
4634  * other than @a __c within this string. If found, returns the
4635  * index where it was found. If not found, returns npos.
4636  */
4637  size_type
4638  find_first_not_of(_CharT __c, size_type __pos = 0) const
4639  _GLIBCXX_NOEXCEPT;
4640 
4641  /**
4642  * @brief Find last position of a character not in string.
4643  * @param __str String containing characters to avoid.
4644  * @param __pos Index of character to search back from (default end).
4645  * @return Index of last occurrence.
4646  *
4647  * Starting from @a __pos, searches backward for a character
4648  * not contained in @a __str within this string. If found,
4649  * returns the index where it was found. If not found, returns
4650  * npos.
4651  */
4652  size_type
4653  find_last_not_of(const basic_string& __str, size_type __pos = npos) const
4654  _GLIBCXX_NOEXCEPT
4655  { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
4656 
4657  /**
4658  * @brief Find last position of a character not in C substring.
4659  * @param __s C string containing characters to avoid.
4660  * @param __pos Index of character to search back from.
4661  * @param __n Number of characters from s to consider.
4662  * @return Index of last occurrence.
4663  *
4664  * Starting from @a __pos, searches backward for a character not
4665  * contained in the first @a __n characters of @a __s within this string.
4666  * If found, returns the index where it was found. If not found,
4667  * returns npos.
4668  */
4669  size_type
4670  find_last_not_of(const _CharT* __s, size_type __pos,
4671  size_type __n) const;
4672  /**
4673  * @brief Find last position of a character not in C string.
4674  * @param __s C string containing characters to avoid.
4675  * @param __pos Index of character to search back from (default end).
4676  * @return Index of last occurrence.
4677  *
4678  * Starting from @a __pos, searches backward for a character
4679  * not contained in @a __s within this string. If found,
4680  * returns the index where it was found. If not found, returns
4681  * npos.
4682  */
4683  size_type
4684  find_last_not_of(const _CharT* __s, size_type __pos = npos) const
4685  {
4686  __glibcxx_requires_string(__s);
4687  return this->find_last_not_of(__s, __pos, traits_type::length(__s));
4688  }
4689 
4690  /**
4691  * @brief Find last position of a different character.
4692  * @param __c Character to avoid.
4693  * @param __pos Index of character to search back from (default end).
4694  * @return Index of last occurrence.
4695  *
4696  * Starting from @a __pos, searches backward for a character other than
4697  * @a __c within this string. If found, returns the index where it was
4698  * found. If not found, returns npos.
4699  */
4700  size_type
4701  find_last_not_of(_CharT __c, size_type __pos = npos) const
4702  _GLIBCXX_NOEXCEPT;
4703 
4704  /**
4705  * @brief Get a substring.
4706  * @param __pos Index of first character (default 0).
4707  * @param __n Number of characters in substring (default remainder).
4708  * @return The new string.
4709  * @throw std::out_of_range If __pos > size().
4710  *
4711  * Construct and return a new string using the @a __n
4712  * characters starting at @a __pos. If the string is too
4713  * short, use the remainder of the characters. If @a __pos is
4714  * beyond the end of the string, out_of_range is thrown.
4715  */
4716  basic_string
4717  substr(size_type __pos = 0, size_type __n = npos) const
4718  { return basic_string(*this,
4719  _M_check(__pos, "basic_string::substr"), __n); }
4720 
4721  /**
4722  * @brief Compare to a string.
4723  * @param __str String to compare against.
4724  * @return Integer < 0, 0, or > 0.
4725  *
4726  * Returns an integer < 0 if this string is ordered before @a
4727  * __str, 0 if their values are equivalent, or > 0 if this
4728  * string is ordered after @a __str. Determines the effective
4729  * length rlen of the strings to compare as the smallest of
4730  * size() and str.size(). The function then compares the two
4731  * strings by calling traits::compare(data(), str.data(),rlen).
4732  * If the result of the comparison is nonzero returns it,
4733  * otherwise the shorter one is ordered first.
4734  */
4735  int
4736  compare(const basic_string& __str) const
4737  {
4738  const size_type __size = this->size();
4739  const size_type __osize = __str.size();
4740  const size_type __len = std::min(__size, __osize);
4741 
4742  int __r = traits_type::compare(_M_data(), __str.data(), __len);
4743  if (!__r)
4744  __r = _S_compare(__size, __osize);
4745  return __r;
4746  }
4747 
4748  /**
4749  * @brief Compare substring to a string.
4750  * @param __pos Index of first character of substring.
4751  * @param __n Number of characters in substring.
4752  * @param __str String to compare against.
4753  * @return Integer < 0, 0, or > 0.
4754  *
4755  * Form the substring of this string from the @a __n characters
4756  * starting at @a __pos. Returns an integer < 0 if the
4757  * substring is ordered before @a __str, 0 if their values are
4758  * equivalent, or > 0 if the substring is ordered after @a
4759  * __str. Determines the effective length rlen of the strings
4760  * to compare as the smallest of the length of the substring
4761  * and @a __str.size(). The function then compares the two
4762  * strings by calling
4763  * traits::compare(substring.data(),str.data(),rlen). If the
4764  * result of the comparison is nonzero returns it, otherwise
4765  * the shorter one is ordered first.
4766  */
4767  int
4768  compare(size_type __pos, size_type __n, const basic_string& __str) const;
4769 
4770  /**
4771  * @brief Compare substring to a substring.
4772  * @param __pos1 Index of first character of substring.
4773  * @param __n1 Number of characters in substring.
4774  * @param __str String to compare against.
4775  * @param __pos2 Index of first character of substring of str.
4776  * @param __n2 Number of characters in substring of str.
4777  * @return Integer < 0, 0, or > 0.
4778  *
4779  * Form the substring of this string from the @a __n1
4780  * characters starting at @a __pos1. Form the substring of @a
4781  * __str from the @a __n2 characters starting at @a __pos2.
4782  * Returns an integer < 0 if this substring is ordered before
4783  * the substring of @a __str, 0 if their values are equivalent,
4784  * or > 0 if this substring is ordered after the substring of
4785  * @a __str. Determines the effective length rlen of the
4786  * strings to compare as the smallest of the lengths of the
4787  * substrings. The function then compares the two strings by
4788  * calling
4789  * traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
4790  * If the result of the comparison is nonzero returns it,
4791  * otherwise the shorter one is ordered first.
4792  */
4793  int
4794  compare(size_type __pos1, size_type __n1, const basic_string& __str,
4795  size_type __pos2, size_type __n2) const;
4796 
4797  /**
4798  * @brief Compare to a C string.
4799  * @param __s C string to compare against.
4800  * @return Integer < 0, 0, or > 0.
4801  *
4802  * Returns an integer < 0 if this string is ordered before @a __s, 0 if
4803  * their values are equivalent, or > 0 if this string is ordered after
4804  * @a __s. Determines the effective length rlen of the strings to
4805  * compare as the smallest of size() and the length of a string
4806  * constructed from @a __s. The function then compares the two strings
4807  * by calling traits::compare(data(),s,rlen). If the result of the
4808  * comparison is nonzero returns it, otherwise the shorter one is
4809  * ordered first.
4810  */
4811  int
4812  compare(const _CharT* __s) const;
4813 
4814  // _GLIBCXX_RESOLVE_LIB_DEFECTS
4815  // 5 String::compare specification questionable
4816  /**
4817  * @brief Compare substring to a C string.
4818  * @param __pos Index of first character of substring.
4819  * @param __n1 Number of characters in substring.
4820  * @param __s C string to compare against.
4821  * @return Integer < 0, 0, or > 0.
4822  *
4823  * Form the substring of this string from the @a __n1
4824  * characters starting at @a pos. Returns an integer < 0 if
4825  * the substring is ordered before @a __s, 0 if their values
4826  * are equivalent, or > 0 if the substring is ordered after @a
4827  * __s. Determines the effective length rlen of the strings to
4828  * compare as the smallest of the length of the substring and
4829  * the length of a string constructed from @a __s. The
4830  * function then compares the two string by calling
4831  * traits::compare(substring.data(),__s,rlen). If the result of
4832  * the comparison is nonzero returns it, otherwise the shorter
4833  * one is ordered first.
4834  */
4835  int
4836  compare(size_type __pos, size_type __n1, const _CharT* __s) const;
4837 
4838  /**
4839  * @brief Compare substring against a character %array.
4840  * @param __pos Index of first character of substring.
4841  * @param __n1 Number of characters in substring.
4842  * @param __s character %array to compare against.
4843  * @param __n2 Number of characters of s.
4844  * @return Integer < 0, 0, or > 0.
4845  *
4846  * Form the substring of this string from the @a __n1
4847  * characters starting at @a __pos. Form a string from the
4848  * first @a __n2 characters of @a __s. Returns an integer < 0
4849  * if this substring is ordered before the string from @a __s,
4850  * 0 if their values are equivalent, or > 0 if this substring
4851  * is ordered after the string from @a __s. Determines the
4852  * effective length rlen of the strings to compare as the
4853  * smallest of the length of the substring and @a __n2. The
4854  * function then compares the two strings by calling
4855  * traits::compare(substring.data(),s,rlen). If the result of
4856  * the comparison is nonzero returns it, otherwise the shorter
4857  * one is ordered first.
4858  *
4859  * NB: s must have at least n2 characters, &apos;\\0&apos; has
4860  * no special meaning.
4861  */
4862  int
4863  compare(size_type __pos, size_type __n1, const _CharT* __s,
4864  size_type __n2) const;
4865  };
4866 #endif // !_GLIBCXX_USE_CXX11_ABI
4867 
4868  // operator+
4869  /**
4870  * @brief Concatenate two strings.
4871  * @param __lhs First string.
4872  * @param __rhs Last string.
4873  * @return New string with value of @a __lhs followed by @a __rhs.
4874  */
4875  template<typename _CharT, typename _Traits, typename _Alloc>
4879  {
4881  __str.append(__rhs);
4882  return __str;
4883  }
4884 
4885  /**
4886  * @brief Concatenate C string and string.
4887  * @param __lhs First string.
4888  * @param __rhs Last string.
4889  * @return New string with value of @a __lhs followed by @a __rhs.
4890  */
4891  template<typename _CharT, typename _Traits, typename _Alloc>
4893  operator+(const _CharT* __lhs,
4895 
4896  /**
4897  * @brief Concatenate character and string.
4898  * @param __lhs First string.
4899  * @param __rhs Last string.
4900  * @return New string with @a __lhs followed by @a __rhs.
4901  */
4902  template<typename _CharT, typename _Traits, typename _Alloc>
4904  operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
4905 
4906  /**
4907  * @brief Concatenate string and C string.
4908  * @param __lhs First string.
4909  * @param __rhs Last string.
4910  * @return New string with @a __lhs followed by @a __rhs.
4911  */
4912  template<typename _CharT, typename _Traits, typename _Alloc>
4915  const _CharT* __rhs)
4916  {
4918  __str.append(__rhs);
4919  return __str;
4920  }
4921 
4922  /**
4923  * @brief Concatenate string and character.
4924  * @param __lhs First string.
4925  * @param __rhs Last string.
4926  * @return New string with @a __lhs followed by @a __rhs.
4927  */
4928  template<typename _CharT, typename _Traits, typename _Alloc>
4931  {
4932  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
4933  typedef typename __string_type::size_type __size_type;
4934  __string_type __str(__lhs);
4935  __str.append(__size_type(1), __rhs);
4936  return __str;
4937  }
4938 
4939 #if __cplusplus >= 201103L
4940  template<typename _CharT, typename _Traits, typename _Alloc>
4944  { return std::move(__lhs.append(__rhs)); }
4945 
4946  template<typename _CharT, typename _Traits, typename _Alloc>
4950  { return std::move(__rhs.insert(0, __lhs)); }
4951 
4952  template<typename _CharT, typename _Traits, typename _Alloc>
4956  {
4957  const auto __size = __lhs.size() + __rhs.size();
4958  const bool __cond = (__size > __lhs.capacity()
4959  && __size <= __rhs.capacity());
4960  return __cond ? std::move(__rhs.insert(0, __lhs))
4961  : std::move(__lhs.append(__rhs));
4962  }
4963 
4964  template<typename _CharT, typename _Traits, typename _Alloc>
4966  operator+(const _CharT* __lhs,
4968  { return std::move(__rhs.insert(0, __lhs)); }
4969 
4970  template<typename _CharT, typename _Traits, typename _Alloc>
4972  operator+(_CharT __lhs,
4974  { return std::move(__rhs.insert(0, 1, __lhs)); }
4975 
4976  template<typename _CharT, typename _Traits, typename _Alloc>
4979  const _CharT* __rhs)
4980  { return std::move(__lhs.append(__rhs)); }
4981 
4982  template<typename _CharT, typename _Traits, typename _Alloc>
4985  _CharT __rhs)
4986  { return std::move(__lhs.append(1, __rhs)); }
4987 #endif
4988 
4989  // operator ==
4990  /**
4991  * @brief Test equivalence of two strings.
4992  * @param __lhs First string.
4993  * @param __rhs Second string.
4994  * @return True if @a __lhs.compare(@a __rhs) == 0. False otherwise.
4995  */
4996  template<typename _CharT, typename _Traits, typename _Alloc>
4997  inline bool
4998  operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5000  _GLIBCXX_NOEXCEPT
5001  { return __lhs.compare(__rhs) == 0; }
5002 
5003  template<typename _CharT>
5004  inline
5005  typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, bool>::__type
5006  operator==(const basic_string<_CharT>& __lhs,
5007  const basic_string<_CharT>& __rhs) _GLIBCXX_NOEXCEPT
5008  { return (__lhs.size() == __rhs.size()
5009  && !std::char_traits<_CharT>::compare(__lhs.data(), __rhs.data(),
5010  __lhs.size())); }
5011 
5012  /**
5013  * @brief Test equivalence of C string and string.
5014  * @param __lhs C string.
5015  * @param __rhs String.
5016  * @return True if @a __rhs.compare(@a __lhs) == 0. False otherwise.
5017  */
5018  template<typename _CharT, typename _Traits, typename _Alloc>
5019  inline bool
5020  operator==(const _CharT* __lhs,
5022  { return __rhs.compare(__lhs) == 0; }
5023 
5024  /**
5025  * @brief Test equivalence of string and C string.
5026  * @param __lhs String.
5027  * @param __rhs C string.
5028  * @return True if @a __lhs.compare(@a __rhs) == 0. False otherwise.
5029  */
5030  template<typename _CharT, typename _Traits, typename _Alloc>
5031  inline bool
5032  operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5033  const _CharT* __rhs)
5034  { return __lhs.compare(__rhs) == 0; }
5035 
5036  // operator !=
5037  /**
5038  * @brief Test difference of two strings.
5039  * @param __lhs First string.
5040  * @param __rhs Second string.
5041  * @return True if @a __lhs.compare(@a __rhs) != 0. False otherwise.
5042  */
5043  template<typename _CharT, typename _Traits, typename _Alloc>
5044  inline bool
5045  operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5047  _GLIBCXX_NOEXCEPT
5048  { return !(__lhs == __rhs); }
5049 
5050  /**
5051  * @brief Test difference of C string and string.
5052  * @param __lhs C string.
5053  * @param __rhs String.
5054  * @return True if @a __rhs.compare(@a __lhs) != 0. False otherwise.
5055  */
5056  template<typename _CharT, typename _Traits, typename _Alloc>
5057  inline bool
5058  operator!=(const _CharT* __lhs,
5060  { return !(__lhs == __rhs); }
5061 
5062  /**
5063  * @brief Test difference of string and C string.
5064  * @param __lhs String.
5065  * @param __rhs C string.
5066  * @return True if @a __lhs.compare(@a __rhs) != 0. False otherwise.
5067  */
5068  template<typename _CharT, typename _Traits, typename _Alloc>
5069  inline bool
5070  operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5071  const _CharT* __rhs)
5072  { return !(__lhs == __rhs); }
5073 
5074  // operator <
5075  /**
5076  * @brief Test if string precedes string.
5077  * @param __lhs First string.
5078  * @param __rhs Second string.
5079  * @return True if @a __lhs precedes @a __rhs. False otherwise.
5080  */
5081  template<typename _CharT, typename _Traits, typename _Alloc>
5082  inline bool
5083  operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5085  _GLIBCXX_NOEXCEPT
5086  { return __lhs.compare(__rhs) < 0; }
5087 
5088  /**
5089  * @brief Test if string precedes C string.
5090  * @param __lhs String.
5091  * @param __rhs C string.
5092  * @return True if @a __lhs precedes @a __rhs. False otherwise.
5093  */
5094  template<typename _CharT, typename _Traits, typename _Alloc>
5095  inline bool
5096  operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5097  const _CharT* __rhs)
5098  { return __lhs.compare(__rhs) < 0; }
5099 
5100  /**
5101  * @brief Test if C string precedes string.
5102  * @param __lhs C string.
5103  * @param __rhs String.
5104  * @return True if @a __lhs precedes @a __rhs. False otherwise.
5105  */
5106  template<typename _CharT, typename _Traits, typename _Alloc>
5107  inline bool
5108  operator<(const _CharT* __lhs,
5110  { return __rhs.compare(__lhs) > 0; }
5111 
5112  // operator >
5113  /**
5114  * @brief Test if string follows string.
5115  * @param __lhs First string.
5116  * @param __rhs Second string.
5117  * @return True if @a __lhs follows @a __rhs. False otherwise.
5118  */
5119  template<typename _CharT, typename _Traits, typename _Alloc>
5120  inline bool
5123  _GLIBCXX_NOEXCEPT
5124  { return __lhs.compare(__rhs) > 0; }
5125 
5126  /**
5127  * @brief Test if string follows C string.
5128  * @param __lhs String.
5129  * @param __rhs C string.
5130  * @return True if @a __lhs follows @a __rhs. False otherwise.
5131  */
5132  template<typename _CharT, typename _Traits, typename _Alloc>
5133  inline bool
5135  const _CharT* __rhs)
5136  { return __lhs.compare(__rhs) > 0; }
5137 
5138  /**
5139  * @brief Test if C string follows string.
5140  * @param __lhs C string.
5141  * @param __rhs String.
5142  * @return True if @a __lhs follows @a __rhs. False otherwise.
5143  */
5144  template<typename _CharT, typename _Traits, typename _Alloc>
5145  inline bool
5146  operator>(const _CharT* __lhs,
5148  { return __rhs.compare(__lhs) < 0; }
5149 
5150  // operator <=
5151  /**
5152  * @brief Test if string doesn't follow string.
5153  * @param __lhs First string.
5154  * @param __rhs Second string.
5155  * @return True if @a __lhs doesn't follow @a __rhs. False otherwise.
5156  */
5157  template<typename _CharT, typename _Traits, typename _Alloc>
5158  inline bool
5159  operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5161  _GLIBCXX_NOEXCEPT
5162  { return __lhs.compare(__rhs) <= 0; }
5163 
5164  /**
5165  * @brief Test if string doesn't follow C string.
5166  * @param __lhs String.
5167  * @param __rhs C string.
5168  * @return True if @a __lhs doesn't follow @a __rhs. False otherwise.
5169  */
5170  template<typename _CharT, typename _Traits, typename _Alloc>
5171  inline bool
5172  operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5173  const _CharT* __rhs)
5174  { return __lhs.compare(__rhs) <= 0; }
5175 
5176  /**
5177  * @brief Test if C string doesn't follow string.
5178  * @param __lhs C string.
5179  * @param __rhs String.
5180  * @return True if @a __lhs doesn't follow @a __rhs. False otherwise.
5181  */
5182  template<typename _CharT, typename _Traits, typename _Alloc>
5183  inline bool
5184  operator<=(const _CharT* __lhs,
5186  { return __rhs.compare(__lhs) >= 0; }
5187 
5188  // operator >=
5189  /**
5190  * @brief Test if string doesn't precede string.
5191  * @param __lhs First string.
5192  * @param __rhs Second string.
5193  * @return True if @a __lhs doesn't precede @a __rhs. False otherwise.
5194  */
5195  template<typename _CharT, typename _Traits, typename _Alloc>
5196  inline bool
5197  operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5199  _GLIBCXX_NOEXCEPT
5200  { return __lhs.compare(__rhs) >= 0; }
5201 
5202  /**
5203  * @brief Test if string doesn't precede C string.
5204  * @param __lhs String.
5205  * @param __rhs C string.
5206  * @return True if @a __lhs doesn't precede @a __rhs. False otherwise.
5207  */
5208  template<typename _CharT, typename _Traits, typename _Alloc>
5209  inline bool
5210  operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5211  const _CharT* __rhs)
5212  { return __lhs.compare(__rhs) >= 0; }
5213 
5214  /**
5215  * @brief Test if C string doesn't precede string.
5216  * @param __lhs C string.
5217  * @param __rhs String.
5218  * @return True if @a __lhs doesn't precede @a __rhs. False otherwise.
5219  */
5220  template<typename _CharT, typename _Traits, typename _Alloc>
5221  inline bool
5222  operator>=(const _CharT* __lhs,
5224  { return __rhs.compare(__lhs) <= 0; }
5225 
5226  /**
5227  * @brief Swap contents of two strings.
5228  * @param __lhs First string.
5229  * @param __rhs Second string.
5230  *
5231  * Exchanges the contents of @a __lhs and @a __rhs in constant time.
5232  */
5233  template<typename _CharT, typename _Traits, typename _Alloc>
5234  inline void
5237 #if __cplusplus >= 201103L
5238  noexcept(noexcept(__lhs.swap(__rhs)))
5239 #endif
5240  { __lhs.swap(__rhs); }
5241 
5242 
5243  /**
5244  * @brief Read stream into a string.
5245  * @param __is Input stream.
5246  * @param __str Buffer to store into.
5247  * @return Reference to the input stream.
5248  *
5249  * Stores characters from @a __is into @a __str until whitespace is
5250  * found, the end of the stream is encountered, or str.max_size()
5251  * is reached. If is.width() is non-zero, that is the limit on the
5252  * number of characters stored into @a __str. Any previous
5253  * contents of @a __str are erased.
5254  */
5255  template<typename _CharT, typename _Traits, typename _Alloc>
5259 
5260  template<>
5263 
5264  /**
5265  * @brief Write string to a stream.
5266  * @param __os Output stream.
5267  * @param __str String to write out.
5268  * @return Reference to the output stream.
5269  *
5270  * Output characters of @a __str into os following the same rules as for
5271  * writing a C string.
5272  */
5273  template<typename _CharT, typename _Traits, typename _Alloc>
5275  operator<<(basic_ostream<_CharT, _Traits>& __os,
5277  {
5278  // _GLIBCXX_RESOLVE_LIB_DEFECTS
5279  // 586. string inserter not a formatted function
5280  return __ostream_insert(__os, __str.data(), __str.size());
5281  }
5282 
5283  /**
5284  * @brief Read a line from stream into a string.
5285  * @param __is Input stream.
5286  * @param __str Buffer to store into.
5287  * @param __delim Character marking end of line.
5288  * @return Reference to the input stream.
5289  *
5290  * Stores characters from @a __is into @a __str until @a __delim is
5291  * found, the end of the stream is encountered, or str.max_size()
5292  * is reached. Any previous contents of @a __str are erased. If
5293  * @a __delim is encountered, it is extracted but not stored into
5294  * @a __str.
5295  */
5296  template<typename _CharT, typename _Traits, typename _Alloc>
5299  basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
5300 
5301  /**
5302  * @brief Read a line from stream into a string.
5303  * @param __is Input stream.
5304  * @param __str Buffer to store into.
5305  * @return Reference to the input stream.
5306  *
5307  * Stores characters from is into @a __str until &apos;\n&apos; is
5308  * found, the end of the stream is encountered, or str.max_size()
5309  * is reached. Any previous contents of @a __str are erased. If
5310  * end of line is encountered, it is extracted but not stored into
5311  * @a __str.
5312  */
5313  template<typename _CharT, typename _Traits, typename _Alloc>
5317  { return std::getline(__is, __str, __is.widen('\n')); }
5318 
5319 #if __cplusplus >= 201103L
5320  /// Read a line from an rvalue stream into a string.
5321  template<typename _CharT, typename _Traits, typename _Alloc>
5324  basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
5325  { return std::getline(__is, __str, __delim); }
5326 
5327  /// Read a line from an rvalue stream into a string.
5328  template<typename _CharT, typename _Traits, typename _Alloc>
5332  { return std::getline(__is, __str); }
5333 #endif
5334 
5335  template<>
5338  char __delim);
5339 
5340 #ifdef _GLIBCXX_USE_WCHAR_T
5341  template<>
5344  wchar_t __delim);
5345 #endif
5346 
5347 _GLIBCXX_END_NAMESPACE_VERSION
5348 } // namespace
5349 
5350 #if __cplusplus >= 201103L && defined(_GLIBCXX_USE_C99)
5351 
5352 #include <ext/string_conversions.h>
5353 
5354 namespace std _GLIBCXX_VISIBILITY(default)
5355 {
5356 _GLIBCXX_BEGIN_NAMESPACE_VERSION
5357 _GLIBCXX_BEGIN_NAMESPACE_CXX11
5358 
5359  // 21.4 Numeric Conversions [string.conversions].
5360  inline int
5361  stoi(const string& __str, size_t* __idx = 0, int __base = 10)
5362  { return __gnu_cxx::__stoa<long, int>(&std::strtol, "stoi", __str.c_str(),
5363  __idx, __base); }
5364 
5365  inline long
5366  stol(const string& __str, size_t* __idx = 0, int __base = 10)
5367  { return __gnu_cxx::__stoa(&std::strtol, "stol", __str.c_str(),
5368  __idx, __base); }
5369 
5370  inline unsigned long
5371  stoul(const string& __str, size_t* __idx = 0, int __base = 10)
5372  { return __gnu_cxx::__stoa(&std::strtoul, "stoul", __str.c_str(),
5373  __idx, __base); }
5374 
5375  inline long long
5376  stoll(const string& __str, size_t* __idx = 0, int __base = 10)
5377  { return __gnu_cxx::__stoa(&std::strtoll, "stoll", __str.c_str(),
5378  __idx, __base); }
5379 
5380  inline unsigned long long
5381  stoull(const string& __str, size_t* __idx = 0, int __base = 10)
5382  { return __gnu_cxx::__stoa(&std::strtoull, "stoull", __str.c_str(),
5383  __idx, __base); }
5384 
5385  // NB: strtof vs strtod.
5386  inline float
5387  stof(const string& __str, size_t* __idx = 0)
5388  { return __gnu_cxx::__stoa(&std::strtof, "stof", __str.c_str(), __idx); }
5389 
5390  inline double
5391  stod(const string& __str, size_t* __idx = 0)
5392  { return __gnu_cxx::__stoa(&std::strtod, "stod", __str.c_str(), __idx); }
5393 
5394  inline long double
5395  stold(const string& __str, size_t* __idx = 0)
5396  { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }
5397 
5398  // NB: (v)snprintf vs sprintf.
5399 
5400  // DR 1261.
5401  inline string
5402  to_string(int __val)
5403  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
5404  "%d", __val); }
5405 
5406  inline string
5407  to_string(unsigned __val)
5408  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5409  4 * sizeof(unsigned),
5410  "%u", __val); }
5411 
5412  inline string
5413  to_string(long __val)
5414  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
5415  "%ld", __val); }
5416 
5417  inline string
5418  to_string(unsigned long __val)
5419  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5420  4 * sizeof(unsigned long),
5421  "%lu", __val); }
5422 
5423  inline string
5424  to_string(long long __val)
5425  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5426  4 * sizeof(long long),
5427  "%lld", __val); }
5428 
5429  inline string
5430  to_string(unsigned long long __val)
5431  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5432  4 * sizeof(unsigned long long),
5433  "%llu", __val); }
5434 
5435  inline string
5436  to_string(float __val)
5437  {
5438  const int __n =
5439  __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
5440  return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5441  "%f", __val);
5442  }
5443 
5444  inline string
5445  to_string(double __val)
5446  {
5447  const int __n =
5448  __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
5449  return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5450  "%f", __val);
5451  }
5452 
5453  inline string
5454  to_string(long double __val)
5455  {
5456  const int __n =
5457  __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
5458  return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5459  "%Lf", __val);
5460  }
5461 
5462 #ifdef _GLIBCXX_USE_WCHAR_T
5463  inline int
5464  stoi(const wstring& __str, size_t* __idx = 0, int __base = 10)
5465  { return __gnu_cxx::__stoa<long, int>(&std::wcstol, "stoi", __str.c_str(),
5466  __idx, __base); }
5467 
5468  inline long
5469  stol(const wstring& __str, size_t* __idx = 0, int __base = 10)
5470  { return __gnu_cxx::__stoa(&std::wcstol, "stol", __str.c_str(),
5471  __idx, __base); }
5472 
5473  inline unsigned long
5474  stoul(const wstring& __str, size_t* __idx = 0, int __base = 10)
5475  { return __gnu_cxx::__stoa(&std::wcstoul, "stoul", __str.c_str(),
5476  __idx, __base); }
5477 
5478  inline long long
5479  stoll(const wstring& __str, size_t* __idx = 0, int __base = 10)
5480  { return __gnu_cxx::__stoa(&std::wcstoll, "stoll", __str.c_str(),
5481  __idx, __base); }
5482 
5483  inline unsigned long long
5484  stoull(const wstring& __str, size_t* __idx = 0, int __base = 10)
5485  { return __gnu_cxx::__stoa(&std::wcstoull, "stoull", __str.c_str(),
5486  __idx, __base); }
5487 
5488  // NB: wcstof vs wcstod.
5489  inline float
5490  stof(const wstring& __str, size_t* __idx = 0)
5491  { return __gnu_cxx::__stoa(&std::wcstof, "stof", __str.c_str(), __idx); }
5492 
5493  inline double
5494  stod(const wstring& __str, size_t* __idx = 0)
5495  { return __gnu_cxx::__stoa(&std::wcstod, "stod", __str.c_str(), __idx); }
5496 
5497  inline long double
5498  stold(const wstring& __str, size_t* __idx = 0)
5499  { return __gnu_cxx::__stoa(&std::wcstold, "stold", __str.c_str(), __idx); }
5500 
5501 #ifndef _GLIBCXX_HAVE_BROKEN_VSWPRINTF
5502  // DR 1261.
5503  inline wstring
5504  to_wstring(int __val)
5505  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(int),
5506  L"%d", __val); }
5507 
5508  inline wstring
5509  to_wstring(unsigned __val)
5510  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5511  4 * sizeof(unsigned),
5512  L"%u", __val); }
5513 
5514  inline wstring
5515  to_wstring(long __val)
5516  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(long),
5517  L"%ld", __val); }
5518 
5519  inline wstring
5520  to_wstring(unsigned long __val)
5521  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5522  4 * sizeof(unsigned long),
5523  L"%lu", __val); }
5524 
5525  inline wstring
5526  to_wstring(long long __val)
5527  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5528  4 * sizeof(long long),
5529  L"%lld", __val); }
5530 
5531  inline wstring
5532  to_wstring(unsigned long long __val)
5533  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5534  4 * sizeof(unsigned long long),
5535  L"%llu", __val); }
5536 
5537  inline wstring
5538  to_wstring(float __val)
5539  {
5540  const int __n =
5541  __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
5542  return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5543  L"%f", __val);
5544  }
5545 
5546  inline wstring
5547  to_wstring(double __val)
5548  {
5549  const int __n =
5550  __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
5551  return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5552  L"%f", __val);
5553  }
5554 
5555  inline wstring
5556  to_wstring(long double __val)
5557  {
5558  const int __n =
5559  __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
5560  return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5561  L"%Lf", __val);
5562  }
5563 #endif // _GLIBCXX_HAVE_BROKEN_VSWPRINTF
5564 #endif
5565 
5566 _GLIBCXX_END_NAMESPACE_CXX11
5567 _GLIBCXX_END_NAMESPACE_VERSION
5568 } // namespace
5569 
5570 #endif /* C++11 && _GLIBCXX_USE_C99 ... */
5571 
5572 #if __cplusplus >= 201103L
5573 
5574 #include <bits/functional_hash.h>
5575 
5576 namespace std _GLIBCXX_VISIBILITY(default)
5577 {
5578 _GLIBCXX_BEGIN_NAMESPACE_VERSION
5579 
5580  // DR 1182.
5581 
5582 #ifndef _GLIBCXX_COMPATIBILITY_CXX0X
5583  /// std::hash specialization for string.
5584  template<>
5585  struct hash<string>
5586  : public __hash_base<size_t, string>
5587  {
5588  size_t
5589  operator()(const string& __s) const noexcept
5590  { return std::_Hash_impl::hash(__s.data(), __s.length()); }
5591  };
5592 
5593  template<>
5594  struct __is_fast_hash<hash<string>> : std::false_type
5595  { };
5596 
5597 #ifdef _GLIBCXX_USE_WCHAR_T
5598  /// std::hash specialization for wstring.
5599  template<>
5600  struct hash<wstring>
5601  : public __hash_base<size_t, wstring>
5602  {
5603  size_t
5604  operator()(const wstring& __s) const noexcept
5605  { return std::_Hash_impl::hash(__s.data(),
5606  __s.length() * sizeof(wchar_t)); }
5607  };
5608 
5609  template<>
5610  struct __is_fast_hash<hash<wstring>> : std::false_type
5611  { };
5612 #endif
5613 #endif /* _GLIBCXX_COMPATIBILITY_CXX0X */
5614 
5615 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
5616  /// std::hash specialization for u16string.
5617  template<>
5618  struct hash<u16string>
5619  : public __hash_base<size_t, u16string>
5620  {
5621  size_t
5622  operator()(const u16string& __s) const noexcept
5623  { return std::_Hash_impl::hash(__s.data(),
5624  __s.length() * sizeof(char16_t)); }
5625  };
5626 
5627  template<>
5628  struct __is_fast_hash<hash<u16string>> : std::false_type
5629  { };
5630 
5631  /// std::hash specialization for u32string.
5632  template<>
5633  struct hash<u32string>
5634  : public __hash_base<size_t, u32string>
5635  {
5636  size_t
5637  operator()(const u32string& __s) const noexcept
5638  { return std::_Hash_impl::hash(__s.data(),
5639  __s.length() * sizeof(char32_t)); }
5640  };
5641 
5642  template<>
5643  struct __is_fast_hash<hash<u32string>> : std::false_type
5644  { };
5645 #endif
5646 
5647 _GLIBCXX_END_NAMESPACE_VERSION
5648 
5649 #if __cplusplus > 201103L
5650 
5651 #define __cpp_lib_string_udls 201304
5652 
5653  inline namespace literals
5654  {
5655  inline namespace string_literals
5656  {
5657 _GLIBCXX_BEGIN_NAMESPACE_VERSION
5658 
5659  _GLIBCXX_DEFAULT_ABI_TAG
5660  inline basic_string<char>
5661  operator""s(const char* __str, size_t __len)
5662  { return basic_string<char>{__str, __len}; }
5663 
5664 #ifdef _GLIBCXX_USE_WCHAR_T
5665  _GLIBCXX_DEFAULT_ABI_TAG
5666  inline basic_string<wchar_t>
5667  operator""s(const wchar_t* __str, size_t __len)
5668  { return basic_string<wchar_t>{__str, __len}; }
5669 #endif
5670 
5671 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
5672  _GLIBCXX_DEFAULT_ABI_TAG
5673  inline basic_string<char16_t>
5674  operator""s(const char16_t* __str, size_t __len)
5675  { return basic_string<char16_t>{__str, __len}; }
5676 
5677  _GLIBCXX_DEFAULT_ABI_TAG
5678  inline basic_string<char32_t>
5679  operator""s(const char32_t* __str, size_t __len)
5680  { return basic_string<char32_t>{__str, __len}; }
5681 #endif
5682 
5683 _GLIBCXX_END_NAMESPACE_VERSION
5684  } // inline namespace string_literals
5685  } // inline namespace literals
5686 
5687 #endif // __cplusplus > 201103L
5688 
5689 } // namespace std
5690 
5691 #endif // C++11
5692 
5693 #endif /* _BASIC_STRING_H */
basic_string & operator+=(const basic_string &__str)
Append a string to this string.
size_type rfind(const basic_string &__str, size_type __pos=npos) const noexcept
Find last position of a string.
integral_constant
Definition: type_traits:69
const_reverse_iterator crbegin() const noexcept
size_type find_first_not_of(const basic_string &__str, size_type __pos=0) const noexcept
Find position of a character not in string.
basic_string & operator+=(const _CharT *__s)
Append a C string.
basic_string & erase(size_type __pos=0, size_type __n=npos)
Remove characters.
reference at(size_type __n)
Provides access to the data contained in the string.
static const size_type npos
Value returned by various member functions when they fail.
basic_string & replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
Replace characters with multiple characters.
const_iterator cend() const noexcept
bool empty() const noexcept
Template class basic_ostream.
Definition: iosfwd:86
basic_string & assign(_InputIterator __first, _InputIterator __last)
Set value to a range of characters.
basic_string & operator+=(initializer_list< _CharT > __l)
Append an initializer_list of characters.
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
basic_string & replace(iterator __i1, iterator __i2, initializer_list< _CharT > __l)
Replace range of characters with initializer_list.
complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition: complex:326
basic_string & replace(iterator __i1, iterator __i2, const basic_string &__str)
Replace range of characters with string.
const_iterator cbegin() const noexcept
Uniform interface to all pointer-like types.
Definition: ptr_traits.h:132
basic_istream< _CharT, _Traits > & getline(basic_istream< _CharT, _Traits > &__is, basic_string< _CharT, _Traits, _Alloc > &__str, _CharT __delim)
Read a line from stream into a string.
basic_string & operator=(_CharT __c)
Set value to string of length 1.
basic_string & append(initializer_list< _CharT > __l)
Append an initializer_list of characters.
basic_string & insert(size_type __pos, const _CharT *__s)
Insert a C string.
basic_string & assign(initializer_list< _CharT > __l)
Set value to an initializer_list of characters.
basic_string & append(const _CharT *__s)
Append a C string.
basic_string & operator=(const _CharT *__s)
Copy contents of s into this string.
basic_string & insert(size_type __pos1, const basic_string &__str)
Insert value of a string.
basic_string & append(const basic_string &__str)
Append a string to this string.
reference front()
initializer_list
basic_string(basic_string &&__str) noexcept
Move construct string.
basic_string & operator=(basic_string &&__str)
Move assign the value of str to this string.
basic_string & assign(size_type __n, _CharT __c)
Set value to multiple characters.
const_reverse_iterator rbegin() const noexcept
basic_string & operator=(initializer_list< _CharT > __l)
Set value to string constructed from initializer list.
One of the comparison functors.
Definition: stl_function.h:341
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:195
void shrink_to_fit() noexcept
A non-binding request to reduce capacity() to size().
const _CharT * c_str() const noexcept
Return const pointer to null-terminated contents.
allocator_type get_allocator() const noexcept
Return copy of allocator used to construct this string.
const_reverse_iterator rend() const noexcept
size_type length() const noexcept
Returns the number of characters in the string, not including any null-termination.
std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, bitset< _Nb > &__x)
Global I/O operators for bitsets.
Definition: bitset:1462
reverse_iterator rbegin()
Uniform interface to C++98 and C++0x allocators.
iterator erase(iterator __position)
Remove one character.
void pop_back()
Remove the last character.
size_type find(const _CharT *__s, size_type __pos=0) const
Find position of a C string.
size_type find(const _CharT *__s, size_type __pos, size_type __n) const
Find position of a C substring.
basic_string & append(_InputIterator __first, _InputIterator __last)
Append a range of characters.
basic_string & operator=(const basic_string &__str)
Assign the value of str to this string.
ISO C++ entities toplevel namespace is std.
basic_string & replace(iterator __i1, iterator __i2, const _CharT *__s, size_type __n)
Replace range of characters with C substring.
basic_string & assign(basic_string &&__str)
Set value to contents of another string.
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Definition: functions.h:558
size_type find_first_of(const basic_string &__str, size_type __pos=0) const noexcept
Find position of a character of string.
basic_string & insert(size_type __pos, size_type __n, _CharT __c)
Insert multiple characters.
const _CharT * data() const noexcept
Return const pointer to contents.
size_type find_last_not_of(const _CharT *__s, size_type __pos=npos) const
Find last position of a character not in C string.
const_reference operator[](size_type __pos) const noexcept
Subscript access to the data contained in the string.
size_type find_first_not_of(const _CharT *__s, size_type __pos=0) const
Find position of a character not in C string.
basic_string substr(size_type __pos=0, size_type __n=npos) const
Get a substring.
const_iterator begin() const noexcept
const_reference front() const noexcept
Basis for explicit traits specializations.
Definition: char_traits.h:227
size_type max_size() const noexcept
Returns the size() of the largest possible string.
void insert(iterator __p, _InputIterator __beg, _InputIterator __end)
Insert a range of characters.
size_type rfind(const _CharT *__s, size_type __pos=npos) const
Find last position of a C string.
reference operator[](size_type __pos)
Subscript access to the data contained in the string.
Template class basic_istream.
Definition: iosfwd:83
size_type find_last_of(_CharT __c, size_type __pos=npos) const noexcept
Find last position of a character.
void push_back(_CharT __c)
Append a single character.
const_reference at(size_type __n) const
Provides access to the data contained in the string.
basic_string()
Default constructor creates an empty string.
size_type find(const basic_string &__str, size_type __pos=0) const noexcept
Find position of a string.
basic_string & replace(iterator __i1, iterator __i2, _InputIterator __k1, _InputIterator __k2)
Replace range of characters with range.
void resize(size_type __n)
Resizes the string to the specified number of characters.
const_reference back() const noexcept
basic_string & replace(iterator __i1, iterator __i2, const _CharT *__s)
Replace range of characters with C string.
basic_string & replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
Replace range of characters with multiple characters.
size_type find_last_of(const _CharT *__s, size_type __pos=npos) const
Find last position of a character of C string.
const_reverse_iterator crend() const noexcept
basic_string & assign(const _CharT *__s)
Set value to contents of a C string.
void resize(size_type __n, _CharT __c)
Resizes the string to the specified number of characters.
reverse_iterator rend()
size_type find_first_of(_CharT __c, size_type __pos=0) const noexcept
Find position of a character.
size_type capacity() const noexcept
size_type find_first_of(const _CharT *__s, size_type __pos=0) const
Find position of a character of C string.
basic_string & replace(size_type __pos1, size_type __n1, const basic_string &__str, size_type __pos2, size_type __n2)
Replace characters with value from another string.
~basic_string() noexcept
Destroy the string instance.
Marking input iterators.
int compare(const basic_string &__str) const
Compare to a string.
void reserve(size_type __res_arg=0)
Attempt to preallocate enough memory for specified number of characters.
void insert(iterator __p, size_type __n, _CharT __c)
Insert multiple characters.
Primary class template hash.
Definition: system_error:134
basic_string & insert(size_type __pos1, const basic_string &__str, size_type __pos2, size_type __n)
Insert a substring.
basic_string & assign(const basic_string &__str, size_type __pos, size_type __n)
Set value to a substring of a string.
const_iterator end() const noexcept
void insert(iterator __p, initializer_list< _CharT > __l)
Insert an initializer_list of characters.
reference back()
basic_string & replace(size_type __pos, size_type __n1, const _CharT *__s)
Replace characters with value of a C string.
size_type copy(_CharT *__s, size_type __n, size_type __pos=0) const
Copy substring into C string.
size_type find_last_not_of(const basic_string &__str, size_type __pos=npos) const noexcept
Find last position of a character not in string.
Managing sequences of characters and character-like objects.
Forward iterators support a superset of input iterator operations.
void swap(basic_string &__s)
Swap contents with another string.
basic_string & operator+=(_CharT __c)
Append a character.
char_type widen(char __c) const
Widens characters.
Definition: basic_ios.h:449
iterator insert(iterator __p, _CharT __c)
Insert one character.
basic_string & replace(size_type __pos, size_type __n, const basic_string &__str)
Replace characters with value from another string.
basic_string & assign(const basic_string &__str)
Set value to contents of another string.
size_type find_last_of(const basic_string &__str, size_type __pos=npos) const noexcept
Find last position of a character of string.