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