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

   1 // Components for manipulating sequences of characters -*- C++ -*-
   2
   3 // Copyright (C) 1997-2018 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.tcc
  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 // Written by Jason Merrill based upon the specification by Takanori Adachi
  35 // in ANSI X3J16/94-0013R2.  Rewritten by Nathan Myers to ISO-14882.
  36 // Non-reference-counted implementation written by Paolo Carlini and
  37 // updated by Jonathan Wakely for ISO-14882-2011.
  38
  39 #ifndef _BASIC_STRING_TCC
  40 #define _BASIC_STRING_TCC 1
  41
  42 #pragma GCC system_header
  43
  44 #include <bits/cxxabi_forced.h>
  45
  46 namespace std _GLIBCXX_VISIBILITY(default)
  47 {
  48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  49
  50 #if _GLIBCXX_USE_CXX11_ABI
  51
  52   template<typename _CharT, typename _Traits, typename _Alloc>
  53     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
  54     basic_string<_CharT, _Traits, _Alloc>::npos;
  55
  56   template<typename _CharT, typename _Traits, typename _Alloc>
  57     void
  58     basic_string<_CharT, _Traits, _Alloc>::
  59     swap(basic_string& __s) _GLIBCXX_NOEXCEPT
  60     {
  61       if (this == &__s)
  62         return;
  63
  64       _Alloc_traits::_S_on_swap(_M_get_allocator(), __s._M_get_allocator());
  65
  66       if (_M_is_local())
  67         if (__s._M_is_local())
  68           {
  69             if (length() && __s.length())
  70               {
  71                 _CharT __tmp_data[_S_local_capacity + 1];
  72                 traits_type::copy(__tmp_data, __s._M_local_buf,
  73                                   _S_local_capacity + 1);
  74                 traits_type::copy(__s._M_local_buf, _M_local_buf,
  75                                   _S_local_capacity + 1);
  76                 traits_type::copy(_M_local_buf, __tmp_data,
  77                                   _S_local_capacity + 1);
  78               }
  79             else if (__s.length())
  80               {
  81                 traits_type::copy(_M_local_buf, __s._M_local_buf,
  82                                   _S_local_capacity + 1);
  83                 _M_length(__s.length());
  84                 __s._M_set_length(0);
  85                 return;
  86               }
  87             else if (length())
  88               {
  89                 traits_type::copy(__s._M_local_buf, _M_local_buf,
  90                                   _S_local_capacity + 1);
  91                 __s._M_length(length());
  92                 _M_set_length(0);
  93                 return;
  94               }
  95           }
  96         else
  97           {
  98             const size_type __tmp_capacity = __s._M_allocated_capacity;
  99             traits_type::copy(__s._M_local_buf, _M_local_buf,
 100                               _S_local_capacity + 1);
 101             _M_data(__s._M_data());
 102             __s._M_data(__s._M_local_buf);
 103             _M_capacity(__tmp_capacity);
 104           }
 105       else
 106         {
 107           const size_type __tmp_capacity = _M_allocated_capacity;
 108           if (__s._M_is_local())
 109             {
 110               traits_type::copy(_M_local_buf, __s._M_local_buf,
 111                                 _S_local_capacity + 1);
 112               __s._M_data(_M_data());
 113               _M_data(_M_local_buf);
 114             }
 115           else
 116             {
 117               pointer __tmp_ptr = _M_data();
 118               _M_data(__s._M_data());
 119               __s._M_data(__tmp_ptr);
 120               _M_capacity(__s._M_allocated_capacity);
 121             }
 122           __s._M_capacity(__tmp_capacity);
 123         }
 124
 125       const size_type __tmp_length = length();
 126       _M_length(__s.length());
 127       __s._M_length(__tmp_length);
 128     }
 129
 130   template<typename _CharT, typename _Traits, typename _Alloc>
 131     typename basic_string<_CharT, _Traits, _Alloc>::pointer
 132     basic_string<_CharT, _Traits, _Alloc>::
 133     _M_create(size_type& __capacity, size_type __old_capacity)
 134     {
 135       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 136       // 83.  String::npos vs. string::max_size()
 137       if (__capacity > max_size())
 138         std::__throw_length_error(__N("basic_string::_M_create"));
 139
 140       // The below implements an exponential growth policy, necessary to
 141       // meet amortized linear time requirements of the library: see
 142       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
 143       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
 144         {
 145           __capacity = 2 * __old_capacity;
 146           // Never allocate a string bigger than max_size.
 147           if (__capacity > max_size())
 148             __capacity = max_size();
 149         }
 150
 151       // NB: Need an array of char_type[__capacity], plus a terminating
 152       // null char_type() element.
 153       return _Alloc_traits::allocate(_M_get_allocator(), __capacity + 1);
 154     }
 155
 156   // NB: This is the special case for Input Iterators, used in
 157   // istreambuf_iterators, etc.
 158   // Input Iterators have a cost structure very different from
 159   // pointers, calling for a different coding style.
 160   template<typename _CharT, typename _Traits, typename _Alloc>
 161     template<typename _InIterator>
 162       void
 163       basic_string<_CharT, _Traits, _Alloc>::
 164       _M_construct(_InIterator __beg, _InIterator __end,
 165                    std::input_iterator_tag)
 166       {
 167         size_type __len = 0;
 168         size_type __capacity = size_type(_S_local_capacity);
 169
 170         while (__beg != __end && __len < __capacity)
 171           {
 172             _M_data()[__len++] = *__beg;
 173             ++__beg;
 174           }
 175
 176         __try
 177           {
 178             while (__beg != __end)
 179               {
 180                 if (__len == __capacity)
 181                   {
 182                     // Allocate more space.
 183                     __capacity = __len + 1;
 184                     pointer __another = _M_create(__capacity, __len);
 185                     this->_S_copy(__another, _M_data(), __len);
 186                     _M_dispose();
 187                     _M_data(__another);
 188                     _M_capacity(__capacity);
 189                   }
 190                 _M_data()[__len++] = *__beg;
 191                 ++__beg;
 192               }
 193           }
 194         __catch(...)
 195           {
 196             _M_dispose();
 197             __throw_exception_again;
 198           }
 199
 200         _M_set_length(__len);
 201       }
 202
 203   template<typename _CharT, typename _Traits, typename _Alloc>
 204     template<typename _InIterator>
 205       void
 206       basic_string<_CharT, _Traits, _Alloc>::
 207       _M_construct(_InIterator __beg, _InIterator __end,
 208                    std::forward_iterator_tag)
 209       {
 210         // NB: Not required, but considered best practice.
 211         if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
 212           std::__throw_logic_error(__N("basic_string::"
 213                                        "_M_construct null not valid"));
 214
 215         size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
 216
 217         if (__dnew > size_type(_S_local_capacity))
 218           {
 219             _M_data(_M_create(__dnew, size_type(0)));
 220             _M_capacity(__dnew);
 221           }
 222
 223         // Check for out_of_range and length_error exceptions.
 224         __try
 225           { this->_S_copy_chars(_M_data(), __beg, __end); }
 226         __catch(...)
 227           {
 228             _M_dispose();
 229             __throw_exception_again;
 230           }
 231
 232         _M_set_length(__dnew);
 233       }
 234
 235   template<typename _CharT, typename _Traits, typename _Alloc>
 236     void
 237     basic_string<_CharT, _Traits, _Alloc>::
 238     _M_construct(size_type __n, _CharT __c)
 239     {
 240       if (__n > size_type(_S_local_capacity))
 241         {
 242           _M_data(_M_create(__n, size_type(0)));
 243           _M_capacity(__n);
 244         }
 245
 246       if (__n)
 247         this->_S_assign(_M_data(), __n, __c);
 248
 249       _M_set_length(__n);
 250     }
 251
 252   template<typename _CharT, typename _Traits, typename _Alloc>
 253     void
 254     basic_string<_CharT, _Traits, _Alloc>::
 255     _M_assign(const basic_string& __str)
 256     {
 257       if (this != &__str)
 258         {
 259           const size_type __rsize = __str.length();
 260           const size_type __capacity = capacity();
 261
 262           if (__rsize > __capacity)
 263             {
 264               size_type __new_capacity = __rsize;
 265               pointer __tmp = _M_create(__new_capacity, __capacity);
 266               _M_dispose();
 267               _M_data(__tmp);
 268               _M_capacity(__new_capacity);
 269             }
 270
 271           if (__rsize)
 272             this->_S_copy(_M_data(), __str._M_data(), __rsize);
 273
 274           _M_set_length(__rsize);
 275         }
 276     }
 277
 278   template<typename _CharT, typename _Traits, typename _Alloc>
 279     void
 280     basic_string<_CharT, _Traits, _Alloc>::
 281     reserve(size_type __res)
 282     {
 283       // Make sure we don't shrink below the current size.
 284       if (__res < length())
 285         __res = length();
 286
 287       const size_type __capacity = capacity();
 288       if (__res != __capacity)
 289         {
 290           if (__res > __capacity
 291               || __res > size_type(_S_local_capacity))
 292             {
 293               pointer __tmp = _M_create(__res, __capacity);
 294               this->_S_copy(__tmp, _M_data(), length() + 1);
 295               _M_dispose();
 296               _M_data(__tmp);
 297               _M_capacity(__res);
 298             }
 299           else if (!_M_is_local())
 300             {
 301               this->_S_copy(_M_local_data(), _M_data(), length() + 1);
 302               _M_destroy(__capacity);
 303               _M_data(_M_local_data());
 304             }
 305         }
 306     }
 307
 308   template<typename _CharT, typename _Traits, typename _Alloc>
 309     void
 310     basic_string<_CharT, _Traits, _Alloc>::
 311     _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
 312               size_type __len2)
 313     {
 314       const size_type __how_much = length() - __pos - __len1;
 315
 316       size_type __new_capacity = length() + __len2 - __len1;
 317       pointer __r = _M_create(__new_capacity, capacity());
 318
 319       if (__pos)
 320         this->_S_copy(__r, _M_data(), __pos);
 321       if (__s && __len2)
 322         this->_S_copy(__r + __pos, __s, __len2);
 323       if (__how_much)
 324         this->_S_copy(__r + __pos + __len2,
 325                       _M_data() + __pos + __len1, __how_much);
 326
 327       _M_dispose();
 328       _M_data(__r);
 329       _M_capacity(__new_capacity);
 330     }
 331
 332   template<typename _CharT, typename _Traits, typename _Alloc>
 333     void
 334     basic_string<_CharT, _Traits, _Alloc>::
 335     _M_erase(size_type __pos, size_type __n)
 336     {
 337       const size_type __how_much = length() - __pos - __n;
 338
 339       if (__how_much && __n)
 340         this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much);
 341
 342       _M_set_length(length() - __n);
 343     }
 344
 345   template<typename _CharT, typename _Traits, typename _Alloc>
 346     void
 347     basic_string<_CharT, _Traits, _Alloc>::
 348     resize(size_type __n, _CharT __c)
 349     {
 350       const size_type __size = this->size();
 351       if (__size < __n)
 352         this->append(__n - __size, __c);
 353       else if (__n < __size)
 354         this->_M_set_length(__n);
 355     }
 356
 357   template<typename _CharT, typename _Traits, typename _Alloc>
 358     basic_string<_CharT, _Traits, _Alloc>&
 359     basic_string<_CharT, _Traits, _Alloc>::
 360     _M_append(const _CharT* __s, size_type __n)
 361     {
 362       const size_type __len = __n + this->size();
 363
 364       if (__len <= this->capacity())
 365         {
 366           if (__n)
 367             this->_S_copy(this->_M_data() + this->size(), __s, __n);
 368         }
 369       else
 370         this->_M_mutate(this->size(), size_type(0), __s, __n);
 371
 372       this->_M_set_length(__len);
 373       return *this;
 374     }
 375
 376   template<typename _CharT, typename _Traits, typename _Alloc>
 377     template<typename _InputIterator>
 378       basic_string<_CharT, _Traits, _Alloc>&
 379       basic_string<_CharT, _Traits, _Alloc>::
 380       _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
 381                           _InputIterator __k1, _InputIterator __k2,
 382                           std::__false_type)
 383       {
 384         const basic_string __s(__k1, __k2);
 385         const size_type __n1 = __i2 - __i1;
 386         return _M_replace(__i1 - begin(), __n1, __s._M_data(),
 387                           __s.size());
 388       }
 389
 390   template<typename _CharT, typename _Traits, typename _Alloc>
 391     basic_string<_CharT, _Traits, _Alloc>&
 392     basic_string<_CharT, _Traits, _Alloc>::
 393     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
 394                    _CharT __c)
 395     {
 396       _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
 397
 398       const size_type __old_size = this->size();
 399       const size_type __new_size = __old_size + __n2 - __n1;
 400
 401       if (__new_size <= this->capacity())
 402         {
 403           pointer __p = this->_M_data() + __pos1;
 404
 405           const size_type __how_much = __old_size - __pos1 - __n1;
 406           if (__how_much && __n1 != __n2)
 407             this->_S_move(__p + __n2, __p + __n1, __how_much);
 408         }
 409       else
 410         this->_M_mutate(__pos1, __n1, 0, __n2);
 411
 412       if (__n2)
 413         this->_S_assign(this->_M_data() + __pos1, __n2, __c);
 414
 415       this->_M_set_length(__new_size);
 416       return *this;
 417     }
 418
 419   template<typename _CharT, typename _Traits, typename _Alloc>
 420     basic_string<_CharT, _Traits, _Alloc>&
 421     basic_string<_CharT, _Traits, _Alloc>::
 422     _M_replace(size_type __pos, size_type __len1, const _CharT* __s,
 423                const size_type __len2)
 424     {
 425       _M_check_length(__len1, __len2, "basic_string::_M_replace");
 426
 427       const size_type __old_size = this->size();
 428       const size_type __new_size = __old_size + __len2 - __len1;
 429
 430       if (__new_size <= this->capacity())
 431         {
 432           pointer __p = this->_M_data() + __pos;
 433
 434           const size_type __how_much = __old_size - __pos - __len1;
 435           if (_M_disjunct(__s))
 436             {
 437               if (__how_much && __len1 != __len2)
 438                 this->_S_move(__p + __len2, __p + __len1, __how_much);
 439               if (__len2)
 440                 this->_S_copy(__p, __s, __len2);
 441             }
 442           else
 443             {
 444               // Work in-place.
 445               if (__len2 && __len2 <= __len1)
 446                 this->_S_move(__p, __s, __len2);
 447               if (__how_much && __len1 != __len2)
 448                 this->_S_move(__p + __len2, __p + __len1, __how_much);
 449               if (__len2 > __len1)
 450                 {
 451                   if (__s + __len2 <= __p + __len1)
 452                     this->_S_move(__p, __s, __len2);
 453                   else if (__s >= __p + __len1)
 454                     this->_S_copy(__p, __s + __len2 - __len1, __len2);
 455                   else
 456                     {
 457                       const size_type __nleft = (__p + __len1) - __s;
 458                       this->_S_move(__p, __s, __nleft);
 459                       this->_S_copy(__p + __nleft, __p + __len2,
 460                                     __len2 - __nleft);
 461                     }
 462                 }
 463             }
 464         }
 465       else
 466         this->_M_mutate(__pos, __len1, __s, __len2);
 467
 468       this->_M_set_length(__new_size);
 469       return *this;
 470     }
 471
 472   template<typename _CharT, typename _Traits, typename _Alloc>
 473     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 474     basic_string<_CharT, _Traits, _Alloc>::
 475     copy(_CharT* __s, size_type __n, size_type __pos) const
 476     {
 477       _M_check(__pos, "basic_string::copy");
 478       __n = _M_limit(__pos, __n);
 479       __glibcxx_requires_string_len(__s, __n);
 480       if (__n)
 481         _S_copy(__s, _M_data() + __pos, __n);
 482       // 21.3.5.7 par 3: do not append null.  (good.)
 483       return __n;
 484     }
 485
 486 #else  // !_GLIBCXX_USE_CXX11_ABI
 487
 488   template<typename _CharT, typename _Traits, typename _Alloc>
 489     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
 490     basic_string<_CharT, _Traits, _Alloc>::
 491     _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;
 492
 493   template<typename _CharT, typename _Traits, typename _Alloc>
 494     const _CharT
 495     basic_string<_CharT, _Traits, _Alloc>::
 496     _Rep::_S_terminal = _CharT();
 497
 498   template<typename _CharT, typename _Traits, typename _Alloc>
 499     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
 500     basic_string<_CharT, _Traits, _Alloc>::npos;
 501
 502   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
 503   // at static init time (before static ctors are run).
 504   template<typename _CharT, typename _Traits, typename _Alloc>
 505     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 506     basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[
 507     (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /
 508       sizeof(size_type)];
 509
 510   // NB: This is the special case for Input Iterators, used in
 511   // istreambuf_iterators, etc.
 512   // Input Iterators have a cost structure very different from
 513   // pointers, calling for a different coding style.
 514   template<typename _CharT, typename _Traits, typename _Alloc>
 515     template<typename _InIterator>
 516       _CharT*
 517       basic_string<_CharT, _Traits, _Alloc>::
 518       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
 519                    input_iterator_tag)
 520       {
 521 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
 522         if (__beg == __end && __a == _Alloc())
 523           return _S_empty_rep()._M_refdata();
 524 #endif
 525         // Avoid reallocation for common case.
 526         _CharT __buf[128];
 527         size_type __len = 0;
 528         while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
 529           {
 530             __buf[__len++] = *__beg;
 531             ++__beg;
 532           }
 533         _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
 534         _M_copy(__r->_M_refdata(), __buf, __len);
 535         __try
 536           {
 537             while (__beg != __end)
 538               {
 539                 if (__len == __r->_M_capacity)
 540                   {
 541                     // Allocate more space.
 542                     _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
 543                     _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
 544                     __r->_M_destroy(__a);
 545                     __r = __another;
 546                   }
 547                 __r->_M_refdata()[__len++] = *__beg;
 548                 ++__beg;
 549               }
 550           }
 551         __catch(...)
 552           {
 553             __r->_M_destroy(__a);
 554             __throw_exception_again;
 555           }
 556         __r->_M_set_length_and_sharable(__len);
 557         return __r->_M_refdata();
 558       }
 559
 560   template<typename _CharT, typename _Traits, typename _Alloc>
 561     template <typename _InIterator>
 562       _CharT*
 563       basic_string<_CharT, _Traits, _Alloc>::
 564       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
 565                    forward_iterator_tag)
 566       {
 567 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
 568         if (__beg == __end && __a == _Alloc())
 569           return _S_empty_rep()._M_refdata();
 570 #endif
 571         // NB: Not required, but considered best practice.
 572         if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
 573           __throw_logic_error(__N("basic_string::_S_construct null not valid"));
 574
 575         const size_type __dnew = static_cast<size_type>(std::distance(__beg,
 576                                                                       __end));
 577         // Check for out_of_range and length_error exceptions.
 578         _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
 579         __try
 580           { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
 581         __catch(...)
 582           {
 583             __r->_M_destroy(__a);
 584             __throw_exception_again;
 585           }
 586         __r->_M_set_length_and_sharable(__dnew);
 587         return __r->_M_refdata();
 588       }
 589
 590   template<typename _CharT, typename _Traits, typename _Alloc>
 591     _CharT*
 592     basic_string<_CharT, _Traits, _Alloc>::
 593     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
 594     {
 595 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
 596       if (__n == 0 && __a == _Alloc())
 597         return _S_empty_rep()._M_refdata();
 598 #endif
 599       // Check for out_of_range and length_error exceptions.
 600       _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
 601       if (__n)
 602         _M_assign(__r->_M_refdata(), __n, __c);
 603
 604       __r->_M_set_length_and_sharable(__n);
 605       return __r->_M_refdata();
 606     }
 607
 608   template<typename _CharT, typename _Traits, typename _Alloc>
 609     basic_string<_CharT, _Traits, _Alloc>::
 610     basic_string(const basic_string& __str)
 611     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
 612                                           __str.get_allocator()),
 613                   __str.get_allocator())
 614     { }
 615
 616   template<typename _CharT, typename _Traits, typename _Alloc>
 617     basic_string<_CharT, _Traits, _Alloc>::
 618     basic_string(const _Alloc& __a)
 619     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
 620     { }
 621
 622   template<typename _CharT, typename _Traits, typename _Alloc>
 623     basic_string<_CharT, _Traits, _Alloc>::
 624     basic_string(const basic_string& __str, size_type __pos, const _Alloc& __a)
 625     : _M_dataplus(_S_construct(__str._M_data()
 626                                + __str._M_check(__pos,
 627                                                 "basic_string::basic_string"),
 628                                __str._M_data() + __str._M_limit(__pos, npos)
 629                                + __pos, __a), __a)
 630     { }
 631
 632   template<typename _CharT, typename _Traits, typename _Alloc>
 633     basic_string<_CharT, _Traits, _Alloc>::
 634     basic_string(const basic_string& __str, size_type __pos, size_type __n)
 635     : _M_dataplus(_S_construct(__str._M_data()
 636                                + __str._M_check(__pos,
 637                                                 "basic_string::basic_string"),
 638                                __str._M_data() + __str._M_limit(__pos, __n)
 639                                + __pos, _Alloc()), _Alloc())
 640     { }
 641
 642   template<typename _CharT, typename _Traits, typename _Alloc>
 643     basic_string<_CharT, _Traits, _Alloc>::
 644     basic_string(const basic_string& __str, size_type __pos,
 645                  size_type __n, const _Alloc& __a)
 646     : _M_dataplus(_S_construct(__str._M_data()
 647                                + __str._M_check(__pos,
 648                                                 "basic_string::basic_string"),
 649                                __str._M_data() + __str._M_limit(__pos, __n)
 650                                + __pos, __a), __a)
 651     { }
 652
 653   // TBD: DPG annotate
 654   template<typename _CharT, typename _Traits, typename _Alloc>
 655     basic_string<_CharT, _Traits, _Alloc>::
 656     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
 657     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
 658     { }
 659
 660   // TBD: DPG annotate
 661   template<typename _CharT, typename _Traits, typename _Alloc>
 662     basic_string<_CharT, _Traits, _Alloc>::
 663     basic_string(const _CharT* __s, const _Alloc& __a)
 664     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
 665                                __s + npos, __a), __a)
 666     { }
 667
 668   template<typename _CharT, typename _Traits, typename _Alloc>
 669     basic_string<_CharT, _Traits, _Alloc>::
 670     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
 671     : _M_dataplus(_S_construct(__n, __c, __a), __a)
 672     { }
 673
 674   // TBD: DPG annotate
 675   template<typename _CharT, typename _Traits, typename _Alloc>
 676     template<typename _InputIterator>
 677     basic_string<_CharT, _Traits, _Alloc>::
 678     basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
 679     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
 680     { }
 681
 682 #if __cplusplus >= 201103L
 683   template<typename _CharT, typename _Traits, typename _Alloc>
 684     basic_string<_CharT, _Traits, _Alloc>::
 685     basic_string(initializer_list<_CharT> __l, const _Alloc& __a)
 686     : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a)
 687     { }
 688 #endif
 689
 690   template<typename _CharT, typename _Traits, typename _Alloc>
 691     basic_string<_CharT, _Traits, _Alloc>&
 692     basic_string<_CharT, _Traits, _Alloc>::
 693     assign(const basic_string& __str)
 694     {
 695       if (_M_rep() != __str._M_rep())
 696         {
 697           // XXX MT
 698           const allocator_type __a = this->get_allocator();
 699           _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
 700           _M_rep()->_M_dispose(__a);
 701           _M_data(__tmp);
 702         }
 703       return *this;
 704     }
 705
 706   template<typename _CharT, typename _Traits, typename _Alloc>
 707     basic_string<_CharT, _Traits, _Alloc>&
 708     basic_string<_CharT, _Traits, _Alloc>::
 709     assign(const _CharT* __s, size_type __n)
 710     {
 711       __glibcxx_requires_string_len(__s, __n);
 712       _M_check_length(this->size(), __n, "basic_string::assign");
 713       if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
 714         return _M_replace_safe(size_type(0), this->size(), __s, __n);
 715       else
 716         {
 717           // Work in-place.
 718           const size_type __pos = __s - _M_data();
 719           if (__pos >= __n)
 720             _M_copy(_M_data(), __s, __n);
 721           else if (__pos)
 722             _M_move(_M_data(), __s, __n);
 723           _M_rep()->_M_set_length_and_sharable(__n);
 724           return *this;
 725         }
 726      }
 727
 728   template<typename _CharT, typename _Traits, typename _Alloc>
 729     basic_string<_CharT, _Traits, _Alloc>&
 730     basic_string<_CharT, _Traits, _Alloc>::
 731     append(size_type __n, _CharT __c)
 732     {
 733       if (__n)
 734         {
 735           _M_check_length(size_type(0), __n, "basic_string::append");
 736           const size_type __len = __n + this->size();
 737           if (__len > this->capacity() || _M_rep()->_M_is_shared())
 738             this->reserve(__len);
 739           _M_assign(_M_data() + this->size(), __n, __c);
 740           _M_rep()->_M_set_length_and_sharable(__len);
 741         }
 742       return *this;
 743     }
 744
 745   template<typename _CharT, typename _Traits, typename _Alloc>
 746     basic_string<_CharT, _Traits, _Alloc>&
 747     basic_string<_CharT, _Traits, _Alloc>::
 748     append(const _CharT* __s, size_type __n)
 749     {
 750       __glibcxx_requires_string_len(__s, __n);
 751       if (__n)
 752         {
 753           _M_check_length(size_type(0), __n, "basic_string::append");
 754           const size_type __len = __n + this->size();
 755           if (__len > this->capacity() || _M_rep()->_M_is_shared())
 756             {
 757               if (_M_disjunct(__s))
 758                 this->reserve(__len);
 759               else
 760                 {
 761                   const size_type __off = __s - _M_data();
 762                   this->reserve(__len);
 763                   __s = _M_data() + __off;
 764                 }
 765             }
 766           _M_copy(_M_data() + this->size(), __s, __n);
 767           _M_rep()->_M_set_length_and_sharable(__len);
 768         }
 769       return *this;
 770     }
 771
 772   template<typename _CharT, typename _Traits, typename _Alloc>
 773     basic_string<_CharT, _Traits, _Alloc>&
 774     basic_string<_CharT, _Traits, _Alloc>::
 775     append(const basic_string& __str)
 776     {
 777       const size_type __size = __str.size();
 778       if (__size)
 779         {
 780           const size_type __len = __size + this->size();
 781           if (__len > this->capacity() || _M_rep()->_M_is_shared())
 782             this->reserve(__len);
 783           _M_copy(_M_data() + this->size(), __str._M_data(), __size);
 784           _M_rep()->_M_set_length_and_sharable(__len);
 785         }
 786       return *this;
 787     }
 788
 789   template<typename _CharT, typename _Traits, typename _Alloc>
 790     basic_string<_CharT, _Traits, _Alloc>&
 791     basic_string<_CharT, _Traits, _Alloc>::
 792     append(const basic_string& __str, size_type __pos, size_type __n)
 793     {
 794       __str._M_check(__pos, "basic_string::append");
 795       __n = __str._M_limit(__pos, __n);
 796       if (__n)
 797         {
 798           const size_type __len = __n + this->size();
 799           if (__len > this->capacity() || _M_rep()->_M_is_shared())
 800             this->reserve(__len);
 801           _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n);
 802           _M_rep()->_M_set_length_and_sharable(__len);
 803         }
 804       return *this;
 805     }
 806
 807    template<typename _CharT, typename _Traits, typename _Alloc>
 808      basic_string<_CharT, _Traits, _Alloc>&
 809      basic_string<_CharT, _Traits, _Alloc>::
 810      insert(size_type __pos, const _CharT* __s, size_type __n)
 811      {
 812        __glibcxx_requires_string_len(__s, __n);
 813        _M_check(__pos, "basic_string::insert");
 814        _M_check_length(size_type(0), __n, "basic_string::insert");
 815        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
 816          return _M_replace_safe(__pos, size_type(0), __s, __n);
 817        else
 818          {
 819            // Work in-place.
 820            const size_type __off = __s - _M_data();
 821            _M_mutate(__pos, 0, __n);
 822            __s = _M_data() + __off;
 823            _CharT* __p = _M_data() + __pos;
 824            if (__s  + __n <= __p)
 825              _M_copy(__p, __s, __n);
 826            else if (__s >= __p)
 827              _M_copy(__p, __s + __n, __n);
 828            else
 829              {
 830                const size_type __nleft = __p - __s;
 831                _M_copy(__p, __s, __nleft);
 832                _M_copy(__p + __nleft, __p + __n, __n - __nleft);
 833              }
 834            return *this;
 835          }
 836      }
 837
 838    template<typename _CharT, typename _Traits, typename _Alloc>
 839      typename basic_string<_CharT, _Traits, _Alloc>::iterator
 840      basic_string<_CharT, _Traits, _Alloc>::
 841      erase(iterator __first, iterator __last)
 842      {
 843        _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
 844                                 && __last <= _M_iend());
 845
 846        // NB: This isn't just an optimization (bail out early when
 847        // there is nothing to do, really), it's also a correctness
 848        // issue vs MT, see libstdc++/40518.
 849        const size_type __size = __last - __first;
 850        if (__size)
 851          {
 852            const size_type __pos = __first - _M_ibegin();
 853            _M_mutate(__pos, __size, size_type(0));
 854            _M_rep()->_M_set_leaked();
 855            return iterator(_M_data() + __pos);
 856          }
 857        else
 858          return __first;
 859      }
 860
 861    template<typename _CharT, typename _Traits, typename _Alloc>
 862      basic_string<_CharT, _Traits, _Alloc>&
 863      basic_string<_CharT, _Traits, _Alloc>::
 864      replace(size_type __pos, size_type __n1, const _CharT* __s,
 865              size_type __n2)
 866      {
 867        __glibcxx_requires_string_len(__s, __n2);
 868        _M_check(__pos, "basic_string::replace");
 869        __n1 = _M_limit(__pos, __n1);
 870        _M_check_length(__n1, __n2, "basic_string::replace");
 871        bool __left;
 872        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
 873          return _M_replace_safe(__pos, __n1, __s, __n2);
 874        else if ((__left = __s + __n2 <= _M_data() + __pos)
 875                 || _M_data() + __pos + __n1 <= __s)
 876          {
 877            // Work in-place: non-overlapping case.
 878            size_type __off = __s - _M_data();
 879            __left ? __off : (__off += __n2 - __n1);
 880            _M_mutate(__pos, __n1, __n2);
 881            _M_copy(_M_data() + __pos, _M_data() + __off, __n2);
 882            return *this;
 883          }
 884        else
 885          {
 886            // Todo: overlapping case.
 887            const basic_string __tmp(__s, __n2);
 888            return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
 889          }
 890      }
 891
 892   template<typename _CharT, typename _Traits, typename _Alloc>
 893     void
 894     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 895     _M_destroy(const _Alloc& __a) throw ()
 896     {
 897       const size_type __size = sizeof(_Rep_base) +
 898                                (this->_M_capacity + 1) * sizeof(_CharT);
 899       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
 900     }
 901
 902   template<typename _CharT, typename _Traits, typename _Alloc>
 903     void
 904     basic_string<_CharT, _Traits, _Alloc>::
 905     _M_leak_hard()
 906     {
 907 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
 908       if (_M_rep() == &_S_empty_rep())
 909         return;
 910 #endif
 911       if (_M_rep()->_M_is_shared())
 912         _M_mutate(0, 0, 0);
 913       _M_rep()->_M_set_leaked();
 914     }
 915
 916   template<typename _CharT, typename _Traits, typename _Alloc>
 917     void
 918     basic_string<_CharT, _Traits, _Alloc>::
 919     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
 920     {
 921       const size_type __old_size = this->size();
 922       const size_type __new_size = __old_size + __len2 - __len1;
 923       const size_type __how_much = __old_size - __pos - __len1;
 924
 925       if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
 926         {
 927           // Must reallocate.
 928           const allocator_type __a = get_allocator();
 929           _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
 930
 931           if (__pos)
 932             _M_copy(__r->_M_refdata(), _M_data(), __pos);
 933           if (__how_much)
 934             _M_copy(__r->_M_refdata() + __pos + __len2,
 935                     _M_data() + __pos + __len1, __how_much);
 936
 937           _M_rep()->_M_dispose(__a);
 938           _M_data(__r->_M_refdata());
 939         }
 940       else if (__how_much && __len1 != __len2)
 941         {
 942           // Work in-place.
 943           _M_move(_M_data() + __pos + __len2,
 944                   _M_data() + __pos + __len1, __how_much);
 945         }
 946       _M_rep()->_M_set_length_and_sharable(__new_size);
 947     }
 948
 949   template<typename _CharT, typename _Traits, typename _Alloc>
 950     void
 951     basic_string<_CharT, _Traits, _Alloc>::
 952     reserve(size_type __res)
 953     {
 954       if (__res != this->capacity() || _M_rep()->_M_is_shared())
 955         {
 956           // Make sure we don't shrink below the current size
 957           if (__res < this->size())
 958             __res = this->size();
 959           const allocator_type __a = get_allocator();
 960           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
 961           _M_rep()->_M_dispose(__a);
 962           _M_data(__tmp);
 963         }
 964     }
 965
 966   template<typename _CharT, typename _Traits, typename _Alloc>
 967     void
 968     basic_string<_CharT, _Traits, _Alloc>::
 969     swap(basic_string& __s)
 970     {
 971       if (_M_rep()->_M_is_leaked())
 972         _M_rep()->_M_set_sharable();
 973       if (__s._M_rep()->_M_is_leaked())
 974         __s._M_rep()->_M_set_sharable();
 975       if (this->get_allocator() == __s.get_allocator())
 976         {
 977           _CharT* __tmp = _M_data();
 978           _M_data(__s._M_data());
 979           __s._M_data(__tmp);
 980         }
 981       // The code below can usually be optimized away.
 982       else
 983         {
 984           const basic_string __tmp1(_M_ibegin(), _M_iend(),
 985                                     __s.get_allocator());
 986           const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
 987                                     this->get_allocator());
 988           *this = __tmp2;
 989           __s = __tmp1;
 990         }
 991     }
 992
 993   template<typename _CharT, typename _Traits, typename _Alloc>
 994     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
 995     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 996     _S_create(size_type __capacity, size_type __old_capacity,
 997               const _Alloc& __alloc)
 998     {
 999       // _GLIBCXX_RESOLVE_LIB_DEFECTS
1000       // 83.  String::npos vs. string::max_size()
1001       if (__capacity > _S_max_size)
1002         __throw_length_error(__N("basic_string::_S_create"));
1003
1004       // The standard places no restriction on allocating more memory
1005       // than is strictly needed within this layer at the moment or as
1006       // requested by an explicit application call to reserve().
1007
1008       // Many malloc implementations perform quite poorly when an
1009       // application attempts to allocate memory in a stepwise fashion
1010       // growing each allocation size by only 1 char.  Additionally,
1011       // it makes little sense to allocate less linear memory than the
1012       // natural blocking size of the malloc implementation.
1013       // Unfortunately, we would need a somewhat low-level calculation
1014       // with tuned parameters to get this perfect for any particular
1015       // malloc implementation.  Fortunately, generalizations about
1016       // common features seen among implementations seems to suffice.
1017
1018       // __pagesize need not match the actual VM page size for good
1019       // results in practice, thus we pick a common value on the low
1020       // side.  __malloc_header_size is an estimate of the amount of
1021       // overhead per memory allocation (in practice seen N * sizeof
1022       // (void*) where N is 0, 2 or 4).  According to folklore,
1023       // picking this value on the high side is better than
1024       // low-balling it (especially when this algorithm is used with
1025       // malloc implementations that allocate memory blocks rounded up
1026       // to a size which is a power of 2).
1027       const size_type __pagesize = 4096;
1028       const size_type __malloc_header_size = 4 * sizeof(void*);
1029
1030       // The below implements an exponential growth policy, necessary to
1031       // meet amortized linear time requirements of the library: see
1032       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
1033       // It's active for allocations requiring an amount of memory above
1034       // system pagesize. This is consistent with the requirements of the
1035       // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
1036       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
1037         __capacity = 2 * __old_capacity;
1038
1039       // NB: Need an array of char_type[__capacity], plus a terminating
1040       // null char_type() element, plus enough for the _Rep data structure.
1041       // Whew. Seemingly so needy, yet so elemental.
1042       size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
1043
1044       const size_type __adj_size = __size + __malloc_header_size;
1045       if (__adj_size > __pagesize && __capacity > __old_capacity)
1046         {
1047           const size_type __extra = __pagesize - __adj_size % __pagesize;
1048           __capacity += __extra / sizeof(_CharT);
1049           // Never allocate a string bigger than _S_max_size.
1050           if (__capacity > _S_max_size)
1051             __capacity = _S_max_size;
1052           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
1053         }
1054
1055       // NB: Might throw, but no worries about a leak, mate: _Rep()
1056       // does not throw.
1057       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
1058       _Rep *__p = new (__place) _Rep;
1059       __p->_M_capacity = __capacity;
1060       // ABI compatibility - 3.4.x set in _S_create both
1061       // _M_refcount and _M_length.  All callers of _S_create
1062       // in basic_string.tcc then set just _M_length.
1063       // In 4.0.x and later both _M_refcount and _M_length
1064       // are initialized in the callers, unfortunately we can
1065       // have 3.4.x compiled code with _S_create callers inlined
1066       // calling 4.0.x+ _S_create.
1067       __p->_M_set_sharable();
1068       return __p;
1069     }
1070
1071   template<typename _CharT, typename _Traits, typename _Alloc>
1072     _CharT*
1073     basic_string<_CharT, _Traits, _Alloc>::_Rep::
1074     _M_clone(const _Alloc& __alloc, size_type __res)
1075     {
1076       // Requested capacity of the clone.
1077       const size_type __requested_cap = this->_M_length + __res;
1078       _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
1079                                   __alloc);
1080       if (this->_M_length)
1081         _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
1082
1083       __r->_M_set_length_and_sharable(this->_M_length);
1084       return __r->_M_refdata();
1085     }
1086
1087   template<typename _CharT, typename _Traits, typename _Alloc>
1088     void
1089     basic_string<_CharT, _Traits, _Alloc>::
1090     resize(size_type __n, _CharT __c)
1091     {
1092       const size_type __size = this->size();
1093       _M_check_length(__size, __n, "basic_string::resize");
1094       if (__size < __n)
1095         this->append(__n - __size, __c);
1096       else if (__n < __size)
1097         this->erase(__n);
1098       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
1099     }
1100
1101   template<typename _CharT, typename _Traits, typename _Alloc>
1102     template<typename _InputIterator>
1103       basic_string<_CharT, _Traits, _Alloc>&
1104       basic_string<_CharT, _Traits, _Alloc>::
1105       _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
1106                           _InputIterator __k2, __false_type)
1107       {
1108         const basic_string __s(__k1, __k2);
1109         const size_type __n1 = __i2 - __i1;
1110         _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
1111         return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
1112                                __s.size());
1113       }
1114
1115   template<typename _CharT, typename _Traits, typename _Alloc>
1116     basic_string<_CharT, _Traits, _Alloc>&
1117     basic_string<_CharT, _Traits, _Alloc>::
1118     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
1119                    _CharT __c)
1120     {
1121       _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
1122       _M_mutate(__pos1, __n1, __n2);
1123       if (__n2)
1124         _M_assign(_M_data() + __pos1, __n2, __c);
1125       return *this;
1126     }
1127
1128   template<typename _CharT, typename _Traits, typename _Alloc>
1129     basic_string<_CharT, _Traits, _Alloc>&
1130     basic_string<_CharT, _Traits, _Alloc>::
1131     _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
1132                     size_type __n2)
1133     {
1134       _M_mutate(__pos1, __n1, __n2);
1135       if (__n2)
1136         _M_copy(_M_data() + __pos1, __s, __n2);
1137       return *this;
1138     }
1139
1140     template<typename _CharT, typename _Traits, typename _Alloc>
1141     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1142     basic_string<_CharT, _Traits, _Alloc>::
1143     copy(_CharT* __s, size_type __n, size_type __pos) const
1144     {
1145       _M_check(__pos, "basic_string::copy");
1146       __n = _M_limit(__pos, __n);
1147       __glibcxx_requires_string_len(__s, __n);
1148       if (__n)
1149         _M_copy(__s, _M_data() + __pos, __n);
1150       // 21.3.5.7 par 3: do not append null.  (good.)
1151       return __n;
1152     }
1153 #endif  // !_GLIBCXX_USE_CXX11_ABI
1154
1155   template<typename _CharT, typename _Traits, typename _Alloc>
1156     basic_string<_CharT, _Traits, _Alloc>
1157     operator+(const _CharT* __lhs,
1158               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1159     {
1160       __glibcxx_requires_string(__lhs);
1161       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1162       typedef typename __string_type::size_type   __size_type;
1163       const __size_type __len = _Traits::length(__lhs);
1164       __string_type __str;
1165       __str.reserve(__len + __rhs.size());
1166       __str.append(__lhs, __len);
1167       __str.append(__rhs);
1168       return __str;
1169     }
1170
1171   template<typename _CharT, typename _Traits, typename _Alloc>
1172     basic_string<_CharT, _Traits, _Alloc>
1173     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
1174     {
1175       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
1176       typedef typename __string_type::size_type   __size_type;
1177       __string_type __str;
1178       const __size_type __len = __rhs.size();
1179       __str.reserve(__len + 1);
1180       __str.append(__size_type(1), __lhs);
1181       __str.append(__rhs);
1182       return __str;
1183     }
1184
1185   template<typename _CharT, typename _Traits, typename _Alloc>
1186     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1187     basic_string<_CharT, _Traits, _Alloc>::
1188     find(const _CharT* __s, size_type __pos, size_type __n) const
1189     _GLIBCXX_NOEXCEPT
1190     {
1191       __glibcxx_requires_string_len(__s, __n);
1192       const size_type __size = this->size();
1193
1194       if (__n == 0)
1195         return __pos <= __size ? __pos : npos;
1196       if (__pos >= __size)
1197         return npos;
1198
1199       const _CharT __elem0 = __s[0];
1200       const _CharT* const __data = data();
1201       const _CharT* __first = __data + __pos;
1202       const _CharT* const __last = __data + __size;
1203       size_type __len = __size - __pos;
1204
1205       while (__len >= __n)
1206         {
1207           // Find the first occurrence of __elem0:
1208           __first = traits_type::find(__first, __len - __n + 1, __elem0);
1209           if (!__first)
1210             return npos;
1211           // Compare the full strings from the first occurrence of __elem0.
1212           // We already know that __first[0] == __s[0] but compare them again
1213           // anyway because __s is probably aligned, which helps memcmp.
1214           if (traits_type::compare(__first, __s, __n) == 0)
1215             return __first - __data;
1216           __len = __last - ++__first;
1217         }
1218       return npos;
1219     }
1220
1221   template<typename _CharT, typename _Traits, typename _Alloc>
1222     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1223     basic_string<_CharT, _Traits, _Alloc>::
1224     find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1225     {
1226       size_type __ret = npos;
1227       const size_type __size = this->size();
1228       if (__pos < __size)
1229         {
1230           const _CharT* __data = _M_data();
1231           const size_type __n = __size - __pos;
1232           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
1233           if (__p)
1234             __ret = __p - __data;
1235         }
1236       return __ret;
1237     }
1238
1239   template<typename _CharT, typename _Traits, typename _Alloc>
1240     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1241     basic_string<_CharT, _Traits, _Alloc>::
1242     rfind(const _CharT* __s, size_type __pos, size_type __n) const
1243     _GLIBCXX_NOEXCEPT
1244     {
1245       __glibcxx_requires_string_len(__s, __n);
1246       const size_type __size = this->size();
1247       if (__n <= __size)
1248         {
1249           __pos = std::min(size_type(__size - __n), __pos);
1250           const _CharT* __data = _M_data();
1251           do
1252             {
1253               if (traits_type::compare(__data + __pos, __s, __n) == 0)
1254                 return __pos;
1255             }
1256           while (__pos-- > 0);
1257         }
1258       return npos;
1259     }
1260
1261   template<typename _CharT, typename _Traits, typename _Alloc>
1262     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1263     basic_string<_CharT, _Traits, _Alloc>::
1264     rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1265     {
1266       size_type __size = this->size();
1267       if (__size)
1268         {
1269           if (--__size > __pos)
1270             __size = __pos;
1271           for (++__size; __size-- > 0; )
1272             if (traits_type::eq(_M_data()[__size], __c))
1273               return __size;
1274         }
1275       return npos;
1276     }
1277
1278   template<typename _CharT, typename _Traits, typename _Alloc>
1279     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1280     basic_string<_CharT, _Traits, _Alloc>::
1281     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
1282     _GLIBCXX_NOEXCEPT
1283     {
1284       __glibcxx_requires_string_len(__s, __n);
1285       for (; __n && __pos < this->size(); ++__pos)
1286         {
1287           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
1288           if (__p)
1289             return __pos;
1290         }
1291       return npos;
1292     }
1293
1294   template<typename _CharT, typename _Traits, typename _Alloc>
1295     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1296     basic_string<_CharT, _Traits, _Alloc>::
1297     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
1298     _GLIBCXX_NOEXCEPT
1299     {
1300       __glibcxx_requires_string_len(__s, __n);
1301       size_type __size = this->size();
1302       if (__size && __n)
1303         {
1304           if (--__size > __pos)
1305             __size = __pos;
1306           do
1307             {
1308               if (traits_type::find(__s, __n, _M_data()[__size]))
1309                 return __size;
1310             }
1311           while (__size-- != 0);
1312         }
1313       return npos;
1314     }
1315
1316   template<typename _CharT, typename _Traits, typename _Alloc>
1317     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1318     basic_string<_CharT, _Traits, _Alloc>::
1319     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
1320     _GLIBCXX_NOEXCEPT
1321     {
1322       __glibcxx_requires_string_len(__s, __n);
1323       for (; __pos < this->size(); ++__pos)
1324         if (!traits_type::find(__s, __n, _M_data()[__pos]))
1325           return __pos;
1326       return npos;
1327     }
1328
1329   template<typename _CharT, typename _Traits, typename _Alloc>
1330     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1331     basic_string<_CharT, _Traits, _Alloc>::
1332     find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1333     {
1334       for (; __pos < this->size(); ++__pos)
1335         if (!traits_type::eq(_M_data()[__pos], __c))
1336           return __pos;
1337       return npos;
1338     }
1339
1340   template<typename _CharT, typename _Traits, typename _Alloc>
1341     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1342     basic_string<_CharT, _Traits, _Alloc>::
1343     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
1344     _GLIBCXX_NOEXCEPT
1345     {
1346       __glibcxx_requires_string_len(__s, __n);
1347       size_type __size = this->size();
1348       if (__size)
1349         {
1350           if (--__size > __pos)
1351             __size = __pos;
1352           do
1353             {
1354               if (!traits_type::find(__s, __n, _M_data()[__size]))
1355                 return __size;
1356             }
1357           while (__size--);
1358         }
1359       return npos;
1360     }
1361
1362   template<typename _CharT, typename _Traits, typename _Alloc>
1363     typename basic_string<_CharT, _Traits, _Alloc>::size_type
1364     basic_string<_CharT, _Traits, _Alloc>::
1365     find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
1366     {
1367       size_type __size = this->size();
1368       if (__size)
1369         {
1370           if (--__size > __pos)
1371             __size = __pos;
1372           do
1373             {
1374               if (!traits_type::eq(_M_data()[__size], __c))
1375                 return __size;
1376             }
1377           while (__size--);
1378         }
1379       return npos;
1380     }
1381
1382   template<typename _CharT, typename _Traits, typename _Alloc>
1383     int
1384     basic_string<_CharT, _Traits, _Alloc>::
1385     compare(size_type __pos, size_type __n, const basic_string& __str) const
1386     {
1387       _M_check(__pos, "basic_string::compare");
1388       __n = _M_limit(__pos, __n);
1389       const size_type __osize = __str.size();
1390       const size_type __len = std::min(__n, __osize);
1391       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
1392       if (!__r)
1393         __r = _S_compare(__n, __osize);
1394       return __r;
1395     }
1396
1397   template<typename _CharT, typename _Traits, typename _Alloc>
1398     int
1399     basic_string<_CharT, _Traits, _Alloc>::
1400     compare(size_type __pos1, size_type __n1, const basic_string& __str,
1401             size_type __pos2, size_type __n2) const
1402     {
1403       _M_check(__pos1, "basic_string::compare");
1404       __str._M_check(__pos2, "basic_string::compare");
1405       __n1 = _M_limit(__pos1, __n1);
1406       __n2 = __str._M_limit(__pos2, __n2);
1407       const size_type __len = std::min(__n1, __n2);
1408       int __r = traits_type::compare(_M_data() + __pos1,
1409                                      __str.data() + __pos2, __len);
1410       if (!__r)
1411         __r = _S_compare(__n1, __n2);
1412       return __r;
1413     }
1414
1415   template<typename _CharT, typename _Traits, typename _Alloc>
1416     int
1417     basic_string<_CharT, _Traits, _Alloc>::
1418     compare(const _CharT* __s) const _GLIBCXX_NOEXCEPT
1419     {
1420       __glibcxx_requires_string(__s);
1421       const size_type __size = this->size();
1422       const size_type __osize = traits_type::length(__s);
1423       const size_type __len = std::min(__size, __osize);
1424       int __r = traits_type::compare(_M_data(), __s, __len);
1425       if (!__r)
1426         __r = _S_compare(__size, __osize);
1427       return __r;
1428     }
1429
1430   template<typename _CharT, typename _Traits, typename _Alloc>
1431     int
1432     basic_string <_CharT, _Traits, _Alloc>::
1433     compare(size_type __pos, size_type __n1, const _CharT* __s) const
1434     {
1435       __glibcxx_requires_string(__s);
1436       _M_check(__pos, "basic_string::compare");
1437       __n1 = _M_limit(__pos, __n1);
1438       const size_type __osize = traits_type::length(__s);
1439       const size_type __len = std::min(__n1, __osize);
1440       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1441       if (!__r)
1442         __r = _S_compare(__n1, __osize);
1443       return __r;
1444     }
1445
1446   template<typename _CharT, typename _Traits, typename _Alloc>
1447     int
1448     basic_string <_CharT, _Traits, _Alloc>::
1449     compare(size_type __pos, size_type __n1, const _CharT* __s,
1450             size_type __n2) const
1451     {
1452       __glibcxx_requires_string_len(__s, __n2);
1453       _M_check(__pos, "basic_string::compare");
1454       __n1 = _M_limit(__pos, __n1);
1455       const size_type __len = std::min(__n1, __n2);
1456       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1457       if (!__r)
1458         __r = _S_compare(__n1, __n2);
1459       return __r;
1460     }
1461
1462   // 21.3.7.9 basic_string::getline and operators
1463   template<typename _CharT, typename _Traits, typename _Alloc>
1464     basic_istream<_CharT, _Traits>&
1465     operator>>(basic_istream<_CharT, _Traits>& __in,
1466                basic_string<_CharT, _Traits, _Alloc>& __str)
1467     {
1468       typedef basic_istream<_CharT, _Traits>            __istream_type;
1469       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
1470       typedef typename __istream_type::ios_base         __ios_base;
1471       typedef typename __istream_type::int_type         __int_type;
1472       typedef typename __string_type::size_type         __size_type;
1473       typedef ctype<_CharT>                             __ctype_type;
1474       typedef typename __ctype_type::ctype_base         __ctype_base;
1475
1476       __size_type __extracted = 0;
1477       typename __ios_base::iostate __err = __ios_base::goodbit;
1478       typename __istream_type::sentry __cerb(__in, false);
1479       if (__cerb)
1480         {
1481           __try
1482             {
1483               // Avoid reallocation for common case.
1484               __str.erase();
1485               _CharT __buf[128];
1486               __size_type __len = 0;
1487               const streamsize __w = __in.width();
1488               const __size_type __n = __w > 0 ? static_cast<__size_type>(__w)
1489                                               : __str.max_size();
1490               const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc());
1491               const __int_type __eof = _Traits::eof();
1492               __int_type __c = __in.rdbuf()->sgetc();
1493
1494               while (__extracted < __n
1495                      && !_Traits::eq_int_type(__c, __eof)
1496                      && !__ct.is(__ctype_base::space,
1497                                  _Traits::to_char_type(__c)))
1498                 {
1499                   if (__len == sizeof(__buf) / sizeof(_CharT))
1500                     {
1501                       __str.append(__buf, sizeof(__buf) / sizeof(_CharT));
1502                       __len = 0;
1503                     }
1504                   __buf[__len++] = _Traits::to_char_type(__c);
1505                   ++__extracted;
1506                   __c = __in.rdbuf()->snextc();
1507                 }
1508               __str.append(__buf, __len);
1509
1510               if (_Traits::eq_int_type(__c, __eof))
1511                 __err |= __ios_base::eofbit;
1512               __in.width(0);
1513             }
1514           __catch(__cxxabiv1::__forced_unwind&)
1515             {
1516               __in._M_setstate(__ios_base::badbit);
1517               __throw_exception_again;
1518             }
1519           __catch(...)
1520             {
1521               // _GLIBCXX_RESOLVE_LIB_DEFECTS
1522               // 91. Description of operator>> and getline() for string<>
1523               // might cause endless loop
1524               __in._M_setstate(__ios_base::badbit);
1525             }
1526         }
1527       // 211.  operator>>(istream&, string&) doesn't set failbit
1528       if (!__extracted)
1529         __err |= __ios_base::failbit;
1530       if (__err)
1531         __in.setstate(__err);
1532       return __in;
1533     }
1534
1535   template<typename _CharT, typename _Traits, typename _Alloc>
1536     basic_istream<_CharT, _Traits>&
1537     getline(basic_istream<_CharT, _Traits>& __in,
1538             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
1539     {
1540       typedef basic_istream<_CharT, _Traits>            __istream_type;
1541       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
1542       typedef typename __istream_type::ios_base         __ios_base;
1543       typedef typename __istream_type::int_type         __int_type;
1544       typedef typename __string_type::size_type         __size_type;
1545
1546       __size_type __extracted = 0;
1547       const __size_type __n = __str.max_size();
1548       typename __ios_base::iostate __err = __ios_base::goodbit;
1549       typename __istream_type::sentry __cerb(__in, true);
1550       if (__cerb)
1551         {
1552           __try
1553             {
1554               __str.erase();
1555               const __int_type __idelim = _Traits::to_int_type(__delim);
1556               const __int_type __eof = _Traits::eof();
1557               __int_type __c = __in.rdbuf()->sgetc();
1558
1559               while (__extracted < __n
1560                      && !_Traits::eq_int_type(__c, __eof)
1561                      && !_Traits::eq_int_type(__c, __idelim))
1562                 {
1563                   __str += _Traits::to_char_type(__c);
1564                   ++__extracted;
1565                   __c = __in.rdbuf()->snextc();
1566                 }
1567
1568               if (_Traits::eq_int_type(__c, __eof))
1569                 __err |= __ios_base::eofbit;
1570               else if (_Traits::eq_int_type(__c, __idelim))
1571                 {
1572                   ++__extracted;
1573                   __in.rdbuf()->sbumpc();
1574                 }
1575               else
1576                 __err |= __ios_base::failbit;
1577             }
1578           __catch(__cxxabiv1::__forced_unwind&)
1579             {
1580               __in._M_setstate(__ios_base::badbit);
1581               __throw_exception_again;
1582             }
1583           __catch(...)
1584             {
1585               // _GLIBCXX_RESOLVE_LIB_DEFECTS
1586               // 91. Description of operator>> and getline() for string<>
1587               // might cause endless loop
1588               __in._M_setstate(__ios_base::badbit);
1589             }
1590         }
1591       if (!__extracted)
1592         __err |= __ios_base::failbit;
1593       if (__err)
1594         __in.setstate(__err);
1595       return __in;
1596     }
1597
1598   // Inhibit implicit instantiations for required instantiations,
1599   // which are defined via explicit instantiations elsewhere.
1600 #if _GLIBCXX_EXTERN_TEMPLATE > 0 && __cplusplus <= 201402L
1601   extern template class basic_string<char>;
1602   extern template
1603     basic_istream<char>&
1604     operator>>(basic_istream<char>&, string&);
1605   extern template
1606     basic_ostream<char>&
1607     operator<<(basic_ostream<char>&, const string&);
1608   extern template
1609     basic_istream<char>&
1610     getline(basic_istream<char>&, string&, char);
1611   extern template
1612     basic_istream<char>&
1613     getline(basic_istream<char>&, string&);
1614
1615 #ifdef _GLIBCXX_USE_WCHAR_T
1616   extern template class basic_string<wchar_t>;
1617   extern template
1618     basic_istream<wchar_t>&
1619     operator>>(basic_istream<wchar_t>&, wstring&);
1620   extern template
1621     basic_ostream<wchar_t>&
1622     operator<<(basic_ostream<wchar_t>&, const wstring&);
1623   extern template
1624     basic_istream<wchar_t>&
1625     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1626   extern template
1627     basic_istream<wchar_t>&
1628     getline(basic_istream<wchar_t>&, wstring&);
1629 #endif
1630 #endif
1631
1632 _GLIBCXX_END_NAMESPACE_VERSION
1633 } // namespace std
1634
1635 #endif