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