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