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