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
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 2, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // You should have received a copy of the GNU General Public License along
00018 // with this library; see the file COPYING.  If not, write to the Free
00019 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
00020 // USA.
00021 
00022 // As a special exception, you may use this file as part of a free software
00023 // library without restriction.  Specifically, if other files instantiate
00024 // templates or use macros or inline functions from this file, or you compile
00025 // this file and link it with other files to produce an executable, this
00026 // file does not by itself cause the resulting executable to be covered by
00027 // the GNU General Public License.  This exception does not however
00028 // invalidate any other reasons why the executable file might be covered by
00029 // the GNU General Public License.
00030 
00031 //
00032 // ISO C++ 14882: 21 Strings library
00033 //
00034 
00040 #ifndef _CPP_BITS_STRING_H
00041 #define _CPP_BITS_STRING_H  1
00042 
00043 #pragma GCC system_header
00044 
00045 #include <bits/atomicity.h>
00046 
00047 namespace std
00048 {
00049   // Documentation?  What's that? 
00050   // Nathan Myers <ncm@cantrip.org>.
00051   //
00052   // A string looks like this:
00053   //
00054   //                                [_Rep]
00055   //                                _M_length
00056   //  [basic_string<char_type>]     _M_capacity
00057   //  _M_dataplus                   _M_state
00058   //  _M_p ---------------->        unnamed array of char_type
00059   
00060   // Where the _M_p points to the first character in the string, and
00061   // you cast it to a pointer-to-_Rep and subtract 1 to get a
00062   // pointer to the header.
00063   
00064   // This approach has the enormous advantage that a string object
00065   // requires only one allocation.  All the ugliness is confined
00066   // within a single pair of inline functions, which each compile to
00067   // a single "add" instruction: _Rep::_M_data(), and
00068   // string::_M_rep(); and the allocation function which gets a
00069   // block of raw bytes and with room enough and constructs a _Rep
00070   // object at the front.
00071   
00072   // The reason you want _M_data pointing to the character array and
00073   // not the _Rep is so that the debugger can see the string
00074   // contents. (Probably we should add a non-inline member to get
00075   // the _Rep for the debugger to use, so users can check the actual
00076   // string length.)
00077   
00078   // Note that the _Rep object is a POD so that you can have a
00079   // static "empty string" _Rep object already "constructed" before
00080   // static constructors have run.  The reference-count encoding is
00081   // chosen so that a 0 indicates one reference, so you never try to
00082   // destroy the empty-string _Rep object.
00083   
00084   // All but the last paragraph is considered pretty conventional
00085   // for a C++ string implementation.
00086   
00087   // 21.3  Template class basic_string
00088   template<typename _CharT, typename _Traits, typename _Alloc>
00089     class basic_string
00090     {
00091       // Types:
00092     public:
00093       typedef _Traits                       traits_type;
00094       typedef typename _Traits::char_type           value_type;
00095       typedef _Alloc                        allocator_type;
00096       typedef typename _Alloc::size_type            size_type;
00097       typedef typename _Alloc::difference_type          difference_type;
00098       typedef typename _Alloc::reference            reference;
00099       typedef typename _Alloc::const_reference          const_reference;
00100       typedef typename _Alloc::pointer              pointer;
00101       typedef typename _Alloc::const_pointer            const_pointer;
00102       typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
00103       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
00104                                                             const_iterator;
00105       typedef reverse_iterator<const_iterator>  const_reverse_iterator;
00106       typedef reverse_iterator<iterator>            reverse_iterator;
00107     
00108     private:
00109       // _Rep: string representation
00110       //   Invariants:
00111       //   1. String really contains _M_length + 1 characters; last is set
00112       //      to 0 only on call to c_str().  We avoid instantiating
00113       //      _CharT() where the interface does not require it.
00114       //   2. _M_capacity >= _M_length
00115       //      Allocated memory is always _M_capacity + (1 * sizeof(_CharT)).
00116       //   3. _M_references has three states:
00117       //      -1: leaked, one reference, no ref-copies allowed, non-const.
00118       //       0: one reference, non-const.
00119       //     n>0: n + 1 references, operations require a lock, const.
00120       //   4. All fields==0 is an empty string, given the extra storage
00121       //      beyond-the-end for a null terminator; thus, the shared
00122       //      empty string representation needs no constructor.
00123       struct _Rep
00124       {
00125     // Types:
00126     typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
00127 
00128     // (Public) Data members: 
00129 
00130     // The maximum number of individual char_type elements of an
00131     // individual string is determined by _S_max_size. This is the
00132     // value that will be returned by max_size().  (Whereas npos
00133     // is the maximum number of bytes the allocator can allocate.)
00134     // If one was to divvy up the theoretical largest size string,
00135     // with a terminating character and m _CharT elements, it'd
00136     // look like this: 
00137     // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
00138     // Solving for m:
00139     // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1 
00140     // In addition, this implementation quarters this ammount.
00141     static const size_type  _S_max_size;
00142     static const _CharT     _S_terminal;
00143 
00144     size_type       _M_length;
00145     size_type       _M_capacity;
00146     _Atomic_word        _M_references;
00147     
00148         bool
00149     _M_is_leaked() const
00150         { return _M_references < 0; }
00151 
00152         bool
00153     _M_is_shared() const
00154         { return _M_references > 0; }
00155 
00156         void
00157     _M_set_leaked() 
00158         { _M_references = -1; }
00159 
00160         void
00161     _M_set_sharable() 
00162         { _M_references = 0; }
00163 
00164     _CharT* 
00165     _M_refdata() throw()
00166     { return reinterpret_cast<_CharT*>(this + 1); }
00167 
00168     _CharT& 
00169     operator[](size_t __s) throw()
00170     { return _M_refdata() [__s]; }
00171 
00172     _CharT* 
00173     _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
00174     { 
00175       return (!_M_is_leaked() && __alloc1 == __alloc2) 
00176               ? _M_refcopy() : _M_clone(__alloc1);  
00177     }
00178 
00179     // Create & Destroy
00180     static _Rep* 
00181     _S_create(size_t, const _Alloc&);
00182 
00183     void 
00184     _M_dispose(const _Alloc& __a)
00185     { 
00186       if (__exchange_and_add(&_M_references, -1) <= 0)  
00187         _M_destroy(__a); 
00188     }  // XXX MT
00189 
00190     void 
00191     _M_destroy(const _Alloc&) throw();
00192 
00193     _CharT* 
00194     _M_refcopy() throw()
00195     { 
00196       __atomic_add(&_M_references, 1); 
00197       return _M_refdata(); 
00198     }  // XXX MT
00199 
00200     _CharT* 
00201     _M_clone(const _Alloc&, size_type __res = 0);
00202       };
00203 
00204       // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
00205       struct _Alloc_hider : _Alloc
00206       {
00207     _Alloc_hider(_CharT* __dat, const _Alloc& __a)
00208     : _Alloc(__a), _M_p(__dat) { }
00209 
00210     _CharT* _M_p; // The actual data.
00211       };
00212 
00213     public:
00214       // Data Members (public):
00215       // NB: This is an unsigned type, and thus represents the maximum
00216       // size that the allocator can hold.
00217       static const size_type    npos = static_cast<size_type>(-1);
00218 
00219     private:
00220       // Data Members (private):
00221       mutable _Alloc_hider  _M_dataplus;
00222 
00223       // The following storage is init'd to 0 by the linker, resulting
00224       // (carefully) in an empty string with one reference.
00225       static size_type _S_empty_rep_storage[(sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
00226 
00227       _CharT* 
00228       _M_data() const 
00229       { return  _M_dataplus._M_p; }
00230 
00231       _CharT* 
00232       _M_data(_CharT* __p) 
00233       { return (_M_dataplus._M_p = __p); }
00234 
00235       _Rep* 
00236       _M_rep() const
00237       { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
00238 
00239       // For the internal use we have functions similar to `begin'/`end'
00240       // but they do not call _M_leak.
00241       iterator 
00242       _M_ibegin() const { return iterator(_M_data()); }
00243 
00244       iterator 
00245       _M_iend() const { return iterator(_M_data() + this->size()); }
00246 
00247       void 
00248       _M_leak()    // for use in begin() & non-const op[]
00249       { 
00250     if (!_M_rep()->_M_is_leaked()) 
00251       _M_leak_hard(); 
00252       }
00253 
00254       iterator 
00255       _M_check(size_type __pos) const
00256       { 
00257     if (__pos > this->size())
00258       __throw_out_of_range("basic_string::_M_check"); 
00259     return _M_ibegin() + __pos; 
00260       }
00261 
00262       // NB: _M_fold doesn't check for a bad __pos1 value.
00263       iterator 
00264       _M_fold(size_type __pos, size_type __off) const
00265       { 
00266     bool __testoff =  __off < this->size() - __pos;
00267     size_type __newoff = __testoff ? __off : this->size() - __pos;
00268     return (_M_ibegin() + __pos + __newoff);
00269       }
00270 
00271       // _S_copy_chars is a separate template to permit specialization
00272       // to optimize for the common case of pointers as iterators.
00273       template<class _Iterator>
00274         static void
00275         _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
00276         { 
00277       for (; __k1 != __k2; ++__k1, ++__p) 
00278         traits_type::assign(*__p, *__k1); // These types are off.
00279     }
00280 
00281       static void
00282       _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2)
00283       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
00284 
00285       static void
00286       _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
00287       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
00288  
00289       static void
00290       _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2)
00291       { traits_type::copy(__p, __k1, __k2 - __k1); }
00292 
00293       static void
00294       _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
00295       { traits_type::copy(__p, __k1, __k2 - __k1); }
00296 
00297       void 
00298       _M_mutate(size_type __pos, size_type __len1, size_type __len2);
00299 
00300       void 
00301       _M_leak_hard();
00302 
00303       static _Rep& 
00304       _S_empty_rep()
00305       { return *reinterpret_cast<_Rep*>(&_S_empty_rep_storage); }
00306 
00307     public:
00308       // Construct/copy/destroy:
00309       // NB: We overload ctors in some cases instead of using default
00310       // arguments, per 17.4.4.4 para. 2 item 2.
00311 
00312       inline 
00313       basic_string();
00314 
00315       explicit 
00316       basic_string(const _Alloc& __a);
00317 
00318       // NB: per LWG issue 42, semantics different from IS:
00319       basic_string(const basic_string& __str);
00320       basic_string(const basic_string& __str, size_type __pos,
00321            size_type __n = npos);
00322       basic_string(const basic_string& __str, size_type __pos,
00323            size_type __n, const _Alloc& __a);
00324 
00325       basic_string(const _CharT* __s, size_type __n,
00326            const _Alloc& __a = _Alloc());
00327       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
00328       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
00329 
00330       template<class _InputIterator>
00331         basic_string(_InputIterator __beg, _InputIterator __end,
00332              const _Alloc& __a = _Alloc());
00333 
00334       ~basic_string() 
00335       { _M_rep()->_M_dispose(this->get_allocator()); }
00336 
00337       basic_string& 
00338       operator=(const basic_string& __str) { return this->assign(__str); }
00339 
00340       basic_string& 
00341       operator=(const _CharT* __s) { return this->assign(__s); }
00342 
00343       basic_string& 
00344       operator=(_CharT __c) { return this->assign(1, __c); }
00345 
00346       // Iterators:
00347       iterator 
00348       begin() 
00349       { 
00350     _M_leak(); 
00351     return iterator(_M_data());
00352       }
00353 
00354       const_iterator 
00355       begin() const 
00356       { return const_iterator(_M_data()); }
00357 
00358       iterator 
00359       end()
00360       {
00361          _M_leak();
00362      return iterator(_M_data() + this->size());
00363       }
00364 
00365       const_iterator 
00366       end() const
00367       { return const_iterator(_M_data() + this->size()); }
00368 
00369       reverse_iterator 
00370       rbegin() 
00371       { return reverse_iterator(this->end()); }
00372 
00373       const_reverse_iterator 
00374       rbegin() const 
00375       { return const_reverse_iterator(this->end()); }
00376 
00377       reverse_iterator 
00378       rend() 
00379       { return reverse_iterator(this->begin()); }
00380 
00381       const_reverse_iterator 
00382       rend() const 
00383       { return const_reverse_iterator(this->begin()); }
00384 
00385     public:
00386       // Capacity:
00387       size_type 
00388       size() const { return _M_rep()->_M_length; }
00389 
00390       size_type 
00391       length() const { return _M_rep()->_M_length; }
00392 
00393       size_type 
00394       max_size() const { return _Rep::_S_max_size; }
00395 
00396       void 
00397       resize(size_type __n, _CharT __c);
00398 
00399       void 
00400       resize(size_type __n) { this->resize(__n, _CharT()); }
00401 
00402       size_type 
00403       capacity() const { return _M_rep()->_M_capacity; }
00404 
00405       void 
00406       reserve(size_type __res_arg = 0);
00407 
00408       void 
00409       clear() { _M_mutate(0, this->size(), 0); }
00410 
00411       bool 
00412       empty() const { return this->size() == 0; }
00413 
00414       // Element access:
00415       const_reference 
00416       operator[] (size_type __pos) const 
00417       { return _M_data()[__pos]; }
00418 
00419       reference 
00420       operator[](size_type __pos) 
00421       { 
00422     _M_leak(); 
00423     return _M_data()[__pos]; 
00424       }
00425 
00426       const_reference 
00427       at(size_type __n) const
00428       {
00429     if (__n >= this->size())
00430       __throw_out_of_range("basic_string::at");
00431     return _M_data()[__n]; 
00432       }
00433 
00434       reference 
00435       at(size_type __n)
00436       {
00437     if (__n >= size())
00438       __throw_out_of_range("basic_string::at");
00439     _M_leak(); 
00440     return _M_data()[__n]; 
00441       }
00442 
00443       // Modifiers:
00444       basic_string& 
00445       operator+=(const basic_string& __str) { return this->append(__str); }
00446 
00447       basic_string& 
00448       operator+=(const _CharT* __s) { return this->append(__s); }
00449 
00450       basic_string& 
00451       operator+=(_CharT __c) { return this->append(size_type(1), __c); }
00452 
00453       basic_string& 
00454       append(const basic_string& __str);
00455 
00456       basic_string& 
00457       append(const basic_string& __str, size_type __pos, size_type __n);
00458 
00459       basic_string& 
00460       append(const _CharT* __s, size_type __n);
00461 
00462       basic_string& 
00463       append(const _CharT* __s)
00464       { return this->append(__s, traits_type::length(__s)); }
00465 
00466       basic_string& 
00467       append(size_type __n, _CharT __c);
00468 
00469       template<class _InputIterator>
00470         basic_string& 
00471         append(_InputIterator __first, _InputIterator __last)
00472         { return this->replace(_M_iend(), _M_iend(), __first, __last); }
00473 
00474       void 
00475       push_back(_CharT __c)
00476       { this->replace(_M_iend(), _M_iend(), 1, __c); }
00477 
00478       basic_string& 
00479       assign(const basic_string& __str);
00480 
00481       basic_string& 
00482       assign(const basic_string& __str, size_type __pos, size_type __n)
00483       {
00484     const size_type __strsize = __str.size();
00485     if (__pos > __strsize)
00486       __throw_out_of_range("basic_string::assign");
00487     const bool __testn = __n < __strsize - __pos;
00488     const size_type __newsize = __testn ? __n : __strsize - __pos;
00489     return this->assign(__str._M_data() + __pos, __newsize);
00490       }
00491 
00492       basic_string& 
00493       assign(const _CharT* __s, size_type __n)
00494       {
00495     if (__n > this->max_size())
00496       __throw_length_error("basic_string::assign");
00497     if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
00498         || less<const _CharT*>()(_M_data() + this->size(), __s))
00499       return _M_replace_safe(_M_ibegin(), _M_iend(), __s, __s + __n);
00500     else
00501       {
00502         // Work in-place
00503         const size_type __pos = __s - _M_data();
00504         if (__pos >= __n)
00505           traits_type::copy(_M_data(), __s, __n);
00506         else if (__pos)
00507           traits_type::move(_M_data(), __s, __n);
00508         _M_rep()->_M_length = __n;
00509         _M_data()[__n] = _Rep::_S_terminal;
00510         return *this;
00511       }
00512       }
00513 
00514       basic_string& 
00515       assign(const _CharT* __s)
00516       { return this->assign(__s, traits_type::length(__s)); }
00517 
00518       basic_string& 
00519       assign(size_type __n, _CharT __c)
00520       { return this->replace(_M_ibegin(), _M_iend(), __n, __c); }
00521 
00522       template<class _InputIterator>
00523         basic_string& 
00524         assign(_InputIterator __first, _InputIterator __last)
00525         { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
00526 
00527       void 
00528       insert(iterator __p, size_type __n, _CharT __c)
00529       { this->replace(__p, __p, __n, __c);  }
00530 
00531       template<class _InputIterator>
00532         void insert(iterator __p, _InputIterator __beg, _InputIterator __end)
00533         { this->replace(__p, __p, __beg, __end); }
00534 
00535       basic_string& 
00536       insert(size_type __pos1, const basic_string& __str)
00537       { return this->insert(__pos1, __str, 0, __str.size()); }
00538 
00539       basic_string& 
00540       insert(size_type __pos1, const basic_string& __str,
00541          size_type __pos2, size_type __n)
00542       {
00543     const size_type __strsize = __str.size();
00544     if (__pos2 > __strsize)
00545       __throw_out_of_range("basic_string::insert");
00546     const bool __testn = __n < __strsize - __pos2;
00547     const size_type __newsize = __testn ? __n : __strsize - __pos2;
00548     return this->insert(__pos1, __str._M_data() + __pos2, __newsize); 
00549       }
00550 
00551       basic_string& 
00552       insert(size_type __pos, const _CharT* __s, size_type __n)
00553       {
00554     const size_type __size = this->size();
00555     if (__pos > __size)
00556       __throw_out_of_range("basic_string::insert");
00557     if (__size > this->max_size() - __n)
00558       __throw_length_error("basic_string::insert");
00559     if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
00560         || less<const _CharT*>()(_M_data() + __size, __s))
00561       return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos,
00562                  __s, __s + __n);
00563     else
00564       {
00565         // Work in-place. If _M_mutate reallocates the string, __s
00566         // does not point anymore to valid data, therefore we save its
00567         // offset, then we restore it.
00568         const size_type __off = __s - _M_data();
00569         _M_mutate(__pos, 0, __n);
00570         __s = _M_data() + __off;
00571         _CharT* __p = _M_data() + __pos;
00572         if (__s  + __n <= __p)
00573           traits_type::copy(__p, __s, __n);
00574         else if (__s >= __p)
00575           traits_type::copy(__p, __s + __n, __n);
00576         else
00577           {
00578         traits_type::copy(__p, __s, __p - __s);
00579         traits_type::copy(__p + (__p - __s), __p + __n, __n - (__p - __s));
00580           }
00581         return *this;
00582       }
00583        }
00584 
00585       basic_string&  
00586       insert(size_type __pos, const _CharT* __s)
00587       { return this->insert(__pos, __s, traits_type::length(__s)); }
00588 
00589       basic_string& 
00590       insert(size_type __pos, size_type __n, _CharT __c)
00591       { 
00592     this->insert(_M_check(__pos), __n, __c); 
00593     return *this; 
00594       }
00595 
00596       iterator 
00597       insert(iterator __p, _CharT __c = _CharT())
00598       {
00599     size_type __pos = __p - _M_ibegin();
00600     this->insert(_M_check(__pos), size_type(1), __c);
00601     _M_rep()->_M_set_leaked(); 
00602     return this->_M_ibegin() + __pos; 
00603       }
00604 
00605       basic_string& 
00606       erase(size_type __pos = 0, size_type __n = npos)
00607       { 
00608     return this->replace(_M_check(__pos), _M_fold(__pos, __n),
00609                  _M_data(), _M_data()); 
00610       }
00611 
00612       iterator 
00613       erase(iterator __position)
00614       {
00615     size_type __i = __position - _M_ibegin();
00616         this->replace(__position, __position + 1, _M_data(), _M_data());
00617     _M_rep()->_M_set_leaked(); 
00618     return _M_ibegin() + __i;
00619       }
00620 
00621       iterator 
00622       erase(iterator __first, iterator __last)
00623       {
00624         size_type __i = __first - _M_ibegin();
00625     this->replace(__first, __last, _M_data(), _M_data());
00626     _M_rep()->_M_set_leaked();
00627        return _M_ibegin() + __i;
00628       }
00629 
00630       basic_string& 
00631       replace(size_type __pos, size_type __n, const basic_string& __str)
00632       { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
00633 
00634       basic_string& 
00635       replace(size_type __pos1, size_type __n1, const basic_string& __str,
00636           size_type __pos2, size_type __n2);
00637 
00638       basic_string& 
00639       replace(size_type __pos, size_type __n1, const _CharT* __s,
00640           size_type __n2)
00641       { 
00642     const size_type __size = this->size();
00643     if (__pos > __size)
00644       __throw_out_of_range("basic_string::replace");
00645     const bool __testn1 = __n1 < __size - __pos;
00646     const size_type __foldn1 = __testn1 ? __n1 : __size - __pos;
00647     if (__size - __foldn1 > this->max_size() - __n2)
00648       __throw_length_error("basic_string::replace");
00649     if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
00650         || less<const _CharT*>()(_M_data() + __size, __s))
00651       return _M_replace_safe(_M_ibegin() + __pos,
00652                  _M_ibegin() + __pos + __foldn1, __s, __s + __n2);  
00653     // Todo: optimized in-place replace.
00654     else return
00655            _M_replace(_M_ibegin() + __pos, _M_ibegin() + __pos + __foldn1,
00656               __s, __s + __n2,
00657               typename iterator_traits<const _CharT*>::iterator_category());
00658       }
00659 
00660       basic_string& 
00661       replace(size_type __pos, size_type __n1, const _CharT* __s)
00662       { return this->replace(__pos, __n1, __s, traits_type::length(__s)); }
00663 
00664       basic_string& 
00665       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
00666       { return this->replace(_M_check(__pos), _M_fold(__pos, __n1), __n2, __c); }
00667 
00668       basic_string& 
00669       replace(iterator __i1, iterator __i2, const basic_string& __str)
00670       { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
00671 
00672       basic_string& 
00673       replace(iterator __i1, iterator __i2,
00674                            const _CharT* __s, size_type __n)
00675       { return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n); }
00676 
00677       basic_string& 
00678       replace(iterator __i1, iterator __i2, const _CharT* __s)
00679       { return this->replace(__i1, __i2, __s, traits_type::length(__s)); }
00680 
00681       basic_string& 
00682       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c);
00683 
00684       template<class _InputIterator>
00685         basic_string& 
00686         replace(iterator __i1, iterator __i2,
00687         _InputIterator __k1, _InputIterator __k2)
00688         { return _M_replace(__i1, __i2, __k1, __k2,
00689          typename iterator_traits<_InputIterator>::iterator_category()); }
00690 
00691       // Specializations for the common case of pointer and iterator:
00692       // useful to avoid the overhead of temporary buffering in _M_replace.
00693       basic_string& 
00694       replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
00695         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
00696                    __k1, __k2 - __k1); }
00697 
00698       basic_string& 
00699       replace(iterator __i1, iterator __i2, const _CharT* __k1, const _CharT* __k2)
00700         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
00701                    __k1, __k2 - __k1); }
00702 
00703       basic_string& 
00704       replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
00705         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
00706                    __k1.base(), __k2 - __k1);
00707     }
00708 
00709       basic_string& 
00710       replace(iterator __i1, iterator __i2, const_iterator __k1, const_iterator __k2)
00711         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
00712                    __k1.base(), __k2 - __k1);
00713     }
00714 
00715     private:
00716       template<class _InputIterator>
00717         basic_string& 
00718         _M_replace(iterator __i1, iterator __i2, _InputIterator __k1, 
00719            _InputIterator __k2, input_iterator_tag);
00720 
00721       template<class _ForwardIterator>
00722         basic_string& 
00723         _M_replace_safe(iterator __i1, iterator __i2, _ForwardIterator __k1, 
00724            _ForwardIterator __k2);
00725 
00726       // _S_construct_aux is used to implement the 21.3.1 para 15 which
00727       // requires special behaviour if _InIter is an integral type
00728       template<class _InIter>
00729         static _CharT*
00730         _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a,
00731              __false_type)
00732     {
00733           typedef typename iterator_traits<_InIter>::iterator_category _Tag;
00734           return _S_construct(__beg, __end, __a, _Tag());
00735     }
00736  
00737       template<class _InIter>
00738         static _CharT*
00739         _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a,
00740              __true_type)
00741     {
00742       return _S_construct(static_cast<size_type>(__beg),
00743                   static_cast<value_type>(__end), __a);
00744     }
00745  
00746       template<class _InIter>
00747         static _CharT*
00748         _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a)
00749     {
00750       typedef typename _Is_integer<_InIter>::_Integral _Integral;
00751       return _S_construct_aux(__beg, __end, __a, _Integral());
00752         }
00753 
00754       // For Input Iterators, used in istreambuf_iterators, etc.
00755       template<class _InIter>
00756         static _CharT*
00757          _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
00758               input_iterator_tag);
00759       
00760       // For forward_iterators up to random_access_iterators, used for
00761       // string::iterator, _CharT*, etc.
00762       template<class _FwdIter>
00763         static _CharT*
00764         _S_construct(_FwdIter __beg, _FwdIter __end, const _Alloc& __a,
00765              forward_iterator_tag);
00766 
00767       static _CharT* 
00768       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
00769 
00770     public:
00771 
00772       size_type 
00773       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
00774 
00775       void 
00776       swap(basic_string<_CharT, _Traits, _Alloc>& __s);
00777 
00778       // String operations:
00779       const _CharT* 
00780       c_str() const
00781       {
00782     // MT: This assumes concurrent writes are OK.
00783     size_type __n = this->size();
00784     traits_type::assign(_M_data()[__n], _Rep::_S_terminal);
00785         return _M_data();
00786       }
00787 
00788       const _CharT* 
00789       data() const { return _M_data(); }
00790 
00791       allocator_type 
00792       get_allocator() const { return _M_dataplus; }
00793 
00794       size_type 
00795       find(const _CharT* __s, size_type __pos, size_type __n) const;
00796 
00797       size_type 
00798       find(const basic_string& __str, size_type __pos = 0) const
00799       { return this->find(__str.data(), __pos, __str.size()); }
00800 
00801       size_type 
00802       find(const _CharT* __s, size_type __pos = 0) const
00803       { return this->find(__s, __pos, traits_type::length(__s)); }
00804 
00805       size_type 
00806       find(_CharT __c, size_type __pos = 0) const;
00807 
00808       size_type 
00809       rfind(const basic_string& __str, size_type __pos = npos) const
00810       { return this->rfind(__str.data(), __pos, __str.size()); }
00811 
00812       size_type 
00813       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
00814 
00815       size_type 
00816       rfind(const _CharT* __s, size_type __pos = npos) const
00817       { return this->rfind(__s, __pos, traits_type::length(__s)); }
00818 
00819       size_type 
00820       rfind(_CharT __c, size_type __pos = npos) const;
00821 
00822       size_type 
00823       find_first_of(const basic_string& __str, size_type __pos = 0) const
00824       { return this->find_first_of(__str.data(), __pos, __str.size()); }
00825 
00826       size_type 
00827       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
00828 
00829       size_type 
00830       find_first_of(const _CharT* __s, size_type __pos = 0) const
00831       { return this->find_first_of(__s, __pos, traits_type::length(__s)); }
00832 
00833       size_type 
00834       find_first_of(_CharT __c, size_type __pos = 0) const
00835       { return this->find(__c, __pos); }
00836 
00837       size_type 
00838       find_last_of(const basic_string& __str, size_type __pos = npos) const
00839       { return this->find_last_of(__str.data(), __pos, __str.size()); }
00840 
00841       size_type 
00842       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
00843 
00844       size_type 
00845       find_last_of(const _CharT* __s, size_type __pos = npos) const
00846       { return this->find_last_of(__s, __pos, traits_type::length(__s)); }
00847 
00848       size_type 
00849       find_last_of(_CharT __c, size_type __pos = npos) const
00850       { return this->rfind(__c, __pos); }
00851 
00852       size_type 
00853       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
00854       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
00855 
00856       size_type 
00857       find_first_not_of(const _CharT* __s, size_type __pos, 
00858             size_type __n) const;
00859 
00860       size_type 
00861       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
00862       { return this->find_first_not_of(__s, __pos, traits_type::length(__s)); }
00863 
00864       size_type 
00865       find_first_not_of(_CharT __c, size_type __pos = 0) const;
00866 
00867       size_type 
00868       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
00869       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
00870 
00871       size_type 
00872       find_last_not_of(const _CharT* __s, size_type __pos, 
00873                size_type __n) const;
00874       size_type 
00875       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
00876       { return this->find_last_not_of(__s, __pos, traits_type::length(__s)); }
00877 
00878       size_type 
00879       find_last_not_of(_CharT __c, size_type __pos = npos) const;
00880 
00881       basic_string 
00882       substr(size_type __pos = 0, size_type __n = npos) const
00883       { 
00884     if (__pos > this->size())
00885       __throw_out_of_range("basic_string::substr");
00886     return basic_string(*this, __pos, __n); 
00887       }
00888 
00889       int 
00890       compare(const basic_string& __str) const
00891       {
00892     size_type __size = this->size();
00893     size_type __osize = __str.size();
00894     size_type __len = min(__size, __osize);
00895       
00896     int __r = traits_type::compare(_M_data(), __str.data(), __len);
00897     if (!__r)
00898       __r =  __size - __osize;
00899     return __r;
00900       }
00901 
00902       int 
00903       compare(size_type __pos, size_type __n, const basic_string& __str) const;
00904 
00905       int 
00906       compare(size_type __pos1, size_type __n1, const basic_string& __str,
00907           size_type __pos2, size_type __n2) const;
00908 
00909       int 
00910       compare(const _CharT* __s) const;
00911 
00912       // _GLIBCPP_RESOLVE_LIB_DEFECTS
00913       // 5. String::compare specification questionable
00914       int 
00915       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
00916 
00917       int 
00918       compare(size_type __pos, size_type __n1, const _CharT* __s, 
00919           size_type __n2) const;
00920   };
00921 
00922 
00923   template<typename _CharT, typename _Traits, typename _Alloc>
00924     inline basic_string<_CharT, _Traits, _Alloc>::
00925     basic_string()
00926     : _M_dataplus(_S_empty_rep()._M_refcopy(), _Alloc()) { }
00927 
00928   // operator+
00929   template<typename _CharT, typename _Traits, typename _Alloc>
00930     basic_string<_CharT, _Traits, _Alloc>
00931     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
00932           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
00933     {
00934       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
00935       __str.append(__rhs);
00936       return __str;
00937     }
00938 
00939   template<typename _CharT, typename _Traits, typename _Alloc>
00940     basic_string<_CharT,_Traits,_Alloc>
00941     operator+(const _CharT* __lhs,
00942           const basic_string<_CharT,_Traits,_Alloc>& __rhs);
00943 
00944   template<typename _CharT, typename _Traits, typename _Alloc>
00945     basic_string<_CharT,_Traits,_Alloc>
00946     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
00947 
00948   template<typename _CharT, typename _Traits, typename _Alloc>
00949     inline basic_string<_CharT, _Traits, _Alloc>
00950     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
00951          const _CharT* __rhs)
00952     {
00953       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
00954       __str.append(__rhs);
00955       return __str;
00956     }
00957 
00958   template<typename _CharT, typename _Traits, typename _Alloc>
00959     inline basic_string<_CharT, _Traits, _Alloc>
00960     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
00961     {
00962       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
00963       typedef typename __string_type::size_type     __size_type;
00964       __string_type __str(__lhs);
00965       __str.append(__size_type(1), __rhs);
00966       return __str;
00967     }
00968 
00969   // operator ==
00970   template<typename _CharT, typename _Traits, typename _Alloc>
00971     inline bool
00972     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
00973            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
00974     { return __lhs.compare(__rhs) == 0; }
00975 
00976   template<typename _CharT, typename _Traits, typename _Alloc>
00977     inline bool
00978     operator==(const _CharT* __lhs,
00979            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
00980     { return __rhs.compare(__lhs) == 0; }
00981 
00982   template<typename _CharT, typename _Traits, typename _Alloc>
00983     inline bool
00984     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
00985            const _CharT* __rhs)
00986     { return __lhs.compare(__rhs) == 0; }
00987 
00988   // operator !=
00989   template<typename _CharT, typename _Traits, typename _Alloc>
00990     inline bool
00991     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
00992            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
00993     { return __rhs.compare(__lhs) != 0; }
00994 
00995   template<typename _CharT, typename _Traits, typename _Alloc>
00996     inline bool
00997     operator!=(const _CharT* __lhs,
00998            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
00999     { return __rhs.compare(__lhs) != 0; }
01000 
01001   template<typename _CharT, typename _Traits, typename _Alloc>
01002     inline bool
01003     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
01004            const _CharT* __rhs)
01005     { return __lhs.compare(__rhs) != 0; }
01006 
01007   // operator <
01008   template<typename _CharT, typename _Traits, typename _Alloc>
01009     inline bool
01010     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
01011           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01012     { return __lhs.compare(__rhs) < 0; }
01013 
01014   template<typename _CharT, typename _Traits, typename _Alloc>
01015     inline bool
01016     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
01017           const _CharT* __rhs)
01018     { return __lhs.compare(__rhs) < 0; }
01019 
01020   template<typename _CharT, typename _Traits, typename _Alloc>
01021     inline bool
01022     operator<(const _CharT* __lhs,
01023           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01024     { return __rhs.compare(__lhs) > 0; }
01025 
01026   // operator >
01027   template<typename _CharT, typename _Traits, typename _Alloc>
01028     inline bool
01029     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
01030           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01031     { return __lhs.compare(__rhs) > 0; }
01032 
01033   template<typename _CharT, typename _Traits, typename _Alloc>
01034     inline bool
01035     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
01036           const _CharT* __rhs)
01037     { return __lhs.compare(__rhs) > 0; }
01038 
01039   template<typename _CharT, typename _Traits, typename _Alloc>
01040     inline bool
01041     operator>(const _CharT* __lhs,
01042           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01043     { return __rhs.compare(__lhs) < 0; }
01044 
01045   // operator <=
01046   template<typename _CharT, typename _Traits, typename _Alloc>
01047     inline bool
01048     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
01049            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01050     { return __lhs.compare(__rhs) <= 0; }
01051 
01052   template<typename _CharT, typename _Traits, typename _Alloc>
01053     inline bool
01054     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
01055            const _CharT* __rhs)
01056     { return __lhs.compare(__rhs) <= 0; }
01057 
01058   template<typename _CharT, typename _Traits, typename _Alloc>
01059     inline bool
01060     operator<=(const _CharT* __lhs,
01061            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01062   { return __rhs.compare(__lhs) >= 0; }
01063 
01064   // operator >=
01065   template<typename _CharT, typename _Traits, typename _Alloc>
01066     inline bool
01067     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
01068            const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01069     { return __lhs.compare(__rhs) >= 0; }
01070 
01071   template<typename _CharT, typename _Traits, typename _Alloc>
01072     inline bool
01073     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
01074            const _CharT* __rhs)
01075     { return __lhs.compare(__rhs) >= 0; }
01076 
01077   template<typename _CharT, typename _Traits, typename _Alloc>
01078     inline bool
01079     operator>=(const _CharT* __lhs,
01080          const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01081     { return __rhs.compare(__lhs) <= 0; }
01082 
01083 
01084   template<typename _CharT, typename _Traits, typename _Alloc>
01085     inline void
01086     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
01087      basic_string<_CharT, _Traits, _Alloc>& __rhs)
01088     { __lhs.swap(__rhs); }
01089 
01090   template<typename _CharT, typename _Traits, typename _Alloc>
01091     basic_istream<_CharT, _Traits>&
01092     operator>>(basic_istream<_CharT, _Traits>& __is,
01093            basic_string<_CharT, _Traits, _Alloc>& __str);
01094 
01095   template<typename _CharT, typename _Traits, typename _Alloc>
01096     basic_ostream<_CharT, _Traits>&
01097     operator<<(basic_ostream<_CharT, _Traits>& __os,
01098            const basic_string<_CharT, _Traits, _Alloc>& __str);
01099 
01100   template<typename _CharT, typename _Traits, typename _Alloc>
01101     basic_istream<_CharT,_Traits>&
01102     getline(basic_istream<_CharT, _Traits>& __is,
01103         basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
01104 
01105   template<typename _CharT, typename _Traits, typename _Alloc>
01106     inline basic_istream<_CharT,_Traits>&
01107     getline(basic_istream<_CharT, _Traits>& __is,
01108         basic_string<_CharT, _Traits, _Alloc>& __str);
01109 } // namespace std
01110 
01111 #endif /* _CPP_BITS_STRING_H */

Generated on Tue Dec 23 12:33:00 2003 for libstdc++-v3 Source by doxygen 1.3.4