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