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