contrib/gcc-5.0/libstdc++-v3/include/bits/basic_string.h

   1 // Components for manipulating sequences of characters -*- C++ -*-
   2
   3 // Copyright (C) 1997-2015 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file bits/basic_string.h
  26  *  This is an internal header file, included by other library headers.
  27  *  Do not attempt to use it directly. @headername{string}
  28  */
  29
  30 //
  31 // ISO C++ 14882: 21 Strings library
  32 //
  33
  34 #ifndef _BASIC_STRING_H
  35 #define _BASIC_STRING_H 1
  36
  37 #pragma GCC system_header
  38
  39 #include <ext/atomicity.h>
  40 #include <ext/alloc_traits.h>
  41 #include <debug/debug.h>
  42 #if __cplusplus >= 201103L
  43 #include <initializer_list>
  44 #endif
  45
  46 namespace std _GLIBCXX_VISIBILITY(default)
  47 {
  48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  49
  50 #if _GLIBCXX_USE_CXX11_ABI
  51 _GLIBCXX_BEGIN_NAMESPACE_CXX11
  52   /**
  53    *  @class basic_string basic_string.h <string>
  54    *  @brief  Managing sequences of characters and character-like objects.
  55    *
  56    *  @ingroup strings
  57    *  @ingroup sequences
  58    *
  59    *  @tparam _CharT  Type of character
  60    *  @tparam _Traits  Traits for character type, defaults to
  61    *                   char_traits<_CharT>.
  62    *  @tparam _Alloc  Allocator type, defaults to allocator<_CharT>.
  63    *
  64    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
  65    *  <a href="tables.html#66">reversible container</a>, and a
  66    *  <a href="tables.html#67">sequence</a>.  Of the
  67    *  <a href="tables.html#68">optional sequence requirements</a>, only
  68    *  @c push_back, @c at, and @c %array access are supported.
  69    */
  70   template<typename _CharT, typename _Traits, typename _Alloc>
  71     class basic_string
  72     {
  73       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
  74         rebind<_CharT>::other _Char_alloc_type;
  75       typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
  76
  77       // Types:
  78     public:
  79       typedef _Traits                                   traits_type;
  80       typedef typename _Traits::char_type               value_type;
  81       typedef _Char_alloc_type                          allocator_type;
  82       typedef typename _Alloc_traits::size_type         size_type;
  83       typedef typename _Alloc_traits::difference_type   difference_type;
  84       typedef typename _Alloc_traits::reference         reference;
  85       typedef typename _Alloc_traits::const_reference   const_reference;
  86       typedef typename _Alloc_traits::pointer           pointer;
  87       typedef typename _Alloc_traits::const_pointer     const_pointer;
  88       typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
  89       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
  90                                                         const_iterator;
  91       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
  92       typedef std::reverse_iterator<iterator>           reverse_iterator;
  93
  94       ///  Value returned by various member functions when they fail.
  95       static const size_type    npos = static_cast<size_type>(-1);
  96
  97     private:
  98       // type used for positions in insert, erase etc.
  99 #if __cplusplus < 201103L
 100       typedef iterator __const_iterator;
 101 #else
 102       typedef const_iterator __const_iterator;
 103 #endif
 104
 105       // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
 106       struct _Alloc_hider : allocator_type // TODO check __is_final
 107       {
 108         _Alloc_hider(pointer __dat, const _Alloc& __a = _Alloc())
 109         : allocator_type(__a), _M_p(__dat) { }
 110
 111         pointer _M_p; // The actual data.
 112       };
 113
 114       _Alloc_hider      _M_dataplus;
 115       size_type         _M_string_length;
 116
 117       enum { _S_local_capacity = 15 / sizeof(_CharT) };
 118
 119       union
 120       {
 121         _CharT           _M_local_buf[_S_local_capacity + 1];
 122         size_type        _M_allocated_capacity;
 123       };
 124
 125       void
 126       _M_data(pointer __p)
 127       { _M_dataplus._M_p = __p; }
 128
 129       void
 130       _M_length(size_type __length)
 131       { _M_string_length = __length; }
 132
 133       pointer
 134       _M_data() const
 135       { return _M_dataplus._M_p; }
 136
 137       pointer
 138       _M_local_data()
 139       {
 140 #if __cplusplus >= 201103L
 141         return std::pointer_traits<pointer>::pointer_to(*_M_local_buf);
 142 #else
 143         return pointer(_M_local_buf);
 144 #endif
 145       }
 146
 147       const_pointer
 148       _M_local_data() const
 149       {
 150 #if __cplusplus >= 201103L
 151         return std::pointer_traits<const_pointer>::pointer_to(*_M_local_buf);
 152 #else
 153         return const_pointer(_M_local_buf);
 154 #endif
 155       }
 156
 157       void
 158       _M_capacity(size_type __capacity)
 159       { _M_allocated_capacity = __capacity; }
 160
 161       void
 162       _M_set_length(size_type __n)
 163       {
 164         _M_length(__n);
 165         traits_type::assign(_M_data()[__n], _CharT());
 166       }
 167
 168       bool
 169       _M_is_local() const
 170       { return _M_data() == _M_local_data(); }
 171
 172       // Create & Destroy
 173       pointer
 174       _M_create(size_type&, size_type);
 175
 176       void
 177       _M_dispose()
 178       {
 179         if (!_M_is_local())
 180           _M_destroy(_M_allocated_capacity);
 181       }
 182
 183       void
 184       _M_destroy(size_type __size) throw()
 185       { _Alloc_traits::deallocate(_M_get_allocator(), _M_data(), __size + 1); }
 186
 187       // _M_construct_aux is used to implement the 21.3.1 para 15 which
 188       // requires special behaviour if _InIterator is an integral type
 189       template<typename _InIterator>
 190         void
 191         _M_construct_aux(_InIterator __beg, _InIterator __end,
 192                          std::__false_type)
 193         {
 194           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
 195           _M_construct(__beg, __end, _Tag());
 196         }
 197
 198       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 199       // 438. Ambiguity in the "do the right thing" clause
 200       template<typename _Integer>
 201         void
 202         _M_construct_aux(_Integer __beg, _Integer __end, std::__true_type)
 203         { _M_construct_aux_2(static_cast<size_type>(__beg), __end); }
 204
 205       void
 206       _M_construct_aux_2(size_type __req, _CharT __c)
 207       { _M_construct(__req, __c); }
 208
 209       template<typename _InIterator>
 210         void
 211         _M_construct(_InIterator __beg, _InIterator __end)
 212         {
 213           typedef typename std::__is_integer<_InIterator>::__type _Integral;
 214           _M_construct_aux(__beg, __end, _Integral());
 215         }
 216
 217       // For Input Iterators, used in istreambuf_iterators, etc.
 218       template<typename _InIterator>
 219         void
 220         _M_construct(_InIterator __beg, _InIterator __end,
 221                      std::input_iterator_tag);
 222
 223       // For forward_iterators up to random_access_iterators, used for
 224       // string::iterator, _CharT*, etc.
 225       template<typename _FwdIterator>
 226         void
 227         _M_construct(_FwdIterator __beg, _FwdIterator __end,
 228                      std::forward_iterator_tag);
 229
 230       void
 231       _M_construct(size_type __req, _CharT __c);
 232
 233       allocator_type&
 234       _M_get_allocator()
 235       { return _M_dataplus; }
 236
 237       const allocator_type&
 238       _M_get_allocator() const
 239       { return _M_dataplus; }
 240
 241     private:
 242
 243 #ifdef _GLIBCXX_DISAMBIGUATE_REPLACE_INST
 244       // The explicit instantiations in misc-inst.cc require this due to
 245       // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64063
 246       template<typename _Tp, bool _Requires =
 247                !__are_same<_Tp, _CharT*>::__value
 248                && !__are_same<_Tp, const _CharT*>::__value
 249                && !__are_same<_Tp, iterator>::__value
 250                && !__are_same<_Tp, const_iterator>::__value>
 251         struct __enable_if_not_native_iterator
 252         { typedef basic_string& __type; };
 253       template<typename _Tp>
 254         struct __enable_if_not_native_iterator<_Tp, false> { };
 255 #endif
 256
 257       size_type
 258       _M_check(size_type __pos, const char* __s) const
 259       {
 260         if (__pos > this->size())
 261           __throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "
 262                                        "this->size() (which is %zu)"),
 263                                    __s, __pos, this->size());
 264         return __pos;
 265       }
 266
 267       void
 268       _M_check_length(size_type __n1, size_type __n2, const char* __s) const
 269       {
 270         if (this->max_size() - (this->size() - __n1) < __n2)
 271           __throw_length_error(__N(__s));
 272       }
 273
 274
 275       // NB: _M_limit doesn't check for a bad __pos value.
 276       size_type
 277       _M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPT
 278       {
 279         const bool __testoff =  __off < this->size() - __pos;
 280         return __testoff ? __off : this->size() - __pos;
 281       }
 282
 283       // True if _Rep and source do not overlap.
 284       bool
 285       _M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPT
 286       {
 287         return (less<const _CharT*>()(__s, _M_data())
 288                 || less<const _CharT*>()(_M_data() + this->size(), __s));
 289       }
 290
 291       // When __n = 1 way faster than the general multichar
 292       // traits_type::copy/move/assign.
 293       static void
 294       _S_copy(_CharT* __d, const _CharT* __s, size_type __n)
 295       {
 296         if (__n == 1)
 297           traits_type::assign(*__d, *__s);
 298         else
 299           traits_type::copy(__d, __s, __n);
 300       }
 301
 302       static void
 303       _S_move(_CharT* __d, const _CharT* __s, size_type __n)
 304       {
 305         if (__n == 1)
 306           traits_type::assign(*__d, *__s);
 307         else
 308           traits_type::move(__d, __s, __n);
 309       }
 310
 311       static void
 312       _S_assign(_CharT* __d, size_type __n, _CharT __c)
 313       {
 314         if (__n == 1)
 315           traits_type::assign(*__d, __c);
 316         else
 317           traits_type::assign(__d, __n, __c);
 318       }
 319
 320       // _S_copy_chars is a separate template to permit specialization
 321       // to optimize for the common case of pointers as iterators.
 322       template<class _Iterator>
 323         static void
 324         _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
 325         _GLIBCXX_NOEXCEPT
 326         {
 327           for (; __k1 != __k2; ++__k1, ++__p)
 328             traits_type::assign(*__p, *__k1); // These types are off.
 329         }
 330
 331       static void
 332       _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) _GLIBCXX_NOEXCEPT
 333       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
 334
 335       static void
 336       _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
 337       _GLIBCXX_NOEXCEPT
 338       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
 339
 340       static void
 341       _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) _GLIBCXX_NOEXCEPT
 342       { _S_copy(__p, __k1, __k2 - __k1); }
 343
 344       static void
 345       _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
 346       _GLIBCXX_NOEXCEPT
 347       { _S_copy(__p, __k1, __k2 - __k1); }
 348
 349       static int
 350       _S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPT
 351       {
 352         const difference_type __d = difference_type(__n1 - __n2);
 353
 354         if (__d > __gnu_cxx::__numeric_traits<int>::__max)
 355           return __gnu_cxx::__numeric_traits<int>::__max;
 356         else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
 357           return __gnu_cxx::__numeric_traits<int>::__min;
 358         else
 359           return int(__d);
 360       }
 361
 362       void
 363       _M_assign(const basic_string& __rcs);
 364
 365       void
 366       _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
 367                 size_type __len2);
 368
 369       void
 370       _M_erase(size_type __pos, size_type __n);
 371
 372     public:
 373       // Construct/copy/destroy:
 374       // NB: We overload ctors in some cases instead of using default
 375       // arguments, per 17.4.4.4 para. 2 item 2.
 376
 377       /**
 378        *  @brief  Default constructor creates an empty string.
 379        */
 380       basic_string() _GLIBCXX_NOEXCEPT
 381       : _M_dataplus(_M_local_data())
 382       { _M_set_length(0); }
 383
 384       /**
 385        *  @brief  Construct an empty string using allocator @a a.
 386        */
 387       explicit
 388       basic_string(const _Alloc& __a)
 389       : _M_dataplus(_M_local_data(), __a)
 390       { _M_set_length(0); }
 391
 392       /**
 393        *  @brief  Construct string with copy of value of @a __str.
 394        *  @param  __str  Source string.
 395        */
 396       basic_string(const basic_string& __str)
 397       : _M_dataplus(_M_local_data(), __str._M_get_allocator()) // TODO A traits
 398       { _M_construct(__str._M_data(), __str._M_data() + __str.length()); }
 399
 400       /**
 401        *  @brief  Construct string as copy of a substring.
 402        *  @param  __str  Source string.
 403        *  @param  __pos  Index of first character to copy from.
 404        *  @param  __n  Number of characters to copy (default remainder).
 405        */
 406       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 407       // 2402. [this constructor] shouldn't use Allocator()
 408       basic_string(const basic_string& __str, size_type __pos,
 409                    size_type __n = npos)
 410       : _M_dataplus(_M_local_data())
 411       {
 412         const _CharT* __start = __str._M_data()
 413           + __str._M_check(__pos, "basic_string::basic_string");
 414         _M_construct(__start, __start + __str._M_limit(__pos, __n));
 415       }
 416
 417       /**
 418        *  @brief  Construct string as copy of a substring.
 419        *  @param  __str  Source string.
 420        *  @param  __pos  Index of first character to copy from.
 421        *  @param  __n  Number of characters to copy (default remainder).
 422        *  @param  __a  Allocator to use.
 423        */
 424       basic_string(const basic_string& __str, size_type __pos,
 425                    size_type __n, const _Alloc& __a)
 426       : _M_dataplus(_M_local_data(), __a)
 427       {
 428         const _CharT* __start
 429           = __str._M_data() + __str._M_check(__pos, "string::string");
 430         _M_construct(__start, __start + __str._M_limit(__pos, __n));
 431       }
 432
 433       /**
 434        *  @brief  Construct string initialized by a character %array.
 435        *  @param  __s  Source character %array.
 436        *  @param  __n  Number of characters to copy.
 437        *  @param  __a  Allocator to use (default is default allocator).
 438        *
 439        *  NB: @a __s must have at least @a __n characters, &apos;\\0&apos;
 440        *  has no special meaning.
 441        */
 442       basic_string(const _CharT* __s, size_type __n,
 443                    const _Alloc& __a = _Alloc())
 444       : _M_dataplus(_M_local_data(), __a)
 445       { _M_construct(__s, __s + __n); }
 446
 447       /**
 448        *  @brief  Construct string as copy of a C string.
 449        *  @param  __s  Source C string.
 450        *  @param  __a  Allocator to use (default is default allocator).
 451        */
 452       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc())
 453       : _M_dataplus(_M_local_data(), __a)
 454       { _M_construct(__s, __s ? __s + traits_type::length(__s) : __s+npos); }
 455
 456       /**
 457        *  @brief  Construct string as multiple characters.
 458        *  @param  __n  Number of characters.
 459        *  @param  __c  Character to use.
 460        *  @param  __a  Allocator to use (default is default allocator).
 461        */
 462       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc())
 463       : _M_dataplus(_M_local_data(), __a)
 464       { _M_construct(__n, __c); }
 465
 466 #if __cplusplus >= 201103L
 467       /**
 468        *  @brief  Move construct string.
 469        *  @param  __str  Source string.
 470        *
 471        *  The newly-created string contains the exact contents of @a __str.
 472        *  @a __str is a valid, but unspecified string.
 473        **/
 474       basic_string(basic_string&& __str) noexcept
 475       : _M_dataplus(_M_local_data(), std::move(__str._M_get_allocator()))
 476       {
 477         if (__str._M_is_local())
 478           {
 479             if (__str.length())
 480               traits_type::copy(_M_local_buf, __str._M_local_buf,
 481                                 _S_local_capacity + 1);
 482           }
 483         else
 484           {
 485             _M_data(__str._M_data());
 486             _M_capacity(__str._M_allocated_capacity);
 487           }
 488
 489         // Must use _M_length() here not _M_set_length() because
 490         // basic_stringbuf relies on writing into unallocated capacity so
 491         // we mess up the contents if we put a '\0' in the string.
 492         _M_length(__str.length());
 493         __str._M_data(__str._M_local_data());
 494         __str._M_set_length(0);
 495       }
 496
 497       /**
 498        *  @brief  Construct string from an initializer %list.
 499        *  @param  __l  std::initializer_list of characters.
 500        *  @param  __a  Allocator to use (default is default allocator).
 501        */
 502       basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc())
 503       : _M_dataplus(_M_local_data(), __a)
 504       { _M_construct(__l.begin(), __l.end()); }
 505
 506       basic_string(const basic_string& __str, const _Alloc& __a)
 507       : _M_dataplus(_M_local_data(), __a)
 508       { _M_construct(__str.begin(), __str.end()); }
 509
 510       basic_string(basic_string&& __str, const _Alloc& __a)
 511       : _M_dataplus(_M_local_data(), __a)
 512       {
 513         if (__str.get_allocator() == __a)
 514           *this = std::move(__str);
 515         else
 516           _M_construct(__str.begin(), __str.end());
 517       }
 518
 519 #endif // C++11
 520
 521       /**
 522        *  @brief  Construct string as copy of a range.
 523        *  @param  __beg  Start of range.
 524        *  @param  __end  End of range.
 525        *  @param  __a  Allocator to use (default is default allocator).
 526        */
 527 #if __cplusplus >= 201103L
 528       template<typename _InputIterator,
 529                typename = std::_RequireInputIter<_InputIterator>>
 530 #else
 531       template<typename _InputIterator>
 532 #endif
 533         basic_string(_InputIterator __beg, _InputIterator __end,
 534                      const _Alloc& __a = _Alloc())
 535         : _M_dataplus(_M_local_data(), __a)
 536         { _M_construct(__beg, __end); }
 537
 538       /**
 539        *  @brief  Destroy the string instance.
 540        */
 541       ~basic_string()
 542       { _M_dispose(); }
 543
 544       /**
 545        *  @brief  Assign the value of @a str to this string.
 546        *  @param  __str  Source string.
 547        */
 548       basic_string&
 549       operator=(const basic_string& __str)
 550       { return this->assign(__str); }
 551
 552       /**
 553        *  @brief  Copy contents of @a s into this string.
 554        *  @param  __s  Source null-terminated string.
 555        */
 556       basic_string&
 557       operator=(const _CharT* __s)
 558       { return this->assign(__s); }
 559
 560       /**
 561        *  @brief  Set value to string of length 1.
 562        *  @param  __c  Source character.
 563        *
 564        *  Assigning to a character makes this string length 1 and
 565        *  (*this)[0] == @a c.
 566        */
 567       basic_string&
 568       operator=(_CharT __c)
 569       {
 570         this->assign(1, __c);
 571         return *this;
 572       }
 573
 574 #if __cplusplus >= 201103L
 575       /**
 576        *  @brief  Move assign the value of @a str to this string.
 577        *  @param  __str  Source string.
 578        *
 579        *  The contents of @a str are moved into this string (without copying).
 580        *  @a str is a valid, but unspecified string.
 581        **/
 582       // PR 58265, this should be noexcept.
 583       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 584       // 2063. Contradictory requirements for string move assignment
 585       basic_string&
 586       operator=(basic_string&& __str)
 587       {
 588         this->swap(__str);
 589         return *this;
 590       }
 591
 592       /**
 593        *  @brief  Set value to string constructed from initializer %list.
 594        *  @param  __l  std::initializer_list.
 595        */
 596       basic_string&
 597       operator=(initializer_list<_CharT> __l)
 598       {
 599         this->assign(__l.begin(), __l.size());
 600         return *this;
 601       }
 602 #endif // C++11
 603
 604       // Iterators:
 605       /**
 606        *  Returns a read/write iterator that points to the first character in
 607        *  the %string.
 608        */
 609       iterator
 610       begin() _GLIBCXX_NOEXCEPT
 611       { return iterator(_M_data()); }
 612
 613       /**
 614        *  Returns a read-only (constant) iterator that points to the first
 615        *  character in the %string.
 616        */
 617       const_iterator
 618       begin() const _GLIBCXX_NOEXCEPT
 619       { return const_iterator(_M_data()); }
 620
 621       /**
 622        *  Returns a read/write iterator that points one past the last
 623        *  character in the %string.
 624        */
 625       iterator
 626       end() _GLIBCXX_NOEXCEPT
 627       { return iterator(_M_data() + this->size()); }
 628
 629       /**
 630        *  Returns a read-only (constant) iterator that points one past the
 631        *  last character in the %string.
 632        */
 633       const_iterator
 634       end() const _GLIBCXX_NOEXCEPT
 635       { return const_iterator(_M_data() + this->size()); }
 636
 637       /**
 638        *  Returns a read/write reverse iterator that points to the last
 639        *  character in the %string.  Iteration is done in reverse element
 640        *  order.
 641        */
 642       reverse_iterator
 643       rbegin() _GLIBCXX_NOEXCEPT
 644       { return reverse_iterator(this->end()); }
 645
 646       /**
 647        *  Returns a read-only (constant) reverse iterator that points
 648        *  to the last character in the %string.  Iteration is done in
 649        *  reverse element order.
 650        */
 651       const_reverse_iterator
 652       rbegin() const _GLIBCXX_NOEXCEPT
 653       { return const_reverse_iterator(this->end()); }
 654
 655       /**
 656        *  Returns a read/write reverse iterator that points to one before the
 657        *  first character in the %string.  Iteration is done in reverse
 658        *  element order.
 659        */
 660       reverse_iterator
 661       rend() _GLIBCXX_NOEXCEPT
 662       { return reverse_iterator(this->begin()); }
 663
 664       /**
 665        *  Returns a read-only (constant) reverse iterator that points
 666        *  to one before the first character in the %string.  Iteration
 667        *  is done in reverse element order.
 668        */
 669       const_reverse_iterator
 670       rend() const _GLIBCXX_NOEXCEPT
 671       { return const_reverse_iterator(this->begin()); }
 672
 673 #if __cplusplus >= 201103L
 674       /**
 675        *  Returns a read-only (constant) iterator that points to the first
 676        *  character in the %string.
 677        */
 678       const_iterator
 679       cbegin() const noexcept
 680       { return const_iterator(this->_M_data()); }
 681
 682       /**
 683        *  Returns a read-only (constant) iterator that points one past the
 684        *  last character in the %string.
 685        */
 686       const_iterator
 687       cend() const noexcept
 688       { return const_iterator(this->_M_data() + this->size()); }
 689
 690       /**
 691        *  Returns a read-only (constant) reverse iterator that points
 692        *  to the last character in the %string.  Iteration is done in
 693        *  reverse element order.
 694        */
 695       const_reverse_iterator
 696       crbegin() const noexcept
 697       { return const_reverse_iterator(this->end()); }
 698
 699       /**
 700        *  Returns a read-only (constant) reverse iterator that points
 701        *  to one before the first character in the %string.  Iteration
 702        *  is done in reverse element order.
 703        */
 704       const_reverse_iterator
 705       crend() const noexcept
 706       { return const_reverse_iterator(this->begin()); }
 707 #endif
 708
 709     public:
 710       // Capacity:
 711       ///  Returns the number of characters in the string, not including any
 712       ///  null-termination.
 713       size_type
 714       size() const _GLIBCXX_NOEXCEPT
 715       { return _M_string_length; }
 716
 717       ///  Returns the number of characters in the string, not including any
 718       ///  null-termination.
 719       size_type
 720       length() const _GLIBCXX_NOEXCEPT
 721       { return _M_string_length; }
 722
 723       ///  Returns the size() of the largest possible %string.
 724       size_type
 725       max_size() const _GLIBCXX_NOEXCEPT
 726       { return (_Alloc_traits::max_size(_M_get_allocator()) - 1) / 2; }
 727
 728       /**
 729        *  @brief  Resizes the %string to the specified number of characters.
 730        *  @param  __n  Number of characters the %string should contain.
 731        *  @param  __c  Character to fill any new elements.
 732        *
 733        *  This function will %resize the %string to the specified
 734        *  number of characters.  If the number is smaller than the
 735        *  %string's current size the %string is truncated, otherwise
 736        *  the %string is extended and new elements are %set to @a __c.
 737        */
 738       void
 739       resize(size_type __n, _CharT __c);
 740
 741       /**
 742        *  @brief  Resizes the %string to the specified number of characters.
 743        *  @param  __n  Number of characters the %string should contain.
 744        *
 745        *  This function will resize the %string to the specified length.  If
 746        *  the new size is smaller than the %string's current size the %string
 747        *  is truncated, otherwise the %string is extended and new characters
 748        *  are default-constructed.  For basic types such as char, this means
 749        *  setting them to 0.
 750        */
 751       void
 752       resize(size_type __n)
 753       { this->resize(__n, _CharT()); }
 754
 755 #if __cplusplus >= 201103L
 756       ///  A non-binding request to reduce capacity() to size().
 757       void
 758       shrink_to_fit() noexcept
 759       {
 760         if (capacity() > size())
 761           {
 762             __try
 763               { reserve(0); }
 764             __catch(...)
 765               { }
 766           }
 767       }
 768 #endif
 769
 770       /**
 771        *  Returns the total number of characters that the %string can hold
 772        *  before needing to allocate more memory.
 773        */
 774       size_type
 775       capacity() const _GLIBCXX_NOEXCEPT
 776       {
 777         return _M_is_local() ? size_type(_S_local_capacity)
 778                              : _M_allocated_capacity;
 779       }
 780
 781       /**
 782        *  @brief  Attempt to preallocate enough memory for specified number of
 783        *          characters.
 784        *  @param  __res_arg  Number of characters required.
 785        *  @throw  std::length_error  If @a __res_arg exceeds @c max_size().
 786        *
 787        *  This function attempts to reserve enough memory for the
 788        *  %string to hold the specified number of characters.  If the
 789        *  number requested is more than max_size(), length_error is
 790        *  thrown.
 791        *
 792        *  The advantage of this function is that if optimal code is a
 793        *  necessity and the user can determine the string length that will be
 794        *  required, the user can reserve the memory in %advance, and thus
 795        *  prevent a possible reallocation of memory and copying of %string
 796        *  data.
 797        */
 798       void
 799       reserve(size_type __res_arg = 0);
 800
 801       /**
 802        *  Erases the string, making it empty.
 803        */
 804       void
 805       clear() _GLIBCXX_NOEXCEPT
 806       { _M_set_length(0); }
 807
 808       /**
 809        *  Returns true if the %string is empty.  Equivalent to
 810        *  <code>*this == ""</code>.
 811        */
 812       bool
 813       empty() const _GLIBCXX_NOEXCEPT
 814       { return this->size() == 0; }
 815
 816       // Element access:
 817       /**
 818        *  @brief  Subscript access to the data contained in the %string.
 819        *  @param  __pos  The index of the character to access.
 820        *  @return  Read-only (constant) reference to the character.
 821        *
 822        *  This operator allows for easy, array-style, data access.
 823        *  Note that data access with this operator is unchecked and
 824        *  out_of_range lookups are not defined. (For checked lookups
 825        *  see at().)
 826        */
 827       const_reference
 828       operator[] (size_type __pos) const _GLIBCXX_NOEXCEPT
 829       {
 830         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
 831         return _M_data()[__pos];
 832       }
 833
 834       /**
 835        *  @brief  Subscript access to the data contained in the %string.
 836        *  @param  __pos  The index of the character to access.
 837        *  @return  Read/write reference to the character.
 838        *
 839        *  This operator allows for easy, array-style, data access.
 840        *  Note that data access with this operator is unchecked and
 841        *  out_of_range lookups are not defined. (For checked lookups
 842        *  see at().)
 843        */
 844       reference
 845       operator[](size_type __pos)
 846       {
 847         // Allow pos == size() both in C++98 mode, as v3 extension,
 848         // and in C++11 mode.
 849         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
 850         // In pedantic mode be strict in C++98 mode.
 851         _GLIBCXX_DEBUG_PEDASSERT(__cplusplus >= 201103L || __pos < size());
 852         return _M_data()[__pos];
 853       }
 854
 855       /**
 856        *  @brief  Provides access to the data contained in the %string.
 857        *  @param __n The index of the character to access.
 858        *  @return  Read-only (const) reference to the character.
 859        *  @throw  std::out_of_range  If @a n is an invalid index.
 860        *
 861        *  This function provides for safer data access.  The parameter is
 862        *  first checked that it is in the range of the string.  The function
 863        *  throws out_of_range if the check fails.
 864        */
 865       const_reference
 866       at(size_type __n) const
 867       {
 868         if (__n >= this->size())
 869           __throw_out_of_range_fmt(__N("basic_string::at: __n "
 870                                        "(which is %zu) >= this->size() "
 871                                        "(which is %zu)"),
 872                                    __n, this->size());
 873         return _M_data()[__n];
 874       }
 875
 876       /**
 877        *  @brief  Provides access to the data contained in the %string.
 878        *  @param __n The index of the character to access.
 879        *  @return  Read/write reference to the character.
 880        *  @throw  std::out_of_range  If @a n is an invalid index.
 881        *
 882        *  This function provides for safer data access.  The parameter is
 883        *  first checked that it is in the range of the string.  The function
 884        *  throws out_of_range if the check fails.
 885        */
 886       reference
 887       at(size_type __n)
 888       {
 889         if (__n >= size())
 890           __throw_out_of_range_fmt(__N("basic_string::at: __n "
 891                                        "(which is %zu) >= this->size() "
 892                                        "(which is %zu)"),
 893                                    __n, this->size());
 894         return _M_data()[__n];
 895       }
 896
 897 #if __cplusplus >= 201103L
 898       /**
 899        *  Returns a read/write reference to the data at the first
 900        *  element of the %string.
 901        */
 902       reference
 903       front() noexcept
 904       { return operator[](0); }
 905
 906       /**
 907        *  Returns a read-only (constant) reference to the data at the first
 908        *  element of the %string.
 909        */
 910       const_reference
 911       front() const noexcept
 912       { return operator[](0); }
 913
 914       /**
 915        *  Returns a read/write reference to the data at the last
 916        *  element of the %string.
 917        */
 918       reference
 919       back() noexcept
 920       { return operator[](this->size() - 1); }
 921
 922       /**
 923        *  Returns a read-only (constant) reference to the data at the
 924        *  last element of the %string.
 925        */
 926       const_reference
 927       back() const noexcept
 928       { return operator[](this->size() - 1); }
 929 #endif
 930
 931       // Modifiers:
 932       /**
 933        *  @brief  Append a string to this string.
 934        *  @param __str  The string to append.
 935        *  @return  Reference to this string.
 936        */
 937       basic_string&
 938       operator+=(const basic_string& __str)
 939       { return this->append(__str); }
 940
 941       /**
 942        *  @brief  Append a C string.
 943        *  @param __s  The C string to append.
 944        *  @return  Reference to this string.
 945        */
 946       basic_string&
 947       operator+=(const _CharT* __s)
 948       { return this->append(__s); }
 949
 950       /**
 951        *  @brief  Append a character.
 952        *  @param __c  The character to append.
 953        *  @return  Reference to this string.
 954        */
 955       basic_string&
 956       operator+=(_CharT __c)
 957       {
 958         this->push_back(__c);
 959         return *this;
 960       }
 961
 962 #if __cplusplus >= 201103L
 963       /**
 964        *  @brief  Append an initializer_list of characters.
 965        *  @param __l  The initializer_list of characters to be appended.
 966        *  @return  Reference to this string.
 967        */
 968       basic_string&
 969       operator+=(initializer_list<_CharT> __l)
 970       { return this->append(__l.begin(), __l.size()); }
 971 #endif // C++11
 972
 973       /**
 974        *  @brief  Append a string to this string.
 975        *  @param __str  The string to append.
 976        *  @return  Reference to this string.
 977        */
 978       basic_string&
 979       append(const basic_string& __str)
 980       { return _M_append(__str._M_data(), __str.size()); }
 981
 982       /**
 983        *  @brief  Append a substring.
 984        *  @param __str  The string to append.
 985        *  @param __pos  Index of the first character of str to append.
 986        *  @param __n  The number of characters to append.
 987        *  @return  Reference to this string.
 988        *  @throw  std::out_of_range if @a __pos is not a valid index.
 989        *
 990        *  This function appends @a __n characters from @a __str
 991        *  starting at @a __pos to this string.  If @a __n is is larger
 992        *  than the number of available characters in @a __str, the
 993        *  remainder of @a __str is appended.
 994        */
 995       basic_string&
 996       append(const basic_string& __str, size_type __pos, size_type __n)
 997       { return _M_append(__str._M_data()
 998                          + __str._M_check(__pos, "basic_string::append"),
 999                          __str._M_limit(__pos, __n)); }
1000
1001       /**
1002        *  @brief  Append a C substring.
1003        *  @param __s  The C string to append.
1004        *  @param __n  The number of characters to append.
1005        *  @return  Reference to this string.
1006        */
1007       basic_string&
1008       append(const _CharT* __s, size_type __n)
1009       {
1010         __glibcxx_requires_string_len(__s, __n);
1011         _M_check_length(size_type(0), __n, "basic_string::append");
1012         return _M_append(__s, __n);
1013       }
1014
1015       /**
1016        *  @brief  Append a C string.
1017        *  @param __s  The C string to append.
1018        *  @return  Reference to this string.
1019        */
1020       basic_string&
1021       append(const _CharT* __s)
1022       {
1023         __glibcxx_requires_string(__s);
1024         const size_type __n = traits_type::length(__s);
1025         _M_check_length(size_type(0), __n, "basic_string::append");
1026         return _M_append(__s, __n);
1027       }
1028
1029       /**
1030        *  @brief  Append multiple characters.
1031        *  @param __n  The number of characters to append.
1032        *  @param __c  The character to use.
1033        *  @return  Reference to this string.
1034        *
1035        *  Appends __n copies of __c to this string.
1036        */
1037       basic_string&
1038       append(size_type __n, _CharT __c)
1039       { return _M_replace_aux(this->size(), size_type(0), __n, __c); }
1040
1041 #if __cplusplus >= 201103L
1042       /**
1043        *  @brief  Append an initializer_list of characters.
1044        *  @param __l  The initializer_list of characters to append.
1045        *  @return  Reference to this string.
1046        */
1047       basic_string&
1048       append(initializer_list<_CharT> __l)
1049       { return this->append(__l.begin(), __l.size()); }
1050 #endif // C++11
1051
1052       /**
1053        *  @brief  Append a range of characters.
1054        *  @param __first  Iterator referencing the first character to append.
1055        *  @param __last  Iterator marking the end of the range.
1056        *  @return  Reference to this string.
1057        *
1058        *  Appends characters in the range [__first,__last) to this string.
1059        */
1060 #if __cplusplus >= 201103L
1061       template<class _InputIterator,
1062                typename = std::_RequireInputIter<_InputIterator>>
1063 #else
1064       template<class _InputIterator>
1065 #endif
1066         basic_string&
1067         append(_InputIterator __first, _InputIterator __last)
1068         { return this->replace(end(), end(), __first, __last); }
1069
1070       /**
1071        *  @brief  Append a single character.
1072        *  @param __c  Character to append.
1073        */
1074       void
1075       push_back(_CharT __c)
1076       {
1077         const size_type __size = this->size();
1078         if (__size + 1 > this->capacity())
1079           this->_M_mutate(__size, size_type(0), 0, size_type(1));
1080         traits_type::assign(this->_M_data()[__size], __c);
1081         this->_M_set_length(__size + 1);
1082       }
1083
1084       /**
1085        *  @brief  Set value to contents of another string.
1086        *  @param  __str  Source string to use.
1087        *  @return  Reference to this string.
1088        */
1089       basic_string&
1090       assign(const basic_string& __str)
1091       {
1092         this->_M_assign(__str);
1093         return *this;
1094       }
1095
1096 #if __cplusplus >= 201103L
1097       /**
1098        *  @brief  Set value to contents of another string.
1099        *  @param  __str  Source string to use.
1100        *  @return  Reference to this string.
1101        *
1102        *  This function sets this string to the exact contents of @a __str.
1103        *  @a __str is a valid, but unspecified string.
1104        */
1105       basic_string&
1106       assign(basic_string&& __str)
1107       {
1108         // _GLIBCXX_RESOLVE_LIB_DEFECTS
1109         // 2063. Contradictory requirements for string move assignment
1110         return *this = std::move(__str);
1111       }
1112 #endif // C++11
1113
1114       /**
1115        *  @brief  Set value to a substring of a string.
1116        *  @param __str  The string to use.
1117        *  @param __pos  Index of the first character of str.
1118        *  @param __n  Number of characters to use.
1119        *  @return  Reference to this string.
1120        *  @throw  std::out_of_range if @a pos is not a valid index.
1121        *
1122        *  This function sets this string to the substring of @a __str
1123        *  consisting of @a __n characters at @a __pos.  If @a __n is
1124        *  is larger than the number of available characters in @a
1125        *  __str, the remainder of @a __str is used.
1126        */
1127       basic_string&
1128       assign(const basic_string& __str, size_type __pos, size_type __n)
1129       { return _M_replace(size_type(0), this->size(), __str._M_data()
1130                           + __str._M_check(__pos, "basic_string::assign"),
1131                           __str._M_limit(__pos, __n)); }
1132
1133       /**
1134        *  @brief  Set value to a C substring.
1135        *  @param __s  The C string to use.
1136        *  @param __n  Number of characters to use.
1137        *  @return  Reference to this string.
1138        *
1139        *  This function sets the value of this string to the first @a __n
1140        *  characters of @a __s.  If @a __n is is larger than the number of
1141        *  available characters in @a __s, the remainder of @a __s is used.
1142        */
1143       basic_string&
1144       assign(const _CharT* __s, size_type __n)
1145       {
1146         __glibcxx_requires_string_len(__s, __n);
1147         return _M_replace(size_type(0), this->size(), __s, __n);
1148       }
1149
1150       /**
1151        *  @brief  Set value to contents of a C string.
1152        *  @param __s  The C string to use.
1153        *  @return  Reference to this string.
1154        *
1155        *  This function sets the value of this string to the value of @a __s.
1156        *  The data is copied, so there is no dependence on @a __s once the
1157        *  function returns.
1158        */
1159       basic_string&
1160       assign(const _CharT* __s)
1161       {
1162         __glibcxx_requires_string(__s);
1163         return _M_replace(size_type(0), this->size(), __s,
1164                           traits_type::length(__s));
1165       }
1166
1167       /**
1168        *  @brief  Set value to multiple characters.
1169        *  @param __n  Length of the resulting string.
1170        *  @param __c  The character to use.
1171        *  @return  Reference to this string.
1172        *
1173        *  This function sets the value of this string to @a __n copies of
1174        *  character @a __c.
1175        */
1176       basic_string&
1177       assign(size_type __n, _CharT __c)
1178       { return _M_replace_aux(size_type(0), this->size(), __n, __c); }
1179
1180       /**
1181        *  @brief  Set value to a range of characters.
1182        *  @param __first  Iterator referencing the first character to append.
1183        *  @param __last  Iterator marking the end of the range.
1184        *  @return  Reference to this string.
1185        *
1186        *  Sets value of string to characters in the range [__first,__last).
1187       */
1188 #if __cplusplus >= 201103L
1189       template<class _InputIterator,
1190                typename = std::_RequireInputIter<_InputIterator>>
1191 #else
1192       template<class _InputIterator>
1193 #endif
1194         basic_string&
1195         assign(_InputIterator __first, _InputIterator __last)
1196         { return this->replace(begin(), end(), __first, __last); }
1197
1198 #if __cplusplus >= 201103L
1199       /**
1200        *  @brief  Set value to an initializer_list of characters.
1201        *  @param __l  The initializer_list of characters to assign.
1202        *  @return  Reference to this string.
1203        */
1204       basic_string&
1205       assign(initializer_list<_CharT> __l)
1206       { return this->assign(__l.begin(), __l.size()); }
1207 #endif // C++11
1208
1209 #if __cplusplus >= 201103L
1210       /**
1211        *  @brief  Insert multiple characters.
1212        *  @param __p  Const_iterator referencing location in string to
1213        *              insert at.
1214        *  @param __n  Number of characters to insert
1215        *  @param __c  The character to insert.
1216        *  @return  Iterator referencing the first inserted char.
1217        *  @throw  std::length_error  If new length exceeds @c max_size().
1218        *
1219        *  Inserts @a __n copies of character @a __c starting at the
1220        *  position referenced by iterator @a __p.  If adding
1221        *  characters causes the length to exceed max_size(),
1222        *  length_error is thrown.  The value of the string doesn't
1223        *  change if an error is thrown.
1224       */
1225       iterator
1226       insert(const_iterator __p, size_type __n, _CharT __c)
1227       {
1228         _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1229         const size_type __pos = __p - begin();
1230         this->replace(__p, __p, __n, __c);
1231         return iterator(this->_M_data() + __pos);
1232       }
1233 #else
1234       /**
1235        *  @brief  Insert multiple characters.
1236        *  @param __p  Iterator referencing location in string to insert at.
1237        *  @param __n  Number of characters to insert
1238        *  @param __c  The character to insert.
1239        *  @throw  std::length_error  If new length exceeds @c max_size().
1240        *
1241        *  Inserts @a __n copies of character @a __c starting at the
1242        *  position referenced by iterator @a __p.  If adding
1243        *  characters causes the length to exceed max_size(),
1244        *  length_error is thrown.  The value of the string doesn't
1245        *  change if an error is thrown.
1246       */
1247       void
1248       insert(iterator __p, size_type __n, _CharT __c)
1249       { this->replace(__p, __p, __n, __c);  }
1250 #endif
1251
1252 #if __cplusplus >= 201103L
1253       /**
1254        *  @brief  Insert a range of characters.
1255        *  @param __p  Const_iterator referencing location in string to
1256        *              insert at.
1257        *  @param __beg  Start of range.
1258        *  @param __end  End of range.
1259        *  @return  Iterator referencing the first inserted char.
1260        *  @throw  std::length_error  If new length exceeds @c max_size().
1261        *
1262        *  Inserts characters in range [beg,end).  If adding characters
1263        *  causes the length to exceed max_size(), length_error is
1264        *  thrown.  The value of the string doesn't change if an error
1265        *  is thrown.
1266       */
1267       template<class _InputIterator,
1268                typename = std::_RequireInputIter<_InputIterator>>
1269         iterator
1270         insert(const_iterator __p, _InputIterator __beg, _InputIterator __end)
1271         {
1272           _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1273           const size_type __pos = __p - begin();
1274           this->replace(__p, __p, __beg, __end);
1275           return iterator(this->_M_data() + __pos);
1276         }
1277 #else
1278       /**
1279        *  @brief  Insert a range of characters.
1280        *  @param __p  Iterator referencing location in string to insert at.
1281        *  @param __beg  Start of range.
1282        *  @param __end  End of range.
1283        *  @throw  std::length_error  If new length exceeds @c max_size().
1284        *
1285        *  Inserts characters in range [__beg,__end).  If adding
1286        *  characters causes the length to exceed max_size(),
1287        *  length_error is thrown.  The value of the string doesn't
1288        *  change if an error is thrown.
1289       */
1290       template<class _InputIterator>
1291         void
1292         insert(iterator __p, _InputIterator __beg, _InputIterator __end)
1293         { this->replace(__p, __p, __beg, __end); }
1294 #endif
1295
1296 #if __cplusplus >= 201103L
1297       /**
1298        *  @brief  Insert an initializer_list of characters.
1299        *  @param __p  Iterator referencing location in string to insert at.
1300        *  @param __l  The initializer_list of characters to insert.
1301        *  @throw  std::length_error  If new length exceeds @c max_size().
1302        */
1303       void
1304       insert(iterator __p, initializer_list<_CharT> __l)
1305       {
1306         _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1307         this->insert(__p - begin(), __l.begin(), __l.size());
1308       }
1309 #endif // C++11
1310
1311       /**
1312        *  @brief  Insert value of a string.
1313        *  @param __pos1  Iterator referencing location in string to insert at.
1314        *  @param __str  The string to insert.
1315        *  @return  Reference to this string.
1316        *  @throw  std::length_error  If new length exceeds @c max_size().
1317        *
1318        *  Inserts value of @a __str starting at @a __pos1.  If adding
1319        *  characters causes the length to exceed max_size(),
1320        *  length_error is thrown.  The value of the string doesn't
1321        *  change if an error is thrown.
1322       */
1323       basic_string&
1324       insert(size_type __pos1, const basic_string& __str)
1325       { return this->replace(__pos1, size_type(0),
1326                              __str._M_data(), __str.size()); }
1327
1328       /**
1329        *  @brief  Insert a substring.
1330        *  @param __pos1  Iterator referencing location in string to insert at.
1331        *  @param __str  The string to insert.
1332        *  @param __pos2  Start of characters in str to insert.
1333        *  @param __n  Number of characters to insert.
1334        *  @return  Reference to this string.
1335        *  @throw  std::length_error  If new length exceeds @c max_size().
1336        *  @throw  std::out_of_range  If @a pos1 > size() or
1337        *  @a __pos2 > @a str.size().
1338        *
1339        *  Starting at @a pos1, insert @a __n character of @a __str
1340        *  beginning with @a __pos2.  If adding characters causes the
1341        *  length to exceed max_size(), length_error is thrown.  If @a
1342        *  __pos1 is beyond the end of this string or @a __pos2 is
1343        *  beyond the end of @a __str, out_of_range is thrown.  The
1344        *  value of the string doesn't change if an error is thrown.
1345       */
1346       basic_string&
1347       insert(size_type __pos1, const basic_string& __str,
1348              size_type __pos2, size_type __n)
1349       { return this->replace(__pos1, size_type(0), __str._M_data()
1350                              + __str._M_check(__pos2, "basic_string::insert"),
1351                              __str._M_limit(__pos2, __n)); }
1352
1353       /**
1354        *  @brief  Insert a C substring.
1355        *  @param __pos  Iterator referencing location in string to insert at.
1356        *  @param __s  The C string to insert.
1357        *  @param __n  The number of characters to insert.
1358        *  @return  Reference to this string.
1359        *  @throw  std::length_error  If new length exceeds @c max_size().
1360        *  @throw  std::out_of_range  If @a __pos is beyond the end of this
1361        *  string.
1362        *
1363        *  Inserts the first @a __n characters of @a __s starting at @a
1364        *  __pos.  If adding characters causes the length to exceed
1365        *  max_size(), length_error is thrown.  If @a __pos is beyond
1366        *  end(), out_of_range is thrown.  The value of the string
1367        *  doesn't change if an error is thrown.
1368       */
1369       basic_string&
1370       insert(size_type __pos, const _CharT* __s, size_type __n)
1371       { return this->replace(__pos, size_type(0), __s, __n); }
1372
1373       /**
1374        *  @brief  Insert a C string.
1375        *  @param __pos  Iterator referencing location in string to insert at.
1376        *  @param __s  The C string to insert.
1377        *  @return  Reference to this string.
1378        *  @throw  std::length_error  If new length exceeds @c max_size().
1379        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1380        *  string.
1381        *
1382        *  Inserts the first @a n characters of @a __s starting at @a __pos.  If
1383        *  adding characters causes the length to exceed max_size(),
1384        *  length_error is thrown.  If @a __pos is beyond end(), out_of_range is
1385        *  thrown.  The value of the string doesn't change if an error is
1386        *  thrown.
1387       */
1388       basic_string&
1389       insert(size_type __pos, const _CharT* __s)
1390       {
1391         __glibcxx_requires_string(__s);
1392         return this->replace(__pos, size_type(0), __s,
1393                              traits_type::length(__s));
1394       }
1395
1396       /**
1397        *  @brief  Insert multiple characters.
1398        *  @param __pos  Index in string to insert at.
1399        *  @param __n  Number of characters to insert
1400        *  @param __c  The character to insert.
1401        *  @return  Reference to this string.
1402        *  @throw  std::length_error  If new length exceeds @c max_size().
1403        *  @throw  std::out_of_range  If @a __pos is beyond the end of this
1404        *  string.
1405        *
1406        *  Inserts @a __n copies of character @a __c starting at index
1407        *  @a __pos.  If adding characters causes the length to exceed
1408        *  max_size(), length_error is thrown.  If @a __pos > length(),
1409        *  out_of_range is thrown.  The value of the string doesn't
1410        *  change if an error is thrown.
1411       */
1412       basic_string&
1413       insert(size_type __pos, size_type __n, _CharT __c)
1414       { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
1415                               size_type(0), __n, __c); }
1416
1417       /**
1418        *  @brief  Insert one character.
1419        *  @param __p  Iterator referencing position in string to insert at.
1420        *  @param __c  The character to insert.
1421        *  @return  Iterator referencing newly inserted char.
1422        *  @throw  std::length_error  If new length exceeds @c max_size().
1423        *
1424        *  Inserts character @a __c at position referenced by @a __p.
1425        *  If adding character causes the length to exceed max_size(),
1426        *  length_error is thrown.  If @a __p is beyond end of string,
1427        *  out_of_range is thrown.  The value of the string doesn't
1428        *  change if an error is thrown.
1429       */
1430       iterator
1431       insert(__const_iterator __p, _CharT __c)
1432       {
1433         _GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1434         const size_type __pos = __p - begin();
1435         _M_replace_aux(__pos, size_type(0), size_type(1), __c);
1436         return iterator(_M_data() + __pos);
1437       }
1438
1439       /**
1440        *  @brief  Remove characters.
1441        *  @param __pos  Index of first character to remove (default 0).
1442        *  @param __n  Number of characters to remove (default remainder).
1443        *  @return  Reference to this string.
1444        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1445        *  string.
1446        *
1447        *  Removes @a __n characters from this string starting at @a
1448        *  __pos.  The length of the string is reduced by @a __n.  If
1449        *  there are < @a __n characters to remove, the remainder of
1450        *  the string is truncated.  If @a __p is beyond end of string,
1451        *  out_of_range is thrown.  The value of the string doesn't
1452        *  change if an error is thrown.
1453       */
1454       basic_string&
1455       erase(size_type __pos = 0, size_type __n = npos)
1456       {
1457         this->_M_erase(_M_check(__pos, "basic_string::erase"),
1458                        _M_limit(__pos, __n));
1459         return *this;
1460       }
1461
1462       /**
1463        *  @brief  Remove one character.
1464        *  @param __position  Iterator referencing the character to remove.
1465        *  @return  iterator referencing same location after removal.
1466        *
1467        *  Removes the character at @a __position from this string. The value
1468        *  of the string doesn't change if an error is thrown.
1469       */
1470       iterator
1471       erase(__const_iterator __position)
1472       {
1473         _GLIBCXX_DEBUG_PEDASSERT(__position >= begin()
1474                                  && __position < end());
1475         const size_type __pos = __position - begin();
1476         this->_M_erase(__pos, size_type(1));
1477         return iterator(_M_data() + __pos);
1478       }
1479
1480       /**
1481        *  @brief  Remove a range of characters.
1482        *  @param __first  Iterator referencing the first character to remove.
1483        *  @param __last  Iterator referencing the end of the range.
1484        *  @return  Iterator referencing location of first after removal.
1485        *
1486        *  Removes the characters in the range [first,last) from this string.
1487        *  The value of the string doesn't change if an error is thrown.
1488       */
1489       iterator
1490       erase(__const_iterator __first, __const_iterator __last)
1491       {
1492         _GLIBCXX_DEBUG_PEDASSERT(__first >= begin() && __first <= __last
1493                                  && __last <= end());
1494         const size_type __pos = __first - begin();
1495         this->_M_erase(__pos, __last - __first);
1496         return iterator(this->_M_data() + __pos);
1497       }
1498
1499 #if __cplusplus >= 201103L
1500       /**
1501        *  @brief  Remove the last character.
1502        *
1503        *  The string must be non-empty.
1504        */
1505       void
1506       pop_back() noexcept
1507       { _M_erase(size()-1, 1); }
1508 #endif // C++11
1509
1510       /**
1511        *  @brief  Replace characters with value from another string.
1512        *  @param __pos  Index of first character to replace.
1513        *  @param __n  Number of characters to be replaced.
1514        *  @param __str  String to insert.
1515        *  @return  Reference to this string.
1516        *  @throw  std::out_of_range  If @a pos is beyond the end of this
1517        *  string.
1518        *  @throw  std::length_error  If new length exceeds @c max_size().
1519        *
1520        *  Removes the characters in the range [__pos,__pos+__n) from
1521        *  this string.  In place, the value of @a __str is inserted.
1522        *  If @a __pos is beyond end of string, out_of_range is thrown.
1523        *  If the length of the result exceeds max_size(), length_error
1524        *  is thrown.  The value of the string doesn't change if an
1525        *  error is thrown.
1526       */
1527       basic_string&
1528       replace(size_type __pos, size_type __n, const basic_string& __str)
1529       { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
1530
1531       /**
1532        *  @brief  Replace characters with value from another string.
1533        *  @param __pos1  Index of first character to replace.
1534        *  @param __n1  Number of characters to be replaced.
1535        *  @param __str  String to insert.
1536        *  @param __pos2  Index of first character of str to use.
1537        *  @param __n2  Number of characters from str to use.
1538        *  @return  Reference to this string.
1539        *  @throw  std::out_of_range  If @a __pos1 > size() or @a __pos2 >
1540        *  __str.size().
1541        *  @throw  std::length_error  If new length exceeds @c max_size().
1542        *
1543        *  Removes the characters in the range [__pos1,__pos1 + n) from this
1544        *  string.  In place, the value of @a __str is inserted.  If @a __pos is
1545        *  beyond end of string, out_of_range is thrown.  If the length of the
1546        *  result exceeds max_size(), length_error is thrown.  The value of the
1547        *  string doesn't change if an error is thrown.
1548       */
1549       basic_string&
1550       replace(size_type __pos1, size_type __n1, const basic_string& __str,
1551               size_type __pos2, size_type __n2)
1552       { return this->replace(__pos1, __n1, __str._M_data()
1553                              + __str._M_check(__pos2, "basic_string::replace"),
1554                              __str._M_limit(__pos2, __n2)); }
1555
1556       /**
1557        *  @brief  Replace characters with value of a C substring.
1558        *  @param __pos  Index of first character to replace.
1559        *  @param __n1  Number of characters to be replaced.
1560        *  @param __s  C string to insert.
1561        *  @param __n2  Number of characters from @a s to use.
1562        *  @return  Reference to this string.
1563        *  @throw  std::out_of_range  If @a pos1 > size().
1564        *  @throw  std::length_error  If new length exceeds @c max_size().
1565        *
1566        *  Removes the characters in the range [__pos,__pos + __n1)
1567        *  from this string.  In place, the first @a __n2 characters of
1568        *  @a __s are inserted, or all of @a __s if @a __n2 is too large.  If
1569        *  @a __pos is beyond end of string, out_of_range is thrown.  If
1570        *  the length of result exceeds max_size(), length_error is
1571        *  thrown.  The value of the string doesn't change if an error
1572        *  is thrown.
1573       */
1574       basic_string&
1575       replace(size_type __pos, size_type __n1, const _CharT* __s,
1576               size_type __n2)
1577       {
1578         __glibcxx_requires_string_len(__s, __n2);
1579         return _M_replace(_M_check(__pos, "basic_string::replace"),
1580                           _M_limit(__pos, __n1), __s, __n2);
1581       }
1582
1583       /**
1584        *  @brief  Replace characters with value of a C string.
1585        *  @param __pos  Index of first character to replace.
1586        *  @param __n1  Number of characters to be replaced.
1587        *  @param __s  C string to insert.
1588        *  @return  Reference to this string.
1589        *  @throw  std::out_of_range  If @a pos > size().
1590        *  @throw  std::length_error  If new length exceeds @c max_size().
1591        *
1592        *  Removes the characters in the range [__pos,__pos + __n1)
1593        *  from this string.  In place, the characters of @a __s are
1594        *  inserted.  If @a __pos is beyond end of string, out_of_range
1595        *  is thrown.  If the length of result exceeds max_size(),
1596        *  length_error is thrown.  The value of the string doesn't
1597        *  change if an error is thrown.
1598       */
1599       basic_string&
1600       replace(size_type __pos, size_type __n1, const _CharT* __s)
1601       {
1602         __glibcxx_requires_string(__s);
1603         return this->replace(__pos, __n1, __s, traits_type::length(__s));
1604       }
1605
1606       /**
1607        *  @brief  Replace characters with multiple characters.
1608        *  @param __pos  Index of first character to replace.
1609        *  @param __n1  Number of characters to be replaced.
1610        *  @param __n2  Number of characters to insert.
1611        *  @param __c  Character to insert.
1612        *  @return  Reference to this string.
1613        *  @throw  std::out_of_range  If @a __pos > size().
1614        *  @throw  std::length_error  If new length exceeds @c max_size().
1615        *
1616        *  Removes the characters in the range [pos,pos + n1) from this
1617        *  string.  In place, @a __n2 copies of @a __c are inserted.
1618        *  If @a __pos is beyond end of string, out_of_range is thrown.
1619        *  If the length of result exceeds max_size(), length_error is
1620        *  thrown.  The value of the string doesn't change if an error
1621        *  is thrown.
1622       */
1623       basic_string&
1624       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
1625       { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
1626                               _M_limit(__pos, __n1), __n2, __c); }
1627
1628       /**
1629        *  @brief  Replace range of characters with string.
1630        *  @param __i1  Iterator referencing start of range to replace.
1631        *  @param __i2  Iterator referencing end of range to replace.
1632        *  @param __str  String value to insert.
1633        *  @return  Reference to this string.
1634        *  @throw  std::length_error  If new length exceeds @c max_size().
1635        *
1636        *  Removes the characters in the range [__i1,__i2).  In place,
1637        *  the value of @a __str is inserted.  If the length of result
1638        *  exceeds max_size(), length_error is thrown.  The value of
1639        *  the string doesn't change if an error is thrown.
1640       */
1641       basic_string&
1642       replace(__const_iterator __i1, __const_iterator __i2,
1643               const basic_string& __str)
1644       { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
1645
1646       /**
1647        *  @brief  Replace range of characters with C substring.
1648        *  @param __i1  Iterator referencing start of range to replace.
1649        *  @param __i2  Iterator referencing end of range to replace.
1650        *  @param __s  C string value to insert.
1651        *  @param __n  Number of characters from s to insert.
1652        *  @return  Reference to this string.
1653        *  @throw  std::length_error  If new length exceeds @c max_size().
1654        *
1655        *  Removes the characters in the range [__i1,__i2).  In place,
1656        *  the first @a __n characters of @a __s are inserted.  If the
1657        *  length of result exceeds max_size(), length_error is thrown.
1658        *  The value of the string doesn't change if an error is
1659        *  thrown.
1660       */
1661       basic_string&
1662       replace(__const_iterator __i1, __const_iterator __i2,
1663               const _CharT* __s, size_type __n)
1664       {
1665         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1666                                  && __i2 <= end());
1667         return this->replace(__i1 - begin(), __i2 - __i1, __s, __n);
1668       }
1669
1670       /**
1671        *  @brief  Replace range of characters with C string.
1672        *  @param __i1  Iterator referencing start of range to replace.
1673        *  @param __i2  Iterator referencing end of range to replace.
1674        *  @param __s  C string value to insert.
1675        *  @return  Reference to this string.
1676        *  @throw  std::length_error  If new length exceeds @c max_size().
1677        *
1678        *  Removes the characters in the range [__i1,__i2).  In place,
1679        *  the characters of @a __s are inserted.  If the length of
1680        *  result exceeds max_size(), length_error is thrown.  The
1681        *  value of the string doesn't change if an error is thrown.
1682       */
1683       basic_string&
1684       replace(__const_iterator __i1, __const_iterator __i2, const _CharT* __s)
1685       {
1686         __glibcxx_requires_string(__s);
1687         return this->replace(__i1, __i2, __s, traits_type::length(__s));
1688       }
1689
1690       /**
1691        *  @brief  Replace range of characters with multiple characters
1692        *  @param __i1  Iterator referencing start of range to replace.
1693        *  @param __i2  Iterator referencing end of range to replace.
1694        *  @param __n  Number of characters to insert.
1695        *  @param __c  Character to insert.
1696        *  @return  Reference to this string.
1697        *  @throw  std::length_error  If new length exceeds @c max_size().
1698        *
1699        *  Removes the characters in the range [__i1,__i2).  In place,
1700        *  @a __n copies of @a __c are inserted.  If the length of
1701        *  result exceeds max_size(), length_error is thrown.  The
1702        *  value of the string doesn't change if an error is thrown.
1703       */
1704       basic_string&
1705       replace(__const_iterator __i1, __const_iterator __i2, size_type __n,
1706               _CharT __c)
1707       {
1708         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1709                                  && __i2 <= end());
1710         return _M_replace_aux(__i1 - begin(), __i2 - __i1, __n, __c);
1711       }
1712
1713       /**
1714        *  @brief  Replace range of characters with range.
1715        *  @param __i1  Iterator referencing start of range to replace.
1716        *  @param __i2  Iterator referencing end of range to replace.
1717        *  @param __k1  Iterator referencing start of range to insert.
1718        *  @param __k2  Iterator referencing end of range to insert.
1719        *  @return  Reference to this string.
1720        *  @throw  std::length_error  If new length exceeds @c max_size().
1721        *
1722        *  Removes the characters in the range [__i1,__i2).  In place,
1723        *  characters in the range [__k1,__k2) are inserted.  If the
1724        *  length of result exceeds max_size(), length_error is thrown.
1725        *  The value of the string doesn't change if an error is
1726        *  thrown.
1727       */
1728 #if __cplusplus >= 201103L
1729       template<class _InputIterator,
1730                typename = std::_RequireInputIter<_InputIterator>>
1731         basic_string&
1732         replace(const_iterator __i1, const_iterator __i2,
1733                 _InputIterator __k1, _InputIterator __k2)
1734         {
1735           _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1736                                    && __i2 <= end());
1737           __glibcxx_requires_valid_range(__k1, __k2);
1738           return this->_M_replace_dispatch(__i1, __i2, __k1, __k2,
1739                                            std::__false_type());
1740         }
1741 #else
1742       template<class _InputIterator>
1743 #ifdef _GLIBCXX_DISAMBIGUATE_REPLACE_INST
1744         typename __enable_if_not_native_iterator<_InputIterator>::__type
1745 #else
1746         basic_string&
1747 #endif
1748         replace(iterator __i1, iterator __i2,
1749                 _InputIterator __k1, _InputIterator __k2)
1750         {
1751           _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1752                                    && __i2 <= end());
1753           __glibcxx_requires_valid_range(__k1, __k2);
1754           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1755           return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
1756         }
1757 #endif
1758
1759       // Specializations for the common case of pointer and iterator:
1760       // useful to avoid the overhead of temporary buffering in _M_replace.
1761       basic_string&
1762       replace(__const_iterator __i1, __const_iterator __i2,
1763               _CharT* __k1, _CharT* __k2)
1764       {
1765         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1766                                  && __i2 <= end());
1767         __glibcxx_requires_valid_range(__k1, __k2);
1768         return this->replace(__i1 - begin(), __i2 - __i1,
1769                              __k1, __k2 - __k1);
1770       }
1771
1772       basic_string&
1773       replace(__const_iterator __i1, __const_iterator __i2,
1774               const _CharT* __k1, const _CharT* __k2)
1775       {
1776         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1777                                  && __i2 <= end());
1778         __glibcxx_requires_valid_range(__k1, __k2);
1779         return this->replace(__i1 - begin(), __i2 - __i1,
1780                              __k1, __k2 - __k1);
1781       }
1782
1783       basic_string&
1784       replace(__const_iterator __i1, __const_iterator __i2,
1785               iterator __k1, iterator __k2)
1786       {
1787         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1788                                  && __i2 <= end());
1789         __glibcxx_requires_valid_range(__k1, __k2);
1790         return this->replace(__i1 - begin(), __i2 - __i1,
1791                              __k1.base(), __k2 - __k1);
1792       }
1793
1794       basic_string&
1795       replace(__const_iterator __i1, __const_iterator __i2,
1796               const_iterator __k1, const_iterator __k2)
1797       {
1798         _GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1799                                  && __i2 <= end());
1800         __glibcxx_requires_valid_range(__k1, __k2);
1801         return this->replace(__i1 - begin(), __i2 - __i1,
1802                              __k1.base(), __k2 - __k1);
1803       }
1804
1805 #if __cplusplus >= 201103L
1806       /**
1807        *  @brief  Replace range of characters with initializer_list.
1808        *  @param __i1  Iterator referencing start of range to replace.
1809        *  @param __i2  Iterator referencing end of range to replace.
1810        *  @param __l  The initializer_list of characters to insert.
1811        *  @return  Reference to this string.
1812        *  @throw  std::length_error  If new length exceeds @c max_size().
1813        *
1814        *  Removes the characters in the range [__i1,__i2).  In place,
1815        *  characters in the range [__k1,__k2) are inserted.  If the
1816        *  length of result exceeds max_size(), length_error is thrown.
1817        *  The value of the string doesn't change if an error is
1818        *  thrown.
1819       */
1820       basic_string& replace(const_iterator __i1, const_iterator __i2,
1821                             initializer_list<_CharT> __l)
1822       { return this->replace(__i1, __i2, __l.begin(), __l.end()); }
1823 #endif // C++11
1824
1825     private:
1826       template<class _Integer>
1827         basic_string&
1828         _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
1829                             _Integer __n, _Integer __val, __true_type)
1830         { return _M_replace_aux(__i1 - begin(), __i2 - __i1, __n, __val); }
1831
1832       template<class _InputIterator>
1833         basic_string&
1834         _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
1835                             _InputIterator __k1, _InputIterator __k2,
1836                             __false_type);
1837
1838       basic_string&
1839       _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
1840                      _CharT __c);
1841
1842       basic_string&
1843       _M_replace(size_type __pos, size_type __len1, const _CharT* __s,
1844                  const size_type __len2);
1845
1846       basic_string&
1847       _M_append(const _CharT* __s, size_type __n);
1848
1849     public:
1850
1851       /**
1852        *  @brief  Copy substring into C string.
1853        *  @param __s  C string to copy value into.
1854        *  @param __n  Number of characters to copy.
1855        *  @param __pos  Index of first character to copy.
1856        *  @return  Number of characters actually copied
1857        *  @throw  std::out_of_range  If __pos > size().
1858        *
1859        *  Copies up to @a __n characters starting at @a __pos into the
1860        *  C string @a __s.  If @a __pos is %greater than size(),
1861        *  out_of_range is thrown.
1862       */
1863       size_type
1864       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
1865
1866       /**
1867        *  @brief  Swap contents with another string.
1868        *  @param __s  String to swap with.
1869        *
1870        *  Exchanges the contents of this string with that of @a __s in constant
1871        *  time.
1872       */
1873       void
1874       swap(basic_string& __s) _GLIBCXX_NOEXCEPT;
1875
1876       // String operations:
1877       /**
1878        *  @brief  Return const pointer to null-terminated contents.
1879        *
1880        *  This is a handle to internal data.  Do not modify or dire things may
1881        *  happen.
1882       */
1883       const _CharT*
1884       c_str() const _GLIBCXX_NOEXCEPT
1885       { return _M_data(); }
1886
1887       /**
1888        *  @brief  Return const pointer to contents.
1889        *
1890        *  This is a handle to internal data.  Do not modify or dire things may
1891        *  happen.
1892       */
1893       const _CharT*
1894       data() const _GLIBCXX_NOEXCEPT
1895       { return _M_data(); }
1896
1897       /**
1898        *  @brief  Return copy of allocator used to construct this string.
1899       */
1900       allocator_type
1901       get_allocator() const _GLIBCXX_NOEXCEPT
1902       { return _M_get_allocator(); }
1903
1904       /**
1905        *  @brief  Find position of a C substring.
1906        *  @param __s  C string to locate.
1907        *  @param __pos  Index of character to search from.
1908        *  @param __n  Number of characters from @a s to search for.
1909        *  @return  Index of start of first occurrence.
1910        *
1911        *  Starting from @a __pos, searches forward for the first @a
1912        *  __n characters in @a __s within this string.  If found,
1913        *  returns the index where it begins.  If not found, returns
1914        *  npos.
1915       */
1916       size_type
1917       find(const _CharT* __s, size_type __pos, size_type __n) const;
1918
1919       /**
1920        *  @brief  Find position of a string.
1921        *  @param __str  String to locate.
1922        *  @param __pos  Index of character to search from (default 0).
1923        *  @return  Index of start of first occurrence.
1924        *
1925        *  Starting from @a __pos, searches forward for value of @a __str within
1926        *  this string.  If found, returns the index where it begins.  If not
1927        *  found, returns npos.
1928       */
1929       size_type
1930       find(const basic_string& __str, size_type __pos = 0) const
1931         _GLIBCXX_NOEXCEPT
1932       { return this->find(__str.data(), __pos, __str.size()); }
1933
1934       /**
1935        *  @brief  Find position of a C string.
1936        *  @param __s  C string to locate.
1937        *  @param __pos  Index of character to search from (default 0).
1938        *  @return  Index of start of first occurrence.
1939        *
1940        *  Starting from @a __pos, searches forward for the value of @a
1941        *  __s within this string.  If found, returns the index where
1942        *  it begins.  If not found, returns npos.
1943       */
1944       size_type
1945       find(const _CharT* __s, size_type __pos = 0) const
1946       {
1947         __glibcxx_requires_string(__s);
1948         return this->find(__s, __pos, traits_type::length(__s));
1949       }
1950
1951       /**
1952        *  @brief  Find position of a character.
1953        *  @param __c  Character to locate.
1954        *  @param __pos  Index of character to search from (default 0).
1955        *  @return  Index of first occurrence.
1956        *
1957        *  Starting from @a __pos, searches forward for @a __c within
1958        *  this string.  If found, returns the index where it was
1959        *  found.  If not found, returns npos.
1960       */
1961       size_type
1962       find(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT;
1963
1964       /**
1965        *  @brief  Find last position of a string.
1966        *  @param __str  String to locate.
1967        *  @param __pos  Index of character to search back from (default end).
1968        *  @return  Index of start of last occurrence.
1969        *
1970        *  Starting from @a __pos, searches backward for value of @a
1971        *  __str within this string.  If found, returns the index where
1972        *  it begins.  If not found, returns npos.
1973       */
1974       size_type
1975       rfind(const basic_string& __str, size_type __pos = npos) const
1976         _GLIBCXX_NOEXCEPT
1977       { return this->rfind(__str.data(), __pos, __str.size()); }
1978
1979       /**
1980        *  @brief  Find last position of a C substring.
1981        *  @param __s  C string to locate.
1982        *  @param __pos  Index of character to search back from.
1983        *  @param __n  Number of characters from s to search for.
1984        *  @return  Index of start of last occurrence.
1985        *
1986        *  Starting from @a __pos, searches backward for the first @a
1987        *  __n characters in @a __s within this string.  If found,
1988        *  returns the index where it begins.  If not found, returns
1989        *  npos.
1990       */
1991       size_type
1992       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
1993
1994       /**
1995        *  @brief  Find last position of a C string.
1996        *  @param __s  C string to locate.
1997        *  @param __pos  Index of character to start search at (default end).
1998        *  @return  Index of start of  last occurrence.
1999        *
2000        *  Starting from @a __pos, searches backward for the value of
2001        *  @a __s within this string.  If found, returns the index
2002        *  where it begins.  If not found, returns npos.
2003       */
2004       size_type
2005       rfind(const _CharT* __s, size_type __pos = npos) const
2006       {
2007         __glibcxx_requires_string(__s);
2008         return this->rfind(__s, __pos, traits_type::length(__s));
2009       }
2010
2011       /**
2012        *  @brief  Find last position of a character.
2013        *  @param __c  Character to locate.
2014        *  @param __pos  Index of character to search back from (default end).
2015        *  @return  Index of last occurrence.
2016        *
2017        *  Starting from @a __pos, searches backward for @a __c within
2018        *  this string.  If found, returns the index where it was
2019        *  found.  If not found, returns npos.
2020       */
2021       size_type
2022       rfind(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT;
2023
2024       /**
2025        *  @brief  Find position of a character of string.
2026        *  @param __str  String containing characters to locate.
2027        *  @param __pos  Index of character to search from (default 0).
2028        *  @return  Index of first occurrence.
2029        *
2030        *  Starting from @a __pos, searches forward for one of the
2031        *  characters of @a __str within this string.  If found,
2032        *  returns the index where it was found.  If not found, returns
2033        *  npos.
2034       */
2035       size_type
2036       find_first_of(const basic_string& __str, size_type __pos = 0) const
2037         _GLIBCXX_NOEXCEPT
2038       { return this->find_first_of(__str.data(), __pos, __str.size()); }
2039
2040       /**
2041        *  @brief  Find position of a character of C substring.
2042        *  @param __s  String containing characters to locate.
2043        *  @param __pos  Index of character to search from.
2044        *  @param __n  Number of characters from s to search for.
2045        *  @return  Index of first occurrence.
2046        *
2047        *  Starting from @a __pos, searches forward for one of the
2048        *  first @a __n characters of @a __s within this string.  If
2049        *  found, returns the index where it was found.  If not found,
2050        *  returns npos.
2051       */
2052       size_type
2053       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
2054
2055       /**
2056        *  @brief  Find position of a character of C string.
2057        *  @param __s  String containing characters to locate.
2058        *  @param __pos  Index of character to search from (default 0).
2059        *  @return  Index of first occurrence.
2060        *
2061        *  Starting from @a __pos, searches forward for one of the
2062        *  characters of @a __s within this string.  If found, returns
2063        *  the index where it was found.  If not found, returns npos.
2064       */
2065       size_type
2066       find_first_of(const _CharT* __s, size_type __pos = 0) const
2067       {
2068         __glibcxx_requires_string(__s);
2069         return this->find_first_of(__s, __pos, traits_type::length(__s));
2070       }
2071
2072       /**
2073        *  @brief  Find position of a character.
2074        *  @param __c  Character to locate.
2075        *  @param __pos  Index of character to search from (default 0).
2076        *  @return  Index of first occurrence.
2077        *
2078        *  Starting from @a __pos, searches forward for the character
2079        *  @a __c within this string.  If found, returns the index
2080        *  where it was found.  If not found, returns npos.
2081        *
2082        *  Note: equivalent to find(__c, __pos).
2083       */
2084       size_type
2085       find_first_of(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT
2086       { return this->find(__c, __pos); }
2087
2088       /**
2089        *  @brief  Find last position of a character of string.
2090        *  @param __str  String containing characters to locate.
2091        *  @param __pos  Index of character to search back from (default end).
2092        *  @return  Index of last occurrence.
2093        *
2094        *  Starting from @a __pos, searches backward for one of the
2095        *  characters of @a __str within this string.  If found,
2096        *  returns the index where it was found.  If not found, returns
2097        *  npos.
2098       */
2099       size_type
2100       find_last_of(const basic_string& __str, size_type __pos = npos) const
2101         _GLIBCXX_NOEXCEPT
2102       { return this->find_last_of(__str.data(), __pos, __str.size()); }
2103
2104       /**
2105        *  @brief  Find last position of a character of C substring.
2106        *  @param __s  C string containing characters to locate.
2107        *  @param __pos  Index of character to search back from.
2108        *  @param __n  Number of characters from s to search for.
2109        *  @return  Index of last occurrence.
2110        *
2111        *  Starting from @a __pos, searches backward for one of the
2112        *  first @a __n characters of @a __s within this string.  If
2113        *  found, returns the index where it was found.  If not found,
2114        *  returns npos.
2115       */
2116       size_type
2117       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
2118
2119       /**
2120        *  @brief  Find last position of a character of C string.
2121        *  @param __s  C string containing characters to locate.
2122        *  @param __pos  Index of character to search back from (default end).
2123        *  @return  Index of last occurrence.
2124        *
2125        *  Starting from @a __pos, searches backward for one of the
2126        *  characters of @a __s within this string.  If found, returns
2127        *  the index where it was found.  If not found, returns npos.
2128       */
2129       size_type
2130       find_last_of(const _CharT* __s, size_type __pos = npos) const
2131       {
2132         __glibcxx_requires_string(__s);
2133         return this->find_last_of(__s, __pos, traits_type::length(__s));
2134       }
2135
2136       /**
2137        *  @brief  Find last position of a character.
2138        *  @param __c  Character to locate.
2139        *  @param __pos  Index of character to search back from (default end).
2140        *  @return  Index of last occurrence.
2141        *
2142        *  Starting from @a __pos, searches backward for @a __c within
2143        *  this string.  If found, returns the index where it was
2144        *  found.  If not found, returns npos.
2145        *
2146        *  Note: equivalent to rfind(__c, __pos).
2147       */
2148       size_type
2149       find_last_of(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT
2150       { return this->rfind(__c, __pos); }
2151
2152       /**
2153        *  @brief  Find position of a character not in string.
2154        *  @param __str  String containing characters to avoid.
2155        *  @param __pos  Index of character to search from (default 0).
2156        *  @return  Index of first occurrence.
2157        *
2158        *  Starting from @a __pos, searches forward for a character not contained
2159        *  in @a __str within this string.  If found, returns the index where it
2160        *  was found.  If not found, returns npos.
2161       */
2162       size_type
2163       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
2164         _GLIBCXX_NOEXCEPT
2165       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
2166
2167       /**
2168        *  @brief  Find position of a character not in C substring.
2169        *  @param __s  C string containing characters to avoid.
2170        *  @param __pos  Index of character to search from.
2171        *  @param __n  Number of characters from __s to consider.
2172        *  @return  Index of first occurrence.
2173        *
2174        *  Starting from @a __pos, searches forward for a character not
2175        *  contained in the first @a __n characters of @a __s within
2176        *  this string.  If found, returns the index where it was
2177        *  found.  If not found, returns npos.
2178       */
2179       size_type
2180       find_first_not_of(const _CharT* __s, size_type __pos,
2181                         size_type __n) const;
2182
2183       /**
2184        *  @brief  Find position of a character not in C string.
2185        *  @param __s  C string containing characters to avoid.
2186        *  @param __pos  Index of character to search from (default 0).
2187        *  @return  Index of first occurrence.
2188        *
2189        *  Starting from @a __pos, searches forward for a character not
2190        *  contained in @a __s within this string.  If found, returns
2191        *  the index where it was found.  If not found, returns npos.
2192       */
2193       size_type
2194       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
2195       {
2196         __glibcxx_requires_string(__s);
2197         return this->find_first_not_of(__s, __pos, traits_type::length(__s));
2198       }
2199
2200       /**
2201        *  @brief  Find position of a different character.
2202        *  @param __c  Character to avoid.
2203        *  @param __pos  Index of character to search from (default 0).
2204        *  @return  Index of first occurrence.
2205        *
2206        *  Starting from @a __pos, searches forward for a character
2207        *  other than @a __c within this string.  If found, returns the
2208        *  index where it was found.  If not found, returns npos.
2209       */
2210       size_type
2211       find_first_not_of(_CharT __c, size_type __pos = 0) const
2212         _GLIBCXX_NOEXCEPT;
2213
2214       /**
2215        *  @brief  Find last position of a character not in string.
2216        *  @param __str  String containing characters to avoid.
2217        *  @param __pos  Index of character to search back from (default end).
2218        *  @return  Index of last occurrence.
2219        *
2220        *  Starting from @a __pos, searches backward for a character
2221        *  not contained in @a __str within this string.  If found,
2222        *  returns the index where it was found.  If not found, returns
2223        *  npos.
2224       */
2225       size_type
2226       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
2227         _GLIBCXX_NOEXCEPT
2228       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
2229
2230       /**
2231        *  @brief  Find last position of a character not in C substring.
2232        *  @param __s  C string containing characters to avoid.
2233        *  @param __pos  Index of character to search back from.
2234        *  @param __n  Number of characters from s to consider.
2235        *  @return  Index of last occurrence.
2236        *
2237        *  Starting from @a __pos, searches backward for a character not
2238        *  contained in the first @a __n characters of @a __s within this string.
2239        *  If found, returns the index where it was found.  If not found,
2240        *  returns npos.
2241       */
2242       size_type
2243       find_last_not_of(const _CharT* __s, size_type __pos,
2244                        size_type __n) const;
2245       /**
2246        *  @brief  Find last position of a character not in C string.
2247        *  @param __s  C string containing characters to avoid.
2248        *  @param __pos  Index of character to search back from (default end).
2249        *  @return  Index of last occurrence.
2250        *
2251        *  Starting from @a __pos, searches backward for a character
2252        *  not contained in @a __s within this string.  If found,
2253        *  returns the index where it was found.  If not found, returns
2254        *  npos.
2255       */
2256       size_type
2257       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
2258       {
2259         __glibcxx_requires_string(__s);
2260         return this->find_last_not_of(__s, __pos, traits_type::length(__s));
2261       }
2262
2263       /**
2264        *  @brief  Find last position of a different character.
2265        *  @param __c  Character to avoid.
2266        *  @param __pos  Index of character to search back from (default end).
2267        *  @return  Index of last occurrence.
2268        *
2269        *  Starting from @a __pos, searches backward for a character other than
2270        *  @a __c within this string.  If found, returns the index where it was
2271        *  found.  If not found, returns npos.
2272       */
2273       size_type
2274       find_last_not_of(_CharT __c, size_type __pos = npos) const
2275         _GLIBCXX_NOEXCEPT;
2276
2277       /**
2278        *  @brief  Get a substring.
2279        *  @param __pos  Index of first character (default 0).
2280        *  @param __n  Number of characters in substring (default remainder).
2281        *  @return  The new string.
2282        *  @throw  std::out_of_range  If __pos > size().
2283        *
2284        *  Construct and return a new string using the @a __n
2285        *  characters starting at @a __pos.  If the string is too
2286        *  short, use the remainder of the characters.  If @a __pos is
2287        *  beyond the end of the string, out_of_range is thrown.
2288       */
2289       basic_string
2290       substr(size_type __pos = 0, size_type __n = npos) const
2291       { return basic_string(*this,
2292                             _M_check(__pos, "basic_string::substr"), __n); }
2293
2294       /**
2295        *  @brief  Compare to a string.
2296        *  @param __str  String to compare against.
2297        *  @return  Integer < 0, 0, or > 0.
2298        *
2299        *  Returns an integer < 0 if this string is ordered before @a
2300        *  __str, 0 if their values are equivalent, or > 0 if this
2301        *  string is ordered after @a __str.  Determines the effective
2302        *  length rlen of the strings to compare as the smallest of
2303        *  size() and str.size().  The function then compares the two
2304        *  strings by calling traits::compare(data(), str.data(),rlen).
2305        *  If the result of the comparison is nonzero returns it,
2306        *  otherwise the shorter one is ordered first.
2307       */
2308       int
2309       compare(const basic_string& __str) const
2310       {
2311         const size_type __size = this->size();
2312         const size_type __osize = __str.size();
2313         const size_type __len = std::min(__size, __osize);
2314
2315         int __r = traits_type::compare(_M_data(), __str.data(), __len);
2316         if (!__r)
2317           __r = _S_compare(__size, __osize);
2318         return __r;
2319       }
2320
2321       /**
2322        *  @brief  Compare substring to a string.
2323        *  @param __pos  Index of first character of substring.
2324        *  @param __n  Number of characters in substring.
2325        *  @param __str  String to compare against.
2326        *  @return  Integer < 0, 0, or > 0.
2327        *
2328        *  Form the substring of this string from the @a __n characters
2329        *  starting at @a __pos.  Returns an integer < 0 if the
2330        *  substring is ordered before @a __str, 0 if their values are
2331        *  equivalent, or > 0 if the substring is ordered after @a
2332        *  __str.  Determines the effective length rlen of the strings
2333        *  to compare as the smallest of the length of the substring
2334        *  and @a __str.size().  The function then compares the two
2335        *  strings by calling
2336        *  traits::compare(substring.data(),str.data(),rlen).  If the
2337        *  result of the comparison is nonzero returns it, otherwise
2338        *  the shorter one is ordered first.
2339       */
2340       int
2341       compare(size_type __pos, size_type __n, const basic_string& __str) const;
2342
2343       /**
2344        *  @brief  Compare substring to a substring.
2345        *  @param __pos1  Index of first character of substring.
2346        *  @param __n1  Number of characters in substring.
2347        *  @param __str  String to compare against.
2348        *  @param __pos2  Index of first character of substring of str.
2349        *  @param __n2  Number of characters in substring of str.
2350        *  @return  Integer < 0, 0, or > 0.
2351        *
2352        *  Form the substring of this string from the @a __n1
2353        *  characters starting at @a __pos1.  Form the substring of @a
2354        *  __str from the @a __n2 characters starting at @a __pos2.
2355        *  Returns an integer < 0 if this substring is ordered before
2356        *  the substring of @a __str, 0 if their values are equivalent,
2357        *  or > 0 if this substring is ordered after the substring of
2358        *  @a __str.  Determines the effective length rlen of the
2359        *  strings to compare as the smallest of the lengths of the
2360        *  substrings.  The function then compares the two strings by
2361        *  calling
2362        *  traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
2363        *  If the result of the comparison is nonzero returns it,
2364        *  otherwise the shorter one is ordered first.
2365       */
2366       int
2367       compare(size_type __pos1, size_type __n1, const basic_string& __str,
2368               size_type __pos2, size_type __n2) const;
2369
2370       /**
2371        *  @brief  Compare to a C string.
2372        *  @param __s  C string to compare against.
2373        *  @return  Integer < 0, 0, or > 0.
2374        *
2375        *  Returns an integer < 0 if this string is ordered before @a __s, 0 if
2376        *  their values are equivalent, or > 0 if this string is ordered after
2377        *  @a __s.  Determines the effective length rlen of the strings to
2378        *  compare as the smallest of size() and the length of a string
2379        *  constructed from @a __s.  The function then compares the two strings
2380        *  by calling traits::compare(data(),s,rlen).  If the result of the
2381        *  comparison is nonzero returns it, otherwise the shorter one is
2382        *  ordered first.
2383       */
2384       int
2385       compare(const _CharT* __s) const;
2386
2387       // _GLIBCXX_RESOLVE_LIB_DEFECTS
2388       // 5 String::compare specification questionable
2389       /**
2390        *  @brief  Compare substring to a C string.
2391        *  @param __pos  Index of first character of substring.
2392        *  @param __n1  Number of characters in substring.
2393        *  @param __s  C string to compare against.
2394        *  @return  Integer < 0, 0, or > 0.
2395        *
2396        *  Form the substring of this string from the @a __n1
2397        *  characters starting at @a pos.  Returns an integer < 0 if
2398        *  the substring is ordered before @a __s, 0 if their values
2399        *  are equivalent, or > 0 if the substring is ordered after @a
2400        *  __s.  Determines the effective length rlen of the strings to
2401        *  compare as the smallest of the length of the substring and
2402        *  the length of a string constructed from @a __s.  The
2403        *  function then compares the two string by calling
2404        *  traits::compare(substring.data(),__s,rlen).  If the result of
2405        *  the comparison is nonzero returns it, otherwise the shorter
2406        *  one is ordered first.
2407       */
2408       int
2409       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
2410
2411       /**
2412        *  @brief  Compare substring against a character %array.
2413        *  @param __pos  Index of first character of substring.
2414        *  @param __n1  Number of characters in substring.
2415        *  @param __s  character %array to compare against.
2416        *  @param __n2  Number of characters of s.
2417        *  @return  Integer < 0, 0, or > 0.
2418        *
2419        *  Form the substring of this string from the @a __n1
2420        *  characters starting at @a __pos.  Form a string from the
2421        *  first @a __n2 characters of @a __s.  Returns an integer < 0
2422        *  if this substring is ordered before the string from @a __s,
2423        *  0 if their values are equivalent, or > 0 if this substring
2424        *  is ordered after the string from @a __s.  Determines the
2425        *  effective length rlen of the strings to compare as the
2426        *  smallest of the length of the substring and @a __n2.  The
2427        *  function then compares the two strings by calling
2428        *  traits::compare(substring.data(),s,rlen).  If the result of
2429        *  the comparison is nonzero returns it, otherwise the shorter
2430        *  one is ordered first.
2431        *
2432        *  NB: s must have at least n2 characters, &apos;\\0&apos; has
2433        *  no special meaning.
2434       */
2435       int
2436       compare(size_type __pos, size_type __n1, const _CharT* __s,
2437               size_type __n2) const;
2438   };
2439 _GLIBCXX_END_NAMESPACE_CXX11
2440 #else  // !_GLIBCXX_USE_CXX11_ABI
2441   // Reference-counted COW string implentation
2442
2443   /**
2444    *  @class basic_string basic_string.h <string>
2445    *  @brief  Managing sequences of characters and character-like objects.
2446    *
2447    *  @ingroup strings
2448    *  @ingroup sequences
2449    *
2450    *  @tparam _CharT  Type of character
2451    *  @tparam _Traits  Traits for character type, defaults to
2452    *                   char_traits<_CharT>.
2453    *  @tparam _Alloc  Allocator type, defaults to allocator<_CharT>.
2454    *
2455    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
2456    *  <a href="tables.html#66">reversible container</a>, and a
2457    *  <a href="tables.html#67">sequence</a>.  Of the
2458    *  <a href="tables.html#68">optional sequence requirements</a>, only
2459    *  @c push_back, @c at, and @c %array access are supported.
2460    *
2461    *  @doctodo
2462    *
2463    *
2464    *  Documentation?  What's that?
2465    *  Nathan Myers <ncm@cantrip.org>.
2466    *
2467    *  A string looks like this:
2468    *
2469    *  @code
2470    *                                        [_Rep]
2471    *                                        _M_length
2472    *   [basic_string<char_type>]            _M_capacity
2473    *   _M_dataplus                          _M_refcount
2474    *   _M_p ---------------->               unnamed array of char_type
2475    *  @endcode
2476    *
2477    *  Where the _M_p points to the first character in the string, and
2478    *  you cast it to a pointer-to-_Rep and subtract 1 to get a
2479    *  pointer to the header.
2480    *
2481    *  This approach has the enormous advantage that a string object
2482    *  requires only one allocation.  All the ugliness is confined
2483    *  within a single %pair of inline functions, which each compile to
2484    *  a single @a add instruction: _Rep::_M_data(), and
2485    *  string::_M_rep(); and the allocation function which gets a
2486    *  block of raw bytes and with room enough and constructs a _Rep
2487    *  object at the front.
2488    *
2489    *  The reason you want _M_data pointing to the character %array and
2490    *  not the _Rep is so that the debugger can see the string
2491    *  contents. (Probably we should add a non-inline member to get
2492    *  the _Rep for the debugger to use, so users can check the actual
2493    *  string length.)
2494    *
2495    *  Note that the _Rep object is a POD so that you can have a
2496    *  static <em>empty string</em> _Rep object already @a constructed before
2497    *  static constructors have run.  The reference-count encoding is
2498    *  chosen so that a 0 indicates one reference, so you never try to
2499    *  destroy the empty-string _Rep object.
2500    *
2501    *  All but the last paragraph is considered pretty conventional
2502    *  for a C++ string implementation.
2503   */
2504   // 21.3  Template class basic_string
2505   template<typename _CharT, typename _Traits, typename _Alloc>
2506     class basic_string
2507     {
2508       typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;
2509
2510       // Types:
2511     public:
2512       typedef _Traits                                       traits_type;
2513       typedef typename _Traits::char_type                   value_type;
2514       typedef _Alloc                                        allocator_type;
2515       typedef typename _CharT_alloc_type::size_type         size_type;
2516       typedef typename _CharT_alloc_type::difference_type   difference_type;
2517       typedef typename _CharT_alloc_type::reference         reference;
2518       typedef typename _CharT_alloc_type::const_reference   const_reference;
2519       typedef typename _CharT_alloc_type::pointer           pointer;
2520       typedef typename _CharT_alloc_type::const_pointer     const_pointer;
2521       typedef __gnu_cxx::__normal_iterator<pointer, basic_string>  iterator;
2522       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
2523                                                             const_iterator;
2524       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
2525       typedef std::reverse_iterator<iterator>               reverse_iterator;
2526
2527     private:
2528       // _Rep: string representation
2529       //   Invariants:
2530       //   1. String really contains _M_length + 1 characters: due to 21.3.4
2531       //      must be kept null-terminated.
2532       //   2. _M_capacity >= _M_length
2533       //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).
2534       //   3. _M_refcount has three states:
2535       //      -1: leaked, one reference, no ref-copies allowed, non-const.
2536       //       0: one reference, non-const.
2537       //     n>0: n + 1 references, operations require a lock, const.
2538       //   4. All fields==0 is an empty string, given the extra storage
2539       //      beyond-the-end for a null terminator; thus, the shared
2540       //      empty string representation needs no constructor.
2541
2542       struct _Rep_base
2543       {
2544         size_type               _M_length;
2545         size_type               _M_capacity;
2546         _Atomic_word            _M_refcount;
2547       };
2548
2549       struct _Rep : _Rep_base
2550       {
2551         // Types:
2552         typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
2553
2554         // (Public) Data members:
2555
2556         // The maximum number of individual char_type elements of an
2557         // individual string is determined by _S_max_size. This is the
2558         // value that will be returned by max_size().  (Whereas npos
2559         // is the maximum number of bytes the allocator can allocate.)
2560         // If one was to divvy up the theoretical largest size string,
2561         // with a terminating character and m _CharT elements, it'd
2562         // look like this:
2563         // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
2564         // Solving for m:
2565         // m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
2566         // In addition, this implementation quarters this amount.
2567         static const size_type  _S_max_size;
2568         static const _CharT     _S_terminal;
2569
2570         // The following storage is init'd to 0 by the linker, resulting
2571         // (carefully) in an empty string with one reference.
2572         static size_type _S_empty_rep_storage[];
2573
2574         static _Rep&
2575         _S_empty_rep() _GLIBCXX_NOEXCEPT
2576         {
2577           // NB: Mild hack to avoid strict-aliasing warnings.  Note that
2578           // _S_empty_rep_storage is never modified and the punning should
2579           // be reasonably safe in this case.
2580           void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);
2581           return *reinterpret_cast<_Rep*>(__p);
2582         }
2583
2584         bool
2585         _M_is_leaked() const _GLIBCXX_NOEXCEPT
2586         { return this->_M_refcount < 0; }
2587
2588         bool
2589         _M_is_shared() const _GLIBCXX_NOEXCEPT
2590         { return this->_M_refcount > 0; }
2591
2592         void
2593         _M_set_leaked() _GLIBCXX_NOEXCEPT
2594         { this->_M_refcount = -1; }
2595
2596         void
2597         _M_set_sharable() _GLIBCXX_NOEXCEPT
2598         { this->_M_refcount = 0; }
2599
2600         void
2601         _M_set_length_and_sharable(size_type __n) _GLIBCXX_NOEXCEPT
2602         {
2603 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2604           if (__builtin_expect(this != &_S_empty_rep(), false))
2605 #endif
2606             {
2607               this->_M_set_sharable();  // One reference.
2608               this->_M_length = __n;
2609               traits_type::assign(this->_M_refdata()[__n], _S_terminal);
2610               // grrr. (per 21.3.4)
2611               // You cannot leave those LWG people alone for a second.
2612             }
2613         }
2614
2615         _CharT*
2616         _M_refdata() throw()
2617         { return reinterpret_cast<_CharT*>(this + 1); }
2618
2619         _CharT*
2620         _M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
2621         {
2622           return (!_M_is_leaked() && __alloc1 == __alloc2)
2623                   ? _M_refcopy() : _M_clone(__alloc1);
2624         }
2625
2626         // Create & Destroy
2627         static _Rep*
2628         _S_create(size_type, size_type, const _Alloc&);
2629
2630         void
2631         _M_dispose(const _Alloc& __a) _GLIBCXX_NOEXCEPT
2632         {
2633 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2634           if (__builtin_expect(this != &_S_empty_rep(), false))
2635 #endif
2636             {
2637               // Be race-detector-friendly.  For more info see bits/c++config.
2638               _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this->_M_refcount);
2639               if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
2640                                                          -1) <= 0)
2641                 {
2642                   _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);
2643                   _M_destroy(__a);
2644                 }
2645             }
2646         }  // XXX MT
2647
2648         void
2649         _M_destroy(const _Alloc&) throw();
2650
2651         _CharT*
2652         _M_refcopy() throw()
2653         {
2654 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2655           if (__builtin_expect(this != &_S_empty_rep(), false))
2656 #endif
2657             __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
2658           return _M_refdata();
2659         }  // XXX MT
2660
2661         _CharT*
2662         _M_clone(const _Alloc&, size_type __res = 0);
2663       };
2664
2665       // Use empty-base optimization: http://www.cantrip.org/emptyopt.html
2666       struct _Alloc_hider : _Alloc
2667       {
2668         _Alloc_hider(_CharT* __dat, const _Alloc& __a) _GLIBCXX_NOEXCEPT
2669         : _Alloc(__a), _M_p(__dat) { }
2670
2671         _CharT* _M_p; // The actual data.
2672       };
2673
2674     public:
2675       // Data Members (public):
2676       // NB: This is an unsigned type, and thus represents the maximum
2677       // size that the allocator can hold.
2678       ///  Value returned by various member functions when they fail.
2679       static const size_type    npos = static_cast<size_type>(-1);
2680
2681     private:
2682       // Data Members (private):
2683       mutable _Alloc_hider      _M_dataplus;
2684
2685       _CharT*
2686       _M_data() const _GLIBCXX_NOEXCEPT
2687       { return  _M_dataplus._M_p; }
2688
2689       _CharT*
2690       _M_data(_CharT* __p) _GLIBCXX_NOEXCEPT
2691       { return (_M_dataplus._M_p = __p); }
2692
2693       _Rep*
2694       _M_rep() const _GLIBCXX_NOEXCEPT
2695       { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
2696
2697       // For the internal use we have functions similar to `begin'/`end'
2698       // but they do not call _M_leak.
2699       iterator
2700       _M_ibegin() const _GLIBCXX_NOEXCEPT
2701       { return iterator(_M_data()); }
2702
2703       iterator
2704       _M_iend() const _GLIBCXX_NOEXCEPT
2705       { return iterator(_M_data() + this->size()); }
2706
2707       void
2708       _M_leak()    // for use in begin() & non-const op[]
2709       {
2710         if (!_M_rep()->_M_is_leaked())
2711           _M_leak_hard();
2712       }
2713
2714       size_type
2715       _M_check(size_type __pos, const char* __s) const
2716       {
2717         if (__pos > this->size())
2718           __throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "
2719                                        "this->size() (which is %zu)"),
2720                                    __s, __pos, this->size());
2721         return __pos;
2722       }
2723
2724       void
2725       _M_check_length(size_type __n1, size_type __n2, const char* __s) const
2726       {
2727         if (this->max_size() - (this->size() - __n1) < __n2)
2728           __throw_length_error(__N(__s));
2729       }
2730
2731       // NB: _M_limit doesn't check for a bad __pos value.
2732       size_type
2733       _M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPT
2734       {
2735         const bool __testoff =  __off < this->size() - __pos;
2736         return __testoff ? __off : this->size() - __pos;
2737       }
2738
2739       // True if _Rep and source do not overlap.
2740       bool
2741       _M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPT
2742       {
2743         return (less<const _CharT*>()(__s, _M_data())
2744                 || less<const _CharT*>()(_M_data() + this->size(), __s));
2745       }
2746
2747       // When __n = 1 way faster than the general multichar
2748       // traits_type::copy/move/assign.
2749       static void
2750       _M_copy(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT
2751       {
2752         if (__n == 1)
2753           traits_type::assign(*__d, *__s);
2754         else
2755           traits_type::copy(__d, __s, __n);
2756       }
2757
2758       static void
2759       _M_move(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT
2760       {
2761         if (__n == 1)
2762           traits_type::assign(*__d, *__s);
2763         else
2764           traits_type::move(__d, __s, __n);
2765       }
2766
2767       static void
2768       _M_assign(_CharT* __d, size_type __n, _CharT __c) _GLIBCXX_NOEXCEPT
2769       {
2770         if (__n == 1)
2771           traits_type::assign(*__d, __c);
2772         else
2773           traits_type::assign(__d, __n, __c);
2774       }
2775
2776       // _S_copy_chars is a separate template to permit specialization
2777       // to optimize for the common case of pointers as iterators.
2778       template<class _Iterator>
2779         static void
2780         _S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
2781         _GLIBCXX_NOEXCEPT
2782         {
2783           for (; __k1 != __k2; ++__k1, ++__p)
2784             traits_type::assign(*__p, *__k1); // These types are off.
2785         }
2786
2787       static void
2788       _S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) _GLIBCXX_NOEXCEPT
2789       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
2790
2791       static void
2792       _S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
2793       _GLIBCXX_NOEXCEPT
2794       { _S_copy_chars(__p, __k1.base(), __k2.base()); }
2795
2796       static void
2797       _S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) _GLIBCXX_NOEXCEPT
2798       { _M_copy(__p, __k1, __k2 - __k1); }
2799
2800       static void
2801       _S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
2802       _GLIBCXX_NOEXCEPT
2803       { _M_copy(__p, __k1, __k2 - __k1); }
2804
2805       static int
2806       _S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPT
2807       {
2808         const difference_type __d = difference_type(__n1 - __n2);
2809
2810         if (__d > __gnu_cxx::__numeric_traits<int>::__max)
2811           return __gnu_cxx::__numeric_traits<int>::__max;
2812         else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
2813           return __gnu_cxx::__numeric_traits<int>::__min;
2814         else
2815           return int(__d);
2816       }
2817
2818       void
2819       _M_mutate(size_type __pos, size_type __len1, size_type __len2);
2820
2821       void
2822       _M_leak_hard();
2823
2824       static _Rep&
2825       _S_empty_rep() _GLIBCXX_NOEXCEPT
2826       { return _Rep::_S_empty_rep(); }
2827
2828     public:
2829       // Construct/copy/destroy:
2830       // NB: We overload ctors in some cases instead of using default
2831       // arguments, per 17.4.4.4 para. 2 item 2.
2832
2833       /**
2834        *  @brief  Default constructor creates an empty string.
2835        */
2836       basic_string()
2837 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2838       : _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
2839 #else
2840       : _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()){ }
2841 #endif
2842
2843       /**
2844        *  @brief  Construct an empty string using allocator @a a.
2845        */
2846       explicit
2847       basic_string(const _Alloc& __a);
2848
2849       // NB: per LWG issue 42, semantics different from IS:
2850       /**
2851        *  @brief  Construct string with copy of value of @a str.
2852        *  @param  __str  Source string.
2853        */
2854       basic_string(const basic_string& __str);
2855       /**
2856        *  @brief  Construct string as copy of a substring.
2857        *  @param  __str  Source string.
2858        *  @param  __pos  Index of first character to copy from.
2859        *  @param  __n  Number of characters to copy (default remainder).
2860        */
2861       basic_string(const basic_string& __str, size_type __pos,
2862                    size_type __n = npos);
2863       /**
2864        *  @brief  Construct string as copy of a substring.
2865        *  @param  __str  Source string.
2866        *  @param  __pos  Index of first character to copy from.
2867        *  @param  __n  Number of characters to copy.
2868        *  @param  __a  Allocator to use.
2869        */
2870       basic_string(const basic_string& __str, size_type __pos,
2871                    size_type __n, const _Alloc& __a);
2872
2873       /**
2874        *  @brief  Construct string initialized by a character %array.
2875        *  @param  __s  Source character %array.
2876        *  @param  __n  Number of characters to copy.
2877        *  @param  __a  Allocator to use (default is default allocator).
2878        *
2879        *  NB: @a __s must have at least @a __n characters, &apos;\\0&apos;
2880        *  has no special meaning.
2881        */
2882       basic_string(const _CharT* __s, size_type __n,
2883                    const _Alloc& __a = _Alloc());
2884       /**
2885        *  @brief  Construct string as copy of a C string.
2886        *  @param  __s  Source C string.
2887        *  @param  __a  Allocator to use (default is default allocator).
2888        */
2889       basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
2890       /**
2891        *  @brief  Construct string as multiple characters.
2892        *  @param  __n  Number of characters.
2893        *  @param  __c  Character to use.
2894        *  @param  __a  Allocator to use (default is default allocator).
2895        */
2896       basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
2897
2898 #if __cplusplus >= 201103L
2899       /**
2900        *  @brief  Move construct string.
2901        *  @param  __str  Source string.
2902        *
2903        *  The newly-created string contains the exact contents of @a __str.
2904        *  @a __str is a valid, but unspecified string.
2905        **/
2906       basic_string(basic_string&& __str)
2907 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2908       noexcept // FIXME C++11: should always be noexcept.
2909 #endif
2910       : _M_dataplus(__str._M_dataplus)
2911       {
2912 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2913         __str._M_data(_S_empty_rep()._M_refdata());
2914 #else
2915         __str._M_data(_S_construct(size_type(), _CharT(), get_allocator()));
2916 #endif
2917       }
2918
2919       /**
2920        *  @brief  Construct string from an initializer %list.
2921        *  @param  __l  std::initializer_list of characters.
2922        *  @param  __a  Allocator to use (default is default allocator).
2923        */
2924       basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc());
2925 #endif // C++11
2926
2927       /**
2928        *  @brief  Construct string as copy of a range.
2929        *  @param  __beg  Start of range.
2930        *  @param  __end  End of range.
2931        *  @param  __a  Allocator to use (default is default allocator).
2932        */
2933       template<class _InputIterator>
2934         basic_string(_InputIterator __beg, _InputIterator __end,
2935                      const _Alloc& __a = _Alloc());
2936
2937       /**
2938        *  @brief  Destroy the string instance.
2939        */
2940       ~basic_string() _GLIBCXX_NOEXCEPT
2941       { _M_rep()->_M_dispose(this->get_allocator()); }
2942
2943       /**
2944        *  @brief  Assign the value of @a str to this string.
2945        *  @param  __str  Source string.
2946        */
2947       basic_string&
2948       operator=(const basic_string& __str)
2949       { return this->assign(__str); }
2950
2951       /**
2952        *  @brief  Copy contents of @a s into this string.
2953        *  @param  __s  Source null-terminated string.
2954        */
2955       basic_string&
2956       operator=(const _CharT* __s)
2957       { return this->assign(__s); }
2958
2959       /**
2960        *  @brief  Set value to string of length 1.
2961        *  @param  __c  Source character.
2962        *
2963        *  Assigning to a character makes this string length 1 and
2964        *  (*this)[0] == @a c.
2965        */
2966       basic_string&
2967       operator=(_CharT __c)
2968       {
2969         this->assign(1, __c);
2970         return *this;
2971       }
2972
2973 #if __cplusplus >= 201103L
2974       /**
2975        *  @brief  Move assign the value of @a str to this string.
2976        *  @param  __str  Source string.
2977        *
2978        *  The contents of @a str are moved into this string (without copying).
2979        *  @a str is a valid, but unspecified string.
2980        **/
2981       // PR 58265, this should be noexcept.
2982       basic_string&
2983       operator=(basic_string&& __str)
2984       {
2985         // NB: DR 1204.
2986         this->swap(__str);
2987         return *this;
2988       }
2989
2990       /**
2991        *  @brief  Set value to string constructed from initializer %list.
2992        *  @param  __l  std::initializer_list.
2993        */
2994       basic_string&
2995       operator=(initializer_list<_CharT> __l)
2996       {
2997         this->assign(__l.begin(), __l.size());
2998         return *this;
2999       }
3000 #endif // C++11
3001
3002       // Iterators:
3003       /**
3004        *  Returns a read/write iterator that points to the first character in
3005        *  the %string.  Unshares the string.
3006        */
3007       iterator
3008       begin() // FIXME C++11: should be noexcept.
3009       {
3010         _M_leak();
3011         return iterator(_M_data());
3012       }
3013
3014       /**
3015        *  Returns a read-only (constant) iterator that points to the first
3016        *  character in the %string.
3017        */
3018       const_iterator
3019       begin() const _GLIBCXX_NOEXCEPT
3020       { return const_iterator(_M_data()); }
3021
3022       /**
3023        *  Returns a read/write iterator that points one past the last
3024        *  character in the %string.  Unshares the string.
3025        */
3026       iterator
3027       end() // FIXME C++11: should be noexcept.
3028       {
3029         _M_leak();
3030         return iterator(_M_data() + this->size());
3031       }
3032
3033       /**
3034        *  Returns a read-only (constant) iterator that points one past the
3035        *  last character in the %string.
3036        */
3037       const_iterator
3038       end() const _GLIBCXX_NOEXCEPT
3039       { return const_iterator(_M_data() + this->size()); }
3040
3041       /**
3042        *  Returns a read/write reverse iterator that points to the last
3043        *  character in the %string.  Iteration is done in reverse element
3044        *  order.  Unshares the string.
3045        */
3046       reverse_iterator
3047       rbegin() // FIXME C++11: should be noexcept.
3048       { return reverse_iterator(this->end()); }
3049
3050       /**
3051        *  Returns a read-only (constant) reverse iterator that points
3052        *  to the last character in the %string.  Iteration is done in
3053        *  reverse element order.
3054        */
3055       const_reverse_iterator
3056       rbegin() const _GLIBCXX_NOEXCEPT
3057       { return const_reverse_iterator(this->end()); }
3058
3059       /**
3060        *  Returns a read/write reverse iterator that points to one before the
3061        *  first character in the %string.  Iteration is done in reverse
3062        *  element order.  Unshares the string.
3063        */
3064       reverse_iterator
3065       rend() // FIXME C++11: should be noexcept.
3066       { return reverse_iterator(this->begin()); }
3067
3068       /**
3069        *  Returns a read-only (constant) reverse iterator that points
3070        *  to one before the first character in the %string.  Iteration
3071        *  is done in reverse element order.
3072        */
3073       const_reverse_iterator
3074       rend() const _GLIBCXX_NOEXCEPT
3075       { return const_reverse_iterator(this->begin()); }
3076
3077 #if __cplusplus >= 201103L
3078       /**
3079        *  Returns a read-only (constant) iterator that points to the first
3080        *  character in the %string.
3081        */
3082       const_iterator
3083       cbegin() const noexcept
3084       { return const_iterator(this->_M_data()); }
3085
3086       /**
3087        *  Returns a read-only (constant) iterator that points one past the
3088        *  last character in the %string.
3089        */
3090       const_iterator
3091       cend() const noexcept
3092       { return const_iterator(this->_M_data() + this->size()); }
3093
3094       /**
3095        *  Returns a read-only (constant) reverse iterator that points
3096        *  to the last character in the %string.  Iteration is done in
3097        *  reverse element order.
3098        */
3099       const_reverse_iterator
3100       crbegin() const noexcept
3101       { return const_reverse_iterator(this->end()); }
3102
3103       /**
3104        *  Returns a read-only (constant) reverse iterator that points
3105        *  to one before the first character in the %string.  Iteration
3106        *  is done in reverse element order.
3107        */
3108       const_reverse_iterator
3109       crend() const noexcept
3110       { return const_reverse_iterator(this->begin()); }
3111 #endif
3112
3113     public:
3114       // Capacity:
3115       ///  Returns the number of characters in the string, not including any
3116       ///  null-termination.
3117       size_type
3118       size() const _GLIBCXX_NOEXCEPT
3119       { return _M_rep()->_M_length; }
3120
3121       ///  Returns the number of characters in the string, not including any
3122       ///  null-termination.
3123       size_type
3124       length() const _GLIBCXX_NOEXCEPT
3125       { return _M_rep()->_M_length; }
3126
3127       ///  Returns the size() of the largest possible %string.
3128       size_type
3129       max_size() const _GLIBCXX_NOEXCEPT
3130       { return _Rep::_S_max_size; }
3131
3132       /**
3133        *  @brief  Resizes the %string to the specified number of characters.
3134        *  @param  __n  Number of characters the %string should contain.
3135        *  @param  __c  Character to fill any new elements.
3136        *
3137        *  This function will %resize the %string to the specified
3138        *  number of characters.  If the number is smaller than the
3139        *  %string's current size the %string is truncated, otherwise
3140        *  the %string is extended and new elements are %set to @a __c.
3141        */
3142       void
3143       resize(size_type __n, _CharT __c);
3144
3145       /**
3146        *  @brief  Resizes the %string to the specified number of characters.
3147        *  @param  __n  Number of characters the %string should contain.
3148        *
3149        *  This function will resize the %string to the specified length.  If
3150        *  the new size is smaller than the %string's current size the %string
3151        *  is truncated, otherwise the %string is extended and new characters
3152        *  are default-constructed.  For basic types such as char, this means
3153        *  setting them to 0.
3154        */
3155       void
3156       resize(size_type __n)
3157       { this->resize(__n, _CharT()); }
3158
3159 #if __cplusplus >= 201103L
3160       ///  A non-binding request to reduce capacity() to size().
3161       void
3162       shrink_to_fit() _GLIBCXX_NOEXCEPT
3163       {
3164         if (capacity() > size())
3165           {
3166             __try
3167               { reserve(0); }
3168             __catch(...)
3169               { }
3170           }
3171       }
3172 #endif
3173
3174       /**
3175        *  Returns the total number of characters that the %string can hold
3176        *  before needing to allocate more memory.
3177        */
3178       size_type
3179       capacity() const _GLIBCXX_NOEXCEPT
3180       { return _M_rep()->_M_capacity; }
3181
3182       /**
3183        *  @brief  Attempt to preallocate enough memory for specified number of
3184        *          characters.
3185        *  @param  __res_arg  Number of characters required.
3186        *  @throw  std::length_error  If @a __res_arg exceeds @c max_size().
3187        *
3188        *  This function attempts to reserve enough memory for the
3189        *  %string to hold the specified number of characters.  If the
3190        *  number requested is more than max_size(), length_error is
3191        *  thrown.
3192        *
3193        *  The advantage of this function is that if optimal code is a
3194        *  necessity and the user can determine the string length that will be
3195        *  required, the user can reserve the memory in %advance, and thus
3196        *  prevent a possible reallocation of memory and copying of %string
3197        *  data.
3198        */
3199       void
3200       reserve(size_type __res_arg = 0);
3201
3202       /**
3203        *  Erases the string, making it empty.
3204        */
3205       // PR 56166: this should not throw.
3206       void
3207       clear()
3208       { _M_mutate(0, this->size(), 0); }
3209
3210       /**
3211        *  Returns true if the %string is empty.  Equivalent to
3212        *  <code>*this == ""</code>.
3213        */
3214       bool
3215       empty() const _GLIBCXX_NOEXCEPT
3216       { return this->size() == 0; }
3217
3218       // Element access:
3219       /**
3220        *  @brief  Subscript access to the data contained in the %string.
3221        *  @param  __pos  The index of the character to access.
3222        *  @return  Read-only (constant) reference to the character.
3223        *
3224        *  This operator allows for easy, array-style, data access.
3225        *  Note that data access with this operator is unchecked and
3226        *  out_of_range lookups are not defined. (For checked lookups
3227        *  see at().)
3228        */
3229       const_reference
3230       operator[] (size_type __pos) const _GLIBCXX_NOEXCEPT
3231       {
3232         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
3233         return _M_data()[__pos];
3234       }
3235
3236       /**
3237        *  @brief  Subscript access to the data contained in the %string.
3238        *  @param  __pos  The index of the character to access.
3239        *  @return  Read/write reference to the character.
3240        *
3241        *  This operator allows for easy, array-style, data access.
3242        *  Note that data access with this operator is unchecked and
3243        *  out_of_range lookups are not defined. (For checked lookups
3244        *  see at().)  Unshares the string.
3245        */
3246       reference
3247       operator[](size_type __pos)
3248       {
3249         // Allow pos == size() both in C++98 mode, as v3 extension,
3250         // and in C++11 mode.
3251         _GLIBCXX_DEBUG_ASSERT(__pos <= size());
3252         // In pedantic mode be strict in C++98 mode.
3253         _GLIBCXX_DEBUG_PEDASSERT(__cplusplus >= 201103L || __pos < size());
3254         _M_leak();
3255         return _M_data()[__pos];
3256       }
3257
3258       /**
3259        *  @brief  Provides access to the data contained in the %string.
3260        *  @param __n The index of the character to access.
3261        *  @return  Read-only (const) reference to the character.
3262        *  @throw  std::out_of_range  If @a n is an invalid index.
3263        *
3264        *  This function provides for safer data access.  The parameter is
3265        *  first checked that it is in the range of the string.  The function
3266        *  throws out_of_range if the check fails.
3267        */
3268       const_reference
3269       at(size_type __n) const
3270       {
3271         if (__n >= this->size())
3272           __throw_out_of_range_fmt(__N("basic_string::at: __n "
3273                                        "(which is %zu) >= this->size() "
3274                                        "(which is %zu)"),
3275                                    __n, this->size());
3276         return _M_data()[__n];
3277       }
3278
3279       /**
3280        *  @brief  Provides access to the data contained in the %string.
3281        *  @param __n The index of the character to access.
3282        *  @return  Read/write reference to the character.
3283        *  @throw  std::out_of_range  If @a n is an invalid index.
3284        *
3285        *  This function provides for safer data access.  The parameter is
3286        *  first checked that it is in the range of the string.  The function
3287        *  throws out_of_range if the check fails.  Success results in
3288        *  unsharing the string.
3289        */
3290       reference
3291       at(size_type __n)
3292       {
3293         if (__n >= size())
3294           __throw_out_of_range_fmt(__N("basic_string::at: __n "
3295                                        "(which is %zu) >= this->size() "
3296                                        "(which is %zu)"),
3297                                    __n, this->size());
3298         _M_leak();
3299         return _M_data()[__n];
3300       }
3301
3302 #if __cplusplus >= 201103L
3303       /**
3304        *  Returns a read/write reference to the data at the first
3305        *  element of the %string.
3306        */
3307       reference
3308       front()
3309       { return operator[](0); }
3310
3311       /**
3312        *  Returns a read-only (constant) reference to the data at the first
3313        *  element of the %string.
3314        */
3315       const_reference
3316       front() const _GLIBCXX_NOEXCEPT
3317       { return operator[](0); }
3318
3319       /**
3320        *  Returns a read/write reference to the data at the last
3321        *  element of the %string.
3322        */
3323       reference
3324       back()
3325       { return operator[](this->size() - 1); }
3326
3327       /**
3328        *  Returns a read-only (constant) reference to the data at the
3329        *  last element of the %string.
3330        */
3331       const_reference
3332       back() const _GLIBCXX_NOEXCEPT
3333       { return operator[](this->size() - 1); }
3334 #endif
3335
3336       // Modifiers:
3337       /**
3338        *  @brief  Append a string to this string.
3339        *  @param __str  The string to append.
3340        *  @return  Reference to this string.
3341        */
3342       basic_string&
3343       operator+=(const basic_string& __str)
3344       { return this->append(__str); }
3345
3346       /**
3347        *  @brief  Append a C string.
3348        *  @param __s  The C string to append.
3349        *  @return  Reference to this string.
3350        */
3351       basic_string&
3352       operator+=(const _CharT* __s)
3353       { return this->append(__s); }
3354
3355       /**
3356        *  @brief  Append a character.
3357        *  @param __c  The character to append.
3358        *  @return  Reference to this string.
3359        */
3360       basic_string&
3361       operator+=(_CharT __c)
3362       {
3363         this->push_back(__c);
3364         return *this;
3365       }
3366
3367 #if __cplusplus >= 201103L
3368       /**
3369        *  @brief  Append an initializer_list of characters.
3370        *  @param __l  The initializer_list of characters to be appended.
3371        *  @return  Reference to this string.
3372        */
3373       basic_string&
3374       operator+=(initializer_list<_CharT> __l)
3375       { return this->append(__l.begin(), __l.size()); }
3376 #endif // C++11
3377
3378       /**
3379        *  @brief  Append a string to this string.
3380        *  @param __str  The string to append.
3381        *  @return  Reference to this string.
3382        */
3383       basic_string&
3384       append(const basic_string& __str);
3385
3386       /**
3387        *  @brief  Append a substring.
3388        *  @param __str  The string to append.
3389        *  @param __pos  Index of the first character of str to append.
3390        *  @param __n  The number of characters to append.
3391        *  @return  Reference to this string.
3392        *  @throw  std::out_of_range if @a __pos is not a valid index.
3393        *
3394        *  This function appends @a __n characters from @a __str
3395        *  starting at @a __pos to this string.  If @a __n is is larger
3396        *  than the number of available characters in @a __str, the
3397        *  remainder of @a __str is appended.
3398        */
3399       basic_string&
3400       append(const basic_string& __str, size_type __pos, size_type __n);
3401
3402       /**
3403        *  @brief  Append a C substring.
3404        *  @param __s  The C string to append.
3405        *  @param __n  The number of characters to append.
3406        *  @return  Reference to this string.
3407        */
3408       basic_string&
3409       append(const _CharT* __s, size_type __n);
3410
3411       /**
3412        *  @brief  Append a C string.
3413        *  @param __s  The C string to append.
3414        *  @return  Reference to this string.
3415        */
3416       basic_string&
3417       append(const _CharT* __s)
3418       {
3419         __glibcxx_requires_string(__s);
3420         return this->append(__s, traits_type::length(__s));
3421       }
3422
3423       /**
3424        *  @brief  Append multiple characters.
3425        *  @param __n  The number of characters to append.
3426        *  @param __c  The character to use.
3427        *  @return  Reference to this string.
3428        *
3429        *  Appends __n copies of __c to this string.
3430        */
3431       basic_string&
3432       append(size_type __n, _CharT __c);
3433
3434 #if __cplusplus >= 201103L
3435       /**
3436        *  @brief  Append an initializer_list of characters.
3437        *  @param __l  The initializer_list of characters to append.
3438        *  @return  Reference to this string.
3439        */
3440       basic_string&
3441       append(initializer_list<_CharT> __l)
3442       { return this->append(__l.begin(), __l.size()); }
3443 #endif // C++11
3444
3445       /**
3446        *  @brief  Append a range of characters.
3447        *  @param __first  Iterator referencing the first character to append.
3448        *  @param __last  Iterator marking the end of the range.
3449        *  @return  Reference to this string.
3450        *
3451        *  Appends characters in the range [__first,__last) to this string.
3452        */
3453       template<class _InputIterator>
3454         basic_string&
3455         append(_InputIterator __first, _InputIterator __last)
3456         { return this->replace(_M_iend(), _M_iend(), __first, __last); }
3457
3458       /**
3459        *  @brief  Append a single character.
3460        *  @param __c  Character to append.
3461        */
3462       void
3463       push_back(_CharT __c)
3464       {
3465         const size_type __len = 1 + this->size();
3466         if (__len > this->capacity() || _M_rep()->_M_is_shared())
3467           this->reserve(__len);
3468         traits_type::assign(_M_data()[this->size()], __c);
3469         _M_rep()->_M_set_length_and_sharable(__len);
3470       }
3471
3472       /**
3473        *  @brief  Set value to contents of another string.
3474        *  @param  __str  Source string to use.
3475        *  @return  Reference to this string.
3476        */
3477       basic_string&
3478       assign(const basic_string& __str);
3479
3480 #if __cplusplus >= 201103L
3481       /**
3482        *  @brief  Set value to contents of another string.
3483        *  @param  __str  Source string to use.
3484        *  @return  Reference to this string.
3485        *
3486        *  This function sets this string to the exact contents of @a __str.
3487        *  @a __str is a valid, but unspecified string.
3488        */
3489       // PR 58265, this should be noexcept.
3490       basic_string&
3491       assign(basic_string&& __str)
3492       {
3493         this->swap(__str);
3494         return *this;
3495       }
3496 #endif // C++11
3497
3498       /**
3499        *  @brief  Set value to a substring of a string.
3500        *  @param __str  The string to use.
3501        *  @param __pos  Index of the first character of str.
3502        *  @param __n  Number of characters to use.
3503        *  @return  Reference to this string.
3504        *  @throw  std::out_of_range if @a pos is not a valid index.
3505        *
3506        *  This function sets this string to the substring of @a __str
3507        *  consisting of @a __n characters at @a __pos.  If @a __n is
3508        *  is larger than the number of available characters in @a
3509        *  __str, the remainder of @a __str is used.
3510        */
3511       basic_string&
3512       assign(const basic_string& __str, size_type __pos, size_type __n)
3513       { return this->assign(__str._M_data()
3514                             + __str._M_check(__pos, "basic_string::assign"),
3515                             __str._M_limit(__pos, __n)); }
3516
3517       /**
3518        *  @brief  Set value to a C substring.
3519        *  @param __s  The C string to use.
3520        *  @param __n  Number of characters to use.
3521        *  @return  Reference to this string.
3522        *
3523        *  This function sets the value of this string to the first @a __n
3524        *  characters of @a __s.  If @a __n is is larger than the number of
3525        *  available characters in @a __s, the remainder of @a __s is used.
3526        */
3527       basic_string&
3528       assign(const _CharT* __s, size_type __n);
3529
3530       /**
3531        *  @brief  Set value to contents of a C string.
3532        *  @param __s  The C string to use.
3533        *  @return  Reference to this string.
3534        *
3535        *  This function sets the value of this string to the value of @a __s.
3536        *  The data is copied, so there is no dependence on @a __s once the
3537        *  function returns.
3538        */
3539       basic_string&
3540       assign(const _CharT* __s)
3541       {
3542         __glibcxx_requires_string(__s);
3543         return this->assign(__s, traits_type::length(__s));
3544       }
3545
3546       /**
3547        *  @brief  Set value to multiple characters.
3548        *  @param __n  Length of the resulting string.
3549        *  @param __c  The character to use.
3550        *  @return  Reference to this string.
3551        *
3552        *  This function sets the value of this string to @a __n copies of
3553        *  character @a __c.
3554        */
3555       basic_string&
3556       assign(size_type __n, _CharT __c)
3557       { return _M_replace_aux(size_type(0), this->size(), __n, __c); }
3558
3559       /**
3560        *  @brief  Set value to a range of characters.
3561        *  @param __first  Iterator referencing the first character to append.
3562        *  @param __last  Iterator marking the end of the range.
3563        *  @return  Reference to this string.
3564        *
3565        *  Sets value of string to characters in the range [__first,__last).
3566       */
3567       template<class _InputIterator>
3568         basic_string&
3569         assign(_InputIterator __first, _InputIterator __last)
3570         { return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
3571
3572 #if __cplusplus >= 201103L
3573       /**
3574        *  @brief  Set value to an initializer_list of characters.
3575        *  @param __l  The initializer_list of characters to assign.
3576        *  @return  Reference to this string.
3577        */
3578       basic_string&
3579       assign(initializer_list<_CharT> __l)
3580       { return this->assign(__l.begin(), __l.size()); }
3581 #endif // C++11
3582
3583       /**
3584        *  @brief  Insert multiple characters.
3585        *  @param __p  Iterator referencing location in string to insert at.
3586        *  @param __n  Number of characters to insert
3587        *  @param __c  The character to insert.
3588        *  @throw  std::length_error  If new length exceeds @c max_size().
3589        *
3590        *  Inserts @a __n copies of character @a __c starting at the
3591        *  position referenced by iterator @a __p.  If adding
3592        *  characters causes the length to exceed max_size(),
3593        *  length_error is thrown.  The value of the string doesn't
3594        *  change if an error is thrown.
3595       */
3596       void
3597       insert(iterator __p, size_type __n, _CharT __c)
3598       { this->replace(__p, __p, __n, __c);  }
3599
3600       /**
3601        *  @brief  Insert a range of characters.
3602        *  @param __p  Iterator referencing location in string to insert at.
3603        *  @param __beg  Start of range.
3604        *  @param __end  End of range.
3605        *  @throw  std::length_error  If new length exceeds @c max_size().
3606        *
3607        *  Inserts characters in range [__beg,__end).  If adding
3608        *  characters causes the length to exceed max_size(),
3609        *  length_error is thrown.  The value of the string doesn't
3610        *  change if an error is thrown.
3611       */
3612       template<class _InputIterator>
3613         void
3614         insert(iterator __p, _InputIterator __beg, _InputIterator __end)
3615         { this->replace(__p, __p, __beg, __end); }
3616
3617 #if __cplusplus >= 201103L
3618       /**
3619        *  @brief  Insert an initializer_list of characters.
3620        *  @param __p  Iterator referencing location in string to insert at.
3621        *  @param __l  The initializer_list of characters to insert.
3622        *  @throw  std::length_error  If new length exceeds @c max_size().
3623        */
3624       void
3625       insert(iterator __p, initializer_list<_CharT> __l)
3626       {
3627         _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
3628         this->insert(__p - _M_ibegin(), __l.begin(), __l.size());
3629       }
3630 #endif // C++11
3631
3632       /**
3633        *  @brief  Insert value of a string.
3634        *  @param __pos1  Iterator referencing location in string to insert at.
3635        *  @param __str  The string to insert.
3636        *  @return  Reference to this string.
3637        *  @throw  std::length_error  If new length exceeds @c max_size().
3638        *
3639        *  Inserts value of @a __str starting at @a __pos1.  If adding
3640        *  characters causes the length to exceed max_size(),
3641        *  length_error is thrown.  The value of the string doesn't
3642        *  change if an error is thrown.
3643       */
3644       basic_string&
3645       insert(size_type __pos1, const basic_string& __str)
3646       { return this->insert(__pos1, __str, size_type(0), __str.size()); }
3647
3648       /**
3649        *  @brief  Insert a substring.
3650        *  @param __pos1  Iterator referencing location in string to insert at.
3651        *  @param __str  The string to insert.
3652        *  @param __pos2  Start of characters in str to insert.
3653        *  @param __n  Number of characters to insert.
3654        *  @return  Reference to this string.
3655        *  @throw  std::length_error  If new length exceeds @c max_size().
3656        *  @throw  std::out_of_range  If @a pos1 > size() or
3657        *  @a __pos2 > @a str.size().
3658        *
3659        *  Starting at @a pos1, insert @a __n character of @a __str
3660        *  beginning with @a __pos2.  If adding characters causes the
3661        *  length to exceed max_size(), length_error is thrown.  If @a
3662        *  __pos1 is beyond the end of this string or @a __pos2 is
3663        *  beyond the end of @a __str, out_of_range is thrown.  The
3664        *  value of the string doesn't change if an error is thrown.
3665       */
3666       basic_string&
3667       insert(size_type __pos1, const basic_string& __str,
3668              size_type __pos2, size_type __n)
3669       { return this->insert(__pos1, __str._M_data()
3670                             + __str._M_check(__pos2, "basic_string::insert"),
3671                             __str._M_limit(__pos2, __n)); }
3672
3673       /**
3674        *  @brief  Insert a C substring.
3675        *  @param __pos  Iterator referencing location in string to insert at.
3676        *  @param __s  The C string to insert.
3677        *  @param __n  The number of characters to insert.
3678        *  @return  Reference to this string.
3679        *  @throw  std::length_error  If new length exceeds @c max_size().
3680        *  @throw  std::out_of_range  If @a __pos is beyond the end of this
3681        *  string.
3682        *
3683        *  Inserts the first @a __n characters of @a __s starting at @a
3684        *  __pos.  If adding characters causes the length to exceed
3685        *  max_size(), length_error is thrown.  If @a __pos is beyond
3686        *  end(), out_of_range is thrown.  The value of the string
3687        *  doesn't change if an error is thrown.
3688       */
3689       basic_string&
3690       insert(size_type __pos, const _CharT* __s, size_type __n);
3691
3692       /**
3693        *  @brief  Insert a C string.
3694        *  @param __pos  Iterator referencing location in string to insert at.
3695        *  @param __s  The C string to insert.
3696        *  @return  Reference to this string.
3697        *  @throw  std::length_error  If new length exceeds @c max_size().
3698        *  @throw  std::out_of_range  If @a pos is beyond the end of this
3699        *  string.
3700        *
3701        *  Inserts the first @a n characters of @a __s starting at @a __pos.  If
3702        *  adding characters causes the length to exceed max_size(),
3703        *  length_error is thrown.  If @a __pos is beyond end(), out_of_range is
3704        *  thrown.  The value of the string doesn't change if an error is
3705        *  thrown.
3706       */
3707       basic_string&
3708       insert(size_type __pos, const _CharT* __s)
3709       {
3710         __glibcxx_requires_string(__s);
3711         return this->insert(__pos, __s, traits_type::length(__s));
3712       }
3713
3714       /**
3715        *  @brief  Insert multiple characters.
3716        *  @param __pos  Index in string to insert at.
3717        *  @param __n  Number of characters to insert
3718        *  @param __c  The character to insert.
3719        *  @return  Reference to this string.
3720        *  @throw  std::length_error  If new length exceeds @c max_size().
3721        *  @throw  std::out_of_range  If @a __pos is beyond the end of this
3722        *  string.
3723        *
3724        *  Inserts @a __n copies of character @a __c starting at index
3725        *  @a __pos.  If adding characters causes the length to exceed
3726        *  max_size(), length_error is thrown.  If @a __pos > length(),
3727        *  out_of_range is thrown.  The value of the string doesn't
3728        *  change if an error is thrown.
3729       */
3730       basic_string&
3731       insert(size_type __pos, size_type __n, _CharT __c)
3732       { return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
3733                               size_type(0), __n, __c); }
3734
3735       /**
3736        *  @brief  Insert one character.
3737        *  @param __p  Iterator referencing position in string to insert at.
3738        *  @param __c  The character to insert.
3739        *  @return  Iterator referencing newly inserted char.
3740        *  @throw  std::length_error  If new length exceeds @c max_size().
3741        *
3742        *  Inserts character @a __c at position referenced by @a __p.
3743        *  If adding character causes the length to exceed max_size(),
3744        *  length_error is thrown.  If @a __p is beyond end of string,
3745        *  out_of_range is thrown.  The value of the string doesn't
3746        *  change if an error is thrown.
3747       */
3748       iterator
3749       insert(iterator __p, _CharT __c)
3750       {
3751         _GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
3752         const size_type __pos = __p - _M_ibegin();
3753         _M_replace_aux(__pos, size_type(0), size_type(1), __c);
3754         _M_rep()->_M_set_leaked();
3755         return iterator(_M_data() + __pos);
3756       }
3757
3758       /**
3759        *  @brief  Remove characters.
3760        *  @param __pos  Index of first character to remove (default 0).
3761        *  @param __n  Number of characters to remove (default remainder).
3762        *  @return  Reference to this string.
3763        *  @throw  std::out_of_range  If @a pos is beyond the end of this
3764        *  string.
3765        *
3766        *  Removes @a __n characters from this string starting at @a
3767        *  __pos.  The length of the string is reduced by @a __n.  If
3768        *  there are < @a __n characters to remove, the remainder of
3769        *  the string is truncated.  If @a __p is beyond end of string,
3770        *  out_of_range is thrown.  The value of the string doesn't
3771        *  change if an error is thrown.
3772       */
3773       basic_string&
3774       erase(size_type __pos = 0, size_type __n = npos)
3775       {
3776         _M_mutate(_M_check(__pos, "basic_string::erase"),
3777                   _M_limit(__pos, __n), size_type(0));
3778         return *this;
3779       }
3780
3781       /**
3782        *  @brief  Remove one character.
3783        *  @param __position  Iterator referencing the character to remove.
3784        *  @return  iterator referencing same location after removal.
3785        *
3786        *  Removes the character at @a __position from this string. The value
3787        *  of the string doesn't change if an error is thrown.
3788       */
3789       iterator
3790       erase(iterator __position)
3791       {
3792         _GLIBCXX_DEBUG_PEDASSERT(__position >= _M_ibegin()
3793                                  && __position < _M_iend());
3794         const size_type __pos = __position - _M_ibegin();
3795         _M_mutate(__pos, size_type(1), size_type(0));
3796         _M_rep()->_M_set_leaked();
3797         return iterator(_M_data() + __pos);
3798       }
3799
3800       /**
3801        *  @brief  Remove a range of characters.
3802        *  @param __first  Iterator referencing the first character to remove.
3803        *  @param __last  Iterator referencing the end of the range.
3804        *  @return  Iterator referencing location of first after removal.
3805        *
3806        *  Removes the characters in the range [first,last) from this string.
3807        *  The value of the string doesn't change if an error is thrown.
3808       */
3809       iterator
3810       erase(iterator __first, iterator __last);
3811
3812 #if __cplusplus >= 201103L
3813       /**
3814        *  @brief  Remove the last character.
3815        *
3816        *  The string must be non-empty.
3817        */
3818       void
3819       pop_back() // FIXME C++11: should be noexcept.
3820       { erase(size()-1, 1); }
3821 #endif // C++11
3822
3823       /**
3824        *  @brief  Replace characters with value from another string.
3825        *  @param __pos  Index of first character to replace.
3826        *  @param __n  Number of characters to be replaced.
3827        *  @param __str  String to insert.
3828        *  @return  Reference to this string.
3829        *  @throw  std::out_of_range  If @a pos is beyond the end of this
3830        *  string.
3831        *  @throw  std::length_error  If new length exceeds @c max_size().
3832        *
3833        *  Removes the characters in the range [__pos,__pos+__n) from
3834        *  this string.  In place, the value of @a __str is inserted.
3835        *  If @a __pos is beyond end of string, out_of_range is thrown.
3836        *  If the length of the result exceeds max_size(), length_error
3837        *  is thrown.  The value of the string doesn't change if an
3838        *  error is thrown.
3839       */
3840       basic_string&
3841       replace(size_type __pos, size_type __n, const basic_string& __str)
3842       { return this->replace(__pos, __n, __str._M_data(), __str.size()); }
3843
3844       /**
3845        *  @brief  Replace characters with value from another string.
3846        *  @param __pos1  Index of first character to replace.
3847        *  @param __n1  Number of characters to be replaced.
3848        *  @param __str  String to insert.
3849        *  @param __pos2  Index of first character of str to use.
3850        *  @param __n2  Number of characters from str to use.
3851        *  @return  Reference to this string.
3852        *  @throw  std::out_of_range  If @a __pos1 > size() or @a __pos2 >
3853        *  __str.size().
3854        *  @throw  std::length_error  If new length exceeds @c max_size().
3855        *
3856        *  Removes the characters in the range [__pos1,__pos1 + n) from this
3857        *  string.  In place, the value of @a __str is inserted.  If @a __pos is
3858        *  beyond end of string, out_of_range is thrown.  If the length of the
3859        *  result exceeds max_size(), length_error is thrown.  The value of the
3860        *  string doesn't change if an error is thrown.
3861       */
3862       basic_string&
3863       replace(size_type __pos1, size_type __n1, const basic_string& __str,
3864               size_type __pos2, size_type __n2)
3865       { return this->replace(__pos1, __n1, __str._M_data()
3866                              + __str._M_check(__pos2, "basic_string::replace"),
3867                              __str._M_limit(__pos2, __n2)); }
3868
3869       /**
3870        *  @brief  Replace characters with value of a C substring.
3871        *  @param __pos  Index of first character to replace.
3872        *  @param __n1  Number of characters to be replaced.
3873        *  @param __s  C string to insert.
3874        *  @param __n2  Number of characters from @a s to use.
3875        *  @return  Reference to this string.
3876        *  @throw  std::out_of_range  If @a pos1 > size().
3877        *  @throw  std::length_error  If new length exceeds @c max_size().
3878        *
3879        *  Removes the characters in the range [__pos,__pos + __n1)
3880        *  from this string.  In place, the first @a __n2 characters of
3881        *  @a __s are inserted, or all of @a __s if @a __n2 is too large.  If
3882        *  @a __pos is beyond end of string, out_of_range is thrown.  If
3883        *  the length of result exceeds max_size(), length_error is
3884        *  thrown.  The value of the string doesn't change if an error
3885        *  is thrown.
3886       */
3887       basic_string&
3888       replace(size_type __pos, size_type __n1, const _CharT* __s,
3889               size_type __n2);
3890
3891       /**
3892        *  @brief  Replace characters with value of a C string.
3893        *  @param __pos  Index of first character to replace.
3894        *  @param __n1  Number of characters to be replaced.
3895        *  @param __s  C string to insert.
3896        *  @return  Reference to this string.
3897        *  @throw  std::out_of_range  If @a pos > size().
3898        *  @throw  std::length_error  If new length exceeds @c max_size().
3899        *
3900        *  Removes the characters in the range [__pos,__pos + __n1)
3901        *  from this string.  In place, the characters of @a __s are
3902        *  inserted.  If @a __pos is beyond end of string, out_of_range
3903        *  is thrown.  If the length of result exceeds max_size(),
3904        *  length_error is thrown.  The value of the string doesn't
3905        *  change if an error is thrown.
3906       */
3907       basic_string&
3908       replace(size_type __pos, size_type __n1, const _CharT* __s)
3909       {
3910         __glibcxx_requires_string(__s);
3911         return this->replace(__pos, __n1, __s, traits_type::length(__s));
3912       }
3913
3914       /**
3915        *  @brief  Replace characters with multiple characters.
3916        *  @param __pos  Index of first character to replace.
3917        *  @param __n1  Number of characters to be replaced.
3918        *  @param __n2  Number of characters to insert.
3919        *  @param __c  Character to insert.
3920        *  @return  Reference to this string.
3921        *  @throw  std::out_of_range  If @a __pos > size().
3922        *  @throw  std::length_error  If new length exceeds @c max_size().
3923        *
3924        *  Removes the characters in the range [pos,pos + n1) from this
3925        *  string.  In place, @a __n2 copies of @a __c are inserted.
3926        *  If @a __pos is beyond end of string, out_of_range is thrown.
3927        *  If the length of result exceeds max_size(), length_error is
3928        *  thrown.  The value of the string doesn't change if an error
3929        *  is thrown.
3930       */
3931       basic_string&
3932       replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
3933       { return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
3934                               _M_limit(__pos, __n1), __n2, __c); }
3935
3936       /**
3937        *  @brief  Replace range of characters with string.
3938        *  @param __i1  Iterator referencing start of range to replace.
3939        *  @param __i2  Iterator referencing end of range to replace.
3940        *  @param __str  String value to insert.
3941        *  @return  Reference to this string.
3942        *  @throw  std::length_error  If new length exceeds @c max_size().
3943        *
3944        *  Removes the characters in the range [__i1,__i2).  In place,
3945        *  the value of @a __str is inserted.  If the length of result
3946        *  exceeds max_size(), length_error is thrown.  The value of
3947        *  the string doesn't change if an error is thrown.
3948       */
3949       basic_string&
3950       replace(iterator __i1, iterator __i2, const basic_string& __str)
3951       { return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
3952
3953       /**
3954        *  @brief  Replace range of characters with C substring.
3955        *  @param __i1  Iterator referencing start of range to replace.
3956        *  @param __i2  Iterator referencing end of range to replace.
3957        *  @param __s  C string value to insert.
3958        *  @param __n  Number of characters from s to insert.
3959        *  @return  Reference to this string.
3960        *  @throw  std::length_error  If new length exceeds @c max_size().
3961        *
3962        *  Removes the characters in the range [__i1,__i2).  In place,
3963        *  the first @a __n characters of @a __s are inserted.  If the
3964        *  length of result exceeds max_size(), length_error is thrown.
3965        *  The value of the string doesn't change if an error is
3966        *  thrown.
3967       */
3968       basic_string&
3969       replace(iterator __i1, iterator __i2, const _CharT* __s, size_type __n)
3970       {
3971         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
3972                                  && __i2 <= _M_iend());
3973         return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n);
3974       }
3975
3976       /**
3977        *  @brief  Replace range of characters with C string.
3978        *  @param __i1  Iterator referencing start of range to replace.
3979        *  @param __i2  Iterator referencing end of range to replace.
3980        *  @param __s  C string value to insert.
3981        *  @return  Reference to this string.
3982        *  @throw  std::length_error  If new length exceeds @c max_size().
3983        *
3984        *  Removes the characters in the range [__i1,__i2).  In place,
3985        *  the characters of @a __s are inserted.  If the length of
3986        *  result exceeds max_size(), length_error is thrown.  The
3987        *  value of the string doesn't change if an error is thrown.
3988       */
3989       basic_string&
3990       replace(iterator __i1, iterator __i2, const _CharT* __s)
3991       {
3992         __glibcxx_requires_string(__s);
3993         return this->replace(__i1, __i2, __s, traits_type::length(__s));
3994       }
3995
3996       /**
3997        *  @brief  Replace range of characters with multiple characters
3998        *  @param __i1  Iterator referencing start of range to replace.
3999        *  @param __i2  Iterator referencing end of range to replace.
4000        *  @param __n  Number of characters to insert.
4001        *  @param __c  Character to insert.
4002        *  @return  Reference to this string.
4003        *  @throw  std::length_error  If new length exceeds @c max_size().
4004        *
4005        *  Removes the characters in the range [__i1,__i2).  In place,
4006        *  @a __n copies of @a __c are inserted.  If the length of
4007        *  result exceeds max_size(), length_error is thrown.  The
4008        *  value of the string doesn't change if an error is thrown.
4009       */
4010       basic_string&
4011       replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
4012       {
4013         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4014                                  && __i2 <= _M_iend());
4015         return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __c);
4016       }
4017
4018       /**
4019        *  @brief  Replace range of characters with range.
4020        *  @param __i1  Iterator referencing start of range to replace.
4021        *  @param __i2  Iterator referencing end of range to replace.
4022        *  @param __k1  Iterator referencing start of range to insert.
4023        *  @param __k2  Iterator referencing end of range to insert.
4024        *  @return  Reference to this string.
4025        *  @throw  std::length_error  If new length exceeds @c max_size().
4026        *
4027        *  Removes the characters in the range [__i1,__i2).  In place,
4028        *  characters in the range [__k1,__k2) are inserted.  If the
4029        *  length of result exceeds max_size(), length_error is thrown.
4030        *  The value of the string doesn't change if an error is
4031        *  thrown.
4032       */
4033       template<class _InputIterator>
4034         basic_string&
4035         replace(iterator __i1, iterator __i2,
4036                 _InputIterator __k1, _InputIterator __k2)
4037         {
4038           _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4039                                    && __i2 <= _M_iend());
4040           __glibcxx_requires_valid_range(__k1, __k2);
4041           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
4042           return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
4043         }
4044
4045       // Specializations for the common case of pointer and iterator:
4046       // useful to avoid the overhead of temporary buffering in _M_replace.
4047       basic_string&
4048       replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
4049       {
4050         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4051                                  && __i2 <= _M_iend());
4052         __glibcxx_requires_valid_range(__k1, __k2);
4053         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4054                              __k1, __k2 - __k1);
4055       }
4056
4057       basic_string&
4058       replace(iterator __i1, iterator __i2,
4059               const _CharT* __k1, const _CharT* __k2)
4060       {
4061         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4062                                  && __i2 <= _M_iend());
4063         __glibcxx_requires_valid_range(__k1, __k2);
4064         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4065                              __k1, __k2 - __k1);
4066       }
4067
4068       basic_string&
4069       replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
4070       {
4071         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4072                                  && __i2 <= _M_iend());
4073         __glibcxx_requires_valid_range(__k1, __k2);
4074         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4075                              __k1.base(), __k2 - __k1);
4076       }
4077
4078       basic_string&
4079       replace(iterator __i1, iterator __i2,
4080               const_iterator __k1, const_iterator __k2)
4081       {
4082         _GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4083                                  && __i2 <= _M_iend());
4084         __glibcxx_requires_valid_range(__k1, __k2);
4085         return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4086                              __k1.base(), __k2 - __k1);
4087       }
4088
4089 #if __cplusplus >= 201103L
4090       /**
4091        *  @brief  Replace range of characters with initializer_list.
4092        *  @param __i1  Iterator referencing start of range to replace.
4093        *  @param __i2  Iterator referencing end of range to replace.
4094        *  @param __l  The initializer_list of characters to insert.
4095        *  @return  Reference to this string.
4096        *  @throw  std::length_error  If new length exceeds @c max_size().
4097        *
4098        *  Removes the characters in the range [__i1,__i2).  In place,
4099        *  characters in the range [__k1,__k2) are inserted.  If the
4100        *  length of result exceeds max_size(), length_error is thrown.
4101        *  The value of the string doesn't change if an error is
4102        *  thrown.
4103       */
4104       basic_string& replace(iterator __i1, iterator __i2,
4105                             initializer_list<_CharT> __l)
4106       { return this->replace(__i1, __i2, __l.begin(), __l.end()); }
4107 #endif // C++11
4108
4109     private:
4110       template<class _Integer>
4111         basic_string&
4112         _M_replace_dispatch(iterator __i1, iterator __i2, _Integer __n,
4113                             _Integer __val, __true_type)
4114         { return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __val); }
4115
4116       template<class _InputIterator>
4117         basic_string&
4118         _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
4119                             _InputIterator __k2, __false_type);
4120
4121       basic_string&
4122       _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
4123                      _CharT __c);
4124
4125       basic_string&
4126       _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
4127                       size_type __n2);
4128
4129       // _S_construct_aux is used to implement the 21.3.1 para 15 which
4130       // requires special behaviour if _InIter is an integral type
4131       template<class _InIterator>
4132         static _CharT*
4133         _S_construct_aux(_InIterator __beg, _InIterator __end,
4134                          const _Alloc& __a, __false_type)
4135         {
4136           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
4137           return _S_construct(__beg, __end, __a, _Tag());
4138         }
4139
4140       // _GLIBCXX_RESOLVE_LIB_DEFECTS
4141       // 438. Ambiguity in the "do the right thing" clause
4142       template<class _Integer>
4143         static _CharT*
4144         _S_construct_aux(_Integer __beg, _Integer __end,
4145                          const _Alloc& __a, __true_type)
4146         { return _S_construct_aux_2(static_cast<size_type>(__beg),
4147                                     __end, __a); }
4148
4149       static _CharT*
4150       _S_construct_aux_2(size_type __req, _CharT __c, const _Alloc& __a)
4151       { return _S_construct(__req, __c, __a); }
4152
4153       template<class _InIterator>
4154         static _CharT*
4155         _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
4156         {
4157           typedef typename std::__is_integer<_InIterator>::__type _Integral;
4158           return _S_construct_aux(__beg, __end, __a, _Integral());
4159         }
4160
4161       // For Input Iterators, used in istreambuf_iterators, etc.
4162       template<class _InIterator>
4163         static _CharT*
4164          _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
4165                       input_iterator_tag);
4166
4167       // For forward_iterators up to random_access_iterators, used for
4168       // string::iterator, _CharT*, etc.
4169       template<class _FwdIterator>
4170         static _CharT*
4171         _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
4172                      forward_iterator_tag);
4173
4174       static _CharT*
4175       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
4176
4177     public:
4178
4179       /**
4180        *  @brief  Copy substring into C string.
4181        *  @param __s  C string to copy value into.
4182        *  @param __n  Number of characters to copy.
4183        *  @param __pos  Index of first character to copy.
4184        *  @return  Number of characters actually copied
4185        *  @throw  std::out_of_range  If __pos > size().
4186        *
4187        *  Copies up to @a __n characters starting at @a __pos into the
4188        *  C string @a __s.  If @a __pos is %greater than size(),
4189        *  out_of_range is thrown.
4190       */
4191       size_type
4192       copy(_CharT* __s, size_type __n, size_type __pos = 0) const;
4193
4194       /**
4195        *  @brief  Swap contents with another string.
4196        *  @param __s  String to swap with.
4197        *
4198        *  Exchanges the contents of this string with that of @a __s in constant
4199        *  time.
4200       */
4201       // PR 58265, this should be noexcept.
4202       void
4203       swap(basic_string& __s);
4204
4205       // String operations:
4206       /**
4207        *  @brief  Return const pointer to null-terminated contents.
4208        *
4209        *  This is a handle to internal data.  Do not modify or dire things may
4210        *  happen.
4211       */
4212       const _CharT*
4213       c_str() const _GLIBCXX_NOEXCEPT
4214       { return _M_data(); }
4215
4216       /**
4217        *  @brief  Return const pointer to contents.
4218        *
4219        *  This is a handle to internal data.  Do not modify or dire things may
4220        *  happen.
4221       */
4222       const _CharT*
4223       data() const _GLIBCXX_NOEXCEPT
4224       { return _M_data(); }
4225
4226       /**
4227        *  @brief  Return copy of allocator used to construct this string.
4228       */
4229       allocator_type
4230       get_allocator() const _GLIBCXX_NOEXCEPT
4231       { return _M_dataplus; }
4232
4233       /**
4234        *  @brief  Find position of a C substring.
4235        *  @param __s  C string to locate.
4236        *  @param __pos  Index of character to search from.
4237        *  @param __n  Number of characters from @a s to search for.
4238        *  @return  Index of start of first occurrence.
4239        *
4240        *  Starting from @a __pos, searches forward for the first @a
4241        *  __n characters in @a __s within this string.  If found,
4242        *  returns the index where it begins.  If not found, returns
4243        *  npos.
4244       */
4245       size_type
4246       find(const _CharT* __s, size_type __pos, size_type __n) const;
4247
4248       /**
4249        *  @brief  Find position of a string.
4250        *  @param __str  String to locate.
4251        *  @param __pos  Index of character to search from (default 0).
4252        *  @return  Index of start of first occurrence.
4253        *
4254        *  Starting from @a __pos, searches forward for value of @a __str within
4255        *  this string.  If found, returns the index where it begins.  If not
4256        *  found, returns npos.
4257       */
4258       size_type
4259       find(const basic_string& __str, size_type __pos = 0) const
4260         _GLIBCXX_NOEXCEPT
4261       { return this->find(__str.data(), __pos, __str.size()); }
4262
4263       /**
4264        *  @brief  Find position of a C string.
4265        *  @param __s  C string to locate.
4266        *  @param __pos  Index of character to search from (default 0).
4267        *  @return  Index of start of first occurrence.
4268        *
4269        *  Starting from @a __pos, searches forward for the value of @a
4270        *  __s within this string.  If found, returns the index where
4271        *  it begins.  If not found, returns npos.
4272       */
4273       size_type
4274       find(const _CharT* __s, size_type __pos = 0) const
4275       {
4276         __glibcxx_requires_string(__s);
4277         return this->find(__s, __pos, traits_type::length(__s));
4278       }
4279
4280       /**
4281        *  @brief  Find position of a character.
4282        *  @param __c  Character to locate.
4283        *  @param __pos  Index of character to search from (default 0).
4284        *  @return  Index of first occurrence.
4285        *
4286        *  Starting from @a __pos, searches forward for @a __c within
4287        *  this string.  If found, returns the index where it was
4288        *  found.  If not found, returns npos.
4289       */
4290       size_type
4291       find(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT;
4292
4293       /**
4294        *  @brief  Find last position of a string.
4295        *  @param __str  String to locate.
4296        *  @param __pos  Index of character to search back from (default end).
4297        *  @return  Index of start of last occurrence.
4298        *
4299        *  Starting from @a __pos, searches backward for value of @a
4300        *  __str within this string.  If found, returns the index where
4301        *  it begins.  If not found, returns npos.
4302       */
4303       size_type
4304       rfind(const basic_string& __str, size_type __pos = npos) const
4305         _GLIBCXX_NOEXCEPT
4306       { return this->rfind(__str.data(), __pos, __str.size()); }
4307
4308       /**
4309        *  @brief  Find last position of a C substring.
4310        *  @param __s  C string to locate.
4311        *  @param __pos  Index of character to search back from.
4312        *  @param __n  Number of characters from s to search for.
4313        *  @return  Index of start of last occurrence.
4314        *
4315        *  Starting from @a __pos, searches backward for the first @a
4316        *  __n characters in @a __s within this string.  If found,
4317        *  returns the index where it begins.  If not found, returns
4318        *  npos.
4319       */
4320       size_type
4321       rfind(const _CharT* __s, size_type __pos, size_type __n) const;
4322
4323       /**
4324        *  @brief  Find last position of a C string.
4325        *  @param __s  C string to locate.
4326        *  @param __pos  Index of character to start search at (default end).
4327        *  @return  Index of start of  last occurrence.
4328        *
4329        *  Starting from @a __pos, searches backward for the value of
4330        *  @a __s within this string.  If found, returns the index
4331        *  where it begins.  If not found, returns npos.
4332       */
4333       size_type
4334       rfind(const _CharT* __s, size_type __pos = npos) const
4335       {
4336         __glibcxx_requires_string(__s);
4337         return this->rfind(__s, __pos, traits_type::length(__s));
4338       }
4339
4340       /**
4341        *  @brief  Find last position of a character.
4342        *  @param __c  Character to locate.
4343        *  @param __pos  Index of character to search back from (default end).
4344        *  @return  Index of last occurrence.
4345        *
4346        *  Starting from @a __pos, searches backward for @a __c within
4347        *  this string.  If found, returns the index where it was
4348        *  found.  If not found, returns npos.
4349       */
4350       size_type
4351       rfind(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT;
4352
4353       /**
4354        *  @brief  Find position of a character of string.
4355        *  @param __str  String containing characters to locate.
4356        *  @param __pos  Index of character to search from (default 0).
4357        *  @return  Index of first occurrence.
4358        *
4359        *  Starting from @a __pos, searches forward for one of the
4360        *  characters of @a __str within this string.  If found,
4361        *  returns the index where it was found.  If not found, returns
4362        *  npos.
4363       */
4364       size_type
4365       find_first_of(const basic_string& __str, size_type __pos = 0) const
4366         _GLIBCXX_NOEXCEPT
4367       { return this->find_first_of(__str.data(), __pos, __str.size()); }
4368
4369       /**
4370        *  @brief  Find position of a character of C substring.
4371        *  @param __s  String containing characters to locate.
4372        *  @param __pos  Index of character to search from.
4373        *  @param __n  Number of characters from s to search for.
4374        *  @return  Index of first occurrence.
4375        *
4376        *  Starting from @a __pos, searches forward for one of the
4377        *  first @a __n characters of @a __s within this string.  If
4378        *  found, returns the index where it was found.  If not found,
4379        *  returns npos.
4380       */
4381       size_type
4382       find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
4383
4384       /**
4385        *  @brief  Find position of a character of C string.
4386        *  @param __s  String containing characters to locate.
4387        *  @param __pos  Index of character to search from (default 0).
4388        *  @return  Index of first occurrence.
4389        *
4390        *  Starting from @a __pos, searches forward for one of the
4391        *  characters of @a __s within this string.  If found, returns
4392        *  the index where it was found.  If not found, returns npos.
4393       */
4394       size_type
4395       find_first_of(const _CharT* __s, size_type __pos = 0) const
4396       {
4397         __glibcxx_requires_string(__s);
4398         return this->find_first_of(__s, __pos, traits_type::length(__s));
4399       }
4400
4401       /**
4402        *  @brief  Find position of a character.
4403        *  @param __c  Character to locate.
4404        *  @param __pos  Index of character to search from (default 0).
4405        *  @return  Index of first occurrence.
4406        *
4407        *  Starting from @a __pos, searches forward for the character
4408        *  @a __c within this string.  If found, returns the index
4409        *  where it was found.  If not found, returns npos.
4410        *
4411        *  Note: equivalent to find(__c, __pos).
4412       */
4413       size_type
4414       find_first_of(_CharT __c, size_type __pos = 0) const _GLIBCXX_NOEXCEPT
4415       { return this->find(__c, __pos); }
4416
4417       /**
4418        *  @brief  Find last position of a character of string.
4419        *  @param __str  String containing characters to locate.
4420        *  @param __pos  Index of character to search back from (default end).
4421        *  @return  Index of last occurrence.
4422        *
4423        *  Starting from @a __pos, searches backward for one of the
4424        *  characters of @a __str within this string.  If found,
4425        *  returns the index where it was found.  If not found, returns
4426        *  npos.
4427       */
4428       size_type
4429       find_last_of(const basic_string& __str, size_type __pos = npos) const
4430         _GLIBCXX_NOEXCEPT
4431       { return this->find_last_of(__str.data(), __pos, __str.size()); }
4432
4433       /**
4434        *  @brief  Find last position of a character of C substring.
4435        *  @param __s  C string containing characters to locate.
4436        *  @param __pos  Index of character to search back from.
4437        *  @param __n  Number of characters from s to search for.
4438        *  @return  Index of last occurrence.
4439        *
4440        *  Starting from @a __pos, searches backward for one of the
4441        *  first @a __n characters of @a __s within this string.  If
4442        *  found, returns the index where it was found.  If not found,
4443        *  returns npos.
4444       */
4445       size_type
4446       find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
4447
4448       /**
4449        *  @brief  Find last position of a character of C string.
4450        *  @param __s  C string containing characters to locate.
4451        *  @param __pos  Index of character to search back from (default end).
4452        *  @return  Index of last occurrence.
4453        *
4454        *  Starting from @a __pos, searches backward for one of the
4455        *  characters of @a __s within this string.  If found, returns
4456        *  the index where it was found.  If not found, returns npos.
4457       */
4458       size_type
4459       find_last_of(const _CharT* __s, size_type __pos = npos) const
4460       {
4461         __glibcxx_requires_string(__s);
4462         return this->find_last_of(__s, __pos, traits_type::length(__s));
4463       }
4464
4465       /**
4466        *  @brief  Find last position of a character.
4467        *  @param __c  Character to locate.
4468        *  @param __pos  Index of character to search back from (default end).
4469        *  @return  Index of last occurrence.
4470        *
4471        *  Starting from @a __pos, searches backward for @a __c within
4472        *  this string.  If found, returns the index where it was
4473        *  found.  If not found, returns npos.
4474        *
4475        *  Note: equivalent to rfind(__c, __pos).
4476       */
4477       size_type
4478       find_last_of(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT
4479       { return this->rfind(__c, __pos); }
4480
4481       /**
4482        *  @brief  Find position of a character not in string.
4483        *  @param __str  String containing characters to avoid.
4484        *  @param __pos  Index of character to search from (default 0).
4485        *  @return  Index of first occurrence.
4486        *
4487        *  Starting from @a __pos, searches forward for a character not contained
4488        *  in @a __str within this string.  If found, returns the index where it
4489        *  was found.  If not found, returns npos.
4490       */
4491       size_type
4492       find_first_not_of(const basic_string& __str, size_type __pos = 0) const
4493         _GLIBCXX_NOEXCEPT
4494       { return this->find_first_not_of(__str.data(), __pos, __str.size()); }
4495
4496       /**
4497        *  @brief  Find position of a character not in C substring.
4498        *  @param __s  C string containing characters to avoid.
4499        *  @param __pos  Index of character to search from.
4500        *  @param __n  Number of characters from __s to consider.
4501        *  @return  Index of first occurrence.
4502        *
4503        *  Starting from @a __pos, searches forward for a character not
4504        *  contained in the first @a __n characters of @a __s within
4505        *  this string.  If found, returns the index where it was
4506        *  found.  If not found, returns npos.
4507       */
4508       size_type
4509       find_first_not_of(const _CharT* __s, size_type __pos,
4510                         size_type __n) const;
4511
4512       /**
4513        *  @brief  Find position of a character not in C string.
4514        *  @param __s  C string containing characters to avoid.
4515        *  @param __pos  Index of character to search from (default 0).
4516        *  @return  Index of first occurrence.
4517        *
4518        *  Starting from @a __pos, searches forward for a character not
4519        *  contained in @a __s within this string.  If found, returns
4520        *  the index where it was found.  If not found, returns npos.
4521       */
4522       size_type
4523       find_first_not_of(const _CharT* __s, size_type __pos = 0) const
4524       {
4525         __glibcxx_requires_string(__s);
4526         return this->find_first_not_of(__s, __pos, traits_type::length(__s));
4527       }
4528
4529       /**
4530        *  @brief  Find position of a different character.
4531        *  @param __c  Character to avoid.
4532        *  @param __pos  Index of character to search from (default 0).
4533        *  @return  Index of first occurrence.
4534        *
4535        *  Starting from @a __pos, searches forward for a character
4536        *  other than @a __c within this string.  If found, returns the
4537        *  index where it was found.  If not found, returns npos.
4538       */
4539       size_type
4540       find_first_not_of(_CharT __c, size_type __pos = 0) const
4541         _GLIBCXX_NOEXCEPT;
4542
4543       /**
4544        *  @brief  Find last position of a character not in string.
4545        *  @param __str  String containing characters to avoid.
4546        *  @param __pos  Index of character to search back from (default end).
4547        *  @return  Index of last occurrence.
4548        *
4549        *  Starting from @a __pos, searches backward for a character
4550        *  not contained in @a __str within this string.  If found,
4551        *  returns the index where it was found.  If not found, returns
4552        *  npos.
4553       */
4554       size_type
4555       find_last_not_of(const basic_string& __str, size_type __pos = npos) const
4556         _GLIBCXX_NOEXCEPT
4557       { return this->find_last_not_of(__str.data(), __pos, __str.size()); }
4558
4559       /**
4560        *  @brief  Find last position of a character not in C substring.
4561        *  @param __s  C string containing characters to avoid.
4562        *  @param __pos  Index of character to search back from.
4563        *  @param __n  Number of characters from s to consider.
4564        *  @return  Index of last occurrence.
4565        *
4566        *  Starting from @a __pos, searches backward for a character not
4567        *  contained in the first @a __n characters of @a __s within this string.
4568        *  If found, returns the index where it was found.  If not found,
4569        *  returns npos.
4570       */
4571       size_type
4572       find_last_not_of(const _CharT* __s, size_type __pos,
4573                        size_type __n) const;
4574       /**
4575        *  @brief  Find last position of a character not in C string.
4576        *  @param __s  C string containing characters to avoid.
4577        *  @param __pos  Index of character to search back from (default end).
4578        *  @return  Index of last occurrence.
4579        *
4580        *  Starting from @a __pos, searches backward for a character
4581        *  not contained in @a __s within this string.  If found,
4582        *  returns the index where it was found.  If not found, returns
4583        *  npos.
4584       */
4585       size_type
4586       find_last_not_of(const _CharT* __s, size_type __pos = npos) const
4587       {
4588         __glibcxx_requires_string(__s);
4589         return this->find_last_not_of(__s, __pos, traits_type::length(__s));
4590       }
4591
4592       /**
4593        *  @brief  Find last position of a different character.
4594        *  @param __c  Character to avoid.
4595        *  @param __pos  Index of character to search back from (default end).
4596        *  @return  Index of last occurrence.
4597        *
4598        *  Starting from @a __pos, searches backward for a character other than
4599        *  @a __c within this string.  If found, returns the index where it was
4600        *  found.  If not found, returns npos.
4601       */
4602       size_type
4603       find_last_not_of(_CharT __c, size_type __pos = npos) const
4604         _GLIBCXX_NOEXCEPT;
4605
4606       /**
4607        *  @brief  Get a substring.
4608        *  @param __pos  Index of first character (default 0).
4609        *  @param __n  Number of characters in substring (default remainder).
4610        *  @return  The new string.
4611        *  @throw  std::out_of_range  If __pos > size().
4612        *
4613        *  Construct and return a new string using the @a __n
4614        *  characters starting at @a __pos.  If the string is too
4615        *  short, use the remainder of the characters.  If @a __pos is
4616        *  beyond the end of the string, out_of_range is thrown.
4617       */
4618       basic_string
4619       substr(size_type __pos = 0, size_type __n = npos) const
4620       { return basic_string(*this,
4621                             _M_check(__pos, "basic_string::substr"), __n); }
4622
4623       /**
4624        *  @brief  Compare to a string.
4625        *  @param __str  String to compare against.
4626        *  @return  Integer < 0, 0, or > 0.
4627        *
4628        *  Returns an integer < 0 if this string is ordered before @a
4629        *  __str, 0 if their values are equivalent, or > 0 if this
4630        *  string is ordered after @a __str.  Determines the effective
4631        *  length rlen of the strings to compare as the smallest of
4632        *  size() and str.size().  The function then compares the two
4633        *  strings by calling traits::compare(data(), str.data(),rlen).
4634        *  If the result of the comparison is nonzero returns it,
4635        *  otherwise the shorter one is ordered first.
4636       */
4637       int
4638       compare(const basic_string& __str) const
4639       {
4640         const size_type __size = this->size();
4641         const size_type __osize = __str.size();
4642         const size_type __len = std::min(__size, __osize);
4643
4644         int __r = traits_type::compare(_M_data(), __str.data(), __len);
4645         if (!__r)
4646           __r = _S_compare(__size, __osize);
4647         return __r;
4648       }
4649
4650       /**
4651        *  @brief  Compare substring to a string.
4652        *  @param __pos  Index of first character of substring.
4653        *  @param __n  Number of characters in substring.
4654        *  @param __str  String to compare against.
4655        *  @return  Integer < 0, 0, or > 0.
4656        *
4657        *  Form the substring of this string from the @a __n characters
4658        *  starting at @a __pos.  Returns an integer < 0 if the
4659        *  substring is ordered before @a __str, 0 if their values are
4660        *  equivalent, or > 0 if the substring is ordered after @a
4661        *  __str.  Determines the effective length rlen of the strings
4662        *  to compare as the smallest of the length of the substring
4663        *  and @a __str.size().  The function then compares the two
4664        *  strings by calling
4665        *  traits::compare(substring.data(),str.data(),rlen).  If the
4666        *  result of the comparison is nonzero returns it, otherwise
4667        *  the shorter one is ordered first.
4668       */
4669       int
4670       compare(size_type __pos, size_type __n, const basic_string& __str) const;
4671
4672       /**
4673        *  @brief  Compare substring to a substring.
4674        *  @param __pos1  Index of first character of substring.
4675        *  @param __n1  Number of characters in substring.
4676        *  @param __str  String to compare against.
4677        *  @param __pos2  Index of first character of substring of str.
4678        *  @param __n2  Number of characters in substring of str.
4679        *  @return  Integer < 0, 0, or > 0.
4680        *
4681        *  Form the substring of this string from the @a __n1
4682        *  characters starting at @a __pos1.  Form the substring of @a
4683        *  __str from the @a __n2 characters starting at @a __pos2.
4684        *  Returns an integer < 0 if this substring is ordered before
4685        *  the substring of @a __str, 0 if their values are equivalent,
4686        *  or > 0 if this substring is ordered after the substring of
4687        *  @a __str.  Determines the effective length rlen of the
4688        *  strings to compare as the smallest of the lengths of the
4689        *  substrings.  The function then compares the two strings by
4690        *  calling
4691        *  traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
4692        *  If the result of the comparison is nonzero returns it,
4693        *  otherwise the shorter one is ordered first.
4694       */
4695       int
4696       compare(size_type __pos1, size_type __n1, const basic_string& __str,
4697               size_type __pos2, size_type __n2) const;
4698
4699       /**
4700        *  @brief  Compare to a C string.
4701        *  @param __s  C string to compare against.
4702        *  @return  Integer < 0, 0, or > 0.
4703        *
4704        *  Returns an integer < 0 if this string is ordered before @a __s, 0 if
4705        *  their values are equivalent, or > 0 if this string is ordered after
4706        *  @a __s.  Determines the effective length rlen of the strings to
4707        *  compare as the smallest of size() and the length of a string
4708        *  constructed from @a __s.  The function then compares the two strings
4709        *  by calling traits::compare(data(),s,rlen).  If the result of the
4710        *  comparison is nonzero returns it, otherwise the shorter one is
4711        *  ordered first.
4712       */
4713       int
4714       compare(const _CharT* __s) const;
4715
4716       // _GLIBCXX_RESOLVE_LIB_DEFECTS
4717       // 5 String::compare specification questionable
4718       /**
4719        *  @brief  Compare substring to a C string.
4720        *  @param __pos  Index of first character of substring.
4721        *  @param __n1  Number of characters in substring.
4722        *  @param __s  C string to compare against.
4723        *  @return  Integer < 0, 0, or > 0.
4724        *
4725        *  Form the substring of this string from the @a __n1
4726        *  characters starting at @a pos.  Returns an integer < 0 if
4727        *  the substring is ordered before @a __s, 0 if their values
4728        *  are equivalent, or > 0 if the substring is ordered after @a
4729        *  __s.  Determines the effective length rlen of the strings to
4730        *  compare as the smallest of the length of the substring and
4731        *  the length of a string constructed from @a __s.  The
4732        *  function then compares the two string by calling
4733        *  traits::compare(substring.data(),__s,rlen).  If the result of
4734        *  the comparison is nonzero returns it, otherwise the shorter
4735        *  one is ordered first.
4736       */
4737       int
4738       compare(size_type __pos, size_type __n1, const _CharT* __s) const;
4739
4740       /**
4741        *  @brief  Compare substring against a character %array.
4742        *  @param __pos  Index of first character of substring.
4743        *  @param __n1  Number of characters in substring.
4744        *  @param __s  character %array to compare against.
4745        *  @param __n2  Number of characters of s.
4746        *  @return  Integer < 0, 0, or > 0.
4747        *
4748        *  Form the substring of this string from the @a __n1
4749        *  characters starting at @a __pos.  Form a string from the
4750        *  first @a __n2 characters of @a __s.  Returns an integer < 0
4751        *  if this substring is ordered before the string from @a __s,
4752        *  0 if their values are equivalent, or > 0 if this substring
4753        *  is ordered after the string from @a __s.  Determines the
4754        *  effective length rlen of the strings to compare as the
4755        *  smallest of the length of the substring and @a __n2.  The
4756        *  function then compares the two strings by calling
4757        *  traits::compare(substring.data(),s,rlen).  If the result of
4758        *  the comparison is nonzero returns it, otherwise the shorter
4759        *  one is ordered first.
4760        *
4761        *  NB: s must have at least n2 characters, &apos;\\0&apos; has
4762        *  no special meaning.
4763       */
4764       int
4765       compare(size_type __pos, size_type __n1, const _CharT* __s,
4766               size_type __n2) const;
4767   };
4768 #endif  // !_GLIBCXX_USE_CXX11_ABI
4769
4770   // operator+
4771   /**
4772    *  @brief  Concatenate two strings.
4773    *  @param __lhs  First string.
4774    *  @param __rhs  Last string.
4775    *  @return  New string with value of @a __lhs followed by @a __rhs.
4776    */
4777   template<typename _CharT, typename _Traits, typename _Alloc>
4778     basic_string<_CharT, _Traits, _Alloc>
4779     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4780               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
4781     {
4782       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
4783       __str.append(__rhs);
4784       return __str;
4785     }
4786
4787   /**
4788    *  @brief  Concatenate C string and string.
4789    *  @param __lhs  First string.
4790    *  @param __rhs  Last string.
4791    *  @return  New string with value of @a __lhs followed by @a __rhs.
4792    */
4793   template<typename _CharT, typename _Traits, typename _Alloc>
4794     basic_string<_CharT,_Traits,_Alloc>
4795     operator+(const _CharT* __lhs,
4796               const basic_string<_CharT,_Traits,_Alloc>& __rhs);
4797
4798   /**
4799    *  @brief  Concatenate character and string.
4800    *  @param __lhs  First string.
4801    *  @param __rhs  Last string.
4802    *  @return  New string with @a __lhs followed by @a __rhs.
4803    */
4804   template<typename _CharT, typename _Traits, typename _Alloc>
4805     basic_string<_CharT,_Traits,_Alloc>
4806     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
4807
4808   /**
4809    *  @brief  Concatenate string and C string.
4810    *  @param __lhs  First string.
4811    *  @param __rhs  Last string.
4812    *  @return  New string with @a __lhs followed by @a __rhs.
4813    */
4814   template<typename _CharT, typename _Traits, typename _Alloc>
4815     inline basic_string<_CharT, _Traits, _Alloc>
4816     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4817               const _CharT* __rhs)
4818     {
4819       basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
4820       __str.append(__rhs);
4821       return __str;
4822     }
4823
4824   /**
4825    *  @brief  Concatenate string and character.
4826    *  @param __lhs  First string.
4827    *  @param __rhs  Last string.
4828    *  @return  New string with @a __lhs followed by @a __rhs.
4829    */
4830   template<typename _CharT, typename _Traits, typename _Alloc>
4831     inline basic_string<_CharT, _Traits, _Alloc>
4832     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
4833     {
4834       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
4835       typedef typename __string_type::size_type         __size_type;
4836       __string_type __str(__lhs);
4837       __str.append(__size_type(1), __rhs);
4838       return __str;
4839     }
4840
4841 #if __cplusplus >= 201103L
4842   template<typename _CharT, typename _Traits, typename _Alloc>
4843     inline basic_string<_CharT, _Traits, _Alloc>
4844     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
4845               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
4846     { return std::move(__lhs.append(__rhs)); }
4847
4848   template<typename _CharT, typename _Traits, typename _Alloc>
4849     inline basic_string<_CharT, _Traits, _Alloc>
4850     operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4851               basic_string<_CharT, _Traits, _Alloc>&& __rhs)
4852     { return std::move(__rhs.insert(0, __lhs)); }
4853
4854   template<typename _CharT, typename _Traits, typename _Alloc>
4855     inline basic_string<_CharT, _Traits, _Alloc>
4856     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
4857               basic_string<_CharT, _Traits, _Alloc>&& __rhs)
4858     {
4859       const auto __size = __lhs.size() + __rhs.size();
4860       const bool __cond = (__size > __lhs.capacity()
4861                            && __size <= __rhs.capacity());
4862       return __cond ? std::move(__rhs.insert(0, __lhs))
4863                     : std::move(__lhs.append(__rhs));
4864     }
4865
4866   template<typename _CharT, typename _Traits, typename _Alloc>
4867     inline basic_string<_CharT, _Traits, _Alloc>
4868     operator+(const _CharT* __lhs,
4869               basic_string<_CharT, _Traits, _Alloc>&& __rhs)
4870     { return std::move(__rhs.insert(0, __lhs)); }
4871
4872   template<typename _CharT, typename _Traits, typename _Alloc>
4873     inline basic_string<_CharT, _Traits, _Alloc>
4874     operator+(_CharT __lhs,
4875               basic_string<_CharT, _Traits, _Alloc>&& __rhs)
4876     { return std::move(__rhs.insert(0, 1, __lhs)); }
4877
4878   template<typename _CharT, typename _Traits, typename _Alloc>
4879     inline basic_string<_CharT, _Traits, _Alloc>
4880     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
4881               const _CharT* __rhs)
4882     { return std::move(__lhs.append(__rhs)); }
4883
4884   template<typename _CharT, typename _Traits, typename _Alloc>
4885     inline basic_string<_CharT, _Traits, _Alloc>
4886     operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
4887               _CharT __rhs)
4888     { return std::move(__lhs.append(1, __rhs)); }
4889 #endif
4890
4891   // operator ==
4892   /**
4893    *  @brief  Test equivalence of two strings.
4894    *  @param __lhs  First string.
4895    *  @param __rhs  Second string.
4896    *  @return  True if @a __lhs.compare(@a __rhs) == 0.  False otherwise.
4897    */
4898   template<typename _CharT, typename _Traits, typename _Alloc>
4899     inline bool
4900     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4901                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
4902     { return __lhs.compare(__rhs) == 0; }
4903
4904   template<typename _CharT>
4905     inline
4906     typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, bool>::__type
4907     operator==(const basic_string<_CharT>& __lhs,
4908                const basic_string<_CharT>& __rhs)
4909     { return (__lhs.size() == __rhs.size()
4910               && !std::char_traits<_CharT>::compare(__lhs.data(), __rhs.data(),
4911                                                     __lhs.size())); }
4912
4913   /**
4914    *  @brief  Test equivalence of C string and string.
4915    *  @param __lhs  C string.
4916    *  @param __rhs  String.
4917    *  @return  True if @a __rhs.compare(@a __lhs) == 0.  False otherwise.
4918    */
4919   template<typename _CharT, typename _Traits, typename _Alloc>
4920     inline bool
4921     operator==(const _CharT* __lhs,
4922                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
4923     { return __rhs.compare(__lhs) == 0; }
4924
4925   /**
4926    *  @brief  Test equivalence of string and C string.
4927    *  @param __lhs  String.
4928    *  @param __rhs  C string.
4929    *  @return  True if @a __lhs.compare(@a __rhs) == 0.  False otherwise.
4930    */
4931   template<typename _CharT, typename _Traits, typename _Alloc>
4932     inline bool
4933     operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4934                const _CharT* __rhs)
4935     { return __lhs.compare(__rhs) == 0; }
4936
4937   // operator !=
4938   /**
4939    *  @brief  Test difference of two strings.
4940    *  @param __lhs  First string.
4941    *  @param __rhs  Second string.
4942    *  @return  True if @a __lhs.compare(@a __rhs) != 0.  False otherwise.
4943    */
4944   template<typename _CharT, typename _Traits, typename _Alloc>
4945     inline bool
4946     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4947                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
4948     { return !(__lhs == __rhs); }
4949
4950   /**
4951    *  @brief  Test difference of C string and string.
4952    *  @param __lhs  C string.
4953    *  @param __rhs  String.
4954    *  @return  True if @a __rhs.compare(@a __lhs) != 0.  False otherwise.
4955    */
4956   template<typename _CharT, typename _Traits, typename _Alloc>
4957     inline bool
4958     operator!=(const _CharT* __lhs,
4959                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
4960     { return !(__lhs == __rhs); }
4961
4962   /**
4963    *  @brief  Test difference of string and C string.
4964    *  @param __lhs  String.
4965    *  @param __rhs  C string.
4966    *  @return  True if @a __lhs.compare(@a __rhs) != 0.  False otherwise.
4967    */
4968   template<typename _CharT, typename _Traits, typename _Alloc>
4969     inline bool
4970     operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4971                const _CharT* __rhs)
4972     { return !(__lhs == __rhs); }
4973
4974   // operator <
4975   /**
4976    *  @brief  Test if string precedes string.
4977    *  @param __lhs  First string.
4978    *  @param __rhs  Second string.
4979    *  @return  True if @a __lhs precedes @a __rhs.  False otherwise.
4980    */
4981   template<typename _CharT, typename _Traits, typename _Alloc>
4982     inline bool
4983     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4984               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
4985     { return __lhs.compare(__rhs) < 0; }
4986
4987   /**
4988    *  @brief  Test if string precedes C string.
4989    *  @param __lhs  String.
4990    *  @param __rhs  C string.
4991    *  @return  True if @a __lhs precedes @a __rhs.  False otherwise.
4992    */
4993   template<typename _CharT, typename _Traits, typename _Alloc>
4994     inline bool
4995     operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4996               const _CharT* __rhs)
4997     { return __lhs.compare(__rhs) < 0; }
4998
4999   /**
5000    *  @brief  Test if C string precedes string.
5001    *  @param __lhs  C string.
5002    *  @param __rhs  String.
5003    *  @return  True if @a __lhs precedes @a __rhs.  False otherwise.
5004    */
5005   template<typename _CharT, typename _Traits, typename _Alloc>
5006     inline bool
5007     operator<(const _CharT* __lhs,
5008               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5009     { return __rhs.compare(__lhs) > 0; }
5010
5011   // operator >
5012   /**
5013    *  @brief  Test if string follows string.
5014    *  @param __lhs  First string.
5015    *  @param __rhs  Second string.
5016    *  @return  True if @a __lhs follows @a __rhs.  False otherwise.
5017    */
5018   template<typename _CharT, typename _Traits, typename _Alloc>
5019     inline bool
5020     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5021               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5022     { return __lhs.compare(__rhs) > 0; }
5023
5024   /**
5025    *  @brief  Test if string follows C string.
5026    *  @param __lhs  String.
5027    *  @param __rhs  C string.
5028    *  @return  True if @a __lhs follows @a __rhs.  False otherwise.
5029    */
5030   template<typename _CharT, typename _Traits, typename _Alloc>
5031     inline bool
5032     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5033               const _CharT* __rhs)
5034     { return __lhs.compare(__rhs) > 0; }
5035
5036   /**
5037    *  @brief  Test if C string follows string.
5038    *  @param __lhs  C string.
5039    *  @param __rhs  String.
5040    *  @return  True if @a __lhs follows @a __rhs.  False otherwise.
5041    */
5042   template<typename _CharT, typename _Traits, typename _Alloc>
5043     inline bool
5044     operator>(const _CharT* __lhs,
5045               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5046     { return __rhs.compare(__lhs) < 0; }
5047
5048   // operator <=
5049   /**
5050    *  @brief  Test if string doesn't follow string.
5051    *  @param __lhs  First string.
5052    *  @param __rhs  Second string.
5053    *  @return  True if @a __lhs doesn't follow @a __rhs.  False otherwise.
5054    */
5055   template<typename _CharT, typename _Traits, typename _Alloc>
5056     inline bool
5057     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5058                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5059     { return __lhs.compare(__rhs) <= 0; }
5060
5061   /**
5062    *  @brief  Test if string doesn't follow C string.
5063    *  @param __lhs  String.
5064    *  @param __rhs  C string.
5065    *  @return  True if @a __lhs doesn't follow @a __rhs.  False otherwise.
5066    */
5067   template<typename _CharT, typename _Traits, typename _Alloc>
5068     inline bool
5069     operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5070                const _CharT* __rhs)
5071     { return __lhs.compare(__rhs) <= 0; }
5072
5073   /**
5074    *  @brief  Test if C string doesn't follow string.
5075    *  @param __lhs  C string.
5076    *  @param __rhs  String.
5077    *  @return  True if @a __lhs doesn't follow @a __rhs.  False otherwise.
5078    */
5079   template<typename _CharT, typename _Traits, typename _Alloc>
5080     inline bool
5081     operator<=(const _CharT* __lhs,
5082                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5083     { return __rhs.compare(__lhs) >= 0; }
5084
5085   // operator >=
5086   /**
5087    *  @brief  Test if string doesn't precede string.
5088    *  @param __lhs  First string.
5089    *  @param __rhs  Second string.
5090    *  @return  True if @a __lhs doesn't precede @a __rhs.  False otherwise.
5091    */
5092   template<typename _CharT, typename _Traits, typename _Alloc>
5093     inline bool
5094     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5095                const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5096     { return __lhs.compare(__rhs) >= 0; }
5097
5098   /**
5099    *  @brief  Test if string doesn't precede C string.
5100    *  @param __lhs  String.
5101    *  @param __rhs  C string.
5102    *  @return  True if @a __lhs doesn't precede @a __rhs.  False otherwise.
5103    */
5104   template<typename _CharT, typename _Traits, typename _Alloc>
5105     inline bool
5106     operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5107                const _CharT* __rhs)
5108     { return __lhs.compare(__rhs) >= 0; }
5109
5110   /**
5111    *  @brief  Test if C string doesn't precede string.
5112    *  @param __lhs  C string.
5113    *  @param __rhs  String.
5114    *  @return  True if @a __lhs doesn't precede @a __rhs.  False otherwise.
5115    */
5116   template<typename _CharT, typename _Traits, typename _Alloc>
5117     inline bool
5118     operator>=(const _CharT* __lhs,
5119              const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5120     { return __rhs.compare(__lhs) <= 0; }
5121
5122   /**
5123    *  @brief  Swap contents of two strings.
5124    *  @param __lhs  First string.
5125    *  @param __rhs  Second string.
5126    *
5127    *  Exchanges the contents of @a __lhs and @a __rhs in constant time.
5128    */
5129   template<typename _CharT, typename _Traits, typename _Alloc>
5130     inline void
5131     swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
5132          basic_string<_CharT, _Traits, _Alloc>& __rhs)
5133     { __lhs.swap(__rhs); }
5134
5135
5136   /**
5137    *  @brief  Read stream into a string.
5138    *  @param __is  Input stream.
5139    *  @param __str  Buffer to store into.
5140    *  @return  Reference to the input stream.
5141    *
5142    *  Stores characters from @a __is into @a __str until whitespace is
5143    *  found, the end of the stream is encountered, or str.max_size()
5144    *  is reached.  If is.width() is non-zero, that is the limit on the
5145    *  number of characters stored into @a __str.  Any previous
5146    *  contents of @a __str are erased.
5147    */
5148   template<typename _CharT, typename _Traits, typename _Alloc>
5149     basic_istream<_CharT, _Traits>&
5150     operator>>(basic_istream<_CharT, _Traits>& __is,
5151                basic_string<_CharT, _Traits, _Alloc>& __str);
5152
5153   template<>
5154     basic_istream<char>&
5155     operator>>(basic_istream<char>& __is, basic_string<char>& __str);
5156
5157   /**
5158    *  @brief  Write string to a stream.
5159    *  @param __os  Output stream.
5160    *  @param __str  String to write out.
5161    *  @return  Reference to the output stream.
5162    *
5163    *  Output characters of @a __str into os following the same rules as for
5164    *  writing a C string.
5165    */
5166   template<typename _CharT, typename _Traits, typename _Alloc>
5167     inline basic_ostream<_CharT, _Traits>&
5168     operator<<(basic_ostream<_CharT, _Traits>& __os,
5169                const basic_string<_CharT, _Traits, _Alloc>& __str)
5170     {
5171       // _GLIBCXX_RESOLVE_LIB_DEFECTS
5172       // 586. string inserter not a formatted function
5173       return __ostream_insert(__os, __str.data(), __str.size());
5174     }
5175
5176   /**
5177    *  @brief  Read a line from stream into a string.
5178    *  @param __is  Input stream.
5179    *  @param __str  Buffer to store into.
5180    *  @param __delim  Character marking end of line.
5181    *  @return  Reference to the input stream.
5182    *
5183    *  Stores characters from @a __is into @a __str until @a __delim is
5184    *  found, the end of the stream is encountered, or str.max_size()
5185    *  is reached.  Any previous contents of @a __str are erased.  If
5186    *  @a __delim is encountered, it is extracted but not stored into
5187    *  @a __str.
5188    */
5189   template<typename _CharT, typename _Traits, typename _Alloc>
5190     basic_istream<_CharT, _Traits>&
5191     getline(basic_istream<_CharT, _Traits>& __is,
5192             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
5193
5194   /**
5195    *  @brief  Read a line from stream into a string.
5196    *  @param __is  Input stream.
5197    *  @param __str  Buffer to store into.
5198    *  @return  Reference to the input stream.
5199    *
5200    *  Stores characters from is into @a __str until &apos;\n&apos; is
5201    *  found, the end of the stream is encountered, or str.max_size()
5202    *  is reached.  Any previous contents of @a __str are erased.  If
5203    *  end of line is encountered, it is extracted but not stored into
5204    *  @a __str.
5205    */
5206   template<typename _CharT, typename _Traits, typename _Alloc>
5207     inline basic_istream<_CharT, _Traits>&
5208     getline(basic_istream<_CharT, _Traits>& __is,
5209             basic_string<_CharT, _Traits, _Alloc>& __str)
5210     { return std::getline(__is, __str, __is.widen('\n')); }
5211
5212 #if __cplusplus >= 201103L
5213   /// Read a line from an rvalue stream into a string.
5214   template<typename _CharT, typename _Traits, typename _Alloc>
5215     inline basic_istream<_CharT, _Traits>&
5216     getline(basic_istream<_CharT, _Traits>&& __is,
5217             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
5218     { return std::getline(__is, __str, __delim); }
5219
5220   /// Read a line from an rvalue stream into a string.
5221   template<typename _CharT, typename _Traits, typename _Alloc>
5222     inline basic_istream<_CharT, _Traits>&
5223     getline(basic_istream<_CharT, _Traits>&& __is,
5224             basic_string<_CharT, _Traits, _Alloc>& __str)
5225     { return std::getline(__is, __str); }
5226 #endif
5227
5228   template<>
5229     basic_istream<char>&
5230     getline(basic_istream<char>& __in, basic_string<char>& __str,
5231             char __delim);
5232
5233 #ifdef _GLIBCXX_USE_WCHAR_T
5234   template<>
5235     basic_istream<wchar_t>&
5236     getline(basic_istream<wchar_t>& __in, basic_string<wchar_t>& __str,
5237             wchar_t __delim);
5238 #endif
5239
5240 _GLIBCXX_END_NAMESPACE_VERSION
5241 } // namespace
5242
5243 #if __cplusplus >= 201103L && defined(_GLIBCXX_USE_C99)
5244
5245 #include <ext/string_conversions.h>
5246
5247 namespace std _GLIBCXX_VISIBILITY(default)
5248 {
5249 _GLIBCXX_BEGIN_NAMESPACE_VERSION
5250 _GLIBCXX_BEGIN_NAMESPACE_CXX11
5251
5252   // 21.4 Numeric Conversions [string.conversions].
5253   inline int
5254   stoi(const string& __str, size_t* __idx = 0, int __base = 10)
5255   { return __gnu_cxx::__stoa<long, int>(&std::strtol, "stoi", __str.c_str(),
5256                                         __idx, __base); }
5257
5258   inline long
5259   stol(const string& __str, size_t* __idx = 0, int __base = 10)
5260   { return __gnu_cxx::__stoa(&std::strtol, "stol", __str.c_str(),
5261                              __idx, __base); }
5262
5263   inline unsigned long
5264   stoul(const string& __str, size_t* __idx = 0, int __base = 10)
5265   { return __gnu_cxx::__stoa(&std::strtoul, "stoul", __str.c_str(),
5266                              __idx, __base); }
5267
5268   inline long long
5269   stoll(const string& __str, size_t* __idx = 0, int __base = 10)
5270   { return __gnu_cxx::__stoa(&std::strtoll, "stoll", __str.c_str(),
5271                              __idx, __base); }
5272
5273   inline unsigned long long
5274   stoull(const string& __str, size_t* __idx = 0, int __base = 10)
5275   { return __gnu_cxx::__stoa(&std::strtoull, "stoull", __str.c_str(),
5276                              __idx, __base); }
5277
5278   // NB: strtof vs strtod.
5279   inline float
5280   stof(const string& __str, size_t* __idx = 0)
5281   { return __gnu_cxx::__stoa(&std::strtof, "stof", __str.c_str(), __idx); }
5282
5283   inline double
5284   stod(const string& __str, size_t* __idx = 0)
5285   { return __gnu_cxx::__stoa(&std::strtod, "stod", __str.c_str(), __idx); }
5286
5287   inline long double
5288   stold(const string& __str, size_t* __idx = 0)
5289   { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }
5290
5291   // NB: (v)snprintf vs sprintf.
5292
5293   // DR 1261.
5294   inline string
5295   to_string(int __val)
5296   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
5297                                            "%d", __val); }
5298
5299   inline string
5300   to_string(unsigned __val)
5301   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5302                                            4 * sizeof(unsigned),
5303                                            "%u", __val); }
5304
5305   inline string
5306   to_string(long __val)
5307   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
5308                                            "%ld", __val); }
5309
5310   inline string
5311   to_string(unsigned long __val)
5312   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5313                                            4 * sizeof(unsigned long),
5314                                            "%lu", __val); }
5315
5316   inline string
5317   to_string(long long __val)
5318   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5319                                            4 * sizeof(long long),
5320                                            "%lld", __val); }
5321
5322   inline string
5323   to_string(unsigned long long __val)
5324   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5325                                            4 * sizeof(unsigned long long),
5326                                            "%llu", __val); }
5327
5328   inline string
5329   to_string(float __val)
5330   {
5331     const int __n =
5332       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
5333     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5334                                            "%f", __val);
5335   }
5336
5337   inline string
5338   to_string(double __val)
5339   {
5340     const int __n =
5341       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
5342     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5343                                            "%f", __val);
5344   }
5345
5346   inline string
5347   to_string(long double __val)
5348   {
5349     const int __n =
5350       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
5351     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5352                                            "%Lf", __val);
5353   }
5354
5355 #ifdef _GLIBCXX_USE_WCHAR_T
5356   inline int
5357   stoi(const wstring& __str, size_t* __idx = 0, int __base = 10)
5358   { return __gnu_cxx::__stoa<long, int>(&std::wcstol, "stoi", __str.c_str(),
5359                                         __idx, __base); }
5360
5361   inline long
5362   stol(const wstring& __str, size_t* __idx = 0, int __base = 10)
5363   { return __gnu_cxx::__stoa(&std::wcstol, "stol", __str.c_str(),
5364                              __idx, __base); }
5365
5366   inline unsigned long
5367   stoul(const wstring& __str, size_t* __idx = 0, int __base = 10)
5368   { return __gnu_cxx::__stoa(&std::wcstoul, "stoul", __str.c_str(),
5369                              __idx, __base); }
5370
5371   inline long long
5372   stoll(const wstring& __str, size_t* __idx = 0, int __base = 10)
5373   { return __gnu_cxx::__stoa(&std::wcstoll, "stoll", __str.c_str(),
5374                              __idx, __base); }
5375
5376   inline unsigned long long
5377   stoull(const wstring& __str, size_t* __idx = 0, int __base = 10)
5378   { return __gnu_cxx::__stoa(&std::wcstoull, "stoull", __str.c_str(),
5379                              __idx, __base); }
5380
5381   // NB: wcstof vs wcstod.
5382   inline float
5383   stof(const wstring& __str, size_t* __idx = 0)
5384   { return __gnu_cxx::__stoa(&std::wcstof, "stof", __str.c_str(), __idx); }
5385
5386   inline double
5387   stod(const wstring& __str, size_t* __idx = 0)
5388   { return __gnu_cxx::__stoa(&std::wcstod, "stod", __str.c_str(), __idx); }
5389
5390   inline long double
5391   stold(const wstring& __str, size_t* __idx = 0)
5392   { return __gnu_cxx::__stoa(&std::wcstold, "stold", __str.c_str(), __idx); }
5393
5394 #ifndef _GLIBCXX_HAVE_BROKEN_VSWPRINTF
5395   // DR 1261.
5396   inline wstring
5397   to_wstring(int __val)
5398   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(int),
5399                                             L"%d", __val); }
5400
5401   inline wstring
5402   to_wstring(unsigned __val)
5403   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5404                                             4 * sizeof(unsigned),
5405                                             L"%u", __val); }
5406
5407   inline wstring
5408   to_wstring(long __val)
5409   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, 4 * sizeof(long),
5410                                             L"%ld", __val); }
5411
5412   inline wstring
5413   to_wstring(unsigned long __val)
5414   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5415                                             4 * sizeof(unsigned long),
5416                                             L"%lu", __val); }
5417
5418   inline wstring
5419   to_wstring(long long __val)
5420   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5421                                             4 * sizeof(long long),
5422                                             L"%lld", __val); }
5423
5424   inline wstring
5425   to_wstring(unsigned long long __val)
5426   { return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5427                                             4 * sizeof(unsigned long long),
5428                                             L"%llu", __val); }
5429
5430   inline wstring
5431   to_wstring(float __val)
5432   {
5433     const int __n =
5434       __gnu_cxx::__numeric_traits<float>::__max_exponent10 + 20;
5435     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5436                                             L"%f", __val);
5437   }
5438
5439   inline wstring
5440   to_wstring(double __val)
5441   {
5442     const int __n =
5443       __gnu_cxx::__numeric_traits<double>::__max_exponent10 + 20;
5444     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5445                                             L"%f", __val);
5446   }
5447
5448   inline wstring
5449   to_wstring(long double __val)
5450   {
5451     const int __n =
5452       __gnu_cxx::__numeric_traits<long double>::__max_exponent10 + 20;
5453     return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5454                                             L"%Lf", __val);
5455   }
5456 #endif // _GLIBCXX_HAVE_BROKEN_VSWPRINTF
5457 #endif
5458
5459 _GLIBCXX_END_NAMESPACE_CXX11
5460 _GLIBCXX_END_NAMESPACE_VERSION
5461 } // namespace
5462
5463 #endif /* C++11 && _GLIBCXX_USE_C99 ... */
5464
5465 #if __cplusplus >= 201103L
5466
5467 #include <bits/functional_hash.h>
5468
5469 namespace std _GLIBCXX_VISIBILITY(default)
5470 {
5471 _GLIBCXX_BEGIN_NAMESPACE_VERSION
5472
5473   // DR 1182.
5474
5475 #ifndef _GLIBCXX_COMPATIBILITY_CXX0X
5476   /// std::hash specialization for string.
5477   template<>
5478     struct hash<string>
5479     : public __hash_base<size_t, string>
5480     {
5481       size_t
5482       operator()(const string& __s) const noexcept
5483       { return std::_Hash_impl::hash(__s.data(), __s.length()); }
5484     };
5485
5486   template<>
5487     struct __is_fast_hash<hash<string>> : std::false_type
5488     { };
5489
5490 #ifdef _GLIBCXX_USE_WCHAR_T
5491   /// std::hash specialization for wstring.
5492   template<>
5493     struct hash<wstring>
5494     : public __hash_base<size_t, wstring>
5495     {
5496       size_t
5497       operator()(const wstring& __s) const noexcept
5498       { return std::_Hash_impl::hash(__s.data(),
5499                                      __s.length() * sizeof(wchar_t)); }
5500     };
5501
5502   template<>
5503     struct __is_fast_hash<hash<wstring>> : std::false_type
5504     { };
5505 #endif
5506 #endif /* _GLIBCXX_COMPATIBILITY_CXX0X */
5507
5508 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
5509   /// std::hash specialization for u16string.
5510   template<>
5511     struct hash<u16string>
5512     : public __hash_base<size_t, u16string>
5513     {
5514       size_t
5515       operator()(const u16string& __s) const noexcept
5516       { return std::_Hash_impl::hash(__s.data(),
5517                                      __s.length() * sizeof(char16_t)); }
5518     };
5519
5520   template<>
5521     struct __is_fast_hash<hash<u16string>> : std::false_type
5522     { };
5523
5524   /// std::hash specialization for u32string.
5525   template<>
5526     struct hash<u32string>
5527     : public __hash_base<size_t, u32string>
5528     {
5529       size_t
5530       operator()(const u32string& __s) const noexcept
5531       { return std::_Hash_impl::hash(__s.data(),
5532                                      __s.length() * sizeof(char32_t)); }
5533     };
5534
5535   template<>
5536     struct __is_fast_hash<hash<u32string>> : std::false_type
5537     { };
5538 #endif
5539
5540 #if __cplusplus > 201103L
5541
5542 #define __cpp_lib_string_udls 201304
5543
5544   inline namespace literals
5545   {
5546   inline namespace string_literals
5547   {
5548
5549     _GLIBCXX_DEFAULT_ABI_TAG
5550     inline basic_string<char>
5551     operator""s(const char* __str, size_t __len)
5552     { return basic_string<char>{__str, __len}; }
5553
5554 #ifdef _GLIBCXX_USE_WCHAR_T
5555     _GLIBCXX_DEFAULT_ABI_TAG
5556     inline basic_string<wchar_t>
5557     operator""s(const wchar_t* __str, size_t __len)
5558     { return basic_string<wchar_t>{__str, __len}; }
5559 #endif
5560
5561 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
5562     _GLIBCXX_DEFAULT_ABI_TAG
5563     inline basic_string<char16_t>
5564     operator""s(const char16_t* __str, size_t __len)
5565     { return basic_string<char16_t>{__str, __len}; }
5566
5567     _GLIBCXX_DEFAULT_ABI_TAG
5568     inline basic_string<char32_t>
5569     operator""s(const char32_t* __str, size_t __len)
5570     { return basic_string<char32_t>{__str, __len}; }
5571 #endif
5572
5573   } // inline namespace string_literals
5574   } // inline namespace literals
5575
5576 #endif // __cplusplus > 201103L
5577
5578 _GLIBCXX_END_NAMESPACE_VERSION
5579 } // namespace std
5580
5581 #endif // C++11
5582
5583 #endif /* _BASIC_STRING_H */