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