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

   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 /** @file basic_string.h
  36  *  This is an internal header file, included by other library headers.
  37  *  You should not attempt to use it directly.
  38  */
  39
  40 #ifndef _CPP_BITS_STRING_H
  41 #define _CPP_BITS_STRING_H        1
  42
  43 #pragma GCC system_header
  44
  45 #include <bits/atomicity.h>
  46
  47 namespace std
  48 {
  49   /**
  50    *  @class basic_string basic_string.h <string>
  51    *  @brief  Managing sequences of characters and character-like objects.
  52    *
  53    *  @ingroup Containers
  54    *  @ingroup Sequences
  55    *
  56    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
  57    *  <a href="tables.html#66">reversible container</a>, and a
  58    *  <a href="tables.html#67">sequence</a>.  Of the
  59    *  <a href="tables.html#68">optional sequence requirements</a>, only
  60    *  @c push_back, @c at, and array access are supported.
  61    *
  62    *  @doctodo
  63    *
  64    *
  65    *  @if maint
  66    *  Documentation?  What's that?
  67    *  Nathan Myers <ncm@cantrip.org>.
  68    *
  69    *  A string looks like this:
  70    *
  71    *  @code
  72    *                                        [_Rep]
  73    *                                        _M_length
  74    *   [basic_string<char_type>]            _M_capacity
  75    *   _M_dataplus                          _M_state
  76    *   _M_p ---------------->               unnamed array of char_type
  77    *  @endcode
  78    *
  79    *  Where the _M_p points to the first character in the string, and
  80    *  you cast it to a pointer-to-_Rep and subtract 1 to get a
  81    *  pointer to the header.
  82    *
  83    *  This approach has the enormous advantage that a string object
  84    *  requires only one allocation.  All the ugliness is confined
  85    *  within a single pair of inline functions, which each compile to
  86    *  a single "add" instruction: _Rep::_M_data(), and
  87    *  string::_M_rep(); and the allocation function which gets a
  88    *  block of raw bytes and with room enough and constructs a _Rep
  89    *  object at the front.
  90    *
  91    *  The reason you want _M_data pointing to the character array and
  92    *  not the _Rep is so that the debugger can see the string
  93    *  contents. (Probably we should add a non-inline member to get
  94    *  the _Rep for the debugger to use, so users can check the actual
  95    *  string length.)
  96    *
  97    *  Note that the _Rep object is a POD so that you can have a
  98    *  static "empty string" _Rep object already "constructed" before
  99    *  static constructors have run.  The reference-count encoding is
 100    *  chosen so that a 0 indicates one reference, so you never try to
 101    *  destroy the empty-string _Rep object.
 102    *
 103    *  All but the last paragraph is considered pretty conventional
 104    *  for a C++ string implementation.
 105    *  @endif
 106   */
 107   // 21.3  Template class basic_string
 108   template<typename _CharT, typename _Traits, typename _Alloc>
 109     class basic_string
 110     {
 111       // Types:
 112     public:
 113       typedef _Traits                                       traits_type;
 114       typedef typename _Traits::char_type                   value_type;
 115       typedef _Alloc                                        allocator_type;
 116       typedef typename _Alloc::size_type                    size_type;
 117       typedef typename _Alloc::difference_type              difference_type;
 118       typedef typename _Alloc::reference                    reference;
 119       typedef typename _Alloc::const_reference              const_reference;
 120       typedef typename _Alloc::pointer                      pointer;
 121       typedef typename _Alloc::const_pointer                const_pointer;
 122       typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
 123       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
 124                                                             const_iterator;
 125       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
 126       typedef std::reverse_iterator<iterator>               reverse_iterator;
 127
 128     private:
 129       // _Rep: string representation
 130       //   Invariants:
 131       //   1. String really contains _M_length + 1 characters; last is set
 132       //      to 0 only on call to c_str().  We avoid instantiating
 133       //      _CharT() where the interface does not require it.
 134       //   2. _M_capacity >= _M_length
 135       //      Allocated memory is always _M_capacity + (1 * sizeof(_CharT)).
 136       //   3. _M_references has three states:
 137       //      -1: leaked, one reference, no ref-copies allowed, non-const.
 138       //       0: one reference, non-const.
 139       //     n>0: n + 1 references, operations require a lock, const.
 140       //   4. All fields==0 is an empty string, given the extra storage
 141       //      beyond-the-end for a null terminator; thus, the shared
 142       //      empty string representation needs no constructor.
 143       struct _Rep
 144       {
 145         // Types:
 146         typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
 147
 148         // (Public) Data members:
 149
 150         // The maximum number of individual char_type elements of an
 151         // individual string is determined by _S_max_size. This is the
 152         // value that will be returned by max_size().  (Whereas npos
 153         // is the maximum number of bytes the allocator can allocate.)
 154         // If one was to divvy up the theoretical largest size string,
 155         // with a terminating character and m _CharT elements, it'd
 156         // look like this:
 157         // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
 158         // Solving for m:
 159         // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
 160         // In addition, this implementation quarters this ammount.
 161         static const size_type  _S_max_size;
 162         static const _CharT     _S_terminal;
 163
 164         size_type               _M_length;
 165         size_type               _M_capacity;
 166         _Atomic_word            _M_references;
 167
 168         bool
 169         _M_is_leaked() const
 170         { return _M_references < 0; }
 171
 172         bool
 173         _M_is_shared() const
 174         { return _M_references > 0; }
 175
 176         void
 177         _M_set_leaked()
 178         { _M_references = -1; }
 179
 180         void
 181         _M_set_sharable()
 182         { _M_references = 0; }
 183
 184         _CharT*
 185         _M_refdata() throw()
 186         { return reinterpret_cast<_CharT*>(this + 1); }
 187
 188         _CharT&
 189         operator[](size_t __s) throw()
 190         { return _M_refdata() [__s]; }
 191
 192         _CharT*
 193         _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
 194         {
 195           return (!_M_is_leaked() && __alloc1 == __alloc2)
 196                   ? _M_refcopy() : _M_clone(__alloc1);
 197         }
 198
 199         // Create & Destroy
 200         static _Rep*
 201         _S_create(size_t, const _Alloc&);
 202
 203         void
 204         _M_dispose(const _Alloc& __a)
 205         {
 206           if (__exchange_and_add(&_M_references, -1) <= 0)
 207             _M_destroy(__a);
 208         }  // XXX MT
 209
 210         void
 211         _M_destroy(const _Alloc&) throw();
 212
 213         _CharT*
 214         _M_refcopy() throw()
 215         {
 216           __atomic_add(&_M_references, 1);
 217           return _M_refdata();
 218         }  // XXX MT
 219
 220         _CharT*
 221         _M_clone(const _Alloc&, size_type __res = 0);
 222       };
 223
 224       // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
 225       struct _Alloc_hider : _Alloc
 226       {
 227         _Alloc_hider(_CharT* __dat, const _Alloc& __a)
 228         : _Alloc(__a), _M_p(__dat) { }
 229
 230         _CharT* _M_p; // The actual data.
 231       };
 232
 233     public:
 234       // Data Members (public):
 235       // NB: This is an unsigned type, and thus represents the maximum
 236       // size that the allocator can hold.
 237       static const size_type    npos = static_cast<size_type>(-1);
 238
 239     private:
 240       // Data Members (private):
 241       mutable _Alloc_hider      _M_dataplus;
 242
 243       // The following storage is init'd to 0 by the linker, resulting
 244       // (carefully) in an empty string with one reference.
 245       static size_type _S_empty_rep_storage[(sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
 246
 247       _CharT*
 248       _M_data() const
 249       { return  _M_dataplus._M_p; }
 250
 251       _CharT*
 252       _M_data(_CharT* __p)
 253       { return (_M_dataplus._M_p = __p); }
 254
 255       _Rep*
 256       _M_rep() const
 257       { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
 258
 259       // For the internal use we have functions similar to `begin'/`end'
 260       // but they do not call _M_leak.
 261       iterator
 262       _M_ibegin() const { return iterator(_M_data()); }
 263
 264       iterator
 265       _M_iend() const { return iterator(_M_data() + this->size()); }
 266
 267       void
 268       _M_leak()    // for use in begin() & non-const op[]
 269       {
 270         if (!_M_rep()->_M_is_leaked())
 271           _M_leak_hard();
 272       }
 273
 274       iterator
 275       _M_check(size_type __pos) const
 276       {
 277         if (__pos > this->size())
 278           __throw_out_of_range("basic_string::_M_check");
 279         return _M_ibegin() + __pos;
 280       }
 281
 282       // NB: _M_fold doesn't check for a bad __pos1 value.
 283       iterator
 284       _M_fold(size_type __pos, size_type __off) const
 285       {
 286         bool __testoff =  __off < this->size() - __pos;
 287         size_type __newoff = __testoff ? __off : this->size() - __pos;
 288         return (_M_ibegin() + __pos + __newoff);
 289       }
 290
 291       // _S_copy_chars is a separate template to permit specialization
 292       // to optimize for the common case of pointers as iterators.
 293       template<class _Iterator>
 294         static void
 295         _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
 296         {
 297           for (; __k1 != __k2; ++__k1, ++__p)
 298             traits_type::assign(*__p, *__k1); // These types are off.
 299         }
 300
 301       static void
 302       _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2)
 303       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
 304
 305       static void
 306       _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
 307       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
 308
 309       static void
 310       _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2)
 311       { traits_type::copy(__p, __k1, __k2 - __k1); }
 312
 313       static void
 314       _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
 315       { traits_type::copy(__p, __k1, __k2 - __k1); }
 316
 317       void
 318       _M_mutate(size_type __pos, size_type __len1, size_type __len2);
 319
 320       void
 321       _M_leak_hard();
 322
 323       static _Rep&
 324       _S_empty_rep()
 325       { return *reinterpret_cast<_Rep*>(&_S_empty_rep_storage); }
 326
 327     public:
 328       // Construct/copy/destroy:
 329       // NB: We overload ctors in some cases instead of using default
 330       // arguments, per 17.4.4.4 para. 2 item 2.
 331
 332       inline
 333       basic_string();
 334
 335       explicit
 336       basic_string(const _Alloc& __a);
 337
 338       // NB: per LWG issue 42, semantics different from IS:
 339       basic_string(const basic_string& __str);
 340       basic_string(const basic_string& __str, size_type __pos,
 341                    size_type __n = npos);
 342       basic_string(const basic_string& __str, size_type __pos,
 343                    size_type __n, const _Alloc& __a);
 344
 345       basic_string(const _CharT* __s, size_type __n,
 346                    const _Alloc& __a = _Alloc());
 347       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
 348       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
 349
 350       template<class _InputIterator>
 351         basic_string(_InputIterator __beg, _InputIterator __end,
 352                      const _Alloc& __a = _Alloc());
 353
 354       ~basic_string()
 355       { _M_rep()->_M_dispose(this->get_allocator()); }
 356
 357       basic_string&
 358       operator=(const basic_string& __str) { return this->assign(__str); }
 359
 360       basic_string&
 361       operator=(const _CharT* __s) { return this->assign(__s); }
 362
 363       basic_string&
 364       operator=(_CharT __c) { return this->assign(1, __c); }
 365
 366       // Iterators:
 367       iterator
 368       begin()
 369       {
 370         _M_leak();
 371         return iterator(_M_data());
 372       }
 373
 374       const_iterator
 375       begin() const
 376       { return const_iterator(_M_data()); }
 377
 378       iterator
 379       end()
 380       {
 381          _M_leak();
 382          return iterator(_M_data() + this->size());
 383       }
 384
 385       const_iterator
 386       end() const
 387       { return const_iterator(_M_data() + this->size()); }
 388
 389       reverse_iterator
 390       rbegin()
 391       { return reverse_iterator(this->end()); }
 392
 393       const_reverse_iterator
 394       rbegin() const
 395       { return const_reverse_iterator(this->end()); }
 396
 397       reverse_iterator
 398       rend()
 399       { return reverse_iterator(this->begin()); }
 400
 401       const_reverse_iterator
 402       rend() const
 403       { return const_reverse_iterator(this->begin()); }
 404
 405     public:
 406       // Capacity:
 407       size_type
 408       size() const { return _M_rep()->_M_length; }
 409
 410       size_type
 411       length() const { return _M_rep()->_M_length; }
 412
 413       size_type
 414       max_size() const { return _Rep::_S_max_size; }
 415
 416       void
 417       resize(size_type __n, _CharT __c);
 418
 419       void
 420       resize(size_type __n) { this->resize(__n, _CharT()); }
 421
 422       size_type
 423       capacity() const { return _M_rep()->_M_capacity; }
 424
 425       void
 426       reserve(size_type __res_arg = 0);
 427
 428       void
 429       clear() { _M_mutate(0, this->size(), 0); }
 430
 431       bool
 432       empty() const { return this->size() == 0; }
 433
 434       // Element access:
 435       const_reference
 436       operator[] (size_type __pos) const
 437       { return _M_data()[__pos]; }
 438
 439       reference
 440       operator[](size_type __pos)
 441       {
 442         _M_leak();
 443         return _M_data()[__pos];
 444       }
 445
 446       const_reference
 447       at(size_type __n) const
 448       {
 449         if (__n >= this->size())
 450           __throw_out_of_range("basic_string::at");
 451         return _M_data()[__n];
 452       }
 453
 454       reference
 455       at(size_type __n)
 456       {
 457         if (__n >= size())
 458           __throw_out_of_range("basic_string::at");
 459         _M_leak();
 460         return _M_data()[__n];
 461       }
 462
 463       // Modifiers:
 464       basic_string&
 465       operator+=(const basic_string& __str) { return this->append(__str); }
 466
 467       basic_string&
 468       operator+=(const _CharT* __s) { return this->append(__s); }
 469
 470       basic_string&
 471       operator+=(_CharT __c) { return this->append(size_type(1), __c); }
 472
 473       basic_string&
 474       append(const basic_string& __str);
 475
 476       basic_string&
 477       append(const basic_string& __str, size_type __pos, size_type __n);
 478
 479       basic_string&
 480       append(const _CharT* __s, size_type __n);
 481
 482       basic_string&
 483       append(const _CharT* __s)
 484       { return this->append(__s, traits_type::length(__s)); }
 485
 486       basic_string&
 487       append(size_type __n, _CharT __c);
 488
 489       template<class _InputIterator>
 490         basic_string&
 491         append(_InputIterator __first, _InputIterator __last)
 492         { return this->replace(_M_iend(), _M_iend(), __first, __last); }
 493
 494       void
 495       push_back(_CharT __c)
 496       { this->replace(_M_iend(), _M_iend(), 1, __c); }
 497
 498       basic_string&
 499       assign(const basic_string& __str);
 500
 501       basic_string&
 502       assign(const basic_string& __str, size_type __pos, size_type __n)
 503       {
 504         const size_type __strsize = __str.size();
 505         if (__pos > __strsize)
 506           __throw_out_of_range("basic_string::assign");
 507         const bool __testn = __n < __strsize - __pos;
 508         const size_type __newsize = __testn ? __n : __strsize - __pos;
 509         return this->assign(__str._M_data() + __pos, __newsize);
 510       }
 511
 512       basic_string&
 513       assign(const _CharT* __s, size_type __n)
 514       {
 515         if (__n > this->max_size())
 516           __throw_length_error("basic_string::assign");
 517         if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 518             || less<const _CharT*>()(_M_data() + this->size(), __s))
 519           return _M_replace_safe(_M_ibegin(), _M_iend(), __s, __s + __n);
 520         else
 521           {
 522             // Work in-place
 523             const size_type __pos = __s - _M_data();
 524             if (__pos >= __n)
 525               traits_type::copy(_M_data(), __s, __n);
 526             else if (__pos)
 527               traits_type::move(_M_data(), __s, __n);
 528             _M_rep()->_M_length = __n;
 529             _M_data()[__n] = _Rep::_S_terminal;
 530             return *this;
 531           }
 532       }
 533
 534       basic_string&
 535       assign(const _CharT* __s)
 536       { return this->assign(__s, traits_type::length(__s)); }
 537
 538       basic_string&
 539       assign(size_type __n, _CharT __c)
 540       { return this->replace(_M_ibegin(), _M_iend(), __n, __c); }
 541
 542       template<class _InputIterator>
 543         basic_string&
 544         assign(_InputIterator __first, _InputIterator __last)
 545         { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
 546
 547       void
 548       insert(iterator __p, size_type __n, _CharT __c)
 549       { this->replace(__p, __p, __n, __c);  }
 550
 551       template<class _InputIterator>
 552         void insert(iterator __p, _InputIterator __beg, _InputIterator __end)
 553         { this->replace(__p, __p, __beg, __end); }
 554
 555       basic_string&
 556       insert(size_type __pos1, const basic_string& __str)
 557       { return this->insert(__pos1, __str, 0, __str.size()); }
 558
 559       basic_string&
 560       insert(size_type __pos1, const basic_string& __str,
 561              size_type __pos2, size_type __n)
 562       {
 563         const size_type __strsize = __str.size();
 564         if (__pos2 > __strsize)
 565           __throw_out_of_range("basic_string::insert");
 566         const bool __testn = __n < __strsize - __pos2;
 567         const size_type __newsize = __testn ? __n : __strsize - __pos2;
 568         return this->insert(__pos1, __str._M_data() + __pos2, __newsize);
 569       }
 570
 571       basic_string&
 572       insert(size_type __pos, const _CharT* __s, size_type __n)
 573       {
 574         const size_type __size = this->size();
 575         if (__pos > __size)
 576           __throw_out_of_range("basic_string::insert");
 577         if (__size > this->max_size() - __n)
 578           __throw_length_error("basic_string::insert");
 579         if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 580             || less<const _CharT*>()(_M_data() + __size, __s))
 581           return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos,
 582                                  __s, __s + __n);
 583         else
 584           {
 585             // Work in-place. If _M_mutate reallocates the string, __s
 586             // does not point anymore to valid data, therefore we save its
 587             // offset, then we restore it.
 588             const size_type __off = __s - _M_data();
 589             _M_mutate(__pos, 0, __n);
 590             __s = _M_data() + __off;
 591             _CharT* __p = _M_data() + __pos;
 592             if (__s  + __n <= __p)
 593               traits_type::copy(__p, __s, __n);
 594             else if (__s >= __p)
 595               traits_type::copy(__p, __s + __n, __n);
 596             else
 597               {
 598                 traits_type::copy(__p, __s, __p - __s);
 599                 traits_type::copy(__p + (__p - __s), __p + __n, __n - (__p - __s));
 600               }
 601             return *this;
 602           }
 603        }
 604
 605       basic_string&
 606       insert(size_type __pos, const _CharT* __s)
 607       { return this->insert(__pos, __s, traits_type::length(__s)); }
 608
 609       basic_string&
 610       insert(size_type __pos, size_type __n, _CharT __c)
 611       {
 612         this->insert(_M_check(__pos), __n, __c);
 613         return *this;
 614       }
 615
 616       iterator
 617       insert(iterator __p, _CharT __c = _CharT())
 618       {
 619         size_type __pos = __p - _M_ibegin();
 620         this->insert(_M_check(__pos), size_type(1), __c);
 621         _M_rep()->_M_set_leaked();
 622         return this->_M_ibegin() + __pos;
 623       }
 624
 625       basic_string&
 626       erase(size_type __pos = 0, size_type __n = npos)
 627       {
 628         return this->replace(_M_check(__pos), _M_fold(__pos, __n),
 629                              _M_data(), _M_data());
 630       }
 631
 632       iterator
 633       erase(iterator __position)
 634       {
 635         size_type __i = __position - _M_ibegin();
 636         this->replace(__position, __position + 1, _M_data(), _M_data());
 637         _M_rep()->_M_set_leaked();
 638         return _M_ibegin() + __i;
 639       }
 640
 641       iterator
 642       erase(iterator __first, iterator __last)
 643       {
 644         size_type __i = __first - _M_ibegin();
 645         this->replace(__first, __last, _M_data(), _M_data());
 646         _M_rep()->_M_set_leaked();
 647        return _M_ibegin() + __i;
 648       }
 649
 650       basic_string&
 651       replace(size_type __pos, size_type __n, const basic_string& __str)
 652       { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
 653
 654       basic_string&
 655       replace(size_type __pos1, size_type __n1, const basic_string& __str,
 656               size_type __pos2, size_type __n2);
 657
 658       basic_string&
 659       replace(size_type __pos, size_type __n1, const _CharT* __s,
 660               size_type __n2)
 661       {
 662         const size_type __size = this->size();
 663         if (__pos > __size)
 664           __throw_out_of_range("basic_string::replace");
 665         const bool __testn1 = __n1 < __size - __pos;
 666         const size_type __foldn1 = __testn1 ? __n1 : __size - __pos;
 667         if (__size - __foldn1 > this->max_size() - __n2)
 668           __throw_length_error("basic_string::replace");
 669         if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 670             || less<const _CharT*>()(_M_data() + __size, __s))
 671           return _M_replace_safe(_M_ibegin() + __pos,
 672                                  _M_ibegin() + __pos + __foldn1, __s, __s + __n2);
 673         // Todo: optimized in-place replace.
 674         else return
 675                _M_replace(_M_ibegin() + __pos, _M_ibegin() + __pos + __foldn1,
 676                           __s, __s + __n2,
 677                           typename iterator_traits<const _CharT*>::iterator_category());
 678       }
 679
 680       basic_string&
 681       replace(size_type __pos, size_type __n1, const _CharT* __s)
 682       { return this->replace(__pos, __n1, __s, traits_type::length(__s)); }
 683
 684       basic_string&
 685       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
 686       { return this->replace(_M_check(__pos), _M_fold(__pos, __n1), __n2, __c); }
 687
 688       basic_string&
 689       replace(iterator __i1, iterator __i2, const basic_string& __str)
 690       { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
 691
 692       basic_string&
 693       replace(iterator __i1, iterator __i2,
 694                            const _CharT* __s, size_type __n)
 695       { return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n); }
 696
 697       basic_string&
 698       replace(iterator __i1, iterator __i2, const _CharT* __s)
 699       { return this->replace(__i1, __i2, __s, traits_type::length(__s)); }
 700
 701       basic_string&
 702       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c);
 703
 704       template<class _InputIterator>
 705         basic_string&
 706         replace(iterator __i1, iterator __i2,
 707                 _InputIterator __k1, _InputIterator __k2)
 708         { return _M_replace(__i1, __i2, __k1, __k2,
 709              typename iterator_traits<_InputIterator>::iterator_category()); }
 710
 711       // Specializations for the common case of pointer and iterator:
 712       // useful to avoid the overhead of temporary buffering in _M_replace.
 713       basic_string&
 714       replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
 715         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
 716                                __k1, __k2 - __k1); }
 717
 718       basic_string&
 719       replace(iterator __i1, iterator __i2, const _CharT* __k1, const _CharT* __k2)
 720         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
 721                                __k1, __k2 - __k1); }
 722
 723       basic_string&
 724       replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
 725         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
 726                                __k1.base(), __k2 - __k1);
 727         }
 728
 729       basic_string&
 730       replace(iterator __i1, iterator __i2, const_iterator __k1, const_iterator __k2)
 731         { return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
 732                                __k1.base(), __k2 - __k1);
 733         }
 734
 735     private:
 736       template<class _InputIterator>
 737         basic_string&
 738         _M_replace(iterator __i1, iterator __i2, _InputIterator __k1,
 739                    _InputIterator __k2, input_iterator_tag);
 740
 741       template<class _ForwardIterator>
 742         basic_string&
 743         _M_replace_safe(iterator __i1, iterator __i2, _ForwardIterator __k1,
 744                    _ForwardIterator __k2);
 745
 746       // _S_construct_aux is used to implement the 21.3.1 para 15 which
 747       // requires special behaviour if _InIter is an integral type
 748       template<class _InIter>
 749         static _CharT*
 750         _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a,
 751                          __false_type)
 752         {
 753           typedef typename iterator_traits<_InIter>::iterator_category _Tag;
 754           return _S_construct(__beg, __end, __a, _Tag());
 755         }
 756
 757       template<class _InIter>
 758         static _CharT*
 759         _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a,
 760                          __true_type)
 761         {
 762           return _S_construct(static_cast<size_type>(__beg),
 763                               static_cast<value_type>(__end), __a);
 764         }
 765
 766       template<class _InIter>
 767         static _CharT*
 768         _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a)
 769         {
 770           typedef typename _Is_integer<_InIter>::_Integral _Integral;
 771           return _S_construct_aux(__beg, __end, __a, _Integral());
 772         }
 773
 774       // For Input Iterators, used in istreambuf_iterators, etc.
 775       template<class _InIter>
 776         static _CharT*
 777          _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
 778                       input_iterator_tag);
 779
 780       // For forward_iterators up to random_access_iterators, used for
 781       // string::iterator, _CharT*, etc.
 782       template<class _FwdIter>
 783         static _CharT*
 784         _S_construct(_FwdIter __beg, _FwdIter __end, const _Alloc& __a,
 785                      forward_iterator_tag);
 786
 787       static _CharT*
 788       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
 789
 790     public:
 791
 792       size_type
 793       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
 794
 795       void
 796       swap(basic_string<_CharT, _Traits, _Alloc>& __s);
 797
 798       // String operations:
 799       const _CharT*
 800       c_str() const
 801       {
 802         // MT: This assumes concurrent writes are OK.
 803         size_type __n = this->size();
 804         traits_type::assign(_M_data()[__n], _Rep::_S_terminal);
 805         return _M_data();
 806       }
 807
 808       const _CharT*
 809       data() const { return _M_data(); }
 810
 811       allocator_type
 812       get_allocator() const { return _M_dataplus; }
 813
 814       size_type
 815       find(const _CharT* __s, size_type __pos, size_type __n) const;
 816
 817       size_type
 818       find(const basic_string& __str, size_type __pos = 0) const
 819       { return this->find(__str.data(), __pos, __str.size()); }
 820
 821       size_type
 822       find(const _CharT* __s, size_type __pos = 0) const
 823       { return this->find(__s, __pos, traits_type::length(__s)); }
 824
 825       size_type
 826       find(_CharT __c, size_type __pos = 0) const;
 827
 828       size_type
 829       rfind(const basic_string& __str, size_type __pos = npos) const
 830       { return this->rfind(__str.data(), __pos, __str.size()); }
 831
 832       size_type
 833       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
 834
 835       size_type
 836       rfind(const _CharT* __s, size_type __pos = npos) const
 837       { return this->rfind(__s, __pos, traits_type::length(__s)); }
 838
 839       size_type
 840       rfind(_CharT __c, size_type __pos = npos) const;
 841
 842       size_type
 843       find_first_of(const basic_string& __str, size_type __pos = 0) const
 844       { return this->find_first_of(__str.data(), __pos, __str.size()); }
 845
 846       size_type
 847       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
 848
 849       size_type
 850       find_first_of(const _CharT* __s, size_type __pos = 0) const
 851       { return this->find_first_of(__s, __pos, traits_type::length(__s)); }
 852
 853       size_type
 854       find_first_of(_CharT __c, size_type __pos = 0) const
 855       { return this->find(__c, __pos); }
 856
 857       size_type
 858       find_last_of(const basic_string& __str, size_type __pos = npos) const
 859       { return this->find_last_of(__str.data(), __pos, __str.size()); }
 860
 861       size_type
 862       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
 863
 864       size_type
 865       find_last_of(const _CharT* __s, size_type __pos = npos) const
 866       { return this->find_last_of(__s, __pos, traits_type::length(__s)); }
 867
 868       size_type
 869       find_last_of(_CharT __c, size_type __pos = npos) const
 870       { return this->rfind(__c, __pos); }
 871
 872       size_type
 873       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
 874       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
 875
 876       size_type
 877       find_first_not_of(const _CharT* __s, size_type __pos,
 878                         size_type __n) const;
 879
 880       size_type
 881       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
 882       { return this->find_first_not_of(__s, __pos, traits_type::length(__s)); }
 883
 884       size_type
 885       find_first_not_of(_CharT __c, size_type __pos = 0) const;
 886
 887       size_type
 888       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
 889       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
 890
 891       size_type
 892       find_last_not_of(const _CharT* __s, size_type __pos,
 893                        size_type __n) const;
 894       size_type
 895       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
 896       { return this->find_last_not_of(__s, __pos, traits_type::length(__s)); }
 897
 898       size_type
 899       find_last_not_of(_CharT __c, size_type __pos = npos) const;
 900
 901       basic_string
 902       substr(size_type __pos = 0, size_type __n = npos) const
 903       {
 904         if (__pos > this->size())
 905           __throw_out_of_range("basic_string::substr");
 906         return basic_string(*this, __pos, __n);
 907       }
 908
 909       int
 910       compare(const basic_string& __str) const
 911       {
 912         size_type __size = this->size();
 913         size_type __osize = __str.size();
 914         size_type __len = std::min(__size, __osize);
 915
 916         int __r = traits_type::compare(_M_data(), __str.data(), __len);
 917         if (!__r)
 918           __r =  __size - __osize;
 919         return __r;
 920       }
 921
 922       int
 923       compare(size_type __pos, size_type __n, const basic_string& __str) const;
 924
 925       int
 926       compare(size_type __pos1, size_type __n1, const basic_string& __str,
 927               size_type __pos2, size_type __n2) const;
 928
 929       int
 930       compare(const _CharT* __s) const;
 931
 932       // _GLIBCPP_RESOLVE_LIB_DEFECTS
 933       // 5. String::compare specification questionable
 934       int
 935       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
 936
 937       int
 938       compare(size_type __pos, size_type __n1, const _CharT* __s,
 939               size_type __n2) const;
 940   };
 941
 942
 943   template<typename _CharT, typename _Traits, typename _Alloc>
 944     inline basic_string<_CharT, _Traits, _Alloc>::
 945     basic_string()
 946     : _M_dataplus(_S_empty_rep()._M_refcopy(), _Alloc()) { }
 947
 948   // operator+
 949   template<typename _CharT, typename _Traits, typename _Alloc>
 950     basic_string<_CharT, _Traits, _Alloc>
 951     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 952               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 953     {
 954       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
 955       __str.append(__rhs);
 956       return __str;
 957     }
 958
 959   template<typename _CharT, typename _Traits, typename _Alloc>
 960     basic_string<_CharT,_Traits,_Alloc>
 961     operator+(const _CharT* __lhs,
 962               const basic_string<_CharT,_Traits,_Alloc>& __rhs);
 963
 964   template<typename _CharT, typename _Traits, typename _Alloc>
 965     basic_string<_CharT,_Traits,_Alloc>
 966     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
 967
 968   template<typename _CharT, typename _Traits, typename _Alloc>
 969     inline basic_string<_CharT, _Traits, _Alloc>
 970     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 971              const _CharT* __rhs)
 972     {
 973       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
 974       __str.append(__rhs);
 975       return __str;
 976     }
 977
 978   template<typename _CharT, typename _Traits, typename _Alloc>
 979     inline basic_string<_CharT, _Traits, _Alloc>
 980     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
 981     {
 982       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
 983       typedef typename __string_type::size_type         __size_type;
 984       __string_type __str(__lhs);
 985       __str.append(__size_type(1), __rhs);
 986       return __str;
 987     }
 988
 989   // operator ==
 990   template<typename _CharT, typename _Traits, typename _Alloc>
 991     inline bool
 992     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 993                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 994     { return __lhs.compare(__rhs) == 0; }
 995
 996   template<typename _CharT, typename _Traits, typename _Alloc>
 997     inline bool
 998     operator==(const _CharT* __lhs,
 999                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1000     { return __rhs.compare(__lhs) == 0; }
1001
1002   template<typename _CharT, typename _Traits, typename _Alloc>
1003     inline bool
1004     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1005                const _CharT* __rhs)
1006     { return __lhs.compare(__rhs) == 0; }
1007
1008   // operator !=
1009   template<typename _CharT, typename _Traits, typename _Alloc>
1010     inline bool
1011     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1012                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1013     { return __rhs.compare(__lhs) != 0; }
1014
1015   template<typename _CharT, typename _Traits, typename _Alloc>
1016     inline bool
1017     operator!=(const _CharT* __lhs,
1018                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1019     { return __rhs.compare(__lhs) != 0; }
1020
1021   template<typename _CharT, typename _Traits, typename _Alloc>
1022     inline bool
1023     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1024                const _CharT* __rhs)
1025     { return __lhs.compare(__rhs) != 0; }
1026
1027   // operator <
1028   template<typename _CharT, typename _Traits, typename _Alloc>
1029     inline bool
1030     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1031               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1032     { return __lhs.compare(__rhs) < 0; }
1033
1034   template<typename _CharT, typename _Traits, typename _Alloc>
1035     inline bool
1036     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1037               const _CharT* __rhs)
1038     { return __lhs.compare(__rhs) < 0; }
1039
1040   template<typename _CharT, typename _Traits, typename _Alloc>
1041     inline bool
1042     operator<(const _CharT* __lhs,
1043               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1044     { return __rhs.compare(__lhs) > 0; }
1045
1046   // operator >
1047   template<typename _CharT, typename _Traits, typename _Alloc>
1048     inline bool
1049     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1050               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1051     { return __lhs.compare(__rhs) > 0; }
1052
1053   template<typename _CharT, typename _Traits, typename _Alloc>
1054     inline bool
1055     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1056               const _CharT* __rhs)
1057     { return __lhs.compare(__rhs) > 0; }
1058
1059   template<typename _CharT, typename _Traits, typename _Alloc>
1060     inline bool
1061     operator>(const _CharT* __lhs,
1062               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1063     { return __rhs.compare(__lhs) < 0; }
1064
1065   // operator <=
1066   template<typename _CharT, typename _Traits, typename _Alloc>
1067     inline bool
1068     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1069                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1070     { return __lhs.compare(__rhs) <= 0; }
1071
1072   template<typename _CharT, typename _Traits, typename _Alloc>
1073     inline bool
1074     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1075                const _CharT* __rhs)
1076     { return __lhs.compare(__rhs) <= 0; }
1077
1078   template<typename _CharT, typename _Traits, typename _Alloc>
1079     inline bool
1080     operator<=(const _CharT* __lhs,
1081                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1082   { return __rhs.compare(__lhs) >= 0; }
1083
1084   // operator >=
1085   template<typename _CharT, typename _Traits, typename _Alloc>
1086     inline bool
1087     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1088                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1089     { return __lhs.compare(__rhs) >= 0; }
1090
1091   template<typename _CharT, typename _Traits, typename _Alloc>
1092     inline bool
1093     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1094                const _CharT* __rhs)
1095     { return __lhs.compare(__rhs) >= 0; }
1096
1097   template<typename _CharT, typename _Traits, typename _Alloc>
1098     inline bool
1099     operator>=(const _CharT* __lhs,
1100              const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1101     { return __rhs.compare(__lhs) <= 0; }
1102
1103
1104   template<typename _CharT, typename _Traits, typename _Alloc>
1105     inline void
1106     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
1107          basic_string<_CharT, _Traits, _Alloc>& __rhs)
1108     { __lhs.swap(__rhs); }
1109
1110   template<typename _CharT, typename _Traits, typename _Alloc>
1111     basic_istream<_CharT, _Traits>&
1112     operator>>(basic_istream<_CharT, _Traits>& __is,
1113                basic_string<_CharT, _Traits, _Alloc>& __str);
1114
1115   template<typename _CharT, typename _Traits, typename _Alloc>
1116     basic_ostream<_CharT, _Traits>&
1117     operator<<(basic_ostream<_CharT, _Traits>& __os,
1118                const basic_string<_CharT, _Traits, _Alloc>& __str);
1119
1120   template<typename _CharT, typename _Traits, typename _Alloc>
1121     basic_istream<_CharT,_Traits>&
1122     getline(basic_istream<_CharT, _Traits>& __is,
1123             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
1124
1125   template<typename _CharT, typename _Traits, typename _Alloc>
1126     inline basic_istream<_CharT,_Traits>&
1127     getline(basic_istream<_CharT, _Traits>& __is,
1128             basic_string<_CharT, _Traits, _Alloc>& __str);
1129 } // namespace std
1130
1131 #endif /* _CPP_BITS_STRING_H */