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