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