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