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 _GLIBCXX_END_NAMESPACE_CXX11
2534 #else // !_GLIBCXX_USE_CXX11_ABI
2535  // Reference-counted COW string implentation
2536 
2537  /**
2538  * @class basic_string basic_string.h <string>
2539  * @brief Managing sequences of characters and character-like objects.
2540  *
2541  * @ingroup strings
2542  * @ingroup sequences
2543  *
2544  * @tparam _CharT Type of character
2545  * @tparam _Traits Traits for character type, defaults to
2546  * char_traits<_CharT>.
2547  * @tparam _Alloc Allocator type, defaults to allocator<_CharT>.
2548  *
2549  * Meets the requirements of a <a href="tables.html#65">container</a>, a
2550  * <a href="tables.html#66">reversible container</a>, and a
2551  * <a href="tables.html#67">sequence</a>. Of the
2552  * <a href="tables.html#68">optional sequence requirements</a>, only
2553  * @c push_back, @c at, and @c %array access are supported.
2554  *
2555  * @doctodo
2556  *
2557  *
2558  * Documentation? What's that?
2559  * Nathan Myers <ncm@cantrip.org>.
2560  *
2561  * A string looks like this:
2562  *
2563  * @code
2564  * [_Rep]
2565  * _M_length
2566  * [basic_string<char_type>] _M_capacity
2567  * _M_dataplus _M_refcount
2568  * _M_p ----------------> unnamed array of char_type
2569  * @endcode
2570  *
2571  * Where the _M_p points to the first character in the string, and
2572  * you cast it to a pointer-to-_Rep and subtract 1 to get a
2573  * pointer to the header.
2574  *
2575  * This approach has the enormous advantage that a string object
2576  * requires only one allocation. All the ugliness is confined
2577  * within a single %pair of inline functions, which each compile to
2578  * a single @a add instruction: _Rep::_M_data(), and
2579  * string::_M_rep(); and the allocation function which gets a
2580  * block of raw bytes and with room enough and constructs a _Rep
2581  * object at the front.
2582  *
2583  * The reason you want _M_data pointing to the character %array and
2584  * not the _Rep is so that the debugger can see the string
2585  * contents. (Probably we should add a non-inline member to get
2586  * the _Rep for the debugger to use, so users can check the actual
2587  * string length.)
2588  *
2589  * Note that the _Rep object is a POD so that you can have a
2590  * static <em>empty string</em> _Rep object already @a constructed before
2591  * static constructors have run. The reference-count encoding is
2592  * chosen so that a 0 indicates one reference, so you never try to
2593  * destroy the empty-string _Rep object.
2594  *
2595  * All but the last paragraph is considered pretty conventional
2596  * for a C++ string implementation.
2597  */
2598  // 21.3 Template class basic_string
2599  template<typename _CharT, typename _Traits, typename _Alloc>
2601  {
2602  typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;
2603 
2604  // Types:
2605  public:
2606  typedef _Traits traits_type;
2607  typedef typename _Traits::char_type value_type;
2608  typedef _Alloc allocator_type;
2609  typedef typename _CharT_alloc_type::size_type size_type;
2610  typedef typename _CharT_alloc_type::difference_type difference_type;
2611  typedef typename _CharT_alloc_type::reference reference;
2612  typedef typename _CharT_alloc_type::const_reference const_reference;
2613  typedef typename _CharT_alloc_type::pointer pointer;
2614  typedef typename _CharT_alloc_type::const_pointer const_pointer;
2615  typedef __gnu_cxx::__normal_iterator<pointer, basic_string> iterator;
2616  typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
2617  const_iterator;
2620 
2621  private:
2622  // _Rep: string representation
2623  // Invariants:
2624  // 1. String really contains _M_length + 1 characters: due to 21.3.4
2625  // must be kept null-terminated.
2626  // 2. _M_capacity >= _M_length
2627  // Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).
2628  // 3. _M_refcount has three states:
2629  // -1: leaked, one reference, no ref-copies allowed, non-const.
2630  // 0: one reference, non-const.
2631  // n>0: n + 1 references, operations require a lock, const.
2632  // 4. All fields==0 is an empty string, given the extra storage
2633  // beyond-the-end for a null terminator; thus, the shared
2634  // empty string representation needs no constructor.
2635 
2636  struct _Rep_base
2637  {
2638  size_type _M_length;
2639  size_type _M_capacity;
2640  _Atomic_word _M_refcount;
2641  };
2642 
2643  struct _Rep : _Rep_base
2644  {
2645  // Types:
2646  typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
2647 
2648  // (Public) Data members:
2649 
2650  // The maximum number of individual char_type elements of an
2651  // individual string is determined by _S_max_size. This is the
2652  // value that will be returned by max_size(). (Whereas npos
2653  // is the maximum number of bytes the allocator can allocate.)
2654  // If one was to divvy up the theoretical largest size string,
2655  // with a terminating character and m _CharT elements, it'd
2656  // look like this:
2657  // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
2658  // Solving for m:
2659  // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
2660  // In addition, this implementation quarters this amount.
2661  static const size_type _S_max_size;
2662  static const _CharT _S_terminal;
2663 
2664  // The following storage is init'd to 0 by the linker, resulting
2665  // (carefully) in an empty string with one reference.
2666  static size_type _S_empty_rep_storage[];
2667 
2668  static _Rep&
2669  _S_empty_rep() _GLIBCXX_NOEXCEPT
2670  {
2671  // NB: Mild hack to avoid strict-aliasing warnings. Note that
2672  // _S_empty_rep_storage is never modified and the punning should
2673  // be reasonably safe in this case.
2674  void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);
2675  return *reinterpret_cast<_Rep*>(__p);
2676  }
2677 
2678  bool
2679  _M_is_leaked() const _GLIBCXX_NOEXCEPT
2680  { return this->_M_refcount < 0; }
2681 
2682  bool
2683  _M_is_shared() const _GLIBCXX_NOEXCEPT
2684  { return this->_M_refcount > 0; }
2685 
2686  void
2687  _M_set_leaked() _GLIBCXX_NOEXCEPT
2688  { this->_M_refcount = -1; }
2689 
2690  void
2691  _M_set_sharable() _GLIBCXX_NOEXCEPT
2692  { this->_M_refcount = 0; }
2693 
2694  void
2695  _M_set_length_and_sharable(size_type __n) _GLIBCXX_NOEXCEPT
2696  {
2697 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2698  if (__builtin_expect(this != &_S_empty_rep(), false))
2699 #endif
2700  {
2701  this->_M_set_sharable(); // One reference.
2702  this->_M_length = __n;
2703  traits_type::assign(this->_M_refdata()[__n], _S_terminal);
2704  // grrr. (per 21.3.4)
2705  // You cannot leave those LWG people alone for a second.
2706  }
2707  }
2708 
2709  _CharT*
2710  _M_refdata() throw()
2711  { return reinterpret_cast<_CharT*>(this + 1); }
2712 
2713  _CharT*
2714  _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
2715  {
2716  return (!_M_is_leaked() && __alloc1 == __alloc2)
2717  ? _M_refcopy() : _M_clone(__alloc1);
2718  }
2719 
2720  // Create & Destroy
2721  static _Rep*
2722  _S_create(size_type, size_type, const _Alloc&);
2723 
2724  void
2725  _M_dispose(const _Alloc& __a) _GLIBCXX_NOEXCEPT
2726  {
2727 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2728  if (__builtin_expect(this != &_S_empty_rep(), false))
2729 #endif
2730  {
2731  // Be race-detector-friendly. For more info see bits/c++config.
2732  _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this->_M_refcount);
2733  if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
2734  -1) <= 0)
2735  {
2736  _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);
2737  _M_destroy(__a);
2738  }
2739  }
2740  } // XXX MT
2741 
2742  void
2743  _M_destroy(const _Alloc&) throw();
2744 
2745  _CharT*
2746  _M_refcopy() throw()
2747  {
2748 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2749  if (__builtin_expect(this != &_S_empty_rep(), false))
2750 #endif
2751  __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
2752  return _M_refdata();
2753  } // XXX MT
2754 
2755  _CharT*
2756  _M_clone(const _Alloc&, size_type __res = 0);
2757  };
2758 
2759  // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
2760  struct _Alloc_hider : _Alloc
2761  {
2762  _Alloc_hider(_CharT* __dat, const _Alloc& __a) _GLIBCXX_NOEXCEPT
2763  : _Alloc(__a), _M_p(__dat) { }
2764 
2765  _CharT* _M_p; // The actual data.
2766  };
2767 
2768  public:
2769  // Data Members (public):
2770  // NB: This is an unsigned type, and thus represents the maximum
2771  // size that the allocator can hold.
2772  /// Value returned by various member functions when they fail.
2773  static const size_type npos = static_cast<size_type>(-1);
2774 
2775  private:
2776  // Data Members (private):
2777  mutable _Alloc_hider _M_dataplus;
2778 
2779  _CharT*
2780  _M_data() const _GLIBCXX_NOEXCEPT
2781  { return _M_dataplus._M_p; }
2782 
2783  _CharT*
2784  _M_data(_CharT* __p) _GLIBCXX_NOEXCEPT
2785  { return (_M_dataplus._M_p = __p); }
2786 
2787  _Rep*
2788  _M_rep() const _GLIBCXX_NOEXCEPT
2789  { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
2790 
2791  // For the internal use we have functions similar to `begin'/`end'
2792  // but they do not call _M_leak.
2793  iterator
2794  _M_ibegin() const _GLIBCXX_NOEXCEPT
2795  { return iterator(_M_data()); }
2796 
2797  iterator
2798  _M_iend() const _GLIBCXX_NOEXCEPT
2799  { return iterator(_M_data() + this->size()); }
2800 
2801  void
2802  _M_leak() // for use in begin() & non-const op[]
2803  {
2804  if (!_M_rep()->_M_is_leaked())
2805  _M_leak_hard();
2806  }
2807 
2808  size_type
2809  _M_check(size_type __pos, const char* __s) const
2810  {
2811  if (__pos > this->size())
2812  __throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "
2813  "this->size() (which is %zu)"),
2814  __s, __pos, this->size());
2815  return __pos;
2816  }
2817 
2818  void
2819  _M_check_length(size_type __n1, size_type __n2, const char* __s) const
2820  {
2821  if (this->max_size() - (this->size() - __n1) < __n2)
2822  __throw_length_error(__N(__s));
2823  }
2824 
2825  // NB: _M_limit doesn't check for a bad __pos value.
2826  size_type
2827  _M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPT
2828  {
2829  const bool __testoff = __off < this->size() - __pos;
2830  return __testoff ? __off : this->size() - __pos;
2831  }
2832 
2833  // True if _Rep and source do not overlap.
2834  bool
2835  _M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPT
2836  {
2837  return (less<const _CharT*>()(__s, _M_data())
2838  || less<const _CharT*>()(_M_data() + this->size(), __s));
2839  }
2840 
2841  // When __n = 1 way faster than the general multichar
2842  // traits_type::copy/move/assign.
2843  static void
2844  _M_copy(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT
2845  {
2846  if (__n == 1)
2847  traits_type::assign(*__d, *__s);
2848  else
2849  traits_type::copy(__d, __s, __n);
2850  }
2851 
2852  static void
2853  _M_move(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT
2854  {
2855  if (__n == 1)
2856  traits_type::assign(*__d, *__s);
2857  else
2858  traits_type::move(__d, __s, __n);
2859  }
2860 
2861  static void
2862  _M_assign(_CharT* __d, size_type __n, _CharT __c) _GLIBCXX_NOEXCEPT
2863  {
2864  if (__n == 1)
2865  traits_type::assign(*__d, __c);
2866  else
2867  traits_type::assign(__d, __n, __c);
2868  }
2869 
2870  // _S_copy_chars is a separate template to permit specialization
2871  // to optimize for the common case of pointers as iterators.
2872  template<class _Iterator>
2873  static void
2874  _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
2875  {
2876  for (; __k1 != __k2; ++__k1, ++__p)
2877  traits_type::assign(*__p, *__k1); // These types are off.
2878  }
2879 
2880  static void
2881  _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) _GLIBCXX_NOEXCEPT
2882  { _S_copy_chars(__p, __k1.base(), __k2.base()); }
2883 
2884  static void
2885  _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
2886  _GLIBCXX_NOEXCEPT
2887  { _S_copy_chars(__p, __k1.base(), __k2.base()); }
2888 
2889  static void
2890  _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) _GLIBCXX_NOEXCEPT
2891  { _M_copy(__p, __k1, __k2 - __k1); }
2892 
2893  static void
2894  _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
2895  _GLIBCXX_NOEXCEPT
2896  { _M_copy(__p, __k1, __k2 - __k1); }
2897 
2898  static int
2899  _S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPT
2900  {
2901  const difference_type __d = difference_type(__n1 - __n2);
2902 
2903  if (__d > __gnu_cxx::__numeric_traits<int>::__max)
2904  return __gnu_cxx::__numeric_traits<int>::__max;
2905  else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
2906  return __gnu_cxx::__numeric_traits<int>::__min;
2907  else
2908  return int(__d);
2909  }
2910 
2911  void
2912  _M_mutate(size_type __pos, size_type __len1, size_type __len2);
2913 
2914  void
2915  _M_leak_hard();
2916 
2917  static _Rep&
2918  _S_empty_rep() _GLIBCXX_NOEXCEPT
2919  { return _Rep::_S_empty_rep(); }
2920 
2921  public:
2922  // Construct/copy/destroy:
2923  // NB: We overload ctors in some cases instead of using default
2924  // arguments, per 17.4.4.4 para. 2 item 2.
2925 
2926  /**
2927  * @brief Default constructor creates an empty string.
2928  */
2930 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2931  : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
2932 #else
2933  : _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()){ }
2934 #endif
2935 
2936  /**
2937  * @brief Construct an empty string using allocator @a a.
2938  */
2939  explicit
2940  basic_string(const _Alloc& __a);
2941 
2942  // NB: per LWG issue 42, semantics different from IS:
2943  /**
2944  * @brief Construct string with copy of value of @a str.
2945  * @param __str Source string.
2946  */
2947  basic_string(const basic_string& __str);
2948  /**
2949  * @brief Construct string as copy of a substring.
2950  * @param __str Source string.
2951  * @param __pos Index of first character to copy from.
2952  * @param __n Number of characters to copy (default remainder).
2953  */
2954  basic_string(const basic_string& __str, size_type __pos,
2955  size_type __n = npos);
2956  /**
2957  * @brief Construct string as copy of a substring.
2958  * @param __str Source string.
2959  * @param __pos Index of first character to copy from.
2960  * @param __n Number of characters to copy.
2961  * @param __a Allocator to use.
2962  */
2963  basic_string(const basic_string& __str, size_type __pos,
2964  size_type __n, const _Alloc& __a);
2965 
2966  /**
2967  * @brief Construct string initialized by a character %array.
2968  * @param __s Source character %array.
2969  * @param __n Number of characters to copy.
2970  * @param __a Allocator to use (default is default allocator).
2971  *
2972  * NB: @a __s must have at least @a __n characters, &apos;\\0&apos;
2973  * has no special meaning.
2974  */
2975  basic_string(const _CharT* __s, size_type __n,
2976  const _Alloc& __a = _Alloc());
2977  /**
2978  * @brief Construct string as copy of a C string.
2979  * @param __s Source C string.
2980  * @param __a Allocator to use (default is default allocator).
2981  */
2982  basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
2983  /**
2984  * @brief Construct string as multiple characters.
2985  * @param __n Number of characters.
2986  * @param __c Character to use.
2987  * @param __a Allocator to use (default is default allocator).
2988  */
2989  basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
2990 
2991 #if __cplusplus >= 201103L
2992  /**
2993  * @brief Move construct string.
2994  * @param __str Source string.
2995  *
2996  * The newly-created string contains the exact contents of @a __str.
2997  * @a __str is a valid, but unspecified string.
2998  **/
3000 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
3001  noexcept // FIXME C++11: should always be noexcept.
3002 #endif
3003  : _M_dataplus(__str._M_dataplus)
3004  {
3005 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
3006  __str._M_data(_S_empty_rep()._M_refdata());
3007 #else
3008  __str._M_data(_S_construct(size_type(), _CharT(), get_allocator()));
3009 #endif
3010  }
3011 
3012  /**
3013  * @brief Construct string from an initializer %list.
3014  * @param __l std::initializer_list of characters.
3015  * @param __a Allocator to use (default is default allocator).
3016  */
3017  basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc());
3018 #endif // C++11
3019 
3020  /**
3021  * @brief Construct string as copy of a range.
3022  * @param __beg Start of range.
3023  * @param __end End of range.
3024  * @param __a Allocator to use (default is default allocator).
3025  */
3026  template<class _InputIterator>
3027  basic_string(_InputIterator __beg, _InputIterator __end,
3028  const _Alloc& __a = _Alloc());
3029 
3030  /**
3031  * @brief Destroy the string instance.
3032  */
3033  ~basic_string() _GLIBCXX_NOEXCEPT
3034  { _M_rep()->_M_dispose(this->get_allocator()); }
3035 
3036  /**
3037  * @brief Assign the value of @a str to this string.
3038  * @param __str Source string.
3039  */
3040  basic_string&
3041  operator=(const basic_string& __str)
3042  { return this->assign(__str); }
3043 
3044  /**
3045  * @brief Copy contents of @a s into this string.
3046  * @param __s Source null-terminated string.
3047  */
3048  basic_string&
3049  operator=(const _CharT* __s)
3050  { return this->assign(__s); }
3051 
3052  /**
3053  * @brief Set value to string of length 1.
3054  * @param __c Source character.
3055  *
3056  * Assigning to a character makes this string length 1 and
3057  * (*this)[0] == @a c.
3058  */
3059  basic_string&
3060  operator=(_CharT __c)
3061  {
3062  this->assign(1, __c);
3063  return *this;
3064  }
3065 
3066 #if __cplusplus >= 201103L
3067  /**
3068  * @brief Move assign the value of @a str to this string.
3069  * @param __str Source string.
3070  *
3071  * The contents of @a str are moved into this string (without copying).
3072  * @a str is a valid, but unspecified string.
3073  **/
3074  // PR 58265, this should be noexcept.
3075  basic_string&
3077  {
3078  // NB: DR 1204.
3079  this->swap(__str);
3080  return *this;
3081  }
3082 
3083  /**
3084  * @brief Set value to string constructed from initializer %list.
3085  * @param __l std::initializer_list.
3086  */
3087  basic_string&
3089  {
3090  this->assign(__l.begin(), __l.size());
3091  return *this;
3092  }
3093 #endif // C++11
3094 
3095  // Iterators:
3096  /**
3097  * Returns a read/write iterator that points to the first character in
3098  * the %string. Unshares the string.
3099  */
3100  iterator
3101  begin() // FIXME C++11: should be noexcept.
3102  {
3103  _M_leak();
3104  return iterator(_M_data());
3105  }
3106 
3107  /**
3108  * Returns a read-only (constant) iterator that points to the first
3109  * character in the %string.
3110  */
3111  const_iterator
3112  begin() const _GLIBCXX_NOEXCEPT
3113  { return const_iterator(_M_data()); }
3114 
3115  /**
3116  * Returns a read/write iterator that points one past the last
3117  * character in the %string. Unshares the string.
3118  */
3119  iterator
3120  end() // FIXME C++11: should be noexcept.
3121  {
3122  _M_leak();
3123  return iterator(_M_data() + this->size());
3124  }
3125 
3126  /**
3127  * Returns a read-only (constant) iterator that points one past the
3128  * last character in the %string.
3129  */
3130  const_iterator
3131  end() const _GLIBCXX_NOEXCEPT
3132  { return const_iterator(_M_data() + this->size()); }
3133 
3134  /**
3135  * Returns a read/write reverse iterator that points to the last
3136  * character in the %string. Iteration is done in reverse element
3137  * order. Unshares the string.
3138  */
3139  reverse_iterator
3140  rbegin() // FIXME C++11: should be noexcept.
3141  { return reverse_iterator(this->end()); }
3142 
3143  /**
3144  * Returns a read-only (constant) reverse iterator that points
3145  * to the last character in the %string. Iteration is done in
3146  * reverse element order.
3147  */
3148  const_reverse_iterator
3149  rbegin() const _GLIBCXX_NOEXCEPT
3150  { return const_reverse_iterator(this->end()); }
3151 
3152  /**
3153  * Returns a read/write reverse iterator that points to one before the
3154  * first character in the %string. Iteration is done in reverse
3155  * element order. Unshares the string.
3156  */
3157  reverse_iterator
3158  rend() // FIXME C++11: should be noexcept.
3159  { return reverse_iterator(this->begin()); }
3160 
3161  /**
3162  * Returns a read-only (constant) reverse iterator that points
3163  * to one before the first character in the %string. Iteration
3164  * is done in reverse element order.
3165  */
3166  const_reverse_iterator
3167  rend() const _GLIBCXX_NOEXCEPT
3168  { return const_reverse_iterator(this->begin()); }
3169 
3170 #if __cplusplus >= 201103L
3171  /**
3172  * Returns a read-only (constant) iterator that points to the first
3173  * character in the %string.
3174  */
3175  const_iterator
3176  cbegin() const noexcept
3177  { return const_iterator(this->_M_data()); }
3178 
3179  /**
3180  * Returns a read-only (constant) iterator that points one past the
3181  * last character in the %string.
3182  */
3183  const_iterator
3184  cend() const noexcept
3185  { return const_iterator(this->_M_data() + this->size()); }
3186 
3187  /**
3188  * Returns a read-only (constant) reverse iterator that points
3189  * to the last character in the %string. Iteration is done in
3190  * reverse element order.
3191  */
3192  const_reverse_iterator
3193  crbegin() const noexcept
3194  { return const_reverse_iterator(this->end()); }
3195 
3196  /**
3197  * Returns a read-only (constant) reverse iterator that points
3198  * to one before the first character in the %string. Iteration
3199  * is done in reverse element order.
3200  */
3201  const_reverse_iterator
3202  crend() const noexcept
3203  { return const_reverse_iterator(this->begin()); }
3204 #endif
3205 
3206  public:
3207  // Capacity:
3208  /// Returns the number of characters in the string, not including any
3209  /// null-termination.
3210  size_type
3211  size() const _GLIBCXX_NOEXCEPT
3212  { return _M_rep()->_M_length; }
3213 
3214  /// Returns the number of characters in the string, not including any
3215  /// null-termination.
3216  size_type
3217  length() const _GLIBCXX_NOEXCEPT
3218  { return _M_rep()->_M_length; }
3219 
3220  /// Returns the size() of the largest possible %string.
3221  size_type
3222  max_size() const _GLIBCXX_NOEXCEPT
3223  { return _Rep::_S_max_size; }
3224 
3225  /**
3226  * @brief Resizes the %string to the specified number of characters.
3227  * @param __n Number of characters the %string should contain.
3228  * @param __c Character to fill any new elements.
3229  *
3230  * This function will %resize the %string to the specified
3231  * number of characters. If the number is smaller than the
3232  * %string's current size the %string is truncated, otherwise
3233  * the %string is extended and new elements are %set to @a __c.
3234  */
3235  void
3236  resize(size_type __n, _CharT __c);
3237 
3238  /**
3239  * @brief Resizes the %string to the specified number of characters.
3240  * @param __n Number of characters the %string should contain.
3241  *
3242  * This function will resize the %string to the specified length. If
3243  * the new size is smaller than the %string's current size the %string
3244  * is truncated, otherwise the %string is extended and new characters
3245  * are default-constructed. For basic types such as char, this means
3246  * setting them to 0.
3247  */
3248  void
3249  resize(size_type __n)
3250  { this->resize(__n, _CharT()); }
3251 
3252 #if __cplusplus >= 201103L
3253  /// A non-binding request to reduce capacity() to size().
3254  void
3255  shrink_to_fit() _GLIBCXX_NOEXCEPT
3256  {
3257 #if __cpp_exceptions
3258  if (capacity() > size())
3259  {
3260  try
3261  { reserve(0); }
3262  catch(...)
3263  { }
3264  }
3265 #endif
3266  }
3267 #endif
3268 
3269  /**
3270  * Returns the total number of characters that the %string can hold
3271  * before needing to allocate more memory.
3272  */
3273  size_type
3274  capacity() const _GLIBCXX_NOEXCEPT
3275  { return _M_rep()->_M_capacity; }
3276 
3277  /**
3278  * @brief Attempt to preallocate enough memory for specified number of
3279  * characters.
3280  * @param __res_arg Number of characters required.
3281  * @throw std::length_error If @a __res_arg exceeds @c max_size().
3282  *
3283  * This function attempts to reserve enough memory for the
3284  * %string to hold the specified number of characters. If the
3285  * number requested is more than max_size(), length_error is
3286  * thrown.
3287  *
3288  * The advantage of this function is that if optimal code is a
3289  * necessity and the user can determine the string length that will be
3290  * required, the user can reserve the memory in %advance, and thus
3291  * prevent a possible reallocation of memory and copying of %string
3292  * data.
3293  */
3294  void
3295  reserve(size_type __res_arg = 0);
3296 
3297  /**
3298  * Erases the string, making it empty.
3299  */
3300  // PR 56166: this should not throw.
3301  void
3303  { _M_mutate(0, this->size(), 0); }
3304 
3305  /**
3306  * Returns true if the %string is empty. Equivalent to
3307  * <code>*this == ""</code>.
3308  */
3309  bool
3310  empty() const _GLIBCXX_NOEXCEPT
3311  { return this->size() == 0; }
3312 
3313  // Element access:
3314  /**
3315  * @brief Subscript access to the data contained in the %string.
3316  * @param __pos The index of the character to access.
3317  * @return Read-only (constant) reference to the character.
3318  *
3319  * This operator allows for easy, array-style, data access.
3320  * Note that data access with this operator is unchecked and
3321  * out_of_range lookups are not defined. (For checked lookups
3322  * see at().)
3323  */
3324  const_reference
3325  operator[] (size_type __pos) const _GLIBCXX_NOEXCEPT
3326  {
3327  _GLIBCXX_DEBUG_ASSERT(__pos <= size());
3328  return _M_data()[__pos];
3329  }
3330 
3331  /**
3332  * @brief Subscript access to the data contained in the %string.
3333  * @param __pos The index of the character to access.
3334  * @return Read/write reference to the character.
3335  *
3336  * This operator allows for easy, array-style, data access.
3337  * Note that data access with this operator is unchecked and
3338  * out_of_range lookups are not defined. (For checked lookups
3339  * see at().) Unshares the string.
3340  */
3341  reference
3342  operator[](size_type __pos)
3343  {
3344  // Allow pos == size() both in C++98 mode, as v3 extension,
3345  // and in C++11 mode.
3346  _GLIBCXX_DEBUG_ASSERT(__pos <= size());
3347  // In pedantic mode be strict in C++98 mode.
3348  _GLIBCXX_DEBUG_PEDASSERT(__cplusplus >= 201103L || __pos < size());
3349  _M_leak();
3350  return _M_data()[__pos];
3351  }
3352 
3353  /**
3354  * @brief Provides access to the data contained in the %string.
3355  * @param __n The index of the character to access.
3356  * @return Read-only (const) reference to the character.
3357  * @throw std::out_of_range If @a n is an invalid index.
3358  *
3359  * This function provides for safer data access. The parameter is
3360  * first checked that it is in the range of the string. The function
3361  * throws out_of_range if the check fails.
3362  */
3363  const_reference
3364  at(size_type __n) const
3365  {
3366  if (__n >= this->size())
3367  __throw_out_of_range_fmt(__N("basic_string::at: __n "
3368  "(which is %zu) >= this->size() "
3369  "(which is %zu)"),
3370  __n, this->size());
3371  return _M_data()[__n];
3372  }
3373 
3374  /**
3375  * @brief Provides access to the data contained in the %string.
3376  * @param __n The index of the character to access.
3377  * @return Read/write reference to the character.
3378  * @throw std::out_of_range If @a n is an invalid index.
3379  *
3380  * This function provides for safer data access. The parameter is
3381  * first checked that it is in the range of the string. The function
3382  * throws out_of_range if the check fails. Success results in
3383  * unsharing the string.
3384  */
3385  reference
3386  at(size_type __n)
3387  {
3388  if (__n >= size())
3389  __throw_out_of_range_fmt(__N("basic_string::at: __n "
3390  "(which is %zu) >= this->size() "
3391  "(which is %zu)"),
3392  __n, this->size());
3393  _M_leak();
3394  return _M_data()[__n];
3395  }
3396 
3397 #if __cplusplus >= 201103L
3398  /**
3399  * Returns a read/write reference to the data at the first
3400  * element of the %string.
3401  */
3402  reference
3404  { return operator[](0); }
3405 
3406  /**
3407  * Returns a read-only (constant) reference to the data at the first
3408  * element of the %string.
3409  */
3410  const_reference
3411  front() const _GLIBCXX_NOEXCEPT
3412  { return operator[](0); }
3413 
3414  /**
3415  * Returns a read/write reference to the data at the last
3416  * element of the %string.
3417  */
3418  reference
3420  { return operator[](this->size() - 1); }
3421 
3422  /**
3423  * Returns a read-only (constant) reference to the data at the
3424  * last element of the %string.
3425  */
3426  const_reference
3427  back() const _GLIBCXX_NOEXCEPT
3428  { return operator[](this->size() - 1); }
3429 #endif
3430 
3431  // Modifiers:
3432  /**
3433  * @brief Append a string to this string.
3434  * @param __str The string to append.
3435  * @return Reference to this string.
3436  */
3437  basic_string&
3438  operator+=(const basic_string& __str)
3439  { return this->append(__str); }
3440 
3441  /**
3442  * @brief Append a C string.
3443  * @param __s The C string to append.
3444  * @return Reference to this string.
3445  */
3446  basic_string&
3447  operator+=(const _CharT* __s)
3448  { return this->append(__s); }
3449 
3450  /**
3451  * @brief Append a character.
3452  * @param __c The character to append.
3453  * @return Reference to this string.
3454  */
3455  basic_string&
3456  operator+=(_CharT __c)
3457  {
3458  this->push_back(__c);
3459  return *this;
3460  }
3461 
3462 #if __cplusplus >= 201103L
3463  /**
3464  * @brief Append an initializer_list of characters.
3465  * @param __l The initializer_list of characters to be appended.
3466  * @return Reference to this string.
3467  */
3468  basic_string&
3470  { return this->append(__l.begin(), __l.size()); }
3471 #endif // C++11
3472 
3473  /**
3474  * @brief Append a string to this string.
3475  * @param __str The string to append.
3476  * @return Reference to this string.
3477  */
3478  basic_string&
3479  append(const basic_string& __str);
3480 
3481  /**
3482  * @brief Append a substring.
3483  * @param __str The string to append.
3484  * @param __pos Index of the first character of str to append.
3485  * @param __n The number of characters to append.
3486  * @return Reference to this string.
3487  * @throw std::out_of_range if @a __pos is not a valid index.
3488  *
3489  * This function appends @a __n characters from @a __str
3490  * starting at @a __pos to this string. If @a __n is is larger
3491  * than the number of available characters in @a __str, the
3492  * remainder of @a __str is appended.
3493  */
3494  basic_string&
3495  append(const basic_string& __str, size_type __pos, size_type __n);
3496 
3497  /**
3498  * @brief Append a C substring.
3499  * @param __s The C string to append.
3500  * @param __n The number of characters to append.
3501  * @return Reference to this string.
3502  */
3503  basic_string&
3504  append(const _CharT* __s, size_type __n);
3505 
3506  /**
3507  * @brief Append a C string.
3508  * @param __s The C string to append.
3509  * @return Reference to this string.
3510  */
3511  basic_string&
3512  append(const _CharT* __s)
3513  {
3514  __glibcxx_requires_string(__s);
3515  return this->append(__s, traits_type::length(__s));
3516  }
3517 
3518  /**
3519  * @brief Append multiple characters.
3520  * @param __n The number of characters to append.
3521  * @param __c The character to use.
3522  * @return Reference to this string.
3523  *
3524  * Appends __n copies of __c to this string.
3525  */
3526  basic_string&
3527  append(size_type __n, _CharT __c);
3528 
3529 #if __cplusplus >= 201103L
3530  /**
3531  * @brief Append an initializer_list of characters.
3532  * @param __l The initializer_list of characters to append.
3533  * @return Reference to this string.
3534  */
3535  basic_string&
3537  { return this->append(__l.begin(), __l.size()); }
3538 #endif // C++11
3539 
3540  /**
3541  * @brief Append a range of characters.
3542  * @param __first Iterator referencing the first character to append.
3543  * @param __last Iterator marking the end of the range.
3544  * @return Reference to this string.
3545  *
3546  * Appends characters in the range [__first,__last) to this string.
3547  */
3548  template<class _InputIterator>
3549  basic_string&
3550  append(_InputIterator __first, _InputIterator __last)
3551  { return this->replace(_M_iend(), _M_iend(), __first, __last); }
3552 
3553  /**
3554  * @brief Append a single character.
3555  * @param __c Character to append.
3556  */
3557  void
3558  push_back(_CharT __c)
3559  {
3560  const size_type __len = 1 + this->size();
3561  if (__len > this->capacity() || _M_rep()->_M_is_shared())
3562  this->reserve(__len);
3563  traits_type::assign(_M_data()[this->size()], __c);
3564  _M_rep()->_M_set_length_and_sharable(__len);
3565  }
3566 
3567  /**
3568  * @brief Set value to contents of another string.
3569  * @param __str Source string to use.
3570  * @return Reference to this string.
3571  */
3572  basic_string&
3573  assign(const basic_string& __str);
3574 
3575 #if __cplusplus >= 201103L
3576  /**
3577  * @brief Set value to contents of another string.
3578  * @param __str Source string to use.
3579  * @return Reference to this string.
3580  *
3581  * This function sets this string to the exact contents of @a __str.
3582  * @a __str is a valid, but unspecified string.
3583  */
3584  // PR 58265, this should be noexcept.
3585  basic_string&
3587  {
3588  this->swap(__str);
3589  return *this;
3590  }
3591 #endif // C++11
3592 
3593  /**
3594  * @brief Set value to a substring of a string.
3595  * @param __str The string to use.
3596  * @param __pos Index of the first character of str.
3597  * @param __n Number of characters to use.
3598  * @return Reference to this string.
3599  * @throw std::out_of_range if @a pos is not a valid index.
3600  *
3601  * This function sets this string to the substring of @a __str
3602  * consisting of @a __n characters at @a __pos. If @a __n is
3603  * is larger than the number of available characters in @a
3604  * __str, the remainder of @a __str is used.
3605  */
3606  basic_string&
3607  assign(const basic_string& __str, size_type __pos, size_type __n)
3608  { return this->assign(__str._M_data()
3609  + __str._M_check(__pos, "basic_string::assign"),
3610  __str._M_limit(__pos, __n)); }
3611 
3612  /**
3613  * @brief Set value to a C substring.
3614  * @param __s The C string to use.
3615  * @param __n Number of characters to use.
3616  * @return Reference to this string.
3617  *
3618  * This function sets the value of this string to the first @a __n
3619  * characters of @a __s. If @a __n is is larger than the number of
3620  * available characters in @a __s, the remainder of @a __s is used.
3621  */
3622  basic_string&
3623  assign(const _CharT* __s, size_type __n);
3624 
3625  /**
3626  * @brief Set value to contents of a C string.
3627  * @param __s The C string to use.
3628  * @return Reference to this string.
3629  *
3630  * This function sets the value of this string to the value of @a __s.
3631  * The data is copied, so there is no dependence on @a __s once the
3632  * function returns.
3633  */
3634  basic_string&
3635  assign(const _CharT* __s)
3636  {
3637  __glibcxx_requires_string(__s);
3638  return this->assign(__s, traits_type::length(__s));
3639  }
3640 
3641  /**
3642  * @brief Set value to multiple characters.
3643  * @param __n Length of the resulting string.
3644  * @param __c The character to use.
3645  * @return Reference to this string.
3646  *
3647  * This function sets the value of this string to @a __n copies of
3648  * character @a __c.
3649  */
3650  basic_string&
3651  assign(size_type __n, _CharT __c)
3652  { return _M_replace_aux(size_type(0), this->size(), __n, __c); }
3653 
3654  /**
3655  * @brief Set value to a range of characters.
3656  * @param __first Iterator referencing the first character to append.
3657  * @param __last Iterator marking the end of the range.
3658  * @return Reference to this string.
3659  *
3660  * Sets value of string to characters in the range [__first,__last).
3661  */
3662  template<class _InputIterator>
3663  basic_string&
3664  assign(_InputIterator __first, _InputIterator __last)
3665  { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
3666 
3667 #if __cplusplus >= 201103L
3668  /**
3669  * @brief Set value to an initializer_list of characters.
3670  * @param __l The initializer_list of characters to assign.
3671  * @return Reference to this string.
3672  */
3673  basic_string&
3675  { return this->assign(__l.begin(), __l.size()); }
3676 #endif // C++11
3677 
3678  /**
3679  * @brief Insert multiple characters.
3680  * @param __p Iterator referencing location in string to insert at.
3681  * @param __n Number of characters to insert
3682  * @param __c The character to insert.
3683  * @throw std::length_error If new length exceeds @c max_size().
3684  *
3685  * Inserts @a __n copies of character @a __c starting at the
3686  * position referenced by iterator @a __p. If adding
3687  * characters causes the length to exceed max_size(),
3688  * length_error is thrown. The value of the string doesn't
3689  * change if an error is thrown.
3690  */
3691  void
3692  insert(iterator __p, size_type __n, _CharT __c)
3693  { this->replace(__p, __p, __n, __c); }
3694 
3695  /**
3696  * @brief Insert a range of characters.
3697  * @param __p Iterator referencing location in string to insert at.
3698  * @param __beg Start of range.
3699  * @param __end End of range.
3700  * @throw std::length_error If new length exceeds @c max_size().
3701  *
3702  * Inserts characters in range [__beg,__end). If adding
3703  * characters causes the length to exceed max_size(),
3704  * length_error is thrown. The value of the string doesn't
3705  * change if an error is thrown.
3706  */
3707  template<class _InputIterator>
3708  void
3709  insert(iterator __p, _InputIterator __beg, _InputIterator __end)
3710  { this->replace(__p, __p, __beg, __end); }
3711 
3712 #if __cplusplus >= 201103L
3713  /**
3714  * @brief Insert an initializer_list of characters.
3715  * @param __p Iterator referencing location in string to insert at.
3716  * @param __l The initializer_list of characters to insert.
3717  * @throw std::length_error If new length exceeds @c max_size().
3718  */
3719  void
3721  {
3722  _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
3723  this->insert(__p - _M_ibegin(), __l.begin(), __l.size());
3724  }
3725 #endif // C++11
3726 
3727  /**
3728  * @brief Insert value of a string.
3729  * @param __pos1 Iterator referencing location in string to insert at.
3730  * @param __str The string to insert.
3731  * @return Reference to this string.
3732  * @throw std::length_error If new length exceeds @c max_size().
3733  *
3734  * Inserts value of @a __str starting at @a __pos1. If adding
3735  * characters causes the length to exceed max_size(),
3736  * length_error is thrown. The value of the string doesn't
3737  * change if an error is thrown.
3738  */
3739  basic_string&
3740  insert(size_type __pos1, const basic_string& __str)
3741  { return this->insert(__pos1, __str, size_type(0), __str.size()); }
3742 
3743  /**
3744  * @brief Insert a substring.
3745  * @param __pos1 Iterator referencing location in string to insert at.
3746  * @param __str The string to insert.
3747  * @param __pos2 Start of characters in str to insert.
3748  * @param __n Number of characters to insert.
3749  * @return Reference to this string.
3750  * @throw std::length_error If new length exceeds @c max_size().
3751  * @throw std::out_of_range If @a pos1 > size() or
3752  * @a __pos2 > @a str.size().
3753  *
3754  * Starting at @a pos1, insert @a __n character of @a __str
3755  * beginning with @a __pos2. If adding characters causes the
3756  * length to exceed max_size(), length_error is thrown. If @a
3757  * __pos1 is beyond the end of this string or @a __pos2 is
3758  * beyond the end of @a __str, out_of_range is thrown. The
3759  * value of the string doesn't change if an error is thrown.
3760  */
3761  basic_string&
3762  insert(size_type __pos1, const basic_string& __str,
3763  size_type __pos2, size_type __n)
3764  { return this->insert(__pos1, __str._M_data()
3765  + __str._M_check(__pos2, "basic_string::insert"),
3766  __str._M_limit(__pos2, __n)); }
3767 
3768  /**
3769  * @brief Insert a C substring.
3770  * @param __pos Iterator referencing location in string to insert at.
3771  * @param __s The C string to insert.
3772  * @param __n The number of characters to insert.
3773  * @return Reference to this string.
3774  * @throw std::length_error If new length exceeds @c max_size().
3775  * @throw std::out_of_range If @a __pos is beyond the end of this
3776  * string.
3777  *
3778  * Inserts the first @a __n characters of @a __s starting at @a
3779  * __pos. If adding characters causes the length to exceed
3780  * max_size(), length_error is thrown. If @a __pos is beyond
3781  * end(), out_of_range is thrown. The value of the string
3782  * doesn't change if an error is thrown.
3783  */
3784  basic_string&
3785  insert(size_type __pos, const _CharT* __s, size_type __n);
3786 
3787  /**
3788  * @brief Insert a C string.
3789  * @param __pos Iterator referencing location in string to insert at.
3790  * @param __s The C string to insert.
3791  * @return Reference to this string.
3792  * @throw std::length_error If new length exceeds @c max_size().
3793  * @throw std::out_of_range If @a pos is beyond the end of this
3794  * string.
3795  *
3796  * Inserts the first @a n characters of @a __s starting at @a __pos. If
3797  * adding characters causes the length to exceed max_size(),
3798  * length_error is thrown. If @a __pos is beyond end(), out_of_range is
3799  * thrown. The value of the string doesn't change if an error is
3800  * thrown.
3801  */
3802  basic_string&
3803  insert(size_type __pos, const _CharT* __s)
3804  {
3805  __glibcxx_requires_string(__s);
3806  return this->insert(__pos, __s, traits_type::length(__s));
3807  }
3808 
3809  /**
3810  * @brief Insert multiple characters.
3811  * @param __pos Index in string to insert at.
3812  * @param __n Number of characters to insert
3813  * @param __c The character to insert.
3814  * @return Reference to this string.
3815  * @throw std::length_error If new length exceeds @c max_size().
3816  * @throw std::out_of_range If @a __pos is beyond the end of this
3817  * string.
3818  *
3819  * Inserts @a __n copies of character @a __c starting at index
3820  * @a __pos. If adding characters causes the length to exceed
3821  * max_size(), length_error is thrown. If @a __pos > length(),
3822  * out_of_range is thrown. The value of the string doesn't
3823  * change if an error is thrown.
3824  */
3825  basic_string&
3826  insert(size_type __pos, size_type __n, _CharT __c)
3827  { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
3828  size_type(0), __n, __c); }
3829 
3830  /**
3831  * @brief Insert one character.
3832  * @param __p Iterator referencing position in string to insert at.
3833  * @param __c The character to insert.
3834  * @return Iterator referencing newly inserted char.
3835  * @throw std::length_error If new length exceeds @c max_size().
3836  *
3837  * Inserts character @a __c at position referenced by @a __p.
3838  * If adding character causes the length to exceed max_size(),
3839  * length_error is thrown. If @a __p is beyond end of string,
3840  * out_of_range is thrown. The value of the string doesn't
3841  * change if an error is thrown.
3842  */
3843  iterator
3844  insert(iterator __p, _CharT __c)
3845  {
3846  _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
3847  const size_type __pos = __p - _M_ibegin();
3848  _M_replace_aux(__pos, size_type(0), size_type(1), __c);
3849  _M_rep()->_M_set_leaked();
3850  return iterator(_M_data() + __pos);
3851  }
3852 
3853  /**
3854  * @brief Remove characters.
3855  * @param __pos Index of first character to remove (default 0).
3856  * @param __n Number of characters to remove (default remainder).
3857  * @return Reference to this string.
3858  * @throw std::out_of_range If @a pos is beyond the end of this
3859  * string.
3860  *
3861  * Removes @a __n characters from this string starting at @a
3862  * __pos. The length of the string is reduced by @a __n. If
3863  * there are < @a __n characters to remove, the remainder of
3864  * the string is truncated. If @a __p is beyond end of string,
3865  * out_of_range is thrown. The value of the string doesn't
3866  * change if an error is thrown.
3867  */
3868  basic_string&
3869  erase(size_type __pos = 0, size_type __n = npos)
3870  {
3871  _M_mutate(_M_check(__pos, "basic_string::erase"),
3872  _M_limit(__pos, __n), size_type(0));
3873  return *this;
3874  }
3875 
3876  /**
3877  * @brief Remove one character.
3878  * @param __position Iterator referencing the character to remove.
3879  * @return iterator referencing same location after removal.
3880  *
3881  * Removes the character at @a __position from this string. The value
3882  * of the string doesn't change if an error is thrown.
3883  */
3884  iterator
3885  erase(iterator __position)
3886  {
3887  _GLIBCXX_DEBUG_PEDASSERT(__position >= _M_ibegin()
3888  && __position < _M_iend());
3889  const size_type __pos = __position - _M_ibegin();
3890  _M_mutate(__pos, size_type(1), size_type(0));
3891  _M_rep()->_M_set_leaked();
3892  return iterator(_M_data() + __pos);
3893  }
3894 
3895  /**
3896  * @brief Remove a range of characters.
3897  * @param __first Iterator referencing the first character to remove.
3898  * @param __last Iterator referencing the end of the range.
3899  * @return Iterator referencing location of first after removal.
3900  *
3901  * Removes the characters in the range [first,last) from this string.
3902  * The value of the string doesn't change if an error is thrown.
3903  */
3904  iterator
3905  erase(iterator __first, iterator __last);
3906 
3907 #if __cplusplus >= 201103L
3908  /**
3909  * @brief Remove the last character.
3910  *
3911  * The string must be non-empty.
3912  */
3913  void
3914  pop_back() // FIXME C++11: should be noexcept.
3915  { erase(size()-1, 1); }
3916 #endif // C++11
3917 
3918  /**
3919  * @brief Replace characters with value from another string.
3920  * @param __pos Index of first character to replace.
3921  * @param __n Number of characters to be replaced.
3922  * @param __str String to insert.
3923  * @return Reference to this string.
3924  * @throw std::out_of_range If @a pos is beyond the end of this
3925  * string.
3926  * @throw std::length_error If new length exceeds @c max_size().
3927  *
3928  * Removes the characters in the range [__pos,__pos+__n) from
3929  * this string. In place, the value of @a __str is inserted.
3930  * If @a __pos is beyond end of string, out_of_range is thrown.
3931  * If the length of the result exceeds max_size(), length_error
3932  * is thrown. The value of the string doesn't change if an
3933  * error is thrown.
3934  */
3935  basic_string&
3936  replace(size_type __pos, size_type __n, const basic_string& __str)
3937  { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
3938 
3939  /**
3940  * @brief Replace characters with value from another string.
3941  * @param __pos1 Index of first character to replace.
3942  * @param __n1 Number of characters to be replaced.
3943  * @param __str String to insert.
3944  * @param __pos2 Index of first character of str to use.
3945  * @param __n2 Number of characters from str to use.
3946  * @return Reference to this string.
3947  * @throw std::out_of_range If @a __pos1 > size() or @a __pos2 >
3948  * __str.size().
3949  * @throw std::length_error If new length exceeds @c max_size().
3950  *
3951  * Removes the characters in the range [__pos1,__pos1 + n) from this
3952  * string. In place, the value of @a __str is inserted. If @a __pos is
3953  * beyond end of string, out_of_range is thrown. If the length of the
3954  * result exceeds max_size(), length_error is thrown. The value of the
3955  * string doesn't change if an error is thrown.
3956  */
3957  basic_string&
3958  replace(size_type __pos1, size_type __n1, const basic_string& __str,
3959  size_type __pos2, size_type __n2)
3960  { return this->replace(__pos1, __n1, __str._M_data()
3961  + __str._M_check(__pos2, "basic_string::replace"),
3962  __str._M_limit(__pos2, __n2)); }
3963 
3964  /**
3965  * @brief Replace characters with value of a C substring.
3966  * @param __pos Index of first character to replace.
3967  * @param __n1 Number of characters to be replaced.
3968  * @param __s C string to insert.
3969  * @param __n2 Number of characters from @a s to use.
3970  * @return Reference to this string.
3971  * @throw std::out_of_range If @a pos1 > size().
3972  * @throw std::length_error If new length exceeds @c max_size().
3973  *
3974  * Removes the characters in the range [__pos,__pos + __n1)
3975  * from this string. In place, the first @a __n2 characters of
3976  * @a __s are inserted, or all of @a __s if @a __n2 is too large. If
3977  * @a __pos is beyond end of string, out_of_range is thrown. If
3978  * the length of result exceeds max_size(), length_error is
3979  * thrown. The value of the string doesn't change if an error
3980  * is thrown.
3981  */
3982  basic_string&
3983  replace(size_type __pos, size_type __n1, const _CharT* __s,
3984  size_type __n2);
3985 
3986  /**
3987  * @brief Replace characters with value of a C string.
3988  * @param __pos Index of first character to replace.
3989  * @param __n1 Number of characters to be replaced.
3990  * @param __s C string to insert.
3991  * @return Reference to this string.
3992  * @throw std::out_of_range If @a pos > size().
3993  * @throw std::length_error If new length exceeds @c max_size().
3994  *
3995  * Removes the characters in the range [__pos,__pos + __n1)
3996  * from this string. In place, the characters of @a __s are
3997  * inserted. If @a __pos is beyond end of string, out_of_range
3998  * is thrown. If the length of result exceeds max_size(),
3999  * length_error is thrown. The value of the string doesn't
4000  * change if an error is thrown.
4001  */
4002  basic_string&
4003  replace(size_type __pos, size_type __n1, const _CharT* __s)
4004  {
4005  __glibcxx_requires_string(__s);
4006  return this->replace(__pos, __n1, __s, traits_type::length(__s));
4007  }
4008 
4009  /**
4010  * @brief Replace characters with multiple characters.
4011  * @param __pos Index of first character to replace.
4012  * @param __n1 Number of characters to be replaced.
4013  * @param __n2 Number of characters to insert.
4014  * @param __c Character to insert.
4015  * @return Reference to this string.
4016  * @throw std::out_of_range If @a __pos > size().
4017  * @throw std::length_error If new length exceeds @c max_size().
4018  *
4019  * Removes the characters in the range [pos,pos + n1) from this
4020  * string. In place, @a __n2 copies of @a __c are inserted.
4021  * If @a __pos is beyond end of string, out_of_range is thrown.
4022  * If the length of result exceeds max_size(), length_error is
4023  * thrown. The value of the string doesn't change if an error
4024  * is thrown.
4025  */
4026  basic_string&
4027  replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
4028  { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
4029  _M_limit(__pos, __n1), __n2, __c); }
4030 
4031  /**
4032  * @brief Replace range of characters with string.
4033  * @param __i1 Iterator referencing start of range to replace.
4034  * @param __i2 Iterator referencing end of range to replace.
4035  * @param __str String value to insert.
4036  * @return Reference to this string.
4037  * @throw std::length_error If new length exceeds @c max_size().
4038  *
4039  * Removes the characters in the range [__i1,__i2). In place,
4040  * the value of @a __str is inserted. If the length of result
4041  * exceeds max_size(), length_error is thrown. The value of
4042  * the string doesn't change if an error is thrown.
4043  */
4044  basic_string&
4045  replace(iterator __i1, iterator __i2, const basic_string& __str)
4046  { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
4047 
4048  /**
4049  * @brief Replace range of characters with C substring.
4050  * @param __i1 Iterator referencing start of range to replace.
4051  * @param __i2 Iterator referencing end of range to replace.
4052  * @param __s C string value to insert.
4053  * @param __n Number of characters from s to insert.
4054  * @return Reference to this string.
4055  * @throw std::length_error If new length exceeds @c max_size().
4056  *
4057  * Removes the characters in the range [__i1,__i2). In place,
4058  * the first @a __n characters of @a __s are inserted. If the
4059  * length of result exceeds max_size(), length_error is thrown.
4060  * The value of the string doesn't change if an error is
4061  * thrown.
4062  */
4063  basic_string&
4064  replace(iterator __i1, iterator __i2, const _CharT* __s, size_type __n)
4065  {
4066  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4067  && __i2 <= _M_iend());
4068  return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n);
4069  }
4070 
4071  /**
4072  * @brief Replace range of characters with C string.
4073  * @param __i1 Iterator referencing start of range to replace.
4074  * @param __i2 Iterator referencing end of range to replace.
4075  * @param __s C string value to insert.
4076  * @return Reference to this string.
4077  * @throw std::length_error If new length exceeds @c max_size().
4078  *
4079  * Removes the characters in the range [__i1,__i2). In place,
4080  * the characters of @a __s are inserted. If the length of
4081  * result exceeds max_size(), length_error is thrown. The
4082  * value of the string doesn't change if an error is thrown.
4083  */
4084  basic_string&
4085  replace(iterator __i1, iterator __i2, const _CharT* __s)
4086  {
4087  __glibcxx_requires_string(__s);
4088  return this->replace(__i1, __i2, __s, traits_type::length(__s));
4089  }
4090 
4091  /**
4092  * @brief Replace range of characters with multiple characters
4093  * @param __i1 Iterator referencing start of range to replace.
4094  * @param __i2 Iterator referencing end of range to replace.
4095  * @param __n Number of characters to insert.
4096  * @param __c Character to insert.
4097  * @return Reference to this string.
4098  * @throw std::length_error If new length exceeds @c max_size().
4099  *
4100  * Removes the characters in the range [__i1,__i2). In place,
4101  * @a __n copies of @a __c are inserted. If the length of
4102  * result exceeds max_size(), length_error is thrown. The
4103  * value of the string doesn't change if an error is thrown.
4104  */
4105  basic_string&
4106  replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
4107  {
4108  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4109  && __i2 <= _M_iend());
4110  return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __c);
4111  }
4112 
4113  /**
4114  * @brief Replace range of characters with range.
4115  * @param __i1 Iterator referencing start of range to replace.
4116  * @param __i2 Iterator referencing end of range to replace.
4117  * @param __k1 Iterator referencing start of range to insert.
4118  * @param __k2 Iterator referencing end of range to insert.
4119  * @return Reference to this string.
4120  * @throw std::length_error If new length exceeds @c max_size().
4121  *
4122  * Removes the characters in the range [__i1,__i2). In place,
4123  * characters in the range [__k1,__k2) are inserted. If the
4124  * length of result exceeds max_size(), length_error is thrown.
4125  * The value of the string doesn't change if an error is
4126  * thrown.
4127  */
4128  template<class _InputIterator>
4129  basic_string&
4130  replace(iterator __i1, iterator __i2,
4131  _InputIterator __k1, _InputIterator __k2)
4132  {
4133  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4134  && __i2 <= _M_iend());
4135  __glibcxx_requires_valid_range(__k1, __k2);
4136  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
4137  return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
4138  }
4139 
4140  // Specializations for the common case of pointer and iterator:
4141  // useful to avoid the overhead of temporary buffering in _M_replace.
4142  basic_string&
4143  replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
4144  {
4145  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4146  && __i2 <= _M_iend());
4147  __glibcxx_requires_valid_range(__k1, __k2);
4148  return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4149  __k1, __k2 - __k1);
4150  }
4151 
4152  basic_string&
4153  replace(iterator __i1, iterator __i2,
4154  const _CharT* __k1, const _CharT* __k2)
4155  {
4156  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4157  && __i2 <= _M_iend());
4158  __glibcxx_requires_valid_range(__k1, __k2);
4159  return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4160  __k1, __k2 - __k1);
4161  }
4162 
4163  basic_string&
4164  replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
4165  {
4166  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4167  && __i2 <= _M_iend());
4168  __glibcxx_requires_valid_range(__k1, __k2);
4169  return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4170  __k1.base(), __k2 - __k1);
4171  }
4172 
4173  basic_string&
4174  replace(iterator __i1, iterator __i2,
4175  const_iterator __k1, const_iterator __k2)
4176  {
4177  _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4178  && __i2 <= _M_iend());
4179  __glibcxx_requires_valid_range(__k1, __k2);
4180  return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4181  __k1.base(), __k2 - __k1);
4182  }
4183 
4184 #if __cplusplus >= 201103L
4185  /**
4186  * @brief Replace range of characters with initializer_list.
4187  * @param __i1 Iterator referencing start of range to replace.
4188  * @param __i2 Iterator referencing end of range to replace.
4189  * @param __l The initializer_list of characters to insert.
4190  * @return Reference to this string.
4191  * @throw std::length_error If new length exceeds @c max_size().
4192  *
4193  * Removes the characters in the range [__i1,__i2). In place,
4194  * characters in the range [__k1,__k2) are inserted. If the
4195  * length of result exceeds max_size(), length_error is thrown.
4196  * The value of the string doesn't change if an error is
4197  * thrown.
4198  */
4199  basic_string& replace(iterator __i1, iterator __i2,
4201  { return this->replace(__i1, __i2, __l.begin(), __l.end()); }
4202 #endif // C++11
4203 
4204  private:
4205  template<class _Integer>
4206  basic_string&
4207  _M_replace_dispatch(iterator __i1, iterator __i2, _Integer __n,
4208  _Integer __val, __true_type)
4209  { return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __val); }
4210 
4211  template<class _InputIterator>
4212  basic_string&
4213  _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
4214  _InputIterator __k2, __false_type);
4215 
4216  basic_string&
4217  _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
4218  _CharT __c);
4219 
4220  basic_string&
4221  _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
4222  size_type __n2);
4223 
4224  // _S_construct_aux is used to implement the 21.3.1 para 15 which
4225  // requires special behaviour if _InIter is an integral type
4226  template<class _InIterator>
4227  static _CharT*
4228  _S_construct_aux(_InIterator __beg, _InIterator __end,
4229  const _Alloc& __a, __false_type)
4230  {
4231  typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
4232  return _S_construct(__beg, __end, __a, _Tag());
4233  }
4234 
4235  // _GLIBCXX_RESOLVE_LIB_DEFECTS
4236  // 438. Ambiguity in the "do the right thing" clause
4237  template<class _Integer>
4238  static _CharT*
4239  _S_construct_aux(_Integer __beg, _Integer __end,
4240  const _Alloc& __a, __true_type)
4241  { return _S_construct_aux_2(static_cast<size_type>(__beg),
4242  __end, __a); }
4243 
4244  static _CharT*
4245  _S_construct_aux_2(size_type __req, _CharT __c, const _Alloc& __a)
4246  { return _S_construct(__req, __c, __a); }
4247 
4248  template<class _InIterator>
4249  static _CharT*
4250  _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
4251  {
4252  typedef typename std::__is_integer<_InIterator>::__type _Integral;
4253  return _S_construct_aux(__beg, __end, __a, _Integral());
4254  }
4255 
4256  // For Input Iterators, used in istreambuf_iterators, etc.
4257  template<class _InIterator>
4258  static _CharT*
4259  _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
4260  input_iterator_tag);
4261 
4262  // For forward_iterators up to random_access_iterators, used for
4263  // string::iterator, _CharT*, etc.
4264  template<class _FwdIterator>
4265  static _CharT*
4266  _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
4267  forward_iterator_tag);
4268 
4269  static _CharT*
4270  _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
4271 
4272  public:
4273 
4274  /**
4275  * @brief Copy substring into C string.
4276  * @param __s C string to copy value into.
4277  * @param __n Number of characters to copy.
4278  * @param __pos Index of first character to copy.
4279  * @return Number of characters actually copied
4280  * @throw std::out_of_range If __pos > size().
4281  *
4282  * Copies up to @a __n characters starting at @a __pos into the
4283  * C string @a __s. If @a __pos is %greater than size(),
4284  * out_of_range is thrown.
4285  */
4286  size_type
4287  copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
4288 
4289  /**
4290  * @brief Swap contents with another string.
4291  * @param __s String to swap with.
4292  *
4293  * Exchanges the contents of this string with that of @a __s in constant
4294  * time.
4295  */
4296  // PR 58265, this should be noexcept.
4297  void
4298  swap(basic_string& __s);
4299 
4300  // String operations:
4301  /**
4302  * @brief Return const pointer to null-terminated contents.
4303  *
4304  * This is a handle to internal data. Do not modify or dire things may
4305  * happen.
4306  */
4307  const _CharT*
4308  c_str() const _GLIBCXX_NOEXCEPT
4309  { return _M_data(); }
4310 
4311  /**
4312  * @brief Return const pointer to contents.
4313  *
4314  * This is a handle to internal data. Do not modify or dire things may
4315  * happen.
4316  */
4317  const _CharT*
4318  data() const _GLIBCXX_NOEXCEPT
4319  { return _M_data(); }
4320 
4321  /**
4322  * @brief Return copy of allocator used to construct this string.
4323  */
4324  allocator_type
4325  get_allocator() const _GLIBCXX_NOEXCEPT
4326  { return _M_dataplus; }
4327 
4328  /**
4329  * @brief Find position of a C substring.
4330  * @param __s C string to locate.
4331  * @param __pos Index of character to search from.
4332  * @param __n Number of characters from @a s to search for.
4333  * @return Index of start of first occurrence.
4334  *
4335  * Starting from @a __pos, searches forward for the first @a
4336  * __n characters in @a __s within this string. If found,
4337  * returns the index where it begins. If not found, returns
4338  * npos.
4339  */
4340  size_type
4341  find(const _CharT* __s, size_type __pos, size_type __n) const;
4342 
4343  /**
4344  * @brief Find position of a string.
4345  * @param __str String to locate.
4346  * @param __pos Index of character to search from (default 0).
4347  * @return Index of start of first occurrence.
4348  *
4349  * Starting from @a __pos, searches forward for value of @a __str within
4350  * this string. If found, returns the index where it begins. If not
4351  * found, returns npos.
4352  */
4353  size_type
4354  find(const basic_string& __str, size_type __pos = 0) const
4355  _GLIBCXX_NOEXCEPT
4356  { return this->find(__str.data(), __pos, __str.size()); }
4357 
4358  /**
4359  * @brief Find position of a C string.
4360  * @param __s C string to locate.
4361  * @param __pos Index of character to search from (default 0).
4362  * @return Index of start of first occurrence.
4363  *
4364  * Starting from @a __pos, searches forward for the value of @a
4365  * __s within this string. If found, returns the index where
4366  * it begins. If not found, returns npos.
4367  */
4368  size_type
4369  find(const _CharT* __s, size_type __pos = 0) const
4370  {
4371  __glibcxx_requires_string(__s);
4372  return this->find(__s, __pos, traits_type::length(__s));
4373  }
4374 
4375  /**
4376  * @brief Find position of a character.
4377  * @param __c Character to locate.
4378  * @param __pos Index of character to search from (default 0).
4379  * @return Index of first occurrence.
4380  *
4381  * Starting from @a __pos, searches forward for @a __c within
4382  * this string. If found, returns the index where it was
4383  * found. If not found, returns npos.
4384  */
4385  size_type
4386  find(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT;
4387 
4388  /**
4389  * @brief Find last position of a string.
4390  * @param __str String to locate.
4391  * @param __pos Index of character to search back from (default end).
4392  * @return Index of start of last occurrence.
4393  *
4394  * Starting from @a __pos, searches backward for value of @a
4395  * __str within this string. If found, returns the index where
4396  * it begins. If not found, returns npos.
4397  */
4398  size_type
4399  rfind(const basic_string& __str, size_type __pos = npos) const
4400  _GLIBCXX_NOEXCEPT
4401  { return this->rfind(__str.data(), __pos, __str.size()); }
4402 
4403  /**
4404  * @brief Find last position of a C substring.
4405  * @param __s C string to locate.
4406  * @param __pos Index of character to search back from.
4407  * @param __n Number of characters from s to search for.
4408  * @return Index of start of last occurrence.
4409  *
4410  * Starting from @a __pos, searches backward for the first @a
4411  * __n characters in @a __s within this string. If found,
4412  * returns the index where it begins. If not found, returns
4413  * npos.
4414  */
4415  size_type
4416  rfind(const _CharT* __s, size_type __pos, size_type __n) const;
4417 
4418  /**
4419  * @brief Find last position of a C string.
4420  * @param __s C string to locate.
4421  * @param __pos Index of character to start search at (default end).
4422  * @return Index of start of last occurrence.
4423  *
4424  * Starting from @a __pos, searches backward for the value of
4425  * @a __s within this string. If found, returns the index
4426  * where it begins. If not found, returns npos.
4427  */
4428  size_type
4429  rfind(const _CharT* __s, size_type __pos = npos) const
4430  {
4431  __glibcxx_requires_string(__s);
4432  return this->rfind(__s, __pos, traits_type::length(__s));
4433  }
4434 
4435  /**
4436  * @brief Find last position of a character.
4437  * @param __c Character to locate.
4438  * @param __pos Index of character to search back from (default end).
4439  * @return Index of last occurrence.
4440  *
4441  * Starting from @a __pos, searches backward for @a __c within
4442  * this string. If found, returns the index where it was
4443  * found. If not found, returns npos.
4444  */
4445  size_type
4446  rfind(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT;
4447 
4448  /**
4449  * @brief Find position of a character of string.
4450  * @param __str String containing characters to locate.
4451  * @param __pos Index of character to search from (default 0).
4452  * @return Index of first occurrence.
4453  *
4454  * Starting from @a __pos, searches forward for one of the
4455  * characters of @a __str within this string. If found,
4456  * returns the index where it was found. If not found, returns
4457  * npos.
4458  */
4459  size_type
4460  find_first_of(const basic_string& __str, size_type __pos = 0) const
4461  _GLIBCXX_NOEXCEPT
4462  { return this->find_first_of(__str.data(), __pos, __str.size()); }
4463 
4464  /**
4465  * @brief Find position of a character of C substring.
4466  * @param __s String containing characters to locate.
4467  * @param __pos Index of character to search from.
4468  * @param __n Number of characters from s to search for.
4469  * @return Index of first occurrence.
4470  *
4471  * Starting from @a __pos, searches forward for one of the
4472  * first @a __n characters of @a __s within this string. If
4473  * found, returns the index where it was found. If not found,
4474  * returns npos.
4475  */
4476  size_type
4477  find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
4478 
4479  /**
4480  * @brief Find position of a character of C string.
4481  * @param __s String containing characters to locate.
4482  * @param __pos Index of character to search from (default 0).
4483  * @return Index of first occurrence.
4484  *
4485  * Starting from @a __pos, searches forward for one of the
4486  * characters of @a __s within this string. If found, returns
4487  * the index where it was found. If not found, returns npos.
4488  */
4489  size_type
4490  find_first_of(const _CharT* __s, size_type __pos = 0) const
4491  {
4492  __glibcxx_requires_string(__s);
4493  return this->find_first_of(__s, __pos, traits_type::length(__s));
4494  }
4495 
4496  /**
4497  * @brief Find position of a character.
4498  * @param __c Character to locate.
4499  * @param __pos Index of character to search from (default 0).
4500  * @return Index of first occurrence.
4501  *
4502  * Starting from @a __pos, searches forward for the character
4503  * @a __c within this string. If found, returns the index
4504  * where it was found. If not found, returns npos.
4505  *
4506  * Note: equivalent to find(__c, __pos).
4507  */
4508  size_type
4509  find_first_of(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT
4510  { return this->find(__c, __pos); }
4511 
4512  /**
4513  * @brief Find last position of a character of string.
4514  * @param __str String containing characters to locate.
4515  * @param __pos Index of character to search back from (default end).
4516  * @return Index of last occurrence.
4517  *
4518  * Starting from @a __pos, searches backward for one of the
4519  * characters of @a __str within this string. If found,
4520  * returns the index where it was found. If not found, returns
4521  * npos.
4522  */
4523  size_type
4524  find_last_of(const basic_string& __str, size_type __pos = npos) const
4525  _GLIBCXX_NOEXCEPT
4526  { return this->find_last_of(__str.data(), __pos, __str.size()); }
4527 
4528  /**
4529  * @brief Find last position of a character of C substring.
4530  * @param __s C string containing characters to locate.
4531  * @param __pos Index of character to search back from.
4532  * @param __n Number of characters from s to search for.
4533  * @return Index of last occurrence.
4534  *
4535  * Starting from @a __pos, searches backward for one of the
4536  * first @a __n characters of @a __s within this string. If
4537  * found, returns the index where it was found. If not found,
4538  * returns npos.
4539  */
4540  size_type
4541  find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
4542 
4543  /**
4544  * @brief Find last position of a character of C string.
4545  * @param __s C string containing characters to locate.
4546  * @param __pos Index of character to search back from (default end).
4547  * @return Index of last occurrence.
4548  *
4549  * Starting from @a __pos, searches backward for one of the
4550  * characters of @a __s within this string. If found, returns
4551  * the index where it was found. If not found, returns npos.
4552  */
4553  size_type
4554  find_last_of(const _CharT* __s, size_type __pos = npos) const
4555  {
4556  __glibcxx_requires_string(__s);
4557  return this->find_last_of(__s, __pos, traits_type::length(__s));
4558  }
4559 
4560  /**
4561  * @brief Find last position of a character.
4562  * @param __c Character to locate.
4563  * @param __pos Index of character to search back from (default end).
4564  * @return Index of last occurrence.
4565  *
4566  * Starting from @a __pos, searches backward for @a __c within
4567  * this string. If found, returns the index where it was
4568  * found. If not found, returns npos.
4569  *
4570  * Note: equivalent to rfind(__c, __pos).
4571  */
4572  size_type
4573  find_last_of(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT
4574  { return this->rfind(__c, __pos); }
4575 
4576  /**
4577  * @brief Find position of a character not in string.
4578  * @param __str String containing characters to avoid.
4579  * @param __pos Index of character to search from (default 0).
4580  * @return Index of first occurrence.
4581  *
4582  * Starting from @a __pos, searches forward for a character not contained
4583  * in @a __str within this string. If found, returns the index where it
4584  * was found. If not found, returns npos.
4585  */
4586  size_type
4587  find_first_not_of(const basic_string& __str, size_type __pos = 0) const
4588  _GLIBCXX_NOEXCEPT
4589  { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
4590 
4591  /**
4592  * @brief Find position of a character not in C substring.
4593  * @param __s C string containing characters to avoid.
4594  * @param __pos Index of character to search from.
4595  * @param __n Number of characters from __s to consider.
4596  * @return Index of first occurrence.
4597  *
4598  * Starting from @a __pos, searches forward for a character not
4599  * contained in the first @a __n characters of @a __s within
4600  * this string. If found, returns the index where it was
4601  * found. If not found, returns npos.
4602  */
4603  size_type
4604  find_first_not_of(const _CharT* __s, size_type __pos,
4605  size_type __n) const;
4606 
4607  /**
4608  * @brief Find position of a character not in C string.
4609  * @param __s C string containing characters to avoid.
4610  * @param __pos Index of character to search from (default 0).
4611  * @return Index of first occurrence.
4612  *
4613  * Starting from @a __pos, searches forward for a character not
4614  * contained in @a __s within this string. If found, returns
4615  * the index where it was found. If not found, returns npos.
4616  */
4617  size_type
4618  find_first_not_of(const _CharT* __s, size_type __pos = 0) const
4619  {
4620  __glibcxx_requires_string(__s);
4621  return this->find_first_not_of(__s, __pos, traits_type::length(__s));
4622  }
4623 
4624  /**
4625  * @brief Find position of a different character.
4626  * @param __c Character to avoid.
4627  * @param __pos Index of character to search from (default 0).
4628  * @return Index of first occurrence.
4629  *
4630  * Starting from @a __pos, searches forward for a character
4631  * other than @a __c within this string. If found, returns the
4632  * index where it was found. If not found, returns npos.
4633  */
4634  size_type
4635  find_first_not_of(_CharT __c, size_type __pos = 0) const
4636  _GLIBCXX_NOEXCEPT;
4637 
4638  /**
4639  * @brief Find last position of a character not in string.
4640  * @param __str String containing characters to avoid.
4641  * @param __pos Index of character to search back from (default end).
4642  * @return Index of last occurrence.
4643  *
4644  * Starting from @a __pos, searches backward for a character
4645  * not contained in @a __str within this string. If found,
4646  * returns the index where it was found. If not found, returns
4647  * npos.
4648  */
4649  size_type
4650  find_last_not_of(const basic_string& __str, size_type __pos = npos) const
4651  _GLIBCXX_NOEXCEPT
4652  { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
4653 
4654  /**
4655  * @brief Find last position of a character not in C substring.
4656  * @param __s C string containing characters to avoid.
4657  * @param __pos Index of character to search back from.
4658  * @param __n Number of characters from s to consider.
4659  * @return Index of last occurrence.
4660  *
4661  * Starting from @a __pos, searches backward for a character not
4662  * contained in the first @a __n characters of @a __s within this string.
4663  * If found, returns the index where it was found. If not found,
4664  * returns npos.
4665  */
4666  size_type
4667  find_last_not_of(const _CharT* __s, size_type __pos,
4668  size_type __n) const;
4669  /**
4670  * @brief Find last position of a character not in C string.
4671  * @param __s C string containing characters to avoid.
4672  * @param __pos Index of character to search back from (default end).
4673  * @return Index of last occurrence.
4674  *
4675  * Starting from @a __pos, searches backward for a character
4676  * not contained in @a __s within this string. If found,
4677  * returns the index where it was found. If not found, returns
4678  * npos.
4679  */
4680  size_type
4681  find_last_not_of(const _CharT* __s, size_type __pos = npos) const
4682  {
4683  __glibcxx_requires_string(__s);
4684  return this->find_last_not_of(__s, __pos, traits_type::length(__s));
4685  }
4686 
4687  /**
4688  * @brief Find last position of a different character.
4689  * @param __c Character to avoid.
4690  * @param __pos Index of character to search back from (default end).
4691  * @return Index of last occurrence.
4692  *
4693  * Starting from @a __pos, searches backward for a character other than
4694  * @a __c within this string. If found, returns the index where it was
4695  * found. If not found, returns npos.
4696  */
4697  size_type
4698  find_last_not_of(_CharT __c, size_type __pos = npos) const
4699  _GLIBCXX_NOEXCEPT;
4700 
4701  /**
4702  * @brief Get a substring.
4703  * @param __pos Index of first character (default 0).
4704  * @param __n Number of characters in substring (default remainder).
4705  * @return The new string.
4706  * @throw std::out_of_range If __pos > size().
4707  *
4708  * Construct and return a new string using the @a __n
4709  * characters starting at @a __pos. If the string is too
4710  * short, use the remainder of the characters. If @a __pos is
4711  * beyond the end of the string, out_of_range is thrown.
4712  */
4713  basic_string
4714  substr(size_type __pos = 0, size_type __n = npos) const
4715  { return basic_string(*this,
4716  _M_check(__pos, "basic_string::substr"), __n); }
4717 
4718  /**
4719  * @brief Compare to a string.
4720  * @param __str String to compare against.
4721  * @return Integer < 0, 0, or > 0.
4722  *
4723  * Returns an integer < 0 if this string is ordered before @a
4724  * __str, 0 if their values are equivalent, or > 0 if this
4725  * string is ordered after @a __str. Determines the effective
4726  * length rlen of the strings to compare as the smallest of
4727  * size() and str.size(). The function then compares the two
4728  * strings by calling traits::compare(data(), str.data(),rlen).
4729  * If the result of the comparison is nonzero returns it,
4730  * otherwise the shorter one is ordered first.
4731  */
4732  int
4733  compare(const basic_string& __str) const
4734  {
4735  const size_type __size = this->size();
4736  const size_type __osize = __str.size();
4737  const size_type __len = std::min(__size, __osize);
4738 
4739  int __r = traits_type::compare(_M_data(), __str.data(), __len);
4740  if (!__r)
4741  __r = _S_compare(__size, __osize);
4742  return __r;
4743  }
4744 
4745  /**
4746  * @brief Compare substring to a string.
4747  * @param __pos Index of first character of substring.
4748  * @param __n Number of characters in substring.
4749  * @param __str String to compare against.
4750  * @return Integer < 0, 0, or > 0.
4751  *
4752  * Form the substring of this string from the @a __n characters
4753  * starting at @a __pos. Returns an integer < 0 if the
4754  * substring is ordered before @a __str, 0 if their values are
4755  * equivalent, or > 0 if the substring is ordered after @a
4756  * __str. Determines the effective length rlen of the strings
4757  * to compare as the smallest of the length of the substring
4758  * and @a __str.size(). The function then compares the two
4759  * strings by calling
4760  * traits::compare(substring.data(),str.data(),rlen). If the
4761  * result of the comparison is nonzero returns it, otherwise
4762  * the shorter one is ordered first.
4763  */
4764  int
4765  compare(size_type __pos, size_type __n, const basic_string& __str) const;
4766 
4767  /**
4768  * @brief Compare substring to a substring.
4769  * @param __pos1 Index of first character of substring.
4770  * @param __n1 Number of characters in substring.
4771  * @param __str String to compare against.
4772  * @param __pos2 Index of first character of substring of str.
4773  * @param __n2 Number of characters in substring of str.
4774  * @return Integer < 0, 0, or > 0.
4775  *
4776  * Form the substring of this string from the @a __n1
4777  * characters starting at @a __pos1. Form the substring of @a
4778  * __str from the @a __n2 characters starting at @a __pos2.
4779  * Returns an integer < 0 if this substring is ordered before
4780  * the substring of @a __str, 0 if their values are equivalent,
4781  * or > 0 if this substring is ordered after the substring of
4782  * @a __str. Determines the effective length rlen of the
4783  * strings to compare as the smallest of the lengths of the
4784  * substrings. The function then compares the two strings by
4785  * calling
4786  * traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
4787  * If the result of the comparison is nonzero returns it,
4788  * otherwise the shorter one is ordered first.
4789  */
4790  int
4791  compare(size_type __pos1, size_type __n1, const basic_string& __str,
4792  size_type __pos2, size_type __n2) const;
4793 
4794  /**
4795  * @brief Compare to a C string.
4796  * @param __s C string to compare against.
4797  * @return Integer < 0, 0, or > 0.
4798  *
4799  * Returns an integer < 0 if this string is ordered before @a __s, 0 if
4800  * their values are equivalent, or > 0 if this string is ordered after
4801  * @a __s. Determines the effective length rlen of the strings to
4802  * compare as the smallest of size() and the length of a string
4803  * constructed from @a __s. The function then compares the two strings
4804  * by calling traits::compare(data(),s,rlen). If the result of the
4805  * comparison is nonzero returns it, otherwise the shorter one is
4806  * ordered first.
4807  */
4808  int
4809  compare(const _CharT* __s) const;
4810 
4811  // _GLIBCXX_RESOLVE_LIB_DEFECTS
4812  // 5 String::compare specification questionable
4813  /**
4814  * @brief Compare substring to a C string.
4815  * @param __pos Index of first character of substring.
4816  * @param __n1 Number of characters in substring.
4817  * @param __s C string to compare against.
4818  * @return Integer < 0, 0, or > 0.
4819  *
4820  * Form the substring of this string from the @a __n1
4821  * characters starting at @a pos. Returns an integer < 0 if
4822  * the substring is ordered before @a __s, 0 if their values
4823  * are equivalent, or > 0 if the substring is ordered after @a
4824  * __s. Determines the effective length rlen of the strings to
4825  * compare as the smallest of the length of the substring and
4826  * the length of a string constructed from @a __s. The
4827  * function then compares the two string by calling
4828  * traits::compare(substring.data(),__s,rlen). If the result of
4829  * the comparison is nonzero returns it, otherwise the shorter
4830  * one is ordered first.
4831  */
4832  int
4833  compare(size_type __pos, size_type __n1, const _CharT* __s) const;
4834 
4835  /**
4836  * @brief Compare substring against a character %array.
4837  * @param __pos Index of first character of substring.
4838  * @param __n1 Number of characters in substring.
4839  * @param __s character %array to compare against.
4840  * @param __n2 Number of characters of s.
4841  * @return Integer < 0, 0, or > 0.
4842  *
4843  * Form the substring of this string from the @a __n1
4844  * characters starting at @a __pos. Form a string from the
4845  * first @a __n2 characters of @a __s. Returns an integer < 0
4846  * if this substring is ordered before the string from @a __s,
4847  * 0 if their values are equivalent, or > 0 if this substring
4848  * is ordered after the string from @a __s. Determines the
4849  * effective length rlen of the strings to compare as the
4850  * smallest of the length of the substring and @a __n2. The
4851  * function then compares the two strings by calling
4852  * traits::compare(substring.data(),s,rlen). If the result of
4853  * the comparison is nonzero returns it, otherwise the shorter
4854  * one is ordered first.
4855  *
4856  * NB: s must have at least n2 characters, &apos;\\0&apos; has
4857  * no special meaning.
4858  */
4859  int
4860  compare(size_type __pos, size_type __n1, const _CharT* __s,
4861  size_type __n2) const;
4862  };
4863 #endif // !_GLIBCXX_USE_CXX11_ABI
4864 
4865  // operator+
4866  /**
4867  * @brief Concatenate two strings.
4868  * @param __lhs First string.
4869  * @param __rhs Last string.
4870  * @return New string with value of @a __lhs followed by @a __rhs.
4871  */
4872  template<typename _CharT, typename _Traits, typename _Alloc>
4873  basic_string<_CharT, _Traits, _Alloc>
4876  {
4878  __str.append(__rhs);
4879  return __str;
4880  }
4881 
4882  /**
4883  * @brief Concatenate C string and string.
4884  * @param __lhs First string.
4885  * @param __rhs Last string.
4886  * @return New string with value of @a __lhs followed by @a __rhs.
4887  */
4888  template<typename _CharT, typename _Traits, typename _Alloc>
4889  basic_string<_CharT,_Traits,_Alloc>
4890  operator+(const _CharT* __lhs,
4891  const basic_string<_CharT,_Traits,_Alloc>& __rhs);
4892 
4893  /**
4894  * @brief Concatenate character and string.
4895  * @param __lhs First string.
4896  * @param __rhs Last string.
4897  * @return New string with @a __lhs followed by @a __rhs.
4898  */
4899  template<typename _CharT, typename _Traits, typename _Alloc>
4900  basic_string<_CharT,_Traits,_Alloc>
4901  operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
4902 
4903  /**
4904  * @brief Concatenate string and C string.
4905  * @param __lhs First string.
4906  * @param __rhs Last string.
4907  * @return New string with @a __lhs followed by @a __rhs.
4908  */
4909  template<typename _CharT, typename _Traits, typename _Alloc>
4910  inline basic_string<_CharT, _Traits, _Alloc>
4912  const _CharT* __rhs)
4913  {
4915  __str.append(__rhs);
4916  return __str;
4917  }
4918 
4919  /**
4920  * @brief Concatenate string and character.
4921  * @param __lhs First string.
4922  * @param __rhs Last string.
4923  * @return New string with @a __lhs followed by @a __rhs.
4924  */
4925  template<typename _CharT, typename _Traits, typename _Alloc>
4926  inline basic_string<_CharT, _Traits, _Alloc>
4928  {
4929  typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
4930  typedef typename __string_type::size_type __size_type;
4931  __string_type __str(__lhs);
4932  __str.append(__size_type(1), __rhs);
4933  return __str;
4934  }
4935 
4936 #if __cplusplus >= 201103L
4937  template<typename _CharT, typename _Traits, typename _Alloc>
4938  inline basic_string<_CharT, _Traits, _Alloc>
4939  operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
4940  const basic_string<_CharT, _Traits, _Alloc>& __rhs)
4941  { return std::move(__lhs.append(__rhs)); }
4942 
4943  template<typename _CharT, typename _Traits, typename _Alloc>
4944  inline basic_string<_CharT, _Traits, _Alloc>
4945  operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4946  basic_string<_CharT, _Traits, _Alloc>&& __rhs)
4947  { return std::move(__rhs.insert(0, __lhs)); }
4948 
4949  template<typename _CharT, typename _Traits, typename _Alloc>
4950  inline basic_string<_CharT, _Traits, _Alloc>
4951  operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
4952  basic_string<_CharT, _Traits, _Alloc>&& __rhs)
4953  {
4954  const auto __size = __lhs.size() + __rhs.size();
4955  const bool __cond = (__size > __lhs.capacity()
4956  && __size <= __rhs.capacity());
4957  return __cond ? std::move(__rhs.insert(0, __lhs))
4958  : std::move(__lhs.append(__rhs));
4959  }
4960 
4961  template<typename _CharT, typename _Traits, typename _Alloc>
4962  inline basic_string<_CharT, _Traits, _Alloc>
4963  operator+(const _CharT* __lhs,
4964  basic_string<_CharT, _Traits, _Alloc>&& __rhs)
4965  { return std::move(__rhs.insert(0, __lhs)); }
4966 
4967  template<typename _CharT, typename _Traits, typename _Alloc>
4968  inline basic_string<_CharT, _Traits, _Alloc>
4969  operator+(_CharT __lhs,
4970  basic_string<_CharT, _Traits, _Alloc>&& __rhs)
4971  { return std::move(__rhs.insert(0, 1, __lhs)); }
4972 
4973  template<typename _CharT, typename _Traits, typename _Alloc>
4974  inline basic_string<_CharT, _Traits, _Alloc>
4975  operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
4976  const _CharT* __rhs)
4977  { return std::move(__lhs.append(__rhs)); }
4978 
4979  template<typename _CharT, typename _Traits, typename _Alloc>
4980  inline basic_string<_CharT, _Traits, _Alloc>
4981  operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
4982  _CharT __rhs)
4983  { return std::move(__lhs.append(1, __rhs)); }
4984 #endif
4985 
4986  // operator ==
4987  /**
4988  * @brief Test equivalence of two strings.
4989  * @param __lhs First string.
4990  * @param __rhs Second string.
4991  * @return True if @a __lhs.compare(@a __rhs) == 0. False otherwise.
4992  */
4993  template<typename _CharT, typename _Traits, typename _Alloc>
4994  inline bool
4995  operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4997  _GLIBCXX_NOEXCEPT
4998  { return __lhs.compare(__rhs) == 0; }
4999 
5000  template<typename _CharT>
5001  inline
5002  typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, bool>::__type
5003  operator==(const basic_string<_CharT>& __lhs,
5004  const basic_string<_CharT>& __rhs) _GLIBCXX_NOEXCEPT
5005  { return (__lhs.size() == __rhs.size()
5006  && !std::char_traits<_CharT>::compare(__lhs.data(), __rhs.data(),
5007  __lhs.size())); }
5008 
5009  /**
5010  * @brief Test equivalence of C string and string.
5011  * @param __lhs C string.
5012  * @param __rhs String.
5013  * @return True if @a __rhs.compare(@a __lhs) == 0. False otherwise.
5014  */
5015  template<typename _CharT, typename _Traits, typename _Alloc>
5016  inline bool
5017  operator==(const _CharT* __lhs,
5019  { return __rhs.compare(__lhs) == 0; }
5020 
5021  /**
5022  * @brief Test equivalence of string and C string.
5023  * @param __lhs String.
5024  * @param __rhs C string.
5025  * @return True if @a __lhs.compare(@a __rhs) == 0. False otherwise.
5026  */
5027  template<typename _CharT, typename _Traits, typename _Alloc>
5028  inline bool
5029  operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5030  const _CharT* __rhs)
5031  { return __lhs.compare(__rhs) == 0; }
5032 
5033  // operator !=
5034  /**
5035  * @brief Test difference of two strings.
5036  * @param __lhs First string.
5037  * @param __rhs Second string.
5038  * @return True if @a __lhs.compare(@a __rhs) != 0. False otherwise.
5039  */
5040  template<typename _CharT, typename _Traits, typename _Alloc>
5041  inline bool
5042  operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5044  _GLIBCXX_NOEXCEPT
5045  { return !(__lhs == __rhs); }
5046 
5047  /**
5048  * @brief Test difference of C string and string.
5049  * @param __lhs C string.
5050  * @param __rhs String.
5051  * @return True if @a __rhs.compare(@a __lhs) != 0. False otherwise.
5052  */
5053  template<typename _CharT, typename _Traits, typename _Alloc>
5054  inline bool
5055  operator!=(const _CharT* __lhs,
5057  { return !(__lhs == __rhs); }
5058 
5059  /**
5060  * @brief Test difference of string and C string.
5061  * @param __lhs String.
5062  * @param __rhs C string.
5063  * @return True if @a __lhs.compare(@a __rhs) != 0. False otherwise.
5064  */
5065  template<typename _CharT, typename _Traits, typename _Alloc>
5066  inline bool
5067  operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5068  const _CharT* __rhs)
5069  { return !(__lhs == __rhs); }
5070 
5071  // operator <
5072  /**
5073  * @brief Test if string precedes string.
5074  * @param __lhs First string.
5075  * @param __rhs Second string.
5076  * @return True if @a __lhs precedes @a __rhs. False otherwise.
5077  */
5078  template<typename _CharT, typename _Traits, typename _Alloc>
5079  inline bool
5080  operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5082  _GLIBCXX_NOEXCEPT
5083  { return __lhs.compare(__rhs) < 0; }
5084 
5085  /**
5086  * @brief Test if string precedes C string.
5087  * @param __lhs String.
5088  * @param __rhs C string.
5089  * @return True if @a __lhs precedes @a __rhs. False otherwise.
5090  */
5091  template<typename _CharT, typename _Traits, typename _Alloc>
5092  inline bool
5093  operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5094  const _CharT* __rhs)
5095  { return __lhs.compare(__rhs) < 0; }
5096 
5097  /**
5098  * @brief Test if C string precedes string.
5099  * @param __lhs C string.
5100  * @param __rhs String.
5101  * @return True if @a __lhs precedes @a __rhs. False otherwise.
5102  */
5103  template<typename _CharT, typename _Traits, typename _Alloc>
5104  inline bool
5105  operator<(const _CharT* __lhs,
5107  { return __rhs.compare(__lhs) > 0; }
5108 
5109  // operator >
5110  /**
5111  * @brief Test if string follows string.
5112  * @param __lhs First string.
5113  * @param __rhs Second string.
5114  * @return True if @a __lhs follows @a __rhs. False otherwise.
5115  */
5116  template<typename _CharT, typename _Traits, typename _Alloc>
5117  inline bool
5120  _GLIBCXX_NOEXCEPT
5121  { return __lhs.compare(__rhs) > 0; }
5122 
5123  /**
5124  * @brief Test if string follows C string.
5125  * @param __lhs String.
5126  * @param __rhs C string.
5127  * @return True if @a __lhs follows @a __rhs. False otherwise.
5128  */
5129  template<typename _CharT, typename _Traits, typename _Alloc>
5130  inline bool
5132  const _CharT* __rhs)
5133  { return __lhs.compare(__rhs) > 0; }
5134 
5135  /**
5136  * @brief Test if C string follows string.
5137  * @param __lhs C string.
5138  * @param __rhs String.
5139  * @return True if @a __lhs follows @a __rhs. False otherwise.
5140  */
5141  template<typename _CharT, typename _Traits, typename _Alloc>
5142  inline bool
5143  operator>(const _CharT* __lhs,
5145  { return __rhs.compare(__lhs) < 0; }
5146 
5147  // operator <=
5148  /**
5149  * @brief Test if string doesn't follow string.
5150  * @param __lhs First string.
5151  * @param __rhs Second string.
5152  * @return True if @a __lhs doesn't follow @a __rhs. False otherwise.
5153  */
5154  template<typename _CharT, typename _Traits, typename _Alloc>
5155  inline bool
5156  operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5158  _GLIBCXX_NOEXCEPT
5159  { return __lhs.compare(__rhs) <= 0; }
5160 
5161  /**
5162  * @brief Test if string doesn't follow C string.
5163  * @param __lhs String.
5164  * @param __rhs C string.
5165  * @return True if @a __lhs doesn't follow @a __rhs. False otherwise.
5166  */
5167  template<typename _CharT, typename _Traits, typename _Alloc>
5168  inline bool
5169  operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5170  const _CharT* __rhs)
5171  { return __lhs.compare(__rhs) <= 0; }
5172 
5173  /**
5174  * @brief Test if C string doesn't follow string.
5175  * @param __lhs C string.
5176  * @param __rhs String.
5177  * @return True if @a __lhs doesn't follow @a __rhs. False otherwise.
5178  */
5179  template<typename _CharT, typename _Traits, typename _Alloc>
5180  inline bool
5181  operator<=(const _CharT* __lhs,
5183  { return __rhs.compare(__lhs) >= 0; }
5184 
5185  // operator >=
5186  /**
5187  * @brief Test if string doesn't precede string.
5188  * @param __lhs First string.
5189  * @param __rhs Second string.
5190  * @return True if @a __lhs doesn't precede @a __rhs. False otherwise.
5191  */
5192  template<typename _CharT, typename _Traits, typename _Alloc>
5193  inline bool
5194  operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5196  _GLIBCXX_NOEXCEPT
5197  { return __lhs.compare(__rhs) >= 0; }
5198 
5199  /**
5200  * @brief Test if string doesn't precede C string.
5201  * @param __lhs String.
5202  * @param __rhs C string.
5203  * @return True if @a __lhs doesn't precede @a __rhs. False otherwise.
5204  */
5205  template<typename _CharT, typename _Traits, typename _Alloc>
5206  inline bool
5207  operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5208  const _CharT* __rhs)
5209  { return __lhs.compare(__rhs) >= 0; }
5210 
5211  /**
5212  * @brief Test if C string doesn't precede string.
5213  * @param __lhs C string.
5214  * @param __rhs String.
5215  * @return True if @a __lhs doesn't precede @a __rhs. False otherwise.
5216  */
5217  template<typename _CharT, typename _Traits, typename _Alloc>
5218  inline bool
5219  operator>=(const _CharT* __lhs,
5221  { return __rhs.compare(__lhs) <= 0; }
5222 
5223  /**
5224  * @brief Swap contents of two strings.
5225  * @param __lhs First string.
5226  * @param __rhs Second string.
5227  *
5228  * Exchanges the contents of @a __lhs and @a __rhs in constant time.
5229  */
5230  template<typename _CharT, typename _Traits, typename _Alloc>
5231  inline void
5234 #if __cplusplus >= 201103L
5235  noexcept(noexcept(__lhs.swap(__rhs)))
5236 #endif
5237  { __lhs.swap(__rhs); }
5238 
5239 
5240  /**
5241  * @brief Read stream into a string.
5242  * @param __is Input stream.
5243  * @param __str Buffer to store into.
5244  * @return Reference to the input stream.
5245  *
5246  * Stores characters from @a __is into @a __str until whitespace is
5247  * found, the end of the stream is encountered, or str.max_size()
5248  * is reached. If is.width() is non-zero, that is the limit on the
5249  * number of characters stored into @a __str. Any previous
5250  * contents of @a __str are erased.
5251  */
5252  template<typename _CharT, typename _Traits, typename _Alloc>
5253  basic_istream<_CharT, _Traits>&
5254  operator>>(basic_istream<_CharT, _Traits>& __is,
5255  basic_string<_CharT, _Traits, _Alloc>& __str);
5256 
5257  template<>
5258  basic_istream<char>&
5259  operator>>(basic_istream<char>& __is, basic_string<char>& __str);
5260 
5261  /**
5262  * @brief Write string to a stream.
5263  * @param __os Output stream.
5264  * @param __str String to write out.
5265  * @return Reference to the output stream.
5266  *
5267  * Output characters of @a __str into os following the same rules as for
5268  * writing a C string.
5269  */
5270  template<typename _CharT, typename _Traits, typename _Alloc>
5271  inline basic_ostream<_CharT, _Traits>&
5272  operator<<(basic_ostream<_CharT, _Traits>& __os,
5274  {
5275  // _GLIBCXX_RESOLVE_LIB_DEFECTS
5276  // 586. string inserter not a formatted function
5277  return __ostream_insert(__os, __str.data(), __str.size());
5278  }
5279 
5280  /**
5281  * @brief Read a line from stream into a string.
5282  * @param __is Input stream.
5283  * @param __str Buffer to store into.
5284  * @param __delim Character marking end of line.
5285  * @return Reference to the input stream.
5286  *
5287  * Stores characters from @a __is into @a __str until @a __delim is
5288  * found, the end of the stream is encountered, or str.max_size()
5289  * is reached. Any previous contents of @a __str are erased. If
5290  * @a __delim is encountered, it is extracted but not stored into
5291  * @a __str.
5292  */
5293  template<typename _CharT, typename _Traits, typename _Alloc>
5294  basic_istream<_CharT, _Traits>&
5295  getline(basic_istream<_CharT, _Traits>& __is,
5296  basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
5297 
5298  /**
5299  * @brief Read a line from stream into a string.
5300  * @param __is Input stream.
5301  * @param __str Buffer to store into.
5302  * @return Reference to the input stream.
5303  *
5304  * Stores characters from is into @a __str until &apos;\n&apos; is
5305  * found, the end of the stream is encountered, or str.max_size()
5306  * is reached. Any previous contents of @a __str are erased. If
5307  * end of line is encountered, it is extracted but not stored into
5308  * @a __str.
5309  */
5310  template<typename _CharT, typename _Traits, typename _Alloc>
5311  inline basic_istream<_CharT, _Traits>&
5314  { return std::getline(__is, __str, __is.widen('\n')); }
5315 
5316 #if __cplusplus >= 201103L
5317  /// Read a line from an rvalue stream into a string.
5318  template<typename _CharT, typename _Traits, typename _Alloc>
5319  inline basic_istream<_CharT, _Traits>&
5321  basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
5322  { return std::getline(__is, __str, __delim); }
5323 
5324  /// Read a line from an rvalue stream into a string.
5325  template<typename _CharT, typename _Traits, typename _Alloc>
5326  inline basic_istream<_CharT, _Traits>&
5329  { return std::getline(__is, __str); }
5330 #endif
5331 
5332  template<>
5333  basic_istream<char>&
5334  getline(basic_istream<char>& __in, basic_string<char>& __str,
5335  char __delim);
5336 
5337 #ifdef _GLIBCXX_USE_WCHAR_T
5338  template<>
5339  basic_istream<wchar_t>&
5340  getline(basic_istream<wchar_t>& __in, basic_string<wchar_t>& __str,
5341  wchar_t __delim);
5342 #endif
5343 
5344 _GLIBCXX_END_NAMESPACE_VERSION
5345 } // namespace
5346 
5347 #if __cplusplus >= 201103L && defined(_GLIBCXX_USE_C99)
5348 
5349 #include <ext/string_conversions.h>
5350 
5351 namespace std _GLIBCXX_VISIBILITY(default)
5352 {
5353 _GLIBCXX_BEGIN_NAMESPACE_VERSION
5354 _GLIBCXX_BEGIN_NAMESPACE_CXX11
5355 
5356  // 21.4 Numeric Conversions [string.conversions].
5357  inline int
5358  stoi(const string& __str, size_t* __idx = 0, int __base = 10)
5359  { return __gnu_cxx::__stoa<long, int>(&std::strtol, "stoi", __str.c_str(),
5360  __idx, __base); }
5361 
5362  inline long
5363  stol(const string& __str, size_t* __idx = 0, int __base = 10)
5364  { return __gnu_cxx::__stoa(&std::strtol, "stol", __str.c_str(),
5365  __idx, __base); }
5366 
5367  inline unsigned long
5368  stoul(const string& __str, size_t* __idx = 0, int __base = 10)
5369  { return __gnu_cxx::__stoa(&std::strtoul, "stoul", __str.c_str(),
5370  __idx, __base); }
5371 
5372  inline long long
5373  stoll(const string& __str, size_t* __idx = 0, int __base = 10)
5374  { return __gnu_cxx::__stoa(&std::strtoll, "stoll", __str.c_str(),
5375  __idx, __base); }
5376 
5377  inline unsigned long long
5378  stoull(const string& __str, size_t* __idx = 0, int __base = 10)
5379  { return __gnu_cxx::__stoa(&std::strtoull, "stoull", __str.c_str(),
5380  __idx, __base); }
5381 
5382  // NB: strtof vs strtod.
5383  inline float
5384  stof(const string& __str, size_t* __idx = 0)
5385  { return __gnu_cxx::__stoa(&std::strtof, "stof", __str.c_str(), __idx); }
5386 
5387  inline double
5388  stod(const string& __str, size_t* __idx = 0)
5389  { return __gnu_cxx::__stoa(&std::strtod, "stod", __str.c_str(), __idx); }
5390 
5391  inline long double
5392  stold(const string& __str, size_t* __idx = 0)
5393  { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }
5394 
5395  // NB: (v)snprintf vs sprintf.
5396 
5397  // DR 1261.
5398  inline string
5399  to_string(int __val)
5400  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
5401  "%d", __val); }
5402 
5403  inline string
5404  to_string(unsigned __val)
5405  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5406  4 * sizeof(unsigned),
5407  "%u", __val); }
5408 
5409  inline string
5410  to_string(long __val)
5411  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
5412  "%ld", __val); }
5413 
5414  inline string
5415  to_string(unsigned long __val)
5416  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5417  4 * sizeof(unsigned long),
5418  "%lu", __val); }
5419 
5420  inline string
5421  to_string(long long __val)
5422  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5423  4 * sizeof(long long),
5424  "%lld", __val); }
5425 
5426  inline string
5427  to_string(unsigned long long __val)
5428  { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5429  4 * sizeof(unsigned long long),
5430  "%llu", __val); }
5431 
5432  inline string
5433  to_string(float __val)
5434  {
5435  const int __n =
5436  __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
5437  return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5438  "%f", __val);
5439  }
5440 
5441  inline string
5442  to_string(double __val)
5443  {
5444  const int __n =
5445  __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
5446  return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5447  "%f", __val);
5448  }
5449 
5450  inline string
5451  to_string(long double __val)
5452  {
5453  const int __n =
5454  __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
5455  return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5456  "%Lf", __val);
5457  }
5458 
5459 #ifdef _GLIBCXX_USE_WCHAR_T
5460  inline int
5461  stoi(const wstring& __str, size_t* __idx = 0, int __base = 10)
5462  { return __gnu_cxx::__stoa<long, int>(&std::wcstol, "stoi", __str.c_str(),
5463  __idx, __base); }
5464 
5465  inline long
5466  stol(const wstring& __str, size_t* __idx = 0, int __base = 10)
5467  { return __gnu_cxx::__stoa(&std::wcstol, "stol", __str.c_str(),
5468  __idx, __base); }
5469 
5470  inline unsigned long
5471  stoul(const wstring& __str, size_t* __idx = 0, int __base = 10)
5472  { return __gnu_cxx::__stoa(&std::wcstoul, "stoul", __str.c_str(),
5473  __idx, __base); }
5474 
5475  inline long long
5476  stoll(const wstring& __str, size_t* __idx = 0, int __base = 10)
5477  { return __gnu_cxx::__stoa(&std::wcstoll, "stoll", __str.c_str(),
5478  __idx, __base); }
5479 
5480  inline unsigned long long
5481  stoull(const wstring& __str, size_t* __idx = 0, int __base = 10)
5482  { return __gnu_cxx::__stoa(&std::wcstoull, "stoull", __str.c_str(),
5483  __idx, __base); }
5484 
5485  // NB: wcstof vs wcstod.
5486  inline float
5487  stof(const wstring& __str, size_t* __idx = 0)
5488  { return __gnu_cxx::__stoa(&std::wcstof, "stof", __str.c_str(), __idx); }
5489 
5490  inline double
5491  stod(const wstring& __str, size_t* __idx = 0)
5492  { return __gnu_cxx::__stoa(&std::wcstod, "stod", __str.c_str(), __idx); }
5493 
5494  inline long double
5495  stold(const wstring& __str, size_t* __idx = 0)
5496  { return __gnu_cxx::__stoa(&std::wcstold, "stold", __str.c_str(), __idx); }
5497 
5498 #ifndef _GLIBCXX_HAVE_BROKEN_VSWPRINTF
5499  // DR 1261.
5500  inline wstring
5501  to_wstring(int __val)
5502  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(int),
5503  L"%d", __val); }
5504 
5505  inline wstring
5506  to_wstring(unsigned __val)
5507  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5508  4 * sizeof(unsigned),
5509  L"%u", __val); }
5510 
5511  inline wstring
5512  to_wstring(long __val)
5513  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(long),
5514  L"%ld", __val); }
5515 
5516  inline wstring
5517  to_wstring(unsigned long __val)
5518  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5519  4 * sizeof(unsigned long),
5520  L"%lu", __val); }
5521 
5522  inline wstring
5523  to_wstring(long long __val)
5524  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5525  4 * sizeof(long long),
5526  L"%lld", __val); }
5527 
5528  inline wstring
5529  to_wstring(unsigned long long __val)
5530  { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5531  4 * sizeof(unsigned long long),
5532  L"%llu", __val); }
5533 
5534  inline wstring
5535  to_wstring(float __val)
5536  {
5537  const int __n =
5538  __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
5539  return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5540  L"%f", __val);
5541  }
5542 
5543  inline wstring
5544  to_wstring(double __val)
5545  {
5546  const int __n =
5547  __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
5548  return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5549  L"%f", __val);
5550  }
5551 
5552  inline wstring
5553  to_wstring(long double __val)
5554  {
5555  const int __n =
5556  __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
5557  return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5558  L"%Lf", __val);
5559  }
5560 #endif // _GLIBCXX_HAVE_BROKEN_VSWPRINTF
5561 #endif
5562 
5563 _GLIBCXX_END_NAMESPACE_CXX11
5564 _GLIBCXX_END_NAMESPACE_VERSION
5565 } // namespace
5566 
5567 #endif /* C++11 && _GLIBCXX_USE_C99 ... */
5568 
5569 #if __cplusplus >= 201103L
5570 
5571 #include <bits/functional_hash.h>
5572 
5573 namespace std _GLIBCXX_VISIBILITY(default)
5574 {
5575 _GLIBCXX_BEGIN_NAMESPACE_VERSION
5576 
5577  // DR 1182.
5578 
5579 #ifndef _GLIBCXX_COMPATIBILITY_CXX0X
5580  /// std::hash specialization for string.
5581  template<>
5582  struct hash<string>
5583  : public __hash_base<size_t, string>
5584  {
5585  size_t
5586  operator()(const string& __s) const noexcept
5587  { return std::_Hash_impl::hash(__s.data(), __s.length()); }
5588  };
5589 
5590  template<>
5591  struct __is_fast_hash<hash<string>> : std::false_type
5592  { };
5593 
5594 #ifdef _GLIBCXX_USE_WCHAR_T
5595  /// std::hash specialization for wstring.
5596  template<>
5597  struct hash<wstring>
5598  : public __hash_base<size_t, wstring>
5599  {
5600  size_t
5601  operator()(const wstring& __s) const noexcept
5602  { return std::_Hash_impl::hash(__s.data(),
5603  __s.length() * sizeof(wchar_t)); }
5604  };
5605 
5606  template<>
5607  struct __is_fast_hash<hash<wstring>> : std::false_type
5608  { };
5609 #endif
5610 #endif /* _GLIBCXX_COMPATIBILITY_CXX0X */
5611 
5612 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
5613  /// std::hash specialization for u16string.
5614  template<>
5615  struct hash<u16string>
5616  : public __hash_base<size_t, u16string>
5617  {
5618  size_t
5619  operator()(const u16string& __s) const noexcept
5620  { return std::_Hash_impl::hash(__s.data(),
5621  __s.length() * sizeof(char16_t)); }
5622  };
5623 
5624  template<>
5625  struct __is_fast_hash<hash<u16string>> : std::false_type
5626  { };
5627 
5628  /// std::hash specialization for u32string.
5629  template<>
5630  struct hash<u32string>
5631  : public __hash_base<size_t, u32string>
5632  {
5633  size_t
5634  operator()(const u32string& __s) const noexcept
5635  { return std::_Hash_impl::hash(__s.data(),
5636  __s.length() * sizeof(char32_t)); }
5637  };
5638 
5639  template<>
5640  struct __is_fast_hash<hash<u32string>> : std::false_type
5641  { };
5642 #endif
5643 
5644 _GLIBCXX_END_NAMESPACE_VERSION
5645 
5646 #if __cplusplus > 201103L
5647 
5648 #define __cpp_lib_string_udls 201304
5649 
5650  inline namespace literals
5651  {
5652  inline namespace string_literals
5653  {
5654 _GLIBCXX_BEGIN_NAMESPACE_VERSION
5655 
5656  _GLIBCXX_DEFAULT_ABI_TAG
5657  inline basic_string<char>
5658  operator""s(const char* __str, size_t __len)
5659  { return basic_string<char>{__str, __len}; }
5660 
5661 #ifdef _GLIBCXX_USE_WCHAR_T
5662  _GLIBCXX_DEFAULT_ABI_TAG
5663  inline basic_string<wchar_t>
5664  operator""s(const wchar_t* __str, size_t __len)
5665  { return basic_string<wchar_t>{__str, __len}; }
5666 #endif
5667 
5668 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
5669  _GLIBCXX_DEFAULT_ABI_TAG
5670  inline basic_string<char16_t>
5671  operator""s(const char16_t* __str, size_t __len)
5672  { return basic_string<char16_t>{__str, __len}; }
5673 
5674  _GLIBCXX_DEFAULT_ABI_TAG
5675  inline basic_string<char32_t>
5676  operator""s(const char32_t* __str, size_t __len)
5677  { return basic_string<char32_t>{__str, __len}; }
5678 #endif
5679 
5680 _GLIBCXX_END_NAMESPACE_VERSION
5681  } // inline namespace string_literals
5682  } // inline namespace literals
5683 
5684 #endif // __cplusplus > 201103L
5685 
5686 } // namespace std
5687 
5688 #endif // C++11
5689 
5690 #endif /* _BASIC_STRING_H */
bool empty() const noexcept
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.
basic_string & assign(_InputIterator __first, _InputIterator __last)
Set value to a range 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, const basic_string &__str)
Replace range of characters with string.
Uniform interface to all pointer-like types.
Definition: ptr_traits.h:132
basic_string & operator=(_CharT __c)
Set value to string of length 1.
basic_string & insert(size_type __pos, const _CharT *__s)
Insert a C string.
basic_string & append(const _CharT *__s)
Append a C string.
const_reverse_iterator crbegin() const noexcept
complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition: complex:326
basic_string & erase(size_type __pos=0, size_type __n=npos)
Remove characters.
reference front()
basic_string & replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
Replace characters with multiple characters.
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.
const_iterator cend() const noexcept
basic_string & operator+=(initializer_list< _CharT > __l)
Append an initializer_list of characters.
basic_string(basic_string &&__str) noexcept
Move construct string.
basic_string & replace(iterator __i1, iterator __i2, initializer_list< _CharT > __l)
Replace range of characters with initializer_list.
basic_string & operator=(basic_string &&__str)
Move assign the value of str to this string.
const_reverse_iterator rbegin() const noexcept
basic_string & operator=(initializer_list< _CharT > __l)
Set value to string constructed from initializer list.
const_iterator cbegin() const noexcept
initializer_list
void shrink_to_fit() noexcept
A non-binding request to reduce capacity() to size().
basic_string & append(initializer_list< _CharT > __l)
Append an initializer_list of characters.
basic_string & assign(initializer_list< _CharT > __l)
Set value to an initializer_list of characters.
basic_string< wchar_t > wstring
A string of wchar_t.
Definition: stringfwd.h:78
const_reverse_iterator rend() const noexcept
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.
reverse_iterator rbegin()
Uniform interface to C++98 and C++0x allocators.
iterator erase(iterator __position)
Remove one character.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:195
size_type find(const _CharT *__s, size_type __pos=0) const
Find position of a C string.
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.
basic_string & assign(size_type __n, _CharT __c)
Set value to multiple characters.
std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, bitset< _Nb > &__x)
Global I/O operators for bitsets.
Definition: bitset:1462
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 _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.
size_type find_first_not_of(const _CharT *__s, size_type __pos=0) const
Find position of a character not in C string.
ISO C++ entities toplevel namespace is std.
const_iterator begin() const noexcept
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Definition: functions.h:558
size_type length() const noexcept
Returns the number of characters in the string, not including any null-termination.
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.
void pop_back()
Remove the last character.
reference operator[](size_type __pos)
Subscript access to the data contained in the string.
size_type find(const _CharT *__s, size_type __pos, size_type __n) const
Find position of a C substring.
basic_string & replace(iterator __i1, iterator __i2, const _CharT *__s, size_type __n)
Replace range of characters with C substring.
const_reference at(size_type __n) const
Provides access to the data contained in the string.
basic_string()
Default constructor creates an empty string.
basic_string & assign(basic_string &&__str)
Set value to contents of another string.
basic_string & replace(iterator __i1, iterator __i2, _InputIterator __k1, _InputIterator __k2)
Replace range of characters with range.
size_type find_first_of(const basic_string &__str, size_type __pos=0) const noexcept
Find position of a character of string.
basic_string & replace(iterator __i1, iterator __i2, const _CharT *__s)
Replace range of characters with C string.
const_reverse_iterator crend() const noexcept
basic_string & insert(size_type __pos, size_type __n, _CharT __c)
Insert multiple characters.
const _CharT * data() const noexcept
Return const pointer to contents.
basic_string & assign(const _CharT *__s)
Set value to contents of a C string.
reverse_iterator rend()
size_type capacity() const noexcept
Template class basic_istream.
Definition: iosfwd:83
const_reference operator[](size_type __pos) const noexcept
Subscript access to the data contained in the string.
Primary class template hash.
Definition: system_error:134
basic_string substr(size_type __pos=0, size_type __n=npos) const
Get a substring.
int compare(const basic_string &__str) const
Compare to a string.
Marking input iterators.
const_reference front() const noexcept
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.
size_type rfind(const _CharT *__s, size_type __pos=npos) const
Find last position of a C string.
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.
Common iterator class.
size_type find(const basic_string &__str, size_type __pos=0) const noexcept
Find position of a string.
Managing sequences of characters and character-like objects.
void resize(size_type __n)
Resizes the string to the specified number of characters.
Forward iterators support a superset of input iterator operations.
const_reference back() const noexcept
void swap(basic_string &__s)
Swap contents with another 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.
basic_string & operator+=(_CharT __c)
Append a character.
void resize(size_type __n, _CharT __c)
Resizes the string to the specified number of characters.
iterator insert(iterator __p, _CharT __c)
Insert one character.
size_type find_first_of(_CharT __c, size_type __pos=0) const noexcept
Find position of a 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_first_of(const _CharT *__s, size_type __pos=0) const
Find position of a character of C string.
size_type find_last_of(const basic_string &__str, size_type __pos=npos) const noexcept
Find last position of a character of 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.
integral_constant
Definition: type_traits:69
void reserve(size_type __res_arg=0)
Attempt to preallocate enough memory for specified number of characters.
basic_string & operator+=(const basic_string &__str)
Append a string to this string.
void insert(iterator __p, size_type __n, _CharT __c)
Insert multiple characters.
size_type rfind(const basic_string &__str, size_type __pos=npos) const noexcept
Find last position of a string.
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.
reference back()
char_type widen(char __c) const
Widens characters.
Definition: basic_ios.h:449
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, 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.