basic_string.h

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

Generated on Thu Nov 1 13:11:19 2007 for libstdc++ by  doxygen 1.5.1