libstdc++-v3/include/bits/basic_string.tcc

   1 // Components for manipulating sequences of characters -*- C++ -*-
   2
   3 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 //
  32 // ISO C++ 14882: 21  Strings library
  33 //
  34
  35 // This file is included by <string>.  It is not meant to be included
  36 // separately.
  37
  38 // Written by Jason Merrill based upon the specification by Takanori Adachi
  39 // in ANSI X3J16/94-0013R2.  Rewritten by Nathan Myers to ISO-14882.
  40
  41 #ifndef _CPP_BITS_STRING_TCC
  42 #define _CPP_BITS_STRING_TCC 1
  43
  44 namespace std
  45 {
  46   template<typename _CharT, typename _Traits, typename _Alloc>
  47     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
  48     basic_string<_CharT, _Traits, _Alloc>::
  49     _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4;
  50
  51   template<typename _CharT, typename _Traits, typename _Alloc>
  52     const _CharT
  53     basic_string<_CharT, _Traits, _Alloc>::
  54     _Rep::_S_terminal = _CharT();
  55
  56   template<typename _CharT, typename _Traits, typename _Alloc>
  57     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
  58     basic_string<_CharT, _Traits, _Alloc>::npos;
  59
  60   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
  61   // at static init time (before static ctors are run).
  62   template<typename _CharT, typename _Traits, typename _Alloc>
  63     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  64     basic_string<_CharT, _Traits, _Alloc>::_S_empty_rep_storage[
  65     (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
  66
  67   // NB: This is the special case for Input Iterators, used in
  68   // istreambuf_iterators, etc.
  69   // Input Iterators have a cost structure very different from
  70   // pointers, calling for a different coding style.
  71   template<typename _CharT, typename _Traits, typename _Alloc>
  72     template<typename _InIter>
  73       _CharT*
  74       basic_string<_CharT, _Traits, _Alloc>::
  75       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
  76                    input_iterator_tag)
  77       {
  78         if (__beg == __end && __a == _Alloc())
  79           return _S_empty_rep()._M_refcopy();
  80         // Avoid reallocation for common case.
  81         _CharT __buf[100];
  82         size_type __i = 0;
  83         while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT))
  84           {
  85             __buf[__i++] = *__beg;
  86             ++__beg;
  87           }
  88         _Rep* __r = _Rep::_S_create(__i, __a);
  89         traits_type::copy(__r->_M_refdata(), __buf, __i);
  90         __r->_M_length = __i;
  91         try
  92           {
  93             // NB: this loop looks precisely this way because
  94             // it avoids comparing __beg != __end any more
  95             // than strictly necessary; != might be expensive!
  96             for (;;)
  97               {
  98                 _CharT* __p = __r->_M_refdata() + __r->_M_length;
  99                 _CharT* __last = __r->_M_refdata() + __r->_M_capacity;
 100                 for (;;)
 101                   {
 102                     if (__beg == __end)
 103                       {
 104                         __r->_M_length = __p - __r->_M_refdata();
 105                         *__p = _Rep::_S_terminal;       // grrr.
 106                         return __r->_M_refdata();
 107                       }
 108                     if (__p == __last)
 109                       break;
 110                     *__p++ = *__beg;
 111                     ++__beg;
 112                   }
 113                 // Allocate more space.
 114                 size_type __len = __p - __r->_M_refdata();
 115                 _Rep* __another = _Rep::_S_create(__len + 1, __a);
 116                 traits_type::copy(__another->_M_refdata(),
 117                                   __r->_M_refdata(), __len);
 118                 __r->_M_destroy(__a);
 119                 __r = __another;
 120                 __r->_M_length = __len;
 121               }
 122           }
 123         catch(...)
 124           {
 125             __r->_M_destroy(__a);
 126             __throw_exception_again;
 127           }
 128         return 0;
 129       }
 130
 131   template<typename _CharT, typename _Traits, typename _Alloc>
 132     template <class _InIter>
 133       _CharT*
 134       basic_string<_CharT, _Traits, _Alloc>::
 135       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
 136                    forward_iterator_tag)
 137       {
 138         size_type __dnew = static_cast<size_type>(distance(__beg, __end));
 139
 140         if (__beg == __end && __a == _Alloc())
 141           return _S_empty_rep()._M_refcopy();
 142
 143         // Check for out_of_range and length_error exceptions.
 144         _Rep* __r = _Rep::_S_create(__dnew, __a);
 145         try
 146           { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
 147         catch(...)
 148           {
 149             __r->_M_destroy(__a);
 150             __throw_exception_again;
 151           }
 152         __r->_M_length = __dnew;
 153
 154         __r->_M_refdata()[__dnew] = _Rep::_S_terminal;  // grrr.
 155         return __r->_M_refdata();
 156       }
 157
 158   template<typename _CharT, typename _Traits, typename _Alloc>
 159     _CharT*
 160     basic_string<_CharT, _Traits, _Alloc>::
 161     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
 162     {
 163       if (__n == 0 && __a == _Alloc())
 164         return _S_empty_rep()._M_refcopy();
 165
 166       // Check for out_of_range and length_error exceptions.
 167       _Rep* __r = _Rep::_S_create(__n, __a);
 168       try
 169         {
 170           if (__n)
 171             traits_type::assign(__r->_M_refdata(), __n, __c);
 172         }
 173       catch(...)
 174         {
 175           __r->_M_destroy(__a);
 176           __throw_exception_again;
 177         }
 178       __r->_M_length = __n;
 179       __r->_M_refdata()[__n] = _Rep::_S_terminal;  // grrr
 180       return __r->_M_refdata();
 181     }
 182
 183   template<typename _CharT, typename _Traits, typename _Alloc>
 184     basic_string<_CharT, _Traits, _Alloc>::
 185     basic_string(const basic_string& __str)
 186     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()),
 187                  __str.get_allocator())
 188     { }
 189
 190   template<typename _CharT, typename _Traits, typename _Alloc>
 191     basic_string<_CharT, _Traits, _Alloc>::
 192     basic_string(const _Alloc& __a)
 193     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
 194     { }
 195
 196   template<typename _CharT, typename _Traits, typename _Alloc>
 197     basic_string<_CharT, _Traits, _Alloc>::
 198     basic_string(const basic_string& __str, size_type __pos, size_type __n)
 199     : _M_dataplus(_S_construct(__str._M_check(__pos),
 200                                __str._M_fold(__pos, __n), _Alloc()), _Alloc())
 201     { }
 202
 203   template<typename _CharT, typename _Traits, typename _Alloc>
 204     basic_string<_CharT, _Traits, _Alloc>::
 205     basic_string(const basic_string& __str, size_type __pos,
 206                  size_type __n, const _Alloc& __a)
 207     : _M_dataplus(_S_construct(__str._M_check(__pos),
 208                                __str._M_fold(__pos, __n), __a), __a)
 209     { }
 210
 211   template<typename _CharT, typename _Traits, typename _Alloc>
 212     basic_string<_CharT, _Traits, _Alloc>::
 213     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
 214     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
 215     { }
 216
 217   template<typename _CharT, typename _Traits, typename _Alloc>
 218     basic_string<_CharT, _Traits, _Alloc>::
 219     basic_string(const _CharT* __s, const _Alloc& __a)
 220     : _M_dataplus(_S_construct(__s, __s + traits_type::length(__s), __a), __a)
 221     { }
 222
 223   template<typename _CharT, typename _Traits, typename _Alloc>
 224     basic_string<_CharT, _Traits, _Alloc>::
 225     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
 226     : _M_dataplus(_S_construct(__n, __c, __a), __a)
 227     { }
 228
 229   template<typename _CharT, typename _Traits, typename _Alloc>
 230     template<typename _InputIter>
 231     basic_string<_CharT, _Traits, _Alloc>::
 232     basic_string(_InputIter __beg, _InputIter __end, const _Alloc& __a)
 233     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
 234     { }
 235
 236   template<typename _CharT, typename _Traits, typename _Alloc>
 237     basic_string<_CharT, _Traits, _Alloc>&
 238     basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str)
 239     {
 240       if (_M_rep() != __str._M_rep())
 241         {
 242           // XXX MT
 243           allocator_type __a = this->get_allocator();
 244           _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
 245           _M_rep()->_M_dispose(__a);
 246           _M_data(__tmp);
 247         }
 248       return *this;
 249     }
 250
 251   template<typename _CharT, typename _Traits, typename _Alloc>
 252     void
 253     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 254     _M_destroy(const _Alloc& __a) throw ()
 255     {
 256       size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT);
 257       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
 258     }
 259
 260   template<typename _CharT, typename _Traits, typename _Alloc>
 261     void
 262     basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
 263     {
 264       if (_M_rep()->_M_is_shared())
 265         _M_mutate(0, 0, 0);
 266       _M_rep()->_M_set_leaked();
 267     }
 268
 269   // _M_mutate and, below, _M_clone, include, in the same form, an exponential
 270   // growth policy, necessary to meet amortized linear time requirements of
 271   // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
 272   // The policy is active for allocations requiring an amount of memory above
 273   // system pagesize. This is consistent with the requirements of the standard:
 274   // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
 275   template<typename _CharT, typename _Traits, typename _Alloc>
 276     void
 277     basic_string<_CharT, _Traits, _Alloc>::
 278     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
 279     {
 280       size_type       __old_size = this->size();
 281       const size_type __new_size = __old_size + __len2 - __len1;
 282       const _CharT*        __src = _M_data()  + __pos + __len1;
 283       const size_type __how_much = __old_size - __pos - __len1;
 284
 285       if (_M_rep()->_M_is_shared() || __new_size > capacity())
 286         {
 287           // Must reallocate.
 288           allocator_type __a = get_allocator();
 289           // See below (_S_create) for the meaning and value of these
 290           // constants.
 291           const size_type __pagesize = 4096;
 292           const size_type __malloc_header_size = 4 * sizeof (void*);
 293           // The biggest string which fits in a memory page
 294           const size_type __page_capacity = (__pagesize - __malloc_header_size
 295                                              - sizeof(_Rep) - sizeof(_CharT))
 296                                              / sizeof(_CharT);
 297           _Rep* __r;
 298           if (__new_size > capacity() && __new_size > __page_capacity)
 299             // Growing exponentially.
 300             __r = _Rep::_S_create(__new_size > 2*capacity() ?
 301                                   __new_size : 2*capacity(), __a);
 302           else
 303             __r = _Rep::_S_create(__new_size, __a);
 304           try
 305             {
 306               if (__pos)
 307                 traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
 308               if (__how_much)
 309                 traits_type::copy(__r->_M_refdata() + __pos + __len2,
 310                                   __src, __how_much);
 311             }
 312           catch(...)
 313             {
 314               __r->_M_dispose(get_allocator());
 315               __throw_exception_again;
 316             }
 317           _M_rep()->_M_dispose(__a);
 318           _M_data(__r->_M_refdata());
 319       }
 320       else if (__how_much && __len1 != __len2)
 321         {
 322           // Work in-place
 323           traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
 324         }
 325       _M_rep()->_M_set_sharable();
 326       _M_rep()->_M_length = __new_size;
 327       _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
 328     // You cannot leave those LWG people alone for a second.
 329     }
 330
 331   template<typename _CharT, typename _Traits, typename _Alloc>
 332     void
 333     basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
 334     {
 335       if (__res > this->capacity() || _M_rep()->_M_is_shared())
 336         {
 337           if (__res > this->max_size())
 338             __throw_length_error("basic_string::reserve");
 339           // Make sure we don't shrink below the current size
 340           if (__res < this->size())
 341             __res = this->size();
 342           allocator_type __a = get_allocator();
 343           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
 344           _M_rep()->_M_dispose(__a);
 345           _M_data(__tmp);
 346         }
 347     }
 348
 349   template<typename _CharT, typename _Traits, typename _Alloc>
 350     void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
 351     {
 352       if (_M_rep()->_M_is_leaked())
 353         _M_rep()->_M_set_sharable();
 354       if (__s._M_rep()->_M_is_leaked())
 355         __s._M_rep()->_M_set_sharable();
 356       if (this->get_allocator() == __s.get_allocator())
 357         {
 358           _CharT* __tmp = _M_data();
 359           _M_data(__s._M_data());
 360           __s._M_data(__tmp);
 361         }
 362       // The code below can usually be optimized away.
 363       else
 364         {
 365           basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator());
 366           basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
 367                               this->get_allocator());
 368           *this = __tmp2;
 369           __s = __tmp1;
 370         }
 371     }
 372
 373   template<typename _CharT, typename _Traits, typename _Alloc>
 374     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
 375     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 376     _S_create(size_t __capacity, const _Alloc& __alloc)
 377     {
 378       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 379 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
 380       // 83.  String::npos vs. string::max_size()
 381       if (__capacity > _S_max_size)
 382 #else
 383       if (__capacity == npos)
 384 #endif
 385         __throw_length_error("basic_string::_S_create");
 386
 387       // NB: Need an array of char_type[__capacity], plus a
 388       // terminating null char_type() element, plus enough for the
 389       // _Rep data structure. Whew. Seemingly so needy, yet so elemental.
 390       size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
 391
 392       // The standard places no restriction on allocating more memory
 393       // than is strictly needed within this layer at the moment or as
 394       // requested by an explicit application call to reserve().  Many
 395       // malloc implementations perform quite poorly when an
 396       // application attempts to allocate memory in a stepwise fashion
 397       // growing each allocation size by only 1 char.  Additionally,
 398       // it makes little sense to allocate less linear memory than the
 399       // natural blocking size of the malloc implementation.
 400       // Unfortunately, we would need a somewhat low-level calculation
 401       // with tuned parameters to get this perfect for any particular
 402       // malloc implementation.  Fortunately, generalizations about
 403       // common features seen among implementations seems to suffice.
 404
 405       // __pagesize need not match the actual VM page size for good
 406       // results in practice, thus we pick a common value on the low
 407       // side.  __malloc_header_size is an estimate of the amount of
 408       // overhead per memory allocation (in practice seen N * sizeof
 409       // (void*) where N is 0, 2 or 4).  According to folklore,
 410       // picking this value on the high side is better than
 411       // low-balling it (especially when this algorithm is used with
 412       // malloc implementations that allocate memory blocks rounded up
 413       // to a size which is a power of 2).
 414       const size_t __pagesize = 4096; // must be 2^i * __subpagesize
 415       const size_t __subpagesize = 128; // should be >> __malloc_header_size
 416       const size_t __malloc_header_size = 4 * sizeof (void*);
 417       if ((__size + __malloc_header_size) > __pagesize)
 418         {
 419           size_t __extra =
 420             (__pagesize - ((__size + __malloc_header_size) % __pagesize))
 421             % __pagesize;
 422           __capacity += __extra / sizeof(_CharT);
 423           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
 424         }
 425       else if (__size > __subpagesize)
 426         {
 427           size_t __extra =
 428             (__subpagesize - ((__size + __malloc_header_size) % __subpagesize))
 429             % __subpagesize;
 430           __capacity += __extra / sizeof(_CharT);
 431           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
 432         }
 433
 434       // NB: Might throw, but no worries about a leak, mate: _Rep()
 435       // does not throw.
 436       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
 437       _Rep *__p = new (__place) _Rep;
 438       __p->_M_capacity = __capacity;
 439       __p->_M_set_sharable();  // one reference
 440       __p->_M_length = 0;
 441       return __p;
 442     }
 443
 444   template<typename _CharT, typename _Traits, typename _Alloc>
 445     _CharT*
 446     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 447     _M_clone(const _Alloc& __alloc, size_type __res)
 448     {
 449       // Requested capacity of the clone.
 450       const size_type __requested_cap = _M_length + __res;
 451       // See above (_S_create) for the meaning and value of these constants.
 452       const size_type __pagesize = 4096;
 453       const size_type __malloc_header_size = 4 * sizeof (void*);
 454       // The biggest string which fits in a memory page.
 455       const size_type __page_capacity =
 456         (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT))
 457         / sizeof(_CharT);
 458       _Rep* __r;
 459       if (__requested_cap > _M_capacity && __requested_cap > __page_capacity)
 460         // Growing exponentially.
 461         __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ?
 462                               __requested_cap : 2*_M_capacity, __alloc);
 463       else
 464         __r = _Rep::_S_create(__requested_cap, __alloc);
 465
 466       if (_M_length)
 467         {
 468           try
 469             { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); }
 470           catch(...)
 471             {
 472               __r->_M_destroy(__alloc);
 473               __throw_exception_again;
 474             }
 475         }
 476       __r->_M_length = _M_length;
 477       return __r->_M_refdata();
 478     }
 479
 480   template<typename _CharT, typename _Traits, typename _Alloc>
 481     void
 482     basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
 483     {
 484       if (__n > max_size())
 485         __throw_length_error("basic_string::resize");
 486       size_type __size = this->size();
 487       if (__size < __n)
 488         this->append(__n - __size, __c);
 489       else if (__n < __size)
 490         this->erase(__n);
 491       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
 492     }
 493
 494   // This is the general replace helper, which gets instantiated both
 495   // for input-iterators and forward-iterators. It buffers internally and
 496   // then calls _M_replace_safe. For input-iterators this is almost the
 497   // best we can do, but for forward-iterators many optimizations could be
 498   // conceived: f.i., when source and destination ranges do not overlap
 499   // buffering is not really needed. In order to easily implement them, it
 500   // could become useful to add an _M_replace(forward_iterator_tag)
 501   template<typename _CharT, typename _Traits, typename _Alloc>
 502     template<typename _InputIter>
 503       basic_string<_CharT, _Traits, _Alloc>&
 504       basic_string<_CharT, _Traits, _Alloc>::
 505       _M_replace(iterator __i1, iterator __i2, _InputIter __k1,
 506                  _InputIter __k2, input_iterator_tag)
 507       {
 508         // Save concerned source string data in a temporary.
 509         basic_string __s(__k1, __k2);
 510         return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend());
 511       }
 512
 513   // This is a special replace helper, which does not buffer internally
 514   // and can be used in the "safe" situations involving forward-iterators,
 515   // i.e., when source and destination ranges are known to not overlap.
 516   // Presently, is called by _M_replace, by the various append and by
 517   // the assigns.
 518   template<typename _CharT, typename _Traits, typename _Alloc>
 519     template<typename _ForwardIter>
 520       basic_string<_CharT, _Traits, _Alloc>&
 521       basic_string<_CharT, _Traits, _Alloc>::
 522       _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1,
 523                       _ForwardIter __k2)
 524       {
 525         size_type __dnew = static_cast<size_type>(distance(__k1, __k2));
 526         size_type __dold = __i2 - __i1;
 527         size_type __dmax = this->max_size();
 528
 529         if (__dmax <= __dnew)
 530           __throw_length_error("basic_string::_M_replace");
 531         size_type __off = __i1 - _M_ibegin();
 532         _M_mutate(__off, __dold, __dnew);
 533
 534         // Invalidated __i1, __i2
 535         if (__dnew)
 536           _S_copy_chars(_M_data() + __off, __k1, __k2);
 537
 538         return *this;
 539       }
 540
 541   template<typename _CharT, typename _Traits, typename _Alloc>
 542     basic_string<_CharT, _Traits, _Alloc>&
 543     basic_string<_CharT, _Traits, _Alloc>::
 544     replace(size_type __pos1, size_type __n1, const basic_string& __str,
 545             size_type __pos2, size_type __n2)
 546     {
 547       const size_type __strsize = __str.size();
 548       if (__pos2 > __strsize)
 549         __throw_out_of_range("basic_string::replace");
 550       const bool __testn2 = __n2 < __strsize - __pos2;
 551       const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2;
 552       return this->replace(__pos1, __n1,
 553                            __str._M_data() + __pos2, __foldn2);
 554     }
 555
 556   template<typename _CharT, typename _Traits, typename _Alloc>
 557     basic_string<_CharT, _Traits, _Alloc>&
 558     basic_string<_CharT, _Traits, _Alloc>::
 559     append(const basic_string& __str)
 560     {
 561       // Iff appending itself, string needs to pre-reserve the
 562       // correct size so that _M_mutate does not clobber the
 563       // iterators formed here.
 564       size_type __size = __str.size();
 565       size_type __len = __size + this->size();
 566       if (__len > this->capacity())
 567         this->reserve(__len);
 568       return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(),
 569                              __str._M_iend());
 570     }
 571
 572   template<typename _CharT, typename _Traits, typename _Alloc>
 573     basic_string<_CharT, _Traits, _Alloc>&
 574     basic_string<_CharT, _Traits, _Alloc>::
 575     append(const basic_string& __str, size_type __pos, size_type __n)
 576     {
 577       // Iff appending itself, string needs to pre-reserve the
 578       // correct size so that _M_mutate does not clobber the
 579       // iterators formed here.
 580       size_type __len = min(__str.size() - __pos, __n) + this->size();
 581       if (__len > this->capacity())
 582         this->reserve(__len);
 583       return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos),
 584                              __str._M_fold(__pos, __n));
 585     }
 586
 587   template<typename _CharT, typename _Traits, typename _Alloc>
 588     basic_string<_CharT, _Traits, _Alloc>&
 589     basic_string<_CharT, _Traits, _Alloc>::
 590     append(const _CharT* __s, size_type __n)
 591     {
 592       size_type __len = __n + this->size();
 593       if (__len > this->capacity())
 594         this->reserve(__len);
 595       return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n);
 596     }
 597
 598   template<typename _CharT, typename _Traits, typename _Alloc>
 599     basic_string<_CharT, _Traits, _Alloc>&
 600     basic_string<_CharT, _Traits, _Alloc>::
 601     append(size_type __n, _CharT __c)
 602     {
 603       size_type __len = __n + this->size();
 604       if (__len > this->capacity())
 605         this->reserve(__len);
 606        return this->replace(_M_iend(), _M_iend(), __n, __c);
 607     }
 608
 609   template<typename _CharT, typename _Traits, typename _Alloc>
 610     basic_string<_CharT, _Traits, _Alloc>
 611     operator+(const _CharT* __lhs,
 612               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 613     {
 614       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 615       typedef typename __string_type::size_type   __size_type;
 616       __size_type __len = _Traits::length(__lhs);
 617       __string_type __str;
 618       __str.reserve(__len + __rhs.size());
 619       __str.append(__lhs, __lhs + __len);
 620       __str.append(__rhs);
 621       return __str;
 622     }
 623
 624   template<typename _CharT, typename _Traits, typename _Alloc>
 625     basic_string<_CharT, _Traits, _Alloc>
 626     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 627     {
 628       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 629       typedef typename __string_type::size_type   __size_type;
 630       __string_type __str;
 631       __size_type __len = __rhs.size();
 632       __str.reserve(__len + 1);
 633       __str.append(__size_type(1), __lhs);
 634       __str.append(__rhs);
 635       return __str;
 636     }
 637
 638   template<typename _CharT, typename _Traits, typename _Alloc>
 639     basic_string<_CharT, _Traits, _Alloc>&
 640     basic_string<_CharT, _Traits, _Alloc>::
 641     replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c)
 642     {
 643       size_type __n1 = __i2 - __i1;
 644       size_type __off1 = __i1 - _M_ibegin();
 645       if (max_size() - (this->size() - __n1) <= __n2)
 646         __throw_length_error("basic_string::replace");
 647       _M_mutate (__off1, __n1, __n2);
 648       // Invalidated __i1, __i2
 649       if (__n2)
 650         traits_type::assign(_M_data() + __off1, __n2, __c);
 651       return *this;
 652     }
 653
 654   template<typename _CharT, typename _Traits, typename _Alloc>
 655     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 656     basic_string<_CharT, _Traits, _Alloc>::
 657     copy(_CharT* __s, size_type __n, size_type __pos) const
 658     {
 659       if (__pos > this->size())
 660         __throw_out_of_range("basic_string::copy");
 661
 662       if (__n > this->size() - __pos)
 663         __n = this->size() - __pos;
 664
 665       traits_type::copy(__s, _M_data() + __pos, __n);
 666       // 21.3.5.7 par 3: do not append null.  (good.)
 667       return __n;
 668     }
 669
 670   template<typename _CharT, typename _Traits, typename _Alloc>
 671     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 672     basic_string<_CharT, _Traits, _Alloc>::
 673     find(const _CharT* __s, size_type __pos, size_type __n) const
 674     {
 675       size_type __size = this->size();
 676       size_t __xpos = __pos;
 677       const _CharT* __data = _M_data();
 678       for (; __xpos + __n <= __size; ++__xpos)
 679         if (traits_type::compare(__data + __xpos, __s, __n) == 0)
 680           return __xpos;
 681       return npos;
 682     }
 683
 684   template<typename _CharT, typename _Traits, typename _Alloc>
 685     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 686     basic_string<_CharT, _Traits, _Alloc>::
 687     find(_CharT __c, size_type __pos) const
 688     {
 689       size_type __size = this->size();
 690       size_type __ret = npos;
 691       if (__pos < __size)
 692         {
 693           const _CharT* __data = _M_data();
 694           size_type __n = __size - __pos;
 695           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
 696           if (__p)
 697             __ret = __p - __data;
 698         }
 699       return __ret;
 700     }
 701
 702
 703   template<typename _CharT, typename _Traits, typename _Alloc>
 704     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 705     basic_string<_CharT, _Traits, _Alloc>::
 706     rfind(const _CharT* __s, size_type __pos, size_type __n) const
 707     {
 708       size_type __size = this->size();
 709       if (__n <= __size)
 710         {
 711           __pos = std::min(__size - __n, __pos);
 712           const _CharT* __data = _M_data();
 713           do
 714             {
 715               if (traits_type::compare(__data + __pos, __s, __n) == 0)
 716                 return __pos;
 717             }
 718           while (__pos-- > 0);
 719         }
 720       return npos;
 721     }
 722
 723   template<typename _CharT, typename _Traits, typename _Alloc>
 724     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 725     basic_string<_CharT, _Traits, _Alloc>::
 726     rfind(_CharT __c, size_type __pos) const
 727     {
 728       size_type __size = this->size();
 729       if (__size)
 730         {
 731           size_t __xpos = __size - 1;
 732           if (__xpos > __pos)
 733             __xpos = __pos;
 734
 735           for (++__xpos; __xpos-- > 0; )
 736             if (traits_type::eq(_M_data()[__xpos], __c))
 737               return __xpos;
 738         }
 739       return npos;
 740     }
 741
 742   template<typename _CharT, typename _Traits, typename _Alloc>
 743     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 744     basic_string<_CharT, _Traits, _Alloc>::
 745     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
 746     {
 747       for (; __n && __pos < this->size(); ++__pos)
 748         {
 749           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
 750           if (__p)
 751             return __pos;
 752         }
 753       return npos;
 754     }
 755
 756   template<typename _CharT, typename _Traits, typename _Alloc>
 757     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 758     basic_string<_CharT, _Traits, _Alloc>::
 759     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
 760     {
 761       size_type __size = this->size();
 762       if (__size && __n)
 763         {
 764           if (--__size > __pos)
 765             __size = __pos;
 766           do
 767             {
 768               if (traits_type::find(__s, __n, _M_data()[__size]))
 769                 return __size;
 770             }
 771           while (__size-- != 0);
 772         }
 773       return npos;
 774     }
 775
 776   template<typename _CharT, typename _Traits, typename _Alloc>
 777     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 778     basic_string<_CharT, _Traits, _Alloc>::
 779     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 780     {
 781       size_t __xpos = __pos;
 782       for (; __xpos < this->size(); ++__xpos)
 783         if (!traits_type::find(__s, __n, _M_data()[__xpos]))
 784           return __xpos;
 785       return npos;
 786     }
 787
 788   template<typename _CharT, typename _Traits, typename _Alloc>
 789     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 790     basic_string<_CharT, _Traits, _Alloc>::
 791     find_first_not_of(_CharT __c, size_type __pos) const
 792     {
 793       size_t __xpos = __pos;
 794       for (; __xpos < this->size(); ++__xpos)
 795         if (!traits_type::eq(_M_data()[__xpos], __c))
 796           return __xpos;
 797       return npos;
 798     }
 799
 800   template<typename _CharT, typename _Traits, typename _Alloc>
 801     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 802     basic_string<_CharT, _Traits, _Alloc>::
 803     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 804     {
 805       size_type __size = this->size();
 806       if (__size)
 807         {
 808           if (--__size > __pos)
 809             __size = __pos;
 810           do
 811             {
 812               if (!traits_type::find(__s, __n, _M_data()[__size]))
 813                 return __size;
 814             }
 815           while (__size--);
 816         }
 817       return npos;
 818     }
 819
 820   template<typename _CharT, typename _Traits, typename _Alloc>
 821     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 822     basic_string<_CharT, _Traits, _Alloc>::
 823     find_last_not_of(_CharT __c, size_type __pos) const
 824     {
 825       size_type __size = this->size();
 826       if (__size)
 827         {
 828           if (--__size > __pos)
 829             __size = __pos;
 830           do
 831             {
 832               if (!traits_type::eq(_M_data()[__size], __c))
 833                 return __size;
 834             }
 835           while (__size--);
 836         }
 837       return npos;
 838     }
 839
 840   template<typename _CharT, typename _Traits, typename _Alloc>
 841     int
 842     basic_string<_CharT, _Traits, _Alloc>::
 843     compare(size_type __pos, size_type __n, const basic_string& __str) const
 844     {
 845       size_type __size = this->size();
 846       size_type __osize = __str.size();
 847       if (__pos > __size)
 848         __throw_out_of_range("basic_string::compare");
 849
 850       size_type __rsize= min(__size - __pos, __n);
 851       size_type __len = min(__rsize, __osize);
 852       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
 853       if (!__r)
 854         __r = __rsize - __osize;
 855       return __r;
 856     }
 857
 858   template<typename _CharT, typename _Traits, typename _Alloc>
 859     int
 860     basic_string<_CharT, _Traits, _Alloc>::
 861     compare(size_type __pos1, size_type __n1, const basic_string& __str,
 862             size_type __pos2, size_type __n2) const
 863     {
 864       size_type __size = this->size();
 865       size_type __osize = __str.size();
 866       if (__pos1 > __size || __pos2 > __osize)
 867         __throw_out_of_range("basic_string::compare");
 868
 869       size_type __rsize = min(__size - __pos1, __n1);
 870       size_type __rosize = min(__osize - __pos2, __n2);
 871       size_type __len = min(__rsize, __rosize);
 872       int __r = traits_type::compare(_M_data() + __pos1,
 873                                      __str.data() + __pos2, __len);
 874       if (!__r)
 875         __r = __rsize - __rosize;
 876       return __r;
 877     }
 878
 879
 880   template<typename _CharT, typename _Traits, typename _Alloc>
 881     int
 882     basic_string<_CharT, _Traits, _Alloc>::
 883     compare(const _CharT* __s) const
 884     {
 885       size_type __size = this->size();
 886       int __r = traits_type::compare(_M_data(), __s, __size);
 887       if (!__r)
 888         __r = __size - traits_type::length(__s);
 889       return __r;
 890     }
 891
 892
 893   template<typename _CharT, typename _Traits, typename _Alloc>
 894     int
 895     basic_string <_CharT, _Traits, _Alloc>::
 896     compare(size_type __pos, size_type __n1, const _CharT* __s) const
 897     {
 898       size_type __size = this->size();
 899       if (__pos > __size)
 900         __throw_out_of_range("basic_string::compare");
 901
 902       size_type __osize = traits_type::length(__s);
 903       size_type __rsize = min(__size - __pos, __n1);
 904       size_type __len = min(__rsize, __osize);
 905       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 906       if (!__r)
 907         __r = __rsize - __osize;
 908       return __r;
 909     }
 910
 911   template<typename _CharT, typename _Traits, typename _Alloc>
 912     int
 913     basic_string <_CharT, _Traits, _Alloc>::
 914     compare(size_type __pos, size_type __n1, const _CharT* __s,
 915             size_type __n2) const
 916     {
 917       size_type __size = this->size();
 918       if (__pos > __size)
 919         __throw_out_of_range("basic_string::compare");
 920
 921       size_type __osize = min(traits_type::length(__s), __n2);
 922       size_type __rsize = min(__size - __pos, __n1);
 923       size_type __len = min(__rsize, __osize);
 924       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 925       if (!__r)
 926         __r = __rsize - __osize;
 927       return __r;
 928     }
 929
 930   template <class _CharT, class _Traits, class _Alloc>
 931     void
 932     _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str,
 933                    _CharT* __buf, typename _Alloc::size_type __bufsiz)
 934     {
 935       typedef typename _Alloc::size_type size_type;
 936       size_type __strsize = __str.size();
 937       size_type __bytes = min(__strsize, __bufsiz - 1);
 938       _Traits::copy(__buf, __str.data(), __bytes);
 939       __buf[__bytes] = _CharT();
 940     }
 941 } // namespace std
 942
 943 #endif