libstdc++
basic_string.h
Go to the documentation of this file.
00001 // Components for manipulating sequences of characters -*- C++ -*-
00002 
00003 // Copyright (C) 1997-2015 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/basic_string.h
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly. @headername{string}
00028  */
00029 
00030 //
00031 // ISO C++ 14882: 21 Strings library
00032 //
00033 
00034 #ifndef _BASIC_STRING_H
00035 #define _BASIC_STRING_H 1
00036 
00037 #pragma GCC system_header
00038 
00039 #include <ext/atomicity.h>
00040 #include <ext/alloc_traits.h>
00041 #include <debug/debug.h>
00042 #if __cplusplus >= 201103L
00043 #include <initializer_list>
00044 #endif
00045 
00046 namespace std _GLIBCXX_VISIBILITY(default)
00047 {
00048 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00049 
00050 #if _GLIBCXX_USE_CXX11_ABI
00051 _GLIBCXX_BEGIN_NAMESPACE_CXX11
00052   /**
00053    *  @class basic_string basic_string.h <string>
00054    *  @brief  Managing sequences of characters and character-like objects.
00055    *
00056    *  @ingroup strings
00057    *  @ingroup sequences
00058    *
00059    *  @tparam _CharT  Type of character
00060    *  @tparam _Traits  Traits for character type, defaults to
00061    *                   char_traits<_CharT>.
00062    *  @tparam _Alloc  Allocator type, defaults to allocator<_CharT>.
00063    *
00064    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00065    *  <a href="tables.html#66">reversible container</a>, and a
00066    *  <a href="tables.html#67">sequence</a>.  Of the
00067    *  <a href="tables.html#68">optional sequence requirements</a>, only
00068    *  @c push_back, @c at, and @c %array access are supported.
00069    */
00070   template<typename _CharT, typename _Traits, typename _Alloc>
00071     class basic_string
00072     {
00073       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
00074         rebind<_CharT>::other _Char_alloc_type;
00075       typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
00076 
00077       // Types:
00078     public:
00079       typedef _Traits                                   traits_type;
00080       typedef typename _Traits::char_type               value_type;
00081       typedef _Char_alloc_type                          allocator_type;
00082       typedef typename _Alloc_traits::size_type         size_type;
00083       typedef typename _Alloc_traits::difference_type   difference_type;
00084       typedef typename _Alloc_traits::reference         reference;
00085       typedef typename _Alloc_traits::const_reference   const_reference;
00086       typedef typename _Alloc_traits::pointer           pointer;
00087       typedef typename _Alloc_traits::const_pointer     const_pointer;
00088       typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
00089       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
00090                                                         const_iterator;
00091       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
00092       typedef std::reverse_iterator<iterator>           reverse_iterator;
00093 
00094       ///  Value returned by various member functions when they fail.
00095       static const size_type    npos = static_cast<size_type>(-1);
00096 
00097     private:
00098       // type used for positions in insert, erase etc.
00099 #if __cplusplus < 201103L
00100       typedef iterator __const_iterator;
00101 #else
00102       typedef const_iterator __const_iterator;
00103 #endif
00104 
00105       // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
00106       struct _Alloc_hider : allocator_type // TODO check __is_final
00107       {
00108         _Alloc_hider(pointer __dat, const _Alloc& __a = _Alloc())
00109         : allocator_type(__a), _M_p(__dat) { }
00110 
00111         pointer _M_p; // The actual data.
00112       };
00113 
00114       _Alloc_hider      _M_dataplus;
00115       size_type         _M_string_length;
00116 
00117       enum { _S_local_capacity = 15 / sizeof(_CharT) };
00118 
00119       union
00120       {
00121         _CharT           _M_local_buf[_S_local_capacity + 1];
00122         size_type        _M_allocated_capacity;
00123       };
00124 
00125       void
00126       _M_data(pointer __p)
00127       { _M_dataplus._M_p = __p; }
00128 
00129       void
00130       _M_length(size_type __length)
00131       { _M_string_length = __length; }
00132 
00133       pointer
00134       _M_data() const
00135       { return _M_dataplus._M_p; }
00136 
00137       pointer
00138       _M_local_data()
00139       {
00140 #if __cplusplus >= 201103L
00141         return std::pointer_traits<pointer>::pointer_to(*_M_local_buf);
00142 #else
00143         return pointer(_M_local_buf);
00144 #endif
00145       }
00146 
00147       const_pointer
00148       _M_local_data() const
00149       {
00150 #if __cplusplus >= 201103L
00151         return std::pointer_traits<const_pointer>::pointer_to(*_M_local_buf);
00152 #else
00153         return const_pointer(_M_local_buf);
00154 #endif
00155       }
00156 
00157       void
00158       _M_capacity(size_type __capacity)
00159       { _M_allocated_capacity = __capacity; }
00160 
00161       void
00162       _M_set_length(size_type __n)
00163       {
00164         _M_length(__n);
00165         traits_type::assign(_M_data()[__n], _CharT());
00166       }
00167 
00168       bool
00169       _M_is_local() const
00170       { return _M_data() == _M_local_data(); }
00171 
00172       // Create & Destroy
00173       pointer
00174       _M_create(size_type&, size_type);
00175 
00176       void
00177       _M_dispose()
00178       {
00179         if (!_M_is_local())
00180           _M_destroy(_M_allocated_capacity);
00181       }
00182 
00183       void
00184       _M_destroy(size_type __size) throw()
00185       { _Alloc_traits::deallocate(_M_get_allocator(), _M_data(), __size + 1); }
00186 
00187       // _M_construct_aux is used to implement the 21.3.1 para 15 which
00188       // requires special behaviour if _InIterator is an integral type
00189       template<typename _InIterator>
00190         void
00191         _M_construct_aux(_InIterator __beg, _InIterator __end,
00192                          std::__false_type)
00193         {
00194           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
00195           _M_construct(__beg, __end, _Tag());
00196         }
00197 
00198       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00199       // 438. Ambiguity in the "do the right thing" clause
00200       template<typename _Integer>
00201         void
00202         _M_construct_aux(_Integer __beg, _Integer __end, std::__true_type)
00203         { _M_construct_aux_2(static_cast<size_type>(__beg), __end); }
00204 
00205       void
00206       _M_construct_aux_2(size_type __req, _CharT __c)
00207       { _M_construct(__req, __c); }
00208 
00209       template<typename _InIterator>
00210         void
00211         _M_construct(_InIterator __beg, _InIterator __end)
00212         {
00213           typedef typename std::__is_integer<_InIterator>::__type _Integral;
00214           _M_construct_aux(__beg, __end, _Integral());
00215         }
00216 
00217       // For Input Iterators, used in istreambuf_iterators, etc.
00218       template<typename _InIterator>
00219         void
00220         _M_construct(_InIterator __beg, _InIterator __end,
00221                      std::input_iterator_tag);
00222 
00223       // For forward_iterators up to random_access_iterators, used for
00224       // string::iterator, _CharT*, etc.
00225       template<typename _FwdIterator>
00226         void
00227         _M_construct(_FwdIterator __beg, _FwdIterator __end,
00228                      std::forward_iterator_tag);
00229 
00230       void
00231       _M_construct(size_type __req, _CharT __c);
00232 
00233       allocator_type&
00234       _M_get_allocator()
00235       { return _M_dataplus; }
00236 
00237       const allocator_type&
00238       _M_get_allocator() const
00239       { return _M_dataplus; }
00240 
00241     private:
00242 
00243 #ifdef _GLIBCXX_DISAMBIGUATE_REPLACE_INST
00244       // The explicit instantiations in misc-inst.cc require this due to
00245       // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64063
00246       template<typename _Tp, bool _Requires =
00247                !__are_same<_Tp, _CharT*>::__value
00248                && !__are_same<_Tp, const _CharT*>::__value
00249                && !__are_same<_Tp, iterator>::__value
00250                && !__are_same<_Tp, const_iterator>::__value>
00251         struct __enable_if_not_native_iterator
00252         { typedef basic_string& __type; };
00253       template<typename _Tp>
00254         struct __enable_if_not_native_iterator<_Tp, false> { };
00255 #endif
00256 
00257       size_type
00258       _M_check(size_type __pos, const char* __s) const
00259       {
00260         if (__pos > this->size())
00261           __throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "
00262                                        "this->size() (which is %zu)"),
00263                                    __s, __pos, this->size());
00264         return __pos;
00265       }
00266 
00267       void
00268       _M_check_length(size_type __n1, size_type __n2, const char* __s) const
00269       {
00270         if (this->max_size() - (this->size() - __n1) < __n2)
00271           __throw_length_error(__N(__s));
00272       }
00273 
00274 
00275       // NB: _M_limit doesn't check for a bad __pos value.
00276       size_type
00277       _M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPT
00278       {
00279         const bool __testoff =  __off < this->size() - __pos;
00280         return __testoff ? __off : this->size() - __pos;
00281       }
00282 
00283       // True if _Rep and source do not overlap.
00284       bool
00285       _M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPT
00286       {
00287         return (less<const _CharT*>()(__s, _M_data())
00288                 || less<const _CharT*>()(_M_data() + this->size(), __s));
00289       }
00290 
00291       // When __n = 1 way faster than the general multichar
00292       // traits_type::copy/move/assign.
00293       static void
00294       _S_copy(_CharT* __d, const _CharT* __s, size_type __n)
00295       {
00296         if (__n == 1)
00297           traits_type::assign(*__d, *__s);
00298         else
00299           traits_type::copy(__d, __s, __n);
00300       }
00301 
00302       static void
00303       _S_move(_CharT* __d, const _CharT* __s, size_type __n)
00304       {
00305         if (__n == 1)
00306           traits_type::assign(*__d, *__s);
00307         else
00308           traits_type::move(__d, __s, __n);
00309       }
00310 
00311       static void
00312       _S_assign(_CharT* __d, size_type __n, _CharT __c)
00313       {
00314         if (__n == 1)
00315           traits_type::assign(*__d, __c);
00316         else
00317           traits_type::assign(__d, __n, __c);
00318       }
00319 
00320       // _S_copy_chars is a separate template to permit specialization
00321       // to optimize for the common case of pointers as iterators.
00322       template<class _Iterator>
00323         static void
00324         _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
00325         _GLIBCXX_NOEXCEPT
00326         {
00327           for (; __k1 != __k2; ++__k1, ++__p)
00328             traits_type::assign(*__p, *__k1); // These types are off.
00329         }
00330 
00331       static void
00332       _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) _GLIBCXX_NOEXCEPT
00333       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
00334 
00335       static void
00336       _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
00337       _GLIBCXX_NOEXCEPT
00338       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
00339 
00340       static void
00341       _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) _GLIBCXX_NOEXCEPT
00342       { _S_copy(__p, __k1, __k2 - __k1); }
00343 
00344       static void
00345       _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
00346       _GLIBCXX_NOEXCEPT
00347       { _S_copy(__p, __k1, __k2 - __k1); }
00348 
00349       static int
00350       _S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPT
00351       {
00352         const difference_type __d = difference_type(__n1 - __n2);
00353 
00354         if (__d > __gnu_cxx::__numeric_traits<int>::__max)
00355           return __gnu_cxx::__numeric_traits<int>::__max;
00356         else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
00357           return __gnu_cxx::__numeric_traits<int>::__min;
00358         else
00359           return int(__d);
00360       }
00361 
00362       void
00363       _M_assign(const basic_string& __rcs);
00364 
00365       void
00366       _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
00367                 size_type __len2);
00368 
00369       void
00370       _M_erase(size_type __pos, size_type __n);
00371 
00372     public:
00373       // Construct/copy/destroy:
00374       // NB: We overload ctors in some cases instead of using default
00375       // arguments, per 17.4.4.4 para. 2 item 2.
00376 
00377       /**
00378        *  @brief  Default constructor creates an empty string.
00379        */
00380       basic_string()
00381 #if __cplusplus >= 201103L
00382       noexcept(is_nothrow_default_constructible<_Alloc>::value)
00383 #endif
00384       : _M_dataplus(_M_local_data())
00385       { _M_set_length(0); }
00386 
00387       /**
00388        *  @brief  Construct an empty string using allocator @a a.
00389        */
00390       explicit
00391       basic_string(const _Alloc& __a)
00392       : _M_dataplus(_M_local_data(), __a)
00393       { _M_set_length(0); }
00394 
00395       /**
00396        *  @brief  Construct string with copy of value of @a __str.
00397        *  @param  __str  Source string.
00398        */
00399       basic_string(const basic_string& __str)
00400       : _M_dataplus(_M_local_data(), __str._M_get_allocator()) // TODO A traits
00401       { _M_construct(__str._M_data(), __str._M_data() + __str.length()); }
00402 
00403       /**
00404        *  @brief  Construct string as copy of a substring.
00405        *  @param  __str  Source string.
00406        *  @param  __pos  Index of first character to copy from.
00407        *  @param  __n  Number of characters to copy (default remainder).
00408        */
00409       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00410       // 2402. [this constructor] shouldn't use Allocator()
00411       basic_string(const basic_string& __str, size_type __pos,
00412                    size_type __n = npos)
00413       : _M_dataplus(_M_local_data())
00414       {
00415         const _CharT* __start = __str._M_data()
00416           + __str._M_check(__pos, "basic_string::basic_string");
00417         _M_construct(__start, __start + __str._M_limit(__pos, __n));
00418       }
00419 
00420       /**
00421        *  @brief  Construct string as copy of a substring.
00422        *  @param  __str  Source string.
00423        *  @param  __pos  Index of first character to copy from.
00424        *  @param  __n  Number of characters to copy (default remainder).
00425        *  @param  __a  Allocator to use.
00426        */
00427       basic_string(const basic_string& __str, size_type __pos,
00428                    size_type __n, const _Alloc& __a)
00429       : _M_dataplus(_M_local_data(), __a)
00430       {
00431         const _CharT* __start
00432           = __str._M_data() + __str._M_check(__pos, "string::string");
00433         _M_construct(__start, __start + __str._M_limit(__pos, __n));
00434       }
00435 
00436       /**
00437        *  @brief  Construct string initialized by a character %array.
00438        *  @param  __s  Source character %array.
00439        *  @param  __n  Number of characters to copy.
00440        *  @param  __a  Allocator to use (default is default allocator).
00441        *
00442        *  NB: @a __s must have at least @a __n characters, &apos;\\0&apos;
00443        *  has no special meaning.
00444        */
00445       basic_string(const _CharT* __s, size_type __n,
00446                    const _Alloc& __a = _Alloc())
00447       : _M_dataplus(_M_local_data(), __a)
00448       { _M_construct(__s, __s + __n); }
00449 
00450       /**
00451        *  @brief  Construct string as copy of a C string.
00452        *  @param  __s  Source C string.
00453        *  @param  __a  Allocator to use (default is default allocator).
00454        */
00455       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc())
00456       : _M_dataplus(_M_local_data(), __a)
00457       { _M_construct(__s, __s ? __s + traits_type::length(__s) : __s+npos); }
00458 
00459       /**
00460        *  @brief  Construct string as multiple characters.
00461        *  @param  __n  Number of characters.
00462        *  @param  __c  Character to use.
00463        *  @param  __a  Allocator to use (default is default allocator).
00464        */
00465       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc())
00466       : _M_dataplus(_M_local_data(), __a)
00467       { _M_construct(__n, __c); }
00468 
00469 #if __cplusplus >= 201103L
00470       /**
00471        *  @brief  Move construct string.
00472        *  @param  __str  Source string.
00473        *
00474        *  The newly-created string contains the exact contents of @a __str.
00475        *  @a __str is a valid, but unspecified string.
00476        **/
00477       basic_string(basic_string&& __str) noexcept
00478       : _M_dataplus(_M_local_data(), std::move(__str._M_get_allocator()))
00479       {
00480         if (__str._M_is_local())
00481           {
00482             traits_type::copy(_M_local_buf, __str._M_local_buf,
00483                               _S_local_capacity + 1);
00484           }
00485         else
00486           {
00487             _M_data(__str._M_data());
00488             _M_capacity(__str._M_allocated_capacity);
00489           }
00490 
00491         // Must use _M_length() here not _M_set_length() because
00492         // basic_stringbuf relies on writing into unallocated capacity so
00493         // we mess up the contents if we put a '\0' in the string.
00494         _M_length(__str.length());
00495         __str._M_data(__str._M_local_data());
00496         __str._M_set_length(0);
00497       }
00498 
00499       /**
00500        *  @brief  Construct string from an initializer %list.
00501        *  @param  __l  std::initializer_list of characters.
00502        *  @param  __a  Allocator to use (default is default allocator).
00503        */
00504       basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc())
00505       : _M_dataplus(_M_local_data(), __a)
00506       { _M_construct(__l.begin(), __l.end()); }
00507 
00508       basic_string(const basic_string& __str, const _Alloc& __a)
00509       : _M_dataplus(_M_local_data(), __a)
00510       { _M_construct(__str.begin(), __str.end()); }
00511 
00512       basic_string(basic_string&& __str, const _Alloc& __a)
00513       : _M_dataplus(_M_local_data(), __a)
00514       {
00515         if (__str.get_allocator() == __a)
00516           *this = std::move(__str);
00517         else
00518           _M_construct(__str.begin(), __str.end());
00519       }
00520 
00521 #endif // C++11
00522 
00523       /**
00524        *  @brief  Construct string as copy of a range.
00525        *  @param  __beg  Start of range.
00526        *  @param  __end  End of range.
00527        *  @param  __a  Allocator to use (default is default allocator).
00528        */
00529 #if __cplusplus >= 201103L
00530       template<typename _InputIterator,
00531                typename = std::_RequireInputIter<_InputIterator>>
00532 #else
00533       template<typename _InputIterator>
00534 #endif
00535         basic_string(_InputIterator __beg, _InputIterator __end,
00536                      const _Alloc& __a = _Alloc())
00537         : _M_dataplus(_M_local_data(), __a)
00538         { _M_construct(__beg, __end); }
00539 
00540       /**
00541        *  @brief  Destroy the string instance.
00542        */
00543       ~basic_string()
00544       { _M_dispose(); }
00545 
00546       /**
00547        *  @brief  Assign the value of @a str to this string.
00548        *  @param  __str  Source string.
00549        */
00550       basic_string&
00551       operator=(const basic_string& __str)
00552       { return this->assign(__str); }
00553 
00554       /**
00555        *  @brief  Copy contents of @a s into this string.
00556        *  @param  __s  Source null-terminated string.
00557        */
00558       basic_string&
00559       operator=(const _CharT* __s)
00560       { return this->assign(__s); }
00561 
00562       /**
00563        *  @brief  Set value to string of length 1.
00564        *  @param  __c  Source character.
00565        *
00566        *  Assigning to a character makes this string length 1 and
00567        *  (*this)[0] == @a c.
00568        */
00569       basic_string&
00570       operator=(_CharT __c)
00571       {
00572         this->assign(1, __c);
00573         return *this;
00574       }
00575 
00576 #if __cplusplus >= 201103L
00577       /**
00578        *  @brief  Move assign the value of @a str to this string.
00579        *  @param  __str  Source string.
00580        *
00581        *  The contents of @a str are moved into this string (without copying).
00582        *  @a str is a valid, but unspecified string.
00583        **/
00584       // PR 58265, this should be noexcept.
00585       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00586       // 2063. Contradictory requirements for string move assignment
00587       basic_string&
00588       operator=(basic_string&& __str)
00589       {
00590         this->swap(__str);
00591         return *this;
00592       }
00593 
00594       /**
00595        *  @brief  Set value to string constructed from initializer %list.
00596        *  @param  __l  std::initializer_list.
00597        */
00598       basic_string&
00599       operator=(initializer_list<_CharT> __l)
00600       {
00601         this->assign(__l.begin(), __l.size());
00602         return *this;
00603       }
00604 #endif // C++11
00605 
00606       // Iterators:
00607       /**
00608        *  Returns a read/write iterator that points to the first character in
00609        *  the %string.
00610        */
00611       iterator
00612       begin() _GLIBCXX_NOEXCEPT
00613       { return iterator(_M_data()); }
00614 
00615       /**
00616        *  Returns a read-only (constant) iterator that points to the first
00617        *  character in the %string.
00618        */
00619       const_iterator
00620       begin() const _GLIBCXX_NOEXCEPT
00621       { return const_iterator(_M_data()); }
00622 
00623       /**
00624        *  Returns a read/write iterator that points one past the last
00625        *  character in the %string.
00626        */
00627       iterator
00628       end() _GLIBCXX_NOEXCEPT
00629       { return iterator(_M_data() + this->size()); }
00630 
00631       /**
00632        *  Returns a read-only (constant) iterator that points one past the
00633        *  last character in the %string.
00634        */
00635       const_iterator
00636       end() const _GLIBCXX_NOEXCEPT
00637       { return const_iterator(_M_data() + this->size()); }
00638 
00639       /**
00640        *  Returns a read/write reverse iterator that points to the last
00641        *  character in the %string.  Iteration is done in reverse element
00642        *  order.
00643        */
00644       reverse_iterator
00645       rbegin() _GLIBCXX_NOEXCEPT
00646       { return reverse_iterator(this->end()); }
00647 
00648       /**
00649        *  Returns a read-only (constant) reverse iterator that points
00650        *  to the last character in the %string.  Iteration is done in
00651        *  reverse element order.
00652        */
00653       const_reverse_iterator
00654       rbegin() const _GLIBCXX_NOEXCEPT
00655       { return const_reverse_iterator(this->end()); }
00656 
00657       /**
00658        *  Returns a read/write reverse iterator that points to one before the
00659        *  first character in the %string.  Iteration is done in reverse
00660        *  element order.
00661        */
00662       reverse_iterator
00663       rend() _GLIBCXX_NOEXCEPT
00664       { return reverse_iterator(this->begin()); }
00665 
00666       /**
00667        *  Returns a read-only (constant) reverse iterator that points
00668        *  to one before the first character in the %string.  Iteration
00669        *  is done in reverse element order.
00670        */
00671       const_reverse_iterator
00672       rend() const _GLIBCXX_NOEXCEPT
00673       { return const_reverse_iterator(this->begin()); }
00674 
00675 #if __cplusplus >= 201103L
00676       /**
00677        *  Returns a read-only (constant) iterator that points to the first
00678        *  character in the %string.
00679        */
00680       const_iterator
00681       cbegin() const noexcept
00682       { return const_iterator(this->_M_data()); }
00683 
00684       /**
00685        *  Returns a read-only (constant) iterator that points one past the
00686        *  last character in the %string.
00687        */
00688       const_iterator
00689       cend() const noexcept
00690       { return const_iterator(this->_M_data() + this->size()); }
00691 
00692       /**
00693        *  Returns a read-only (constant) reverse iterator that points
00694        *  to the last character in the %string.  Iteration is done in
00695        *  reverse element order.
00696        */
00697       const_reverse_iterator
00698       crbegin() const noexcept
00699       { return const_reverse_iterator(this->end()); }
00700 
00701       /**
00702        *  Returns a read-only (constant) reverse iterator that points
00703        *  to one before the first character in the %string.  Iteration
00704        *  is done in reverse element order.
00705        */
00706       const_reverse_iterator
00707       crend() const noexcept
00708       { return const_reverse_iterator(this->begin()); }
00709 #endif
00710 
00711     public:
00712       // Capacity:
00713       ///  Returns the number of characters in the string, not including any
00714       ///  null-termination.
00715       size_type
00716       size() const _GLIBCXX_NOEXCEPT
00717       { return _M_string_length; }
00718 
00719       ///  Returns the number of characters in the string, not including any
00720       ///  null-termination.
00721       size_type
00722       length() const _GLIBCXX_NOEXCEPT
00723       { return _M_string_length; }
00724 
00725       ///  Returns the size() of the largest possible %string.
00726       size_type
00727       max_size() const _GLIBCXX_NOEXCEPT
00728       { return (_Alloc_traits::max_size(_M_get_allocator()) - 1) / 2; }
00729 
00730       /**
00731        *  @brief  Resizes the %string to the specified number of characters.
00732        *  @param  __n  Number of characters the %string should contain.
00733        *  @param  __c  Character to fill any new elements.
00734        *
00735        *  This function will %resize the %string to the specified
00736        *  number of characters.  If the number is smaller than the
00737        *  %string's current size the %string is truncated, otherwise
00738        *  the %string is extended and new elements are %set to @a __c.
00739        */
00740       void
00741       resize(size_type __n, _CharT __c);
00742 
00743       /**
00744        *  @brief  Resizes the %string to the specified number of characters.
00745        *  @param  __n  Number of characters the %string should contain.
00746        *
00747        *  This function will resize the %string to the specified length.  If
00748        *  the new size is smaller than the %string's current size the %string
00749        *  is truncated, otherwise the %string is extended and new characters
00750        *  are default-constructed.  For basic types such as char, this means
00751        *  setting them to 0.
00752        */
00753       void
00754       resize(size_type __n)
00755       { this->resize(__n, _CharT()); }
00756 
00757 #if __cplusplus >= 201103L
00758       ///  A non-binding request to reduce capacity() to size().
00759       void
00760       shrink_to_fit() noexcept
00761       {
00762         if (capacity() > size())
00763           {
00764             __try
00765               { reserve(0); }
00766             __catch(...)
00767               { }
00768           }
00769       }
00770 #endif
00771 
00772       /**
00773        *  Returns the total number of characters that the %string can hold
00774        *  before needing to allocate more memory.
00775        */
00776       size_type
00777       capacity() const _GLIBCXX_NOEXCEPT
00778       {
00779         return _M_is_local() ? size_type(_S_local_capacity)
00780                              : _M_allocated_capacity;
00781       }
00782 
00783       /**
00784        *  @brief  Attempt to preallocate enough memory for specified number of
00785        *          characters.
00786        *  @param  __res_arg  Number of characters required.
00787        *  @throw  std::length_error  If @a __res_arg exceeds @c max_size().
00788        *
00789        *  This function attempts to reserve enough memory for the
00790        *  %string to hold the specified number of characters.  If the
00791        *  number requested is more than max_size(), length_error is
00792        *  thrown.
00793        *
00794        *  The advantage of this function is that if optimal code is a
00795        *  necessity and the user can determine the string length that will be
00796        *  required, the user can reserve the memory in %advance, and thus
00797        *  prevent a possible reallocation of memory and copying of %string
00798        *  data.
00799        */
00800       void
00801       reserve(size_type __res_arg = 0);
00802 
00803       /**
00804        *  Erases the string, making it empty.
00805        */
00806       void
00807       clear() _GLIBCXX_NOEXCEPT
00808       { _M_set_length(0); }
00809 
00810       /**
00811        *  Returns true if the %string is empty.  Equivalent to 
00812        *  <code>*this == ""</code>.
00813        */
00814       bool
00815       empty() const _GLIBCXX_NOEXCEPT
00816       { return this->size() == 0; }
00817 
00818       // Element access:
00819       /**
00820        *  @brief  Subscript access to the data contained in the %string.
00821        *  @param  __pos  The index of the character to access.
00822        *  @return  Read-only (constant) reference to the character.
00823        *
00824        *  This operator allows for easy, array-style, data access.
00825        *  Note that data access with this operator is unchecked and
00826        *  out_of_range lookups are not defined. (For checked lookups
00827        *  see at().)
00828        */
00829       const_reference
00830       operator[] (size_type __pos) const _GLIBCXX_NOEXCEPT
00831       {
00832         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
00833         return _M_data()[__pos];
00834       }
00835 
00836       /**
00837        *  @brief  Subscript access to the data contained in the %string.
00838        *  @param  __pos  The index of the character to access.
00839        *  @return  Read/write reference to the character.
00840        *
00841        *  This operator allows for easy, array-style, data access.
00842        *  Note that data access with this operator is unchecked and
00843        *  out_of_range lookups are not defined. (For checked lookups
00844        *  see at().)
00845        */
00846       reference
00847       operator[](size_type __pos)
00848       {
00849         // Allow pos == size() both in C++98 mode, as v3 extension,
00850         // and in C++11 mode.
00851         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
00852         // In pedantic mode be strict in C++98 mode.
00853         _GLIBCXX_DEBUG_PEDASSERT(__cplusplus >= 201103L || __pos < size());
00854         return _M_data()[__pos];
00855       }
00856 
00857       /**
00858        *  @brief  Provides access to the data contained in the %string.
00859        *  @param __n The index of the character to access.
00860        *  @return  Read-only (const) reference to the character.
00861        *  @throw  std::out_of_range  If @a n is an invalid index.
00862        *
00863        *  This function provides for safer data access.  The parameter is
00864        *  first checked that it is in the range of the string.  The function
00865        *  throws out_of_range if the check fails.
00866        */
00867       const_reference
00868       at(size_type __n) const
00869       {
00870         if (__n >= this->size())
00871           __throw_out_of_range_fmt(__N("basic_string::at: __n "
00872                                        "(which is %zu) >= this->size() "
00873                                        "(which is %zu)"),
00874                                    __n, this->size());
00875         return _M_data()[__n];
00876       }
00877 
00878       /**
00879        *  @brief  Provides access to the data contained in the %string.
00880        *  @param __n The index of the character to access.
00881        *  @return  Read/write reference to the character.
00882        *  @throw  std::out_of_range  If @a n is an invalid index.
00883        *
00884        *  This function provides for safer data access.  The parameter is
00885        *  first checked that it is in the range of the string.  The function
00886        *  throws out_of_range if the check fails.
00887        */
00888       reference
00889       at(size_type __n)
00890       {
00891         if (__n >= size())
00892           __throw_out_of_range_fmt(__N("basic_string::at: __n "
00893                                        "(which is %zu) >= this->size() "
00894                                        "(which is %zu)"),
00895                                    __n, this->size());
00896         return _M_data()[__n];
00897       }
00898 
00899 #if __cplusplus >= 201103L
00900       /**
00901        *  Returns a read/write reference to the data at the first
00902        *  element of the %string.
00903        */
00904       reference
00905       front() noexcept
00906       { return operator[](0); }
00907 
00908       /**
00909        *  Returns a read-only (constant) reference to the data at the first
00910        *  element of the %string.
00911        */
00912       const_reference
00913       front() const noexcept
00914       { return operator[](0); }
00915 
00916       /**
00917        *  Returns a read/write reference to the data at the last
00918        *  element of the %string.
00919        */
00920       reference
00921       back() noexcept
00922       { return operator[](this->size() - 1); }
00923 
00924       /**
00925        *  Returns a read-only (constant) reference to the data at the
00926        *  last element of the %string.
00927        */
00928       const_reference
00929       back() const noexcept
00930       { return operator[](this->size() - 1); }
00931 #endif
00932 
00933       // Modifiers:
00934       /**
00935        *  @brief  Append a string to this string.
00936        *  @param __str  The string to append.
00937        *  @return  Reference to this string.
00938        */
00939       basic_string&
00940       operator+=(const basic_string& __str)
00941       { return this->append(__str); }
00942 
00943       /**
00944        *  @brief  Append a C string.
00945        *  @param __s  The C string to append.
00946        *  @return  Reference to this string.
00947        */
00948       basic_string&
00949       operator+=(const _CharT* __s)
00950       { return this->append(__s); }
00951 
00952       /**
00953        *  @brief  Append a character.
00954        *  @param __c  The character to append.
00955        *  @return  Reference to this string.
00956        */
00957       basic_string&
00958       operator+=(_CharT __c)
00959       {
00960         this->push_back(__c);
00961         return *this;
00962       }
00963 
00964 #if __cplusplus >= 201103L
00965       /**
00966        *  @brief  Append an initializer_list of characters.
00967        *  @param __l  The initializer_list of characters to be appended.
00968        *  @return  Reference to this string.
00969        */
00970       basic_string&
00971       operator+=(initializer_list<_CharT> __l)
00972       { return this->append(__l.begin(), __l.size()); }
00973 #endif // C++11
00974 
00975       /**
00976        *  @brief  Append a string to this string.
00977        *  @param __str  The string to append.
00978        *  @return  Reference to this string.
00979        */
00980       basic_string&
00981       append(const basic_string& __str)
00982       { return _M_append(__str._M_data(), __str.size()); }
00983 
00984       /**
00985        *  @brief  Append a substring.
00986        *  @param __str  The string to append.
00987        *  @param __pos  Index of the first character of str to append.
00988        *  @param __n  The number of characters to append.
00989        *  @return  Reference to this string.
00990        *  @throw  std::out_of_range if @a __pos is not a valid index.
00991        *
00992        *  This function appends @a __n characters from @a __str
00993        *  starting at @a __pos to this string.  If @a __n is is larger
00994        *  than the number of available characters in @a __str, the
00995        *  remainder of @a __str is appended.
00996        */
00997       basic_string&
00998       append(const basic_string& __str, size_type __pos, size_type __n)
00999       { return _M_append(__str._M_data()
01000                          + __str._M_check(__pos, "basic_string::append"),
01001                          __str._M_limit(__pos, __n)); }
01002 
01003       /**
01004        *  @brief  Append a C substring.
01005        *  @param __s  The C string to append.
01006        *  @param __n  The number of characters to append.
01007        *  @return  Reference to this string.
01008        */
01009       basic_string&
01010       append(const _CharT* __s, size_type __n)
01011       {
01012         __glibcxx_requires_string_len(__s, __n);
01013         _M_check_length(size_type(0), __n, "basic_string::append");
01014         return _M_append(__s, __n);
01015       }
01016 
01017       /**
01018        *  @brief  Append a C string.
01019        *  @param __s  The C string to append.
01020        *  @return  Reference to this string.
01021        */
01022       basic_string&
01023       append(const _CharT* __s)
01024       {
01025         __glibcxx_requires_string(__s);
01026         const size_type __n = traits_type::length(__s);
01027         _M_check_length(size_type(0), __n, "basic_string::append");
01028         return _M_append(__s, __n);
01029       }
01030 
01031       /**
01032        *  @brief  Append multiple characters.
01033        *  @param __n  The number of characters to append.
01034        *  @param __c  The character to use.
01035        *  @return  Reference to this string.
01036        *
01037        *  Appends __n copies of __c to this string.
01038        */
01039       basic_string&
01040       append(size_type __n, _CharT __c)
01041       { return _M_replace_aux(this->size(), size_type(0), __n, __c); }
01042 
01043 #if __cplusplus >= 201103L
01044       /**
01045        *  @brief  Append an initializer_list of characters.
01046        *  @param __l  The initializer_list of characters to append.
01047        *  @return  Reference to this string.
01048        */
01049       basic_string&
01050       append(initializer_list<_CharT> __l)
01051       { return this->append(__l.begin(), __l.size()); }
01052 #endif // C++11
01053 
01054       /**
01055        *  @brief  Append a range of characters.
01056        *  @param __first  Iterator referencing the first character to append.
01057        *  @param __last  Iterator marking the end of the range.
01058        *  @return  Reference to this string.
01059        *
01060        *  Appends characters in the range [__first,__last) to this string.
01061        */
01062 #if __cplusplus >= 201103L
01063       template<class _InputIterator,
01064                typename = std::_RequireInputIter<_InputIterator>>
01065 #else
01066       template<class _InputIterator>
01067 #endif
01068         basic_string&
01069         append(_InputIterator __first, _InputIterator __last)
01070         { return this->replace(end(), end(), __first, __last); }
01071 
01072       /**
01073        *  @brief  Append a single character.
01074        *  @param __c  Character to append.
01075        */
01076       void
01077       push_back(_CharT __c)
01078       {
01079         const size_type __size = this->size();
01080         if (__size + 1 > this->capacity())
01081           this->_M_mutate(__size, size_type(0), 0, size_type(1));
01082         traits_type::assign(this->_M_data()[__size], __c);
01083         this->_M_set_length(__size + 1);
01084       }
01085 
01086       /**
01087        *  @brief  Set value to contents of another string.
01088        *  @param  __str  Source string to use.
01089        *  @return  Reference to this string.
01090        */
01091       basic_string&
01092       assign(const basic_string& __str)
01093       {
01094         this->_M_assign(__str);
01095         return *this;
01096       }
01097 
01098 #if __cplusplus >= 201103L
01099       /**
01100        *  @brief  Set value to contents of another string.
01101        *  @param  __str  Source string to use.
01102        *  @return  Reference to this string.
01103        *
01104        *  This function sets this string to the exact contents of @a __str.
01105        *  @a __str is a valid, but unspecified string.
01106        */
01107       basic_string&
01108       assign(basic_string&& __str)
01109       {
01110         // _GLIBCXX_RESOLVE_LIB_DEFECTS
01111         // 2063. Contradictory requirements for string move assignment
01112         return *this = std::move(__str);
01113       }
01114 #endif // C++11
01115 
01116       /**
01117        *  @brief  Set value to a substring of a string.
01118        *  @param __str  The string to use.
01119        *  @param __pos  Index of the first character of str.
01120        *  @param __n  Number of characters to use.
01121        *  @return  Reference to this string.
01122        *  @throw  std::out_of_range if @a pos is not a valid index.
01123        *
01124        *  This function sets this string to the substring of @a __str
01125        *  consisting of @a __n characters at @a __pos.  If @a __n is
01126        *  is larger than the number of available characters in @a
01127        *  __str, the remainder of @a __str is used.
01128        */
01129       basic_string&
01130       assign(const basic_string& __str, size_type __pos, size_type __n)
01131       { return _M_replace(size_type(0), this->size(), __str._M_data()
01132                           + __str._M_check(__pos, "basic_string::assign"),
01133                           __str._M_limit(__pos, __n)); }
01134 
01135       /**
01136        *  @brief  Set value to a C substring.
01137        *  @param __s  The C string to use.
01138        *  @param __n  Number of characters to use.
01139        *  @return  Reference to this string.
01140        *
01141        *  This function sets the value of this string to the first @a __n
01142        *  characters of @a __s.  If @a __n is is larger than the number of
01143        *  available characters in @a __s, the remainder of @a __s is used.
01144        */
01145       basic_string&
01146       assign(const _CharT* __s, size_type __n)
01147       {
01148         __glibcxx_requires_string_len(__s, __n);
01149         return _M_replace(size_type(0), this->size(), __s, __n);
01150       }
01151 
01152       /**
01153        *  @brief  Set value to contents of a C string.
01154        *  @param __s  The C string to use.
01155        *  @return  Reference to this string.
01156        *
01157        *  This function sets the value of this string to the value of @a __s.
01158        *  The data is copied, so there is no dependence on @a __s once the
01159        *  function returns.
01160        */
01161       basic_string&
01162       assign(const _CharT* __s)
01163       {
01164         __glibcxx_requires_string(__s);
01165         return _M_replace(size_type(0), this->size(), __s,
01166                           traits_type::length(__s));
01167       }
01168 
01169       /**
01170        *  @brief  Set value to multiple characters.
01171        *  @param __n  Length of the resulting string.
01172        *  @param __c  The character to use.
01173        *  @return  Reference to this string.
01174        *
01175        *  This function sets the value of this string to @a __n copies of
01176        *  character @a __c.
01177        */
01178       basic_string&
01179       assign(size_type __n, _CharT __c)
01180       { return _M_replace_aux(size_type(0), this->size(), __n, __c); }
01181 
01182       /**
01183        *  @brief  Set value to a range of characters.
01184        *  @param __first  Iterator referencing the first character to append.
01185        *  @param __last  Iterator marking the end of the range.
01186        *  @return  Reference to this string.
01187        *
01188        *  Sets value of string to characters in the range [__first,__last).
01189       */
01190 #if __cplusplus >= 201103L
01191       template<class _InputIterator,
01192                typename = std::_RequireInputIter<_InputIterator>>
01193 #else
01194       template<class _InputIterator>
01195 #endif
01196         basic_string&
01197         assign(_InputIterator __first, _InputIterator __last)
01198         { return this->replace(begin(), end(), __first, __last); }
01199 
01200 #if __cplusplus >= 201103L
01201       /**
01202        *  @brief  Set value to an initializer_list of characters.
01203        *  @param __l  The initializer_list of characters to assign.
01204        *  @return  Reference to this string.
01205        */
01206       basic_string&
01207       assign(initializer_list<_CharT> __l)
01208       { return this->assign(__l.begin(), __l.size()); }
01209 #endif // C++11
01210 
01211 #if __cplusplus >= 201103L
01212       /**
01213        *  @brief  Insert multiple characters.
01214        *  @param __p  Const_iterator referencing location in string to
01215        *              insert at.
01216        *  @param __n  Number of characters to insert
01217        *  @param __c  The character to insert.
01218        *  @return  Iterator referencing the first inserted char.
01219        *  @throw  std::length_error  If new length exceeds @c max_size().
01220        *
01221        *  Inserts @a __n copies of character @a __c starting at the
01222        *  position referenced by iterator @a __p.  If adding
01223        *  characters causes the length to exceed max_size(),
01224        *  length_error is thrown.  The value of the string doesn't
01225        *  change if an error is thrown.
01226       */
01227       iterator
01228       insert(const_iterator __p, size_type __n, _CharT __c)
01229       {
01230         _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
01231         const size_type __pos = __p - begin();
01232         this->replace(__p, __p, __n, __c);
01233         return iterator(this->_M_data() + __pos);
01234       }
01235 #else
01236       /**
01237        *  @brief  Insert multiple characters.
01238        *  @param __p  Iterator referencing location in string to insert at.
01239        *  @param __n  Number of characters to insert
01240        *  @param __c  The character to insert.
01241        *  @throw  std::length_error  If new length exceeds @c max_size().
01242        *
01243        *  Inserts @a __n copies of character @a __c starting at the
01244        *  position referenced by iterator @a __p.  If adding
01245        *  characters causes the length to exceed max_size(),
01246        *  length_error is thrown.  The value of the string doesn't
01247        *  change if an error is thrown.
01248       */
01249       void
01250       insert(iterator __p, size_type __n, _CharT __c)
01251       { this->replace(__p, __p, __n, __c);  }
01252 #endif
01253 
01254 #if __cplusplus >= 201103L
01255       /**
01256        *  @brief  Insert a range of characters.
01257        *  @param __p  Const_iterator referencing location in string to
01258        *              insert at.
01259        *  @param __beg  Start of range.
01260        *  @param __end  End of range.
01261        *  @return  Iterator referencing the first inserted char.
01262        *  @throw  std::length_error  If new length exceeds @c max_size().
01263        *
01264        *  Inserts characters in range [beg,end).  If adding characters
01265        *  causes the length to exceed max_size(), length_error is
01266        *  thrown.  The value of the string doesn't change if an error
01267        *  is thrown.
01268       */
01269       template<class _InputIterator,
01270                typename = std::_RequireInputIter<_InputIterator>>
01271         iterator
01272         insert(const_iterator __p, _InputIterator __beg, _InputIterator __end)
01273         {
01274           _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
01275           const size_type __pos = __p - begin();
01276           this->replace(__p, __p, __beg, __end);
01277           return iterator(this->_M_data() + __pos);
01278         }
01279 #else
01280       /**
01281        *  @brief  Insert a range of characters.
01282        *  @param __p  Iterator referencing location in string to insert at.
01283        *  @param __beg  Start of range.
01284        *  @param __end  End of range.
01285        *  @throw  std::length_error  If new length exceeds @c max_size().
01286        *
01287        *  Inserts characters in range [__beg,__end).  If adding
01288        *  characters causes the length to exceed max_size(),
01289        *  length_error is thrown.  The value of the string doesn't
01290        *  change if an error is thrown.
01291       */
01292       template<class _InputIterator>
01293         void
01294         insert(iterator __p, _InputIterator __beg, _InputIterator __end)
01295         { this->replace(__p, __p, __beg, __end); }
01296 #endif
01297 
01298 #if __cplusplus >= 201103L
01299       /**
01300        *  @brief  Insert an initializer_list of characters.
01301        *  @param __p  Iterator referencing location in string to insert at.
01302        *  @param __l  The initializer_list of characters to insert.
01303        *  @throw  std::length_error  If new length exceeds @c max_size().
01304        */
01305       void
01306       insert(iterator __p, initializer_list<_CharT> __l)
01307       {
01308         _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
01309         this->insert(__p - begin(), __l.begin(), __l.size());
01310       }
01311 #endif // C++11
01312 
01313       /**
01314        *  @brief  Insert value of a string.
01315        *  @param __pos1  Iterator referencing location in string to insert at.
01316        *  @param __str  The string to insert.
01317        *  @return  Reference to this string.
01318        *  @throw  std::length_error  If new length exceeds @c max_size().
01319        *
01320        *  Inserts value of @a __str starting at @a __pos1.  If adding
01321        *  characters causes the length to exceed max_size(),
01322        *  length_error is thrown.  The value of the string doesn't
01323        *  change if an error is thrown.
01324       */
01325       basic_string&
01326       insert(size_type __pos1, const basic_string& __str)
01327       { return this->replace(__pos1, size_type(0),
01328                              __str._M_data(), __str.size()); }
01329 
01330       /**
01331        *  @brief  Insert a substring.
01332        *  @param __pos1  Iterator referencing location in string to insert at.
01333        *  @param __str  The string to insert.
01334        *  @param __pos2  Start of characters in str to insert.
01335        *  @param __n  Number of characters to insert.
01336        *  @return  Reference to this string.
01337        *  @throw  std::length_error  If new length exceeds @c max_size().
01338        *  @throw  std::out_of_range  If @a pos1 > size() or
01339        *  @a __pos2 > @a str.size().
01340        *
01341        *  Starting at @a pos1, insert @a __n character of @a __str
01342        *  beginning with @a __pos2.  If adding characters causes the
01343        *  length to exceed max_size(), length_error is thrown.  If @a
01344        *  __pos1 is beyond the end of this string or @a __pos2 is
01345        *  beyond the end of @a __str, out_of_range is thrown.  The
01346        *  value of the string doesn't change if an error is thrown.
01347       */
01348       basic_string&
01349       insert(size_type __pos1, const basic_string& __str,
01350              size_type __pos2, size_type __n)
01351       { return this->replace(__pos1, size_type(0), __str._M_data()
01352                              + __str._M_check(__pos2, "basic_string::insert"),
01353                              __str._M_limit(__pos2, __n)); }
01354 
01355       /**
01356        *  @brief  Insert a C substring.
01357        *  @param __pos  Iterator referencing location in string to insert at.
01358        *  @param __s  The C string to insert.
01359        *  @param __n  The number of characters to insert.
01360        *  @return  Reference to this string.
01361        *  @throw  std::length_error  If new length exceeds @c max_size().
01362        *  @throw  std::out_of_range  If @a __pos is beyond the end of this
01363        *  string.
01364        *
01365        *  Inserts the first @a __n characters of @a __s starting at @a
01366        *  __pos.  If adding characters causes the length to exceed
01367        *  max_size(), length_error is thrown.  If @a __pos is beyond
01368        *  end(), out_of_range is thrown.  The value of the string
01369        *  doesn't change if an error is thrown.
01370       */
01371       basic_string&
01372       insert(size_type __pos, const _CharT* __s, size_type __n)
01373       { return this->replace(__pos, size_type(0), __s, __n); }
01374 
01375       /**
01376        *  @brief  Insert a C string.
01377        *  @param __pos  Iterator referencing location in string to insert at.
01378        *  @param __s  The C string to insert.
01379        *  @return  Reference to this string.
01380        *  @throw  std::length_error  If new length exceeds @c max_size().
01381        *  @throw  std::out_of_range  If @a pos is beyond the end of this
01382        *  string.
01383        *
01384        *  Inserts the first @a n characters of @a __s starting at @a __pos.  If
01385        *  adding characters causes the length to exceed max_size(),
01386        *  length_error is thrown.  If @a __pos is beyond end(), out_of_range is
01387        *  thrown.  The value of the string doesn't change if an error is
01388        *  thrown.
01389       */
01390       basic_string&
01391       insert(size_type __pos, const _CharT* __s)
01392       {
01393         __glibcxx_requires_string(__s);
01394         return this->replace(__pos, size_type(0), __s,
01395                              traits_type::length(__s));
01396       }
01397 
01398       /**
01399        *  @brief  Insert multiple characters.
01400        *  @param __pos  Index in string to insert at.
01401        *  @param __n  Number of characters to insert
01402        *  @param __c  The character to insert.
01403        *  @return  Reference to this string.
01404        *  @throw  std::length_error  If new length exceeds @c max_size().
01405        *  @throw  std::out_of_range  If @a __pos is beyond the end of this
01406        *  string.
01407        *
01408        *  Inserts @a __n copies of character @a __c starting at index
01409        *  @a __pos.  If adding characters causes the length to exceed
01410        *  max_size(), length_error is thrown.  If @a __pos > length(),
01411        *  out_of_range is thrown.  The value of the string doesn't
01412        *  change if an error is thrown.
01413       */
01414       basic_string&
01415       insert(size_type __pos, size_type __n, _CharT __c)
01416       { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
01417                               size_type(0), __n, __c); }
01418 
01419       /**
01420        *  @brief  Insert one character.
01421        *  @param __p  Iterator referencing position in string to insert at.
01422        *  @param __c  The character to insert.
01423        *  @return  Iterator referencing newly inserted char.
01424        *  @throw  std::length_error  If new length exceeds @c max_size().
01425        *
01426        *  Inserts character @a __c at position referenced by @a __p.
01427        *  If adding character causes the length to exceed max_size(),
01428        *  length_error is thrown.  If @a __p is beyond end of string,
01429        *  out_of_range is thrown.  The value of the string doesn't
01430        *  change if an error is thrown.
01431       */
01432       iterator
01433       insert(__const_iterator __p, _CharT __c)
01434       {
01435         _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
01436         const size_type __pos = __p - begin();
01437         _M_replace_aux(__pos, size_type(0), size_type(1), __c);
01438         return iterator(_M_data() + __pos);
01439       }
01440 
01441       /**
01442        *  @brief  Remove characters.
01443        *  @param __pos  Index of first character to remove (default 0).
01444        *  @param __n  Number of characters to remove (default remainder).
01445        *  @return  Reference to this string.
01446        *  @throw  std::out_of_range  If @a pos is beyond the end of this
01447        *  string.
01448        *
01449        *  Removes @a __n characters from this string starting at @a
01450        *  __pos.  The length of the string is reduced by @a __n.  If
01451        *  there are < @a __n characters to remove, the remainder of
01452        *  the string is truncated.  If @a __p is beyond end of string,
01453        *  out_of_range is thrown.  The value of the string doesn't
01454        *  change if an error is thrown.
01455       */
01456       basic_string&
01457       erase(size_type __pos = 0, size_type __n = npos)
01458       {
01459         this->_M_erase(_M_check(__pos, "basic_string::erase"),
01460                        _M_limit(__pos, __n));
01461         return *this;
01462       }
01463 
01464       /**
01465        *  @brief  Remove one character.
01466        *  @param __position  Iterator referencing the character to remove.
01467        *  @return  iterator referencing same location after removal.
01468        *
01469        *  Removes the character at @a __position from this string. The value
01470        *  of the string doesn't change if an error is thrown.
01471       */
01472       iterator
01473       erase(__const_iterator __position)
01474       {
01475         _GLIBCXX_DEBUG_PEDASSERT(__position >= begin()
01476                                  && __position < end());
01477         const size_type __pos = __position - begin();
01478         this->_M_erase(__pos, size_type(1));
01479         return iterator(_M_data() + __pos);
01480       }
01481 
01482       /**
01483        *  @brief  Remove a range of characters.
01484        *  @param __first  Iterator referencing the first character to remove.
01485        *  @param __last  Iterator referencing the end of the range.
01486        *  @return  Iterator referencing location of first after removal.
01487        *
01488        *  Removes the characters in the range [first,last) from this string.
01489        *  The value of the string doesn't change if an error is thrown.
01490       */
01491       iterator
01492       erase(__const_iterator __first, __const_iterator __last)
01493       {
01494         _GLIBCXX_DEBUG_PEDASSERT(__first >= begin() && __first <= __last
01495                                  && __last <= end());
01496         const size_type __pos = __first - begin();
01497         this->_M_erase(__pos, __last - __first);
01498         return iterator(this->_M_data() + __pos);
01499       }
01500 
01501 #if __cplusplus >= 201103L
01502       /**
01503        *  @brief  Remove the last character.
01504        *
01505        *  The string must be non-empty.
01506        */
01507       void
01508       pop_back() noexcept
01509       { _M_erase(size()-1, 1); }
01510 #endif // C++11
01511 
01512       /**
01513        *  @brief  Replace characters with value from another string.
01514        *  @param __pos  Index of first character to replace.
01515        *  @param __n  Number of characters to be replaced.
01516        *  @param __str  String to insert.
01517        *  @return  Reference to this string.
01518        *  @throw  std::out_of_range  If @a pos is beyond the end of this
01519        *  string.
01520        *  @throw  std::length_error  If new length exceeds @c max_size().
01521        *
01522        *  Removes the characters in the range [__pos,__pos+__n) from
01523        *  this string.  In place, the value of @a __str is inserted.
01524        *  If @a __pos is beyond end of string, out_of_range is thrown.
01525        *  If the length of the result exceeds max_size(), length_error
01526        *  is thrown.  The value of the string doesn't change if an
01527        *  error is thrown.
01528       */
01529       basic_string&
01530       replace(size_type __pos, size_type __n, const basic_string& __str)
01531       { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
01532 
01533       /**
01534        *  @brief  Replace characters with value from another string.
01535        *  @param __pos1  Index of first character to replace.
01536        *  @param __n1  Number of characters to be replaced.
01537        *  @param __str  String to insert.
01538        *  @param __pos2  Index of first character of str to use.
01539        *  @param __n2  Number of characters from str to use.
01540        *  @return  Reference to this string.
01541        *  @throw  std::out_of_range  If @a __pos1 > size() or @a __pos2 >
01542        *  __str.size().
01543        *  @throw  std::length_error  If new length exceeds @c max_size().
01544        *
01545        *  Removes the characters in the range [__pos1,__pos1 + n) from this
01546        *  string.  In place, the value of @a __str is inserted.  If @a __pos is
01547        *  beyond end of string, out_of_range is thrown.  If the length of the
01548        *  result exceeds max_size(), length_error is thrown.  The value of the
01549        *  string doesn't change if an error is thrown.
01550       */
01551       basic_string&
01552       replace(size_type __pos1, size_type __n1, const basic_string& __str,
01553               size_type __pos2, size_type __n2)
01554       { return this->replace(__pos1, __n1, __str._M_data()
01555                              + __str._M_check(__pos2, "basic_string::replace"),
01556                              __str._M_limit(__pos2, __n2)); }
01557 
01558       /**
01559        *  @brief  Replace characters with value of a C substring.
01560        *  @param __pos  Index of first character to replace.
01561        *  @param __n1  Number of characters to be replaced.
01562        *  @param __s  C string to insert.
01563        *  @param __n2  Number of characters from @a s to use.
01564        *  @return  Reference to this string.
01565        *  @throw  std::out_of_range  If @a pos1 > size().
01566        *  @throw  std::length_error  If new length exceeds @c max_size().
01567        *
01568        *  Removes the characters in the range [__pos,__pos + __n1)
01569        *  from this string.  In place, the first @a __n2 characters of
01570        *  @a __s are inserted, or all of @a __s if @a __n2 is too large.  If
01571        *  @a __pos is beyond end of string, out_of_range is thrown.  If
01572        *  the length of result exceeds max_size(), length_error is
01573        *  thrown.  The value of the string doesn't change if an error
01574        *  is thrown.
01575       */
01576       basic_string&
01577       replace(size_type __pos, size_type __n1, const _CharT* __s,
01578               size_type __n2)
01579       {
01580         __glibcxx_requires_string_len(__s, __n2);
01581         return _M_replace(_M_check(__pos, "basic_string::replace"),
01582                           _M_limit(__pos, __n1), __s, __n2);
01583       }
01584 
01585       /**
01586        *  @brief  Replace characters with value of a C string.
01587        *  @param __pos  Index of first character to replace.
01588        *  @param __n1  Number of characters to be replaced.
01589        *  @param __s  C string to insert.
01590        *  @return  Reference to this string.
01591        *  @throw  std::out_of_range  If @a pos > size().
01592        *  @throw  std::length_error  If new length exceeds @c max_size().
01593        *
01594        *  Removes the characters in the range [__pos,__pos + __n1)
01595        *  from this string.  In place, the characters of @a __s are
01596        *  inserted.  If @a __pos is beyond end of string, out_of_range
01597        *  is thrown.  If the length of result exceeds max_size(),
01598        *  length_error is thrown.  The value of the string doesn't
01599        *  change if an error is thrown.
01600       */
01601       basic_string&
01602       replace(size_type __pos, size_type __n1, const _CharT* __s)
01603       {
01604         __glibcxx_requires_string(__s);
01605         return this->replace(__pos, __n1, __s, traits_type::length(__s));
01606       }
01607 
01608       /**
01609        *  @brief  Replace characters with multiple characters.
01610        *  @param __pos  Index of first character to replace.
01611        *  @param __n1  Number of characters to be replaced.
01612        *  @param __n2  Number of characters to insert.
01613        *  @param __c  Character to insert.
01614        *  @return  Reference to this string.
01615        *  @throw  std::out_of_range  If @a __pos > size().
01616        *  @throw  std::length_error  If new length exceeds @c max_size().
01617        *
01618        *  Removes the characters in the range [pos,pos + n1) from this
01619        *  string.  In place, @a __n2 copies of @a __c are inserted.
01620        *  If @a __pos is beyond end of string, out_of_range is thrown.
01621        *  If the length of result exceeds max_size(), length_error is
01622        *  thrown.  The value of the string doesn't change if an error
01623        *  is thrown.
01624       */
01625       basic_string&
01626       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
01627       { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
01628                               _M_limit(__pos, __n1), __n2, __c); }
01629 
01630       /**
01631        *  @brief  Replace range of characters with string.
01632        *  @param __i1  Iterator referencing start of range to replace.
01633        *  @param __i2  Iterator referencing end of range to replace.
01634        *  @param __str  String value to insert.
01635        *  @return  Reference to this string.
01636        *  @throw  std::length_error  If new length exceeds @c max_size().
01637        *
01638        *  Removes the characters in the range [__i1,__i2).  In place,
01639        *  the value of @a __str is inserted.  If the length of result
01640        *  exceeds max_size(), length_error is thrown.  The value of
01641        *  the string doesn't change if an error is thrown.
01642       */
01643       basic_string&
01644       replace(__const_iterator __i1, __const_iterator __i2,
01645               const basic_string& __str)
01646       { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
01647 
01648       /**
01649        *  @brief  Replace range of characters with C substring.
01650        *  @param __i1  Iterator referencing start of range to replace.
01651        *  @param __i2  Iterator referencing end of range to replace.
01652        *  @param __s  C string value to insert.
01653        *  @param __n  Number of characters from s to insert.
01654        *  @return  Reference to this string.
01655        *  @throw  std::length_error  If new length exceeds @c max_size().
01656        *
01657        *  Removes the characters in the range [__i1,__i2).  In place,
01658        *  the first @a __n characters of @a __s are inserted.  If the
01659        *  length of result exceeds max_size(), length_error is thrown.
01660        *  The value of the string doesn't change if an error is
01661        *  thrown.
01662       */
01663       basic_string&
01664       replace(__const_iterator __i1, __const_iterator __i2,
01665               const _CharT* __s, size_type __n)
01666       {
01667         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
01668                                  && __i2 <= end());
01669         return this->replace(__i1 - begin(), __i2 - __i1, __s, __n);
01670       }
01671 
01672       /**
01673        *  @brief  Replace range of characters with C string.
01674        *  @param __i1  Iterator referencing start of range to replace.
01675        *  @param __i2  Iterator referencing end of range to replace.
01676        *  @param __s  C string value to insert.
01677        *  @return  Reference to this string.
01678        *  @throw  std::length_error  If new length exceeds @c max_size().
01679        *
01680        *  Removes the characters in the range [__i1,__i2).  In place,
01681        *  the characters of @a __s are inserted.  If the length of
01682        *  result exceeds max_size(), length_error is thrown.  The
01683        *  value of the string doesn't change if an error is thrown.
01684       */
01685       basic_string&
01686       replace(__const_iterator __i1, __const_iterator __i2, const _CharT* __s)
01687       {
01688         __glibcxx_requires_string(__s);
01689         return this->replace(__i1, __i2, __s, traits_type::length(__s));
01690       }
01691 
01692       /**
01693        *  @brief  Replace range of characters with multiple characters
01694        *  @param __i1  Iterator referencing start of range to replace.
01695        *  @param __i2  Iterator referencing end of range to replace.
01696        *  @param __n  Number of characters to insert.
01697        *  @param __c  Character to insert.
01698        *  @return  Reference to this string.
01699        *  @throw  std::length_error  If new length exceeds @c max_size().
01700        *
01701        *  Removes the characters in the range [__i1,__i2).  In place,
01702        *  @a __n copies of @a __c are inserted.  If the length of
01703        *  result exceeds max_size(), length_error is thrown.  The
01704        *  value of the string doesn't change if an error is thrown.
01705       */
01706       basic_string&
01707       replace(__const_iterator __i1, __const_iterator __i2, size_type __n,
01708               _CharT __c)
01709       {
01710         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
01711                                  && __i2 <= end());
01712         return _M_replace_aux(__i1 - begin(), __i2 - __i1, __n, __c);
01713       }
01714 
01715       /**
01716        *  @brief  Replace range of characters with range.
01717        *  @param __i1  Iterator referencing start of range to replace.
01718        *  @param __i2  Iterator referencing end of range to replace.
01719        *  @param __k1  Iterator referencing start of range to insert.
01720        *  @param __k2  Iterator referencing end of range to insert.
01721        *  @return  Reference to this string.
01722        *  @throw  std::length_error  If new length exceeds @c max_size().
01723        *
01724        *  Removes the characters in the range [__i1,__i2).  In place,
01725        *  characters in the range [__k1,__k2) are inserted.  If the
01726        *  length of result exceeds max_size(), length_error is thrown.
01727        *  The value of the string doesn't change if an error is
01728        *  thrown.
01729       */
01730 #if __cplusplus >= 201103L
01731       template<class _InputIterator,
01732                typename = std::_RequireInputIter<_InputIterator>>
01733         basic_string&
01734         replace(const_iterator __i1, const_iterator __i2,
01735                 _InputIterator __k1, _InputIterator __k2)
01736         {
01737           _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
01738                                    && __i2 <= end());
01739           __glibcxx_requires_valid_range(__k1, __k2);
01740           return this->_M_replace_dispatch(__i1, __i2, __k1, __k2,
01741                                            std::__false_type());
01742         }
01743 #else
01744       template<class _InputIterator>
01745 #ifdef _GLIBCXX_DISAMBIGUATE_REPLACE_INST
01746         typename __enable_if_not_native_iterator<_InputIterator>::__type
01747 #else
01748         basic_string&
01749 #endif
01750         replace(iterator __i1, iterator __i2,
01751                 _InputIterator __k1, _InputIterator __k2)
01752         {
01753           _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
01754                                    && __i2 <= end());
01755           __glibcxx_requires_valid_range(__k1, __k2);
01756           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
01757           return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
01758         }
01759 #endif
01760 
01761       // Specializations for the common case of pointer and iterator:
01762       // useful to avoid the overhead of temporary buffering in _M_replace.
01763       basic_string&
01764       replace(__const_iterator __i1, __const_iterator __i2,
01765               _CharT* __k1, _CharT* __k2)
01766       {
01767         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
01768                                  && __i2 <= end());
01769         __glibcxx_requires_valid_range(__k1, __k2);
01770         return this->replace(__i1 - begin(), __i2 - __i1,
01771                              __k1, __k2 - __k1);
01772       }
01773 
01774       basic_string&
01775       replace(__const_iterator __i1, __const_iterator __i2,
01776               const _CharT* __k1, const _CharT* __k2)
01777       {
01778         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
01779                                  && __i2 <= end());
01780         __glibcxx_requires_valid_range(__k1, __k2);
01781         return this->replace(__i1 - begin(), __i2 - __i1,
01782                              __k1, __k2 - __k1);
01783       }
01784 
01785       basic_string&
01786       replace(__const_iterator __i1, __const_iterator __i2,
01787               iterator __k1, iterator __k2)
01788       {
01789         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
01790                                  && __i2 <= end());
01791         __glibcxx_requires_valid_range(__k1, __k2);
01792         return this->replace(__i1 - begin(), __i2 - __i1,
01793                              __k1.base(), __k2 - __k1);
01794       }
01795 
01796       basic_string&
01797       replace(__const_iterator __i1, __const_iterator __i2,
01798               const_iterator __k1, const_iterator __k2)
01799       {
01800         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
01801                                  && __i2 <= end());
01802         __glibcxx_requires_valid_range(__k1, __k2);
01803         return this->replace(__i1 - begin(), __i2 - __i1,
01804                              __k1.base(), __k2 - __k1);
01805       }
01806 
01807 #if __cplusplus >= 201103L
01808       /**
01809        *  @brief  Replace range of characters with initializer_list.
01810        *  @param __i1  Iterator referencing start of range to replace.
01811        *  @param __i2  Iterator referencing end of range to replace.
01812        *  @param __l  The initializer_list of characters to insert.
01813        *  @return  Reference to this string.
01814        *  @throw  std::length_error  If new length exceeds @c max_size().
01815        *
01816        *  Removes the characters in the range [__i1,__i2).  In place,
01817        *  characters in the range [__k1,__k2) are inserted.  If the
01818        *  length of result exceeds max_size(), length_error is thrown.
01819        *  The value of the string doesn't change if an error is
01820        *  thrown.
01821       */
01822       basic_string& replace(const_iterator __i1, const_iterator __i2,
01823                             initializer_list<_CharT> __l)
01824       { return this->replace(__i1, __i2, __l.begin(), __l.end()); }
01825 #endif // C++11
01826 
01827     private:
01828       template<class _Integer>
01829         basic_string&
01830         _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
01831                             _Integer __n, _Integer __val, __true_type)
01832         { return _M_replace_aux(__i1 - begin(), __i2 - __i1, __n, __val); }
01833 
01834       template<class _InputIterator>
01835         basic_string&
01836         _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
01837                             _InputIterator __k1, _InputIterator __k2,
01838                             __false_type);
01839 
01840       basic_string&
01841       _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
01842                      _CharT __c);
01843 
01844       basic_string&
01845       _M_replace(size_type __pos, size_type __len1, const _CharT* __s,
01846                  const size_type __len2);
01847 
01848       basic_string&
01849       _M_append(const _CharT* __s, size_type __n);
01850 
01851     public:
01852 
01853       /**
01854        *  @brief  Copy substring into C string.
01855        *  @param __s  C string to copy value into.
01856        *  @param __n  Number of characters to copy.
01857        *  @param __pos  Index of first character to copy.
01858        *  @return  Number of characters actually copied
01859        *  @throw  std::out_of_range  If __pos > size().
01860        *
01861        *  Copies up to @a __n characters starting at @a __pos into the
01862        *  C string @a __s.  If @a __pos is %greater than size(),
01863        *  out_of_range is thrown.
01864       */
01865       size_type
01866       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
01867 
01868       /**
01869        *  @brief  Swap contents with another string.
01870        *  @param __s  String to swap with.
01871        *
01872        *  Exchanges the contents of this string with that of @a __s in constant
01873        *  time.
01874       */
01875       void
01876       swap(basic_string& __s) _GLIBCXX_NOEXCEPT;
01877 
01878       // String operations:
01879       /**
01880        *  @brief  Return const pointer to null-terminated contents.
01881        *
01882        *  This is a handle to internal data.  Do not modify or dire things may
01883        *  happen.
01884       */
01885       const _CharT*
01886       c_str() const _GLIBCXX_NOEXCEPT
01887       { return _M_data(); }
01888 
01889       /**
01890        *  @brief  Return const pointer to contents.
01891        *
01892        *  This is a handle to internal data.  Do not modify or dire things may
01893        *  happen.
01894       */
01895       const _CharT*
01896       data() const _GLIBCXX_NOEXCEPT
01897       { return _M_data(); }
01898 
01899       /**
01900        *  @brief  Return copy of allocator used to construct this string.
01901       */
01902       allocator_type
01903       get_allocator() const _GLIBCXX_NOEXCEPT
01904       { return _M_get_allocator(); }
01905 
01906       /**
01907        *  @brief  Find position of a C substring.
01908        *  @param __s  C string to locate.
01909        *  @param __pos  Index of character to search from.
01910        *  @param __n  Number of characters from @a s to search for.
01911        *  @return  Index of start of first occurrence.
01912        *
01913        *  Starting from @a __pos, searches forward for the first @a
01914        *  __n characters in @a __s within this string.  If found,
01915        *  returns the index where it begins.  If not found, returns
01916        *  npos.
01917       */
01918       size_type
01919       find(const _CharT* __s, size_type __pos, size_type __n) const;
01920 
01921       /**
01922        *  @brief  Find position of a string.
01923        *  @param __str  String to locate.
01924        *  @param __pos  Index of character to search from (default 0).
01925        *  @return  Index of start of first occurrence.
01926        *
01927        *  Starting from @a __pos, searches forward for value of @a __str within
01928        *  this string.  If found, returns the index where it begins.  If not
01929        *  found, returns npos.
01930       */
01931       size_type
01932       find(const basic_string& __str, size_type __pos = 0) const
01933         _GLIBCXX_NOEXCEPT
01934       { return this->find(__str.data(), __pos, __str.size()); }
01935 
01936       /**
01937        *  @brief  Find position of a C string.
01938        *  @param __s  C string to locate.
01939        *  @param __pos  Index of character to search from (default 0).
01940        *  @return  Index of start of first occurrence.
01941        *
01942        *  Starting from @a __pos, searches forward for the value of @a
01943        *  __s within this string.  If found, returns the index where
01944        *  it begins.  If not found, returns npos.
01945       */
01946       size_type
01947       find(const _CharT* __s, size_type __pos = 0) const
01948       {
01949         __glibcxx_requires_string(__s);
01950         return this->find(__s, __pos, traits_type::length(__s));
01951       }
01952 
01953       /**
01954        *  @brief  Find position of a character.
01955        *  @param __c  Character to locate.
01956        *  @param __pos  Index of character to search from (default 0).
01957        *  @return  Index of first occurrence.
01958        *
01959        *  Starting from @a __pos, searches forward for @a __c within
01960        *  this string.  If found, returns the index where it was
01961        *  found.  If not found, returns npos.
01962       */
01963       size_type
01964       find(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT;
01965 
01966       /**
01967        *  @brief  Find last position of a string.
01968        *  @param __str  String to locate.
01969        *  @param __pos  Index of character to search back from (default end).
01970        *  @return  Index of start of last occurrence.
01971        *
01972        *  Starting from @a __pos, searches backward for value of @a
01973        *  __str within this string.  If found, returns the index where
01974        *  it begins.  If not found, returns npos.
01975       */
01976       size_type
01977       rfind(const basic_string& __str, size_type __pos = npos) const
01978         _GLIBCXX_NOEXCEPT
01979       { return this->rfind(__str.data(), __pos, __str.size()); }
01980 
01981       /**
01982        *  @brief  Find last position of a C substring.
01983        *  @param __s  C string to locate.
01984        *  @param __pos  Index of character to search back from.
01985        *  @param __n  Number of characters from s to search for.
01986        *  @return  Index of start of last occurrence.
01987        *
01988        *  Starting from @a __pos, searches backward for the first @a
01989        *  __n characters in @a __s within this string.  If found,
01990        *  returns the index where it begins.  If not found, returns
01991        *  npos.
01992       */
01993       size_type
01994       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
01995 
01996       /**
01997        *  @brief  Find last position of a C string.
01998        *  @param __s  C string to locate.
01999        *  @param __pos  Index of character to start search at (default end).
02000        *  @return  Index of start of  last occurrence.
02001        *
02002        *  Starting from @a __pos, searches backward for the value of
02003        *  @a __s within this string.  If found, returns the index
02004        *  where it begins.  If not found, returns npos.
02005       */
02006       size_type
02007       rfind(const _CharT* __s, size_type __pos = npos) const
02008       {
02009         __glibcxx_requires_string(__s);
02010         return this->rfind(__s, __pos, traits_type::length(__s));
02011       }
02012 
02013       /**
02014        *  @brief  Find last position of a character.
02015        *  @param __c  Character to locate.
02016        *  @param __pos  Index of character to search back from (default end).
02017        *  @return  Index of last occurrence.
02018        *
02019        *  Starting from @a __pos, searches backward for @a __c within
02020        *  this string.  If found, returns the index where it was
02021        *  found.  If not found, returns npos.
02022       */
02023       size_type
02024       rfind(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT;
02025 
02026       /**
02027        *  @brief  Find position of a character of string.
02028        *  @param __str  String containing characters to locate.
02029        *  @param __pos  Index of character to search from (default 0).
02030        *  @return  Index of first occurrence.
02031        *
02032        *  Starting from @a __pos, searches forward for one of the
02033        *  characters of @a __str within this string.  If found,
02034        *  returns the index where it was found.  If not found, returns
02035        *  npos.
02036       */
02037       size_type
02038       find_first_of(const basic_string& __str, size_type __pos = 0) const
02039         _GLIBCXX_NOEXCEPT
02040       { return this->find_first_of(__str.data(), __pos, __str.size()); }
02041 
02042       /**
02043        *  @brief  Find position of a character of C substring.
02044        *  @param __s  String containing characters to locate.
02045        *  @param __pos  Index of character to search from.
02046        *  @param __n  Number of characters from s to search for.
02047        *  @return  Index of first occurrence.
02048        *
02049        *  Starting from @a __pos, searches forward for one of the
02050        *  first @a __n characters of @a __s within this string.  If
02051        *  found, returns the index where it was found.  If not found,
02052        *  returns npos.
02053       */
02054       size_type
02055       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
02056 
02057       /**
02058        *  @brief  Find position of a character of C string.
02059        *  @param __s  String containing characters to locate.
02060        *  @param __pos  Index of character to search from (default 0).
02061        *  @return  Index of first occurrence.
02062        *
02063        *  Starting from @a __pos, searches forward for one of the
02064        *  characters of @a __s within this string.  If found, returns
02065        *  the index where it was found.  If not found, returns npos.
02066       */
02067       size_type
02068       find_first_of(const _CharT* __s, size_type __pos = 0) const
02069       {
02070         __glibcxx_requires_string(__s);
02071         return this->find_first_of(__s, __pos, traits_type::length(__s));
02072       }
02073 
02074       /**
02075        *  @brief  Find position of a character.
02076        *  @param __c  Character to locate.
02077        *  @param __pos  Index of character to search from (default 0).
02078        *  @return  Index of first occurrence.
02079        *
02080        *  Starting from @a __pos, searches forward for the character
02081        *  @a __c within this string.  If found, returns the index
02082        *  where it was found.  If not found, returns npos.
02083        *
02084        *  Note: equivalent to find(__c, __pos).
02085       */
02086       size_type
02087       find_first_of(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT
02088       { return this->find(__c, __pos); }
02089 
02090       /**
02091        *  @brief  Find last position of a character of string.
02092        *  @param __str  String containing characters to locate.
02093        *  @param __pos  Index of character to search back from (default end).
02094        *  @return  Index of last occurrence.
02095        *
02096        *  Starting from @a __pos, searches backward for one of the
02097        *  characters of @a __str within this string.  If found,
02098        *  returns the index where it was found.  If not found, returns
02099        *  npos.
02100       */
02101       size_type
02102       find_last_of(const basic_string& __str, size_type __pos = npos) const
02103         _GLIBCXX_NOEXCEPT
02104       { return this->find_last_of(__str.data(), __pos, __str.size()); }
02105 
02106       /**
02107        *  @brief  Find last position of a character of C substring.
02108        *  @param __s  C string containing characters to locate.
02109        *  @param __pos  Index of character to search back from.
02110        *  @param __n  Number of characters from s to search for.
02111        *  @return  Index of last occurrence.
02112        *
02113        *  Starting from @a __pos, searches backward for one of the
02114        *  first @a __n characters of @a __s within this string.  If
02115        *  found, returns the index where it was found.  If not found,
02116        *  returns npos.
02117       */
02118       size_type
02119       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
02120 
02121       /**
02122        *  @brief  Find last position of a character of C string.
02123        *  @param __s  C string containing characters to locate.
02124        *  @param __pos  Index of character to search back from (default end).
02125        *  @return  Index of last occurrence.
02126        *
02127        *  Starting from @a __pos, searches backward for one of the
02128        *  characters of @a __s within this string.  If found, returns
02129        *  the index where it was found.  If not found, returns npos.
02130       */
02131       size_type
02132       find_last_of(const _CharT* __s, size_type __pos = npos) const
02133       {
02134         __glibcxx_requires_string(__s);
02135         return this->find_last_of(__s, __pos, traits_type::length(__s));
02136       }
02137 
02138       /**
02139        *  @brief  Find last position of a character.
02140        *  @param __c  Character to locate.
02141        *  @param __pos  Index of character to search back from (default end).
02142        *  @return  Index of last occurrence.
02143        *
02144        *  Starting from @a __pos, searches backward for @a __c within
02145        *  this string.  If found, returns the index where it was
02146        *  found.  If not found, returns npos.
02147        *
02148        *  Note: equivalent to rfind(__c, __pos).
02149       */
02150       size_type
02151       find_last_of(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT
02152       { return this->rfind(__c, __pos); }
02153 
02154       /**
02155        *  @brief  Find position of a character not in string.
02156        *  @param __str  String containing characters to avoid.
02157        *  @param __pos  Index of character to search from (default 0).
02158        *  @return  Index of first occurrence.
02159        *
02160        *  Starting from @a __pos, searches forward for a character not contained
02161        *  in @a __str within this string.  If found, returns the index where it
02162        *  was found.  If not found, returns npos.
02163       */
02164       size_type
02165       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
02166         _GLIBCXX_NOEXCEPT
02167       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
02168 
02169       /**
02170        *  @brief  Find position of a character not in C substring.
02171        *  @param __s  C string containing characters to avoid.
02172        *  @param __pos  Index of character to search from.
02173        *  @param __n  Number of characters from __s to consider.
02174        *  @return  Index of first occurrence.
02175        *
02176        *  Starting from @a __pos, searches forward for a character not
02177        *  contained in the first @a __n characters of @a __s within
02178        *  this string.  If found, returns the index where it was
02179        *  found.  If not found, returns npos.
02180       */
02181       size_type
02182       find_first_not_of(const _CharT* __s, size_type __pos,
02183                         size_type __n) const;
02184 
02185       /**
02186        *  @brief  Find position of a character not in C string.
02187        *  @param __s  C string containing characters to avoid.
02188        *  @param __pos  Index of character to search from (default 0).
02189        *  @return  Index of first occurrence.
02190        *
02191        *  Starting from @a __pos, searches forward for a character not
02192        *  contained in @a __s within this string.  If found, returns
02193        *  the index where it was found.  If not found, returns npos.
02194       */
02195       size_type
02196       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
02197       {
02198         __glibcxx_requires_string(__s);
02199         return this->find_first_not_of(__s, __pos, traits_type::length(__s));
02200       }
02201 
02202       /**
02203        *  @brief  Find position of a different character.
02204        *  @param __c  Character to avoid.
02205        *  @param __pos  Index of character to search from (default 0).
02206        *  @return  Index of first occurrence.
02207        *
02208        *  Starting from @a __pos, searches forward for a character
02209        *  other than @a __c within this string.  If found, returns the
02210        *  index where it was found.  If not found, returns npos.
02211       */
02212       size_type
02213       find_first_not_of(_CharT __c, size_type __pos = 0) const
02214         _GLIBCXX_NOEXCEPT;
02215 
02216       /**
02217        *  @brief  Find last position of a character not in string.
02218        *  @param __str  String containing characters to avoid.
02219        *  @param __pos  Index of character to search back from (default end).
02220        *  @return  Index of last occurrence.
02221        *
02222        *  Starting from @a __pos, searches backward for a character
02223        *  not contained in @a __str within this string.  If found,
02224        *  returns the index where it was found.  If not found, returns
02225        *  npos.
02226       */
02227       size_type
02228       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
02229         _GLIBCXX_NOEXCEPT
02230       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
02231 
02232       /**
02233        *  @brief  Find last position of a character not in C substring.
02234        *  @param __s  C string containing characters to avoid.
02235        *  @param __pos  Index of character to search back from.
02236        *  @param __n  Number of characters from s to consider.
02237        *  @return  Index of last occurrence.
02238        *
02239        *  Starting from @a __pos, searches backward for a character not
02240        *  contained in the first @a __n characters of @a __s within this string.
02241        *  If found, returns the index where it was found.  If not found,
02242        *  returns npos.
02243       */
02244       size_type
02245       find_last_not_of(const _CharT* __s, size_type __pos,
02246                        size_type __n) const;
02247       /**
02248        *  @brief  Find last position of a character not in C string.
02249        *  @param __s  C string containing characters to avoid.
02250        *  @param __pos  Index of character to search back from (default end).
02251        *  @return  Index of last occurrence.
02252        *
02253        *  Starting from @a __pos, searches backward for a character
02254        *  not contained in @a __s within this string.  If found,
02255        *  returns the index where it was found.  If not found, returns
02256        *  npos.
02257       */
02258       size_type
02259       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
02260       {
02261         __glibcxx_requires_string(__s);
02262         return this->find_last_not_of(__s, __pos, traits_type::length(__s));
02263       }
02264 
02265       /**
02266        *  @brief  Find last position of a different character.
02267        *  @param __c  Character to avoid.
02268        *  @param __pos  Index of character to search back from (default end).
02269        *  @return  Index of last occurrence.
02270        *
02271        *  Starting from @a __pos, searches backward for a character other than
02272        *  @a __c within this string.  If found, returns the index where it was
02273        *  found.  If not found, returns npos.
02274       */
02275       size_type
02276       find_last_not_of(_CharT __c, size_type __pos = npos) const
02277         _GLIBCXX_NOEXCEPT;
02278 
02279       /**
02280        *  @brief  Get a substring.
02281        *  @param __pos  Index of first character (default 0).
02282        *  @param __n  Number of characters in substring (default remainder).
02283        *  @return  The new string.
02284        *  @throw  std::out_of_range  If __pos > size().
02285        *
02286        *  Construct and return a new string using the @a __n
02287        *  characters starting at @a __pos.  If the string is too
02288        *  short, use the remainder of the characters.  If @a __pos is
02289        *  beyond the end of the string, out_of_range is thrown.
02290       */
02291       basic_string
02292       substr(size_type __pos = 0, size_type __n = npos) const
02293       { return basic_string(*this,
02294                             _M_check(__pos, "basic_string::substr"), __n); }
02295 
02296       /**
02297        *  @brief  Compare to a string.
02298        *  @param __str  String to compare against.
02299        *  @return  Integer < 0, 0, or > 0.
02300        *
02301        *  Returns an integer < 0 if this string is ordered before @a
02302        *  __str, 0 if their values are equivalent, or > 0 if this
02303        *  string is ordered after @a __str.  Determines the effective
02304        *  length rlen of the strings to compare as the smallest of
02305        *  size() and str.size().  The function then compares the two
02306        *  strings by calling traits::compare(data(), str.data(),rlen).
02307        *  If the result of the comparison is nonzero returns it,
02308        *  otherwise the shorter one is ordered first.
02309       */
02310       int
02311       compare(const basic_string& __str) const
02312       {
02313         const size_type __size = this->size();
02314         const size_type __osize = __str.size();
02315         const size_type __len = std::min(__size, __osize);
02316 
02317         int __r = traits_type::compare(_M_data(), __str.data(), __len);
02318         if (!__r)
02319           __r = _S_compare(__size, __osize);
02320         return __r;
02321       }
02322 
02323       /**
02324        *  @brief  Compare substring to a string.
02325        *  @param __pos  Index of first character of substring.
02326        *  @param __n  Number of characters in substring.
02327        *  @param __str  String to compare against.
02328        *  @return  Integer < 0, 0, or > 0.
02329        *
02330        *  Form the substring of this string from the @a __n characters
02331        *  starting at @a __pos.  Returns an integer < 0 if the
02332        *  substring is ordered before @a __str, 0 if their values are
02333        *  equivalent, or > 0 if the substring is ordered after @a
02334        *  __str.  Determines the effective length rlen of the strings
02335        *  to compare as the smallest of the length of the substring
02336        *  and @a __str.size().  The function then compares the two
02337        *  strings by calling
02338        *  traits::compare(substring.data(),str.data(),rlen).  If the
02339        *  result of the comparison is nonzero returns it, otherwise
02340        *  the shorter one is ordered first.
02341       */
02342       int
02343       compare(size_type __pos, size_type __n, const basic_string& __str) const;
02344 
02345       /**
02346        *  @brief  Compare substring to a substring.
02347        *  @param __pos1  Index of first character of substring.
02348        *  @param __n1  Number of characters in substring.
02349        *  @param __str  String to compare against.
02350        *  @param __pos2  Index of first character of substring of str.
02351        *  @param __n2  Number of characters in substring of str.
02352        *  @return  Integer < 0, 0, or > 0.
02353        *
02354        *  Form the substring of this string from the @a __n1
02355        *  characters starting at @a __pos1.  Form the substring of @a
02356        *  __str from the @a __n2 characters starting at @a __pos2.
02357        *  Returns an integer < 0 if this substring is ordered before
02358        *  the substring of @a __str, 0 if their values are equivalent,
02359        *  or > 0 if this substring is ordered after the substring of
02360        *  @a __str.  Determines the effective length rlen of the
02361        *  strings to compare as the smallest of the lengths of the
02362        *  substrings.  The function then compares the two strings by
02363        *  calling
02364        *  traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
02365        *  If the result of the comparison is nonzero returns it,
02366        *  otherwise the shorter one is ordered first.
02367       */
02368       int
02369       compare(size_type __pos1, size_type __n1, const basic_string& __str,
02370               size_type __pos2, size_type __n2) const;
02371 
02372       /**
02373        *  @brief  Compare to a C string.
02374        *  @param __s  C string to compare against.
02375        *  @return  Integer < 0, 0, or > 0.
02376        *
02377        *  Returns an integer < 0 if this string is ordered before @a __s, 0 if
02378        *  their values are equivalent, or > 0 if this string is ordered after
02379        *  @a __s.  Determines the effective length rlen of the strings to
02380        *  compare as the smallest of size() and the length of a string
02381        *  constructed from @a __s.  The function then compares the two strings
02382        *  by calling traits::compare(data(),s,rlen).  If the result of the
02383        *  comparison is nonzero returns it, otherwise the shorter one is
02384        *  ordered first.
02385       */
02386       int
02387       compare(const _CharT* __s) const;
02388 
02389       // _GLIBCXX_RESOLVE_LIB_DEFECTS
02390       // 5 String::compare specification questionable
02391       /**
02392        *  @brief  Compare substring to a C string.
02393        *  @param __pos  Index of first character of substring.
02394        *  @param __n1  Number of characters in substring.
02395        *  @param __s  C string to compare against.
02396        *  @return  Integer < 0, 0, or > 0.
02397        *
02398        *  Form the substring of this string from the @a __n1
02399        *  characters starting at @a pos.  Returns an integer < 0 if
02400        *  the substring is ordered before @a __s, 0 if their values
02401        *  are equivalent, or > 0 if the substring is ordered after @a
02402        *  __s.  Determines the effective length rlen of the strings to
02403        *  compare as the smallest of the length of the substring and
02404        *  the length of a string constructed from @a __s.  The
02405        *  function then compares the two string by calling
02406        *  traits::compare(substring.data(),__s,rlen).  If the result of
02407        *  the comparison is nonzero returns it, otherwise the shorter
02408        *  one is ordered first.
02409       */
02410       int
02411       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
02412 
02413       /**
02414        *  @brief  Compare substring against a character %array.
02415        *  @param __pos  Index of first character of substring.
02416        *  @param __n1  Number of characters in substring.
02417        *  @param __s  character %array to compare against.
02418        *  @param __n2  Number of characters of s.
02419        *  @return  Integer < 0, 0, or > 0.
02420        *
02421        *  Form the substring of this string from the @a __n1
02422        *  characters starting at @a __pos.  Form a string from the
02423        *  first @a __n2 characters of @a __s.  Returns an integer < 0
02424        *  if this substring is ordered before the string from @a __s,
02425        *  0 if their values are equivalent, or > 0 if this substring
02426        *  is ordered after the string from @a __s.  Determines the
02427        *  effective length rlen of the strings to compare as the
02428        *  smallest of the length of the substring and @a __n2.  The
02429        *  function then compares the two strings by calling
02430        *  traits::compare(substring.data(),s,rlen).  If the result of
02431        *  the comparison is nonzero returns it, otherwise the shorter
02432        *  one is ordered first.
02433        *
02434        *  NB: s must have at least n2 characters, &apos;\\0&apos; has
02435        *  no special meaning.
02436       */
02437       int
02438       compare(size_type __pos, size_type __n1, const _CharT* __s,
02439               size_type __n2) const;
02440   };
02441 _GLIBCXX_END_NAMESPACE_CXX11
02442 #else  // !_GLIBCXX_USE_CXX11_ABI
02443   // Reference-counted COW string implentation
02444 
02445   /**
02446    *  @class basic_string basic_string.h <string>
02447    *  @brief  Managing sequences of characters and character-like objects.
02448    *
02449    *  @ingroup strings
02450    *  @ingroup sequences
02451    *
02452    *  @tparam _CharT  Type of character
02453    *  @tparam _Traits  Traits for character type, defaults to
02454    *                   char_traits<_CharT>.
02455    *  @tparam _Alloc  Allocator type, defaults to allocator<_CharT>.
02456    *
02457    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
02458    *  <a href="tables.html#66">reversible container</a>, and a
02459    *  <a href="tables.html#67">sequence</a>.  Of the
02460    *  <a href="tables.html#68">optional sequence requirements</a>, only
02461    *  @c push_back, @c at, and @c %array access are supported.
02462    *
02463    *  @doctodo
02464    *
02465    *
02466    *  Documentation?  What's that?
02467    *  Nathan Myers <ncm@cantrip.org>.
02468    *
02469    *  A string looks like this:
02470    *
02471    *  @code
02472    *                                        [_Rep]
02473    *                                        _M_length
02474    *   [basic_string<char_type>]            _M_capacity
02475    *   _M_dataplus                          _M_refcount
02476    *   _M_p ---------------->               unnamed array of char_type
02477    *  @endcode
02478    *
02479    *  Where the _M_p points to the first character in the string, and
02480    *  you cast it to a pointer-to-_Rep and subtract 1 to get a
02481    *  pointer to the header.
02482    *
02483    *  This approach has the enormous advantage that a string object
02484    *  requires only one allocation.  All the ugliness is confined
02485    *  within a single %pair of inline functions, which each compile to
02486    *  a single @a add instruction: _Rep::_M_data(), and
02487    *  string::_M_rep(); and the allocation function which gets a
02488    *  block of raw bytes and with room enough and constructs a _Rep
02489    *  object at the front.
02490    *
02491    *  The reason you want _M_data pointing to the character %array and
02492    *  not the _Rep is so that the debugger can see the string
02493    *  contents. (Probably we should add a non-inline member to get
02494    *  the _Rep for the debugger to use, so users can check the actual
02495    *  string length.)
02496    *
02497    *  Note that the _Rep object is a POD so that you can have a
02498    *  static <em>empty string</em> _Rep object already @a constructed before
02499    *  static constructors have run.  The reference-count encoding is
02500    *  chosen so that a 0 indicates one reference, so you never try to
02501    *  destroy the empty-string _Rep object.
02502    *
02503    *  All but the last paragraph is considered pretty conventional
02504    *  for a C++ string implementation.
02505   */
02506   // 21.3  Template class basic_string
02507   template<typename _CharT, typename _Traits, typename _Alloc>
02508     class basic_string
02509     {
02510       typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;
02511 
02512       // Types:
02513     public:
02514       typedef _Traits                                       traits_type;
02515       typedef typename _Traits::char_type                   value_type;
02516       typedef _Alloc                                        allocator_type;
02517       typedef typename _CharT_alloc_type::size_type         size_type;
02518       typedef typename _CharT_alloc_type::difference_type   difference_type;
02519       typedef typename _CharT_alloc_type::reference         reference;
02520       typedef typename _CharT_alloc_type::const_reference   const_reference;
02521       typedef typename _CharT_alloc_type::pointer           pointer;
02522       typedef typename _CharT_alloc_type::const_pointer     const_pointer;
02523       typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
02524       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
02525                                                             const_iterator;
02526       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
02527       typedef std::reverse_iterator<iterator>               reverse_iterator;
02528 
02529     private:
02530       // _Rep: string representation
02531       //   Invariants:
02532       //   1. String really contains _M_length + 1 characters: due to 21.3.4
02533       //      must be kept null-terminated.
02534       //   2. _M_capacity >= _M_length
02535       //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).
02536       //   3. _M_refcount has three states:
02537       //      -1: leaked, one reference, no ref-copies allowed, non-const.
02538       //       0: one reference, non-const.
02539       //     n>0: n + 1 references, operations require a lock, const.
02540       //   4. All fields==0 is an empty string, given the extra storage
02541       //      beyond-the-end for a null terminator; thus, the shared
02542       //      empty string representation needs no constructor.
02543 
02544       struct _Rep_base
02545       {
02546         size_type               _M_length;
02547         size_type               _M_capacity;
02548         _Atomic_word            _M_refcount;
02549       };
02550 
02551       struct _Rep : _Rep_base
02552       {
02553         // Types:
02554         typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
02555 
02556         // (Public) Data members:
02557 
02558         // The maximum number of individual char_type elements of an
02559         // individual string is determined by _S_max_size. This is the
02560         // value that will be returned by max_size().  (Whereas npos
02561         // is the maximum number of bytes the allocator can allocate.)
02562         // If one was to divvy up the theoretical largest size string,
02563         // with a terminating character and m _CharT elements, it'd
02564         // look like this:
02565         // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
02566         // Solving for m:
02567         // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
02568         // In addition, this implementation quarters this amount.
02569         static const size_type  _S_max_size;
02570         static const _CharT     _S_terminal;
02571 
02572         // The following storage is init'd to 0 by the linker, resulting
02573         // (carefully) in an empty string with one reference.
02574         static size_type _S_empty_rep_storage[];
02575 
02576         static _Rep&
02577         _S_empty_rep() _GLIBCXX_NOEXCEPT
02578         { 
02579           // NB: Mild hack to avoid strict-aliasing warnings.  Note that
02580           // _S_empty_rep_storage is never modified and the punning should
02581           // be reasonably safe in this case.
02582           void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);
02583           return *reinterpret_cast<_Rep*>(__p);
02584         }
02585 
02586         bool
02587         _M_is_leaked() const _GLIBCXX_NOEXCEPT
02588         { return this->_M_refcount < 0; }
02589 
02590         bool
02591         _M_is_shared() const _GLIBCXX_NOEXCEPT
02592         { return this->_M_refcount > 0; }
02593 
02594         void
02595         _M_set_leaked() _GLIBCXX_NOEXCEPT
02596         { this->_M_refcount = -1; }
02597 
02598         void
02599         _M_set_sharable() _GLIBCXX_NOEXCEPT
02600         { this->_M_refcount = 0; }
02601 
02602         void
02603         _M_set_length_and_sharable(size_type __n) _GLIBCXX_NOEXCEPT
02604         {
02605 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
02606           if (__builtin_expect(this != &_S_empty_rep(), false))
02607 #endif
02608             {
02609               this->_M_set_sharable();  // One reference.
02610               this->_M_length = __n;
02611               traits_type::assign(this->_M_refdata()[__n], _S_terminal);
02612               // grrr. (per 21.3.4)
02613               // You cannot leave those LWG people alone for a second.
02614             }
02615         }
02616 
02617         _CharT*
02618         _M_refdata() throw()
02619         { return reinterpret_cast<_CharT*>(this + 1); }
02620 
02621         _CharT*
02622         _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
02623         {
02624           return (!_M_is_leaked() && __alloc1 == __alloc2)
02625                   ? _M_refcopy() : _M_clone(__alloc1);
02626         }
02627 
02628         // Create & Destroy
02629         static _Rep*
02630         _S_create(size_type, size_type, const _Alloc&);
02631 
02632         void
02633         _M_dispose(const _Alloc& __a) _GLIBCXX_NOEXCEPT
02634         {
02635 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
02636           if (__builtin_expect(this != &_S_empty_rep(), false))
02637 #endif
02638             {
02639               // Be race-detector-friendly.  For more info see bits/c++config.
02640               _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this->_M_refcount);
02641               if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
02642                                                          -1) <= 0)
02643                 {
02644                   _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);
02645                   _M_destroy(__a);
02646                 }
02647             }
02648         }  // XXX MT
02649 
02650         void
02651         _M_destroy(const _Alloc&) throw();
02652 
02653         _CharT*
02654         _M_refcopy() throw()
02655         {
02656 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
02657           if (__builtin_expect(this != &_S_empty_rep(), false))
02658 #endif
02659             __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
02660           return _M_refdata();
02661         }  // XXX MT
02662 
02663         _CharT*
02664         _M_clone(const _Alloc&, size_type __res = 0);
02665       };
02666 
02667       // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
02668       struct _Alloc_hider : _Alloc
02669       {
02670         _Alloc_hider(_CharT* __dat, const _Alloc& __a) _GLIBCXX_NOEXCEPT
02671         : _Alloc(__a), _M_p(__dat) { }
02672 
02673         _CharT* _M_p; // The actual data.
02674       };
02675 
02676     public:
02677       // Data Members (public):
02678       // NB: This is an unsigned type, and thus represents the maximum
02679       // size that the allocator can hold.
02680       ///  Value returned by various member functions when they fail.
02681       static const size_type    npos = static_cast<size_type>(-1);
02682 
02683     private:
02684       // Data Members (private):
02685       mutable _Alloc_hider      _M_dataplus;
02686 
02687       _CharT*
02688       _M_data() const _GLIBCXX_NOEXCEPT
02689       { return  _M_dataplus._M_p; }
02690 
02691       _CharT*
02692       _M_data(_CharT* __p) _GLIBCXX_NOEXCEPT
02693       { return (_M_dataplus._M_p = __p); }
02694 
02695       _Rep*
02696       _M_rep() const _GLIBCXX_NOEXCEPT
02697       { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
02698 
02699       // For the internal use we have functions similar to `begin'/`end'
02700       // but they do not call _M_leak.
02701       iterator
02702       _M_ibegin() const _GLIBCXX_NOEXCEPT
02703       { return iterator(_M_data()); }
02704 
02705       iterator
02706       _M_iend() const _GLIBCXX_NOEXCEPT
02707       { return iterator(_M_data() + this->size()); }
02708 
02709       void
02710       _M_leak()    // for use in begin() & non-const op[]
02711       {
02712         if (!_M_rep()->_M_is_leaked())
02713           _M_leak_hard();
02714       }
02715 
02716       size_type
02717       _M_check(size_type __pos, const char* __s) const
02718       {
02719         if (__pos > this->size())
02720           __throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "
02721                                        "this->size() (which is %zu)"),
02722                                    __s, __pos, this->size());
02723         return __pos;
02724       }
02725 
02726       void
02727       _M_check_length(size_type __n1, size_type __n2, const char* __s) const
02728       {
02729         if (this->max_size() - (this->size() - __n1) < __n2)
02730           __throw_length_error(__N(__s));
02731       }
02732 
02733       // NB: _M_limit doesn't check for a bad __pos value.
02734       size_type
02735       _M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPT
02736       {
02737         const bool __testoff =  __off < this->size() - __pos;
02738         return __testoff ? __off : this->size() - __pos;
02739       }
02740 
02741       // True if _Rep and source do not overlap.
02742       bool
02743       _M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPT
02744       {
02745         return (less<const _CharT*>()(__s, _M_data())
02746                 || less<const _CharT*>()(_M_data() + this->size(), __s));
02747       }
02748 
02749       // When __n = 1 way faster than the general multichar
02750       // traits_type::copy/move/assign.
02751       static void
02752       _M_copy(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT
02753       {
02754         if (__n == 1)
02755           traits_type::assign(*__d, *__s);
02756         else
02757           traits_type::copy(__d, __s, __n);
02758       }
02759 
02760       static void
02761       _M_move(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT
02762       {
02763         if (__n == 1)
02764           traits_type::assign(*__d, *__s);
02765         else
02766           traits_type::move(__d, __s, __n);       
02767       }
02768 
02769       static void
02770       _M_assign(_CharT* __d, size_type __n, _CharT __c) _GLIBCXX_NOEXCEPT
02771       {
02772         if (__n == 1)
02773           traits_type::assign(*__d, __c);
02774         else
02775           traits_type::assign(__d, __n, __c);     
02776       }
02777 
02778       // _S_copy_chars is a separate template to permit specialization
02779       // to optimize for the common case of pointers as iterators.
02780       template<class _Iterator>
02781         static void
02782         _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
02783         _GLIBCXX_NOEXCEPT
02784         {
02785           for (; __k1 != __k2; ++__k1, ++__p)
02786             traits_type::assign(*__p, *__k1); // These types are off.
02787         }
02788 
02789       static void
02790       _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) _GLIBCXX_NOEXCEPT
02791       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
02792 
02793       static void
02794       _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
02795       _GLIBCXX_NOEXCEPT
02796       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
02797 
02798       static void
02799       _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) _GLIBCXX_NOEXCEPT
02800       { _M_copy(__p, __k1, __k2 - __k1); }
02801 
02802       static void
02803       _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
02804       _GLIBCXX_NOEXCEPT
02805       { _M_copy(__p, __k1, __k2 - __k1); }
02806 
02807       static int
02808       _S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPT
02809       {
02810         const difference_type __d = difference_type(__n1 - __n2);
02811 
02812         if (__d > __gnu_cxx::__numeric_traits<int>::__max)
02813           return __gnu_cxx::__numeric_traits<int>::__max;
02814         else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
02815           return __gnu_cxx::__numeric_traits<int>::__min;
02816         else
02817           return int(__d);
02818       }
02819 
02820       void
02821       _M_mutate(size_type __pos, size_type __len1, size_type __len2);
02822 
02823       void
02824       _M_leak_hard();
02825 
02826       static _Rep&
02827       _S_empty_rep() _GLIBCXX_NOEXCEPT
02828       { return _Rep::_S_empty_rep(); }
02829 
02830     public:
02831       // Construct/copy/destroy:
02832       // NB: We overload ctors in some cases instead of using default
02833       // arguments, per 17.4.4.4 para. 2 item 2.
02834 
02835       /**
02836        *  @brief  Default constructor creates an empty string.
02837        */
02838       basic_string()
02839 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
02840       : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
02841 #else
02842       : _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()){ }
02843 #endif
02844 
02845       /**
02846        *  @brief  Construct an empty string using allocator @a a.
02847        */
02848       explicit
02849       basic_string(const _Alloc& __a);
02850 
02851       // NB: per LWG issue 42, semantics different from IS:
02852       /**
02853        *  @brief  Construct string with copy of value of @a str.
02854        *  @param  __str  Source string.
02855        */
02856       basic_string(const basic_string& __str);
02857       /**
02858        *  @brief  Construct string as copy of a substring.
02859        *  @param  __str  Source string.
02860        *  @param  __pos  Index of first character to copy from.
02861        *  @param  __n  Number of characters to copy (default remainder).
02862        */
02863       basic_string(const basic_string& __str, size_type __pos,
02864                    size_type __n = npos);
02865       /**
02866        *  @brief  Construct string as copy of a substring.
02867        *  @param  __str  Source string.
02868        *  @param  __pos  Index of first character to copy from.
02869        *  @param  __n  Number of characters to copy.
02870        *  @param  __a  Allocator to use.
02871        */
02872       basic_string(const basic_string& __str, size_type __pos,
02873                    size_type __n, const _Alloc& __a);
02874 
02875       /**
02876        *  @brief  Construct string initialized by a character %array.
02877        *  @param  __s  Source character %array.
02878        *  @param  __n  Number of characters to copy.
02879        *  @param  __a  Allocator to use (default is default allocator).
02880        *
02881        *  NB: @a __s must have at least @a __n characters, &apos;\\0&apos;
02882        *  has no special meaning.
02883        */
02884       basic_string(const _CharT* __s, size_type __n,
02885                    const _Alloc& __a = _Alloc());
02886       /**
02887        *  @brief  Construct string as copy of a C string.
02888        *  @param  __s  Source C string.
02889        *  @param  __a  Allocator to use (default is default allocator).
02890        */
02891       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
02892       /**
02893        *  @brief  Construct string as multiple characters.
02894        *  @param  __n  Number of characters.
02895        *  @param  __c  Character to use.
02896        *  @param  __a  Allocator to use (default is default allocator).
02897        */
02898       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
02899 
02900 #if __cplusplus >= 201103L
02901       /**
02902        *  @brief  Move construct string.
02903        *  @param  __str  Source string.
02904        *
02905        *  The newly-created string contains the exact contents of @a __str.
02906        *  @a __str is a valid, but unspecified string.
02907        **/
02908       basic_string(basic_string&& __str)
02909 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
02910       noexcept // FIXME C++11: should always be noexcept.
02911 #endif
02912       : _M_dataplus(__str._M_dataplus)
02913       {
02914 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
02915         __str._M_data(_S_empty_rep()._M_refdata());
02916 #else
02917         __str._M_data(_S_construct(size_type(), _CharT(), get_allocator()));
02918 #endif
02919       }
02920 
02921       /**
02922        *  @brief  Construct string from an initializer %list.
02923        *  @param  __l  std::initializer_list of characters.
02924        *  @param  __a  Allocator to use (default is default allocator).
02925        */
02926       basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc());
02927 #endif // C++11
02928 
02929       /**
02930        *  @brief  Construct string as copy of a range.
02931        *  @param  __beg  Start of range.
02932        *  @param  __end  End of range.
02933        *  @param  __a  Allocator to use (default is default allocator).
02934        */
02935       template<class _InputIterator>
02936         basic_string(_InputIterator __beg, _InputIterator __end,
02937                      const _Alloc& __a = _Alloc());
02938 
02939       /**
02940        *  @brief  Destroy the string instance.
02941        */
02942       ~basic_string() _GLIBCXX_NOEXCEPT
02943       { _M_rep()->_M_dispose(this->get_allocator()); }
02944 
02945       /**
02946        *  @brief  Assign the value of @a str to this string.
02947        *  @param  __str  Source string.
02948        */
02949       basic_string&
02950       operator=(const basic_string& __str) 
02951       { return this->assign(__str); }
02952 
02953       /**
02954        *  @brief  Copy contents of @a s into this string.
02955        *  @param  __s  Source null-terminated string.
02956        */
02957       basic_string&
02958       operator=(const _CharT* __s) 
02959       { return this->assign(__s); }
02960 
02961       /**
02962        *  @brief  Set value to string of length 1.
02963        *  @param  __c  Source character.
02964        *
02965        *  Assigning to a character makes this string length 1 and
02966        *  (*this)[0] == @a c.
02967        */
02968       basic_string&
02969       operator=(_CharT __c) 
02970       { 
02971         this->assign(1, __c); 
02972         return *this;
02973       }
02974 
02975 #if __cplusplus >= 201103L
02976       /**
02977        *  @brief  Move assign the value of @a str to this string.
02978        *  @param  __str  Source string.
02979        *
02980        *  The contents of @a str are moved into this string (without copying).
02981        *  @a str is a valid, but unspecified string.
02982        **/
02983       // PR 58265, this should be noexcept.
02984       basic_string&
02985       operator=(basic_string&& __str)
02986       {
02987         // NB: DR 1204.
02988         this->swap(__str);
02989         return *this;
02990       }
02991 
02992       /**
02993        *  @brief  Set value to string constructed from initializer %list.
02994        *  @param  __l  std::initializer_list.
02995        */
02996       basic_string&
02997       operator=(initializer_list<_CharT> __l)
02998       {
02999         this->assign(__l.begin(), __l.size());
03000         return *this;
03001       }
03002 #endif // C++11
03003 
03004       // Iterators:
03005       /**
03006        *  Returns a read/write iterator that points to the first character in
03007        *  the %string.  Unshares the string.
03008        */
03009       iterator
03010       begin() // FIXME C++11: should be noexcept.
03011       {
03012         _M_leak();
03013         return iterator(_M_data());
03014       }
03015 
03016       /**
03017        *  Returns a read-only (constant) iterator that points to the first
03018        *  character in the %string.
03019        */
03020       const_iterator
03021       begin() const _GLIBCXX_NOEXCEPT
03022       { return const_iterator(_M_data()); }
03023 
03024       /**
03025        *  Returns a read/write iterator that points one past the last
03026        *  character in the %string.  Unshares the string.
03027        */
03028       iterator
03029       end() // FIXME C++11: should be noexcept.
03030       {
03031         _M_leak();
03032         return iterator(_M_data() + this->size());
03033       }
03034 
03035       /**
03036        *  Returns a read-only (constant) iterator that points one past the
03037        *  last character in the %string.
03038        */
03039       const_iterator
03040       end() const _GLIBCXX_NOEXCEPT
03041       { return const_iterator(_M_data() + this->size()); }
03042 
03043       /**
03044        *  Returns a read/write reverse iterator that points to the last
03045        *  character in the %string.  Iteration is done in reverse element
03046        *  order.  Unshares the string.
03047        */
03048       reverse_iterator
03049       rbegin() // FIXME C++11: should be noexcept.
03050       { return reverse_iterator(this->end()); }
03051 
03052       /**
03053        *  Returns a read-only (constant) reverse iterator that points
03054        *  to the last character in the %string.  Iteration is done in
03055        *  reverse element order.
03056        */
03057       const_reverse_iterator
03058       rbegin() const _GLIBCXX_NOEXCEPT
03059       { return const_reverse_iterator(this->end()); }
03060 
03061       /**
03062        *  Returns a read/write reverse iterator that points to one before the
03063        *  first character in the %string.  Iteration is done in reverse
03064        *  element order.  Unshares the string.
03065        */
03066       reverse_iterator
03067       rend() // FIXME C++11: should be noexcept.
03068       { return reverse_iterator(this->begin()); }
03069 
03070       /**
03071        *  Returns a read-only (constant) reverse iterator that points
03072        *  to one before the first character in the %string.  Iteration
03073        *  is done in reverse element order.
03074        */
03075       const_reverse_iterator
03076       rend() const _GLIBCXX_NOEXCEPT
03077       { return const_reverse_iterator(this->begin()); }
03078 
03079 #if __cplusplus >= 201103L
03080       /**
03081        *  Returns a read-only (constant) iterator that points to the first
03082        *  character in the %string.
03083        */
03084       const_iterator
03085       cbegin() const noexcept
03086       { return const_iterator(this->_M_data()); }
03087 
03088       /**
03089        *  Returns a read-only (constant) iterator that points one past the
03090        *  last character in the %string.
03091        */
03092       const_iterator
03093       cend() const noexcept
03094       { return const_iterator(this->_M_data() + this->size()); }
03095 
03096       /**
03097        *  Returns a read-only (constant) reverse iterator that points
03098        *  to the last character in the %string.  Iteration is done in
03099        *  reverse element order.
03100        */
03101       const_reverse_iterator
03102       crbegin() const noexcept
03103       { return const_reverse_iterator(this->end()); }
03104 
03105       /**
03106        *  Returns a read-only (constant) reverse iterator that points
03107        *  to one before the first character in the %string.  Iteration
03108        *  is done in reverse element order.
03109        */
03110       const_reverse_iterator
03111       crend() const noexcept
03112       { return const_reverse_iterator(this->begin()); }
03113 #endif
03114 
03115     public:
03116       // Capacity:
03117       ///  Returns the number of characters in the string, not including any
03118       ///  null-termination.
03119       size_type
03120       size() const _GLIBCXX_NOEXCEPT
03121       { return _M_rep()->_M_length; }
03122 
03123       ///  Returns the number of characters in the string, not including any
03124       ///  null-termination.
03125       size_type
03126       length() const _GLIBCXX_NOEXCEPT
03127       { return _M_rep()->_M_length; }
03128 
03129       ///  Returns the size() of the largest possible %string.
03130       size_type
03131       max_size() const _GLIBCXX_NOEXCEPT
03132       { return _Rep::_S_max_size; }
03133 
03134       /**
03135        *  @brief  Resizes the %string to the specified number of characters.
03136        *  @param  __n  Number of characters the %string should contain.
03137        *  @param  __c  Character to fill any new elements.
03138        *
03139        *  This function will %resize the %string to the specified
03140        *  number of characters.  If the number is smaller than the
03141        *  %string's current size the %string is truncated, otherwise
03142        *  the %string is extended and new elements are %set to @a __c.
03143        */
03144       void
03145       resize(size_type __n, _CharT __c);
03146 
03147       /**
03148        *  @brief  Resizes the %string to the specified number of characters.
03149        *  @param  __n  Number of characters the %string should contain.
03150        *
03151        *  This function will resize the %string to the specified length.  If
03152        *  the new size is smaller than the %string's current size the %string
03153        *  is truncated, otherwise the %string is extended and new characters
03154        *  are default-constructed.  For basic types such as char, this means
03155        *  setting them to 0.
03156        */
03157       void
03158       resize(size_type __n)
03159       { this->resize(__n, _CharT()); }
03160 
03161 #if __cplusplus >= 201103L
03162       ///  A non-binding request to reduce capacity() to size().
03163       void
03164       shrink_to_fit() _GLIBCXX_NOEXCEPT
03165       {
03166         if (capacity() > size())
03167           {
03168             __try
03169               { reserve(0); }
03170             __catch(...)
03171               { }
03172           }
03173       }
03174 #endif
03175 
03176       /**
03177        *  Returns the total number of characters that the %string can hold
03178        *  before needing to allocate more memory.
03179        */
03180       size_type
03181       capacity() const _GLIBCXX_NOEXCEPT
03182       { return _M_rep()->_M_capacity; }
03183 
03184       /**
03185        *  @brief  Attempt to preallocate enough memory for specified number of
03186        *          characters.
03187        *  @param  __res_arg  Number of characters required.
03188        *  @throw  std::length_error  If @a __res_arg exceeds @c max_size().
03189        *
03190        *  This function attempts to reserve enough memory for the
03191        *  %string to hold the specified number of characters.  If the
03192        *  number requested is more than max_size(), length_error is
03193        *  thrown.
03194        *
03195        *  The advantage of this function is that if optimal code is a
03196        *  necessity and the user can determine the string length that will be
03197        *  required, the user can reserve the memory in %advance, and thus
03198        *  prevent a possible reallocation of memory and copying of %string
03199        *  data.
03200        */
03201       void
03202       reserve(size_type __res_arg = 0);
03203 
03204       /**
03205        *  Erases the string, making it empty.
03206        */
03207       // PR 56166: this should not throw.
03208       void
03209       clear()
03210       { _M_mutate(0, this->size(), 0); }
03211 
03212       /**
03213        *  Returns true if the %string is empty.  Equivalent to 
03214        *  <code>*this == ""</code>.
03215        */
03216       bool
03217       empty() const _GLIBCXX_NOEXCEPT
03218       { return this->size() == 0; }
03219 
03220       // Element access:
03221       /**
03222        *  @brief  Subscript access to the data contained in the %string.
03223        *  @param  __pos  The index of the character to access.
03224        *  @return  Read-only (constant) reference to the character.
03225        *
03226        *  This operator allows for easy, array-style, data access.
03227        *  Note that data access with this operator is unchecked and
03228        *  out_of_range lookups are not defined. (For checked lookups
03229        *  see at().)
03230        */
03231       const_reference
03232       operator[] (size_type __pos) const _GLIBCXX_NOEXCEPT
03233       {
03234         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
03235         return _M_data()[__pos];
03236       }
03237 
03238       /**
03239        *  @brief  Subscript access to the data contained in the %string.
03240        *  @param  __pos  The index of the character to access.
03241        *  @return  Read/write reference to the character.
03242        *
03243        *  This operator allows for easy, array-style, data access.
03244        *  Note that data access with this operator is unchecked and
03245        *  out_of_range lookups are not defined. (For checked lookups
03246        *  see at().)  Unshares the string.
03247        */
03248       reference
03249       operator[](size_type __pos)
03250       {
03251         // Allow pos == size() both in C++98 mode, as v3 extension,
03252         // and in C++11 mode.
03253         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
03254         // In pedantic mode be strict in C++98 mode.
03255         _GLIBCXX_DEBUG_PEDASSERT(__cplusplus >= 201103L || __pos < size());
03256         _M_leak();
03257         return _M_data()[__pos];
03258       }
03259 
03260       /**
03261        *  @brief  Provides access to the data contained in the %string.
03262        *  @param __n The index of the character to access.
03263        *  @return  Read-only (const) reference to the character.
03264        *  @throw  std::out_of_range  If @a n is an invalid index.
03265        *
03266        *  This function provides for safer data access.  The parameter is
03267        *  first checked that it is in the range of the string.  The function
03268        *  throws out_of_range if the check fails.
03269        */
03270       const_reference
03271       at(size_type __n) const
03272       {
03273         if (__n >= this->size())
03274           __throw_out_of_range_fmt(__N("basic_string::at: __n "
03275                                        "(which is %zu) >= this->size() "
03276                                        "(which is %zu)"),
03277                                    __n, this->size());
03278         return _M_data()[__n];
03279       }
03280 
03281       /**
03282        *  @brief  Provides access to the data contained in the %string.
03283        *  @param __n The index of the character to access.
03284        *  @return  Read/write reference to the character.
03285        *  @throw  std::out_of_range  If @a n is an invalid index.
03286        *
03287        *  This function provides for safer data access.  The parameter is
03288        *  first checked that it is in the range of the string.  The function
03289        *  throws out_of_range if the check fails.  Success results in
03290        *  unsharing the string.
03291        */
03292       reference
03293       at(size_type __n)
03294       {
03295         if (__n >= size())
03296           __throw_out_of_range_fmt(__N("basic_string::at: __n "
03297                                        "(which is %zu) >= this->size() "
03298                                        "(which is %zu)"),
03299                                    __n, this->size());
03300         _M_leak();
03301         return _M_data()[__n];
03302       }
03303 
03304 #if __cplusplus >= 201103L
03305       /**
03306        *  Returns a read/write reference to the data at the first
03307        *  element of the %string.
03308        */
03309       reference
03310       front()
03311       { return operator[](0); }
03312 
03313       /**
03314        *  Returns a read-only (constant) reference to the data at the first
03315        *  element of the %string.
03316        */
03317       const_reference
03318       front() const _GLIBCXX_NOEXCEPT
03319       { return operator[](0); }
03320 
03321       /**
03322        *  Returns a read/write reference to the data at the last
03323        *  element of the %string.
03324        */
03325       reference
03326       back()
03327       { return operator[](this->size() - 1); }
03328 
03329       /**
03330        *  Returns a read-only (constant) reference to the data at the
03331        *  last element of the %string.
03332        */
03333       const_reference
03334       back() const _GLIBCXX_NOEXCEPT
03335       { return operator[](this->size() - 1); }
03336 #endif
03337 
03338       // Modifiers:
03339       /**
03340        *  @brief  Append a string to this string.
03341        *  @param __str  The string to append.
03342        *  @return  Reference to this string.
03343        */
03344       basic_string&
03345       operator+=(const basic_string& __str)
03346       { return this->append(__str); }
03347 
03348       /**
03349        *  @brief  Append a C string.
03350        *  @param __s  The C string to append.
03351        *  @return  Reference to this string.
03352        */
03353       basic_string&
03354       operator+=(const _CharT* __s)
03355       { return this->append(__s); }
03356 
03357       /**
03358        *  @brief  Append a character.
03359        *  @param __c  The character to append.
03360        *  @return  Reference to this string.
03361        */
03362       basic_string&
03363       operator+=(_CharT __c)
03364       { 
03365         this->push_back(__c);
03366         return *this;
03367       }
03368 
03369 #if __cplusplus >= 201103L
03370       /**
03371        *  @brief  Append an initializer_list of characters.
03372        *  @param __l  The initializer_list of characters to be appended.
03373        *  @return  Reference to this string.
03374        */
03375       basic_string&
03376       operator+=(initializer_list<_CharT> __l)
03377       { return this->append(__l.begin(), __l.size()); }
03378 #endif // C++11
03379 
03380       /**
03381        *  @brief  Append a string to this string.
03382        *  @param __str  The string to append.
03383        *  @return  Reference to this string.
03384        */
03385       basic_string&
03386       append(const basic_string& __str);
03387 
03388       /**
03389        *  @brief  Append a substring.
03390        *  @param __str  The string to append.
03391        *  @param __pos  Index of the first character of str to append.
03392        *  @param __n  The number of characters to append.
03393        *  @return  Reference to this string.
03394        *  @throw  std::out_of_range if @a __pos is not a valid index.
03395        *
03396        *  This function appends @a __n characters from @a __str
03397        *  starting at @a __pos to this string.  If @a __n is is larger
03398        *  than the number of available characters in @a __str, the
03399        *  remainder of @a __str is appended.
03400        */
03401       basic_string&
03402       append(const basic_string& __str, size_type __pos, size_type __n);
03403 
03404       /**
03405        *  @brief  Append a C substring.
03406        *  @param __s  The C string to append.
03407        *  @param __n  The number of characters to append.
03408        *  @return  Reference to this string.
03409        */
03410       basic_string&
03411       append(const _CharT* __s, size_type __n);
03412 
03413       /**
03414        *  @brief  Append a C string.
03415        *  @param __s  The C string to append.
03416        *  @return  Reference to this string.
03417        */
03418       basic_string&
03419       append(const _CharT* __s)
03420       {
03421         __glibcxx_requires_string(__s);
03422         return this->append(__s, traits_type::length(__s));
03423       }
03424 
03425       /**
03426        *  @brief  Append multiple characters.
03427        *  @param __n  The number of characters to append.
03428        *  @param __c  The character to use.
03429        *  @return  Reference to this string.
03430        *
03431        *  Appends __n copies of __c to this string.
03432        */
03433       basic_string&
03434       append(size_type __n, _CharT __c);
03435 
03436 #if __cplusplus >= 201103L
03437       /**
03438        *  @brief  Append an initializer_list of characters.
03439        *  @param __l  The initializer_list of characters to append.
03440        *  @return  Reference to this string.
03441        */
03442       basic_string&
03443       append(initializer_list<_CharT> __l)
03444       { return this->append(__l.begin(), __l.size()); }
03445 #endif // C++11
03446 
03447       /**
03448        *  @brief  Append a range of characters.
03449        *  @param __first  Iterator referencing the first character to append.
03450        *  @param __last  Iterator marking the end of the range.
03451        *  @return  Reference to this string.
03452        *
03453        *  Appends characters in the range [__first,__last) to this string.
03454        */
03455       template<class _InputIterator>
03456         basic_string&
03457         append(_InputIterator __first, _InputIterator __last)
03458         { return this->replace(_M_iend(), _M_iend(), __first, __last); }
03459 
03460       /**
03461        *  @brief  Append a single character.
03462        *  @param __c  Character to append.
03463        */
03464       void
03465       push_back(_CharT __c)
03466       { 
03467         const size_type __len = 1 + this->size();
03468         if (__len > this->capacity() || _M_rep()->_M_is_shared())
03469           this->reserve(__len);
03470         traits_type::assign(_M_data()[this->size()], __c);
03471         _M_rep()->_M_set_length_and_sharable(__len);
03472       }
03473 
03474       /**
03475        *  @brief  Set value to contents of another string.
03476        *  @param  __str  Source string to use.
03477        *  @return  Reference to this string.
03478        */
03479       basic_string&
03480       assign(const basic_string& __str);
03481 
03482 #if __cplusplus >= 201103L
03483       /**
03484        *  @brief  Set value to contents of another string.
03485        *  @param  __str  Source string to use.
03486        *  @return  Reference to this string.
03487        *
03488        *  This function sets this string to the exact contents of @a __str.
03489        *  @a __str is a valid, but unspecified string.
03490        */
03491       // PR 58265, this should be noexcept.
03492       basic_string&
03493       assign(basic_string&& __str)
03494       {
03495         this->swap(__str);
03496         return *this;
03497       }
03498 #endif // C++11
03499 
03500       /**
03501        *  @brief  Set value to a substring of a string.
03502        *  @param __str  The string to use.
03503        *  @param __pos  Index of the first character of str.
03504        *  @param __n  Number of characters to use.
03505        *  @return  Reference to this string.
03506        *  @throw  std::out_of_range if @a pos is not a valid index.
03507        *
03508        *  This function sets this string to the substring of @a __str
03509        *  consisting of @a __n characters at @a __pos.  If @a __n is
03510        *  is larger than the number of available characters in @a
03511        *  __str, the remainder of @a __str is used.
03512        */
03513       basic_string&
03514       assign(const basic_string& __str, size_type __pos, size_type __n)
03515       { return this->assign(__str._M_data()
03516                             + __str._M_check(__pos, "basic_string::assign"),
03517                             __str._M_limit(__pos, __n)); }
03518 
03519       /**
03520        *  @brief  Set value to a C substring.
03521        *  @param __s  The C string to use.
03522        *  @param __n  Number of characters to use.
03523        *  @return  Reference to this string.
03524        *
03525        *  This function sets the value of this string to the first @a __n
03526        *  characters of @a __s.  If @a __n is is larger than the number of
03527        *  available characters in @a __s, the remainder of @a __s is used.
03528        */
03529       basic_string&
03530       assign(const _CharT* __s, size_type __n);
03531 
03532       /**
03533        *  @brief  Set value to contents of a C string.
03534        *  @param __s  The C string to use.
03535        *  @return  Reference to this string.
03536        *
03537        *  This function sets the value of this string to the value of @a __s.
03538        *  The data is copied, so there is no dependence on @a __s once the
03539        *  function returns.
03540        */
03541       basic_string&
03542       assign(const _CharT* __s)
03543       {
03544         __glibcxx_requires_string(__s);
03545         return this->assign(__s, traits_type::length(__s));
03546       }
03547 
03548       /**
03549        *  @brief  Set value to multiple characters.
03550        *  @param __n  Length of the resulting string.
03551        *  @param __c  The character to use.
03552        *  @return  Reference to this string.
03553        *
03554        *  This function sets the value of this string to @a __n copies of
03555        *  character @a __c.
03556        */
03557       basic_string&
03558       assign(size_type __n, _CharT __c)
03559       { return _M_replace_aux(size_type(0), this->size(), __n, __c); }
03560 
03561       /**
03562        *  @brief  Set value to a range of characters.
03563        *  @param __first  Iterator referencing the first character to append.
03564        *  @param __last  Iterator marking the end of the range.
03565        *  @return  Reference to this string.
03566        *
03567        *  Sets value of string to characters in the range [__first,__last).
03568       */
03569       template<class _InputIterator>
03570         basic_string&
03571         assign(_InputIterator __first, _InputIterator __last)
03572         { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
03573 
03574 #if __cplusplus >= 201103L
03575       /**
03576        *  @brief  Set value to an initializer_list of characters.
03577        *  @param __l  The initializer_list of characters to assign.
03578        *  @return  Reference to this string.
03579        */
03580       basic_string&
03581       assign(initializer_list<_CharT> __l)
03582       { return this->assign(__l.begin(), __l.size()); }
03583 #endif // C++11
03584 
03585       /**
03586        *  @brief  Insert multiple characters.
03587        *  @param __p  Iterator referencing location in string to insert at.
03588        *  @param __n  Number of characters to insert
03589        *  @param __c  The character to insert.
03590        *  @throw  std::length_error  If new length exceeds @c max_size().
03591        *
03592        *  Inserts @a __n copies of character @a __c starting at the
03593        *  position referenced by iterator @a __p.  If adding
03594        *  characters causes the length to exceed max_size(),
03595        *  length_error is thrown.  The value of the string doesn't
03596        *  change if an error is thrown.
03597       */
03598       void
03599       insert(iterator __p, size_type __n, _CharT __c)
03600       { this->replace(__p, __p, __n, __c);  }
03601 
03602       /**
03603        *  @brief  Insert a range of characters.
03604        *  @param __p  Iterator referencing location in string to insert at.
03605        *  @param __beg  Start of range.
03606        *  @param __end  End of range.
03607        *  @throw  std::length_error  If new length exceeds @c max_size().
03608        *
03609        *  Inserts characters in range [__beg,__end).  If adding
03610        *  characters causes the length to exceed max_size(),
03611        *  length_error is thrown.  The value of the string doesn't
03612        *  change if an error is thrown.
03613       */
03614       template<class _InputIterator>
03615         void
03616         insert(iterator __p, _InputIterator __beg, _InputIterator __end)
03617         { this->replace(__p, __p, __beg, __end); }
03618 
03619 #if __cplusplus >= 201103L
03620       /**
03621        *  @brief  Insert an initializer_list of characters.
03622        *  @param __p  Iterator referencing location in string to insert at.
03623        *  @param __l  The initializer_list of characters to insert.
03624        *  @throw  std::length_error  If new length exceeds @c max_size().
03625        */
03626       void
03627       insert(iterator __p, initializer_list<_CharT> __l)
03628       {
03629         _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
03630         this->insert(__p - _M_ibegin(), __l.begin(), __l.size());
03631       }
03632 #endif // C++11
03633 
03634       /**
03635        *  @brief  Insert value of a string.
03636        *  @param __pos1  Iterator referencing location in string to insert at.
03637        *  @param __str  The string to insert.
03638        *  @return  Reference to this string.
03639        *  @throw  std::length_error  If new length exceeds @c max_size().
03640        *
03641        *  Inserts value of @a __str starting at @a __pos1.  If adding
03642        *  characters causes the length to exceed max_size(),
03643        *  length_error is thrown.  The value of the string doesn't
03644        *  change if an error is thrown.
03645       */
03646       basic_string&
03647       insert(size_type __pos1, const basic_string& __str)
03648       { return this->insert(__pos1, __str, size_type(0), __str.size()); }
03649 
03650       /**
03651        *  @brief  Insert a substring.
03652        *  @param __pos1  Iterator referencing location in string to insert at.
03653        *  @param __str  The string to insert.
03654        *  @param __pos2  Start of characters in str to insert.
03655        *  @param __n  Number of characters to insert.
03656        *  @return  Reference to this string.
03657        *  @throw  std::length_error  If new length exceeds @c max_size().
03658        *  @throw  std::out_of_range  If @a pos1 > size() or
03659        *  @a __pos2 > @a str.size().
03660        *
03661        *  Starting at @a pos1, insert @a __n character of @a __str
03662        *  beginning with @a __pos2.  If adding characters causes the
03663        *  length to exceed max_size(), length_error is thrown.  If @a
03664        *  __pos1 is beyond the end of this string or @a __pos2 is
03665        *  beyond the end of @a __str, out_of_range is thrown.  The
03666        *  value of the string doesn't change if an error is thrown.
03667       */
03668       basic_string&
03669       insert(size_type __pos1, const basic_string& __str,
03670              size_type __pos2, size_type __n)
03671       { return this->insert(__pos1, __str._M_data()
03672                             + __str._M_check(__pos2, "basic_string::insert"),
03673                             __str._M_limit(__pos2, __n)); }
03674 
03675       /**
03676        *  @brief  Insert a C substring.
03677        *  @param __pos  Iterator referencing location in string to insert at.
03678        *  @param __s  The C string to insert.
03679        *  @param __n  The number of characters to insert.
03680        *  @return  Reference to this string.
03681        *  @throw  std::length_error  If new length exceeds @c max_size().
03682        *  @throw  std::out_of_range  If @a __pos is beyond the end of this
03683        *  string.
03684        *
03685        *  Inserts the first @a __n characters of @a __s starting at @a
03686        *  __pos.  If adding characters causes the length to exceed
03687        *  max_size(), length_error is thrown.  If @a __pos is beyond
03688        *  end(), out_of_range is thrown.  The value of the string
03689        *  doesn't change if an error is thrown.
03690       */
03691       basic_string&
03692       insert(size_type __pos, const _CharT* __s, size_type __n);
03693 
03694       /**
03695        *  @brief  Insert a C string.
03696        *  @param __pos  Iterator referencing location in string to insert at.
03697        *  @param __s  The C string to insert.
03698        *  @return  Reference to this string.
03699        *  @throw  std::length_error  If new length exceeds @c max_size().
03700        *  @throw  std::out_of_range  If @a pos is beyond the end of this
03701        *  string.
03702        *
03703        *  Inserts the first @a n characters of @a __s starting at @a __pos.  If
03704        *  adding characters causes the length to exceed max_size(),
03705        *  length_error is thrown.  If @a __pos is beyond end(), out_of_range is
03706        *  thrown.  The value of the string doesn't change if an error is
03707        *  thrown.
03708       */
03709       basic_string&
03710       insert(size_type __pos, const _CharT* __s)
03711       {
03712         __glibcxx_requires_string(__s);
03713         return this->insert(__pos, __s, traits_type::length(__s));
03714       }
03715 
03716       /**
03717        *  @brief  Insert multiple characters.
03718        *  @param __pos  Index in string to insert at.
03719        *  @param __n  Number of characters to insert
03720        *  @param __c  The character to insert.
03721        *  @return  Reference to this string.
03722        *  @throw  std::length_error  If new length exceeds @c max_size().
03723        *  @throw  std::out_of_range  If @a __pos is beyond the end of this
03724        *  string.
03725        *
03726        *  Inserts @a __n copies of character @a __c starting at index
03727        *  @a __pos.  If adding characters causes the length to exceed
03728        *  max_size(), length_error is thrown.  If @a __pos > length(),
03729        *  out_of_range is thrown.  The value of the string doesn't
03730        *  change if an error is thrown.
03731       */
03732       basic_string&
03733       insert(size_type __pos, size_type __n, _CharT __c)
03734       { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
03735                               size_type(0), __n, __c); }
03736 
03737       /**
03738        *  @brief  Insert one character.
03739        *  @param __p  Iterator referencing position in string to insert at.
03740        *  @param __c  The character to insert.
03741        *  @return  Iterator referencing newly inserted char.
03742        *  @throw  std::length_error  If new length exceeds @c max_size().
03743        *
03744        *  Inserts character @a __c at position referenced by @a __p.
03745        *  If adding character causes the length to exceed max_size(),
03746        *  length_error is thrown.  If @a __p is beyond end of string,
03747        *  out_of_range is thrown.  The value of the string doesn't
03748        *  change if an error is thrown.
03749       */
03750       iterator
03751       insert(iterator __p, _CharT __c)
03752       {
03753         _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
03754         const size_type __pos = __p - _M_ibegin();
03755         _M_replace_aux(__pos, size_type(0), size_type(1), __c);
03756         _M_rep()->_M_set_leaked();
03757         return iterator(_M_data() + __pos);
03758       }
03759 
03760       /**
03761        *  @brief  Remove characters.
03762        *  @param __pos  Index of first character to remove (default 0).
03763        *  @param __n  Number of characters to remove (default remainder).
03764        *  @return  Reference to this string.
03765        *  @throw  std::out_of_range  If @a pos is beyond the end of this
03766        *  string.
03767        *
03768        *  Removes @a __n characters from this string starting at @a
03769        *  __pos.  The length of the string is reduced by @a __n.  If
03770        *  there are < @a __n characters to remove, the remainder of
03771        *  the string is truncated.  If @a __p is beyond end of string,
03772        *  out_of_range is thrown.  The value of the string doesn't
03773        *  change if an error is thrown.
03774       */
03775       basic_string&
03776       erase(size_type __pos = 0, size_type __n = npos)
03777       { 
03778         _M_mutate(_M_check(__pos, "basic_string::erase"),
03779                   _M_limit(__pos, __n), size_type(0));
03780         return *this;
03781       }
03782 
03783       /**
03784        *  @brief  Remove one character.
03785        *  @param __position  Iterator referencing the character to remove.
03786        *  @return  iterator referencing same location after removal.
03787        *
03788        *  Removes the character at @a __position from this string. The value
03789        *  of the string doesn't change if an error is thrown.
03790       */
03791       iterator
03792       erase(iterator __position)
03793       {
03794         _GLIBCXX_DEBUG_PEDASSERT(__position >= _M_ibegin()
03795                                  && __position < _M_iend());
03796         const size_type __pos = __position - _M_ibegin();
03797         _M_mutate(__pos, size_type(1), size_type(0));
03798         _M_rep()->_M_set_leaked();
03799         return iterator(_M_data() + __pos);
03800       }
03801 
03802       /**
03803        *  @brief  Remove a range of characters.
03804        *  @param __first  Iterator referencing the first character to remove.
03805        *  @param __last  Iterator referencing the end of the range.
03806        *  @return  Iterator referencing location of first after removal.
03807        *
03808        *  Removes the characters in the range [first,last) from this string.
03809        *  The value of the string doesn't change if an error is thrown.
03810       */
03811       iterator
03812       erase(iterator __first, iterator __last);
03813  
03814 #if __cplusplus >= 201103L
03815       /**
03816        *  @brief  Remove the last character.
03817        *
03818        *  The string must be non-empty.
03819        */
03820       void
03821       pop_back() // FIXME C++11: should be noexcept.
03822       { erase(size()-1, 1); }
03823 #endif // C++11
03824 
03825       /**
03826        *  @brief  Replace characters with value from another string.
03827        *  @param __pos  Index of first character to replace.
03828        *  @param __n  Number of characters to be replaced.
03829        *  @param __str  String to insert.
03830        *  @return  Reference to this string.
03831        *  @throw  std::out_of_range  If @a pos is beyond the end of this
03832        *  string.
03833        *  @throw  std::length_error  If new length exceeds @c max_size().
03834        *
03835        *  Removes the characters in the range [__pos,__pos+__n) from
03836        *  this string.  In place, the value of @a __str is inserted.
03837        *  If @a __pos is beyond end of string, out_of_range is thrown.
03838        *  If the length of the result exceeds max_size(), length_error
03839        *  is thrown.  The value of the string doesn't change if an
03840        *  error is thrown.
03841       */
03842       basic_string&
03843       replace(size_type __pos, size_type __n, const basic_string& __str)
03844       { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
03845 
03846       /**
03847        *  @brief  Replace characters with value from another string.
03848        *  @param __pos1  Index of first character to replace.
03849        *  @param __n1  Number of characters to be replaced.
03850        *  @param __str  String to insert.
03851        *  @param __pos2  Index of first character of str to use.
03852        *  @param __n2  Number of characters from str to use.
03853        *  @return  Reference to this string.
03854        *  @throw  std::out_of_range  If @a __pos1 > size() or @a __pos2 >
03855        *  __str.size().
03856        *  @throw  std::length_error  If new length exceeds @c max_size().
03857        *
03858        *  Removes the characters in the range [__pos1,__pos1 + n) from this
03859        *  string.  In place, the value of @a __str is inserted.  If @a __pos is
03860        *  beyond end of string, out_of_range is thrown.  If the length of the
03861        *  result exceeds max_size(), length_error is thrown.  The value of the
03862        *  string doesn't change if an error is thrown.
03863       */
03864       basic_string&
03865       replace(size_type __pos1, size_type __n1, const basic_string& __str,
03866               size_type __pos2, size_type __n2)
03867       { return this->replace(__pos1, __n1, __str._M_data()
03868                              + __str._M_check(__pos2, "basic_string::replace"),
03869                              __str._M_limit(__pos2, __n2)); }
03870 
03871       /**
03872        *  @brief  Replace characters with value of a C substring.
03873        *  @param __pos  Index of first character to replace.
03874        *  @param __n1  Number of characters to be replaced.
03875        *  @param __s  C string to insert.
03876        *  @param __n2  Number of characters from @a s to use.
03877        *  @return  Reference to this string.
03878        *  @throw  std::out_of_range  If @a pos1 > size().
03879        *  @throw  std::length_error  If new length exceeds @c max_size().
03880        *
03881        *  Removes the characters in the range [__pos,__pos + __n1)
03882        *  from this string.  In place, the first @a __n2 characters of
03883        *  @a __s are inserted, or all of @a __s if @a __n2 is too large.  If
03884        *  @a __pos is beyond end of string, out_of_range is thrown.  If
03885        *  the length of result exceeds max_size(), length_error is
03886        *  thrown.  The value of the string doesn't change if an error
03887        *  is thrown.
03888       */
03889       basic_string&
03890       replace(size_type __pos, size_type __n1, const _CharT* __s,
03891               size_type __n2);
03892 
03893       /**
03894        *  @brief  Replace characters with value of a C string.
03895        *  @param __pos  Index of first character to replace.
03896        *  @param __n1  Number of characters to be replaced.
03897        *  @param __s  C string to insert.
03898        *  @return  Reference to this string.
03899        *  @throw  std::out_of_range  If @a pos > size().
03900        *  @throw  std::length_error  If new length exceeds @c max_size().
03901        *
03902        *  Removes the characters in the range [__pos,__pos + __n1)
03903        *  from this string.  In place, the characters of @a __s are
03904        *  inserted.  If @a __pos is beyond end of string, out_of_range
03905        *  is thrown.  If the length of result exceeds max_size(),
03906        *  length_error is thrown.  The value of the string doesn't
03907        *  change if an error is thrown.
03908       */
03909       basic_string&
03910       replace(size_type __pos, size_type __n1, const _CharT* __s)
03911       {
03912         __glibcxx_requires_string(__s);
03913         return this->replace(__pos, __n1, __s, traits_type::length(__s));
03914       }
03915 
03916       /**
03917        *  @brief  Replace characters with multiple characters.
03918        *  @param __pos  Index of first character to replace.
03919        *  @param __n1  Number of characters to be replaced.
03920        *  @param __n2  Number of characters to insert.
03921        *  @param __c  Character to insert.
03922        *  @return  Reference to this string.
03923        *  @throw  std::out_of_range  If @a __pos > size().
03924        *  @throw  std::length_error  If new length exceeds @c max_size().
03925        *
03926        *  Removes the characters in the range [pos,pos + n1) from this
03927        *  string.  In place, @a __n2 copies of @a __c are inserted.
03928        *  If @a __pos is beyond end of string, out_of_range is thrown.
03929        *  If the length of result exceeds max_size(), length_error is
03930        *  thrown.  The value of the string doesn't change if an error
03931        *  is thrown.
03932       */
03933       basic_string&
03934       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
03935       { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
03936                               _M_limit(__pos, __n1), __n2, __c); }
03937 
03938       /**
03939        *  @brief  Replace range of characters with string.
03940        *  @param __i1  Iterator referencing start of range to replace.
03941        *  @param __i2  Iterator referencing end of range to replace.
03942        *  @param __str  String value to insert.
03943        *  @return  Reference to this string.
03944        *  @throw  std::length_error  If new length exceeds @c max_size().
03945        *
03946        *  Removes the characters in the range [__i1,__i2).  In place,
03947        *  the value of @a __str is inserted.  If the length of result
03948        *  exceeds max_size(), length_error is thrown.  The value of
03949        *  the string doesn't change if an error is thrown.
03950       */
03951       basic_string&
03952       replace(iterator __i1, iterator __i2, const basic_string& __str)
03953       { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
03954 
03955       /**
03956        *  @brief  Replace range of characters with C substring.
03957        *  @param __i1  Iterator referencing start of range to replace.
03958        *  @param __i2  Iterator referencing end of range to replace.
03959        *  @param __s  C string value to insert.
03960        *  @param __n  Number of characters from s to insert.
03961        *  @return  Reference to this string.
03962        *  @throw  std::length_error  If new length exceeds @c max_size().
03963        *
03964        *  Removes the characters in the range [__i1,__i2).  In place,
03965        *  the first @a __n characters of @a __s are inserted.  If the
03966        *  length of result exceeds max_size(), length_error is thrown.
03967        *  The value of the string doesn't change if an error is
03968        *  thrown.
03969       */
03970       basic_string&
03971       replace(iterator __i1, iterator __i2, const _CharT* __s, size_type __n)
03972       {
03973         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
03974                                  && __i2 <= _M_iend());
03975         return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n);
03976       }
03977 
03978       /**
03979        *  @brief  Replace range of characters with C string.
03980        *  @param __i1  Iterator referencing start of range to replace.
03981        *  @param __i2  Iterator referencing end of range to replace.
03982        *  @param __s  C string value to insert.
03983        *  @return  Reference to this string.
03984        *  @throw  std::length_error  If new length exceeds @c max_size().
03985        *
03986        *  Removes the characters in the range [__i1,__i2).  In place,
03987        *  the characters of @a __s are inserted.  If the length of
03988        *  result exceeds max_size(), length_error is thrown.  The
03989        *  value of the string doesn't change if an error is thrown.
03990       */
03991       basic_string&
03992       replace(iterator __i1, iterator __i2, const _CharT* __s)
03993       {
03994         __glibcxx_requires_string(__s);
03995         return this->replace(__i1, __i2, __s, traits_type::length(__s));
03996       }
03997 
03998       /**
03999        *  @brief  Replace range of characters with multiple characters
04000        *  @param __i1  Iterator referencing start of range to replace.
04001        *  @param __i2  Iterator referencing end of range to replace.
04002        *  @param __n  Number of characters to insert.
04003        *  @param __c  Character to insert.
04004        *  @return  Reference to this string.
04005        *  @throw  std::length_error  If new length exceeds @c max_size().
04006        *
04007        *  Removes the characters in the range [__i1,__i2).  In place,
04008        *  @a __n copies of @a __c are inserted.  If the length of
04009        *  result exceeds max_size(), length_error is thrown.  The
04010        *  value of the string doesn't change if an error is thrown.
04011       */
04012       basic_string&
04013       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
04014       {
04015         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
04016                                  && __i2 <= _M_iend());
04017         return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __c);
04018       }
04019 
04020       /**
04021        *  @brief  Replace range of characters with range.
04022        *  @param __i1  Iterator referencing start of range to replace.
04023        *  @param __i2  Iterator referencing end of range to replace.
04024        *  @param __k1  Iterator referencing start of range to insert.
04025        *  @param __k2  Iterator referencing end of range to insert.
04026        *  @return  Reference to this string.
04027        *  @throw  std::length_error  If new length exceeds @c max_size().
04028        *
04029        *  Removes the characters in the range [__i1,__i2).  In place,
04030        *  characters in the range [__k1,__k2) are inserted.  If the
04031        *  length of result exceeds max_size(), length_error is thrown.
04032        *  The value of the string doesn't change if an error is
04033        *  thrown.
04034       */
04035       template<class _InputIterator>
04036         basic_string&
04037         replace(iterator __i1, iterator __i2,
04038                 _InputIterator __k1, _InputIterator __k2)
04039         {
04040           _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
04041                                    && __i2 <= _M_iend());
04042           __glibcxx_requires_valid_range(__k1, __k2);
04043           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
04044           return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
04045         }
04046 
04047       // Specializations for the common case of pointer and iterator:
04048       // useful to avoid the overhead of temporary buffering in _M_replace.
04049       basic_string&
04050       replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
04051       {
04052         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
04053                                  && __i2 <= _M_iend());
04054         __glibcxx_requires_valid_range(__k1, __k2);
04055         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
04056                              __k1, __k2 - __k1);
04057       }
04058 
04059       basic_string&
04060       replace(iterator __i1, iterator __i2,
04061               const _CharT* __k1, const _CharT* __k2)
04062       {
04063         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
04064                                  && __i2 <= _M_iend());
04065         __glibcxx_requires_valid_range(__k1, __k2);
04066         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
04067                              __k1, __k2 - __k1);
04068       }
04069 
04070       basic_string&
04071       replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
04072       {
04073         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
04074                                  && __i2 <= _M_iend());
04075         __glibcxx_requires_valid_range(__k1, __k2);
04076         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
04077                              __k1.base(), __k2 - __k1);
04078       }
04079 
04080       basic_string&
04081       replace(iterator __i1, iterator __i2,
04082               const_iterator __k1, const_iterator __k2)
04083       {
04084         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
04085                                  && __i2 <= _M_iend());
04086         __glibcxx_requires_valid_range(__k1, __k2);
04087         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
04088                              __k1.base(), __k2 - __k1);
04089       }
04090       
04091 #if __cplusplus >= 201103L
04092       /**
04093        *  @brief  Replace range of characters with initializer_list.
04094        *  @param __i1  Iterator referencing start of range to replace.
04095        *  @param __i2  Iterator referencing end of range to replace.
04096        *  @param __l  The initializer_list of characters to insert.
04097        *  @return  Reference to this string.
04098        *  @throw  std::length_error  If new length exceeds @c max_size().
04099        *
04100        *  Removes the characters in the range [__i1,__i2).  In place,
04101        *  characters in the range [__k1,__k2) are inserted.  If the
04102        *  length of result exceeds max_size(), length_error is thrown.
04103        *  The value of the string doesn't change if an error is
04104        *  thrown.
04105       */
04106       basic_string& replace(iterator __i1, iterator __i2,
04107                             initializer_list<_CharT> __l)
04108       { return this->replace(__i1, __i2, __l.begin(), __l.end()); }
04109 #endif // C++11
04110 
04111     private:
04112       template<class _Integer>
04113         basic_string&
04114         _M_replace_dispatch(iterator __i1, iterator __i2, _Integer __n,
04115                             _Integer __val, __true_type)
04116         { return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __val); }
04117 
04118       template<class _InputIterator>
04119         basic_string&
04120         _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
04121                             _InputIterator __k2, __false_type);
04122 
04123       basic_string&
04124       _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
04125                      _CharT __c);
04126 
04127       basic_string&
04128       _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
04129                       size_type __n2);
04130 
04131       // _S_construct_aux is used to implement the 21.3.1 para 15 which
04132       // requires special behaviour if _InIter is an integral type
04133       template<class _InIterator>
04134         static _CharT*
04135         _S_construct_aux(_InIterator __beg, _InIterator __end,
04136                          const _Alloc& __a, __false_type)
04137         {
04138           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
04139           return _S_construct(__beg, __end, __a, _Tag());
04140         }
04141 
04142       // _GLIBCXX_RESOLVE_LIB_DEFECTS
04143       // 438. Ambiguity in the "do the right thing" clause
04144       template<class _Integer>
04145         static _CharT*
04146         _S_construct_aux(_Integer __beg, _Integer __end,
04147                          const _Alloc& __a, __true_type)
04148         { return _S_construct_aux_2(static_cast<size_type>(__beg),
04149                                     __end, __a); }
04150 
04151       static _CharT*
04152       _S_construct_aux_2(size_type __req, _CharT __c, const _Alloc& __a)
04153       { return _S_construct(__req, __c, __a); }
04154 
04155       template<class _InIterator>
04156         static _CharT*
04157         _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
04158         {
04159           typedef typename std::__is_integer<_InIterator>::__type _Integral;
04160           return _S_construct_aux(__beg, __end, __a, _Integral());
04161         }
04162 
04163       // For Input Iterators, used in istreambuf_iterators, etc.
04164       template<class _InIterator>
04165         static _CharT*
04166          _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
04167                       input_iterator_tag);
04168 
04169       // For forward_iterators up to random_access_iterators, used for
04170       // string::iterator, _CharT*, etc.
04171       template<class _FwdIterator>
04172         static _CharT*
04173         _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
04174                      forward_iterator_tag);
04175 
04176       static _CharT*
04177       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
04178 
04179     public:
04180 
04181       /**
04182        *  @brief  Copy substring into C string.
04183        *  @param __s  C string to copy value into.
04184        *  @param __n  Number of characters to copy.
04185        *  @param __pos  Index of first character to copy.
04186        *  @return  Number of characters actually copied
04187        *  @throw  std::out_of_range  If __pos > size().
04188        *
04189        *  Copies up to @a __n characters starting at @a __pos into the
04190        *  C string @a __s.  If @a __pos is %greater than size(),
04191        *  out_of_range is thrown.
04192       */
04193       size_type
04194       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
04195 
04196       /**
04197        *  @brief  Swap contents with another string.
04198        *  @param __s  String to swap with.
04199        *
04200        *  Exchanges the contents of this string with that of @a __s in constant
04201        *  time.
04202       */
04203       // PR 58265, this should be noexcept.
04204       void
04205       swap(basic_string& __s);
04206 
04207       // String operations:
04208       /**
04209        *  @brief  Return const pointer to null-terminated contents.
04210        *
04211        *  This is a handle to internal data.  Do not modify or dire things may
04212        *  happen.
04213       */
04214       const _CharT*
04215       c_str() const _GLIBCXX_NOEXCEPT
04216       { return _M_data(); }
04217 
04218       /**
04219        *  @brief  Return const pointer to contents.
04220        *
04221        *  This is a handle to internal data.  Do not modify or dire things may
04222        *  happen.
04223       */
04224       const _CharT*
04225       data() const _GLIBCXX_NOEXCEPT
04226       { return _M_data(); }
04227 
04228       /**
04229        *  @brief  Return copy of allocator used to construct this string.
04230       */
04231       allocator_type
04232       get_allocator() const _GLIBCXX_NOEXCEPT
04233       { return _M_dataplus; }
04234 
04235       /**
04236        *  @brief  Find position of a C substring.
04237        *  @param __s  C string to locate.
04238        *  @param __pos  Index of character to search from.
04239        *  @param __n  Number of characters from @a s to search for.
04240        *  @return  Index of start of first occurrence.
04241        *
04242        *  Starting from @a __pos, searches forward for the first @a
04243        *  __n characters in @a __s within this string.  If found,
04244        *  returns the index where it begins.  If not found, returns
04245        *  npos.
04246       */
04247       size_type
04248       find(const _CharT* __s, size_type __pos, size_type __n) const;
04249 
04250       /**
04251        *  @brief  Find position of a string.
04252        *  @param __str  String to locate.
04253        *  @param __pos  Index of character to search from (default 0).
04254        *  @return  Index of start of first occurrence.
04255        *
04256        *  Starting from @a __pos, searches forward for value of @a __str within
04257        *  this string.  If found, returns the index where it begins.  If not
04258        *  found, returns npos.
04259       */
04260       size_type
04261       find(const basic_string& __str, size_type __pos = 0) const
04262         _GLIBCXX_NOEXCEPT
04263       { return this->find(__str.data(), __pos, __str.size()); }
04264 
04265       /**
04266        *  @brief  Find position of a C string.
04267        *  @param __s  C string to locate.
04268        *  @param __pos  Index of character to search from (default 0).
04269        *  @return  Index of start of first occurrence.
04270        *
04271        *  Starting from @a __pos, searches forward for the value of @a
04272        *  __s within this string.  If found, returns the index where
04273        *  it begins.  If not found, returns npos.
04274       */
04275       size_type
04276       find(const _CharT* __s, size_type __pos = 0) const
04277       {
04278         __glibcxx_requires_string(__s);
04279         return this->find(__s, __pos, traits_type::length(__s));
04280       }
04281 
04282       /**
04283        *  @brief  Find position of a character.
04284        *  @param __c  Character to locate.
04285        *  @param __pos  Index of character to search from (default 0).
04286        *  @return  Index of first occurrence.
04287        *
04288        *  Starting from @a __pos, searches forward for @a __c within
04289        *  this string.  If found, returns the index where it was
04290        *  found.  If not found, returns npos.
04291       */
04292       size_type
04293       find(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT;
04294 
04295       /**
04296        *  @brief  Find last position of a string.
04297        *  @param __str  String to locate.
04298        *  @param __pos  Index of character to search back from (default end).
04299        *  @return  Index of start of last occurrence.
04300        *
04301        *  Starting from @a __pos, searches backward for value of @a
04302        *  __str within this string.  If found, returns the index where
04303        *  it begins.  If not found, returns npos.
04304       */
04305       size_type
04306       rfind(const basic_string& __str, size_type __pos = npos) const
04307         _GLIBCXX_NOEXCEPT
04308       { return this->rfind(__str.data(), __pos, __str.size()); }
04309 
04310       /**
04311        *  @brief  Find last position of a C substring.
04312        *  @param __s  C string to locate.
04313        *  @param __pos  Index of character to search back from.
04314        *  @param __n  Number of characters from s to search for.
04315        *  @return  Index of start of last occurrence.
04316        *
04317        *  Starting from @a __pos, searches backward for the first @a
04318        *  __n characters in @a __s within this string.  If found,
04319        *  returns the index where it begins.  If not found, returns
04320        *  npos.
04321       */
04322       size_type
04323       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
04324 
04325       /**
04326        *  @brief  Find last position of a C string.
04327        *  @param __s  C string to locate.
04328        *  @param __pos  Index of character to start search at (default end).
04329        *  @return  Index of start of  last occurrence.
04330        *
04331        *  Starting from @a __pos, searches backward for the value of
04332        *  @a __s within this string.  If found, returns the index
04333        *  where it begins.  If not found, returns npos.
04334       */
04335       size_type
04336       rfind(const _CharT* __s, size_type __pos = npos) const
04337       {
04338         __glibcxx_requires_string(__s);
04339         return this->rfind(__s, __pos, traits_type::length(__s));
04340       }
04341 
04342       /**
04343        *  @brief  Find last position of a character.
04344        *  @param __c  Character to locate.
04345        *  @param __pos  Index of character to search back from (default end).
04346        *  @return  Index of last occurrence.
04347        *
04348        *  Starting from @a __pos, searches backward for @a __c within
04349        *  this string.  If found, returns the index where it was
04350        *  found.  If not found, returns npos.
04351       */
04352       size_type
04353       rfind(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT;
04354 
04355       /**
04356        *  @brief  Find position of a character of string.
04357        *  @param __str  String containing characters to locate.
04358        *  @param __pos  Index of character to search from (default 0).
04359        *  @return  Index of first occurrence.
04360        *
04361        *  Starting from @a __pos, searches forward for one of the
04362        *  characters of @a __str within this string.  If found,
04363        *  returns the index where it was found.  If not found, returns
04364        *  npos.
04365       */
04366       size_type
04367       find_first_of(const basic_string& __str, size_type __pos = 0) const
04368         _GLIBCXX_NOEXCEPT
04369       { return this->find_first_of(__str.data(), __pos, __str.size()); }
04370 
04371       /**
04372        *  @brief  Find position of a character of C substring.
04373        *  @param __s  String containing characters to locate.
04374        *  @param __pos  Index of character to search from.
04375        *  @param __n  Number of characters from s to search for.
04376        *  @return  Index of first occurrence.
04377        *
04378        *  Starting from @a __pos, searches forward for one of the
04379        *  first @a __n characters of @a __s within this string.  If
04380        *  found, returns the index where it was found.  If not found,
04381        *  returns npos.
04382       */
04383       size_type
04384       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
04385 
04386       /**
04387        *  @brief  Find position of a character of C string.
04388        *  @param __s  String containing characters to locate.
04389        *  @param __pos  Index of character to search from (default 0).
04390        *  @return  Index of first occurrence.
04391        *
04392        *  Starting from @a __pos, searches forward for one of the
04393        *  characters of @a __s within this string.  If found, returns
04394        *  the index where it was found.  If not found, returns npos.
04395       */
04396       size_type
04397       find_first_of(const _CharT* __s, size_type __pos = 0) const
04398       {
04399         __glibcxx_requires_string(__s);
04400         return this->find_first_of(__s, __pos, traits_type::length(__s));
04401       }
04402 
04403       /**
04404        *  @brief  Find position of a character.
04405        *  @param __c  Character to locate.
04406        *  @param __pos  Index of character to search from (default 0).
04407        *  @return  Index of first occurrence.
04408        *
04409        *  Starting from @a __pos, searches forward for the character
04410        *  @a __c within this string.  If found, returns the index
04411        *  where it was found.  If not found, returns npos.
04412        *
04413        *  Note: equivalent to find(__c, __pos).
04414       */
04415       size_type
04416       find_first_of(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT
04417       { return this->find(__c, __pos); }
04418 
04419       /**
04420        *  @brief  Find last position of a character of string.
04421        *  @param __str  String containing characters to locate.
04422        *  @param __pos  Index of character to search back from (default end).
04423        *  @return  Index of last occurrence.
04424        *
04425        *  Starting from @a __pos, searches backward for one of the
04426        *  characters of @a __str within this string.  If found,
04427        *  returns the index where it was found.  If not found, returns
04428        *  npos.
04429       */
04430       size_type
04431       find_last_of(const basic_string& __str, size_type __pos = npos) const
04432         _GLIBCXX_NOEXCEPT
04433       { return this->find_last_of(__str.data(), __pos, __str.size()); }
04434 
04435       /**
04436        *  @brief  Find last position of a character of C substring.
04437        *  @param __s  C string containing characters to locate.
04438        *  @param __pos  Index of character to search back from.
04439        *  @param __n  Number of characters from s to search for.
04440        *  @return  Index of last occurrence.
04441        *
04442        *  Starting from @a __pos, searches backward for one of the
04443        *  first @a __n characters of @a __s within this string.  If
04444        *  found, returns the index where it was found.  If not found,
04445        *  returns npos.
04446       */
04447       size_type
04448       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
04449 
04450       /**
04451        *  @brief  Find last position of a character of C string.
04452        *  @param __s  C string containing characters to locate.
04453        *  @param __pos  Index of character to search back from (default end).
04454        *  @return  Index of last occurrence.
04455        *
04456        *  Starting from @a __pos, searches backward for one of the
04457        *  characters of @a __s within this string.  If found, returns
04458        *  the index where it was found.  If not found, returns npos.
04459       */
04460       size_type
04461       find_last_of(const _CharT* __s, size_type __pos = npos) const
04462       {
04463         __glibcxx_requires_string(__s);
04464         return this->find_last_of(__s, __pos, traits_type::length(__s));
04465       }
04466 
04467       /**
04468        *  @brief  Find last position of a character.
04469        *  @param __c  Character to locate.
04470        *  @param __pos  Index of character to search back from (default end).
04471        *  @return  Index of last occurrence.
04472        *
04473        *  Starting from @a __pos, searches backward for @a __c within
04474        *  this string.  If found, returns the index where it was
04475        *  found.  If not found, returns npos.
04476        *
04477        *  Note: equivalent to rfind(__c, __pos).
04478       */
04479       size_type
04480       find_last_of(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT
04481       { return this->rfind(__c, __pos); }
04482 
04483       /**
04484        *  @brief  Find position of a character not in string.
04485        *  @param __str  String containing characters to avoid.
04486        *  @param __pos  Index of character to search from (default 0).
04487        *  @return  Index of first occurrence.
04488        *
04489        *  Starting from @a __pos, searches forward for a character not contained
04490        *  in @a __str within this string.  If found, returns the index where it
04491        *  was found.  If not found, returns npos.
04492       */
04493       size_type
04494       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
04495         _GLIBCXX_NOEXCEPT
04496       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
04497 
04498       /**
04499        *  @brief  Find position of a character not in C substring.
04500        *  @param __s  C string containing characters to avoid.
04501        *  @param __pos  Index of character to search from.
04502        *  @param __n  Number of characters from __s to consider.
04503        *  @return  Index of first occurrence.
04504        *
04505        *  Starting from @a __pos, searches forward for a character not
04506        *  contained in the first @a __n characters of @a __s within
04507        *  this string.  If found, returns the index where it was
04508        *  found.  If not found, returns npos.
04509       */
04510       size_type
04511       find_first_not_of(const _CharT* __s, size_type __pos,
04512                         size_type __n) const;
04513 
04514       /**
04515        *  @brief  Find position of a character not in C string.
04516        *  @param __s  C string containing characters to avoid.
04517        *  @param __pos  Index of character to search from (default 0).
04518        *  @return  Index of first occurrence.
04519        *
04520        *  Starting from @a __pos, searches forward for a character not
04521        *  contained in @a __s within this string.  If found, returns
04522        *  the index where it was found.  If not found, returns npos.
04523       */
04524       size_type
04525       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
04526       {
04527         __glibcxx_requires_string(__s);
04528         return this->find_first_not_of(__s, __pos, traits_type::length(__s));
04529       }
04530 
04531       /**
04532        *  @brief  Find position of a different character.
04533        *  @param __c  Character to avoid.
04534        *  @param __pos  Index of character to search from (default 0).
04535        *  @return  Index of first occurrence.
04536        *
04537        *  Starting from @a __pos, searches forward for a character
04538        *  other than @a __c within this string.  If found, returns the
04539        *  index where it was found.  If not found, returns npos.
04540       */
04541       size_type
04542       find_first_not_of(_CharT __c, size_type __pos = 0) const
04543         _GLIBCXX_NOEXCEPT;
04544 
04545       /**
04546        *  @brief  Find last position of a character not in string.
04547        *  @param __str  String containing characters to avoid.
04548        *  @param __pos  Index of character to search back from (default end).
04549        *  @return  Index of last occurrence.
04550        *
04551        *  Starting from @a __pos, searches backward for a character
04552        *  not contained in @a __str within this string.  If found,
04553        *  returns the index where it was found.  If not found, returns
04554        *  npos.
04555       */
04556       size_type
04557       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
04558         _GLIBCXX_NOEXCEPT
04559       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
04560 
04561       /**
04562        *  @brief  Find last position of a character not in C substring.
04563        *  @param __s  C string containing characters to avoid.
04564        *  @param __pos  Index of character to search back from.
04565        *  @param __n  Number of characters from s to consider.
04566        *  @return  Index of last occurrence.
04567        *
04568        *  Starting from @a __pos, searches backward for a character not
04569        *  contained in the first @a __n characters of @a __s within this string.
04570        *  If found, returns the index where it was found.  If not found,
04571        *  returns npos.
04572       */
04573       size_type
04574       find_last_not_of(const _CharT* __s, size_type __pos,
04575                        size_type __n) const;
04576       /**
04577        *  @brief  Find last position of a character not in C string.
04578        *  @param __s  C string containing characters to avoid.
04579        *  @param __pos  Index of character to search back from (default end).
04580        *  @return  Index of last occurrence.
04581        *
04582        *  Starting from @a __pos, searches backward for a character
04583        *  not contained in @a __s within this string.  If found,
04584        *  returns the index where it was found.  If not found, returns
04585        *  npos.
04586       */
04587       size_type
04588       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
04589       {
04590         __glibcxx_requires_string(__s);
04591         return this->find_last_not_of(__s, __pos, traits_type::length(__s));
04592       }
04593 
04594       /**
04595        *  @brief  Find last position of a different character.
04596        *  @param __c  Character to avoid.
04597        *  @param __pos  Index of character to search back from (default end).
04598        *  @return  Index of last occurrence.
04599        *
04600        *  Starting from @a __pos, searches backward for a character other than
04601        *  @a __c within this string.  If found, returns the index where it was
04602        *  found.  If not found, returns npos.
04603       */
04604       size_type
04605       find_last_not_of(_CharT __c, size_type __pos = npos) const
04606         _GLIBCXX_NOEXCEPT;
04607 
04608       /**
04609        *  @brief  Get a substring.
04610        *  @param __pos  Index of first character (default 0).
04611        *  @param __n  Number of characters in substring (default remainder).
04612        *  @return  The new string.
04613        *  @throw  std::out_of_range  If __pos > size().
04614        *
04615        *  Construct and return a new string using the @a __n
04616        *  characters starting at @a __pos.  If the string is too
04617        *  short, use the remainder of the characters.  If @a __pos is
04618        *  beyond the end of the string, out_of_range is thrown.
04619       */
04620       basic_string
04621       substr(size_type __pos = 0, size_type __n = npos) const
04622       { return basic_string(*this,
04623                             _M_check(__pos, "basic_string::substr"), __n); }
04624 
04625       /**
04626        *  @brief  Compare to a string.
04627        *  @param __str  String to compare against.
04628        *  @return  Integer < 0, 0, or > 0.
04629        *
04630        *  Returns an integer < 0 if this string is ordered before @a
04631        *  __str, 0 if their values are equivalent, or > 0 if this
04632        *  string is ordered after @a __str.  Determines the effective
04633        *  length rlen of the strings to compare as the smallest of
04634        *  size() and str.size().  The function then compares the two
04635        *  strings by calling traits::compare(data(), str.data(),rlen).
04636        *  If the result of the comparison is nonzero returns it,
04637        *  otherwise the shorter one is ordered first.
04638       */
04639       int
04640       compare(const basic_string& __str) const
04641       {
04642         const size_type __size = this->size();
04643         const size_type __osize = __str.size();
04644         const size_type __len = std::min(__size, __osize);
04645 
04646         int __r = traits_type::compare(_M_data(), __str.data(), __len);
04647         if (!__r)
04648           __r = _S_compare(__size, __osize);
04649         return __r;
04650       }
04651 
04652       /**
04653        *  @brief  Compare substring to a string.
04654        *  @param __pos  Index of first character of substring.
04655        *  @param __n  Number of characters in substring.
04656        *  @param __str  String to compare against.
04657        *  @return  Integer < 0, 0, or > 0.
04658        *
04659        *  Form the substring of this string from the @a __n characters
04660        *  starting at @a __pos.  Returns an integer < 0 if the
04661        *  substring is ordered before @a __str, 0 if their values are
04662        *  equivalent, or > 0 if the substring is ordered after @a
04663        *  __str.  Determines the effective length rlen of the strings
04664        *  to compare as the smallest of the length of the substring
04665        *  and @a __str.size().  The function then compares the two
04666        *  strings by calling
04667        *  traits::compare(substring.data(),str.data(),rlen).  If the
04668        *  result of the comparison is nonzero returns it, otherwise
04669        *  the shorter one is ordered first.
04670       */
04671       int
04672       compare(size_type __pos, size_type __n, const basic_string& __str) const;
04673 
04674       /**
04675        *  @brief  Compare substring to a substring.
04676        *  @param __pos1  Index of first character of substring.
04677        *  @param __n1  Number of characters in substring.
04678        *  @param __str  String to compare against.
04679        *  @param __pos2  Index of first character of substring of str.
04680        *  @param __n2  Number of characters in substring of str.
04681        *  @return  Integer < 0, 0, or > 0.
04682        *
04683        *  Form the substring of this string from the @a __n1
04684        *  characters starting at @a __pos1.  Form the substring of @a
04685        *  __str from the @a __n2 characters starting at @a __pos2.
04686        *  Returns an integer < 0 if this substring is ordered before
04687        *  the substring of @a __str, 0 if their values are equivalent,
04688        *  or > 0 if this substring is ordered after the substring of
04689        *  @a __str.  Determines the effective length rlen of the
04690        *  strings to compare as the smallest of the lengths of the
04691        *  substrings.  The function then compares the two strings by
04692        *  calling
04693        *  traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
04694        *  If the result of the comparison is nonzero returns it,
04695        *  otherwise the shorter one is ordered first.
04696       */
04697       int
04698       compare(size_type __pos1, size_type __n1, const basic_string& __str,
04699               size_type __pos2, size_type __n2) const;
04700 
04701       /**
04702        *  @brief  Compare to a C string.
04703        *  @param __s  C string to compare against.
04704        *  @return  Integer < 0, 0, or > 0.
04705        *
04706        *  Returns an integer < 0 if this string is ordered before @a __s, 0 if
04707        *  their values are equivalent, or > 0 if this string is ordered after
04708        *  @a __s.  Determines the effective length rlen of the strings to
04709        *  compare as the smallest of size() and the length of a string
04710        *  constructed from @a __s.  The function then compares the two strings
04711        *  by calling traits::compare(data(),s,rlen).  If the result of the
04712        *  comparison is nonzero returns it, otherwise the shorter one is
04713        *  ordered first.
04714       */
04715       int
04716       compare(const _CharT* __s) const;
04717 
04718       // _GLIBCXX_RESOLVE_LIB_DEFECTS
04719       // 5 String::compare specification questionable
04720       /**
04721        *  @brief  Compare substring to a C string.
04722        *  @param __pos  Index of first character of substring.
04723        *  @param __n1  Number of characters in substring.
04724        *  @param __s  C string to compare against.
04725        *  @return  Integer < 0, 0, or > 0.
04726        *
04727        *  Form the substring of this string from the @a __n1
04728        *  characters starting at @a pos.  Returns an integer < 0 if
04729        *  the substring is ordered before @a __s, 0 if their values
04730        *  are equivalent, or > 0 if the substring is ordered after @a
04731        *  __s.  Determines the effective length rlen of the strings to
04732        *  compare as the smallest of the length of the substring and
04733        *  the length of a string constructed from @a __s.  The
04734        *  function then compares the two string by calling
04735        *  traits::compare(substring.data(),__s,rlen).  If the result of
04736        *  the comparison is nonzero returns it, otherwise the shorter
04737        *  one is ordered first.
04738       */
04739       int
04740       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
04741 
04742       /**
04743        *  @brief  Compare substring against a character %array.
04744        *  @param __pos  Index of first character of substring.
04745        *  @param __n1  Number of characters in substring.
04746        *  @param __s  character %array to compare against.
04747        *  @param __n2  Number of characters of s.
04748        *  @return  Integer < 0, 0, or > 0.
04749        *
04750        *  Form the substring of this string from the @a __n1
04751        *  characters starting at @a __pos.  Form a string from the
04752        *  first @a __n2 characters of @a __s.  Returns an integer < 0
04753        *  if this substring is ordered before the string from @a __s,
04754        *  0 if their values are equivalent, or > 0 if this substring
04755        *  is ordered after the string from @a __s.  Determines the
04756        *  effective length rlen of the strings to compare as the
04757        *  smallest of the length of the substring and @a __n2.  The
04758        *  function then compares the two strings by calling
04759        *  traits::compare(substring.data(),s,rlen).  If the result of
04760        *  the comparison is nonzero returns it, otherwise the shorter
04761        *  one is ordered first.
04762        *
04763        *  NB: s must have at least n2 characters, &apos;\\0&apos; has
04764        *  no special meaning.
04765       */
04766       int
04767       compare(size_type __pos, size_type __n1, const _CharT* __s,
04768               size_type __n2) const;
04769   };
04770 #endif  // !_GLIBCXX_USE_CXX11_ABI
04771 
04772   // operator+
04773   /**
04774    *  @brief  Concatenate two strings.
04775    *  @param __lhs  First string.
04776    *  @param __rhs  Last string.
04777    *  @return  New string with value of @a __lhs followed by @a __rhs.
04778    */
04779   template<typename _CharT, typename _Traits, typename _Alloc>
04780     basic_string<_CharT, _Traits, _Alloc>
04781     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
04782               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
04783     {
04784       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
04785       __str.append(__rhs);
04786       return __str;
04787     }
04788 
04789   /**
04790    *  @brief  Concatenate C string and string.
04791    *  @param __lhs  First string.
04792    *  @param __rhs  Last string.
04793    *  @return  New string with value of @a __lhs followed by @a __rhs.
04794    */
04795   template<typename _CharT, typename _Traits, typename _Alloc>
04796     basic_string<_CharT,_Traits,_Alloc>
04797     operator+(const _CharT* __lhs,
04798               const basic_string<_CharT,_Traits,_Alloc>& __rhs);
04799 
04800   /**
04801    *  @brief  Concatenate character and string.
04802    *  @param __lhs  First string.
04803    *  @param __rhs  Last string.
04804    *  @return  New string with @a __lhs followed by @a __rhs.
04805    */
04806   template<typename _CharT, typename _Traits, typename _Alloc>
04807     basic_string<_CharT,_Traits,_Alloc>
04808     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
04809 
04810   /**
04811    *  @brief  Concatenate string and C string.
04812    *  @param __lhs  First string.
04813    *  @param __rhs  Last string.
04814    *  @return  New string with @a __lhs followed by @a __rhs.
04815    */
04816   template<typename _CharT, typename _Traits, typename _Alloc>
04817     inline basic_string<_CharT, _Traits, _Alloc>
04818     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
04819               const _CharT* __rhs)
04820     {
04821       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
04822       __str.append(__rhs);
04823       return __str;
04824     }
04825 
04826   /**
04827    *  @brief  Concatenate string and character.
04828    *  @param __lhs  First string.
04829    *  @param __rhs  Last string.
04830    *  @return  New string with @a __lhs followed by @a __rhs.
04831    */
04832   template<typename _CharT, typename _Traits, typename _Alloc>
04833     inline basic_string<_CharT, _Traits, _Alloc>
04834     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
04835     {
04836       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
04837       typedef typename __string_type::size_type         __size_type;
04838       __string_type __str(__lhs);
04839       __str.append(__size_type(1), __rhs);
04840       return __str;
04841     }
04842 
04843 #if __cplusplus >= 201103L
04844   template<typename _CharT, typename _Traits, typename _Alloc>
04845     inline basic_string<_CharT, _Traits, _Alloc>
04846     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
04847               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
04848     { return std::move(__lhs.append(__rhs)); }
04849 
04850   template<typename _CharT, typename _Traits, typename _Alloc>
04851     inline basic_string<_CharT, _Traits, _Alloc>
04852     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
04853               basic_string<_CharT, _Traits, _Alloc>&& __rhs)
04854     { return std::move(__rhs.insert(0, __lhs)); }
04855 
04856   template<typename _CharT, typename _Traits, typename _Alloc>
04857     inline basic_string<_CharT, _Traits, _Alloc>
04858     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
04859               basic_string<_CharT, _Traits, _Alloc>&& __rhs)
04860     {
04861       const auto __size = __lhs.size() + __rhs.size();
04862       const bool __cond = (__size > __lhs.capacity()
04863                            && __size <= __rhs.capacity());
04864       return __cond ? std::move(__rhs.insert(0, __lhs))
04865                     : std::move(__lhs.append(__rhs));
04866     }
04867 
04868   template<typename _CharT, typename _Traits, typename _Alloc>
04869     inline basic_string<_CharT, _Traits, _Alloc>
04870     operator+(const _CharT* __lhs,
04871               basic_string<_CharT, _Traits, _Alloc>&& __rhs)
04872     { return std::move(__rhs.insert(0, __lhs)); }
04873 
04874   template<typename _CharT, typename _Traits, typename _Alloc>
04875     inline basic_string<_CharT, _Traits, _Alloc>
04876     operator+(_CharT __lhs,
04877               basic_string<_CharT, _Traits, _Alloc>&& __rhs)
04878     { return std::move(__rhs.insert(0, 1, __lhs)); }
04879 
04880   template<typename _CharT, typename _Traits, typename _Alloc>
04881     inline basic_string<_CharT, _Traits, _Alloc>
04882     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
04883               const _CharT* __rhs)
04884     { return std::move(__lhs.append(__rhs)); }
04885 
04886   template<typename _CharT, typename _Traits, typename _Alloc>
04887     inline basic_string<_CharT, _Traits, _Alloc>
04888     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
04889               _CharT __rhs)
04890     { return std::move(__lhs.append(1, __rhs)); }
04891 #endif
04892 
04893   // operator ==
04894   /**
04895    *  @brief  Test equivalence of two strings.
04896    *  @param __lhs  First string.
04897    *  @param __rhs  Second string.
04898    *  @return  True if @a __lhs.compare(@a __rhs) == 0.  False otherwise.
04899    */
04900   template<typename _CharT, typename _Traits, typename _Alloc>
04901     inline bool
04902     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
04903                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
04904     { return __lhs.compare(__rhs) == 0; }
04905 
04906   template<typename _CharT>
04907     inline
04908     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, bool>::__type
04909     operator==(const basic_string<_CharT>& __lhs,
04910                const basic_string<_CharT>& __rhs)
04911     { return (__lhs.size() == __rhs.size()
04912               && !std::char_traits<_CharT>::compare(__lhs.data(), __rhs.data(),
04913                                                     __lhs.size())); }
04914 
04915   /**
04916    *  @brief  Test equivalence of C string and string.
04917    *  @param __lhs  C string.
04918    *  @param __rhs  String.
04919    *  @return  True if @a __rhs.compare(@a __lhs) == 0.  False otherwise.
04920    */
04921   template<typename _CharT, typename _Traits, typename _Alloc>
04922     inline bool
04923     operator==(const _CharT* __lhs,
04924                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
04925     { return __rhs.compare(__lhs) == 0; }
04926 
04927   /**
04928    *  @brief  Test equivalence of string and C string.
04929    *  @param __lhs  String.
04930    *  @param __rhs  C string.
04931    *  @return  True if @a __lhs.compare(@a __rhs) == 0.  False otherwise.
04932    */
04933   template<typename _CharT, typename _Traits, typename _Alloc>
04934     inline bool
04935     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
04936                const _CharT* __rhs)
04937     { return __lhs.compare(__rhs) == 0; }
04938 
04939   // operator !=
04940   /**
04941    *  @brief  Test difference of two strings.
04942    *  @param __lhs  First string.
04943    *  @param __rhs  Second string.
04944    *  @return  True if @a __lhs.compare(@a __rhs) != 0.  False otherwise.
04945    */
04946   template<typename _CharT, typename _Traits, typename _Alloc>
04947     inline bool
04948     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
04949                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
04950     { return !(__lhs == __rhs); }
04951 
04952   /**
04953    *  @brief  Test difference of C string and string.
04954    *  @param __lhs  C string.
04955    *  @param __rhs  String.
04956    *  @return  True if @a __rhs.compare(@a __lhs) != 0.  False otherwise.
04957    */
04958   template<typename _CharT, typename _Traits, typename _Alloc>
04959     inline bool
04960     operator!=(const _CharT* __lhs,
04961                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
04962     { return !(__lhs == __rhs); }
04963 
04964   /**
04965    *  @brief  Test difference of string and C string.
04966    *  @param __lhs  String.
04967    *  @param __rhs  C string.
04968    *  @return  True if @a __lhs.compare(@a __rhs) != 0.  False otherwise.
04969    */
04970   template<typename _CharT, typename _Traits, typename _Alloc>
04971     inline bool
04972     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
04973                const _CharT* __rhs)
04974     { return !(__lhs == __rhs); }
04975 
04976   // operator <
04977   /**
04978    *  @brief  Test if string precedes string.
04979    *  @param __lhs  First string.
04980    *  @param __rhs  Second string.
04981    *  @return  True if @a __lhs precedes @a __rhs.  False otherwise.
04982    */
04983   template<typename _CharT, typename _Traits, typename _Alloc>
04984     inline bool
04985     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
04986               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
04987     { return __lhs.compare(__rhs) < 0; }
04988 
04989   /**
04990    *  @brief  Test if string precedes C string.
04991    *  @param __lhs  String.
04992    *  @param __rhs  C string.
04993    *  @return  True if @a __lhs precedes @a __rhs.  False otherwise.
04994    */
04995   template<typename _CharT, typename _Traits, typename _Alloc>
04996     inline bool
04997     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
04998               const _CharT* __rhs)
04999     { return __lhs.compare(__rhs) < 0; }
05000 
05001   /**
05002    *  @brief  Test if C string precedes string.
05003    *  @param __lhs  C string.
05004    *  @param __rhs  String.
05005    *  @return  True if @a __lhs precedes @a __rhs.  False otherwise.
05006    */
05007   template<typename _CharT, typename _Traits, typename _Alloc>
05008     inline bool
05009     operator<(const _CharT* __lhs,
05010               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
05011     { return __rhs.compare(__lhs) > 0; }
05012 
05013   // operator >
05014   /**
05015    *  @brief  Test if string follows string.
05016    *  @param __lhs  First string.
05017    *  @param __rhs  Second string.
05018    *  @return  True if @a __lhs follows @a __rhs.  False otherwise.
05019    */
05020   template<typename _CharT, typename _Traits, typename _Alloc>
05021     inline bool
05022     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
05023               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
05024     { return __lhs.compare(__rhs) > 0; }
05025 
05026   /**
05027    *  @brief  Test if string follows C string.
05028    *  @param __lhs  String.
05029    *  @param __rhs  C string.
05030    *  @return  True if @a __lhs follows @a __rhs.  False otherwise.
05031    */
05032   template<typename _CharT, typename _Traits, typename _Alloc>
05033     inline bool
05034     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
05035               const _CharT* __rhs)
05036     { return __lhs.compare(__rhs) > 0; }
05037 
05038   /**
05039    *  @brief  Test if C string follows string.
05040    *  @param __lhs  C string.
05041    *  @param __rhs  String.
05042    *  @return  True if @a __lhs follows @a __rhs.  False otherwise.
05043    */
05044   template<typename _CharT, typename _Traits, typename _Alloc>
05045     inline bool
05046     operator>(const _CharT* __lhs,
05047               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
05048     { return __rhs.compare(__lhs) < 0; }
05049 
05050   // operator <=
05051   /**
05052    *  @brief  Test if string doesn't follow string.
05053    *  @param __lhs  First string.
05054    *  @param __rhs  Second string.
05055    *  @return  True if @a __lhs doesn't follow @a __rhs.  False otherwise.
05056    */
05057   template<typename _CharT, typename _Traits, typename _Alloc>
05058     inline bool
05059     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
05060                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
05061     { return __lhs.compare(__rhs) <= 0; }
05062 
05063   /**
05064    *  @brief  Test if string doesn't follow C string.
05065    *  @param __lhs  String.
05066    *  @param __rhs  C string.
05067    *  @return  True if @a __lhs doesn't follow @a __rhs.  False otherwise.
05068    */
05069   template<typename _CharT, typename _Traits, typename _Alloc>
05070     inline bool
05071     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
05072                const _CharT* __rhs)
05073     { return __lhs.compare(__rhs) <= 0; }
05074 
05075   /**
05076    *  @brief  Test if C string doesn't follow string.
05077    *  @param __lhs  C string.
05078    *  @param __rhs  String.
05079    *  @return  True if @a __lhs doesn't follow @a __rhs.  False otherwise.
05080    */
05081   template<typename _CharT, typename _Traits, typename _Alloc>
05082     inline bool
05083     operator<=(const _CharT* __lhs,
05084                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
05085     { return __rhs.compare(__lhs) >= 0; }
05086 
05087   // operator >=
05088   /**
05089    *  @brief  Test if string doesn't precede string.
05090    *  @param __lhs  First string.
05091    *  @param __rhs  Second string.
05092    *  @return  True if @a __lhs doesn't precede @a __rhs.  False otherwise.
05093    */
05094   template<typename _CharT, typename _Traits, typename _Alloc>
05095     inline bool
05096     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
05097                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
05098     { return __lhs.compare(__rhs) >= 0; }
05099 
05100   /**
05101    *  @brief  Test if string doesn't precede C string.
05102    *  @param __lhs  String.
05103    *  @param __rhs  C string.
05104    *  @return  True if @a __lhs doesn't precede @a __rhs.  False otherwise.
05105    */
05106   template<typename _CharT, typename _Traits, typename _Alloc>
05107     inline bool
05108     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
05109                const _CharT* __rhs)
05110     { return __lhs.compare(__rhs) >= 0; }
05111 
05112   /**
05113    *  @brief  Test if C string doesn't precede string.
05114    *  @param __lhs  C string.
05115    *  @param __rhs  String.
05116    *  @return  True if @a __lhs doesn't precede @a __rhs.  False otherwise.
05117    */
05118   template<typename _CharT, typename _Traits, typename _Alloc>
05119     inline bool
05120     operator>=(const _CharT* __lhs,
05121              const basic_string<_CharT, _Traits, _Alloc>& __rhs)
05122     { return __rhs.compare(__lhs) <= 0; }
05123 
05124   /**
05125    *  @brief  Swap contents of two strings.
05126    *  @param __lhs  First string.
05127    *  @param __rhs  Second string.
05128    *
05129    *  Exchanges the contents of @a __lhs and @a __rhs in constant time.
05130    */
05131   template<typename _CharT, typename _Traits, typename _Alloc>
05132     inline void
05133     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
05134          basic_string<_CharT, _Traits, _Alloc>& __rhs)
05135     { __lhs.swap(__rhs); }
05136 
05137 
05138   /**
05139    *  @brief  Read stream into a string.
05140    *  @param __is  Input stream.
05141    *  @param __str  Buffer to store into.
05142    *  @return  Reference to the input stream.
05143    *
05144    *  Stores characters from @a __is into @a __str until whitespace is
05145    *  found, the end of the stream is encountered, or str.max_size()
05146    *  is reached.  If is.width() is non-zero, that is the limit on the
05147    *  number of characters stored into @a __str.  Any previous
05148    *  contents of @a __str are erased.
05149    */
05150   template<typename _CharT, typename _Traits, typename _Alloc>
05151     basic_istream<_CharT, _Traits>&
05152     operator>>(basic_istream<_CharT, _Traits>& __is,
05153                basic_string<_CharT, _Traits, _Alloc>& __str);
05154 
05155   template<>
05156     basic_istream<char>&
05157     operator>>(basic_istream<char>& __is, basic_string<char>& __str);
05158 
05159   /**
05160    *  @brief  Write string to a stream.
05161    *  @param __os  Output stream.
05162    *  @param __str  String to write out.
05163    *  @return  Reference to the output stream.
05164    *
05165    *  Output characters of @a __str into os following the same rules as for
05166    *  writing a C string.
05167    */
05168   template<typename _CharT, typename _Traits, typename _Alloc>
05169     inline basic_ostream<_CharT, _Traits>&
05170     operator<<(basic_ostream<_CharT, _Traits>& __os,
05171                const basic_string<_CharT, _Traits, _Alloc>& __str)
05172     {
05173       // _GLIBCXX_RESOLVE_LIB_DEFECTS
05174       // 586. string inserter not a formatted function
05175       return __ostream_insert(__os, __str.data(), __str.size());
05176     }
05177 
05178   /**
05179    *  @brief  Read a line from stream into a string.
05180    *  @param __is  Input stream.
05181    *  @param __str  Buffer to store into.
05182    *  @param __delim  Character marking end of line.
05183    *  @return  Reference to the input stream.
05184    *
05185    *  Stores characters from @a __is into @a __str until @a __delim is
05186    *  found, the end of the stream is encountered, or str.max_size()
05187    *  is reached.  Any previous contents of @a __str are erased.  If
05188    *  @a __delim is encountered, it is extracted but not stored into
05189    *  @a __str.
05190    */
05191   template<typename _CharT, typename _Traits, typename _Alloc>
05192     basic_istream<_CharT, _Traits>&
05193     getline(basic_istream<_CharT, _Traits>& __is,
05194             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
05195 
05196   /**
05197    *  @brief  Read a line from stream into a string.
05198    *  @param __is  Input stream.
05199    *  @param __str  Buffer to store into.
05200    *  @return  Reference to the input stream.
05201    *
05202    *  Stores characters from is into @a __str until &apos;\n&apos; is
05203    *  found, the end of the stream is encountered, or str.max_size()
05204    *  is reached.  Any previous contents of @a __str are erased.  If
05205    *  end of line is encountered, it is extracted but not stored into
05206    *  @a __str.
05207    */
05208   template<typename _CharT, typename _Traits, typename _Alloc>
05209     inline basic_istream<_CharT, _Traits>&
05210     getline(basic_istream<_CharT, _Traits>& __is,
05211             basic_string<_CharT, _Traits, _Alloc>& __str)
05212     { return std::getline(__is, __str, __is.widen('\n')); }
05213 
05214 #if __cplusplus >= 201103L
05215   /// Read a line from an rvalue stream into a string.
05216   template<typename _CharT, typename _Traits, typename _Alloc>
05217     inline basic_istream<_CharT, _Traits>&
05218     getline(basic_istream<_CharT, _Traits>&& __is,
05219             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
05220     { return std::getline(__is, __str, __delim); }
05221 
05222   /// Read a line from an rvalue stream into a string.
05223   template<typename _CharT, typename _Traits, typename _Alloc>
05224     inline basic_istream<_CharT, _Traits>&
05225     getline(basic_istream<_CharT, _Traits>&& __is,
05226             basic_string<_CharT, _Traits, _Alloc>& __str)
05227     { return std::getline(__is, __str); }
05228 #endif
05229 
05230   template<>
05231     basic_istream<char>&
05232     getline(basic_istream<char>& __in, basic_string<char>& __str,
05233             char __delim);
05234 
05235 #ifdef _GLIBCXX_USE_WCHAR_T
05236   template<>
05237     basic_istream<wchar_t>&
05238     getline(basic_istream<wchar_t>& __in, basic_string<wchar_t>& __str,
05239             wchar_t __delim);
05240 #endif  
05241 
05242 _GLIBCXX_END_NAMESPACE_VERSION
05243 } // namespace
05244 
05245 #if __cplusplus >= 201103L && defined(_GLIBCXX_USE_C99)
05246 
05247 #include <ext/string_conversions.h>
05248 
05249 namespace std _GLIBCXX_VISIBILITY(default)
05250 {
05251 _GLIBCXX_BEGIN_NAMESPACE_VERSION
05252 _GLIBCXX_BEGIN_NAMESPACE_CXX11
05253 
05254   // 21.4 Numeric Conversions [string.conversions].
05255   inline int
05256   stoi(const string& __str, size_t* __idx = 0, int __base = 10)
05257   { return __gnu_cxx::__stoa<long, int>(&std::strtol, "stoi", __str.c_str(),
05258                                         __idx, __base); }
05259 
05260   inline long
05261   stol(const string& __str, size_t* __idx = 0, int __base = 10)
05262   { return __gnu_cxx::__stoa(&std::strtol, "stol", __str.c_str(),
05263                              __idx, __base); }
05264 
05265   inline unsigned long
05266   stoul(const string& __str, size_t* __idx = 0, int __base = 10)
05267   { return __gnu_cxx::__stoa(&std::strtoul, "stoul", __str.c_str(),
05268                              __idx, __base); }
05269 
05270   inline long long
05271   stoll(const string& __str, size_t* __idx = 0, int __base = 10)
05272   { return __gnu_cxx::__stoa(&std::strtoll, "stoll", __str.c_str(),
05273                              __idx, __base); }
05274 
05275   inline unsigned long long
05276   stoull(const string& __str, size_t* __idx = 0, int __base = 10)
05277   { return __gnu_cxx::__stoa(&std::strtoull, "stoull", __str.c_str(),
05278                              __idx, __base); }
05279 
05280   // NB: strtof vs strtod.
05281   inline float
05282   stof(const string& __str, size_t* __idx = 0)
05283   { return __gnu_cxx::__stoa(&std::strtof, "stof", __str.c_str(), __idx); }
05284 
05285   inline double
05286   stod(const string& __str, size_t* __idx = 0)
05287   { return __gnu_cxx::__stoa(&std::strtod, "stod", __str.c_str(), __idx); }
05288 
05289   inline long double
05290   stold(const string& __str, size_t* __idx = 0)
05291   { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }
05292 
05293   // NB: (v)snprintf vs sprintf.
05294 
05295   // DR 1261.
05296   inline string
05297   to_string(int __val)
05298   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
05299                                            "%d", __val); }
05300 
05301   inline string
05302   to_string(unsigned __val)
05303   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
05304                                            4 * sizeof(unsigned),
05305                                            "%u", __val); }
05306 
05307   inline string
05308   to_string(long __val)
05309   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
05310                                            "%ld", __val); }
05311 
05312   inline string
05313   to_string(unsigned long __val)
05314   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
05315                                            4 * sizeof(unsigned long),
05316                                            "%lu", __val); }
05317 
05318   inline string
05319   to_string(long long __val)
05320   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
05321                                            4 * sizeof(long long),
05322                                            "%lld", __val); }
05323 
05324   inline string
05325   to_string(unsigned long long __val)
05326   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
05327                                            4 * sizeof(unsigned long long),
05328                                            "%llu", __val); }
05329 
05330   inline string
05331   to_string(float __val)
05332   {
05333     const int __n = 
05334       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
05335     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
05336                                            "%f", __val);
05337   }
05338 
05339   inline string
05340   to_string(double __val)
05341   {
05342     const int __n = 
05343       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
05344     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
05345                                            "%f", __val);
05346   }
05347 
05348   inline string
05349   to_string(long double __val)
05350   {
05351     const int __n = 
05352       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
05353     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
05354                                            "%Lf", __val);
05355   }
05356 
05357 #ifdef _GLIBCXX_USE_WCHAR_T
05358   inline int 
05359   stoi(const wstring& __str, size_t* __idx = 0, int __base = 10)
05360   { return __gnu_cxx::__stoa<long, int>(&std::wcstol, "stoi", __str.c_str(),
05361                                         __idx, __base); }
05362 
05363   inline long 
05364   stol(const wstring& __str, size_t* __idx = 0, int __base = 10)
05365   { return __gnu_cxx::__stoa(&std::wcstol, "stol", __str.c_str(),
05366                              __idx, __base); }
05367 
05368   inline unsigned long
05369   stoul(const wstring& __str, size_t* __idx = 0, int __base = 10)
05370   { return __gnu_cxx::__stoa(&std::wcstoul, "stoul", __str.c_str(),
05371                              __idx, __base); }
05372 
05373   inline long long
05374   stoll(const wstring& __str, size_t* __idx = 0, int __base = 10)
05375   { return __gnu_cxx::__stoa(&std::wcstoll, "stoll", __str.c_str(),
05376                              __idx, __base); }
05377 
05378   inline unsigned long long
05379   stoull(const wstring& __str, size_t* __idx = 0, int __base = 10)
05380   { return __gnu_cxx::__stoa(&std::wcstoull, "stoull", __str.c_str(),
05381                              __idx, __base); }
05382 
05383   // NB: wcstof vs wcstod.
05384   inline float
05385   stof(const wstring& __str, size_t* __idx = 0)
05386   { return __gnu_cxx::__stoa(&std::wcstof, "stof", __str.c_str(), __idx); }
05387 
05388   inline double
05389   stod(const wstring& __str, size_t* __idx = 0)
05390   { return __gnu_cxx::__stoa(&std::wcstod, "stod", __str.c_str(), __idx); }
05391 
05392   inline long double
05393   stold(const wstring& __str, size_t* __idx = 0)
05394   { return __gnu_cxx::__stoa(&std::wcstold, "stold", __str.c_str(), __idx); }
05395 
05396 #ifndef _GLIBCXX_HAVE_BROKEN_VSWPRINTF
05397   // DR 1261.
05398   inline wstring
05399   to_wstring(int __val)
05400   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(int),
05401                                             L"%d", __val); }
05402 
05403   inline wstring
05404   to_wstring(unsigned __val)
05405   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
05406                                             4 * sizeof(unsigned),
05407                                             L"%u", __val); }
05408 
05409   inline wstring
05410   to_wstring(long __val)
05411   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(long),
05412                                             L"%ld", __val); }
05413 
05414   inline wstring
05415   to_wstring(unsigned long __val)
05416   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
05417                                             4 * sizeof(unsigned long),
05418                                             L"%lu", __val); }
05419 
05420   inline wstring
05421   to_wstring(long long __val)
05422   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
05423                                             4 * sizeof(long long),
05424                                             L"%lld", __val); }
05425 
05426   inline wstring
05427   to_wstring(unsigned long long __val)
05428   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
05429                                             4 * sizeof(unsigned long long),
05430                                             L"%llu", __val); }
05431 
05432   inline wstring
05433   to_wstring(float __val)
05434   {
05435     const int __n =
05436       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
05437     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
05438                                             L"%f", __val);
05439   }
05440 
05441   inline wstring
05442   to_wstring(double __val)
05443   {
05444     const int __n =
05445       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
05446     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
05447                                             L"%f", __val);
05448   }
05449 
05450   inline wstring
05451   to_wstring(long double __val)
05452   {
05453     const int __n =
05454       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
05455     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
05456                                             L"%Lf", __val);
05457   }
05458 #endif // _GLIBCXX_HAVE_BROKEN_VSWPRINTF
05459 #endif
05460 
05461 _GLIBCXX_END_NAMESPACE_CXX11
05462 _GLIBCXX_END_NAMESPACE_VERSION
05463 } // namespace
05464 
05465 #endif /* C++11 && _GLIBCXX_USE_C99 ... */
05466 
05467 #if __cplusplus >= 201103L
05468 
05469 #include <bits/functional_hash.h>
05470 
05471 namespace std _GLIBCXX_VISIBILITY(default)
05472 {
05473 _GLIBCXX_BEGIN_NAMESPACE_VERSION
05474 
05475   // DR 1182.
05476 
05477 #ifndef _GLIBCXX_COMPATIBILITY_CXX0X
05478   /// std::hash specialization for string.
05479   template<>
05480     struct hash<string>
05481     : public __hash_base<size_t, string>
05482     {
05483       size_t
05484       operator()(const string& __s) const noexcept
05485       { return std::_Hash_impl::hash(__s.data(), __s.length()); }
05486     };
05487 
05488   template<>
05489     struct __is_fast_hash<hash<string>> : std::false_type
05490     { };
05491 
05492 #ifdef _GLIBCXX_USE_WCHAR_T
05493   /// std::hash specialization for wstring.
05494   template<>
05495     struct hash<wstring>
05496     : public __hash_base<size_t, wstring>
05497     {
05498       size_t
05499       operator()(const wstring& __s) const noexcept
05500       { return std::_Hash_impl::hash(__s.data(),
05501                                      __s.length() * sizeof(wchar_t)); }
05502     };
05503 
05504   template<>
05505     struct __is_fast_hash<hash<wstring>> : std::false_type
05506     { };
05507 #endif
05508 #endif /* _GLIBCXX_COMPATIBILITY_CXX0X */
05509 
05510 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
05511   /// std::hash specialization for u16string.
05512   template<>
05513     struct hash<u16string>
05514     : public __hash_base<size_t, u16string>
05515     {
05516       size_t
05517       operator()(const u16string& __s) const noexcept
05518       { return std::_Hash_impl::hash(__s.data(),
05519                                      __s.length() * sizeof(char16_t)); }
05520     };
05521 
05522   template<>
05523     struct __is_fast_hash<hash<u16string>> : std::false_type
05524     { };
05525 
05526   /// std::hash specialization for u32string.
05527   template<>
05528     struct hash<u32string>
05529     : public __hash_base<size_t, u32string>
05530     {
05531       size_t
05532       operator()(const u32string& __s) const noexcept
05533       { return std::_Hash_impl::hash(__s.data(),
05534                                      __s.length() * sizeof(char32_t)); }
05535     };
05536 
05537   template<>
05538     struct __is_fast_hash<hash<u32string>> : std::false_type
05539     { };
05540 #endif
05541 
05542 #if __cplusplus > 201103L
05543 
05544 #define __cpp_lib_string_udls 201304
05545 
05546   inline namespace literals
05547   {
05548   inline namespace string_literals
05549   {
05550 
05551     _GLIBCXX_DEFAULT_ABI_TAG
05552     inline basic_string<char>
05553     operator""s(const char* __str, size_t __len)
05554     { return basic_string<char>{__str, __len}; }
05555 
05556 #ifdef _GLIBCXX_USE_WCHAR_T
05557     _GLIBCXX_DEFAULT_ABI_TAG
05558     inline basic_string<wchar_t>
05559     operator""s(const wchar_t* __str, size_t __len)
05560     { return basic_string<wchar_t>{__str, __len}; }
05561 #endif
05562 
05563 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
05564     _GLIBCXX_DEFAULT_ABI_TAG
05565     inline basic_string<char16_t>
05566     operator""s(const char16_t* __str, size_t __len)
05567     { return basic_string<char16_t>{__str, __len}; }
05568 
05569     _GLIBCXX_DEFAULT_ABI_TAG
05570     inline basic_string<char32_t>
05571     operator""s(const char32_t* __str, size_t __len)
05572     { return basic_string<char32_t>{__str, __len}; }
05573 #endif
05574 
05575   } // inline namespace string_literals
05576   } // inline namespace literals
05577 
05578 #endif // __cplusplus > 201103L
05579 
05580 _GLIBCXX_END_NAMESPACE_VERSION
05581 } // namespace std
05582 
05583 #endif // C++11
05584 
05585 #endif /* _BASIC_STRING_H */