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