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

   1 // Components for manipulating sequences of characters -*- C++ -*-
   2
   3 // Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 //
  31 // ISO C++ 14882: 21 Strings library
  32 //
  33
  34 /** @file basic_string.h
  35  *  This is an internal header file, included by other library headers.
  36  *  You should not attempt to use it directly.
  37  */
  38
  39 #ifndef _CPP_BITS_STRING_H
  40 #define _CPP_BITS_STRING_H      1
  41
  42 #pragma GCC system_header
  43
  44 #include <bits/atomicity.h>
  45
  46 namespace std
  47 {
  48   // Documentation?  What's that?
  49   // Nathan Myers <ncm@cantrip.org>.
  50   //
  51   // A string looks like this:
  52   //
  53   //                                    [_Rep]
  54   //                                    _M_length
  55   //  [basic_string<char_type>]         _M_capacity
  56   //  _M_dataplus                       _M_state
  57   //  _M_p ---------------->            unnamed array of char_type
  58
  59   // Where the _M_p points to the first character in the string, and
  60   // you cast it to a pointer-to-_Rep and subtract 1 to get a
  61   // pointer to the header.
  62
  63   // This approach has the enormous advantage that a string object
  64   // requires only one allocation.  All the ugliness is confined
  65   // within a single pair of inline functions, which each compile to
  66   // a single "add" instruction: _Rep::_M_data(), and
  67   // string::_M_rep(); and the allocation function which gets a
  68   // block of raw bytes and with room enough and constructs a _Rep
  69   // object at the front.
  70
  71   // The reason you want _M_data pointing to the character array and
  72   // not the _Rep is so that the debugger can see the string
  73   // contents. (Probably we should add a non-inline member to get
  74   // the _Rep for the debugger to use, so users can check the actual
  75   // string length.)
  76
  77   // Note that the _Rep object is a POD so that you can have a
  78   // static "empty string" _Rep object already "constructed" before
  79   // static constructors have run.  The reference-count encoding is
  80   // chosen so that a 0 indicates one reference, so you never try to
  81   // destroy the empty-string _Rep object.
  82
  83   // All but the last paragraph is considered pretty conventional
  84   // for a C++ string implementation.
  85
  86   // 21.3  Template class basic_string
  87   template<typename _CharT, typename _Traits, typename _Alloc>
  88     class basic_string
  89     {
  90       // Types:
  91     public:
  92       typedef _Traits                                       traits_type;
  93       typedef typename _Traits::char_type                   value_type;
  94       typedef _Alloc                                        allocator_type;
  95       typedef typename _Alloc::size_type                    size_type;
  96       typedef typename _Alloc::difference_type              difference_type;
  97       typedef typename _Alloc::reference                    reference;
  98       typedef typename _Alloc::const_reference              const_reference;
  99       typedef typename _Alloc::pointer                      pointer;
 100       typedef typename _Alloc::const_pointer                const_pointer;
 101       typedef __normal_iterator<pointer, basic_string>      iterator;
 102       typedef __normal_iterator<const_pointer, basic_string> const_iterator;
 103       typedef reverse_iterator<const_iterator>  const_reverse_iterator;
 104       typedef reverse_iterator<iterator>                    reverse_iterator;
 105
 106     private:
 107       // _Rep: string representation
 108       //   Invariants:
 109       //   1. String really contains _M_length + 1 characters; last is set
 110       //      to 0 only on call to c_str().  We avoid instantiating
 111       //      _CharT() where the interface does not require it.
 112       //   2. _M_capacity >= _M_length
 113       //      Allocated memory is always _M_capacity + (1 * sizeof(_CharT)).
 114       //   3. _M_references has three states:
 115       //      -1: leaked, one reference, no ref-copies allowed, non-const.
 116       //       0: one reference, non-const.
 117       //     n>0: n + 1 references, operations require a lock, const.
 118       //   4. All fields==0 is an empty string, given the extra storage
 119       //      beyond-the-end for a null terminator; thus, the shared
 120       //      empty string representation needs no constructor.
 121
 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       {
 535         iterator __p = _M_check(__pos1);
 536         this->replace(__p, __p, __str._M_ibegin(), __str._M_iend());
 537         return *this;
 538       }
 539
 540       basic_string&
 541       insert(size_type __pos1, const basic_string& __str,
 542              size_type __pos2, size_type __n)
 543       {
 544         iterator __p = _M_check(__pos1);
 545         this->replace(__p, __p, __str._M_check(__pos2),
 546                       __str._M_fold(__pos2, __n));
 547         return *this;
 548       }
 549
 550       basic_string&
 551       insert(size_type __pos, const _CharT* __s, size_type __n)
 552       {
 553         iterator __p = _M_check(__pos);
 554         this->replace(__p, __p, __s, __s + __n);
 555         return *this;
 556       }
 557
 558       basic_string&
 559       insert(size_type __pos, const _CharT* __s)
 560       { return this->insert(__pos, __s, traits_type::length(__s)); }
 561
 562       basic_string&
 563       insert(size_type __pos, size_type __n, _CharT __c)
 564       {
 565         this->insert(_M_check(__pos), __n, __c);
 566         return *this;
 567       }
 568
 569       iterator
 570       insert(iterator __p, _CharT __c = _CharT())
 571       {
 572         size_type __pos = __p - _M_ibegin();
 573         this->insert(_M_check(__pos), size_type(1), __c);
 574         _M_rep()->_M_set_leaked();
 575         return this->_M_ibegin() + __pos;
 576       }
 577
 578       basic_string&
 579       erase(size_type __pos = 0, size_type __n = npos)
 580       {
 581         return this->replace(_M_check(__pos), _M_fold(__pos, __n),
 582                              _M_data(), _M_data());
 583       }
 584
 585       iterator
 586       erase(iterator __position)
 587       {
 588         size_type __i = __position - _M_ibegin();
 589         this->replace(__position, __position + 1, _M_data(), _M_data());
 590         _M_rep()->_M_set_leaked();
 591         return _M_ibegin() + __i;
 592       }
 593
 594       iterator
 595       erase(iterator __first, iterator __last)
 596       {
 597         size_type __i = __first - _M_ibegin();
 598         this->replace(__first, __last, _M_data(), _M_data());
 599         _M_rep()->_M_set_leaked();
 600        return _M_ibegin() + __i;
 601       }
 602
 603       basic_string&
 604       replace(size_type __pos, size_type __n, const basic_string& __str)
 605       {
 606         return this->replace(_M_check(__pos), _M_fold(__pos, __n),
 607                               __str.begin(), __str.end());
 608       }
 609
 610       basic_string&
 611       replace(size_type __pos1, size_type __n1, const basic_string& __str,
 612               size_type __pos2, size_type __n2);
 613
 614       basic_string&
 615       replace(size_type __pos, size_type __n1, const _CharT* __s,
 616               size_type __n2)
 617       {
 618         return this->replace(_M_check(__pos), _M_fold(__pos, __n1),
 619                              __s, __s + __n2);
 620       }
 621
 622       basic_string&
 623       replace(size_type __pos, size_type __n1, const _CharT* __s)
 624       {
 625         return this->replace(_M_check(__pos), _M_fold(__pos, __n1),
 626                              __s, __s + traits_type::length(__s));
 627       }
 628
 629       basic_string&
 630       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
 631       {
 632         return this->replace(_M_check(__pos), _M_fold(__pos, __n1), __n2, __c);
 633       }
 634
 635       basic_string&
 636       replace(iterator __i1, iterator __i2, const basic_string& __str)
 637       { return this->replace(__i1, __i2, __str.begin(), __str.end()); }
 638
 639       basic_string&
 640       replace(iterator __i1, iterator __i2,
 641                            const _CharT* __s, size_type __n)
 642       { return this->replace(__i1, __i2, __s, __s + __n); }
 643
 644       basic_string&
 645       replace(iterator __i1, iterator __i2, const _CharT* __s)
 646       { return this->replace(__i1, __i2, __s,
 647                              __s + traits_type::length(__s)); }
 648
 649       basic_string&
 650       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c);
 651
 652       template<class _InputIterator>
 653         basic_string&
 654         replace(iterator __i1, iterator __i2,
 655                 _InputIterator __k1, _InputIterator __k2)
 656         { return _M_replace(__i1, __i2, __k1, __k2,
 657              typename iterator_traits<_InputIterator>::iterator_category()); }
 658
 659     private:
 660       template<class _InputIterator>
 661         basic_string&
 662         _M_replace(iterator __i1, iterator __i2, _InputIterator __k1,
 663                    _InputIterator __k2, input_iterator_tag);
 664
 665       template<class _ForwardIterator>
 666         basic_string&
 667         _M_replace_safe(iterator __i1, iterator __i2, _ForwardIterator __k1,
 668                    _ForwardIterator __k2);
 669
 670       // _S_construct_aux is used to implement the 21.3.1 para 15 which
 671       // requires special behaviour if _InIter is an integral type
 672       template<class _InIter>
 673         static _CharT*
 674         _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a,
 675                          __false_type)
 676         {
 677           typedef typename iterator_traits<_InIter>::iterator_category _Tag;
 678           return _S_construct(__beg, __end, __a, _Tag());
 679         }
 680
 681       template<class _InIter>
 682         static _CharT*
 683         _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a,
 684                          __true_type)
 685         {
 686           return _S_construct(static_cast<size_type>(__beg),
 687                               static_cast<value_type>(__end), __a);
 688         }
 689
 690       template<class _InIter>
 691         static _CharT*
 692         _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a)
 693         {
 694           typedef typename _Is_integer<_InIter>::_Integral _Integral;
 695           return _S_construct_aux(__beg, __end, __a, _Integral());
 696         }
 697
 698       // For Input Iterators, used in istreambuf_iterators, etc.
 699       template<class _InIter>
 700         static _CharT*
 701          _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
 702                       input_iterator_tag);
 703
 704       // For forward_iterators up to random_access_iterators, used for
 705       // string::iterator, _CharT*, etc.
 706       template<class _FwdIter>
 707         static _CharT*
 708         _S_construct(_FwdIter __end, _FwdIter __beg, const _Alloc& __a,
 709                      forward_iterator_tag);
 710
 711       static _CharT*
 712       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
 713
 714     public:
 715
 716       size_type
 717       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
 718
 719       void
 720       swap(basic_string<_CharT, _Traits, _Alloc>& __s);
 721
 722       // String operations:
 723       const _CharT*
 724       c_str() const
 725       {
 726         // MT: This assumes concurrent writes are OK.
 727         size_type __n = this->size();
 728         traits_type::assign(_M_data()[__n], _Rep::_S_terminal);
 729         return _M_data();
 730       }
 731
 732       const _CharT*
 733       data() const { return _M_data(); }
 734
 735       allocator_type
 736       get_allocator() const { return _M_dataplus; }
 737
 738       size_type
 739       find(const _CharT* __s, size_type __pos, size_type __n) const;
 740
 741       size_type
 742       find(const basic_string& __str, size_type __pos = 0) const
 743       { return this->find(__str.data(), __pos, __str.size()); }
 744
 745       size_type
 746       find(const _CharT* __s, size_type __pos = 0) const
 747       { return this->find(__s, __pos, traits_type::length(__s)); }
 748
 749       size_type
 750       find(_CharT __c, size_type __pos = 0) const;
 751
 752       size_type
 753       rfind(const basic_string& __str, size_type __pos = npos) const
 754       { return this->rfind(__str.data(), __pos, __str.size()); }
 755
 756       size_type
 757       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
 758
 759       size_type
 760       rfind(const _CharT* __s, size_type __pos = npos) const
 761       { return this->rfind(__s, __pos, traits_type::length(__s)); }
 762
 763       size_type
 764       rfind(_CharT __c, size_type __pos = npos) const;
 765
 766       size_type
 767       find_first_of(const basic_string& __str, size_type __pos = 0) const
 768       { return this->find_first_of(__str.data(), __pos, __str.size()); }
 769
 770       size_type
 771       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
 772
 773       size_type
 774       find_first_of(const _CharT* __s, size_type __pos = 0) const
 775       { return this->find_first_of(__s, __pos, traits_type::length(__s)); }
 776
 777       size_type
 778       find_first_of(_CharT __c, size_type __pos = 0) const
 779       { return this->find(__c, __pos); }
 780
 781       size_type
 782       find_last_of(const basic_string& __str, size_type __pos = npos) const
 783       { return this->find_last_of(__str.data(), __pos, __str.size()); }
 784
 785       size_type
 786       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
 787
 788       size_type
 789       find_last_of(const _CharT* __s, size_type __pos = npos) const
 790       { return this->find_last_of(__s, __pos, traits_type::length(__s)); }
 791
 792       size_type
 793       find_last_of(_CharT __c, size_type __pos = npos) const
 794       { return this->rfind(__c, __pos); }
 795
 796       size_type
 797       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
 798       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
 799
 800       size_type
 801       find_first_not_of(const _CharT* __s, size_type __pos,
 802                         size_type __n) const;
 803
 804       size_type
 805       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
 806       { return this->find_first_not_of(__s, __pos, traits_type::length(__s)); }
 807
 808       size_type
 809       find_first_not_of(_CharT __c, size_type __pos = 0) const;
 810
 811       size_type
 812       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
 813       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
 814
 815       size_type
 816       find_last_not_of(const _CharT* __s, size_type __pos,
 817                        size_type __n) const;
 818       size_type
 819       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
 820       { return this->find_last_not_of(__s, __pos, traits_type::length(__s)); }
 821
 822       size_type
 823       find_last_not_of(_CharT __c, size_type __pos = npos) const;
 824
 825       basic_string
 826       substr(size_type __pos = 0, size_type __n = npos) const
 827       {
 828         if (__pos > this->size())
 829           __throw_out_of_range("basic_string::substr");
 830         return basic_string(*this, __pos, __n);
 831       }
 832
 833       int
 834       compare(const basic_string& __str) const
 835       {
 836         size_type __size = this->size();
 837         size_type __osize = __str.size();
 838         size_type __len = min(__size, __osize);
 839
 840         int __r = traits_type::compare(_M_data(), __str.data(), __len);
 841         if (!__r)
 842           __r =  __size - __osize;
 843         return __r;
 844       }
 845
 846       int
 847       compare(size_type __pos, size_type __n, const basic_string& __str) const;
 848
 849       int
 850       compare(size_type __pos1, size_type __n1, const basic_string& __str,
 851               size_type __pos2, size_type __n2) const;
 852
 853       int
 854       compare(const _CharT* __s) const;
 855
 856 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
 857 // 5. String::compare specification questionable
 858       int
 859       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
 860
 861       int
 862       compare(size_type __pos, size_type __n1, const _CharT* __s,
 863               size_type __n2) const;
 864 #endif
 865   };
 866
 867
 868   template<typename _CharT, typename _Traits, typename _Alloc>
 869     inline basic_string<_CharT, _Traits, _Alloc>::
 870     basic_string()
 871     : _M_dataplus(_S_empty_rep()._M_refcopy(), _Alloc()) { }
 872
 873   // operator+
 874   template<typename _CharT, typename _Traits, typename _Alloc>
 875     basic_string<_CharT, _Traits, _Alloc>
 876     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 877               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 878     {
 879       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
 880       __str.append(__rhs);
 881       return __str;
 882     }
 883
 884   template<typename _CharT, typename _Traits, typename _Alloc>
 885     basic_string<_CharT,_Traits,_Alloc>
 886     operator+(const _CharT* __lhs,
 887               const basic_string<_CharT,_Traits,_Alloc>& __rhs);
 888
 889   template<typename _CharT, typename _Traits, typename _Alloc>
 890     basic_string<_CharT,_Traits,_Alloc>
 891     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
 892
 893   template<typename _CharT, typename _Traits, typename _Alloc>
 894     inline basic_string<_CharT, _Traits, _Alloc>
 895     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 896              const _CharT* __rhs)
 897     {
 898       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
 899       __str.append(__rhs);
 900       return __str;
 901     }
 902
 903   template<typename _CharT, typename _Traits, typename _Alloc>
 904     inline basic_string<_CharT, _Traits, _Alloc>
 905     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
 906     {
 907       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
 908       typedef typename __string_type::size_type         __size_type;
 909       __string_type __str(__lhs);
 910       __str.append(__size_type(1), __rhs);
 911       return __str;
 912     }
 913
 914   // operator ==
 915   template<typename _CharT, typename _Traits, typename _Alloc>
 916     inline bool
 917     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 918                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 919     { return __lhs.compare(__rhs) == 0; }
 920
 921   template<typename _CharT, typename _Traits, typename _Alloc>
 922     inline bool
 923     operator==(const _CharT* __lhs,
 924                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 925     { return __rhs.compare(__lhs) == 0; }
 926
 927   template<typename _CharT, typename _Traits, typename _Alloc>
 928     inline bool
 929     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 930                const _CharT* __rhs)
 931     { return __lhs.compare(__rhs) == 0; }
 932
 933   // operator !=
 934   template<typename _CharT, typename _Traits, typename _Alloc>
 935     inline bool
 936     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 937                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 938     { return __rhs.compare(__lhs) != 0; }
 939
 940   template<typename _CharT, typename _Traits, typename _Alloc>
 941     inline bool
 942     operator!=(const _CharT* __lhs,
 943                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 944     { return __rhs.compare(__lhs) != 0; }
 945
 946   template<typename _CharT, typename _Traits, typename _Alloc>
 947     inline bool
 948     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 949                const _CharT* __rhs)
 950     { return __lhs.compare(__rhs) != 0; }
 951
 952   // operator <
 953   template<typename _CharT, typename _Traits, typename _Alloc>
 954     inline bool
 955     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 956               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 957     { return __lhs.compare(__rhs) < 0; }
 958
 959   template<typename _CharT, typename _Traits, typename _Alloc>
 960     inline bool
 961     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 962               const _CharT* __rhs)
 963     { return __lhs.compare(__rhs) < 0; }
 964
 965   template<typename _CharT, typename _Traits, typename _Alloc>
 966     inline bool
 967     operator<(const _CharT* __lhs,
 968               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 969     { return __rhs.compare(__lhs) > 0; }
 970
 971   // operator >
 972   template<typename _CharT, typename _Traits, typename _Alloc>
 973     inline bool
 974     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 975               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 976     { return __lhs.compare(__rhs) > 0; }
 977
 978   template<typename _CharT, typename _Traits, typename _Alloc>
 979     inline bool
 980     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 981               const _CharT* __rhs)
 982     { return __lhs.compare(__rhs) > 0; }
 983
 984   template<typename _CharT, typename _Traits, typename _Alloc>
 985     inline bool
 986     operator>(const _CharT* __lhs,
 987               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 988     { return __rhs.compare(__lhs) < 0; }
 989
 990   // operator <=
 991   template<typename _CharT, typename _Traits, typename _Alloc>
 992     inline bool
 993     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 994                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 995     { return __lhs.compare(__rhs) <= 0; }
 996
 997   template<typename _CharT, typename _Traits, typename _Alloc>
 998     inline bool
 999     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1000                const _CharT* __rhs)
1001     { return __lhs.compare(__rhs) <= 0; }
1002
1003   template<typename _CharT, typename _Traits, typename _Alloc>
1004     inline bool
1005     operator<=(const _CharT* __lhs,
1006                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1007   { return __rhs.compare(__lhs) >= 0; }
1008
1009   // operator >=
1010   template<typename _CharT, typename _Traits, typename _Alloc>
1011     inline bool
1012     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1013                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1014     { return __lhs.compare(__rhs) >= 0; }
1015
1016   template<typename _CharT, typename _Traits, typename _Alloc>
1017     inline bool
1018     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
1019                const _CharT* __rhs)
1020     { return __lhs.compare(__rhs) >= 0; }
1021
1022   template<typename _CharT, typename _Traits, typename _Alloc>
1023     inline bool
1024     operator>=(const _CharT* __lhs,
1025              const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1026     { return __rhs.compare(__lhs) <= 0; }
1027
1028
1029   template<typename _CharT, typename _Traits, typename _Alloc>
1030     inline void
1031     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
1032          basic_string<_CharT, _Traits, _Alloc>& __rhs)
1033     { __lhs.swap(__rhs); }
1034
1035   template<typename _CharT, typename _Traits, typename _Alloc>
1036     basic_istream<_CharT, _Traits>&
1037     operator>>(basic_istream<_CharT, _Traits>& __is,
1038                basic_string<_CharT, _Traits, _Alloc>& __str);
1039
1040   template<typename _CharT, typename _Traits, typename _Alloc>
1041     basic_ostream<_CharT, _Traits>&
1042     operator<<(basic_ostream<_CharT, _Traits>& __os,
1043                const basic_string<_CharT, _Traits, _Alloc>& __str);
1044
1045   template<typename _CharT, typename _Traits, typename _Alloc>
1046     basic_istream<_CharT,_Traits>&
1047     getline(basic_istream<_CharT, _Traits>& __is,
1048             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
1049
1050   template<typename _CharT, typename _Traits, typename _Alloc>
1051     inline basic_istream<_CharT,_Traits>&
1052     getline(basic_istream<_CharT, _Traits>& __is,
1053             basic_string<_CharT, _Traits, _Alloc>& __str);
1054 } // namespace std
1055
1056 #endif /* _CPP_BITS_STRING_H */