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

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