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