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