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         return this->assign(__str._M_check(__pos), __str._M_fold(__pos, __n));
 482       }
 483
 484       basic_string&
 485       assign(const _CharT* __s, size_type __n)
 486       { return this->assign(__s, __s + __n); }
 487
 488       basic_string&
 489       assign(const _CharT* __s)
 490       { return this->assign(__s, __s + traits_type::length(__s)); }
 491
 492       basic_string&
 493       assign(size_type __n, _CharT __c)
 494       { return this->replace(_M_ibegin(), _M_iend(), __n, __c); }
 495
 496       template<class _InputIterator>
 497         basic_string&
 498         assign(_InputIterator __first, _InputIterator __last)
 499         { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
 500
 501       void
 502       insert(iterator __p, size_type __n, _CharT __c)
 503       { this->replace(__p, __p, __n, __c);  }
 504
 505       template<class _InputIterator>
 506         void insert(iterator __p, _InputIterator __beg, _InputIterator __end)
 507         { this->replace(__p, __p, __beg, __end); }
 508
 509       basic_string&
 510       insert(size_type __pos1, const basic_string& __str)
 511       {
 512         iterator __p = _M_check(__pos1);
 513         this->replace(__p, __p, __str._M_ibegin(), __str._M_iend());
 514         return *this;
 515       }
 516
 517       basic_string&
 518       insert(size_type __pos1, const basic_string& __str,
 519              size_type __pos2, size_type __n)
 520       {
 521         iterator __p = _M_check(__pos1);
 522         this->replace(__p, __p, __str._M_check(__pos2),
 523                       __str._M_fold(__pos2, __n));
 524         return *this;
 525       }
 526
 527       basic_string&
 528       insert(size_type __pos, const _CharT* __s, size_type __n)
 529       {
 530         iterator __p = _M_check(__pos);
 531         this->replace(__p, __p, __s, __s + __n);
 532         return *this;
 533       }
 534
 535       basic_string&
 536       insert(size_type __pos, const _CharT* __s)
 537       { return this->insert(__pos, __s, traits_type::length(__s)); }
 538
 539       basic_string&
 540       insert(size_type __pos, size_type __n, _CharT __c)
 541       {
 542         this->insert(_M_check(__pos), __n, __c);
 543         return *this;
 544       }
 545
 546       iterator
 547       insert(iterator __p, _CharT __c = _CharT())
 548       {
 549         size_type __pos = __p - _M_ibegin();
 550         this->insert(_M_check(__pos), size_type(1), __c);
 551         _M_rep()->_M_set_leaked();
 552         return this->_M_ibegin() + __pos;
 553       }
 554
 555       basic_string&
 556       erase(size_type __pos = 0, size_type __n = npos)
 557       {
 558         return this->replace(_M_check(__pos), _M_fold(__pos, __n),
 559                              _M_data(), _M_data());
 560       }
 561
 562       iterator
 563       erase(iterator __position)
 564       {
 565         size_type __i = __position - _M_ibegin();
 566         this->replace(__position, __position + 1, _M_data(), _M_data());
 567         _M_rep()->_M_set_leaked();
 568         return _M_ibegin() + __i;
 569       }
 570
 571       iterator
 572       erase(iterator __first, iterator __last)
 573       {
 574         size_type __i = __first - _M_ibegin();
 575         this->replace(__first, __last, _M_data(), _M_data());
 576         _M_rep()->_M_set_leaked();
 577        return _M_ibegin() + __i;
 578       }
 579
 580       basic_string&
 581       replace(size_type __pos, size_type __n, const basic_string& __str)
 582       {
 583         return this->replace(_M_check(__pos), _M_fold(__pos, __n),
 584                               __str.begin(), __str.end());
 585       }
 586
 587       basic_string&
 588       replace(size_type __pos1, size_type __n1, const basic_string& __str,
 589               size_type __pos2, size_type __n2);
 590
 591       basic_string&
 592       replace(size_type __pos, size_type __n1, const _CharT* __s,
 593               size_type __n2)
 594       {
 595         return this->replace(_M_check(__pos), _M_fold(__pos, __n1),
 596                              __s, __s + __n2);
 597       }
 598
 599       basic_string&
 600       replace(size_type __pos, size_type __n1, const _CharT* __s)
 601       {
 602         return this->replace(_M_check(__pos), _M_fold(__pos, __n1),
 603                              __s, __s + traits_type::length(__s));
 604       }
 605
 606       basic_string&
 607       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
 608       {
 609         return this->replace(_M_check(__pos), _M_fold(__pos, __n1), __n2, __c);
 610       }
 611
 612       basic_string&
 613       replace(iterator __i1, iterator __i2, const basic_string& __str)
 614       { return this->replace(__i1, __i2, __str.begin(), __str.end()); }
 615
 616       basic_string&
 617       replace(iterator __i1, iterator __i2,
 618                            const _CharT* __s, size_type __n)
 619       { return this->replace(__i1, __i2, __s, __s + __n); }
 620
 621       basic_string&
 622       replace(iterator __i1, iterator __i2, const _CharT* __s)
 623       { return this->replace(__i1, __i2, __s,
 624                              __s + traits_type::length(__s)); }
 625
 626       basic_string&
 627       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c);
 628
 629       template<class _InputIterator>
 630         basic_string&
 631         replace(iterator __i1, iterator __i2,
 632                 _InputIterator __k1, _InputIterator __k2)
 633         { return _M_replace(__i1, __i2, __k1, __k2,
 634              typename iterator_traits<_InputIterator>::iterator_category()); }
 635
 636     private:
 637       template<class _InputIterator>
 638         basic_string&
 639         _M_replace(iterator __i1, iterator __i2, _InputIterator __k1,
 640                    _InputIterator __k2, input_iterator_tag);
 641
 642       template<class _ForwardIterator>
 643         basic_string&
 644         _M_replace_safe(iterator __i1, iterator __i2, _ForwardIterator __k1,
 645                    _ForwardIterator __k2);
 646
 647       // _S_construct_aux is used to implement the 21.3.1 para 15 which
 648       // requires special behaviour if _InIter is an integral type
 649       template<class _InIter>
 650         static _CharT*
 651         _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a,
 652                          __false_type)
 653         {
 654           typedef typename iterator_traits<_InIter>::iterator_category _Tag;
 655           return _S_construct(__beg, __end, __a, _Tag());
 656         }
 657
 658       template<class _InIter>
 659         static _CharT*
 660         _S_construct_aux(_InIter __beg, _InIter __end, const _Alloc& __a,
 661                          __true_type)
 662         {
 663           return _S_construct(static_cast<size_type>(__beg),
 664                               static_cast<value_type>(__end), __a);
 665         }
 666
 667       template<class _InIter>
 668         static _CharT*
 669         _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a)
 670         {
 671           typedef typename _Is_integer<_InIter>::_Integral _Integral;
 672           return _S_construct_aux(__beg, __end, __a, _Integral());
 673         }
 674
 675       // For Input Iterators, used in istreambuf_iterators, etc.
 676       template<class _InIter>
 677         static _CharT*
 678          _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
 679                       input_iterator_tag);
 680
 681       // For forward_iterators up to random_access_iterators, used for
 682       // string::iterator, _CharT*, etc.
 683       template<class _FwdIter>
 684         static _CharT*
 685         _S_construct(_FwdIter __end, _FwdIter __beg, const _Alloc& __a,
 686                      forward_iterator_tag);
 687
 688       static _CharT*
 689       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
 690
 691     public:
 692
 693       size_type
 694       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
 695
 696       void
 697       swap(basic_string<_CharT, _Traits, _Alloc>& __s);
 698
 699       // String operations:
 700       const _CharT*
 701       c_str() const
 702       {
 703         // MT: This assumes concurrent writes are OK.
 704         size_type __n = this->size();
 705         traits_type::assign(_M_data()[__n], _Rep::_S_terminal);
 706         return _M_data();
 707       }
 708
 709       const _CharT*
 710       data() const { return _M_data(); }
 711
 712       allocator_type
 713       get_allocator() const { return _M_dataplus; }
 714
 715       size_type
 716       find(const _CharT* __s, size_type __pos, size_type __n) const;
 717
 718       size_type
 719       find(const basic_string& __str, size_type __pos = 0) const
 720       { return this->find(__str.data(), __pos, __str.size()); }
 721
 722       size_type
 723       find(const _CharT* __s, size_type __pos = 0) const
 724       { return this->find(__s, __pos, traits_type::length(__s)); }
 725
 726       size_type
 727       find(_CharT __c, size_type __pos = 0) const;
 728
 729       size_type
 730       rfind(const basic_string& __str, size_type __pos = npos) const
 731       { return this->rfind(__str.data(), __pos, __str.size()); }
 732
 733       size_type
 734       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
 735
 736       size_type
 737       rfind(const _CharT* __s, size_type __pos = npos) const
 738       { return this->rfind(__s, __pos, traits_type::length(__s)); }
 739
 740       size_type
 741       rfind(_CharT __c, size_type __pos = npos) const;
 742
 743       size_type
 744       find_first_of(const basic_string& __str, size_type __pos = 0) const
 745       { return this->find_first_of(__str.data(), __pos, __str.size()); }
 746
 747       size_type
 748       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
 749
 750       size_type
 751       find_first_of(const _CharT* __s, size_type __pos = 0) const
 752       { return this->find_first_of(__s, __pos, traits_type::length(__s)); }
 753
 754       size_type
 755       find_first_of(_CharT __c, size_type __pos = 0) const
 756       { return this->find(__c, __pos); }
 757
 758       size_type
 759       find_last_of(const basic_string& __str, size_type __pos = npos) const
 760       { return this->find_last_of(__str.data(), __pos, __str.size()); }
 761
 762       size_type
 763       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
 764
 765       size_type
 766       find_last_of(const _CharT* __s, size_type __pos = npos) const
 767       { return this->find_last_of(__s, __pos, traits_type::length(__s)); }
 768
 769       size_type
 770       find_last_of(_CharT __c, size_type __pos = npos) const
 771       { return this->rfind(__c, __pos); }
 772
 773       size_type
 774       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
 775       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
 776
 777       size_type
 778       find_first_not_of(const _CharT* __s, size_type __pos,
 779                         size_type __n) const;
 780
 781       size_type
 782       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
 783       { return this->find_first_not_of(__s, __pos, traits_type::length(__s)); }
 784
 785       size_type
 786       find_first_not_of(_CharT __c, size_type __pos = 0) const;
 787
 788       size_type
 789       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
 790       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
 791
 792       size_type
 793       find_last_not_of(const _CharT* __s, size_type __pos,
 794                        size_type __n) const;
 795       size_type
 796       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
 797       { return this->find_last_not_of(__s, __pos, traits_type::length(__s)); }
 798
 799       size_type
 800       find_last_not_of(_CharT __c, size_type __pos = npos) const;
 801
 802       basic_string
 803       substr(size_type __pos = 0, size_type __n = npos) const
 804       {
 805         if (__pos > this->size())
 806           __throw_out_of_range("basic_string::substr");
 807         return basic_string(*this, __pos, __n);
 808       }
 809
 810       int
 811       compare(const basic_string& __str) const
 812       {
 813         size_type __size = this->size();
 814         size_type __osize = __str.size();
 815         size_type __len = min(__size, __osize);
 816
 817         int __r = traits_type::compare(_M_data(), __str.data(), __len);
 818         if (!__r)
 819           __r =  __size - __osize;
 820         return __r;
 821       }
 822
 823       int
 824       compare(size_type __pos, size_type __n, const basic_string& __str) const;
 825
 826       int
 827       compare(size_type __pos1, size_type __n1, const basic_string& __str,
 828               size_type __pos2, size_type __n2) const;
 829
 830       int
 831       compare(const _CharT* __s) const;
 832
 833 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
 834 // 5. String::compare specification questionable
 835       int
 836       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
 837
 838       int
 839       compare(size_type __pos, size_type __n1, const _CharT* __s,
 840               size_type __n2) const;
 841 #endif
 842   };
 843
 844
 845   template<typename _CharT, typename _Traits, typename _Alloc>
 846     inline basic_string<_CharT, _Traits, _Alloc>::
 847     basic_string()
 848     : _M_dataplus(_S_empty_rep()._M_refcopy(), _Alloc()) { }
 849
 850   // operator+
 851   template<typename _CharT, typename _Traits, typename _Alloc>
 852     basic_string<_CharT, _Traits, _Alloc>
 853     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 854               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 855     {
 856       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
 857       __str.append(__rhs);
 858       return __str;
 859     }
 860
 861   template<typename _CharT, typename _Traits, typename _Alloc>
 862     basic_string<_CharT,_Traits,_Alloc>
 863     operator+(const _CharT* __lhs,
 864               const basic_string<_CharT,_Traits,_Alloc>& __rhs);
 865
 866   template<typename _CharT, typename _Traits, typename _Alloc>
 867     basic_string<_CharT,_Traits,_Alloc>
 868     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
 869
 870   template<typename _CharT, typename _Traits, typename _Alloc>
 871     inline basic_string<_CharT, _Traits, _Alloc>
 872     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 873              const _CharT* __rhs)
 874     {
 875       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
 876       __str.append(__rhs);
 877       return __str;
 878     }
 879
 880   template<typename _CharT, typename _Traits, typename _Alloc>
 881     inline basic_string<_CharT, _Traits, _Alloc>
 882     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
 883     {
 884       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
 885       typedef typename __string_type::size_type         __size_type;
 886       __string_type __str(__lhs);
 887       __str.append(__size_type(1), __rhs);
 888       return __str;
 889     }
 890
 891   // operator ==
 892   template<typename _CharT, typename _Traits, typename _Alloc>
 893     inline bool
 894     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 895                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 896     { return __lhs.compare(__rhs) == 0; }
 897
 898   template<typename _CharT, typename _Traits, typename _Alloc>
 899     inline bool
 900     operator==(const _CharT* __lhs,
 901                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 902     { return __rhs.compare(__lhs) == 0; }
 903
 904   template<typename _CharT, typename _Traits, typename _Alloc>
 905     inline bool
 906     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 907                const _CharT* __rhs)
 908     { return __lhs.compare(__rhs) == 0; }
 909
 910   // operator !=
 911   template<typename _CharT, typename _Traits, typename _Alloc>
 912     inline bool
 913     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 914                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 915     { return __rhs.compare(__lhs) != 0; }
 916
 917   template<typename _CharT, typename _Traits, typename _Alloc>
 918     inline bool
 919     operator!=(const _CharT* __lhs,
 920                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 921     { return __rhs.compare(__lhs) != 0; }
 922
 923   template<typename _CharT, typename _Traits, typename _Alloc>
 924     inline bool
 925     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 926                const _CharT* __rhs)
 927     { return __lhs.compare(__rhs) != 0; }
 928
 929   // operator <
 930   template<typename _CharT, typename _Traits, typename _Alloc>
 931     inline bool
 932     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 933               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 934     { return __lhs.compare(__rhs) < 0; }
 935
 936   template<typename _CharT, typename _Traits, typename _Alloc>
 937     inline bool
 938     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 939               const _CharT* __rhs)
 940     { return __lhs.compare(__rhs) < 0; }
 941
 942   template<typename _CharT, typename _Traits, typename _Alloc>
 943     inline bool
 944     operator<(const _CharT* __lhs,
 945               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 946     { return __rhs.compare(__lhs) > 0; }
 947
 948   // operator >
 949   template<typename _CharT, typename _Traits, typename _Alloc>
 950     inline bool
 951     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 952               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 953     { return __lhs.compare(__rhs) > 0; }
 954
 955   template<typename _CharT, typename _Traits, typename _Alloc>
 956     inline bool
 957     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 958               const _CharT* __rhs)
 959     { return __lhs.compare(__rhs) > 0; }
 960
 961   template<typename _CharT, typename _Traits, typename _Alloc>
 962     inline bool
 963     operator>(const _CharT* __lhs,
 964               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 965     { return __rhs.compare(__lhs) < 0; }
 966
 967   // operator <=
 968   template<typename _CharT, typename _Traits, typename _Alloc>
 969     inline bool
 970     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 971                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 972     { return __lhs.compare(__rhs) <= 0; }
 973
 974   template<typename _CharT, typename _Traits, typename _Alloc>
 975     inline bool
 976     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 977                const _CharT* __rhs)
 978     { return __lhs.compare(__rhs) <= 0; }
 979
 980   template<typename _CharT, typename _Traits, typename _Alloc>
 981     inline bool
 982     operator<=(const _CharT* __lhs,
 983                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 984   { return __rhs.compare(__lhs) >= 0; }
 985
 986   // operator >=
 987   template<typename _CharT, typename _Traits, typename _Alloc>
 988     inline bool
 989     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 990                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 991     { return __lhs.compare(__rhs) >= 0; }
 992
 993   template<typename _CharT, typename _Traits, typename _Alloc>
 994     inline bool
 995     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
 996                const _CharT* __rhs)
 997     { return __lhs.compare(__rhs) >= 0; }
 998
 999   template<typename _CharT, typename _Traits, typename _Alloc>
1000     inline bool
1001     operator>=(const _CharT* __lhs,
1002              const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1003     { return __rhs.compare(__lhs) <= 0; }
1004
1005
1006   template<typename _CharT, typename _Traits, typename _Alloc>
1007     inline void
1008     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
1009          basic_string<_CharT, _Traits, _Alloc>& __rhs)
1010     { __lhs.swap(__rhs); }
1011
1012   template<typename _CharT, typename _Traits, typename _Alloc>
1013     basic_istream<_CharT, _Traits>&
1014     operator>>(basic_istream<_CharT, _Traits>& __is,
1015                basic_string<_CharT, _Traits, _Alloc>& __str);
1016
1017   template<typename _CharT, typename _Traits, typename _Alloc>
1018     basic_ostream<_CharT, _Traits>&
1019     operator<<(basic_ostream<_CharT, _Traits>& __os,
1020                const basic_string<_CharT, _Traits, _Alloc>& __str);
1021
1022   template<typename _CharT, typename _Traits, typename _Alloc>
1023     basic_istream<_CharT,_Traits>&
1024     getline(basic_istream<_CharT, _Traits>& __is,
1025             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
1026
1027   template<typename _CharT, typename _Traits, typename _Alloc>
1028     inline basic_istream<_CharT,_Traits>&
1029     getline(basic_istream<_CharT, _Traits>& __is,
1030             basic_string<_CharT, _Traits, _Alloc>& __str);
1031 } // namespace std
1032
1033 #endif /* _CPP_BITS_STRING_H */