libstdc++
basic_string.h
Go to the documentation of this file.
00001 // Components for manipulating sequences of characters -*- C++ -*-
00002 
00003 // Copyright (C) 1997-2013 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 <debug/debug.h>
00041 #if __cplusplus >= 201103L
00042 #include <initializer_list>
00043 #endif
00044 
00045 namespace std _GLIBCXX_VISIBILITY(default)
00046 {
00047 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00048 
00049   /**
00050    *  @class basic_string basic_string.h <string>
00051    *  @brief  Managing sequences of characters and character-like objects.
00052    *
00053    *  @ingroup strings
00054    *  @ingroup sequences
00055    *
00056    *  @tparam _CharT  Type of character
00057    *  @tparam _Traits  Traits for character type, defaults to
00058    *                   char_traits<_CharT>.
00059    *  @tparam _Alloc  Allocator type, defaults to allocator<_CharT>.
00060    *
00061    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00062    *  <a href="tables.html#66">reversible container</a>, and a
00063    *  <a href="tables.html#67">sequence</a>.  Of the
00064    *  <a href="tables.html#68">optional sequence requirements</a>, only
00065    *  @c push_back, @c at, and @c %array access are supported.
00066    *
00067    *  @doctodo
00068    *
00069    *
00070    *  Documentation?  What's that?
00071    *  Nathan Myers <ncm@cantrip.org>.
00072    *
00073    *  A string looks like this:
00074    *
00075    *  @code
00076    *                                        [_Rep]
00077    *                                        _M_length
00078    *   [basic_string<char_type>]            _M_capacity
00079    *   _M_dataplus                          _M_refcount
00080    *   _M_p ---------------->               unnamed array of char_type
00081    *  @endcode
00082    *
00083    *  Where the _M_p points to the first character in the string, and
00084    *  you cast it to a pointer-to-_Rep and subtract 1 to get a
00085    *  pointer to the header.
00086    *
00087    *  This approach has the enormous advantage that a string object
00088    *  requires only one allocation.  All the ugliness is confined
00089    *  within a single %pair of inline functions, which each compile to
00090    *  a single @a add instruction: _Rep::_M_data(), and
00091    *  string::_M_rep(); and the allocation function which gets a
00092    *  block of raw bytes and with room enough and constructs a _Rep
00093    *  object at the front.
00094    *
00095    *  The reason you want _M_data pointing to the character %array and
00096    *  not the _Rep is so that the debugger can see the string
00097    *  contents. (Probably we should add a non-inline member to get
00098    *  the _Rep for the debugger to use, so users can check the actual
00099    *  string length.)
00100    *
00101    *  Note that the _Rep object is a POD so that you can have a
00102    *  static <em>empty string</em> _Rep object already @a constructed before
00103    *  static constructors have run.  The reference-count encoding is
00104    *  chosen so that a 0 indicates one reference, so you never try to
00105    *  destroy the empty-string _Rep object.
00106    *
00107    *  All but the last paragraph is considered pretty conventional
00108    *  for a C++ string implementation.
00109   */
00110   // 21.3  Template class basic_string
00111   template<typename _CharT, typename _Traits, typename _Alloc>
00112     class basic_string
00113     {
00114       typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;
00115 
00116       // Types:
00117     public:
00118       typedef _Traits                       traits_type;
00119       typedef typename _Traits::char_type           value_type;
00120       typedef _Alloc                        allocator_type;
00121       typedef typename _CharT_alloc_type::size_type     size_type;
00122       typedef typename _CharT_alloc_type::difference_type   difference_type;
00123       typedef typename _CharT_alloc_type::reference     reference;
00124       typedef typename _CharT_alloc_type::const_reference   const_reference;
00125       typedef typename _CharT_alloc_type::pointer       pointer;
00126       typedef typename _CharT_alloc_type::const_pointer     const_pointer;
00127       typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
00128       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
00129                                                             const_iterator;
00130       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00131       typedef std::reverse_iterator<iterator>           reverse_iterator;
00132 
00133     private:
00134       // _Rep: string representation
00135       //   Invariants:
00136       //   1. String really contains _M_length + 1 characters: due to 21.3.4
00137       //      must be kept null-terminated.
00138       //   2. _M_capacity >= _M_length
00139       //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).
00140       //   3. _M_refcount has three states:
00141       //      -1: leaked, one reference, no ref-copies allowed, non-const.
00142       //       0: one reference, non-const.
00143       //     n>0: n + 1 references, operations require a lock, const.
00144       //   4. All fields==0 is an empty string, given the extra storage
00145       //      beyond-the-end for a null terminator; thus, the shared
00146       //      empty string representation needs no constructor.
00147 
00148       struct _Rep_base
00149       {
00150     size_type       _M_length;
00151     size_type       _M_capacity;
00152     _Atomic_word        _M_refcount;
00153       };
00154 
00155       struct _Rep : _Rep_base
00156       {
00157     // Types:
00158     typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
00159 
00160     // (Public) Data members:
00161 
00162     // The maximum number of individual char_type elements of an
00163     // individual string is determined by _S_max_size. This is the
00164     // value that will be returned by max_size().  (Whereas npos
00165     // is the maximum number of bytes the allocator can allocate.)
00166     // If one was to divvy up the theoretical largest size string,
00167     // with a terminating character and m _CharT elements, it'd
00168     // look like this:
00169     // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
00170     // Solving for m:
00171     // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
00172     // In addition, this implementation quarters this amount.
00173     static const size_type  _S_max_size;
00174     static const _CharT _S_terminal;
00175 
00176     // The following storage is init'd to 0 by the linker, resulting
00177         // (carefully) in an empty string with one reference.
00178         static size_type _S_empty_rep_storage[];
00179 
00180         static _Rep&
00181         _S_empty_rep()
00182         { 
00183       // NB: Mild hack to avoid strict-aliasing warnings.  Note that
00184       // _S_empty_rep_storage is never modified and the punning should
00185       // be reasonably safe in this case.
00186       void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);
00187       return *reinterpret_cast<_Rep*>(__p);
00188     }
00189 
00190         bool
00191     _M_is_leaked() const
00192         { return this->_M_refcount < 0; }
00193 
00194         bool
00195     _M_is_shared() const
00196         { return this->_M_refcount > 0; }
00197 
00198         void
00199     _M_set_leaked()
00200         { this->_M_refcount = -1; }
00201 
00202         void
00203     _M_set_sharable()
00204         { this->_M_refcount = 0; }
00205 
00206     void
00207     _M_set_length_and_sharable(size_type __n)
00208     {
00209 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
00210       if (__builtin_expect(this != &_S_empty_rep(), false))
00211 #endif
00212         {
00213           this->_M_set_sharable();  // One reference.
00214           this->_M_length = __n;
00215           traits_type::assign(this->_M_refdata()[__n], _S_terminal);
00216           // grrr. (per 21.3.4)
00217           // You cannot leave those LWG people alone for a second.
00218         }
00219     }
00220 
00221     _CharT*
00222     _M_refdata() throw()
00223     { return reinterpret_cast<_CharT*>(this + 1); }
00224 
00225     _CharT*
00226     _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
00227     {
00228       return (!_M_is_leaked() && __alloc1 == __alloc2)
00229               ? _M_refcopy() : _M_clone(__alloc1);
00230     }
00231 
00232     // Create & Destroy
00233     static _Rep*
00234     _S_create(size_type, size_type, const _Alloc&);
00235 
00236     void
00237     _M_dispose(const _Alloc& __a)
00238     {
00239 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
00240       if (__builtin_expect(this != &_S_empty_rep(), false))
00241 #endif
00242         {
00243           // Be race-detector-friendly.  For more info see bits/c++config.
00244           _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this->_M_refcount);
00245           if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
00246                              -1) <= 0)
00247         {
00248           _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);
00249           _M_destroy(__a);
00250         }
00251         }
00252     }  // XXX MT
00253 
00254     void
00255     _M_destroy(const _Alloc&) throw();
00256 
00257     _CharT*
00258     _M_refcopy() throw()
00259     {
00260 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
00261       if (__builtin_expect(this != &_S_empty_rep(), false))
00262 #endif
00263             __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
00264       return _M_refdata();
00265     }  // XXX MT
00266 
00267     _CharT*
00268     _M_clone(const _Alloc&, size_type __res = 0);
00269       };
00270 
00271       // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
00272       struct _Alloc_hider : _Alloc
00273       {
00274     _Alloc_hider(_CharT* __dat, const _Alloc& __a)
00275     : _Alloc(__a), _M_p(__dat) { }
00276 
00277     _CharT* _M_p; // The actual data.
00278       };
00279 
00280     public:
00281       // Data Members (public):
00282       // NB: This is an unsigned type, and thus represents the maximum
00283       // size that the allocator can hold.
00284       ///  Value returned by various member functions when they fail.
00285       static const size_type    npos = static_cast<size_type>(-1);
00286 
00287     private:
00288       // Data Members (private):
00289       mutable _Alloc_hider  _M_dataplus;
00290 
00291       _CharT*
00292       _M_data() const
00293       { return  _M_dataplus._M_p; }
00294 
00295       _CharT*
00296       _M_data(_CharT* __p)
00297       { return (_M_dataplus._M_p = __p); }
00298 
00299       _Rep*
00300       _M_rep() const
00301       { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
00302 
00303       // For the internal use we have functions similar to `begin'/`end'
00304       // but they do not call _M_leak.
00305       iterator
00306       _M_ibegin() const
00307       { return iterator(_M_data()); }
00308 
00309       iterator
00310       _M_iend() const
00311       { return iterator(_M_data() + this->size()); }
00312 
00313       void
00314       _M_leak()    // for use in begin() & non-const op[]
00315       {
00316     if (!_M_rep()->_M_is_leaked())
00317       _M_leak_hard();
00318       }
00319 
00320       size_type
00321       _M_check(size_type __pos, const char* __s) const
00322       {
00323     if (__pos > this->size())
00324       __throw_out_of_range(__N(__s));
00325     return __pos;
00326       }
00327 
00328       void
00329       _M_check_length(size_type __n1, size_type __n2, const char* __s) const
00330       {
00331     if (this->max_size() - (this->size() - __n1) < __n2)
00332       __throw_length_error(__N(__s));
00333       }
00334 
00335       // NB: _M_limit doesn't check for a bad __pos value.
00336       size_type
00337       _M_limit(size_type __pos, size_type __off) const
00338       {
00339     const bool __testoff =  __off < this->size() - __pos;
00340     return __testoff ? __off : this->size() - __pos;
00341       }
00342 
00343       // True if _Rep and source do not overlap.
00344       bool
00345       _M_disjunct(const _CharT* __s) const
00346       {
00347     return (less<const _CharT*>()(__s, _M_data())
00348         || less<const _CharT*>()(_M_data() + this->size(), __s));
00349       }
00350 
00351       // When __n = 1 way faster than the general multichar
00352       // traits_type::copy/move/assign.
00353       static void
00354       _M_copy(_CharT* __d, const _CharT* __s, size_type __n)
00355       {
00356     if (__n == 1)
00357       traits_type::assign(*__d, *__s);
00358     else
00359       traits_type::copy(__d, __s, __n);
00360       }
00361 
00362       static void
00363       _M_move(_CharT* __d, const _CharT* __s, size_type __n)
00364       {
00365     if (__n == 1)
00366       traits_type::assign(*__d, *__s);
00367     else
00368       traits_type::move(__d, __s, __n);   
00369       }
00370 
00371       static void
00372       _M_assign(_CharT* __d, size_type __n, _CharT __c)
00373       {
00374     if (__n == 1)
00375       traits_type::assign(*__d, __c);
00376     else
00377       traits_type::assign(__d, __n, __c);     
00378       }
00379 
00380       // _S_copy_chars is a separate template to permit specialization
00381       // to optimize for the common case of pointers as iterators.
00382       template<class _Iterator>
00383         static void
00384         _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
00385         {
00386       for (; __k1 != __k2; ++__k1, ++__p)
00387         traits_type::assign(*__p, *__k1); // These types are off.
00388     }
00389 
00390       static void
00391       _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2)
00392       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
00393 
00394       static void
00395       _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
00396       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
00397 
00398       static void
00399       _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2)
00400       { _M_copy(__p, __k1, __k2 - __k1); }
00401 
00402       static void
00403       _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
00404       { _M_copy(__p, __k1, __k2 - __k1); }
00405 
00406       static int
00407       _S_compare(size_type __n1, size_type __n2)
00408       {
00409     const difference_type __d = difference_type(__n1 - __n2);
00410 
00411     if (__d > __gnu_cxx::__numeric_traits<int>::__max)
00412       return __gnu_cxx::__numeric_traits<int>::__max;
00413     else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
00414       return __gnu_cxx::__numeric_traits<int>::__min;
00415     else
00416       return int(__d);
00417       }
00418 
00419       void
00420       _M_mutate(size_type __pos, size_type __len1, size_type __len2);
00421 
00422       void
00423       _M_leak_hard();
00424 
00425       static _Rep&
00426       _S_empty_rep()
00427       { return _Rep::_S_empty_rep(); }
00428 
00429     public:
00430       // Construct/copy/destroy:
00431       // NB: We overload ctors in some cases instead of using default
00432       // arguments, per 17.4.4.4 para. 2 item 2.
00433 
00434       /**
00435        *  @brief  Default constructor creates an empty string.
00436        */
00437       basic_string()
00438 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
00439       : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
00440 #else
00441       : _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()){ }
00442 #endif
00443 
00444       /**
00445        *  @brief  Construct an empty string using allocator @a a.
00446        */
00447       explicit
00448       basic_string(const _Alloc& __a);
00449 
00450       // NB: per LWG issue 42, semantics different from IS:
00451       /**
00452        *  @brief  Construct string with copy of value of @a str.
00453        *  @param  __str  Source string.
00454        */
00455       basic_string(const basic_string& __str);
00456       /**
00457        *  @brief  Construct string as copy of a substring.
00458        *  @param  __str  Source string.
00459        *  @param  __pos  Index of first character to copy from.
00460        *  @param  __n  Number of characters to copy (default remainder).
00461        */
00462       basic_string(const basic_string& __str, size_type __pos,
00463            size_type __n = npos);
00464       /**
00465        *  @brief  Construct string as copy of a substring.
00466        *  @param  __str  Source string.
00467        *  @param  __pos  Index of first character to copy from.
00468        *  @param  __n  Number of characters to copy.
00469        *  @param  __a  Allocator to use.
00470        */
00471       basic_string(const basic_string& __str, size_type __pos,
00472            size_type __n, const _Alloc& __a);
00473 
00474       /**
00475        *  @brief  Construct string initialized by a character %array.
00476        *  @param  __s  Source character %array.
00477        *  @param  __n  Number of characters to copy.
00478        *  @param  __a  Allocator to use (default is default allocator).
00479        *
00480        *  NB: @a __s must have at least @a __n characters, &apos;\\0&apos;
00481        *  has no special meaning.
00482        */
00483       basic_string(const _CharT* __s, size_type __n,
00484            const _Alloc& __a = _Alloc());
00485       /**
00486        *  @brief  Construct string as copy of a C string.
00487        *  @param  __s  Source C string.
00488        *  @param  __a  Allocator to use (default is default allocator).
00489        */
00490       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
00491       /**
00492        *  @brief  Construct string as multiple characters.
00493        *  @param  __n  Number of characters.
00494        *  @param  __c  Character to use.
00495        *  @param  __a  Allocator to use (default is default allocator).
00496        */
00497       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
00498 
00499 #if __cplusplus >= 201103L
00500       /**
00501        *  @brief  Move construct string.
00502        *  @param  __str  Source string.
00503        *
00504        *  The newly-created string contains the exact contents of @a __str.
00505        *  @a __str is a valid, but unspecified string.
00506        **/
00507       basic_string(basic_string&& __str) noexcept
00508       : _M_dataplus(__str._M_dataplus)
00509       {
00510 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
00511     __str._M_data(_S_empty_rep()._M_refdata());
00512 #else
00513     __str._M_data(_S_construct(size_type(), _CharT(), get_allocator()));
00514 #endif
00515       }
00516 
00517       /**
00518        *  @brief  Construct string from an initializer %list.
00519        *  @param  __l  std::initializer_list of characters.
00520        *  @param  __a  Allocator to use (default is default allocator).
00521        */
00522       basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc());
00523 #endif // C++11
00524 
00525       /**
00526        *  @brief  Construct string as copy of a range.
00527        *  @param  __beg  Start of range.
00528        *  @param  __end  End of range.
00529        *  @param  __a  Allocator to use (default is default allocator).
00530        */
00531       template<class _InputIterator>
00532         basic_string(_InputIterator __beg, _InputIterator __end,
00533              const _Alloc& __a = _Alloc());
00534 
00535       /**
00536        *  @brief  Destroy the string instance.
00537        */
00538       ~basic_string() _GLIBCXX_NOEXCEPT
00539       { _M_rep()->_M_dispose(this->get_allocator()); }
00540 
00541       /**
00542        *  @brief  Assign the value of @a str to this string.
00543        *  @param  __str  Source string.
00544        */
00545       basic_string&
00546       operator=(const basic_string& __str) 
00547       { return this->assign(__str); }
00548 
00549       /**
00550        *  @brief  Copy contents of @a s into this string.
00551        *  @param  __s  Source null-terminated string.
00552        */
00553       basic_string&
00554       operator=(const _CharT* __s) 
00555       { return this->assign(__s); }
00556 
00557       /**
00558        *  @brief  Set value to string of length 1.
00559        *  @param  __c  Source character.
00560        *
00561        *  Assigning to a character makes this string length 1 and
00562        *  (*this)[0] == @a c.
00563        */
00564       basic_string&
00565       operator=(_CharT __c) 
00566       { 
00567     this->assign(1, __c); 
00568     return *this;
00569       }
00570 
00571 #if __cplusplus >= 201103L
00572       /**
00573        *  @brief  Move assign the value of @a str to this string.
00574        *  @param  __str  Source string.
00575        *
00576        *  The contents of @a str are moved into this string (without copying).
00577        *  @a str is a valid, but unspecified string.
00578        **/
00579       basic_string&
00580       operator=(basic_string&& __str)
00581       {
00582     // NB: DR 1204.
00583     this->swap(__str);
00584     return *this;
00585       }
00586 
00587       /**
00588        *  @brief  Set value to string constructed from initializer %list.
00589        *  @param  __l  std::initializer_list.
00590        */
00591       basic_string&
00592       operator=(initializer_list<_CharT> __l)
00593       {
00594     this->assign(__l.begin(), __l.size());
00595     return *this;
00596       }
00597 #endif // C++11
00598 
00599       // Iterators:
00600       /**
00601        *  Returns a read/write iterator that points to the first character in
00602        *  the %string.  Unshares the string.
00603        */
00604       iterator
00605       begin() _GLIBCXX_NOEXCEPT
00606       {
00607     _M_leak();
00608     return iterator(_M_data());
00609       }
00610 
00611       /**
00612        *  Returns a read-only (constant) iterator that points to the first
00613        *  character in the %string.
00614        */
00615       const_iterator
00616       begin() const _GLIBCXX_NOEXCEPT
00617       { return const_iterator(_M_data()); }
00618 
00619       /**
00620        *  Returns a read/write iterator that points one past the last
00621        *  character in the %string.  Unshares the string.
00622        */
00623       iterator
00624       end() _GLIBCXX_NOEXCEPT
00625       {
00626     _M_leak();
00627     return iterator(_M_data() + this->size());
00628       }
00629 
00630       /**
00631        *  Returns a read-only (constant) iterator that points one past the
00632        *  last character in the %string.
00633        */
00634       const_iterator
00635       end() const _GLIBCXX_NOEXCEPT
00636       { return const_iterator(_M_data() + this->size()); }
00637 
00638       /**
00639        *  Returns a read/write reverse iterator that points to the last
00640        *  character in the %string.  Iteration is done in reverse element
00641        *  order.  Unshares the string.
00642        */
00643       reverse_iterator
00644       rbegin() _GLIBCXX_NOEXCEPT
00645       { return reverse_iterator(this->end()); }
00646 
00647       /**
00648        *  Returns a read-only (constant) reverse iterator that points
00649        *  to the last character in the %string.  Iteration is done in
00650        *  reverse element order.
00651        */
00652       const_reverse_iterator
00653       rbegin() const _GLIBCXX_NOEXCEPT
00654       { return const_reverse_iterator(this->end()); }
00655 
00656       /**
00657        *  Returns a read/write reverse iterator that points to one before the
00658        *  first character in the %string.  Iteration is done in reverse
00659        *  element order.  Unshares the string.
00660        */
00661       reverse_iterator
00662       rend() _GLIBCXX_NOEXCEPT
00663       { return reverse_iterator(this->begin()); }
00664 
00665       /**
00666        *  Returns a read-only (constant) reverse iterator that points
00667        *  to one before the first character in the %string.  Iteration
00668        *  is done in reverse element order.
00669        */
00670       const_reverse_iterator
00671       rend() const _GLIBCXX_NOEXCEPT
00672       { return const_reverse_iterator(this->begin()); }
00673 
00674 #if __cplusplus >= 201103L
00675       /**
00676        *  Returns a read-only (constant) iterator that points to the first
00677        *  character in the %string.
00678        */
00679       const_iterator
00680       cbegin() const noexcept
00681       { return const_iterator(this->_M_data()); }
00682 
00683       /**
00684        *  Returns a read-only (constant) iterator that points one past the
00685        *  last character in the %string.
00686        */
00687       const_iterator
00688       cend() const noexcept
00689       { return const_iterator(this->_M_data() + this->size()); }
00690 
00691       /**
00692        *  Returns a read-only (constant) reverse iterator that points
00693        *  to the last character in the %string.  Iteration is done in
00694        *  reverse element order.
00695        */
00696       const_reverse_iterator
00697       crbegin() const noexcept
00698       { return const_reverse_iterator(this->end()); }
00699 
00700       /**
00701        *  Returns a read-only (constant) reverse iterator that points
00702        *  to one before the first character in the %string.  Iteration
00703        *  is done in reverse element order.
00704        */
00705       const_reverse_iterator
00706       crend() const noexcept
00707       { return const_reverse_iterator(this->begin()); }
00708 #endif
00709 
00710     public:
00711       // Capacity:
00712       ///  Returns the number of characters in the string, not including any
00713       ///  null-termination.
00714       size_type
00715       size() const _GLIBCXX_NOEXCEPT
00716       { return _M_rep()->_M_length; }
00717 
00718       ///  Returns the number of characters in the string, not including any
00719       ///  null-termination.
00720       size_type
00721       length() const _GLIBCXX_NOEXCEPT
00722       { return _M_rep()->_M_length; }
00723 
00724       ///  Returns the size() of the largest possible %string.
00725       size_type
00726       max_size() const _GLIBCXX_NOEXCEPT
00727       { return _Rep::_S_max_size; }
00728 
00729       /**
00730        *  @brief  Resizes the %string to the specified number of characters.
00731        *  @param  __n  Number of characters the %string should contain.
00732        *  @param  __c  Character to fill any new elements.
00733        *
00734        *  This function will %resize the %string to the specified
00735        *  number of characters.  If the number is smaller than the
00736        *  %string's current size the %string is truncated, otherwise
00737        *  the %string is extended and new elements are %set to @a __c.
00738        */
00739       void
00740       resize(size_type __n, _CharT __c);
00741 
00742       /**
00743        *  @brief  Resizes the %string to the specified number of characters.
00744        *  @param  __n  Number of characters the %string should contain.
00745        *
00746        *  This function will resize the %string to the specified length.  If
00747        *  the new size is smaller than the %string's current size the %string
00748        *  is truncated, otherwise the %string is extended and new characters
00749        *  are default-constructed.  For basic types such as char, this means
00750        *  setting them to 0.
00751        */
00752       void
00753       resize(size_type __n)
00754       { this->resize(__n, _CharT()); }
00755 
00756 #if __cplusplus >= 201103L
00757       ///  A non-binding request to reduce capacity() to size().
00758       void
00759       shrink_to_fit()
00760       {
00761     if (capacity() > size())
00762       {
00763         __try
00764           { reserve(0); }
00765         __catch(...)
00766           { }
00767       }
00768       }
00769 #endif
00770 
00771       /**
00772        *  Returns the total number of characters that the %string can hold
00773        *  before needing to allocate more memory.
00774        */
00775       size_type
00776       capacity() const _GLIBCXX_NOEXCEPT
00777       { return _M_rep()->_M_capacity; }
00778 
00779       /**
00780        *  @brief  Attempt to preallocate enough memory for specified number of
00781        *          characters.
00782        *  @param  __res_arg  Number of characters required.
00783        *  @throw  std::length_error  If @a __res_arg exceeds @c max_size().
00784        *
00785        *  This function attempts to reserve enough memory for the
00786        *  %string to hold the specified number of characters.  If the
00787        *  number requested is more than max_size(), length_error is
00788        *  thrown.
00789        *
00790        *  The advantage of this function is that if optimal code is a
00791        *  necessity and the user can determine the string length that will be
00792        *  required, the user can reserve the memory in %advance, and thus
00793        *  prevent a possible reallocation of memory and copying of %string
00794        *  data.
00795        */
00796       void
00797       reserve(size_type __res_arg = 0);
00798 
00799       /**
00800        *  Erases the string, making it empty.
00801        */
00802       void
00803       clear() _GLIBCXX_NOEXCEPT
00804       { _M_mutate(0, this->size(), 0); }
00805 
00806       /**
00807        *  Returns true if the %string is empty.  Equivalent to 
00808        *  <code>*this == ""</code>.
00809        */
00810       bool
00811       empty() const _GLIBCXX_NOEXCEPT
00812       { return this->size() == 0; }
00813 
00814       // Element access:
00815       /**
00816        *  @brief  Subscript access to the data contained in the %string.
00817        *  @param  __pos  The index of the character to access.
00818        *  @return  Read-only (constant) reference to the character.
00819        *
00820        *  This operator allows for easy, array-style, data access.
00821        *  Note that data access with this operator is unchecked and
00822        *  out_of_range lookups are not defined. (For checked lookups
00823        *  see at().)
00824        */
00825       const_reference
00826       operator[] (size_type __pos) const
00827       {
00828     _GLIBCXX_DEBUG_ASSERT(__pos <= size());
00829     return _M_data()[__pos];
00830       }
00831 
00832       /**
00833        *  @brief  Subscript access to the data contained in the %string.
00834        *  @param  __pos  The index of the character to access.
00835        *  @return  Read/write reference to the character.
00836        *
00837        *  This operator allows for easy, array-style, data access.
00838        *  Note that data access with this operator is unchecked and
00839        *  out_of_range lookups are not defined. (For checked lookups
00840        *  see at().)  Unshares the string.
00841        */
00842       reference
00843       operator[](size_type __pos)
00844       {
00845         // allow pos == size() as v3 extension:
00846     _GLIBCXX_DEBUG_ASSERT(__pos <= size());
00847         // but be strict in pedantic mode:
00848     _GLIBCXX_DEBUG_PEDASSERT(__pos < size());
00849     _M_leak();
00850     return _M_data()[__pos];
00851       }
00852 
00853       /**
00854        *  @brief  Provides access to the data contained in the %string.
00855        *  @param __n The index of the character to access.
00856        *  @return  Read-only (const) reference to the character.
00857        *  @throw  std::out_of_range  If @a n is an invalid index.
00858        *
00859        *  This function provides for safer data access.  The parameter is
00860        *  first checked that it is in the range of the string.  The function
00861        *  throws out_of_range if the check fails.
00862        */
00863       const_reference
00864       at(size_type __n) const
00865       {
00866     if (__n >= this->size())
00867       __throw_out_of_range(__N("basic_string::at"));
00868     return _M_data()[__n];
00869       }
00870 
00871       /**
00872        *  @brief  Provides access to the data contained in the %string.
00873        *  @param __n The index of the character to access.
00874        *  @return  Read/write reference to the character.
00875        *  @throw  std::out_of_range  If @a n is an invalid index.
00876        *
00877        *  This function provides for safer data access.  The parameter is
00878        *  first checked that it is in the range of the string.  The function
00879        *  throws out_of_range if the check fails.  Success results in
00880        *  unsharing the string.
00881        */
00882       reference
00883       at(size_type __n)
00884       {
00885     if (__n >= size())
00886       __throw_out_of_range(__N("basic_string::at"));
00887     _M_leak();
00888     return _M_data()[__n];
00889       }
00890 
00891 #if __cplusplus >= 201103L
00892       /**
00893        *  Returns a read/write reference to the data at the first
00894        *  element of the %string.
00895        */
00896       reference
00897       front()
00898       { return operator[](0); }
00899 
00900       /**
00901        *  Returns a read-only (constant) reference to the data at the first
00902        *  element of the %string.
00903        */
00904       const_reference
00905       front() const
00906       { return operator[](0); }
00907 
00908       /**
00909        *  Returns a read/write reference to the data at the last
00910        *  element of the %string.
00911        */
00912       reference
00913       back()
00914       { return operator[](this->size() - 1); }
00915 
00916       /**
00917        *  Returns a read-only (constant) reference to the data at the
00918        *  last element of the %string.
00919        */
00920       const_reference
00921       back() const
00922       { return operator[](this->size() - 1); }
00923 #endif
00924 
00925       // Modifiers:
00926       /**
00927        *  @brief  Append a string to this string.
00928        *  @param __str  The string to append.
00929        *  @return  Reference to this string.
00930        */
00931       basic_string&
00932       operator+=(const basic_string& __str)
00933       { return this->append(__str); }
00934 
00935       /**
00936        *  @brief  Append a C string.
00937        *  @param __s  The C string to append.
00938        *  @return  Reference to this string.
00939        */
00940       basic_string&
00941       operator+=(const _CharT* __s)
00942       { return this->append(__s); }
00943 
00944       /**
00945        *  @brief  Append a character.
00946        *  @param __c  The character to append.
00947        *  @return  Reference to this string.
00948        */
00949       basic_string&
00950       operator+=(_CharT __c)
00951       { 
00952     this->push_back(__c);
00953     return *this;
00954       }
00955 
00956 #if __cplusplus >= 201103L
00957       /**
00958        *  @brief  Append an initializer_list of characters.
00959        *  @param __l  The initializer_list of characters to be appended.
00960        *  @return  Reference to this string.
00961        */
00962       basic_string&
00963       operator+=(initializer_list<_CharT> __l)
00964       { return this->append(__l.begin(), __l.size()); }
00965 #endif // C++11
00966 
00967       /**
00968        *  @brief  Append a string to this string.
00969        *  @param __str  The string to append.
00970        *  @return  Reference to this string.
00971        */
00972       basic_string&
00973       append(const basic_string& __str);
00974 
00975       /**
00976        *  @brief  Append a substring.
00977        *  @param __str  The string to append.
00978        *  @param __pos  Index of the first character of str to append.
00979        *  @param __n  The number of characters to append.
00980        *  @return  Reference to this string.
00981        *  @throw  std::out_of_range if @a __pos is not a valid index.
00982        *
00983        *  This function appends @a __n characters from @a __str
00984        *  starting at @a __pos to this string.  If @a __n is is larger
00985        *  than the number of available characters in @a __str, the
00986        *  remainder of @a __str is appended.
00987        */
00988       basic_string&
00989       append(const basic_string& __str, size_type __pos, size_type __n);
00990 
00991       /**
00992        *  @brief  Append a C substring.
00993        *  @param __s  The C string to append.
00994        *  @param __n  The number of characters to append.
00995        *  @return  Reference to this string.
00996        */
00997       basic_string&
00998       append(const _CharT* __s, size_type __n);
00999 
01000       /**
01001        *  @brief  Append a C string.
01002        *  @param __s  The C string to append.
01003        *  @return  Reference to this string.
01004        */
01005       basic_string&
01006       append(const _CharT* __s)
01007       {
01008     __glibcxx_requires_string(__s);
01009     return this->append(__s, traits_type::length(__s));
01010       }
01011 
01012       /**
01013        *  @brief  Append multiple characters.
01014        *  @param __n  The number of characters to append.
01015        *  @param __c  The character to use.
01016        *  @return  Reference to this string.
01017        *
01018        *  Appends __n copies of __c to this string.
01019        */
01020       basic_string&
01021       append(size_type __n, _CharT __c);
01022 
01023 #if __cplusplus >= 201103L
01024       /**
01025        *  @brief  Append an initializer_list of characters.
01026        *  @param __l  The initializer_list of characters to append.
01027        *  @return  Reference to this string.
01028        */
01029       basic_string&
01030       append(initializer_list<_CharT> __l)
01031       { return this->append(__l.begin(), __l.size()); }
01032 #endif // C++11
01033 
01034       /**
01035        *  @brief  Append a range of characters.
01036        *  @param __first  Iterator referencing the first character to append.
01037        *  @param __last  Iterator marking the end of the range.
01038        *  @return  Reference to this string.
01039        *
01040        *  Appends characters in the range [__first,__last) to this string.
01041        */
01042       template<class _InputIterator>
01043         basic_string&
01044         append(_InputIterator __first, _InputIterator __last)
01045         { return this->replace(_M_iend(), _M_iend(), __first, __last); }
01046 
01047       /**
01048        *  @brief  Append a single character.
01049        *  @param __c  Character to append.
01050        */
01051       void
01052       push_back(_CharT __c)
01053       { 
01054     const size_type __len = 1 + this->size();
01055     if (__len > this->capacity() || _M_rep()->_M_is_shared())
01056       this->reserve(__len);
01057     traits_type::assign(_M_data()[this->size()], __c);
01058     _M_rep()->_M_set_length_and_sharable(__len);
01059       }
01060 
01061       /**
01062        *  @brief  Set value to contents of another string.
01063        *  @param  __str  Source string to use.
01064        *  @return  Reference to this string.
01065        */
01066       basic_string&
01067       assign(const basic_string& __str);
01068 
01069 #if __cplusplus >= 201103L
01070       /**
01071        *  @brief  Set value to contents of another string.
01072        *  @param  __str  Source string to use.
01073        *  @return  Reference to this string.
01074        *
01075        *  This function sets this string to the exact contents of @a __str.
01076        *  @a __str is a valid, but unspecified string.
01077        */
01078       basic_string&
01079       assign(basic_string&& __str)
01080       {
01081     this->swap(__str);
01082     return *this;
01083       }
01084 #endif // C++11
01085 
01086       /**
01087        *  @brief  Set value to a substring of a string.
01088        *  @param __str  The string to use.
01089        *  @param __pos  Index of the first character of str.
01090        *  @param __n  Number of characters to use.
01091        *  @return  Reference to this string.
01092        *  @throw  std::out_of_range if @a pos is not a valid index.
01093        *
01094        *  This function sets this string to the substring of @a __str
01095        *  consisting of @a __n characters at @a __pos.  If @a __n is
01096        *  is larger than the number of available characters in @a
01097        *  __str, the remainder of @a __str is used.
01098        */
01099       basic_string&
01100       assign(const basic_string& __str, size_type __pos, size_type __n)
01101       { return this->assign(__str._M_data()
01102                 + __str._M_check(__pos, "basic_string::assign"),
01103                 __str._M_limit(__pos, __n)); }
01104 
01105       /**
01106        *  @brief  Set value to a C substring.
01107        *  @param __s  The C string to use.
01108        *  @param __n  Number of characters to use.
01109        *  @return  Reference to this string.
01110        *
01111        *  This function sets the value of this string to the first @a __n
01112        *  characters of @a __s.  If @a __n is is larger than the number of
01113        *  available characters in @a __s, the remainder of @a __s is used.
01114        */
01115       basic_string&
01116       assign(const _CharT* __s, size_type __n);
01117 
01118       /**
01119        *  @brief  Set value to contents of a C string.
01120        *  @param __s  The C string to use.
01121        *  @return  Reference to this string.
01122        *
01123        *  This function sets the value of this string to the value of @a __s.
01124        *  The data is copied, so there is no dependence on @a __s once the
01125        *  function returns.
01126        */
01127       basic_string&
01128       assign(const _CharT* __s)
01129       {
01130     __glibcxx_requires_string(__s);
01131     return this->assign(__s, traits_type::length(__s));
01132       }
01133 
01134       /**
01135        *  @brief  Set value to multiple characters.
01136        *  @param __n  Length of the resulting string.
01137        *  @param __c  The character to use.
01138        *  @return  Reference to this string.
01139        *
01140        *  This function sets the value of this string to @a __n copies of
01141        *  character @a __c.
01142        */
01143       basic_string&
01144       assign(size_type __n, _CharT __c)
01145       { return _M_replace_aux(size_type(0), this->size(), __n, __c); }
01146 
01147       /**
01148        *  @brief  Set value to a range of characters.
01149        *  @param __first  Iterator referencing the first character to append.
01150        *  @param __last  Iterator marking the end of the range.
01151        *  @return  Reference to this string.
01152        *
01153        *  Sets value of string to characters in the range [__first,__last).
01154       */
01155       template<class _InputIterator>
01156         basic_string&
01157         assign(_InputIterator __first, _InputIterator __last)
01158         { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
01159 
01160 #if __cplusplus >= 201103L
01161       /**
01162        *  @brief  Set value to an initializer_list of characters.
01163        *  @param __l  The initializer_list of characters to assign.
01164        *  @return  Reference to this string.
01165        */
01166       basic_string&
01167       assign(initializer_list<_CharT> __l)
01168       { return this->assign(__l.begin(), __l.size()); }
01169 #endif // C++11
01170 
01171       /**
01172        *  @brief  Insert multiple characters.
01173        *  @param __p  Iterator referencing location in string to insert at.
01174        *  @param __n  Number of characters to insert
01175        *  @param __c  The character to insert.
01176        *  @throw  std::length_error  If new length exceeds @c max_size().
01177        *
01178        *  Inserts @a __n copies of character @a __c starting at the
01179        *  position referenced by iterator @a __p.  If adding
01180        *  characters causes the length to exceed max_size(),
01181        *  length_error is thrown.  The value of the string doesn't
01182        *  change if an error is thrown.
01183       */
01184       void
01185       insert(iterator __p, size_type __n, _CharT __c)
01186       { this->replace(__p, __p, __n, __c);  }
01187 
01188       /**
01189        *  @brief  Insert a range of characters.
01190        *  @param __p  Iterator referencing location in string to insert at.
01191        *  @param __beg  Start of range.
01192        *  @param __end  End of range.
01193        *  @throw  std::length_error  If new length exceeds @c max_size().
01194        *
01195        *  Inserts characters in range [__beg,__end).  If adding
01196        *  characters causes the length to exceed max_size(),
01197        *  length_error is thrown.  The value of the string doesn't
01198        *  change if an error is thrown.
01199       */
01200       template<class _InputIterator>
01201         void
01202         insert(iterator __p, _InputIterator __beg, _InputIterator __end)
01203         { this->replace(__p, __p, __beg, __end); }
01204 
01205 #if __cplusplus >= 201103L
01206       /**
01207        *  @brief  Insert an initializer_list of characters.
01208        *  @param __p  Iterator referencing location in string to insert at.
01209        *  @param __l  The initializer_list of characters to insert.
01210        *  @throw  std::length_error  If new length exceeds @c max_size().
01211        */
01212       void
01213       insert(iterator __p, initializer_list<_CharT> __l)
01214       {
01215     _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
01216     this->insert(__p - _M_ibegin(), __l.begin(), __l.size());
01217       }
01218 #endif // C++11
01219 
01220       /**
01221        *  @brief  Insert value of a string.
01222        *  @param __pos1  Iterator referencing location in string to insert at.
01223        *  @param __str  The string to insert.
01224        *  @return  Reference to this string.
01225        *  @throw  std::length_error  If new length exceeds @c max_size().
01226        *
01227        *  Inserts value of @a __str starting at @a __pos1.  If adding
01228        *  characters causes the length to exceed max_size(),
01229        *  length_error is thrown.  The value of the string doesn't
01230        *  change if an error is thrown.
01231       */
01232       basic_string&
01233       insert(size_type __pos1, const basic_string& __str)
01234       { return this->insert(__pos1, __str, size_type(0), __str.size()); }
01235 
01236       /**
01237        *  @brief  Insert a substring.
01238        *  @param __pos1  Iterator referencing location in string to insert at.
01239        *  @param __str  The string to insert.
01240        *  @param __pos2  Start of characters in str to insert.
01241        *  @param __n  Number of characters to insert.
01242        *  @return  Reference to this string.
01243        *  @throw  std::length_error  If new length exceeds @c max_size().
01244        *  @throw  std::out_of_range  If @a pos1 > size() or
01245        *  @a __pos2 > @a str.size().
01246        *
01247        *  Starting at @a pos1, insert @a __n character of @a __str
01248        *  beginning with @a __pos2.  If adding characters causes the
01249        *  length to exceed max_size(), length_error is thrown.  If @a
01250        *  __pos1 is beyond the end of this string or @a __pos2 is
01251        *  beyond the end of @a __str, out_of_range is thrown.  The
01252        *  value of the string doesn't change if an error is thrown.
01253       */
01254       basic_string&
01255       insert(size_type __pos1, const basic_string& __str,
01256          size_type __pos2, size_type __n)
01257       { return this->insert(__pos1, __str._M_data()
01258                 + __str._M_check(__pos2, "basic_string::insert"),
01259                 __str._M_limit(__pos2, __n)); }
01260 
01261       /**
01262        *  @brief  Insert a C substring.
01263        *  @param __pos  Iterator referencing location in string to insert at.
01264        *  @param __s  The C string to insert.
01265        *  @param __n  The number of characters to insert.
01266        *  @return  Reference to this string.
01267        *  @throw  std::length_error  If new length exceeds @c max_size().
01268        *  @throw  std::out_of_range  If @a __pos is beyond the end of this
01269        *  string.
01270        *
01271        *  Inserts the first @a __n characters of @a __s starting at @a
01272        *  __pos.  If adding characters causes the length to exceed
01273        *  max_size(), length_error is thrown.  If @a __pos is beyond
01274        *  end(), out_of_range is thrown.  The value of the string
01275        *  doesn't change if an error is thrown.
01276       */
01277       basic_string&
01278       insert(size_type __pos, const _CharT* __s, size_type __n);
01279 
01280       /**
01281        *  @brief  Insert a C string.
01282        *  @param __pos  Iterator referencing location in string to insert at.
01283        *  @param __s  The C string to insert.
01284        *  @return  Reference to this string.
01285        *  @throw  std::length_error  If new length exceeds @c max_size().
01286        *  @throw  std::out_of_range  If @a pos is beyond the end of this
01287        *  string.
01288        *
01289        *  Inserts the first @a n characters of @a __s starting at @a __pos.  If
01290        *  adding characters causes the length to exceed max_size(),
01291        *  length_error is thrown.  If @a __pos is beyond end(), out_of_range is
01292        *  thrown.  The value of the string doesn't change if an error is
01293        *  thrown.
01294       */
01295       basic_string&
01296       insert(size_type __pos, const _CharT* __s)
01297       {
01298     __glibcxx_requires_string(__s);
01299     return this->insert(__pos, __s, traits_type::length(__s));
01300       }
01301 
01302       /**
01303        *  @brief  Insert multiple characters.
01304        *  @param __pos  Index in string to insert at.
01305        *  @param __n  Number of characters to insert
01306        *  @param __c  The character to insert.
01307        *  @return  Reference to this string.
01308        *  @throw  std::length_error  If new length exceeds @c max_size().
01309        *  @throw  std::out_of_range  If @a __pos is beyond the end of this
01310        *  string.
01311        *
01312        *  Inserts @a __n copies of character @a __c starting at index
01313        *  @a __pos.  If adding characters causes the length to exceed
01314        *  max_size(), length_error is thrown.  If @a __pos > length(),
01315        *  out_of_range is thrown.  The value of the string doesn't
01316        *  change if an error is thrown.
01317       */
01318       basic_string&
01319       insert(size_type __pos, size_type __n, _CharT __c)
01320       { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
01321                   size_type(0), __n, __c); }
01322 
01323       /**
01324        *  @brief  Insert one character.
01325        *  @param __p  Iterator referencing position in string to insert at.
01326        *  @param __c  The character to insert.
01327        *  @return  Iterator referencing newly inserted char.
01328        *  @throw  std::length_error  If new length exceeds @c max_size().
01329        *
01330        *  Inserts character @a __c at position referenced by @a __p.
01331        *  If adding character causes the length to exceed max_size(),
01332        *  length_error is thrown.  If @a __p is beyond end of string,
01333        *  out_of_range is thrown.  The value of the string doesn't
01334        *  change if an error is thrown.
01335       */
01336       iterator
01337       insert(iterator __p, _CharT __c)
01338       {
01339     _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
01340     const size_type __pos = __p - _M_ibegin();
01341     _M_replace_aux(__pos, size_type(0), size_type(1), __c);
01342     _M_rep()->_M_set_leaked();
01343     return iterator(_M_data() + __pos);
01344       }
01345 
01346       /**
01347        *  @brief  Remove characters.
01348        *  @param __pos  Index of first character to remove (default 0).
01349        *  @param __n  Number of characters to remove (default remainder).
01350        *  @return  Reference to this string.
01351        *  @throw  std::out_of_range  If @a pos is beyond the end of this
01352        *  string.
01353        *
01354        *  Removes @a __n characters from this string starting at @a
01355        *  __pos.  The length of the string is reduced by @a __n.  If
01356        *  there are < @a __n characters to remove, the remainder of
01357        *  the string is truncated.  If @a __p is beyond end of string,
01358        *  out_of_range is thrown.  The value of the string doesn't
01359        *  change if an error is thrown.
01360       */
01361       basic_string&
01362       erase(size_type __pos = 0, size_type __n = npos)
01363       { 
01364     _M_mutate(_M_check(__pos, "basic_string::erase"),
01365           _M_limit(__pos, __n), size_type(0));
01366     return *this;
01367       }
01368 
01369       /**
01370        *  @brief  Remove one character.
01371        *  @param __position  Iterator referencing the character to remove.
01372        *  @return  iterator referencing same location after removal.
01373        *
01374        *  Removes the character at @a __position from this string. The value
01375        *  of the string doesn't change if an error is thrown.
01376       */
01377       iterator
01378       erase(iterator __position)
01379       {
01380     _GLIBCXX_DEBUG_PEDASSERT(__position >= _M_ibegin()
01381                  && __position < _M_iend());
01382     const size_type __pos = __position - _M_ibegin();
01383     _M_mutate(__pos, size_type(1), size_type(0));
01384     _M_rep()->_M_set_leaked();
01385     return iterator(_M_data() + __pos);
01386       }
01387 
01388       /**
01389        *  @brief  Remove a range of characters.
01390        *  @param __first  Iterator referencing the first character to remove.
01391        *  @param __last  Iterator referencing the end of the range.
01392        *  @return  Iterator referencing location of first after removal.
01393        *
01394        *  Removes the characters in the range [first,last) from this string.
01395        *  The value of the string doesn't change if an error is thrown.
01396       */
01397       iterator
01398       erase(iterator __first, iterator __last);
01399  
01400 #if __cplusplus >= 201103L
01401       /**
01402        *  @brief  Remove the last character.
01403        *
01404        *  The string must be non-empty.
01405        */
01406       void
01407       pop_back()
01408       { erase(size()-1, 1); }
01409 #endif // C++11
01410 
01411       /**
01412        *  @brief  Replace characters with value from another string.
01413        *  @param __pos  Index of first character to replace.
01414        *  @param __n  Number of characters to be replaced.
01415        *  @param __str  String to insert.
01416        *  @return  Reference to this string.
01417        *  @throw  std::out_of_range  If @a pos is beyond the end of this
01418        *  string.
01419        *  @throw  std::length_error  If new length exceeds @c max_size().
01420        *
01421        *  Removes the characters in the range [__pos,__pos+__n) from
01422        *  this string.  In place, the value of @a __str is inserted.
01423        *  If @a __pos is beyond end of string, out_of_range is thrown.
01424        *  If the length of the result exceeds max_size(), length_error
01425        *  is thrown.  The value of the string doesn't change if an
01426        *  error is thrown.
01427       */
01428       basic_string&
01429       replace(size_type __pos, size_type __n, const basic_string& __str)
01430       { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
01431 
01432       /**
01433        *  @brief  Replace characters with value from another string.
01434        *  @param __pos1  Index of first character to replace.
01435        *  @param __n1  Number of characters to be replaced.
01436        *  @param __str  String to insert.
01437        *  @param __pos2  Index of first character of str to use.
01438        *  @param __n2  Number of characters from str to use.
01439        *  @return  Reference to this string.
01440        *  @throw  std::out_of_range  If @a __pos1 > size() or @a __pos2 >
01441        *  __str.size().
01442        *  @throw  std::length_error  If new length exceeds @c max_size().
01443        *
01444        *  Removes the characters in the range [__pos1,__pos1 + n) from this
01445        *  string.  In place, the value of @a __str is inserted.  If @a __pos is
01446        *  beyond end of string, out_of_range is thrown.  If the length of the
01447        *  result exceeds max_size(), length_error is thrown.  The value of the
01448        *  string doesn't change if an error is thrown.
01449       */
01450       basic_string&
01451       replace(size_type __pos1, size_type __n1, const basic_string& __str,
01452           size_type __pos2, size_type __n2)
01453       { return this->replace(__pos1, __n1, __str._M_data()
01454                  + __str._M_check(__pos2, "basic_string::replace"),
01455                  __str._M_limit(__pos2, __n2)); }
01456 
01457       /**
01458        *  @brief  Replace characters with value of a C substring.
01459        *  @param __pos  Index of first character to replace.
01460        *  @param __n1  Number of characters to be replaced.
01461        *  @param __s  C string to insert.
01462        *  @param __n2  Number of characters from @a s to use.
01463        *  @return  Reference to this string.
01464        *  @throw  std::out_of_range  If @a pos1 > size().
01465        *  @throw  std::length_error  If new length exceeds @c max_size().
01466        *
01467        *  Removes the characters in the range [__pos,__pos + __n1)
01468        *  from this string.  In place, the first @a __n2 characters of
01469        *  @a __s are inserted, or all of @a __s if @a __n2 is too large.  If
01470        *  @a __pos is beyond end of string, out_of_range is thrown.  If
01471        *  the length of result exceeds max_size(), length_error is
01472        *  thrown.  The value of the string doesn't change if an error
01473        *  is thrown.
01474       */
01475       basic_string&
01476       replace(size_type __pos, size_type __n1, const _CharT* __s,
01477           size_type __n2);
01478 
01479       /**
01480        *  @brief  Replace characters with value of a C string.
01481        *  @param __pos  Index of first character to replace.
01482        *  @param __n1  Number of characters to be replaced.
01483        *  @param __s  C string to insert.
01484        *  @return  Reference to this string.
01485        *  @throw  std::out_of_range  If @a pos > size().
01486        *  @throw  std::length_error  If new length exceeds @c max_size().
01487        *
01488        *  Removes the characters in the range [__pos,__pos + __n1)
01489        *  from this string.  In place, the characters of @a __s are
01490        *  inserted.  If @a __pos is beyond end of string, out_of_range
01491        *  is thrown.  If the length of result exceeds max_size(),
01492        *  length_error is thrown.  The value of the string doesn't
01493        *  change if an error is thrown.
01494       */
01495       basic_string&
01496       replace(size_type __pos, size_type __n1, const _CharT* __s)
01497       {
01498     __glibcxx_requires_string(__s);
01499     return this->replace(__pos, __n1, __s, traits_type::length(__s));
01500       }
01501 
01502       /**
01503        *  @brief  Replace characters with multiple characters.
01504        *  @param __pos  Index of first character to replace.
01505        *  @param __n1  Number of characters to be replaced.
01506        *  @param __n2  Number of characters to insert.
01507        *  @param __c  Character to insert.
01508        *  @return  Reference to this string.
01509        *  @throw  std::out_of_range  If @a __pos > size().
01510        *  @throw  std::length_error  If new length exceeds @c max_size().
01511        *
01512        *  Removes the characters in the range [pos,pos + n1) from this
01513        *  string.  In place, @a __n2 copies of @a __c are inserted.
01514        *  If @a __pos is beyond end of string, out_of_range is thrown.
01515        *  If the length of result exceeds max_size(), length_error is
01516        *  thrown.  The value of the string doesn't change if an error
01517        *  is thrown.
01518       */
01519       basic_string&
01520       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
01521       { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
01522                   _M_limit(__pos, __n1), __n2, __c); }
01523 
01524       /**
01525        *  @brief  Replace range of characters with string.
01526        *  @param __i1  Iterator referencing start of range to replace.
01527        *  @param __i2  Iterator referencing end of range to replace.
01528        *  @param __str  String value to insert.
01529        *  @return  Reference to this string.
01530        *  @throw  std::length_error  If new length exceeds @c max_size().
01531        *
01532        *  Removes the characters in the range [__i1,__i2).  In place,
01533        *  the value of @a __str is inserted.  If the length of result
01534        *  exceeds max_size(), length_error is thrown.  The value of
01535        *  the string doesn't change if an error is thrown.
01536       */
01537       basic_string&
01538       replace(iterator __i1, iterator __i2, const basic_string& __str)
01539       { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
01540 
01541       /**
01542        *  @brief  Replace range of characters with C substring.
01543        *  @param __i1  Iterator referencing start of range to replace.
01544        *  @param __i2  Iterator referencing end of range to replace.
01545        *  @param __s  C string value to insert.
01546        *  @param __n  Number of characters from s to insert.
01547        *  @return  Reference to this string.
01548        *  @throw  std::length_error  If new length exceeds @c max_size().
01549        *
01550        *  Removes the characters in the range [__i1,__i2).  In place,
01551        *  the first @a __n characters of @a __s are inserted.  If the
01552        *  length of result exceeds max_size(), length_error is thrown.
01553        *  The value of the string doesn't change if an error is
01554        *  thrown.
01555       */
01556       basic_string&
01557       replace(iterator __i1, iterator __i2, const _CharT* __s, size_type __n)
01558       {
01559     _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
01560                  && __i2 <= _M_iend());
01561     return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n);
01562       }
01563 
01564       /**
01565        *  @brief  Replace range of characters with C string.
01566        *  @param __i1  Iterator referencing start of range to replace.
01567        *  @param __i2  Iterator referencing end of range to replace.
01568        *  @param __s  C string value to insert.
01569        *  @return  Reference to this string.
01570        *  @throw  std::length_error  If new length exceeds @c max_size().
01571        *
01572        *  Removes the characters in the range [__i1,__i2).  In place,
01573        *  the characters of @a __s are inserted.  If the length of
01574        *  result exceeds max_size(), length_error is thrown.  The
01575        *  value of the string doesn't change if an error is thrown.
01576       */
01577       basic_string&
01578       replace(iterator __i1, iterator __i2, const _CharT* __s)
01579       {
01580     __glibcxx_requires_string(__s);
01581     return this->replace(__i1, __i2, __s, traits_type::length(__s));
01582       }
01583 
01584       /**
01585        *  @brief  Replace range of characters with multiple characters
01586        *  @param __i1  Iterator referencing start of range to replace.
01587        *  @param __i2  Iterator referencing end of range to replace.
01588        *  @param __n  Number of characters to insert.
01589        *  @param __c  Character to insert.
01590        *  @return  Reference to this string.
01591        *  @throw  std::length_error  If new length exceeds @c max_size().
01592        *
01593        *  Removes the characters in the range [__i1,__i2).  In place,
01594        *  @a __n copies of @a __c are inserted.  If the length of
01595        *  result exceeds max_size(), length_error is thrown.  The
01596        *  value of the string doesn't change if an error is thrown.
01597       */
01598       basic_string&
01599       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
01600       {
01601     _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
01602                  && __i2 <= _M_iend());
01603     return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __c);
01604       }
01605 
01606       /**
01607        *  @brief  Replace range of characters with range.
01608        *  @param __i1  Iterator referencing start of range to replace.
01609        *  @param __i2  Iterator referencing end of range to replace.
01610        *  @param __k1  Iterator referencing start of range to insert.
01611        *  @param __k2  Iterator referencing end of range to insert.
01612        *  @return  Reference to this string.
01613        *  @throw  std::length_error  If new length exceeds @c max_size().
01614        *
01615        *  Removes the characters in the range [__i1,__i2).  In place,
01616        *  characters in the range [__k1,__k2) are inserted.  If the
01617        *  length of result exceeds max_size(), length_error is thrown.
01618        *  The value of the string doesn't change if an error is
01619        *  thrown.
01620       */
01621       template<class _InputIterator>
01622         basic_string&
01623         replace(iterator __i1, iterator __i2,
01624         _InputIterator __k1, _InputIterator __k2)
01625         {
01626       _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
01627                    && __i2 <= _M_iend());
01628       __glibcxx_requires_valid_range(__k1, __k2);
01629       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
01630       return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
01631     }
01632 
01633       // Specializations for the common case of pointer and iterator:
01634       // useful to avoid the overhead of temporary buffering in _M_replace.
01635       basic_string&
01636       replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
01637       {
01638     _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
01639                  && __i2 <= _M_iend());
01640     __glibcxx_requires_valid_range(__k1, __k2);
01641     return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
01642                  __k1, __k2 - __k1);
01643       }
01644 
01645       basic_string&
01646       replace(iterator __i1, iterator __i2,
01647           const _CharT* __k1, const _CharT* __k2)
01648       {
01649     _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
01650                  && __i2 <= _M_iend());
01651     __glibcxx_requires_valid_range(__k1, __k2);
01652     return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
01653                  __k1, __k2 - __k1);
01654       }
01655 
01656       basic_string&
01657       replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
01658       {
01659     _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
01660                  && __i2 <= _M_iend());
01661     __glibcxx_requires_valid_range(__k1, __k2);
01662     return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
01663                  __k1.base(), __k2 - __k1);
01664       }
01665 
01666       basic_string&
01667       replace(iterator __i1, iterator __i2,
01668           const_iterator __k1, const_iterator __k2)
01669       {
01670     _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
01671                  && __i2 <= _M_iend());
01672     __glibcxx_requires_valid_range(__k1, __k2);
01673     return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
01674                  __k1.base(), __k2 - __k1);
01675       }
01676       
01677 #if __cplusplus >= 201103L
01678       /**
01679        *  @brief  Replace range of characters with initializer_list.
01680        *  @param __i1  Iterator referencing start of range to replace.
01681        *  @param __i2  Iterator referencing end of range to replace.
01682        *  @param __l  The initializer_list of characters to insert.
01683        *  @return  Reference to this string.
01684        *  @throw  std::length_error  If new length exceeds @c max_size().
01685        *
01686        *  Removes the characters in the range [__i1,__i2).  In place,
01687        *  characters in the range [__k1,__k2) are inserted.  If the
01688        *  length of result exceeds max_size(), length_error is thrown.
01689        *  The value of the string doesn't change if an error is
01690        *  thrown.
01691       */
01692       basic_string& replace(iterator __i1, iterator __i2,
01693                 initializer_list<_CharT> __l)
01694       { return this->replace(__i1, __i2, __l.begin(), __l.end()); }
01695 #endif // C++11
01696 
01697     private:
01698       template<class _Integer>
01699     basic_string&
01700     _M_replace_dispatch(iterator __i1, iterator __i2, _Integer __n,
01701                 _Integer __val, __true_type)
01702         { return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __val); }
01703 
01704       template<class _InputIterator>
01705     basic_string&
01706     _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
01707                 _InputIterator __k2, __false_type);
01708 
01709       basic_string&
01710       _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
01711              _CharT __c);
01712 
01713       basic_string&
01714       _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
01715               size_type __n2);
01716 
01717       // _S_construct_aux is used to implement the 21.3.1 para 15 which
01718       // requires special behaviour if _InIter is an integral type
01719       template<class _InIterator>
01720         static _CharT*
01721         _S_construct_aux(_InIterator __beg, _InIterator __end,
01722              const _Alloc& __a, __false_type)
01723     {
01724           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
01725           return _S_construct(__beg, __end, __a, _Tag());
01726     }
01727 
01728       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01729       // 438. Ambiguity in the "do the right thing" clause
01730       template<class _Integer>
01731         static _CharT*
01732         _S_construct_aux(_Integer __beg, _Integer __end,
01733              const _Alloc& __a, __true_type)
01734         { return _S_construct_aux_2(static_cast<size_type>(__beg),
01735                     __end, __a); }
01736 
01737       static _CharT*
01738       _S_construct_aux_2(size_type __req, _CharT __c, const _Alloc& __a)
01739       { return _S_construct(__req, __c, __a); }
01740 
01741       template<class _InIterator>
01742         static _CharT*
01743         _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
01744     {
01745       typedef typename std::__is_integer<_InIterator>::__type _Integral;
01746       return _S_construct_aux(__beg, __end, __a, _Integral());
01747         }
01748 
01749       // For Input Iterators, used in istreambuf_iterators, etc.
01750       template<class _InIterator>
01751         static _CharT*
01752          _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
01753               input_iterator_tag);
01754 
01755       // For forward_iterators up to random_access_iterators, used for
01756       // string::iterator, _CharT*, etc.
01757       template<class _FwdIterator>
01758         static _CharT*
01759         _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
01760              forward_iterator_tag);
01761 
01762       static _CharT*
01763       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
01764 
01765     public:
01766 
01767       /**
01768        *  @brief  Copy substring into C string.
01769        *  @param __s  C string to copy value into.
01770        *  @param __n  Number of characters to copy.
01771        *  @param __pos  Index of first character to copy.
01772        *  @return  Number of characters actually copied
01773        *  @throw  std::out_of_range  If __pos > size().
01774        *
01775        *  Copies up to @a __n characters starting at @a __pos into the
01776        *  C string @a __s.  If @a __pos is %greater than size(),
01777        *  out_of_range is thrown.
01778       */
01779       size_type
01780       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
01781 
01782       /**
01783        *  @brief  Swap contents with another string.
01784        *  @param __s  String to swap with.
01785        *
01786        *  Exchanges the contents of this string with that of @a __s in constant
01787        *  time.
01788       */
01789       void
01790       swap(basic_string& __s);
01791 
01792       // String operations:
01793       /**
01794        *  @brief  Return const pointer to null-terminated contents.
01795        *
01796        *  This is a handle to internal data.  Do not modify or dire things may
01797        *  happen.
01798       */
01799       const _CharT*
01800       c_str() const _GLIBCXX_NOEXCEPT
01801       { return _M_data(); }
01802 
01803       /**
01804        *  @brief  Return const pointer to contents.
01805        *
01806        *  This is a handle to internal data.  Do not modify or dire things may
01807        *  happen.
01808       */
01809       const _CharT*
01810       data() const _GLIBCXX_NOEXCEPT
01811       { return _M_data(); }
01812 
01813       /**
01814        *  @brief  Return copy of allocator used to construct this string.
01815       */
01816       allocator_type
01817       get_allocator() const _GLIBCXX_NOEXCEPT
01818       { return _M_dataplus; }
01819 
01820       /**
01821        *  @brief  Find position of a C substring.
01822        *  @param __s  C string to locate.
01823        *  @param __pos  Index of character to search from.
01824        *  @param __n  Number of characters from @a s to search for.
01825        *  @return  Index of start of first occurrence.
01826        *
01827        *  Starting from @a __pos, searches forward for the first @a
01828        *  __n characters in @a __s within this string.  If found,
01829        *  returns the index where it begins.  If not found, returns
01830        *  npos.
01831       */
01832       size_type
01833       find(const _CharT* __s, size_type __pos, size_type __n) const;
01834 
01835       /**
01836        *  @brief  Find position of a string.
01837        *  @param __str  String to locate.
01838        *  @param __pos  Index of character to search from (default 0).
01839        *  @return  Index of start of first occurrence.
01840        *
01841        *  Starting from @a __pos, searches forward for value of @a __str within
01842        *  this string.  If found, returns the index where it begins.  If not
01843        *  found, returns npos.
01844       */
01845       size_type
01846       find(const basic_string& __str, size_type __pos = 0) const
01847     _GLIBCXX_NOEXCEPT
01848       { return this->find(__str.data(), __pos, __str.size()); }
01849 
01850       /**
01851        *  @brief  Find position of a C string.
01852        *  @param __s  C string to locate.
01853        *  @param __pos  Index of character to search from (default 0).
01854        *  @return  Index of start of first occurrence.
01855        *
01856        *  Starting from @a __pos, searches forward for the value of @a
01857        *  __s within this string.  If found, returns the index where
01858        *  it begins.  If not found, returns npos.
01859       */
01860       size_type
01861       find(const _CharT* __s, size_type __pos = 0) const
01862       {
01863     __glibcxx_requires_string(__s);
01864     return this->find(__s, __pos, traits_type::length(__s));
01865       }
01866 
01867       /**
01868        *  @brief  Find position of a character.
01869        *  @param __c  Character to locate.
01870        *  @param __pos  Index of character to search from (default 0).
01871        *  @return  Index of first occurrence.
01872        *
01873        *  Starting from @a __pos, searches forward for @a __c within
01874        *  this string.  If found, returns the index where it was
01875        *  found.  If not found, returns npos.
01876       */
01877       size_type
01878       find(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT;
01879 
01880       /**
01881        *  @brief  Find last position of a string.
01882        *  @param __str  String to locate.
01883        *  @param __pos  Index of character to search back from (default end).
01884        *  @return  Index of start of last occurrence.
01885        *
01886        *  Starting from @a __pos, searches backward for value of @a
01887        *  __str within this string.  If found, returns the index where
01888        *  it begins.  If not found, returns npos.
01889       */
01890       size_type
01891       rfind(const basic_string& __str, size_type __pos = npos) const
01892     _GLIBCXX_NOEXCEPT
01893       { return this->rfind(__str.data(), __pos, __str.size()); }
01894 
01895       /**
01896        *  @brief  Find last position of a C substring.
01897        *  @param __s  C string to locate.
01898        *  @param __pos  Index of character to search back from.
01899        *  @param __n  Number of characters from s to search for.
01900        *  @return  Index of start of last occurrence.
01901        *
01902        *  Starting from @a __pos, searches backward for the first @a
01903        *  __n characters in @a __s within this string.  If found,
01904        *  returns the index where it begins.  If not found, returns
01905        *  npos.
01906       */
01907       size_type
01908       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
01909 
01910       /**
01911        *  @brief  Find last position of a C string.
01912        *  @param __s  C string to locate.
01913        *  @param __pos  Index of character to start search at (default end).
01914        *  @return  Index of start of  last occurrence.
01915        *
01916        *  Starting from @a __pos, searches backward for the value of
01917        *  @a __s within this string.  If found, returns the index
01918        *  where it begins.  If not found, returns npos.
01919       */
01920       size_type
01921       rfind(const _CharT* __s, size_type __pos = npos) const
01922       {
01923     __glibcxx_requires_string(__s);
01924     return this->rfind(__s, __pos, traits_type::length(__s));
01925       }
01926 
01927       /**
01928        *  @brief  Find last position of a character.
01929        *  @param __c  Character to locate.
01930        *  @param __pos  Index of character to search back from (default end).
01931        *  @return  Index of last occurrence.
01932        *
01933        *  Starting from @a __pos, searches backward for @a __c within
01934        *  this string.  If found, returns the index where it was
01935        *  found.  If not found, returns npos.
01936       */
01937       size_type
01938       rfind(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT;
01939 
01940       /**
01941        *  @brief  Find position of a character of string.
01942        *  @param __str  String containing characters to locate.
01943        *  @param __pos  Index of character to search from (default 0).
01944        *  @return  Index of first occurrence.
01945        *
01946        *  Starting from @a __pos, searches forward for one of the
01947        *  characters of @a __str within this string.  If found,
01948        *  returns the index where it was found.  If not found, returns
01949        *  npos.
01950       */
01951       size_type
01952       find_first_of(const basic_string& __str, size_type __pos = 0) const
01953     _GLIBCXX_NOEXCEPT
01954       { return this->find_first_of(__str.data(), __pos, __str.size()); }
01955 
01956       /**
01957        *  @brief  Find position of a character of C substring.
01958        *  @param __s  String containing characters to locate.
01959        *  @param __pos  Index of character to search from.
01960        *  @param __n  Number of characters from s to search for.
01961        *  @return  Index of first occurrence.
01962        *
01963        *  Starting from @a __pos, searches forward for one of the
01964        *  first @a __n characters of @a __s within this string.  If
01965        *  found, returns the index where it was found.  If not found,
01966        *  returns npos.
01967       */
01968       size_type
01969       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
01970 
01971       /**
01972        *  @brief  Find position of a character of C string.
01973        *  @param __s  String containing characters to locate.
01974        *  @param __pos  Index of character to search from (default 0).
01975        *  @return  Index of first occurrence.
01976        *
01977        *  Starting from @a __pos, searches forward for one of the
01978        *  characters of @a __s within this string.  If found, returns
01979        *  the index where it was found.  If not found, returns npos.
01980       */
01981       size_type
01982       find_first_of(const _CharT* __s, size_type __pos = 0) const
01983       {
01984     __glibcxx_requires_string(__s);
01985     return this->find_first_of(__s, __pos, traits_type::length(__s));
01986       }
01987 
01988       /**
01989        *  @brief  Find position of a character.
01990        *  @param __c  Character to locate.
01991        *  @param __pos  Index of character to search from (default 0).
01992        *  @return  Index of first occurrence.
01993        *
01994        *  Starting from @a __pos, searches forward for the character
01995        *  @a __c within this string.  If found, returns the index
01996        *  where it was found.  If not found, returns npos.
01997        *
01998        *  Note: equivalent to find(__c, __pos).
01999       */
02000       size_type
02001       find_first_of(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT
02002       { return this->find(__c, __pos); }
02003 
02004       /**
02005        *  @brief  Find last position of a character of string.
02006        *  @param __str  String containing characters to locate.
02007        *  @param __pos  Index of character to search back from (default end).
02008        *  @return  Index of last occurrence.
02009        *
02010        *  Starting from @a __pos, searches backward for one of the
02011        *  characters of @a __str within this string.  If found,
02012        *  returns the index where it was found.  If not found, returns
02013        *  npos.
02014       */
02015       size_type
02016       find_last_of(const basic_string& __str, size_type __pos = npos) const
02017     _GLIBCXX_NOEXCEPT
02018       { return this->find_last_of(__str.data(), __pos, __str.size()); }
02019 
02020       /**
02021        *  @brief  Find last position of a character of C substring.
02022        *  @param __s  C string containing characters to locate.
02023        *  @param __pos  Index of character to search back from.
02024        *  @param __n  Number of characters from s to search for.
02025        *  @return  Index of last occurrence.
02026        *
02027        *  Starting from @a __pos, searches backward for one of the
02028        *  first @a __n characters of @a __s within this string.  If
02029        *  found, returns the index where it was found.  If not found,
02030        *  returns npos.
02031       */
02032       size_type
02033       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
02034 
02035       /**
02036        *  @brief  Find last position of a character of C string.
02037        *  @param __s  C string containing characters to locate.
02038        *  @param __pos  Index of character to search back from (default end).
02039        *  @return  Index of last occurrence.
02040        *
02041        *  Starting from @a __pos, searches backward for one of the
02042        *  characters of @a __s within this string.  If found, returns
02043        *  the index where it was found.  If not found, returns npos.
02044       */
02045       size_type
02046       find_last_of(const _CharT* __s, size_type __pos = npos) const
02047       {
02048     __glibcxx_requires_string(__s);
02049     return this->find_last_of(__s, __pos, traits_type::length(__s));
02050       }
02051 
02052       /**
02053        *  @brief  Find last position of a character.
02054        *  @param __c  Character to locate.
02055        *  @param __pos  Index of character to search back from (default end).
02056        *  @return  Index of last occurrence.
02057        *
02058        *  Starting from @a __pos, searches backward for @a __c within
02059        *  this string.  If found, returns the index where it was
02060        *  found.  If not found, returns npos.
02061        *
02062        *  Note: equivalent to rfind(__c, __pos).
02063       */
02064       size_type
02065       find_last_of(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT
02066       { return this->rfind(__c, __pos); }
02067 
02068       /**
02069        *  @brief  Find position of a character not in string.
02070        *  @param __str  String containing characters to avoid.
02071        *  @param __pos  Index of character to search from (default 0).
02072        *  @return  Index of first occurrence.
02073        *
02074        *  Starting from @a __pos, searches forward for a character not contained
02075        *  in @a __str within this string.  If found, returns the index where it
02076        *  was found.  If not found, returns npos.
02077       */
02078       size_type
02079       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
02080     _GLIBCXX_NOEXCEPT
02081       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
02082 
02083       /**
02084        *  @brief  Find position of a character not in C substring.
02085        *  @param __s  C string containing characters to avoid.
02086        *  @param __pos  Index of character to search from.
02087        *  @param __n  Number of characters from __s to consider.
02088        *  @return  Index of first occurrence.
02089        *
02090        *  Starting from @a __pos, searches forward for a character not
02091        *  contained in the first @a __n characters of @a __s within
02092        *  this string.  If found, returns the index where it was
02093        *  found.  If not found, returns npos.
02094       */
02095       size_type
02096       find_first_not_of(const _CharT* __s, size_type __pos,
02097             size_type __n) const;
02098 
02099       /**
02100        *  @brief  Find position of a character not in C string.
02101        *  @param __s  C string containing characters to avoid.
02102        *  @param __pos  Index of character to search from (default 0).
02103        *  @return  Index of first occurrence.
02104        *
02105        *  Starting from @a __pos, searches forward for a character not
02106        *  contained in @a __s within this string.  If found, returns
02107        *  the index where it was found.  If not found, returns npos.
02108       */
02109       size_type
02110       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
02111       {
02112     __glibcxx_requires_string(__s);
02113     return this->find_first_not_of(__s, __pos, traits_type::length(__s));
02114       }
02115 
02116       /**
02117        *  @brief  Find position of a different character.
02118        *  @param __c  Character to avoid.
02119        *  @param __pos  Index of character to search from (default 0).
02120        *  @return  Index of first occurrence.
02121        *
02122        *  Starting from @a __pos, searches forward for a character
02123        *  other than @a __c within this string.  If found, returns the
02124        *  index where it was found.  If not found, returns npos.
02125       */
02126       size_type
02127       find_first_not_of(_CharT __c, size_type __pos = 0) const
02128     _GLIBCXX_NOEXCEPT;
02129 
02130       /**
02131        *  @brief  Find last position of a character not in string.
02132        *  @param __str  String containing characters to avoid.
02133        *  @param __pos  Index of character to search back from (default end).
02134        *  @return  Index of last occurrence.
02135        *
02136        *  Starting from @a __pos, searches backward for a character
02137        *  not contained in @a __str within this string.  If found,
02138        *  returns the index where it was found.  If not found, returns
02139        *  npos.
02140       */
02141       size_type
02142       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
02143     _GLIBCXX_NOEXCEPT
02144       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
02145 
02146       /**
02147        *  @brief  Find last position of a character not in C substring.
02148        *  @param __s  C string containing characters to avoid.
02149        *  @param __pos  Index of character to search back from.
02150        *  @param __n  Number of characters from s to consider.
02151        *  @return  Index of last occurrence.
02152        *
02153        *  Starting from @a __pos, searches backward for a character not
02154        *  contained in the first @a __n characters of @a __s within this string.
02155        *  If found, returns the index where it was found.  If not found,
02156        *  returns npos.
02157       */
02158       size_type
02159       find_last_not_of(const _CharT* __s, size_type __pos,
02160                size_type __n) const;
02161       /**
02162        *  @brief  Find last position of a character not in C string.
02163        *  @param __s  C string containing characters to avoid.
02164        *  @param __pos  Index of character to search back from (default end).
02165        *  @return  Index of last occurrence.
02166        *
02167        *  Starting from @a __pos, searches backward for a character
02168        *  not contained in @a __s within this string.  If found,
02169        *  returns the index where it was found.  If not found, returns
02170        *  npos.
02171       */
02172       size_type
02173       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
02174       {
02175     __glibcxx_requires_string(__s);
02176     return this->find_last_not_of(__s, __pos, traits_type::length(__s));
02177       }
02178 
02179       /**
02180        *  @brief  Find last position of a different character.
02181        *  @param __c  Character to avoid.
02182        *  @param __pos  Index of character to search back from (default end).
02183        *  @return  Index of last occurrence.
02184        *
02185        *  Starting from @a __pos, searches backward for a character other than
02186        *  @a __c within this string.  If found, returns the index where it was
02187        *  found.  If not found, returns npos.
02188       */
02189       size_type
02190       find_last_not_of(_CharT __c, size_type __pos = npos) const
02191     _GLIBCXX_NOEXCEPT;
02192 
02193       /**
02194        *  @brief  Get a substring.
02195        *  @param __pos  Index of first character (default 0).
02196        *  @param __n  Number of characters in substring (default remainder).
02197        *  @return  The new string.
02198        *  @throw  std::out_of_range  If __pos > size().
02199        *
02200        *  Construct and return a new string using the @a __n
02201        *  characters starting at @a __pos.  If the string is too
02202        *  short, use the remainder of the characters.  If @a __pos is
02203        *  beyond the end of the string, out_of_range is thrown.
02204       */
02205       basic_string
02206       substr(size_type __pos = 0, size_type __n = npos) const
02207       { return basic_string(*this,
02208                 _M_check(__pos, "basic_string::substr"), __n); }
02209 
02210       /**
02211        *  @brief  Compare to a string.
02212        *  @param __str  String to compare against.
02213        *  @return  Integer < 0, 0, or > 0.
02214        *
02215        *  Returns an integer < 0 if this string is ordered before @a
02216        *  __str, 0 if their values are equivalent, or > 0 if this
02217        *  string is ordered after @a __str.  Determines the effective
02218        *  length rlen of the strings to compare as the smallest of
02219        *  size() and str.size().  The function then compares the two
02220        *  strings by calling traits::compare(data(), str.data(),rlen).
02221        *  If the result of the comparison is nonzero returns it,
02222        *  otherwise the shorter one is ordered first.
02223       */
02224       int
02225       compare(const basic_string& __str) const
02226       {
02227     const size_type __size = this->size();
02228     const size_type __osize = __str.size();
02229     const size_type __len = std::min(__size, __osize);
02230 
02231     int __r = traits_type::compare(_M_data(), __str.data(), __len);
02232     if (!__r)
02233       __r = _S_compare(__size, __osize);
02234     return __r;
02235       }
02236 
02237       /**
02238        *  @brief  Compare substring to a string.
02239        *  @param __pos  Index of first character of substring.
02240        *  @param __n  Number of characters in substring.
02241        *  @param __str  String to compare against.
02242        *  @return  Integer < 0, 0, or > 0.
02243        *
02244        *  Form the substring of this string from the @a __n characters
02245        *  starting at @a __pos.  Returns an integer < 0 if the
02246        *  substring is ordered before @a __str, 0 if their values are
02247        *  equivalent, or > 0 if the substring is ordered after @a
02248        *  __str.  Determines the effective length rlen of the strings
02249        *  to compare as the smallest of the length of the substring
02250        *  and @a __str.size().  The function then compares the two
02251        *  strings by calling
02252        *  traits::compare(substring.data(),str.data(),rlen).  If the
02253        *  result of the comparison is nonzero returns it, otherwise
02254        *  the shorter one is ordered first.
02255       */
02256       int
02257       compare(size_type __pos, size_type __n, const basic_string& __str) const;
02258 
02259       /**
02260        *  @brief  Compare substring to a substring.
02261        *  @param __pos1  Index of first character of substring.
02262        *  @param __n1  Number of characters in substring.
02263        *  @param __str  String to compare against.
02264        *  @param __pos2  Index of first character of substring of str.
02265        *  @param __n2  Number of characters in substring of str.
02266        *  @return  Integer < 0, 0, or > 0.
02267        *
02268        *  Form the substring of this string from the @a __n1
02269        *  characters starting at @a __pos1.  Form the substring of @a
02270        *  __str from the @a __n2 characters starting at @a __pos2.
02271        *  Returns an integer < 0 if this substring is ordered before
02272        *  the substring of @a __str, 0 if their values are equivalent,
02273        *  or > 0 if this substring is ordered after the substring of
02274        *  @a __str.  Determines the effective length rlen of the
02275        *  strings to compare as the smallest of the lengths of the
02276        *  substrings.  The function then compares the two strings by
02277        *  calling
02278        *  traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
02279        *  If the result of the comparison is nonzero returns it,
02280        *  otherwise the shorter one is ordered first.
02281       */
02282       int
02283       compare(size_type __pos1, size_type __n1, const basic_string& __str,
02284           size_type __pos2, size_type __n2) const;
02285 
02286       /**
02287        *  @brief  Compare to a C string.
02288        *  @param __s  C string to compare against.
02289        *  @return  Integer < 0, 0, or > 0.
02290        *
02291        *  Returns an integer < 0 if this string is ordered before @a __s, 0 if
02292        *  their values are equivalent, or > 0 if this string is ordered after
02293        *  @a __s.  Determines the effective length rlen of the strings to
02294        *  compare as the smallest of size() and the length of a string
02295        *  constructed from @a __s.  The function then compares the two strings
02296        *  by calling traits::compare(data(),s,rlen).  If the result of the
02297        *  comparison is nonzero returns it, otherwise the shorter one is
02298        *  ordered first.
02299       */
02300       int
02301       compare(const _CharT* __s) const;
02302 
02303       // _GLIBCXX_RESOLVE_LIB_DEFECTS
02304       // 5 String::compare specification questionable
02305       /**
02306        *  @brief  Compare substring to a C string.
02307        *  @param __pos  Index of first character of substring.
02308        *  @param __n1  Number of characters in substring.
02309        *  @param __s  C string to compare against.
02310        *  @return  Integer < 0, 0, or > 0.
02311        *
02312        *  Form the substring of this string from the @a __n1
02313        *  characters starting at @a pos.  Returns an integer < 0 if
02314        *  the substring is ordered before @a __s, 0 if their values
02315        *  are equivalent, or > 0 if the substring is ordered after @a
02316        *  __s.  Determines the effective length rlen of the strings to
02317        *  compare as the smallest of the length of the substring and
02318        *  the length of a string constructed from @a __s.  The
02319        *  function then compares the two string by calling
02320        *  traits::compare(substring.data(),__s,rlen).  If the result of
02321        *  the comparison is nonzero returns it, otherwise the shorter
02322        *  one is ordered first.
02323       */
02324       int
02325       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
02326 
02327       /**
02328        *  @brief  Compare substring against a character %array.
02329        *  @param __pos  Index of first character of substring.
02330        *  @param __n1  Number of characters in substring.
02331        *  @param __s  character %array to compare against.
02332        *  @param __n2  Number of characters of s.
02333        *  @return  Integer < 0, 0, or > 0.
02334        *
02335        *  Form the substring of this string from the @a __n1
02336        *  characters starting at @a __pos.  Form a string from the
02337        *  first @a __n2 characters of @a __s.  Returns an integer < 0
02338        *  if this substring is ordered before the string from @a __s,
02339        *  0 if their values are equivalent, or > 0 if this substring
02340        *  is ordered after the string from @a __s.  Determines the
02341        *  effective length rlen of the strings to compare as the
02342        *  smallest of the length of the substring and @a __n2.  The
02343        *  function then compares the two strings by calling
02344        *  traits::compare(substring.data(),s,rlen).  If the result of
02345        *  the comparison is nonzero returns it, otherwise the shorter
02346        *  one is ordered first.
02347        *
02348        *  NB: s must have at least n2 characters, &apos;\\0&apos; has
02349        *  no special meaning.
02350       */
02351       int
02352       compare(size_type __pos, size_type __n1, const _CharT* __s,
02353           size_type __n2) const;
02354   };
02355 
02356   // operator+
02357   /**
02358    *  @brief  Concatenate two strings.
02359    *  @param __lhs  First string.
02360    *  @param __rhs  Last string.
02361    *  @return  New string with value of @a __lhs followed by @a __rhs.
02362    */
02363   template<typename _CharT, typename _Traits, typename _Alloc>
02364     basic_string<_CharT, _Traits, _Alloc>
02365     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02366           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02367     {
02368       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
02369       __str.append(__rhs);
02370       return __str;
02371     }
02372 
02373   /**
02374    *  @brief  Concatenate C string and string.
02375    *  @param __lhs  First string.
02376    *  @param __rhs  Last string.
02377    *  @return  New string with value of @a __lhs followed by @a __rhs.
02378    */
02379   template<typename _CharT, typename _Traits, typename _Alloc>
02380     basic_string<_CharT,_Traits,_Alloc>
02381     operator+(const _CharT* __lhs,
02382           const basic_string<_CharT,_Traits,_Alloc>& __rhs);
02383 
02384   /**
02385    *  @brief  Concatenate character and string.
02386    *  @param __lhs  First string.
02387    *  @param __rhs  Last string.
02388    *  @return  New string with @a __lhs followed by @a __rhs.
02389    */
02390   template<typename _CharT, typename _Traits, typename _Alloc>
02391     basic_string<_CharT,_Traits,_Alloc>
02392     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
02393 
02394   /**
02395    *  @brief  Concatenate string and C string.
02396    *  @param __lhs  First string.
02397    *  @param __rhs  Last string.
02398    *  @return  New string with @a __lhs followed by @a __rhs.
02399    */
02400   template<typename _CharT, typename _Traits, typename _Alloc>
02401     inline basic_string<_CharT, _Traits, _Alloc>
02402     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02403          const _CharT* __rhs)
02404     {
02405       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
02406       __str.append(__rhs);
02407       return __str;
02408     }
02409 
02410   /**
02411    *  @brief  Concatenate string and character.
02412    *  @param __lhs  First string.
02413    *  @param __rhs  Last string.
02414    *  @return  New string with @a __lhs followed by @a __rhs.
02415    */
02416   template<typename _CharT, typename _Traits, typename _Alloc>
02417     inline basic_string<_CharT, _Traits, _Alloc>
02418     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
02419     {
02420       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
02421       typedef typename __string_type::size_type     __size_type;
02422       __string_type __str(__lhs);
02423       __str.append(__size_type(1), __rhs);
02424       return __str;
02425     }
02426 
02427 #if __cplusplus >= 201103L
02428   template<typename _CharT, typename _Traits, typename _Alloc>
02429     inline basic_string<_CharT, _Traits, _Alloc>
02430     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
02431           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02432     { return std::move(__lhs.append(__rhs)); }
02433 
02434   template<typename _CharT, typename _Traits, typename _Alloc>
02435     inline basic_string<_CharT, _Traits, _Alloc>
02436     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02437           basic_string<_CharT, _Traits, _Alloc>&& __rhs)
02438     { return std::move(__rhs.insert(0, __lhs)); }
02439 
02440   template<typename _CharT, typename _Traits, typename _Alloc>
02441     inline basic_string<_CharT, _Traits, _Alloc>
02442     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
02443           basic_string<_CharT, _Traits, _Alloc>&& __rhs)
02444     {
02445       const auto __size = __lhs.size() + __rhs.size();
02446       const bool __cond = (__size > __lhs.capacity()
02447                && __size <= __rhs.capacity());
02448       return __cond ? std::move(__rhs.insert(0, __lhs))
02449                 : std::move(__lhs.append(__rhs));
02450     }
02451 
02452   template<typename _CharT, typename _Traits, typename _Alloc>
02453     inline basic_string<_CharT, _Traits, _Alloc>
02454     operator+(const _CharT* __lhs,
02455           basic_string<_CharT, _Traits, _Alloc>&& __rhs)
02456     { return std::move(__rhs.insert(0, __lhs)); }
02457 
02458   template<typename _CharT, typename _Traits, typename _Alloc>
02459     inline basic_string<_CharT, _Traits, _Alloc>
02460     operator+(_CharT __lhs,
02461           basic_string<_CharT, _Traits, _Alloc>&& __rhs)
02462     { return std::move(__rhs.insert(0, 1, __lhs)); }
02463 
02464   template<typename _CharT, typename _Traits, typename _Alloc>
02465     inline basic_string<_CharT, _Traits, _Alloc>
02466     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
02467           const _CharT* __rhs)
02468     { return std::move(__lhs.append(__rhs)); }
02469 
02470   template<typename _CharT, typename _Traits, typename _Alloc>
02471     inline basic_string<_CharT, _Traits, _Alloc>
02472     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
02473           _CharT __rhs)
02474     { return std::move(__lhs.append(1, __rhs)); }
02475 #endif
02476 
02477   // operator ==
02478   /**
02479    *  @brief  Test equivalence of two strings.
02480    *  @param __lhs  First string.
02481    *  @param __rhs  Second string.
02482    *  @return  True if @a __lhs.compare(@a __rhs) == 0.  False otherwise.
02483    */
02484   template<typename _CharT, typename _Traits, typename _Alloc>
02485     inline bool
02486     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02487            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02488     { return __lhs.compare(__rhs) == 0; }
02489 
02490   template<typename _CharT>
02491     inline
02492     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, bool>::__type
02493     operator==(const basic_string<_CharT>& __lhs,
02494            const basic_string<_CharT>& __rhs)
02495     { return (__lhs.size() == __rhs.size()
02496           && !std::char_traits<_CharT>::compare(__lhs.data(), __rhs.data(),
02497                             __lhs.size())); }
02498 
02499   /**
02500    *  @brief  Test equivalence of C string and string.
02501    *  @param __lhs  C string.
02502    *  @param __rhs  String.
02503    *  @return  True if @a __rhs.compare(@a __lhs) == 0.  False otherwise.
02504    */
02505   template<typename _CharT, typename _Traits, typename _Alloc>
02506     inline bool
02507     operator==(const _CharT* __lhs,
02508            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02509     { return __rhs.compare(__lhs) == 0; }
02510 
02511   /**
02512    *  @brief  Test equivalence of string and C string.
02513    *  @param __lhs  String.
02514    *  @param __rhs  C string.
02515    *  @return  True if @a __lhs.compare(@a __rhs) == 0.  False otherwise.
02516    */
02517   template<typename _CharT, typename _Traits, typename _Alloc>
02518     inline bool
02519     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02520            const _CharT* __rhs)
02521     { return __lhs.compare(__rhs) == 0; }
02522 
02523   // operator !=
02524   /**
02525    *  @brief  Test difference of two strings.
02526    *  @param __lhs  First string.
02527    *  @param __rhs  Second string.
02528    *  @return  True if @a __lhs.compare(@a __rhs) != 0.  False otherwise.
02529    */
02530   template<typename _CharT, typename _Traits, typename _Alloc>
02531     inline bool
02532     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02533            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02534     { return !(__lhs == __rhs); }
02535 
02536   /**
02537    *  @brief  Test difference of C string and string.
02538    *  @param __lhs  C string.
02539    *  @param __rhs  String.
02540    *  @return  True if @a __rhs.compare(@a __lhs) != 0.  False otherwise.
02541    */
02542   template<typename _CharT, typename _Traits, typename _Alloc>
02543     inline bool
02544     operator!=(const _CharT* __lhs,
02545            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02546     { return !(__lhs == __rhs); }
02547 
02548   /**
02549    *  @brief  Test difference of string and C string.
02550    *  @param __lhs  String.
02551    *  @param __rhs  C string.
02552    *  @return  True if @a __lhs.compare(@a __rhs) != 0.  False otherwise.
02553    */
02554   template<typename _CharT, typename _Traits, typename _Alloc>
02555     inline bool
02556     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02557            const _CharT* __rhs)
02558     { return !(__lhs == __rhs); }
02559 
02560   // operator <
02561   /**
02562    *  @brief  Test if string precedes string.
02563    *  @param __lhs  First string.
02564    *  @param __rhs  Second string.
02565    *  @return  True if @a __lhs precedes @a __rhs.  False otherwise.
02566    */
02567   template<typename _CharT, typename _Traits, typename _Alloc>
02568     inline bool
02569     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02570           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02571     { return __lhs.compare(__rhs) < 0; }
02572 
02573   /**
02574    *  @brief  Test if string precedes C string.
02575    *  @param __lhs  String.
02576    *  @param __rhs  C string.
02577    *  @return  True if @a __lhs precedes @a __rhs.  False otherwise.
02578    */
02579   template<typename _CharT, typename _Traits, typename _Alloc>
02580     inline bool
02581     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02582           const _CharT* __rhs)
02583     { return __lhs.compare(__rhs) < 0; }
02584 
02585   /**
02586    *  @brief  Test if C string precedes string.
02587    *  @param __lhs  C string.
02588    *  @param __rhs  String.
02589    *  @return  True if @a __lhs precedes @a __rhs.  False otherwise.
02590    */
02591   template<typename _CharT, typename _Traits, typename _Alloc>
02592     inline bool
02593     operator<(const _CharT* __lhs,
02594           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02595     { return __rhs.compare(__lhs) > 0; }
02596 
02597   // operator >
02598   /**
02599    *  @brief  Test if string follows string.
02600    *  @param __lhs  First string.
02601    *  @param __rhs  Second string.
02602    *  @return  True if @a __lhs follows @a __rhs.  False otherwise.
02603    */
02604   template<typename _CharT, typename _Traits, typename _Alloc>
02605     inline bool
02606     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02607           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02608     { return __lhs.compare(__rhs) > 0; }
02609 
02610   /**
02611    *  @brief  Test if string follows C string.
02612    *  @param __lhs  String.
02613    *  @param __rhs  C string.
02614    *  @return  True if @a __lhs follows @a __rhs.  False otherwise.
02615    */
02616   template<typename _CharT, typename _Traits, typename _Alloc>
02617     inline bool
02618     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02619           const _CharT* __rhs)
02620     { return __lhs.compare(__rhs) > 0; }
02621 
02622   /**
02623    *  @brief  Test if C string follows string.
02624    *  @param __lhs  C string.
02625    *  @param __rhs  String.
02626    *  @return  True if @a __lhs follows @a __rhs.  False otherwise.
02627    */
02628   template<typename _CharT, typename _Traits, typename _Alloc>
02629     inline bool
02630     operator>(const _CharT* __lhs,
02631           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02632     { return __rhs.compare(__lhs) < 0; }
02633 
02634   // operator <=
02635   /**
02636    *  @brief  Test if string doesn't follow string.
02637    *  @param __lhs  First string.
02638    *  @param __rhs  Second string.
02639    *  @return  True if @a __lhs doesn't follow @a __rhs.  False otherwise.
02640    */
02641   template<typename _CharT, typename _Traits, typename _Alloc>
02642     inline bool
02643     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02644            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02645     { return __lhs.compare(__rhs) <= 0; }
02646 
02647   /**
02648    *  @brief  Test if string doesn't follow C string.
02649    *  @param __lhs  String.
02650    *  @param __rhs  C string.
02651    *  @return  True if @a __lhs doesn't follow @a __rhs.  False otherwise.
02652    */
02653   template<typename _CharT, typename _Traits, typename _Alloc>
02654     inline bool
02655     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02656            const _CharT* __rhs)
02657     { return __lhs.compare(__rhs) <= 0; }
02658 
02659   /**
02660    *  @brief  Test if C string doesn't follow string.
02661    *  @param __lhs  C string.
02662    *  @param __rhs  String.
02663    *  @return  True if @a __lhs doesn't follow @a __rhs.  False otherwise.
02664    */
02665   template<typename _CharT, typename _Traits, typename _Alloc>
02666     inline bool
02667     operator<=(const _CharT* __lhs,
02668            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02669     { return __rhs.compare(__lhs) >= 0; }
02670 
02671   // operator >=
02672   /**
02673    *  @brief  Test if string doesn't precede string.
02674    *  @param __lhs  First string.
02675    *  @param __rhs  Second string.
02676    *  @return  True if @a __lhs doesn't precede @a __rhs.  False otherwise.
02677    */
02678   template<typename _CharT, typename _Traits, typename _Alloc>
02679     inline bool
02680     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02681            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02682     { return __lhs.compare(__rhs) >= 0; }
02683 
02684   /**
02685    *  @brief  Test if string doesn't precede C string.
02686    *  @param __lhs  String.
02687    *  @param __rhs  C string.
02688    *  @return  True if @a __lhs doesn't precede @a __rhs.  False otherwise.
02689    */
02690   template<typename _CharT, typename _Traits, typename _Alloc>
02691     inline bool
02692     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
02693            const _CharT* __rhs)
02694     { return __lhs.compare(__rhs) >= 0; }
02695 
02696   /**
02697    *  @brief  Test if C string doesn't precede string.
02698    *  @param __lhs  C string.
02699    *  @param __rhs  String.
02700    *  @return  True if @a __lhs doesn't precede @a __rhs.  False otherwise.
02701    */
02702   template<typename _CharT, typename _Traits, typename _Alloc>
02703     inline bool
02704     operator>=(const _CharT* __lhs,
02705          const basic_string<_CharT, _Traits, _Alloc>& __rhs)
02706     { return __rhs.compare(__lhs) <= 0; }
02707 
02708   /**
02709    *  @brief  Swap contents of two strings.
02710    *  @param __lhs  First string.
02711    *  @param __rhs  Second string.
02712    *
02713    *  Exchanges the contents of @a __lhs and @a __rhs in constant time.
02714    */
02715   template<typename _CharT, typename _Traits, typename _Alloc>
02716     inline void
02717     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
02718      basic_string<_CharT, _Traits, _Alloc>& __rhs)
02719     { __lhs.swap(__rhs); }
02720 
02721   /**
02722    *  @brief  Read stream into a string.
02723    *  @param __is  Input stream.
02724    *  @param __str  Buffer to store into.
02725    *  @return  Reference to the input stream.
02726    *
02727    *  Stores characters from @a __is into @a __str until whitespace is
02728    *  found, the end of the stream is encountered, or str.max_size()
02729    *  is reached.  If is.width() is non-zero, that is the limit on the
02730    *  number of characters stored into @a __str.  Any previous
02731    *  contents of @a __str are erased.
02732    */
02733   template<typename _CharT, typename _Traits, typename _Alloc>
02734     basic_istream<_CharT, _Traits>&
02735     operator>>(basic_istream<_CharT, _Traits>& __is,
02736            basic_string<_CharT, _Traits, _Alloc>& __str);
02737 
02738   template<>
02739     basic_istream<char>&
02740     operator>>(basic_istream<char>& __is, basic_string<char>& __str);
02741 
02742   /**
02743    *  @brief  Write string to a stream.
02744    *  @param __os  Output stream.
02745    *  @param __str  String to write out.
02746    *  @return  Reference to the output stream.
02747    *
02748    *  Output characters of @a __str into os following the same rules as for
02749    *  writing a C string.
02750    */
02751   template<typename _CharT, typename _Traits, typename _Alloc>
02752     inline basic_ostream<_CharT, _Traits>&
02753     operator<<(basic_ostream<_CharT, _Traits>& __os,
02754            const basic_string<_CharT, _Traits, _Alloc>& __str)
02755     {
02756       // _GLIBCXX_RESOLVE_LIB_DEFECTS
02757       // 586. string inserter not a formatted function
02758       return __ostream_insert(__os, __str.data(), __str.size());
02759     }
02760 
02761   /**
02762    *  @brief  Read a line from stream into a string.
02763    *  @param __is  Input stream.
02764    *  @param __str  Buffer to store into.
02765    *  @param __delim  Character marking end of line.
02766    *  @return  Reference to the input stream.
02767    *
02768    *  Stores characters from @a __is into @a __str until @a __delim is
02769    *  found, the end of the stream is encountered, or str.max_size()
02770    *  is reached.  Any previous contents of @a __str are erased.  If
02771    *  @a __delim is encountered, it is extracted but not stored into
02772    *  @a __str.
02773    */
02774   template<typename _CharT, typename _Traits, typename _Alloc>
02775     basic_istream<_CharT, _Traits>&
02776     getline(basic_istream<_CharT, _Traits>& __is,
02777         basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
02778 
02779   /**
02780    *  @brief  Read a line from stream into a string.
02781    *  @param __is  Input stream.
02782    *  @param __str  Buffer to store into.
02783    *  @return  Reference to the input stream.
02784    *
02785    *  Stores characters from is into @a __str until &apos;\n&apos; is
02786    *  found, the end of the stream is encountered, or str.max_size()
02787    *  is reached.  Any previous contents of @a __str are erased.  If
02788    *  end of line is encountered, it is extracted but not stored into
02789    *  @a __str.
02790    */
02791   template<typename _CharT, typename _Traits, typename _Alloc>
02792     inline basic_istream<_CharT, _Traits>&
02793     getline(basic_istream<_CharT, _Traits>& __is,
02794         basic_string<_CharT, _Traits, _Alloc>& __str)
02795     { return getline(__is, __str, __is.widen('\n')); }
02796 
02797   template<>
02798     basic_istream<char>&
02799     getline(basic_istream<char>& __in, basic_string<char>& __str,
02800         char __delim);
02801 
02802 #ifdef _GLIBCXX_USE_WCHAR_T
02803   template<>
02804     basic_istream<wchar_t>&
02805     getline(basic_istream<wchar_t>& __in, basic_string<wchar_t>& __str,
02806         wchar_t __delim);
02807 #endif  
02808 
02809 _GLIBCXX_END_NAMESPACE_VERSION
02810 } // namespace
02811 
02812 #if ((__cplusplus >= 201103L) && defined(_GLIBCXX_USE_C99) \
02813      && !defined(_GLIBCXX_HAVE_BROKEN_VSWPRINTF))
02814 
02815 #include <ext/string_conversions.h>
02816 
02817 namespace std _GLIBCXX_VISIBILITY(default)
02818 {
02819 _GLIBCXX_BEGIN_NAMESPACE_VERSION
02820 
02821   // 21.4 Numeric Conversions [string.conversions].
02822   inline int
02823   stoi(const string& __str, size_t* __idx = 0, int __base = 10)
02824   { return __gnu_cxx::__stoa<long, int>(&std::strtol, "stoi", __str.c_str(),
02825                     __idx, __base); }
02826 
02827   inline long
02828   stol(const string& __str, size_t* __idx = 0, int __base = 10)
02829   { return __gnu_cxx::__stoa(&std::strtol, "stol", __str.c_str(),
02830                  __idx, __base); }
02831 
02832   inline unsigned long
02833   stoul(const string& __str, size_t* __idx = 0, int __base = 10)
02834   { return __gnu_cxx::__stoa(&std::strtoul, "stoul", __str.c_str(),
02835                  __idx, __base); }
02836 
02837   inline long long
02838   stoll(const string& __str, size_t* __idx = 0, int __base = 10)
02839   { return __gnu_cxx::__stoa(&std::strtoll, "stoll", __str.c_str(),
02840                  __idx, __base); }
02841 
02842   inline unsigned long long
02843   stoull(const string& __str, size_t* __idx = 0, int __base = 10)
02844   { return __gnu_cxx::__stoa(&std::strtoull, "stoull", __str.c_str(),
02845                  __idx, __base); }
02846 
02847   // NB: strtof vs strtod.
02848   inline float
02849   stof(const string& __str, size_t* __idx = 0)
02850   { return __gnu_cxx::__stoa(&std::strtof, "stof", __str.c_str(), __idx); }
02851 
02852   inline double
02853   stod(const string& __str, size_t* __idx = 0)
02854   { return __gnu_cxx::__stoa(&std::strtod, "stod", __str.c_str(), __idx); }
02855 
02856   inline long double
02857   stold(const string& __str, size_t* __idx = 0)
02858   { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }
02859 
02860   // NB: (v)snprintf vs sprintf.
02861 
02862   // DR 1261.
02863   inline string
02864   to_string(int __val)
02865   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
02866                        "%d", __val); }
02867 
02868   inline string
02869   to_string(unsigned __val)
02870   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
02871                        4 * sizeof(unsigned),
02872                        "%u", __val); }
02873 
02874   inline string
02875   to_string(long __val)
02876   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
02877                        "%ld", __val); }
02878 
02879   inline string
02880   to_string(unsigned long __val)
02881   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
02882                        4 * sizeof(unsigned long),
02883                        "%lu", __val); }
02884 
02885   inline string
02886   to_string(long long __val)
02887   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
02888                        4 * sizeof(long long),
02889                        "%lld", __val); }
02890 
02891   inline string
02892   to_string(unsigned long long __val)
02893   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
02894                        4 * sizeof(unsigned long long),
02895                        "%llu", __val); }
02896 
02897   inline string
02898   to_string(float __val)
02899   {
02900     const int __n = 
02901       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
02902     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
02903                        "%f", __val);
02904   }
02905 
02906   inline string
02907   to_string(double __val)
02908   {
02909     const int __n = 
02910       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
02911     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
02912                        "%f", __val);
02913   }
02914 
02915   inline string
02916   to_string(long double __val)
02917   {
02918     const int __n = 
02919       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
02920     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
02921                        "%Lf", __val);
02922   }
02923 
02924 #ifdef _GLIBCXX_USE_WCHAR_T
02925   inline int 
02926   stoi(const wstring& __str, size_t* __idx = 0, int __base = 10)
02927   { return __gnu_cxx::__stoa<long, int>(&std::wcstol, "stoi", __str.c_str(),
02928                     __idx, __base); }
02929 
02930   inline long 
02931   stol(const wstring& __str, size_t* __idx = 0, int __base = 10)
02932   { return __gnu_cxx::__stoa(&std::wcstol, "stol", __str.c_str(),
02933                  __idx, __base); }
02934 
02935   inline unsigned long
02936   stoul(const wstring& __str, size_t* __idx = 0, int __base = 10)
02937   { return __gnu_cxx::__stoa(&std::wcstoul, "stoul", __str.c_str(),
02938                  __idx, __base); }
02939 
02940   inline long long
02941   stoll(const wstring& __str, size_t* __idx = 0, int __base = 10)
02942   { return __gnu_cxx::__stoa(&std::wcstoll, "stoll", __str.c_str(),
02943                  __idx, __base); }
02944 
02945   inline unsigned long long
02946   stoull(const wstring& __str, size_t* __idx = 0, int __base = 10)
02947   { return __gnu_cxx::__stoa(&std::wcstoull, "stoull", __str.c_str(),
02948                  __idx, __base); }
02949 
02950   // NB: wcstof vs wcstod.
02951   inline float
02952   stof(const wstring& __str, size_t* __idx = 0)
02953   { return __gnu_cxx::__stoa(&std::wcstof, "stof", __str.c_str(), __idx); }
02954 
02955   inline double
02956   stod(const wstring& __str, size_t* __idx = 0)
02957   { return __gnu_cxx::__stoa(&std::wcstod, "stod", __str.c_str(), __idx); }
02958 
02959   inline long double
02960   stold(const wstring& __str, size_t* __idx = 0)
02961   { return __gnu_cxx::__stoa(&std::wcstold, "stold", __str.c_str(), __idx); }
02962 
02963   // DR 1261.
02964   inline wstring
02965   to_wstring(int __val)
02966   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(int),
02967                         L"%d", __val); }
02968 
02969   inline wstring
02970   to_wstring(unsigned __val)
02971   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
02972                         4 * sizeof(unsigned),
02973                         L"%u", __val); }
02974 
02975   inline wstring
02976   to_wstring(long __val)
02977   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(long),
02978                         L"%ld", __val); }
02979 
02980   inline wstring
02981   to_wstring(unsigned long __val)
02982   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
02983                         4 * sizeof(unsigned long),
02984                         L"%lu", __val); }
02985 
02986   inline wstring
02987   to_wstring(long long __val)
02988   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
02989                         4 * sizeof(long long),
02990                         L"%lld", __val); }
02991 
02992   inline wstring
02993   to_wstring(unsigned long long __val)
02994   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
02995                         4 * sizeof(unsigned long long),
02996                         L"%llu", __val); }
02997 
02998   inline wstring
02999   to_wstring(float __val)
03000   {
03001     const int __n =
03002       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
03003     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
03004                         L"%f", __val);
03005   }
03006 
03007   inline wstring
03008   to_wstring(double __val)
03009   {
03010     const int __n =
03011       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
03012     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
03013                         L"%f", __val);
03014   }
03015 
03016   inline wstring
03017   to_wstring(long double __val)
03018   {
03019     const int __n =
03020       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
03021     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
03022                         L"%Lf", __val);
03023   }
03024 #endif
03025 
03026 _GLIBCXX_END_NAMESPACE_VERSION
03027 } // namespace
03028 
03029 #endif /* C++11 && _GLIBCXX_USE_C99 ... */
03030 
03031 #if __cplusplus >= 201103L
03032 
03033 #include <bits/functional_hash.h>
03034 
03035 namespace std _GLIBCXX_VISIBILITY(default)
03036 {
03037 _GLIBCXX_BEGIN_NAMESPACE_VERSION
03038 
03039   // DR 1182.
03040 
03041 #ifndef _GLIBCXX_COMPATIBILITY_CXX0X
03042   /// std::hash specialization for string.
03043   template<>
03044     struct hash<string>
03045     : public __hash_base<size_t, string>
03046     {
03047       size_t
03048       operator()(const string& __s) const noexcept
03049       { return std::_Hash_impl::hash(__s.data(), __s.length()); }
03050     };
03051 
03052   template<>
03053     struct __is_fast_hash<hash<string>> : std::false_type
03054     { };
03055 
03056 #ifdef _GLIBCXX_USE_WCHAR_T
03057   /// std::hash specialization for wstring.
03058   template<>
03059     struct hash<wstring>
03060     : public __hash_base<size_t, wstring>
03061     {
03062       size_t
03063       operator()(const wstring& __s) const noexcept
03064       { return std::_Hash_impl::hash(__s.data(),
03065                                      __s.length() * sizeof(wchar_t)); }
03066     };
03067 
03068   template<>
03069     struct __is_fast_hash<hash<wstring>> : std::false_type
03070     { };
03071 #endif
03072 #endif /* _GLIBCXX_COMPATIBILITY_CXX0X */
03073 
03074 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
03075   /// std::hash specialization for u16string.
03076   template<>
03077     struct hash<u16string>
03078     : public __hash_base<size_t, u16string>
03079     {
03080       size_t
03081       operator()(const u16string& __s) const noexcept
03082       { return std::_Hash_impl::hash(__s.data(),
03083                                      __s.length() * sizeof(char16_t)); }
03084     };
03085 
03086   template<>
03087     struct __is_fast_hash<hash<u16string>> : std::false_type
03088     { };
03089 
03090   /// std::hash specialization for u32string.
03091   template<>
03092     struct hash<u32string>
03093     : public __hash_base<size_t, u32string>
03094     {
03095       size_t
03096       operator()(const u32string& __s) const noexcept
03097       { return std::_Hash_impl::hash(__s.data(),
03098                                      __s.length() * sizeof(char32_t)); }
03099     };
03100 
03101   template<>
03102     struct __is_fast_hash<hash<u32string>> : std::false_type
03103     { };
03104 #endif
03105 
03106 _GLIBCXX_END_NAMESPACE_VERSION
03107 } // namespace
03108 
03109 #endif // C++11
03110 
03111 #endif /* _BASIC_STRING_H */