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