# 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
    00004 // Free Software Foundation, Inc.
    00005 //
    00006 // This file is part of the GNU ISO C++ Library.  This library is free
    00007 // software; you can redistribute it and/or modify it under the
    00008 // terms of the GNU General Public License as published by the
    00009 // Free Software Foundation; either version 2, or (at your option)
    00010 // any later version.
    00011
    00012 // This library is distributed in the hope that it will be useful,
    00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
    00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    00015 // GNU General Public License for more details.
    00016
    00017 // You should have received a copy of the GNU General Public License along
    00018 // with this library; see the file COPYING.  If not, write to the Free
    00019 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
    00020 // USA.
    00021
    00022 // As a special exception, you may use this file as part of a free software
    00023 // library without restriction.  Specifically, if other files instantiate
    00024 // templates or use macros or inline functions from this file, or you compile
    00025 // this file and link it with other files to produce an executable, this
    00026 // file does not by itself cause the resulting executable to be covered by
    00027 // the GNU General Public License.  This exception does not however
    00028 // invalidate any other reasons why the executable file might be covered by
    00029 // the GNU General Public License.
    00030
    00031 //
    00032 // ISO C++ 14882: 21 Strings library
    00033 //
    00034
    00035 /** @file basic_string.h
    00036  *  This is an internal header file, included by other library headers.
    00037  *  You should not attempt to use it directly.
    00038  */
    00039
    00040 #ifndef _BASIC_STRING_H
    00041 #define _BASIC_STRING_H 1
    00042
    00043 #pragma GCC system_header
    00044
    00045 #include <bits/atomicity.h>
    00046 #include <debug/debug.h>
    00047
    00048 namespace std
    00049 {
    00050   /**
    00051    *  @class basic_string basic_string.h <string>
    00052    *  @brief  Managing sequences of characters and character-like objects.
    00053    *
    00054    *  @ingroup Containers
    00055    *  @ingroup Sequences
    00056    *
    00057    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
    00058    *  <a href="tables.html#66">reversible container</a>, and a
    00059    *  <a href="tables.html#67">sequence</a>.  Of the
    00060    *  <a href="tables.html#68">optional sequence requirements</a>, only
    00061    *  @c push_back, @c at, and array access are supported.
    00062    *
    00063    *  @doctodo
    00064    *
    00065    *
    00066    *  @if maint
    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 "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 "empty string" _Rep object already "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    *  @endif
    00107   */
    00108   // 21.3  Template class basic_string
    00109   template<typename _CharT, typename _Traits, typename _Alloc>
    00110     class basic_string
    00111     {
    00112       // Types:
    00113     public:
    00114       typedef _Traits                       traits_type;
    00115       typedef typename _Traits::char_type           value_type;
    00116       typedef _Alloc                        allocator_type;
    00117       typedef typename _Alloc::size_type            size_type;
    00118       typedef typename _Alloc::difference_type          difference_type;
    00119       typedef typename _Alloc::reference            reference;
    00120       typedef typename _Alloc::const_reference          const_reference;
    00121       typedef typename _Alloc::pointer              pointer;
    00122       typedef typename _Alloc::const_pointer            const_pointer;
    00123       typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
    00124       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
    00125                                                             const_iterator;
    00126       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
    00127       typedef std::reverse_iterator<iterator>           reverse_iterator;
    00128
    00129     private:
    00130       // _Rep: string representation
    00131       //   Invariants:
    00132       //   1. String really contains _M_length + 1 characters: due to 21.3.4
    00133       //      must be kept null-terminated.
    00134       //   2. _M_capacity >= _M_length
    00135       //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).
    00136       //   3. _M_refcount has three states:
    00137       //      -1: leaked, one reference, no ref-copies allowed, non-const.
    00138       //       0: one reference, non-const.
    00139       //     n>0: n + 1 references, operations require a lock, const.
    00140       //   4. All fields==0 is an empty string, given the extra storage
    00141       //      beyond-the-end for a null terminator; thus, the shared
    00142       //      empty string representation needs no constructor.
    00143
    00144       struct _Rep_base
    00145       {
    00146     size_type       _M_length;
    00147     size_type       _M_capacity;
    00148     _Atomic_word        _M_refcount;
    00149       };
    00150
    00151       struct _Rep : _Rep_base
    00152       {
    00153     // Types:
    00154     typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
    00155
    00156     // (Public) Data members:
    00157
    00158     // The maximum number of individual char_type elements of an
    00159     // individual string is determined by _S_max_size. This is the
    00160     // value that will be returned by max_size().  (Whereas npos
    00161     // is the maximum number of bytes the allocator can allocate.)
    00162     // If one was to divvy up the theoretical largest size string,
    00163     // with a terminating character and m _CharT elements, it'd
    00164     // look like this:
    00165     // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
    00166     // Solving for m:
    00167     // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
    00168     // In addition, this implementation quarters this amount.
    00169     static const size_type  _S_max_size;
    00170     static const _CharT _S_terminal;
    00171
    00172     // The following storage is init'd to 0 by the linker, resulting
    00173         // (carefully) in an empty string with one reference.
    00174         static size_type _S_empty_rep_storage[];
    00175
    00176         static _Rep&
    00177         _S_empty_rep()
    00178         { return *reinterpret_cast<_Rep*>(&_S_empty_rep_storage); }
    00179
    00180         bool
    00181     _M_is_leaked() const
    00182         { return this->_M_refcount < 0; }
    00183
    00184         bool
    00185     _M_is_shared() const
    00186         { return this->_M_refcount > 0; }
    00187
    00188         void
    00189     _M_set_leaked()
    00190         { this->_M_refcount = -1; }
    00191
    00192         void
    00193     _M_set_sharable()
    00194         { this->_M_refcount = 0; }
    00195
    00196     _CharT*
    00197     _M_refdata() throw()
    00198     { return reinterpret_cast<_CharT*>(this + 1); }
    00199
    00200     _CharT*
    00201     _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
    00202     {
    00203       return (!_M_is_leaked() && __alloc1 == __alloc2)
    00204               ? _M_refcopy() : _M_clone(__alloc1);
    00205     }
    00206
    00207     // Create & Destroy
    00208     static _Rep*
    00209     _S_create(size_type, size_type, const _Alloc&);
    00210
    00211     void
    00212     _M_dispose(const _Alloc& __a)
    00213     {
    00214       if (__builtin_expect(this != &_S_empty_rep(), false))
    00215         if (__gnu_cxx::__exchange_and_add(&this->_M_refcount, -1) <= 0)
    00216           _M_destroy(__a);
    00217     }  // XXX MT
    00218
    00219     void
    00220     _M_destroy(const _Alloc&) throw();
    00221
    00222     _CharT*
    00223     _M_refcopy() throw()
    00224     {
    00225       if (__builtin_expect(this != &_S_empty_rep(), false))
    00226             __gnu_cxx::__atomic_add(&this->_M_refcount, 1);
    00227       return _M_refdata();
    00228     }  // XXX MT
    00229
    00230     _CharT*
    00231     _M_clone(const _Alloc&, size_type __res = 0);
    00232       };
    00233
    00234       // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
    00235       struct _Alloc_hider : _Alloc
    00236       {
    00237     _Alloc_hider(_CharT* __dat, const _Alloc& __a)
    00238     : _Alloc(__a), _M_p(__dat) { }
    00239
    00240     _CharT* _M_p; // The actual data.
    00241       };
    00242
    00243     public:
    00244       // Data Members (public):
    00245       // NB: This is an unsigned type, and thus represents the maximum
    00246       // size that the allocator can hold.
    00247       /// @var
    00248       /// Value returned by various member functions when they fail.
    00249       static const size_type    npos = static_cast<size_type>(-1);
    00250
    00251     private:
    00252       // Data Members (private):
    00253       mutable _Alloc_hider  _M_dataplus;
    00254
    00255       _CharT*
    00256       _M_data() const
    00257       { return  _M_dataplus._M_p; }
    00258
    00259       _CharT*
    00260       _M_data(_CharT* __p)
    00261       { return (_M_dataplus._M_p = __p); }
    00262
    00263       _Rep*
    00264       _M_rep() const
    00265       { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
    00266
    00267       // For the internal use we have functions similar to `begin'/`end'
    00268       // but they do not call _M_leak.
    00269       iterator
    00270       _M_ibegin() const { return iterator(_M_data()); }
    00271
    00272       iterator
    00273       _M_iend() const { return iterator(_M_data() + this->size()); }
    00274
    00275       void
    00276       _M_leak()    // for use in begin() & non-const op[]
    00277       {
    00278     if (!_M_rep()->_M_is_leaked())
    00279       _M_leak_hard();
    00280       }
    00281
    00282       size_type
    00283       _M_check(size_type __pos, const char* __s) const
    00284       {
    00285     if (__pos > this->size())
    00286       __throw_out_of_range(__N(__s));
    00287     return __pos;
    00288       }
    00289
    00290       // NB: _M_limit doesn't check for a bad __pos value.
    00291       size_type
    00292       _M_limit(size_type __pos, size_type __off) const
    00293       {
    00294     const bool __testoff =  __off < this->size() - __pos;
    00295     return __testoff ? __off : this->size() - __pos;
    00296       }
    00297
    00298       // _S_copy_chars is a separate template to permit specialization
    00299       // to optimize for the common case of pointers as iterators.
    00300       template<class _Iterator>
    00301         static void
    00302         _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
    00303         {
    00304       for (; __k1 != __k2; ++__k1, ++__p)
    00305         traits_type::assign(*__p, *__k1); // These types are off.
    00306     }
    00307
    00308       static void
    00309       _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2)
    00310       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
    00311
    00312       static void
    00313       _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
    00314       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
    00315
    00316       static void
    00317       _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2)
    00318       { traits_type::copy(__p, __k1, __k2 - __k1); }
    00319
    00320       static void
    00321       _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
    00322       { traits_type::copy(__p, __k1, __k2 - __k1); }
    00323
    00324       void
    00325       _M_mutate(size_type __pos, size_type __len1, size_type __len2);
    00326
    00327       void
    00328       _M_leak_hard();
    00329
    00330       static _Rep&
    00331       _S_empty_rep()
    00332       { return _Rep::_S_empty_rep(); }
    00333
    00334     public:
    00335       // Construct/copy/destroy:
    00336       // NB: We overload ctors in some cases instead of using default
    00337       // arguments, per 17.4.4.4 para. 2 item 2.
    00338
    00339       /**
    00340        *  @brief  Default constructor creates an empty string.
    00341        */
    00342       inline
    00343       basic_string();
    00344
    00345       /**
    00346        *  @brief  Construct an empty string using allocator a.
    00347        */
    00348       explicit
    00349       basic_string(const _Alloc& __a);
    00350
    00351       // NB: per LWG issue 42, semantics different from IS:
    00352       /**
    00353        *  @brief  Construct string with copy of value of @a str.
    00354        *  @param  str  Source string.
    00355        */
    00356       basic_string(const basic_string& __str);
    00357       /**
    00358        *  @brief  Construct string as copy of a substring.
    00359        *  @param  str  Source string.
    00360        *  @param  pos  Index of first character to copy from.
    00361        *  @param  n  Number of characters to copy (default remainder).
    00362        */
    00363       basic_string(const basic_string& __str, size_type __pos,
    00364            size_type __n = npos);
    00365       /**
    00366        *  @brief  Construct string as copy of a substring.
    00367        *  @param  str  Source string.
    00368        *  @param  pos  Index of first character to copy from.
    00369        *  @param  n  Number of characters to copy.
    00370        *  @param  a  Allocator to use.
    00371        */
    00372       basic_string(const basic_string& __str, size_type __pos,
    00373            size_type __n, const _Alloc& __a);
    00374
    00375       /**
    00376        *  @brief  Construct string initialized by a character array.
    00377        *  @param  s  Source character array.
    00378        *  @param  n  Number of characters to copy.
    00379        *  @param  a  Allocator to use (default is default allocator).
    00380        *
    00381        *  NB: s must have at least n characters, '\0' has no special
    00382        *  meaning.
    00383        */
    00384       basic_string(const _CharT* __s, size_type __n,
    00385            const _Alloc& __a = _Alloc());
    00386       /**
    00387        *  @brief  Construct string as copy of a C string.
    00388        *  @param  s  Source C string.
    00389        *  @param  a  Allocator to use (default is default allocator).
    00390        */
    00391       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
    00392       /**
    00393        *  @brief  Construct string as multiple characters.
    00394        *  @param  n  Number of characters.
    00395        *  @param  c  Character to use.
    00396        *  @param  a  Allocator to use (default is default allocator).
    00397        */
    00398       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
    00399
    00400       /**
    00401        *  @brief  Construct string as copy of a range.
    00402        *  @param  beg  Start of range.
    00403        *  @param  end  End of range.
    00404        *  @param  a  Allocator to use (default is default allocator).
    00405        */
    00406       template<class _InputIterator>
    00407         basic_string(_InputIterator __beg, _InputIterator __end,
    00408              const _Alloc& __a = _Alloc());
    00409
    00410       /**
    00411        *  @brief  Destroy the string instance.
    00412        */
    00413       ~basic_string()
    00414       { _M_rep()->_M_dispose(this->get_allocator()); }
    00415
    00416       /**
    00417        *  @brief  Assign the value of @a str to this string.
    00418        *  @param  str  Source string.
    00419        */
    00420       basic_string&
    00421       operator=(const basic_string& __str)
    00422       {
    00423     this->assign(__str);
    00424     return *this;
    00425       }
    00426
    00427       /**
    00428        *  @brief  Copy contents of @a s into this string.
    00429        *  @param  s  Source null-terminated string.
    00430        */
    00431       basic_string&
    00432       operator=(const _CharT* __s)
    00433       {
    00434     this->assign(__s);
    00435     return *this;
    00436       }
    00437
    00438       /**
    00439        *  @brief  Set value to string of length 1.
    00440        *  @param  c  Source character.
    00441        *
    00442        *  Assigning to a character makes this string length 1 and
    00443        *  (*this)[0] == @a c.
    00444        */
    00445       basic_string&
    00446       operator=(_CharT __c)
    00447       {
    00448     this->assign(1, __c);
    00449     return *this;
    00450       }
    00451
    00452       // Iterators:
    00453       /**
    00454        *  Returns a read/write iterator that points to the first character in
    00455        *  the %string.  Unshares the string.
    00456        */
    00457       iterator
    00458       begin()
    00459       {
    00460     _M_leak();
    00461     return iterator(_M_data());
    00462       }
    00463
    00464       /**
    00465        *  Returns a read-only (constant) iterator that points to the first
    00466        *  character in the %string.
    00467        */
    00468       const_iterator
    00469       begin() const
    00470       { return const_iterator(_M_data()); }
    00471
    00472       /**
    00473        *  Returns a read/write iterator that points one past the last
    00474        *  character in the %string.  Unshares the string.
    00475        */
    00476       iterator
    00477       end()
    00478       {
    00479     _M_leak();
    00480     return iterator(_M_data() + this->size());
    00481       }
    00482
    00483       /**
    00484        *  Returns a read-only (constant) iterator that points one past the
    00485        *  last character in the %string.
    00486        */
    00487       const_iterator
    00488       end() const
    00489       { return const_iterator(_M_data() + this->size()); }
    00490
    00491       /**
    00492        *  Returns a read/write reverse iterator that points to the last
    00493        *  character in the %string.  Iteration is done in reverse element
    00494        *  order.  Unshares the string.
    00495        */
    00496       reverse_iterator
    00497       rbegin()
    00498       { return reverse_iterator(this->end()); }
    00499
    00500       /**
    00501        *  Returns a read-only (constant) reverse iterator that points
    00502        *  to the last character in the %string.  Iteration is done in
    00503        *  reverse element order.
    00504        */
    00505       const_reverse_iterator
    00506       rbegin() const
    00507       { return const_reverse_iterator(this->end()); }
    00508
    00509       /**
    00510        *  Returns a read/write reverse iterator that points to one before the
    00511        *  first character in the %string.  Iteration is done in reverse
    00512        *  element order.  Unshares the string.
    00513        */
    00514       reverse_iterator
    00515       rend()
    00516       { return reverse_iterator(this->begin()); }
    00517
    00518       /**
    00519        *  Returns a read-only (constant) reverse iterator that points
    00520        *  to one before the first character in the %string.  Iteration
    00521        *  is done in reverse element order.
    00522        */
    00523       const_reverse_iterator
    00524       rend() const
    00525       { return const_reverse_iterator(this->begin()); }
    00526
    00527     public:
    00528       // Capacity:
    00529       ///  Returns the number of characters in the string, not including any
    00530       ///  null-termination.
    00531       size_type
    00532       size() const { return _M_rep()->_M_length; }
    00533
    00534       ///  Returns the number of characters in the string, not including any
    00535       ///  null-termination.
    00536       size_type
    00537       length() const { return _M_rep()->_M_length; }
    00538
    00539       /// Returns the size() of the largest possible %string.
    00540       size_type
    00541       max_size() const { return _Rep::_S_max_size; }
    00542
    00543       /**
    00544        *  @brief  Resizes the %string to the specified number of characters.
    00545        *  @param  n  Number of characters the %string should contain.
    00546        *  @param  c  Character to fill any new elements.
    00547        *
    00548        *  This function will %resize the %string to the specified
    00549        *  number of characters.  If the number is smaller than the
    00550        *  %string's current size the %string is truncated, otherwise
    00551        *  the %string is extended and new elements are set to @a c.
    00552        */
    00553       void
    00554       resize(size_type __n, _CharT __c);
    00555
    00556       /**
    00557        *  @brief  Resizes the %string to the specified number of characters.
    00558        *  @param  n  Number of characters the %string should contain.
    00559        *
    00560        *  This function will resize the %string to the specified length.  If
    00561        *  the new size is smaller than the %string's current size the %string
    00562        *  is truncated, otherwise the %string is extended and new characters
    00563        *  are default-constructed.  For basic types such as char, this means
    00564        *  setting them to 0.
    00565        */
    00566       void
    00567       resize(size_type __n) { this->resize(__n, _CharT()); }
    00568
    00569       /**
    00570        *  Returns the total number of characters that the %string can hold
    00571        *  before needing to allocate more memory.
    00572        */
    00573       size_type
    00574       capacity() const { return _M_rep()->_M_capacity; }
    00575
    00576       /**
    00577        *  @brief  Attempt to preallocate enough memory for specified number of
    00578        *          characters.
    00579        *  @param  n  Number of characters required.
    00580        *  @throw  std::length_error  If @a n exceeds @c max_size().
    00581        *
    00582        *  This function attempts to reserve enough memory for the
    00583        *  %string to hold the specified number of characters.  If the
    00584        *  number requested is more than max_size(), length_error is
    00585        *  thrown.
    00586        *
    00587        *  The advantage of this function is that if optimal code is a
    00588        *  necessity and the user can determine the string length that will be
    00589        *  required, the user can reserve the memory in %advance, and thus
    00590        *  prevent a possible reallocation of memory and copying of %string
    00591        *  data.
    00592        */
    00593       void
    00594       reserve(size_type __res_arg = 0);
    00595
    00596       /**
    00597        *  Erases the string, making it empty.
    00598        */
    00599       void
    00600       clear() { _M_mutate(0, this->size(), 0); }
    00601
    00602       /**
    00603        *  Returns true if the %string is empty.  Equivalent to *this == "".
    00604        */
    00605       bool
    00606       empty() const { return this->size() == 0; }
    00607
    00608       // Element access:
    00609       /**
    00610        *  @brief  Subscript access to the data contained in the %string.
    00611        *  @param  n  The index of the character to access.
    00612        *  @return  Read-only (constant) reference to the character.
    00613        *
    00614        *  This operator allows for easy, array-style, data access.
    00615        *  Note that data access with this operator is unchecked and
    00616        *  out_of_range lookups are not defined. (For checked lookups
    00617        *  see at().)
    00618        */
    00619       const_reference
    00620       operator[] (size_type __pos) const
    00621       {
    00622     _GLIBCXX_DEBUG_ASSERT(__pos <= size());
    00623     return _M_data()[__pos];
    00624       }
    00625
    00626       /**
    00627        *  @brief  Subscript access to the data contained in the %string.
    00628        *  @param  n  The index of the character to access.
    00629        *  @return  Read/write reference to the character.
    00630        *
    00631        *  This operator allows for easy, array-style, data access.
    00632        *  Note that data access with this operator is unchecked and
    00633        *  out_of_range lookups are not defined. (For checked lookups
    00634        *  see at().)  Unshares the string.
    00635        */
    00636       reference
    00637       operator[](size_type __pos)
    00638       {
    00639     _GLIBCXX_DEBUG_ASSERT(__pos < size());
    00640     _M_leak();
    00641     return _M_data()[__pos];
    00642       }
    00643
    00644       /**
    00645        *  @brief  Provides access to the data contained in the %string.
    00646        *  @param n The index of the character to access.
    00647        *  @return  Read-only (const) reference to the character.
    00648        *  @throw  std::out_of_range  If @a n is an invalid index.
    00649        *
    00650        *  This function provides for safer data access.  The parameter is
    00651        *  first checked that it is in the range of the string.  The function
    00652        *  throws out_of_range if the check fails.
    00653        */
    00654       const_reference
    00655       at(size_type __n) const
    00656       {
    00657     if (__n >= this->size())
    00658       __throw_out_of_range(__N("basic_string::at"));
    00659     return _M_data()[__n];
    00660       }
    00661
    00662       /**
    00663        *  @brief  Provides access to the data contained in the %string.
    00664        *  @param n The index of the character to access.
    00665        *  @return  Read/write reference to the character.
    00666        *  @throw  std::out_of_range  If @a n is an invalid index.
    00667        *
    00668        *  This function provides for safer data access.  The parameter is
    00669        *  first checked that it is in the range of the string.  The function
    00670        *  throws out_of_range if the check fails.  Success results in
    00671        *  unsharing the string.
    00672        */
    00673       reference
    00674       at(size_type __n)
    00675       {
    00676     if (__n >= size())
    00677       __throw_out_of_range(__N("basic_string::at"));
    00678     _M_leak();
    00679     return _M_data()[__n];
    00680       }
    00681
    00682       // Modifiers:
    00683       /**
    00684        *  @brief  Append a string to this string.
    00685        *  @param str  The string to append.
    00686        *  @return  Reference to this string.
    00687        */
    00688       basic_string&
    00689       operator+=(const basic_string& __str) { return this->append(__str); }
    00690
    00691       /**
    00692        *  @brief  Append a C string.
    00693        *  @param s  The C string to append.
    00694        *  @return  Reference to this string.
    00695        */
    00696       basic_string&
    00697       operator+=(const _CharT* __s) { return this->append(__s); }
    00698
    00699       /**
    00700        *  @brief  Append a character.
    00701        *  @param s  The character to append.
    00702        *  @return  Reference to this string.
    00703        */
    00704       basic_string&
    00705       operator+=(_CharT __c) { return this->append(size_type(1), __c); }
    00706
    00707       /**
    00708        *  @brief  Append a string to this string.
    00709        *  @param str  The string to append.
    00710        *  @return  Reference to this string.
    00711        */
    00712       basic_string&
    00713       append(const basic_string& __str);
    00714
    00715       /**
    00716        *  @brief  Append a substring.
    00717        *  @param str  The string to append.
    00718        *  @param pos  Index of the first character of str to append.
    00719        *  @param n  The number of characters to append.
    00720        *  @return  Reference to this string.
    00721        *  @throw  std::out_of_range if @a pos is not a valid index.
    00722        *
    00723        *  This function appends @a n characters from @a str starting at @a pos
    00724        *  to this string.  If @a n is is larger than the number of available
    00725        *  characters in @a str, the remainder of @a str is appended.
    00726        */
    00727       basic_string&
    00728       append(const basic_string& __str, size_type __pos, size_type __n);
    00729
    00730       /**
    00731        *  @brief  Append a C substring.
    00732        *  @param s  The C string to append.
    00733        *  @param n  The number of characters to append.
    00734        *  @return  Reference to this string.
    00735        */
    00736       basic_string&
    00737       append(const _CharT* __s, size_type __n);
    00738
    00739       /**
    00740        *  @brief  Append a C string.
    00741        *  @param s  The C string to append.
    00742        *  @return  Reference to this string.
    00743        */
    00744       basic_string&
    00745       append(const _CharT* __s)
    00746       {
    00747     __glibcxx_requires_string(__s);
    00748     return this->append(__s, traits_type::length(__s));
    00749       }
    00750
    00751       /**
    00752        *  @brief  Append multiple characters.
    00753        *  @param n  The number of characters to append.
    00754        *  @param c  The character to use.
    00755        *  @return  Reference to this string.
    00756        *
    00757        *  Appends n copies of c to this string.
    00758        */
    00759       basic_string&
    00760       append(size_type __n, _CharT __c)
    00761       { return _M_replace_aux(this->size(), size_type(0), __n, __c); }
    00762
    00763       /**
    00764        *  @brief  Append a range of characters.
    00765        *  @param first  Iterator referencing the first character to append.
    00766        *  @param last  Iterator marking the end of the range.
    00767        *  @return  Reference to this string.
    00768        *
    00769        *  Appends characters in the range [first,last) to this string.
    00770        */
    00771       template<class _InputIterator>
    00772         basic_string&
    00773         append(_InputIterator __first, _InputIterator __last)
    00774         { return this->replace(_M_iend(), _M_iend(), __first, __last); }
    00775
    00776       /**
    00777        *  @brief  Append a single character.
    00778        *  @param c  Character to append.
    00779        */
    00780       void
    00781       push_back(_CharT __c)
    00782       { _M_replace_aux(this->size(), size_type(0), size_type(1), __c); }
    00783
    00784       /**
    00785        *  @brief  Set value to contents of another string.
    00786        *  @param  str  Source string to use.
    00787        *  @return  Reference to this string.
    00788        */
    00789       basic_string&
    00790       assign(const basic_string& __str);
    00791
    00792       /**
    00793        *  @brief  Set value to a substring of a string.
    00794        *  @param str  The string to use.
    00795        *  @param pos  Index of the first character of str.
    00796        *  @param n  Number of characters to use.
    00797        *  @return  Reference to this string.
    00798        *  @throw  std::out_of_range if @a pos is not a valid index.
    00799        *
    00800        *  This function sets this string to the substring of @a str consisting
    00801        *  of @a n characters at @a pos.  If @a n is is larger than the number
    00802        *  of available characters in @a str, the remainder of @a str is used.
    00803        */
    00804       basic_string&
    00805       assign(const basic_string& __str, size_type __pos, size_type __n)
    00806       { return this->assign(__str._M_data()
    00807                 + __str._M_check(__pos, "basic_string::assign"),
    00808                 __str._M_limit(__pos, __n)); }
    00809
    00810       /**
    00811        *  @brief  Set value to a C substring.
    00812        *  @param s  The C string to use.
    00813        *  @param n  Number of characters to use.
    00814        *  @return  Reference to this string.
    00815        *
    00816        *  This function sets the value of this string to the first @a n
    00817        *  characters of @a s.  If @a n is is larger than the number of
    00818        *  available characters in @a s, the remainder of @a s is used.
    00819        */
    00820       basic_string&
    00821       assign(const _CharT* __s, size_type __n);
    00822
    00823       /**
    00824        *  @brief  Set value to contents of a C string.
    00825        *  @param s  The C string to use.
    00826        *  @return  Reference to this string.
    00827        *
    00828        *  This function sets the value of this string to the value of @a s.
    00829        *  The data is copied, so there is no dependence on @a s once the
    00830        *  function returns.
    00831        */
    00832       basic_string&
    00833       assign(const _CharT* __s)
    00834       {
    00835     __glibcxx_requires_string(__s);
    00836     return this->assign(__s, traits_type::length(__s));
    00837       }
    00838
    00839       /**
    00840        *  @brief  Set value to multiple characters.
    00841        *  @param n  Length of the resulting string.
    00842        *  @param c  The character to use.
    00843        *  @return  Reference to this string.
    00844        *
    00845        *  This function sets the value of this string to @a n copies of
    00846        *  character @a c.
    00847        */
    00848       basic_string&
    00849       assign(size_type __n, _CharT __c)
    00850       { return _M_replace_aux(size_type(0), this->size(), __n, __c); }
    00851
    00852       /**
    00853        *  @brief  Set value to a range of characters.
    00854        *  @param first  Iterator referencing the first character to append.
    00855        *  @param last  Iterator marking the end of the range.
    00856        *  @return  Reference to this string.
    00857        *
    00858        *  Sets value of string to characters in the range [first,last).
    00859       */
    00860       template<class _InputIterator>
    00861         basic_string&
    00862         assign(_InputIterator __first, _InputIterator __last)
    00863         { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
    00864
    00865       /**
    00866        *  @brief  Insert multiple characters.
    00867        *  @param p  Iterator referencing location in string to insert at.
    00868        *  @param n  Number of characters to insert
    00869        *  @param c  The character to insert.
    00870        *  @throw  std::length_error  If new length exceeds @c max_size().
    00871        *
    00872        *  Inserts @a n copies of character @a c starting at the position
    00873        *  referenced by iterator @a p.  If adding characters causes the length
    00874        *  to exceed max_size(), length_error is thrown.  The value of the
    00875        *  string doesn't change if an error is thrown.
    00876       */
    00877       void
    00878       insert(iterator __p, size_type __n, _CharT __c)
    00879       { this->replace(__p, __p, __n, __c);  }
    00880
    00881       /**
    00882        *  @brief  Insert a range of characters.
    00883        *  @param p  Iterator referencing location in string to insert at.
    00884        *  @param beg  Start of range.
    00885        *  @param end  End of range.
    00886        *  @throw  std::length_error  If new length exceeds @c max_size().
    00887        *
    00888        *  Inserts characters in range [beg,end).  If adding characters causes
    00889        *  the length to exceed max_size(), length_error is thrown.  The value
    00890        *  of the string doesn't change if an error is thrown.
    00891       */
    00892       template<class _InputIterator>
    00893         void insert(iterator __p, _InputIterator __beg, _InputIterator __end)
    00894         { this->replace(__p, __p, __beg, __end); }
    00895
    00896       /**
    00897        *  @brief  Insert value of a string.
    00898        *  @param pos1  Iterator referencing location in string to insert at.
    00899        *  @param str  The string to insert.
    00900        *  @return  Reference to this string.
    00901        *  @throw  std::length_error  If new length exceeds @c max_size().
    00902        *
    00903        *  Inserts value of @a str starting at @a pos1.  If adding characters
    00904        *  causes the length to exceed max_size(), length_error is thrown.  The
    00905        *  value of the string doesn't change if an error is thrown.
    00906       */
    00907       basic_string&
    00908       insert(size_type __pos1, const basic_string& __str)
    00909       { return this->insert(__pos1, __str, size_type(0), __str.size()); }
    00910
    00911       /**
    00912        *  @brief  Insert a substring.
    00913        *  @param pos1  Iterator referencing location in string to insert at.
    00914        *  @param str  The string to insert.
    00915        *  @param pos2  Start of characters in str to insert.
    00916        *  @param n  Number of characters to insert.
    00917        *  @return  Reference to this string.
    00918        *  @throw  std::length_error  If new length exceeds @c max_size().
    00919        *  @throw  std::out_of_range  If @a pos1 > size() or
    00920        *  @a pos2 > @a str.size().
    00921        *
    00922        *  Starting at @a pos1, insert @a n character of @a str beginning with
    00923        *  @a pos2.  If adding characters causes the length to exceed
    00924        *  max_size(), length_error is thrown.  If @a pos1 is beyond the end of
    00925        *  this string or @a pos2 is beyond the end of @a str, out_of_range is
    00926        *  thrown.  The value of the string doesn't change if an error is
    00927        *  thrown.
    00928       */
    00929       basic_string&
    00930       insert(size_type __pos1, const basic_string& __str,
    00931          size_type __pos2, size_type __n)
    00932       { return this->insert(__pos1, __str._M_data()
    00933                 + __str._M_check(__pos2, "basic_string::insert"),
    00934                 __str._M_limit(__pos2, __n)); }
    00935
    00936       /**
    00937        *  @brief  Insert a C substring.
    00938        *  @param pos  Iterator referencing location in string to insert at.
    00939        *  @param s  The C string to insert.
    00940        *  @param n  The number of characters to insert.
    00941        *  @return  Reference to this string.
    00942        *  @throw  std::length_error  If new length exceeds @c max_size().
    00943        *  @throw  std::out_of_range  If @a pos is beyond the end of this
    00944        *  string.
    00945        *
    00946        *  Inserts the first @a n characters of @a s starting at @a pos.  If
    00947        *  adding characters causes the length to exceed max_size(),
    00948        *  length_error is thrown.  If @a pos is beyond end(), out_of_range is
    00949        *  thrown.  The value of the string doesn't change if an error is
    00950        *  thrown.
    00951       */
    00952       basic_string&
    00953       insert(size_type __pos, const _CharT* __s, size_type __n);
    00954
    00955       /**
    00956        *  @brief  Insert a C string.
    00957        *  @param pos  Iterator referencing location in string to insert at.
    00958        *  @param s  The C string to insert.
    00959        *  @return  Reference to this string.
    00960        *  @throw  std::length_error  If new length exceeds @c max_size().
    00961        *  @throw  std::out_of_range  If @a pos is beyond the end of this
    00962        *  string.
    00963        *
    00964        *  Inserts the first @a n characters of @a s starting at @a pos.  If
    00965        *  adding characters causes the length to exceed max_size(),
    00966        *  length_error is thrown.  If @a pos is beyond end(), out_of_range is
    00967        *  thrown.  The value of the string doesn't change if an error is
    00968        *  thrown.
    00969       */
    00970       basic_string&
    00971       insert(size_type __pos, const _CharT* __s)
    00972       {
    00973     __glibcxx_requires_string(__s);
    00974     return this->insert(__pos, __s, traits_type::length(__s));
    00975       }
    00976
    00977       /**
    00978        *  @brief  Insert multiple characters.
    00979        *  @param pos  Index in string to insert at.
    00980        *  @param n  Number of characters to insert
    00981        *  @param c  The character to insert.
    00982        *  @return  Reference to this string.
    00983        *  @throw  std::length_error  If new length exceeds @c max_size().
    00984        *  @throw  std::out_of_range  If @a pos is beyond the end of this
    00985        *  string.
    00986        *
    00987        *  Inserts @a n copies of character @a c starting at index @a pos.  If
    00988        *  adding characters causes the length to exceed max_size(),
    00989        *  length_error is thrown.  If @a pos > length(), out_of_range is
    00990        *  thrown.  The value of the string doesn't change if an error is
    00991        *  thrown.
    00992       */
    00993       basic_string&
    00994       insert(size_type __pos, size_type __n, _CharT __c)
    00995       { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
    00996                   size_type(0), __n, __c); }
    00997
    00998       /**
    00999        *  @brief  Insert one character.
    01000        *  @param p  Iterator referencing position in string to insert at.
    01001        *  @param c  The character to insert.
    01002        *  @return  Iterator referencing newly inserted char.
    01003        *  @throw  std::length_error  If new length exceeds @c max_size().
    01004        *
    01005        *  Inserts character @a c at position referenced by @a p.  If adding
    01006        *  character causes the length to exceed max_size(), length_error is
    01007        *  thrown.  If @a p is beyond end of string, out_of_range is thrown.
    01008        *  The value of the string doesn't change if an error is thrown.
    01009       */
    01010       iterator
    01011       insert(iterator __p, _CharT __c)
    01012       {
    01013     _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
    01014     const size_type __pos = __p - _M_ibegin();
    01015     _M_replace_aux(__pos, size_type(0), size_type(1), __c);
    01016     _M_rep()->_M_set_leaked();
    01017     return this->_M_ibegin() + __pos;
    01018       }
    01019
    01020       /**
    01021        *  @brief  Remove characters.
    01022        *  @param pos  Index of first character to remove (default 0).
    01023        *  @param n  Number of characters to remove (default remainder).
    01024        *  @return  Reference to this string.
    01025        *  @throw  std::out_of_range  If @a pos is beyond the end of this
    01026        *  string.
    01027        *
    01028        *  Removes @a n characters from this string starting at @a pos.  The
    01029        *  length of the string is reduced by @a n.  If there are < @a n
    01030        *  characters to remove, the remainder of the string is truncated.  If
    01031        *  @a p is beyond end of string, out_of_range is thrown.  The value of
    01032        *  the string doesn't change if an error is thrown.
    01033       */
    01034       basic_string&
    01035       erase(size_type __pos = 0, size_type __n = npos)
    01036       { return _M_replace_safe(_M_check(__pos, "basic_string::erase"),
    01037                    _M_limit(__pos, __n), NULL, size_type(0)); }
    01038
    01039       /**
    01040        *  @brief  Remove one character.
    01041        *  @param position  Iterator referencing the character to remove.
    01042        *  @return  iterator referencing same location after removal.
    01043        *
    01044        *  Removes the character at @a position from this string. The value
    01045        *  of the string doesn't change if an error is thrown.
    01046       */
    01047       iterator
    01048       erase(iterator __position)
    01049       {
    01050     _GLIBCXX_DEBUG_PEDASSERT(__position >= _M_ibegin()
    01051                  && __position < _M_iend());
    01052     const size_type __pos = __position - _M_ibegin();
    01053     _M_replace_safe(__pos, size_type(1), NULL, size_type(0));
    01054     _M_rep()->_M_set_leaked();
    01055     return _M_ibegin() + __pos;
    01056       }
    01057
    01058       /**
    01059        *  @brief  Remove a range of characters.
    01060        *  @param first  Iterator referencing the first character to remove.
    01061        *  @param last  Iterator referencing the end of the range.
    01062        *  @return  Iterator referencing location of first after removal.
    01063        *
    01064        *  Removes the characters in the range [first,last) from this string.
    01065        *  The value of the string doesn't change if an error is thrown.
    01066       */
    01067       iterator
    01068       erase(iterator __first, iterator __last)
    01069       {
    01070     _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
    01071                  && __last <= _M_iend());
    01072         const size_type __pos = __first - _M_ibegin();
    01073     _M_replace_safe(__pos, __last - __first, NULL, size_type(0));
    01074     _M_rep()->_M_set_leaked();
    01075     return _M_ibegin() + __pos;
    01076       }
    01077
    01078       /**
    01079        *  @brief  Replace characters with value from another string.
    01080        *  @param pos  Index of first character to replace.
    01081        *  @param n  Number of characters to be replaced.
    01082        *  @param str  String to insert.
    01083        *  @return  Reference to this string.
    01084        *  @throw  std::out_of_range  If @a pos is beyond the end of this
    01085        *  string.
    01086        *  @throw  std::length_error  If new length exceeds @c max_size().
    01087        *
    01088        *  Removes the characters in the range [pos,pos+n) from this string.
    01089        *  In place, the value of @a str is inserted.  If @a pos is beyond end
    01090        *  of string, out_of_range is thrown.  If the length of the result
    01091        *  exceeds max_size(), length_error is thrown.  The value of the string
    01092        *  doesn't change if an error is thrown.
    01093       */
    01094       basic_string&
    01095       replace(size_type __pos, size_type __n, const basic_string& __str)
    01096       { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
    01097
    01098       /**
    01099        *  @brief  Replace characters with value from another string.
    01100        *  @param pos1  Index of first character to replace.
    01101        *  @param n1  Number of characters to be replaced.
    01102        *  @param str  String to insert.
    01103        *  @param pos2  Index of first character of str to use.
    01104        *  @param n2  Number of characters from str to use.
    01105        *  @return  Reference to this string.
    01106        *  @throw  std::out_of_range  If @a pos1 > size() or @a pos2 >
    01107        *  str.size().
    01108        *  @throw  std::length_error  If new length exceeds @c max_size().
    01109        *
    01110        *  Removes the characters in the range [pos1,pos1 + n) from this
    01111        *  string.  In place, the value of @a str is inserted.  If @a pos is
    01112        *  beyond end of string, out_of_range is thrown.  If the length of the
    01113        *  result exceeds max_size(), length_error is thrown.  The value of the
    01114        *  string doesn't change if an error is thrown.
    01115       */
    01116       basic_string&
    01117       replace(size_type __pos1, size_type __n1, const basic_string& __str,
    01118           size_type __pos2, size_type __n2)
    01119       { return this->replace(__pos1, __n1, __str._M_data()
    01120                  + __str._M_check(__pos2, "basic_string::replace"),
    01121                  __str._M_limit(__pos2, __n2)); }
    01122
    01123       /**
    01124        *  @brief  Replace characters with value of a C substring.
    01125        *  @param pos  Index of first character to replace.
    01126        *  @param n1  Number of characters to be replaced.
    01127        *  @param str  C string to insert.
    01128        *  @param n2  Number of characters from str to use.
    01129        *  @return  Reference to this string.
    01130        *  @throw  std::out_of_range  If @a pos1 > size().
    01131        *  @throw  std::length_error  If new length exceeds @c max_size().
    01132        *
    01133        *  Removes the characters in the range [pos,pos + n1) from this string.
    01134        *  In place, the first @a n2 characters of @a str are inserted, or all
    01135        *  of @a str if @a n2 is too large.  If @a pos is beyond end of string,
    01136        *  out_of_range is thrown.  If the length of result exceeds max_size(),
    01137        *  length_error is thrown.  The value of the string doesn't change if
    01138        *  an error is thrown.
    01139       */
    01140       basic_string&
    01141       replace(size_type __pos, size_type __n1, const _CharT* __s,
    01142           size_type __n2);
    01143
    01144       /**
    01145        *  @brief  Replace characters with value of a C string.
    01146        *  @param pos  Index of first character to replace.
    01147        *  @param n1  Number of characters to be replaced.
    01148        *  @param str  C string to insert.
    01149        *  @return  Reference to this string.
    01150        *  @throw  std::out_of_range  If @a pos > size().
    01151        *  @throw  std::length_error  If new length exceeds @c max_size().
    01152        *
    01153        *  Removes the characters in the range [pos,pos + n1) from this string.
    01154        *  In place, the first @a n characters of @a str are inserted.  If @a
    01155        *  pos is beyond end of string, out_of_range is thrown.  If the length
    01156        *  of result exceeds max_size(), length_error is thrown.  The value of
    01157        *  the string doesn't change if an error is thrown.
    01158       */
    01159       basic_string&
    01160       replace(size_type __pos, size_type __n1, const _CharT* __s)
    01161       {
    01162     __glibcxx_requires_string(__s);
    01163     return this->replace(__pos, __n1, __s, traits_type::length(__s));
    01164       }
    01165
    01166       /**
    01167        *  @brief  Replace characters with multiple characters.
    01168        *  @param pos  Index of first character to replace.
    01169        *  @param n1  Number of characters to be replaced.
    01170        *  @param n2  Number of characters to insert.
    01171        *  @param c  Character to insert.
    01172        *  @return  Reference to this string.
    01173        *  @throw  std::out_of_range  If @a pos > size().
    01174        *  @throw  std::length_error  If new length exceeds @c max_size().
    01175        *
    01176        *  Removes the characters in the range [pos,pos + n1) from this string.
    01177        *  In place, @a n2 copies of @a c are inserted.  If @a pos is beyond
    01178        *  end of string, out_of_range is thrown.  If the length of result
    01179        *  exceeds max_size(), length_error is thrown.  The value of the string
    01180        *  doesn't change if an error is thrown.
    01181       */
    01182       basic_string&
    01183       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
    01184       { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
    01185                   _M_limit(__pos, __n1), __n2, __c); }
    01186
    01187       /**
    01188        *  @brief  Replace range of characters with string.
    01189        *  @param i1  Iterator referencing start of range to replace.
    01190        *  @param i2  Iterator referencing end of range to replace.
    01191        *  @param str  String value to insert.
    01192        *  @return  Reference to this string.
    01193        *  @throw  std::length_error  If new length exceeds @c max_size().
    01194        *
    01195        *  Removes the characters in the range [i1,i2).  In place, the value of
    01196        *  @a str is inserted.  If the length of result exceeds max_size(),
    01197        *  length_error is thrown.  The value of the string doesn't change if
    01198        *  an error is thrown.
    01199       */
    01200       basic_string&
    01201       replace(iterator __i1, iterator __i2, const basic_string& __str)
    01202       { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
    01203
    01204       /**
    01205        *  @brief  Replace range of characters with C substring.
    01206        *  @param i1  Iterator referencing start of range to replace.
    01207        *  @param i2  Iterator referencing end of range to replace.
    01208        *  @param s  C string value to insert.
    01209        *  @param n  Number of characters from s to insert.
    01210        *  @return  Reference to this string.
    01211        *  @throw  std::length_error  If new length exceeds @c max_size().
    01212        *
    01213        *  Removes the characters in the range [i1,i2).  In place, the first @a
    01214        *  n characters of @a s are inserted.  If the length of result exceeds
    01215        *  max_size(), length_error is thrown.  The value of the string doesn't
    01216        *  change if an error is thrown.
    01217       */
    01218       basic_string&
    01219       replace(iterator __i1, iterator __i2, const _CharT* __s, size_type __n)
    01220       {
    01221     _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
    01222                  && __i2 <= _M_iend());
    01223     return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n);
    01224       }
    01225
    01226       /**
    01227        *  @brief  Replace range of characters with C string.
    01228        *  @param i1  Iterator referencing start of range to replace.
    01229        *  @param i2  Iterator referencing end of range to replace.
    01230        *  @param s  C string value to insert.
    01231        *  @return  Reference to this string.
    01232        *  @throw  std::length_error  If new length exceeds @c max_size().
    01233        *
    01234        *  Removes the characters in the range [i1,i2).  In place, the
    01235        *  characters of @a s are inserted.  If the length of result exceeds
    01236        *  max_size(), length_error is thrown.  The value of the string doesn't
    01237        *  change if an error is thrown.
    01238       */
    01239       basic_string&
    01240       replace(iterator __i1, iterator __i2, const _CharT* __s)
    01241       {
    01242     __glibcxx_requires_string(__s);
    01243     return this->replace(__i1, __i2, __s, traits_type::length(__s));
    01244       }
    01245
    01246       /**
    01247        *  @brief  Replace range of characters with multiple characters
    01248        *  @param i1  Iterator referencing start of range to replace.
    01249        *  @param i2  Iterator referencing end of range to replace.
    01250        *  @param n  Number of characters to insert.
    01251        *  @param c  Character to insert.
    01252        *  @return  Reference to this string.
    01253        *  @throw  std::length_error  If new length exceeds @c max_size().
    01254        *
    01255        *  Removes the characters in the range [i1,i2).  In place, @a n copies
    01256        *  of @a c are inserted.  If the length of result exceeds max_size(),
    01257        *  length_error is thrown.  The value of the string doesn't change if
    01258        *  an error is thrown.
    01259       */
    01260       basic_string&
    01261       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
    01262       {
    01263     _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
    01264                  && __i2 <= _M_iend());
    01265     return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __c);
    01266       }
    01267
    01268       /**
    01269        *  @brief  Replace range of characters with range.
    01270        *  @param i1  Iterator referencing start of range to replace.
    01271        *  @param i2  Iterator referencing end of range to replace.
    01272        *  @param k1  Iterator referencing start of range to insert.
    01273        *  @param k2  Iterator referencing end of range to insert.
    01274        *  @return  Reference to this string.
    01275        *  @throw  std::length_error  If new length exceeds @c max_size().
    01276        *
    01277        *  Removes the characters in the range [i1,i2).  In place, characters
    01278        *  in the range [k1,k2) are inserted.  If the length of result exceeds
    01279        *  max_size(), length_error is thrown.  The value of the string doesn't
    01280        *  change if an error is thrown.
    01281       */
    01282       template<class _InputIterator>
    01283         basic_string&
    01284         replace(iterator __i1, iterator __i2,
    01285         _InputIterator __k1, _InputIterator __k2)
    01286         {
    01287       _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
    01288                    && __i2 <= _M_iend());
    01289       __glibcxx_requires_valid_range(__k1, __k2);
    01290       typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    01291       return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
    01292     }
    01293
    01294       // Specializations for the common case of pointer and iterator:
    01295       // useful to avoid the overhead of temporary buffering in _M_replace.
    01296       basic_string&
    01297         replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
    01298         {
    01299       _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
    01300                    && __i2 <= _M_iend());
    01301       __glibcxx_requires_valid_range(__k1, __k2);
    01302       return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
    01303                    __k1, __k2 - __k1);
    01304     }
    01305
    01306       basic_string&
    01307         replace(iterator __i1, iterator __i2,
    01308         const _CharT* __k1, const _CharT* __k2)
    01309         {
    01310       _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
    01311                    && __i2 <= _M_iend());
    01312       __glibcxx_requires_valid_range(__k1, __k2);
    01313       return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
    01314                    __k1, __k2 - __k1);
    01315     }
    01316
    01317       basic_string&
    01318         replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
    01319         {
    01320       _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
    01321                    && __i2 <= _M_iend());
    01322       __glibcxx_requires_valid_range(__k1, __k2);
    01323       return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
    01324                    __k1.base(), __k2 - __k1);
    01325     }
    01326
    01327       basic_string&
    01328         replace(iterator __i1, iterator __i2,
    01329         const_iterator __k1, const_iterator __k2)
    01330         {
    01331       _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
    01332                    && __i2 <= _M_iend());
    01333       __glibcxx_requires_valid_range(__k1, __k2);
    01334       return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
    01335                    __k1.base(), __k2 - __k1);
    01336     }
    01337
    01338     private:
    01339       template<class _Integer>
    01340     basic_string&
    01341     _M_replace_dispatch(iterator __i1, iterator __i2, _Integer __n,
    01342                 _Integer __val, __true_type)
    01343         { return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __val); }
    01344
    01345       template<class _InputIterator>
    01346     basic_string&
    01347     _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
    01348                 _InputIterator __k2, __false_type);
    01349
    01350       basic_string&
    01351       _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
    01352              _CharT __c)
    01353       {
    01354     if (this->max_size() - (this->size() - __n1) < __n2)
    01355       __throw_length_error(__N("basic_string::_M_replace_aux"));
    01356     _M_mutate(__pos1, __n1, __n2);
    01357     if (__n2 == 1)
    01358       _M_data()[__pos1] = __c;
    01359     else if (__n2)
    01360       traits_type::assign(_M_data() + __pos1, __n2, __c);
    01361     return *this;
    01362       }
    01363
    01364       basic_string&
    01365       _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
    01366               size_type __n2)
    01367       {
    01368     _M_mutate(__pos1, __n1, __n2);
    01369     if (__n2 == 1)
    01370       _M_data()[__pos1] = *__s;
    01371     else if (__n2)
    01372       traits_type::copy(_M_data() + __pos1, __s, __n2);
    01373     return *this;
    01374       }
    01375
    01376       // _S_construct_aux is used to implement the 21.3.1 para 15 which
    01377       // requires special behaviour if _InIter is an integral type
    01378       template<class _InIterator>
    01379         static _CharT*
    01380         _S_construct_aux(_InIterator __beg, _InIterator __end,
    01381              const _Alloc& __a, __false_type)
    01382     {
    01383           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
    01384           return _S_construct(__beg, __end, __a, _Tag());
    01385     }
    01386
    01387       template<class _InIterator>
    01388         static _CharT*
    01389         _S_construct_aux(_InIterator __beg, _InIterator __end,
    01390              const _Alloc& __a, __true_type)
    01391     { return _S_construct(static_cast<size_type>(__beg),
    01392                   static_cast<value_type>(__end), __a); }
    01393
    01394       template<class _InIterator>
    01395         static _CharT*
    01396         _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
    01397     {
    01398       typedef typename _Is_integer<_InIterator>::_Integral _Integral;
    01399       return _S_construct_aux(__beg, __end, __a, _Integral());
    01400         }
    01401
    01402       // For Input Iterators, used in istreambuf_iterators, etc.
    01403       template<class _InIterator>
    01404         static _CharT*
    01405          _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
    01406               input_iterator_tag);
    01407
    01408       // For forward_iterators up to random_access_iterators, used for
    01409       // string::iterator, _CharT*, etc.
    01410       template<class _FwdIterator>
    01411         static _CharT*
    01412         _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
    01413              forward_iterator_tag);
    01414
    01415       static _CharT*
    01416       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
    01417
    01418     public:
    01419
    01420       /**
    01421        *  @brief  Copy substring into C string.
    01422        *  @param s  C string to copy value into.
    01423        *  @param n  Number of characters to copy.
    01424        *  @param pos  Index of first character to copy.
    01425        *  @return  Number of characters actually copied
    01426        *  @throw  std::out_of_range  If pos > size().
    01427        *
    01428        *  Copies up to @a n characters starting at @a pos into the C string @a
    01429        *  s.  If @a pos is greater than size(), out_of_range is thrown.
    01430       */
    01431       size_type
    01432       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
    01433
    01434       /**
    01435        *  @brief  Swap contents with another string.
    01436        *  @param s  String to swap with.
    01437        *
    01438        *  Exchanges the contents of this string with that of @a s in constant
    01439        *  time.
    01440       */
    01441       void
    01442       swap(basic_string& __s);
    01443
    01444       // String operations:
    01445       /**
    01446        *  @brief  Return const pointer to null-terminated contents.
    01447        *
    01448        *  This is a handle to internal data.  Do not modify or dire things may
    01449        *  happen.
    01450       */
    01451       const _CharT*
    01452       c_str() const { return _M_data(); }
    01453
    01454       /**
    01455        *  @brief  Return const pointer to contents.
    01456        *
    01457        *  This is a handle to internal data.  Do not modify or dire things may
    01458        *  happen.
    01459       */
    01460       const _CharT*
    01461       data() const { return _M_data(); }
    01462
    01463       /**
    01464        *  @brief  Return copy of allocator used to construct this string.
    01465       */
    01466       allocator_type
    01467       get_allocator() const { return _M_dataplus; }
    01468
    01469       /**
    01470        *  @brief  Find position of a C substring.
    01471        *  @param s  C string to locate.
    01472        *  @param pos  Index of character to search from.
    01473        *  @param n  Number of characters from @a s to search for.
    01474        *  @return  Index of start of first occurrence.
    01475        *
    01476        *  Starting from @a pos, searches forward for the first @a n characters
    01477        *  in @a s within this string.  If found, returns the index where it
    01478        *  begins.  If not found, returns npos.
    01479       */
    01480       size_type
    01481       find(const _CharT* __s, size_type __pos, size_type __n) const;
    01482
    01483       /**
    01484        *  @brief  Find position of a string.
    01485        *  @param str  String to locate.
    01486        *  @param pos  Index of character to search from (default 0).
    01487        *  @return  Index of start of first occurrence.
    01488        *
    01489        *  Starting from @a pos, searches forward for value of @a str within
    01490        *  this string.  If found, returns the index where it begins.  If not
    01491        *  found, returns npos.
    01492       */
    01493       size_type
    01494       find(const basic_string& __str, size_type __pos = 0) const
    01495       { return this->find(__str.data(), __pos, __str.size()); }
    01496
    01497       /**
    01498        *  @brief  Find position of a C string.
    01499        *  @param s  C string to locate.
    01500        *  @param pos  Index of character to search from (default 0).
    01501        *  @return  Index of start of first occurrence.
    01502        *
    01503        *  Starting from @a pos, searches forward for the value of @a s within
    01504        *  this string.  If found, returns the index where it begins.  If not
    01505        *  found, returns npos.
    01506       */
    01507       size_type
    01508       find(const _CharT* __s, size_type __pos = 0) const
    01509       {
    01510     __glibcxx_requires_string(__s);
    01511     return this->find(__s, __pos, traits_type::length(__s));
    01512       }
    01513
    01514       /**
    01515        *  @brief  Find position of a character.
    01516        *  @param c  Character to locate.
    01517        *  @param pos  Index of character to search from (default 0).
    01518        *  @return  Index of first occurrence.
    01519        *
    01520        *  Starting from @a pos, searches forward for @a c within this string.
    01521        *  If found, returns the index where it was found.  If not found,
    01522        *  returns npos.
    01523       */
    01524       size_type
    01525       find(_CharT __c, size_type __pos = 0) const;
    01526
    01527       /**
    01528        *  @brief  Find last position of a string.
    01529        *  @param str  String to locate.
    01530        *  @param pos  Index of character to search back from (default end).
    01531        *  @return  Index of start of last occurrence.
    01532        *
    01533        *  Starting from @a pos, searches backward for value of @a str within
    01534        *  this string.  If found, returns the index where it begins.  If not
    01535        *  found, returns npos.
    01536       */
    01537       size_type
    01538       rfind(const basic_string& __str, size_type __pos = npos) const
    01539       { return this->rfind(__str.data(), __pos, __str.size()); }
    01540
    01541       /**
    01542        *  @brief  Find last position of a C substring.
    01543        *  @param s  C string to locate.
    01544        *  @param pos  Index of character to search back from.
    01545        *  @param n  Number of characters from s to search for.
    01546        *  @return  Index of start of last occurrence.
    01547        *
    01548        *  Starting from @a pos, searches backward for the first @a n
    01549        *  characters in @a s within this string.  If found, returns the index
    01550        *  where it begins.  If not found, returns npos.
    01551       */
    01552       size_type
    01553       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
    01554
    01555       /**
    01556        *  @brief  Find last position of a C string.
    01557        *  @param s  C string to locate.
    01558        *  @param pos  Index of character to start search at (default 0).
    01559        *  @return  Index of start of  last occurrence.
    01560        *
    01561        *  Starting from @a pos, searches backward for the value of @a s within
    01562        *  this string.  If found, returns the index where it begins.  If not
    01563        *  found, returns npos.
    01564       */
    01565       size_type
    01566       rfind(const _CharT* __s, size_type __pos = npos) const
    01567       {
    01568     __glibcxx_requires_string(__s);
    01569     return this->rfind(__s, __pos, traits_type::length(__s));
    01570       }
    01571
    01572       /**
    01573        *  @brief  Find last position of a character.
    01574        *  @param c  Character to locate.
    01575        *  @param pos  Index of character to search back from (default 0).
    01576        *  @return  Index of last occurrence.
    01577        *
    01578        *  Starting from @a pos, searches backward for @a c within this string.
    01579        *  If found, returns the index where it was found.  If not found,
    01580        *  returns npos.
    01581       */
    01582       size_type
    01583       rfind(_CharT __c, size_type __pos = npos) const;
    01584
    01585       /**
    01586        *  @brief  Find position of a character of string.
    01587        *  @param str  String containing characters to locate.
    01588        *  @param pos  Index of character to search from (default 0).
    01589        *  @return  Index of first occurrence.
    01590        *
    01591        *  Starting from @a pos, searches forward for one of the characters of
    01592        *  @a str within this string.  If found, returns the index where it was
    01593        *  found.  If not found, returns npos.
    01594       */
    01595       size_type
    01596       find_first_of(const basic_string& __str, size_type __pos = 0) const
    01597       { return this->find_first_of(__str.data(), __pos, __str.size()); }
    01598
    01599       /**
    01600        *  @brief  Find position of a character of C substring.
    01601        *  @param s  String containing characters to locate.
    01602        *  @param pos  Index of character to search from (default 0).
    01603        *  @param n  Number of characters from s to search for.
    01604        *  @return  Index of first occurrence.
    01605        *
    01606        *  Starting from @a pos, searches forward for one of the first @a n
    01607        *  characters of @a s within this string.  If found, returns the index
    01608        *  where it was found.  If not found, returns npos.
    01609       */
    01610       size_type
    01611       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
    01612
    01613       /**
    01614        *  @brief  Find position of a character of C string.
    01615        *  @param s  String containing characters to locate.
    01616        *  @param pos  Index of character to search from (default 0).
    01617        *  @return  Index of first occurrence.
    01618        *
    01619        *  Starting from @a pos, searches forward for one of the characters of
    01620        *  @a s within this string.  If found, returns the index where it was
    01621        *  found.  If not found, returns npos.
    01622       */
    01623       size_type
    01624       find_first_of(const _CharT* __s, size_type __pos = 0) const
    01625       {
    01626     __glibcxx_requires_string(__s);
    01627     return this->find_first_of(__s, __pos, traits_type::length(__s));
    01628       }
    01629
    01630       /**
    01631        *  @brief  Find position of a character.
    01632        *  @param c  Character to locate.
    01633        *  @param pos  Index of character to search from (default 0).
    01634        *  @return  Index of first occurrence.
    01635        *
    01636        *  Starting from @a pos, searches forward for the character @a c within
    01637        *  this string.  If found, returns the index where it was found.  If
    01638        *  not found, returns npos.
    01639        *
    01640        *  Note: equivalent to find(c, pos).
    01641       */
    01642       size_type
    01643       find_first_of(_CharT __c, size_type __pos = 0) const
    01644       { return this->find(__c, __pos); }
    01645
    01646       /**
    01647        *  @brief  Find last position of a character of string.
    01648        *  @param str  String containing characters to locate.
    01649        *  @param pos  Index of character to search back from (default end).
    01650        *  @return  Index of last occurrence.
    01651        *
    01652        *  Starting from @a pos, searches backward for one of the characters of
    01653        *  @a str within this string.  If found, returns the index where it was
    01654        *  found.  If not found, returns npos.
    01655       */
    01656       size_type
    01657       find_last_of(const basic_string& __str, size_type __pos = npos) const
    01658       { return this->find_last_of(__str.data(), __pos, __str.size()); }
    01659
    01660       /**
    01661        *  @brief  Find last position of a character of C substring.
    01662        *  @param s  C string containing characters to locate.
    01663        *  @param pos  Index of character to search back from (default end).
    01664        *  @param n  Number of characters from s to search for.
    01665        *  @return  Index of last occurrence.
    01666        *
    01667        *  Starting from @a pos, searches backward for one of the first @a n
    01668        *  characters of @a s within this string.  If found, returns the index
    01669        *  where it was found.  If not found, returns npos.
    01670       */
    01671       size_type
    01672       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
    01673
    01674       /**
    01675        *  @brief  Find last position of a character of C string.
    01676        *  @param s  C string containing characters to locate.
    01677        *  @param pos  Index of character to search back from (default end).
    01678        *  @return  Index of last occurrence.
    01679        *
    01680        *  Starting from @a pos, searches backward for one of the characters of
    01681        *  @a s within this string.  If found, returns the index where it was
    01682        *  found.  If not found, returns npos.
    01683       */
    01684       size_type
    01685       find_last_of(const _CharT* __s, size_type __pos = npos) const
    01686       {
    01687     __glibcxx_requires_string(__s);
    01688     return this->find_last_of(__s, __pos, traits_type::length(__s));
    01689       }
    01690
    01691       /**
    01692        *  @brief  Find last position of a character.
    01693        *  @param c  Character to locate.
    01694        *  @param pos  Index of character to search back from (default 0).
    01695        *  @return  Index of last occurrence.
    01696        *
    01697        *  Starting from @a pos, searches backward for @a c within this string.
    01698        *  If found, returns the index where it was found.  If not found,
    01699        *  returns npos.
    01700        *
    01701        *  Note: equivalent to rfind(c, pos).
    01702       */
    01703       size_type
    01704       find_last_of(_CharT __c, size_type __pos = npos) const
    01705       { return this->rfind(__c, __pos); }
    01706
    01707       /**
    01708        *  @brief  Find position of a character not in string.
    01709        *  @param str  String containing characters to avoid.
    01710        *  @param pos  Index of character to search from (default 0).
    01711        *  @return  Index of first occurrence.
    01712        *
    01713        *  Starting from @a pos, searches forward for a character not contained
    01714        *  in @a str within this string.  If found, returns the index where it
    01715        *  was found.  If not found, returns npos.
    01716       */
    01717       size_type
    01718       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
    01719       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
    01720
    01721       /**
    01722        *  @brief  Find position of a character not in C substring.
    01723        *  @param s  C string containing characters to avoid.
    01724        *  @param pos  Index of character to search from (default 0).
    01725        *  @param n  Number of characters from s to consider.
    01726        *  @return  Index of first occurrence.
    01727        *
    01728        *  Starting from @a pos, searches forward for a character not contained
    01729        *  in the first @a n characters of @a s within this string.  If found,
    01730        *  returns the index where it was found.  If not found, returns npos.
    01731       */
    01732       size_type
    01733       find_first_not_of(const _CharT* __s, size_type __pos,
    01734             size_type __n) const;
    01735
    01736       /**
    01737        *  @brief  Find position of a character not in C string.
    01738        *  @param s  C string containing characters to avoid.
    01739        *  @param pos  Index of character to search from (default 0).
    01740        *  @return  Index of first occurrence.
    01741        *
    01742        *  Starting from @a pos, searches forward for a character not contained
    01743        *  in @a s within this string.  If found, returns the index where it
    01744        *  was found.  If not found, returns npos.
    01745       */
    01746       size_type
    01747       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
    01748       {
    01749     __glibcxx_requires_string(__s);
    01750     return this->find_first_not_of(__s, __pos, traits_type::length(__s));
    01751       }
    01752
    01753       /**
    01754        *  @brief  Find position of a different character.
    01755        *  @param c  Character to avoid.
    01756        *  @param pos  Index of character to search from (default 0).
    01757        *  @return  Index of first occurrence.
    01758        *
    01759        *  Starting from @a pos, searches forward for a character other than @a c
    01760        *  within this string.  If found, returns the index where it was found.
    01761        *  If not found, returns npos.
    01762       */
    01763       size_type
    01764       find_first_not_of(_CharT __c, size_type __pos = 0) const;
    01765
    01766       /**
    01767        *  @brief  Find last position of a character not in string.
    01768        *  @param str  String containing characters to avoid.
    01769        *  @param pos  Index of character to search from (default 0).
    01770        *  @return  Index of first occurrence.
    01771        *
    01772        *  Starting from @a pos, searches backward for a character not
    01773        *  contained in @a str within this string.  If found, returns the index
    01774        *  where it was found.  If not found, returns npos.
    01775       */
    01776       size_type
    01777       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
    01778       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
    01779
    01780       /**
    01781        *  @brief  Find last position of a character not in C substring.
    01782        *  @param s  C string containing characters to avoid.
    01783        *  @param pos  Index of character to search from (default 0).
    01784        *  @param n  Number of characters from s to consider.
    01785        *  @return  Index of first occurrence.
    01786        *
    01787        *  Starting from @a pos, searches backward for a character not
    01788        *  contained in the first @a n characters of @a s within this string.
    01789        *  If found, returns the index where it was found.  If not found,
    01790        *  returns npos.
    01791       */
    01792       size_type
    01793       find_last_not_of(const _CharT* __s, size_type __pos,
    01794                size_type __n) const;
    01795       /**
    01796        *  @brief  Find position of a character not in C string.
    01797        *  @param s  C string containing characters to avoid.
    01798        *  @param pos  Index of character to search from (default 0).
    01799        *  @return  Index of first occurrence.
    01800        *
    01801        *  Starting from @a pos, searches backward for a character not
    01802        *  contained in @a s within this string.  If found, returns the index
    01803        *  where it was found.  If not found, returns npos.
    01804       */
    01805       size_type
    01806       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
    01807       {
    01808     __glibcxx_requires_string(__s);
    01809     return this->find_last_not_of(__s, __pos, traits_type::length(__s));
    01810       }
    01811
    01812       /**
    01813        *  @brief  Find last position of a different character.
    01814        *  @param c  Character to avoid.
    01815        *  @param pos  Index of character to search from (default 0).
    01816        *  @return  Index of first occurrence.
    01817        *
    01818        *  Starting from @a pos, searches backward for a character other than
    01819        *  @a c within this string.  If found, returns the index where it was
    01820        *  found.  If not found, returns npos.
    01821       */
    01822       size_type
    01823       find_last_not_of(_CharT __c, size_type __pos = npos) const;
    01824
    01825       /**
    01826        *  @brief  Get a substring.
    01827        *  @param pos  Index of first character (default 0).
    01828        *  @param n  Number of characters in substring (default remainder).
    01829        *  @return  The new string.
    01830        *  @throw  std::out_of_range  If pos > size().
    01831        *
    01832        *  Construct and return a new string using the @a n characters starting
    01833        *  at @a pos.  If the string is too short, use the remainder of the
    01834        *  characters.  If @a pos is beyond the end of the string, out_of_range
    01835        *  is thrown.
    01836       */
    01837       basic_string
    01838       substr(size_type __pos = 0, size_type __n = npos) const
    01839       { return basic_string(*this,
    01840                 _M_check(__pos, "basic_string::substr"), __n); }
    01841
    01842       /**
    01843        *  @brief  Compare to a string.
    01844        *  @param str  String to compare against.
    01845        *  @return  Integer < 0, 0, or > 0.
    01846        *
    01847        *  Returns an integer < 0 if this string is ordered before @a str, 0 if
    01848        *  their values are equivalent, or > 0 if this string is ordered after
    01849        *  @a str.  If the lengths of @a str and this string are different, the
    01850        *  shorter one is ordered first.  If they are the same, returns the
    01851        *  result of traits::compare(data(),str.data(),size());
    01852       */
    01853       int
    01854       compare(const basic_string& __str) const
    01855       {
    01856     const size_type __size = this->size();
    01857     const size_type __osize = __str.size();
    01858     const size_type __len = std::min(__size, __osize);
    01859
    01860     int __r = traits_type::compare(_M_data(), __str.data(), __len);
    01861     if (!__r)
    01862       __r =  __size - __osize;
    01863     return __r;
    01864       }
    01865
    01866       /**
    01867        *  @brief  Compare substring to a string.
    01868        *  @param pos  Index of first character of substring.
    01869        *  @param n  Number of characters in substring.
    01870        *  @param str  String to compare against.
    01871        *  @return  Integer < 0, 0, or > 0.
    01872        *
    01873        *  Form the substring of this string from the @a n characters starting
    01874        *  at @a pos.  Returns an integer < 0 if the substring is ordered
    01875        *  before @a str, 0 if their values are equivalent, or > 0 if the
    01876        *  substring is ordered after @a str.  If the lengths @a of str and the
    01877        *  substring are different, the shorter one is ordered first.  If they
    01878        *  are the same, returns the result of
    01879        *  traits::compare(substring.data(),str.data(),size());
    01880       */
    01881       int
    01882       compare(size_type __pos, size_type __n, const basic_string& __str) const;
    01883
    01884       /**
    01885        *  @brief  Compare substring to a substring.
    01886        *  @param pos1  Index of first character of substring.
    01887        *  @param n1  Number of characters in substring.
    01888        *  @param str  String to compare against.
    01889        *  @param pos2  Index of first character of substring of str.
    01890        *  @param n2  Number of characters in substring of str.
    01891        *  @return  Integer < 0, 0, or > 0.
    01892        *
    01893        *  Form the substring of this string from the @a n1 characters starting
    01894        *  at @a pos1.  Form the substring of @a str from the @a n2 characters
    01895        *  starting at @a pos2.  Returns an integer < 0 if this substring is
    01896        *  ordered before the substring of @a str, 0 if their values are
    01897        *  equivalent, or > 0 if this substring is ordered after the substring
    01898        *  of @a str.  If the lengths of the substring of @a str and this
    01899        *  substring are different, the shorter one is ordered first.  If they
    01900        *  are the same, returns the result of
    01901        *  traits::compare(substring.data(),str.substr(pos2,n2).data(),size());
    01902       */
    01903       int
    01904       compare(size_type __pos1, size_type __n1, const basic_string& __str,
    01905           size_type __pos2, size_type __n2) const;
    01906
    01907       /**
    01908        *  @brief  Compare to a C string.
    01909        *  @param s  C string to compare against.
    01910        *  @return  Integer < 0, 0, or > 0.
    01911        *
    01912        *  Returns an integer < 0 if this string is ordered before @a s, 0 if
    01913        *  their values are equivalent, or > 0 if this string is ordered after
    01914        *  @a s.  If the lengths of @a s and this string are different, the
    01915        *  shorter one is ordered first.  If they are the same, returns the
    01916        *  result of traits::compare(data(),s,size());
    01917       */
    01918       int
    01919       compare(const _CharT* __s) const;
    01920
    01921       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    01922       // 5 String::compare specification questionable
    01923       /**
    01924        *  @brief  Compare substring to a C string.
    01925        *  @param pos  Index of first character of substring.
    01926        *  @param n1  Number of characters in substring.
    01927        *  @param s  C string to compare against.
    01928        *  @return  Integer < 0, 0, or > 0.
    01929        *
    01930        *  Form the substring of this string from the @a n1 characters starting
    01931        *  at @a pos.  Returns an integer < 0 if the substring is ordered
    01932        *  before @a s, 0 if their values are equivalent, or > 0 if the
    01933        *  substring is ordered after @a s.  If the lengths of @a s and the
    01934        *  substring are different, the shorter one is ordered first.  If they
    01935        *  are the same, returns the result of
    01936        *  traits::compare(substring.data(),s,size());
    01937       */
    01938       int
    01939       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
    01940
    01941       /**
    01942        *  @brief  Compare substring against a character array.
    01943        *  @param pos1  Index of first character of substring.
    01944        *  @param n1  Number of characters in substring.
    01945        *  @param s  character array to compare against.
    01946        *  @param n2  Number of characters of s.
    01947        *  @return  Integer < 0, 0, or > 0.
    01948        *
    01949        *  Form the substring of this string from the @a n1 characters starting
    01950        *  at @a pos1.  Form a string from the first @a n2 characters of @a s.
    01951        *  Returns an integer < 0 if this substring is ordered before the string
    01952        *  from @a s, 0 if their values are equivalent, or > 0 if this substring
    01953        *  is ordered after the string from @a s. If the lengths of this
    01954        *  substring and @a n2 are different, the shorter one is ordered first.
    01955        *  If they are the same, returns the result of
    01956        *  traits::compare(substring.data(),s,size());
    01957        *
    01958        *  NB: s must have at least n2 characters, '\0' has no special
    01959        *  meaning.
    01960       */
    01961       int
    01962       compare(size_type __pos, size_type __n1, const _CharT* __s,
    01963           size_type __n2) const;
    01964   };
    01965
    01966
    01967   template<typename _CharT, typename _Traits, typename _Alloc>
    01968     inline basic_string<_CharT, _Traits, _Alloc>::
    01969     basic_string()
    01970     : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
    01971
    01972   // operator+
    01973   /**
    01974    *  @brief  Concatenate two strings.
    01975    *  @param lhs  First string.
    01976    *  @param rhs  Last string.
    01977    *  @return  New string with value of @a lhs followed by @a rhs.
    01978    */
    01979   template<typename _CharT, typename _Traits, typename _Alloc>
    01980     basic_string<_CharT, _Traits, _Alloc>
    01981     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    01982           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    01983     {
    01984       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
    01985       __str.append(__rhs);
    01986       return __str;
    01987     }
    01988
    01989   /**
    01990    *  @brief  Concatenate C string and string.
    01991    *  @param lhs  First string.
    01992    *  @param rhs  Last string.
    01993    *  @return  New string with value of @a lhs followed by @a rhs.
    01994    */
    01995   template<typename _CharT, typename _Traits, typename _Alloc>
    01996     basic_string<_CharT,_Traits,_Alloc>
    01997     operator+(const _CharT* __lhs,
    01998           const basic_string<_CharT,_Traits,_Alloc>& __rhs);
    01999
    02000   /**
    02001    *  @brief  Concatenate character and string.
    02002    *  @param lhs  First string.
    02003    *  @param rhs  Last string.
    02004    *  @return  New string with @a lhs followed by @a rhs.
    02005    */
    02006   template<typename _CharT, typename _Traits, typename _Alloc>
    02007     basic_string<_CharT,_Traits,_Alloc>
    02008     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
    02009
    02010   /**
    02011    *  @brief  Concatenate string and C string.
    02012    *  @param lhs  First string.
    02013    *  @param rhs  Last string.
    02014    *  @return  New string with @a lhs followed by @a rhs.
    02015    */
    02016   template<typename _CharT, typename _Traits, typename _Alloc>
    02017     inline basic_string<_CharT, _Traits, _Alloc>
    02018     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02019          const _CharT* __rhs)
    02020     {
    02021       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
    02022       __str.append(__rhs);
    02023       return __str;
    02024     }
    02025
    02026   /**
    02027    *  @brief  Concatenate string and character.
    02028    *  @param lhs  First string.
    02029    *  @param rhs  Last string.
    02030    *  @return  New string with @a lhs followed by @a rhs.
    02031    */
    02032   template<typename _CharT, typename _Traits, typename _Alloc>
    02033     inline basic_string<_CharT, _Traits, _Alloc>
    02034     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
    02035     {
    02036       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
    02037       typedef typename __string_type::size_type     __size_type;
    02038       __string_type __str(__lhs);
    02039       __str.append(__size_type(1), __rhs);
    02040       return __str;
    02041     }
    02042
    02043   // operator ==
    02044   /**
    02045    *  @brief  Test equivalence of two strings.
    02046    *  @param lhs  First string.
    02047    *  @param rhs  Second string.
    02048    *  @return  True if @a lhs.compare(@a rhs) == 0.  False otherwise.
    02049    */
    02050   template<typename _CharT, typename _Traits, typename _Alloc>
    02051     inline bool
    02052     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02053            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02054     { return __lhs.compare(__rhs) == 0; }
    02055
    02056   /**
    02057    *  @brief  Test equivalence of C string and string.
    02058    *  @param lhs  C string.
    02059    *  @param rhs  String.
    02060    *  @return  True if @a rhs.compare(@a lhs) == 0.  False otherwise.
    02061    */
    02062   template<typename _CharT, typename _Traits, typename _Alloc>
    02063     inline bool
    02064     operator==(const _CharT* __lhs,
    02065            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02066     { return __rhs.compare(__lhs) == 0; }
    02067
    02068   /**
    02069    *  @brief  Test equivalence of string and C string.
    02070    *  @param lhs  String.
    02071    *  @param rhs  C string.
    02072    *  @return  True if @a lhs.compare(@a rhs) == 0.  False otherwise.
    02073    */
    02074   template<typename _CharT, typename _Traits, typename _Alloc>
    02075     inline bool
    02076     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02077            const _CharT* __rhs)
    02078     { return __lhs.compare(__rhs) == 0; }
    02079
    02080   // operator !=
    02081   /**
    02082    *  @brief  Test difference of two strings.
    02083    *  @param lhs  First string.
    02084    *  @param rhs  Second string.
    02085    *  @return  True if @a lhs.compare(@a rhs) != 0.  False otherwise.
    02086    */
    02087   template<typename _CharT, typename _Traits, typename _Alloc>
    02088     inline bool
    02089     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02090            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02091     { return __rhs.compare(__lhs) != 0; }
    02092
    02093   /**
    02094    *  @brief  Test difference of C string and string.
    02095    *  @param lhs  C string.
    02096    *  @param rhs  String.
    02097    *  @return  True if @a rhs.compare(@a lhs) != 0.  False otherwise.
    02098    */
    02099   template<typename _CharT, typename _Traits, typename _Alloc>
    02100     inline bool
    02101     operator!=(const _CharT* __lhs,
    02102            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02103     { return __rhs.compare(__lhs) != 0; }
    02104
    02105   /**
    02106    *  @brief  Test difference of string and C string.
    02107    *  @param lhs  String.
    02108    *  @param rhs  C string.
    02109    *  @return  True if @a lhs.compare(@a rhs) != 0.  False otherwise.
    02110    */
    02111   template<typename _CharT, typename _Traits, typename _Alloc>
    02112     inline bool
    02113     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02114            const _CharT* __rhs)
    02115     { return __lhs.compare(__rhs) != 0; }
    02116
    02117   // operator <
    02118   /**
    02119    *  @brief  Test if string precedes string.
    02120    *  @param lhs  First string.
    02121    *  @param rhs  Second string.
    02122    *  @return  True if @a lhs precedes @a rhs.  False otherwise.
    02123    */
    02124   template<typename _CharT, typename _Traits, typename _Alloc>
    02125     inline bool
    02126     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02127           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02128     { return __lhs.compare(__rhs) < 0; }
    02129
    02130   /**
    02131    *  @brief  Test if string precedes C string.
    02132    *  @param lhs  String.
    02133    *  @param rhs  C string.
    02134    *  @return  True if @a lhs precedes @a rhs.  False otherwise.
    02135    */
    02136   template<typename _CharT, typename _Traits, typename _Alloc>
    02137     inline bool
    02138     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02139           const _CharT* __rhs)
    02140     { return __lhs.compare(__rhs) < 0; }
    02141
    02142   /**
    02143    *  @brief  Test if C string precedes string.
    02144    *  @param lhs  C string.
    02145    *  @param rhs  String.
    02146    *  @return  True if @a lhs precedes @a rhs.  False otherwise.
    02147    */
    02148   template<typename _CharT, typename _Traits, typename _Alloc>
    02149     inline bool
    02150     operator<(const _CharT* __lhs,
    02151           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02152     { return __rhs.compare(__lhs) > 0; }
    02153
    02154   // operator >
    02155   /**
    02156    *  @brief  Test if string follows string.
    02157    *  @param lhs  First string.
    02158    *  @param rhs  Second string.
    02159    *  @return  True if @a lhs follows @a rhs.  False otherwise.
    02160    */
    02161   template<typename _CharT, typename _Traits, typename _Alloc>
    02162     inline bool
    02163     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02164           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02165     { return __lhs.compare(__rhs) > 0; }
    02166
    02167   /**
    02168    *  @brief  Test if string follows C string.
    02169    *  @param lhs  String.
    02170    *  @param rhs  C string.
    02171    *  @return  True if @a lhs follows @a rhs.  False otherwise.
    02172    */
    02173   template<typename _CharT, typename _Traits, typename _Alloc>
    02174     inline bool
    02175     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02176           const _CharT* __rhs)
    02177     { return __lhs.compare(__rhs) > 0; }
    02178
    02179   /**
    02180    *  @brief  Test if C string follows string.
    02181    *  @param lhs  C string.
    02182    *  @param rhs  String.
    02183    *  @return  True if @a lhs follows @a rhs.  False otherwise.
    02184    */
    02185   template<typename _CharT, typename _Traits, typename _Alloc>
    02186     inline bool
    02187     operator>(const _CharT* __lhs,
    02188           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02189     { return __rhs.compare(__lhs) < 0; }
    02190
    02191   // operator <=
    02192   /**
    02193    *  @brief  Test if string doesn't follow string.
    02194    *  @param lhs  First string.
    02195    *  @param rhs  Second string.
    02196    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
    02197    */
    02198   template<typename _CharT, typename _Traits, typename _Alloc>
    02199     inline bool
    02200     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02201            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02202     { return __lhs.compare(__rhs) <= 0; }
    02203
    02204   /**
    02205    *  @brief  Test if string doesn't follow C string.
    02206    *  @param lhs  String.
    02207    *  @param rhs  C string.
    02208    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
    02209    */
    02210   template<typename _CharT, typename _Traits, typename _Alloc>
    02211     inline bool
    02212     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02213            const _CharT* __rhs)
    02214     { return __lhs.compare(__rhs) <= 0; }
    02215
    02216   /**
    02217    *  @brief  Test if C string doesn't follow string.
    02218    *  @param lhs  C string.
    02219    *  @param rhs  String.
    02220    *  @return  True if @a lhs doesn't follow @a rhs.  False otherwise.
    02221    */
    02222   template<typename _CharT, typename _Traits, typename _Alloc>
    02223     inline bool
    02224     operator<=(const _CharT* __lhs,
    02225            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02226   { return __rhs.compare(__lhs) >= 0; }
    02227
    02228   // operator >=
    02229   /**
    02230    *  @brief  Test if string doesn't precede string.
    02231    *  @param lhs  First string.
    02232    *  @param rhs  Second string.
    02233    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
    02234    */
    02235   template<typename _CharT, typename _Traits, typename _Alloc>
    02236     inline bool
    02237     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02238            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02239     { return __lhs.compare(__rhs) >= 0; }
    02240
    02241   /**
    02242    *  @brief  Test if string doesn't precede C string.
    02243    *  @param lhs  String.
    02244    *  @param rhs  C string.
    02245    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
    02246    */
    02247   template<typename _CharT, typename _Traits, typename _Alloc>
    02248     inline bool
    02249     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02250            const _CharT* __rhs)
    02251     { return __lhs.compare(__rhs) >= 0; }
    02252
    02253   /**
    02254    *  @brief  Test if C string doesn't precede string.
    02255    *  @param lhs  C string.
    02256    *  @param rhs  String.
    02257    *  @return  True if @a lhs doesn't precede @a rhs.  False otherwise.
    02258    */
    02259   template<typename _CharT, typename _Traits, typename _Alloc>
    02260     inline bool
    02261     operator>=(const _CharT* __lhs,
    02262          const basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02263     { return __rhs.compare(__lhs) <= 0; }
    02264
    02265   /**
    02266    *  @brief  Swap contents of two strings.
    02267    *  @param lhs  First string.
    02268    *  @param rhs  Second string.
    02269    *
    02270    *  Exchanges the contents of @a lhs and @a rhs in constant time.
    02271    */
    02272   template<typename _CharT, typename _Traits, typename _Alloc>
    02273     inline void
    02274     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
    02275      basic_string<_CharT, _Traits, _Alloc>& __rhs)
    02276     { __lhs.swap(__rhs); }
    02277
    02278   /**
    02279    *  @brief  Read stream into a string.
    02280    *  @param is  Input stream.
    02281    *  @param str  Buffer to store into.
    02282    *  @return  Reference to the input stream.
    02283    *
    02284    *  Stores characters from @a is into @a str until whitespace is found, the
    02285    *  end of the stream is encountered, or str.max_size() is reached.  If
    02286    *  is.width() is non-zero, that is the limit on the number of characters
    02287    *  stored into @a str.  Any previous contents of @a str are erased.
    02288    */
    02289   template<typename _CharT, typename _Traits, typename _Alloc>
    02290     basic_istream<_CharT, _Traits>&
    02291     operator>>(basic_istream<_CharT, _Traits>& __is,
    02292            basic_string<_CharT, _Traits, _Alloc>& __str);
    02293
    02294   /**
    02295    *  @brief  Write string to a stream.
    02296    *  @param os  Output stream.
    02297    *  @param str  String to write out.
    02298    *  @return  Reference to the output stream.
    02299    *
    02300    *  Output characters of @a str into os following the same rules as for
    02301    *  writing a C string.
    02302    */
    02303   template<typename _CharT, typename _Traits, typename _Alloc>
    02304     basic_ostream<_CharT, _Traits>&
    02305     operator<<(basic_ostream<_CharT, _Traits>& __os,
    02306            const basic_string<_CharT, _Traits, _Alloc>& __str);
    02307
    02308   /**
    02309    *  @brief  Read a line from stream into a string.
    02310    *  @param is  Input stream.
    02311    *  @param str  Buffer to store into.
    02312    *  @param delim  Character marking end of line.
    02313    *  @return  Reference to the input stream.
    02314    *
    02315    *  Stores characters from @a is into @a str until @a delim is found, the
    02316    *  end of the stream is encountered, or str.max_size() is reached.  If
    02317    *  is.width() is non-zero, that is the limit on the number of characters
    02318    *  stored into @a str.  Any previous contents of @a str are erased.  If @a
    02319    *  delim was encountered, it is extracted but not stored into @a str.
    02320    */
    02321   template<typename _CharT, typename _Traits, typename _Alloc>
    02322     basic_istream<_CharT,_Traits>&
    02323     getline(basic_istream<_CharT, _Traits>& __is,
    02324         basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
    02325
    02326   /**
    02327    *  @brief  Read a line from stream into a string.
    02328    *  @param is  Input stream.
    02329    *  @param str  Buffer to store into.
    02330    *  @return  Reference to the input stream.
    02331    *
    02332    *  Stores characters from is into @a str until '\n' is found, the end of
    02333    *  the stream is encountered, or str.max_size() is reached.  If is.width()
    02334    *  is non-zero, that is the limit on the number of characters stored into
    02335    *  @a str.  Any previous contents of @a str are erased.  If end of line was
    02336    *  encountered, it is extracted but not stored into @a str.
    02337    */
    02338   template<typename _CharT, typename _Traits, typename _Alloc>
    02339     inline basic_istream<_CharT,_Traits>&
    02340     getline(basic_istream<_CharT, _Traits>& __is,
    02341         basic_string<_CharT, _Traits, _Alloc>& __str);
    02342 } // namespace std
    02343
    02344 #endif /* _BASIC_STRING_H */