libstdc++
basic_string.tcc
Go to the documentation of this file.
00001 // Components for manipulating sequences of characters -*- C++ -*-
00002 
00003 // Copyright (C) 1997-2019 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/basic_string.tcc
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly. @headername{string}
00028  */
00029 
00030 //
00031 // ISO C++ 14882: 21  Strings library
00032 //
00033 
00034 // Written by Jason Merrill based upon the specification by Takanori Adachi
00035 // in ANSI X3J16/94-0013R2.  Rewritten by Nathan Myers to ISO-14882.
00036 // Non-reference-counted implementation written by Paolo Carlini and
00037 // updated by Jonathan Wakely for ISO-14882-2011.
00038 
00039 #ifndef _BASIC_STRING_TCC
00040 #define _BASIC_STRING_TCC 1
00041 
00042 #pragma GCC system_header
00043 
00044 #include <bits/cxxabi_forced.h>
00045 
00046 namespace std _GLIBCXX_VISIBILITY(default)
00047 {
00048 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00049 
00050 #if _GLIBCXX_USE_CXX11_ABI
00051 
00052   template<typename _CharT, typename _Traits, typename _Alloc>
00053     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
00054     basic_string<_CharT, _Traits, _Alloc>::npos;
00055 
00056   template<typename _CharT, typename _Traits, typename _Alloc>
00057     void
00058     basic_string<_CharT, _Traits, _Alloc>::
00059     swap(basic_string& __s) _GLIBCXX_NOEXCEPT
00060     {
00061       if (this == &__s)
00062         return;
00063 
00064       _Alloc_traits::_S_on_swap(_M_get_allocator(), __s._M_get_allocator());
00065 
00066       if (_M_is_local())
00067         if (__s._M_is_local())
00068           {
00069             if (length() && __s.length())
00070               {
00071                 _CharT __tmp_data[_S_local_capacity + 1];
00072                 traits_type::copy(__tmp_data, __s._M_local_buf,
00073                                   _S_local_capacity + 1);
00074                 traits_type::copy(__s._M_local_buf, _M_local_buf,
00075                                   _S_local_capacity + 1);
00076                 traits_type::copy(_M_local_buf, __tmp_data,
00077                                   _S_local_capacity + 1);
00078               }
00079             else if (__s.length())
00080               {
00081                 traits_type::copy(_M_local_buf, __s._M_local_buf,
00082                                   _S_local_capacity + 1);
00083                 _M_length(__s.length());
00084                 __s._M_set_length(0);
00085                 return;
00086               }
00087             else if (length())
00088               {
00089                 traits_type::copy(__s._M_local_buf, _M_local_buf,
00090                                   _S_local_capacity + 1);
00091                 __s._M_length(length());
00092                 _M_set_length(0);
00093                 return;
00094               }
00095           }
00096         else
00097           {
00098             const size_type __tmp_capacity = __s._M_allocated_capacity;
00099             traits_type::copy(__s._M_local_buf, _M_local_buf,
00100                               _S_local_capacity + 1);
00101             _M_data(__s._M_data());
00102             __s._M_data(__s._M_local_buf);
00103             _M_capacity(__tmp_capacity);
00104           }
00105       else
00106         {
00107           const size_type __tmp_capacity = _M_allocated_capacity;
00108           if (__s._M_is_local())
00109             {
00110               traits_type::copy(_M_local_buf, __s._M_local_buf,
00111                                 _S_local_capacity + 1);
00112               __s._M_data(_M_data());
00113               _M_data(_M_local_buf);
00114             }
00115           else
00116             {
00117               pointer __tmp_ptr = _M_data();
00118               _M_data(__s._M_data());
00119               __s._M_data(__tmp_ptr);
00120               _M_capacity(__s._M_allocated_capacity);
00121             }
00122           __s._M_capacity(__tmp_capacity);
00123         }
00124 
00125       const size_type __tmp_length = length();
00126       _M_length(__s.length());
00127       __s._M_length(__tmp_length);
00128     }
00129 
00130   template<typename _CharT, typename _Traits, typename _Alloc>
00131     typename basic_string<_CharT, _Traits, _Alloc>::pointer
00132     basic_string<_CharT, _Traits, _Alloc>::
00133     _M_create(size_type& __capacity, size_type __old_capacity)
00134     {
00135       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00136       // 83.  String::npos vs. string::max_size()
00137       if (__capacity > max_size())
00138         std::__throw_length_error(__N("basic_string::_M_create"));
00139 
00140       // The below implements an exponential growth policy, necessary to
00141       // meet amortized linear time requirements of the library: see
00142       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
00143       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
00144         {
00145           __capacity = 2 * __old_capacity;
00146           // Never allocate a string bigger than max_size.
00147           if (__capacity > max_size())
00148             __capacity = max_size();
00149         }
00150 
00151       // NB: Need an array of char_type[__capacity], plus a terminating
00152       // null char_type() element.
00153       return _Alloc_traits::allocate(_M_get_allocator(), __capacity + 1);
00154     }
00155 
00156   // NB: This is the special case for Input Iterators, used in
00157   // istreambuf_iterators, etc.
00158   // Input Iterators have a cost structure very different from
00159   // pointers, calling for a different coding style.
00160   template<typename _CharT, typename _Traits, typename _Alloc>
00161     template<typename _InIterator>
00162       void
00163       basic_string<_CharT, _Traits, _Alloc>::
00164       _M_construct(_InIterator __beg, _InIterator __end,
00165                    std::input_iterator_tag)
00166       {
00167         size_type __len = 0;
00168         size_type __capacity = size_type(_S_local_capacity);
00169 
00170         while (__beg != __end && __len < __capacity)
00171           {
00172             _M_data()[__len++] = *__beg;
00173             ++__beg;
00174           }
00175 
00176         __try
00177           {
00178             while (__beg != __end)
00179               {
00180                 if (__len == __capacity)
00181                   {
00182                     // Allocate more space.
00183                     __capacity = __len + 1;
00184                     pointer __another = _M_create(__capacity, __len);
00185                     this->_S_copy(__another, _M_data(), __len);
00186                     _M_dispose();
00187                     _M_data(__another);
00188                     _M_capacity(__capacity);
00189                   }
00190                 _M_data()[__len++] = *__beg;
00191                 ++__beg;
00192               }
00193           }
00194         __catch(...)
00195           {
00196             _M_dispose();
00197             __throw_exception_again;
00198           }
00199 
00200         _M_set_length(__len);
00201       }
00202 
00203   template<typename _CharT, typename _Traits, typename _Alloc>
00204     template<typename _InIterator>
00205       void
00206       basic_string<_CharT, _Traits, _Alloc>::
00207       _M_construct(_InIterator __beg, _InIterator __end,
00208                    std::forward_iterator_tag)
00209       {
00210         // NB: Not required, but considered best practice.
00211         if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
00212           std::__throw_logic_error(__N("basic_string::"
00213                                        "_M_construct null not valid"));
00214 
00215         size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
00216 
00217         if (__dnew > size_type(_S_local_capacity))
00218           {
00219             _M_data(_M_create(__dnew, size_type(0)));
00220             _M_capacity(__dnew);
00221           }
00222 
00223         // Check for out_of_range and length_error exceptions.
00224         __try
00225           { this->_S_copy_chars(_M_data(), __beg, __end); }
00226         __catch(...)
00227           {
00228             _M_dispose();
00229             __throw_exception_again;
00230           }
00231 
00232         _M_set_length(__dnew);
00233       }
00234 
00235   template<typename _CharT, typename _Traits, typename _Alloc>
00236     void
00237     basic_string<_CharT, _Traits, _Alloc>::
00238     _M_construct(size_type __n, _CharT __c)
00239     {
00240       if (__n > size_type(_S_local_capacity))
00241         {
00242           _M_data(_M_create(__n, size_type(0)));
00243           _M_capacity(__n);
00244         }
00245 
00246       if (__n)
00247         this->_S_assign(_M_data(), __n, __c);
00248 
00249       _M_set_length(__n);
00250     }
00251 
00252   template<typename _CharT, typename _Traits, typename _Alloc>
00253     void
00254     basic_string<_CharT, _Traits, _Alloc>::
00255     _M_assign(const basic_string& __str)
00256     {
00257       if (this != &__str)
00258         {
00259           const size_type __rsize = __str.length();
00260           const size_type __capacity = capacity();
00261 
00262           if (__rsize > __capacity)
00263             {
00264               size_type __new_capacity = __rsize;
00265               pointer __tmp = _M_create(__new_capacity, __capacity);
00266               _M_dispose();
00267               _M_data(__tmp);
00268               _M_capacity(__new_capacity);
00269             }
00270 
00271           if (__rsize)
00272             this->_S_copy(_M_data(), __str._M_data(), __rsize);
00273 
00274           _M_set_length(__rsize);
00275         }
00276     }
00277 
00278   template<typename _CharT, typename _Traits, typename _Alloc>
00279     void
00280     basic_string<_CharT, _Traits, _Alloc>::
00281     reserve(size_type __res)
00282     {
00283       // Make sure we don't shrink below the current size.
00284       if (__res < length())
00285         __res = length();
00286 
00287       const size_type __capacity = capacity();
00288       if (__res != __capacity)
00289         {
00290           if (__res > __capacity
00291               || __res > size_type(_S_local_capacity))
00292             {
00293               pointer __tmp = _M_create(__res, __capacity);
00294               this->_S_copy(__tmp, _M_data(), length() + 1);
00295               _M_dispose();
00296               _M_data(__tmp);
00297               _M_capacity(__res);
00298             }
00299           else if (!_M_is_local())
00300             {
00301               this->_S_copy(_M_local_data(), _M_data(), length() + 1);
00302               _M_destroy(__capacity);
00303               _M_data(_M_local_data());
00304             }
00305         }
00306     }
00307 
00308   template<typename _CharT, typename _Traits, typename _Alloc>
00309     void
00310     basic_string<_CharT, _Traits, _Alloc>::
00311     _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
00312               size_type __len2)
00313     {
00314       const size_type __how_much = length() - __pos - __len1;
00315 
00316       size_type __new_capacity = length() + __len2 - __len1;
00317       pointer __r = _M_create(__new_capacity, capacity());
00318 
00319       if (__pos)
00320         this->_S_copy(__r, _M_data(), __pos);
00321       if (__s && __len2)
00322         this->_S_copy(__r + __pos, __s, __len2);
00323       if (__how_much)
00324         this->_S_copy(__r + __pos + __len2,
00325                       _M_data() + __pos + __len1, __how_much);
00326 
00327       _M_dispose();
00328       _M_data(__r);
00329       _M_capacity(__new_capacity);
00330     }
00331 
00332   template<typename _CharT, typename _Traits, typename _Alloc>
00333     void
00334     basic_string<_CharT, _Traits, _Alloc>::
00335     _M_erase(size_type __pos, size_type __n)
00336     {
00337       const size_type __how_much = length() - __pos - __n;
00338 
00339       if (__how_much && __n)
00340         this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much);
00341 
00342       _M_set_length(length() - __n);
00343     }
00344 
00345   template<typename _CharT, typename _Traits, typename _Alloc>
00346     void
00347     basic_string<_CharT, _Traits, _Alloc>::
00348     resize(size_type __n, _CharT __c)
00349     {
00350       const size_type __size = this->size();
00351       if (__size < __n)
00352         this->append(__n - __size, __c);
00353       else if (__n < __size)
00354         this->_M_set_length(__n);
00355     }
00356 
00357   template<typename _CharT, typename _Traits, typename _Alloc>
00358     basic_string<_CharT, _Traits, _Alloc>&
00359     basic_string<_CharT, _Traits, _Alloc>::
00360     _M_append(const _CharT* __s, size_type __n)
00361     {
00362       const size_type __len = __n + this->size();
00363 
00364       if (__len <= this->capacity())
00365         {
00366           if (__n)
00367             this->_S_copy(this->_M_data() + this->size(), __s, __n);
00368         }
00369       else
00370         this->_M_mutate(this->size(), size_type(0), __s, __n);
00371 
00372       this->_M_set_length(__len);
00373       return *this;
00374     }
00375 
00376   template<typename _CharT, typename _Traits, typename _Alloc>
00377     template<typename _InputIterator>
00378       basic_string<_CharT, _Traits, _Alloc>&
00379       basic_string<_CharT, _Traits, _Alloc>::
00380       _M_replace_dispatch(const_iterator __i1, const_iterator __i2,
00381                           _InputIterator __k1, _InputIterator __k2,
00382                           std::__false_type)
00383       {
00384         const basic_string __s(__k1, __k2);
00385         const size_type __n1 = __i2 - __i1;
00386         return _M_replace(__i1 - begin(), __n1, __s._M_data(),
00387                           __s.size());
00388       }
00389 
00390   template<typename _CharT, typename _Traits, typename _Alloc>
00391     basic_string<_CharT, _Traits, _Alloc>&
00392     basic_string<_CharT, _Traits, _Alloc>::
00393     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
00394                    _CharT __c)
00395     {
00396       _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
00397 
00398       const size_type __old_size = this->size();
00399       const size_type __new_size = __old_size + __n2 - __n1;
00400 
00401       if (__new_size <= this->capacity())
00402         {
00403           pointer __p = this->_M_data() + __pos1;
00404 
00405           const size_type __how_much = __old_size - __pos1 - __n1;
00406           if (__how_much && __n1 != __n2)
00407             this->_S_move(__p + __n2, __p + __n1, __how_much);
00408         }
00409       else
00410         this->_M_mutate(__pos1, __n1, 0, __n2);
00411 
00412       if (__n2)
00413         this->_S_assign(this->_M_data() + __pos1, __n2, __c);
00414 
00415       this->_M_set_length(__new_size);
00416       return *this;
00417     }
00418 
00419   template<typename _CharT, typename _Traits, typename _Alloc>
00420     basic_string<_CharT, _Traits, _Alloc>&
00421     basic_string<_CharT, _Traits, _Alloc>::
00422     _M_replace(size_type __pos, size_type __len1, const _CharT* __s,
00423                const size_type __len2)
00424     {
00425       _M_check_length(__len1, __len2, "basic_string::_M_replace");
00426 
00427       const size_type __old_size = this->size();
00428       const size_type __new_size = __old_size + __len2 - __len1;
00429 
00430       if (__new_size <= this->capacity())
00431         {
00432           pointer __p = this->_M_data() + __pos;
00433 
00434           const size_type __how_much = __old_size - __pos - __len1;
00435           if (_M_disjunct(__s))
00436             {
00437               if (__how_much && __len1 != __len2)
00438                 this->_S_move(__p + __len2, __p + __len1, __how_much);
00439               if (__len2)
00440                 this->_S_copy(__p, __s, __len2);
00441             }
00442           else
00443             {
00444               // Work in-place.
00445               if (__len2 && __len2 <= __len1)
00446                 this->_S_move(__p, __s, __len2);
00447               if (__how_much && __len1 != __len2)
00448                 this->_S_move(__p + __len2, __p + __len1, __how_much);
00449               if (__len2 > __len1)
00450                 {
00451                   if (__s + __len2 <= __p + __len1)
00452                     this->_S_move(__p, __s, __len2);
00453                   else if (__s >= __p + __len1)
00454                     this->_S_copy(__p, __s + __len2 - __len1, __len2);
00455                   else
00456                     {
00457                       const size_type __nleft = (__p + __len1) - __s;
00458                       this->_S_move(__p, __s, __nleft);
00459                       this->_S_copy(__p + __nleft, __p + __len2,
00460                                     __len2 - __nleft);
00461                     }
00462                 }
00463             }
00464         }
00465       else
00466         this->_M_mutate(__pos, __len1, __s, __len2);
00467 
00468       this->_M_set_length(__new_size);
00469       return *this;
00470     }
00471 
00472   template<typename _CharT, typename _Traits, typename _Alloc>
00473     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00474     basic_string<_CharT, _Traits, _Alloc>::
00475     copy(_CharT* __s, size_type __n, size_type __pos) const
00476     {
00477       _M_check(__pos, "basic_string::copy");
00478       __n = _M_limit(__pos, __n);
00479       __glibcxx_requires_string_len(__s, __n);
00480       if (__n)
00481         _S_copy(__s, _M_data() + __pos, __n);
00482       // 21.3.5.7 par 3: do not append null.  (good.)
00483       return __n;
00484     }
00485 
00486 #else  // !_GLIBCXX_USE_CXX11_ABI
00487 
00488   template<typename _CharT, typename _Traits, typename _Alloc>
00489     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
00490     basic_string<_CharT, _Traits, _Alloc>::
00491     _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;
00492 
00493   template<typename _CharT, typename _Traits, typename _Alloc>
00494     const _CharT
00495     basic_string<_CharT, _Traits, _Alloc>::
00496     _Rep::_S_terminal = _CharT();
00497 
00498   template<typename _CharT, typename _Traits, typename _Alloc>
00499     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
00500     basic_string<_CharT, _Traits, _Alloc>::npos;
00501 
00502   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
00503   // at static init time (before static ctors are run).
00504   template<typename _CharT, typename _Traits, typename _Alloc>
00505     typename basic_string<_CharT, _Traits, _Alloc>::size_type
00506     basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[
00507     (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /
00508       sizeof(size_type)];
00509 
00510   // NB: This is the special case for Input Iterators, used in
00511   // istreambuf_iterators, etc.
00512   // Input Iterators have a cost structure very different from
00513   // pointers, calling for a different coding style.
00514   template<typename _CharT, typename _Traits, typename _Alloc>
00515     template<typename _InIterator>
00516       _CharT*
00517       basic_string<_CharT, _Traits, _Alloc>::
00518       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00519                    input_iterator_tag)
00520       {
00521 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
00522         if (__beg == __end && __a == _Alloc())
00523           return _S_empty_rep()._M_refdata();
00524 #endif
00525         // Avoid reallocation for common case.
00526         _CharT __buf[128];
00527         size_type __len = 0;
00528         while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
00529           {
00530             __buf[__len++] = *__beg;
00531             ++__beg;
00532           }
00533         _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
00534         _M_copy(__r->_M_refdata(), __buf, __len);
00535         __try
00536           {
00537             while (__beg != __end)
00538               {
00539                 if (__len == __r->_M_capacity)
00540                   {
00541                     // Allocate more space.
00542                     _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
00543                     _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
00544                     __r->_M_destroy(__a);
00545                     __r = __another;
00546                   }
00547                 __r->_M_refdata()[__len++] = *__beg;
00548                 ++__beg;
00549               }
00550           }
00551         __catch(...)
00552           {
00553             __r->_M_destroy(__a);
00554             __throw_exception_again;
00555           }
00556         __r->_M_set_length_and_sharable(__len);
00557         return __r->_M_refdata();
00558       }
00559 
00560   template<typename _CharT, typename _Traits, typename _Alloc>
00561     template <typename _InIterator>
00562       _CharT*
00563       basic_string<_CharT, _Traits, _Alloc>::
00564       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00565                    forward_iterator_tag)
00566       {
00567 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
00568         if (__beg == __end && __a == _Alloc())
00569           return _S_empty_rep()._M_refdata();
00570 #endif
00571         // NB: Not required, but considered best practice.
00572         if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
00573           __throw_logic_error(__N("basic_string::_S_construct null not valid"));
00574 
00575         const size_type __dnew = static_cast<size_type>(std::distance(__beg,
00576                                                                       __end));
00577         // Check for out_of_range and length_error exceptions.
00578         _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
00579         __try
00580           { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
00581         __catch(...)
00582           {
00583             __r->_M_destroy(__a);
00584             __throw_exception_again;
00585           }
00586         __r->_M_set_length_and_sharable(__dnew);
00587         return __r->_M_refdata();
00588       }
00589 
00590   template<typename _CharT, typename _Traits, typename _Alloc>
00591     _CharT*
00592     basic_string<_CharT, _Traits, _Alloc>::
00593     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
00594     {
00595 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
00596       if (__n == 0 && __a == _Alloc())
00597         return _S_empty_rep()._M_refdata();
00598 #endif
00599       // Check for out_of_range and length_error exceptions.
00600       _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
00601       if (__n)
00602         _M_assign(__r->_M_refdata(), __n, __c);
00603 
00604       __r->_M_set_length_and_sharable(__n);
00605       return __r->_M_refdata();
00606     }
00607 
00608   template<typename _CharT, typename _Traits, typename _Alloc>
00609     basic_string<_CharT, _Traits, _Alloc>::
00610     basic_string(const basic_string& __str)
00611     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
00612                                           __str.get_allocator()),
00613                   __str.get_allocator())
00614     { }
00615 
00616   template<typename _CharT, typename _Traits, typename _Alloc>
00617     basic_string<_CharT, _Traits, _Alloc>::
00618     basic_string(const _Alloc& __a)
00619     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
00620     { }
00621 
00622   template<typename _CharT, typename _Traits, typename _Alloc>
00623     basic_string<_CharT, _Traits, _Alloc>::
00624     basic_string(const basic_string& __str, size_type __pos, const _Alloc& __a)
00625     : _M_dataplus(_S_construct(__str._M_data()
00626                                + __str._M_check(__pos,
00627                                                 "basic_string::basic_string"),
00628                                __str._M_data() + __str._M_limit(__pos, npos)
00629                                + __pos, __a), __a)
00630     { }
00631 
00632   template<typename _CharT, typename _Traits, typename _Alloc>
00633     basic_string<_CharT, _Traits, _Alloc>::
00634     basic_string(const basic_string& __str, size_type __pos, size_type __n)
00635     : _M_dataplus(_S_construct(__str._M_data()
00636                                + __str._M_check(__pos,
00637                                                 "basic_string::basic_string"),
00638                                __str._M_data() + __str._M_limit(__pos, __n)
00639                                + __pos, _Alloc()), _Alloc())
00640     { }
00641 
00642   template<typename _CharT, typename _Traits, typename _Alloc>
00643     basic_string<_CharT, _Traits, _Alloc>::
00644     basic_string(const basic_string& __str, size_type __pos,
00645                  size_type __n, const _Alloc& __a)
00646     : _M_dataplus(_S_construct(__str._M_data()
00647                                + __str._M_check(__pos,
00648                                                 "basic_string::basic_string"),
00649                                __str._M_data() + __str._M_limit(__pos, __n)
00650                                + __pos, __a), __a)
00651     { }
00652 
00653   // TBD: DPG annotate
00654   template<typename _CharT, typename _Traits, typename _Alloc>
00655     basic_string<_CharT, _Traits, _Alloc>::
00656     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
00657     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
00658     { }
00659 
00660   // TBD: DPG annotate
00661   template<typename _CharT, typename _Traits, typename _Alloc>
00662     basic_string<_CharT, _Traits, _Alloc>::
00663     basic_string(const _CharT* __s, const _Alloc& __a)
00664     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
00665                                __s + npos, __a), __a)
00666     { }
00667 
00668   template<typename _CharT, typename _Traits, typename _Alloc>
00669     basic_string<_CharT, _Traits, _Alloc>::
00670     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
00671     : _M_dataplus(_S_construct(__n, __c, __a), __a)
00672     { }
00673 
00674   // TBD: DPG annotate
00675   template<typename _CharT, typename _Traits, typename _Alloc>
00676     template<typename _InputIterator>
00677     basic_string<_CharT, _Traits, _Alloc>::
00678     basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
00679     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
00680     { }
00681 
00682 #if __cplusplus >= 201103L
00683   template<typename _CharT, typename _Traits, typename _Alloc>
00684     basic_string<_CharT, _Traits, _Alloc>::
00685     basic_string(initializer_list<_CharT> __l, const _Alloc& __a)
00686     : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a)
00687     { }
00688 #endif
00689 
00690   template<typename _CharT, typename _Traits, typename _Alloc>
00691     basic_string<_CharT, _Traits, _Alloc>&
00692     basic_string<_CharT, _Traits, _Alloc>::
00693     assign(const basic_string& __str)
00694     {
00695       if (_M_rep() != __str._M_rep())
00696         {
00697           // XXX MT
00698           const allocator_type __a = this->get_allocator();
00699           _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
00700           _M_rep()->_M_dispose(__a);
00701           _M_data(__tmp);
00702         }
00703       return *this;
00704     }
00705 
00706   template<typename _CharT, typename _Traits, typename _Alloc>
00707     basic_string<_CharT, _Traits, _Alloc>&
00708     basic_string<_CharT, _Traits, _Alloc>::
00709     assign(const _CharT* __s, size_type __n)
00710     {
00711       __glibcxx_requires_string_len(__s, __n);
00712       _M_check_length(this->size(), __n, "basic_string::assign");
00713       if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
00714         return _M_replace_safe(size_type(0), this->size(), __s, __n);
00715       else
00716         {
00717           // Work in-place.
00718           const size_type __pos = __s - _M_data();
00719           if (__pos >= __n)
00720             _M_copy(_M_data(), __s, __n);
00721           else if (__pos)
00722             _M_move(_M_data(), __s, __n);
00723           _M_rep()->_M_set_length_and_sharable(__n);
00724           return *this;
00725         }
00726      }
00727 
00728   template<typename _CharT, typename _Traits, typename _Alloc>
00729     basic_string<_CharT, _Traits, _Alloc>&
00730     basic_string<_CharT, _Traits, _Alloc>::
00731     append(size_type __n, _CharT __c)
00732     {
00733       if (__n)
00734         {
00735           _M_check_length(size_type(0), __n, "basic_string::append");     
00736           const size_type __len = __n + this->size();
00737           if (__len > this->capacity() || _M_rep()->_M_is_shared())
00738             this->reserve(__len);
00739           _M_assign(_M_data() + this->size(), __n, __c);
00740           _M_rep()->_M_set_length_and_sharable(__len);
00741         }
00742       return *this;
00743     }
00744 
00745   template<typename _CharT, typename _Traits, typename _Alloc>
00746     basic_string<_CharT, _Traits, _Alloc>&
00747     basic_string<_CharT, _Traits, _Alloc>::
00748     append(const _CharT* __s, size_type __n)
00749     {
00750       __glibcxx_requires_string_len(__s, __n);
00751       if (__n)
00752         {
00753           _M_check_length(size_type(0), __n, "basic_string::append");
00754           const size_type __len = __n + this->size();
00755           if (__len > this->capacity() || _M_rep()->_M_is_shared())
00756             {
00757               if (_M_disjunct(__s))
00758                 this->reserve(__len);
00759               else
00760                 {
00761                   const size_type __off = __s - _M_data();
00762                   this->reserve(__len);
00763                   __s = _M_data() + __off;
00764                 }
00765             }
00766           _M_copy(_M_data() + this->size(), __s, __n);
00767           _M_rep()->_M_set_length_and_sharable(__len);
00768         }
00769       return *this;
00770     }
00771 
00772   template<typename _CharT, typename _Traits, typename _Alloc>
00773     basic_string<_CharT, _Traits, _Alloc>&
00774     basic_string<_CharT, _Traits, _Alloc>::
00775     append(const basic_string& __str)
00776     {
00777       const size_type __size = __str.size();
00778       if (__size)
00779         {
00780           const size_type __len = __size + this->size();
00781           if (__len > this->capacity() || _M_rep()->_M_is_shared())
00782             this->reserve(__len);
00783           _M_copy(_M_data() + this->size(), __str._M_data(), __size);
00784           _M_rep()->_M_set_length_and_sharable(__len);
00785         }
00786       return *this;
00787     }    
00788 
00789   template<typename _CharT, typename _Traits, typename _Alloc>
00790     basic_string<_CharT, _Traits, _Alloc>&
00791     basic_string<_CharT, _Traits, _Alloc>::
00792     append(const basic_string& __str, size_type __pos, size_type __n)
00793     {
00794       __str._M_check(__pos, "basic_string::append");
00795       __n = __str._M_limit(__pos, __n);
00796       if (__n)
00797         {
00798           const size_type __len = __n + this->size();
00799           if (__len > this->capacity() || _M_rep()->_M_is_shared())
00800             this->reserve(__len);
00801           _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n);
00802           _M_rep()->_M_set_length_and_sharable(__len);    
00803         }
00804       return *this;
00805     }
00806 
00807    template<typename _CharT, typename _Traits, typename _Alloc>
00808      basic_string<_CharT, _Traits, _Alloc>&
00809      basic_string<_CharT, _Traits, _Alloc>::
00810      insert(size_type __pos, const _CharT* __s, size_type __n)
00811      {
00812        __glibcxx_requires_string_len(__s, __n);
00813        _M_check(__pos, "basic_string::insert");
00814        _M_check_length(size_type(0), __n, "basic_string::insert");
00815        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
00816          return _M_replace_safe(__pos, size_type(0), __s, __n);
00817        else
00818          {
00819            // Work in-place.
00820            const size_type __off = __s - _M_data();
00821            _M_mutate(__pos, 0, __n);
00822            __s = _M_data() + __off;
00823            _CharT* __p = _M_data() + __pos;
00824            if (__s  + __n <= __p)
00825              _M_copy(__p, __s, __n);
00826            else if (__s >= __p)
00827              _M_copy(__p, __s + __n, __n);
00828            else
00829              {
00830                const size_type __nleft = __p - __s;
00831                _M_copy(__p, __s, __nleft);
00832                _M_copy(__p + __nleft, __p + __n, __n - __nleft);
00833              }
00834            return *this;
00835          }
00836      }
00837 
00838    template<typename _CharT, typename _Traits, typename _Alloc>
00839      typename basic_string<_CharT, _Traits, _Alloc>::iterator
00840      basic_string<_CharT, _Traits, _Alloc>::
00841      erase(iterator __first, iterator __last)
00842      {
00843        _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
00844                                 && __last <= _M_iend());
00845 
00846        // NB: This isn't just an optimization (bail out early when
00847        // there is nothing to do, really), it's also a correctness
00848        // issue vs MT, see libstdc++/40518.
00849        const size_type __size = __last - __first;
00850        if (__size)
00851          {
00852            const size_type __pos = __first - _M_ibegin();
00853            _M_mutate(__pos, __size, size_type(0));
00854            _M_rep()->_M_set_leaked();
00855            return iterator(_M_data() + __pos);
00856          }
00857        else
00858          return __first;
00859      }
00860 
00861    template<typename _CharT, typename _Traits, typename _Alloc>
00862      basic_string<_CharT, _Traits, _Alloc>&
00863      basic_string<_CharT, _Traits, _Alloc>::
00864      replace(size_type __pos, size_type __n1, const _CharT* __s,
00865              size_type __n2)
00866      {
00867        __glibcxx_requires_string_len(__s, __n2);
00868        _M_check(__pos, "basic_string::replace");
00869        __n1 = _M_limit(__pos, __n1);
00870        _M_check_length(__n1, __n2, "basic_string::replace");
00871        bool __left;
00872        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
00873          return _M_replace_safe(__pos, __n1, __s, __n2);
00874        else if ((__left = __s + __n2 <= _M_data() + __pos)
00875                 || _M_data() + __pos + __n1 <= __s)
00876          {
00877            // Work in-place: non-overlapping case.
00878            size_type __off = __s - _M_data();
00879            __left ? __off : (__off += __n2 - __n1);
00880            _M_mutate(__pos, __n1, __n2);
00881            _M_copy(_M_data() + __pos, _M_data() + __off, __n2);
00882            return *this;
00883          }
00884        else
00885          {
00886            // Todo: overlapping case.
00887            const basic_string __tmp(__s, __n2);
00888            return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
00889          }
00890      }
00891 
00892   template<typename _CharT, typename _Traits, typename _Alloc>
00893     void
00894     basic_string<_CharT, _Traits, _Alloc>::_Rep::
00895     _M_destroy(const _Alloc& __a) throw ()
00896     {
00897       const size_type __size = sizeof(_Rep_base) +
00898                                (this->_M_capacity + 1) * sizeof(_CharT);
00899       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
00900     }
00901 
00902   template<typename _CharT, typename _Traits, typename _Alloc>
00903     void
00904     basic_string<_CharT, _Traits, _Alloc>::
00905     _M_leak_hard()
00906     {
00907 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
00908       if (_M_rep() == &_S_empty_rep())
00909         return;
00910 #endif
00911       if (_M_rep()->_M_is_shared())
00912         _M_mutate(0, 0, 0);
00913       _M_rep()->_M_set_leaked();
00914     }
00915 
00916   template<typename _CharT, typename _Traits, typename _Alloc>
00917     void
00918     basic_string<_CharT, _Traits, _Alloc>::
00919     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
00920     {
00921       const size_type __old_size = this->size();
00922       const size_type __new_size = __old_size + __len2 - __len1;
00923       const size_type __how_much = __old_size - __pos - __len1;
00924 
00925       if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
00926         {
00927           // Must reallocate.
00928           const allocator_type __a = get_allocator();
00929           _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
00930 
00931           if (__pos)
00932             _M_copy(__r->_M_refdata(), _M_data(), __pos);
00933           if (__how_much)
00934             _M_copy(__r->_M_refdata() + __pos + __len2,
00935                     _M_data() + __pos + __len1, __how_much);
00936 
00937           _M_rep()->_M_dispose(__a);
00938           _M_data(__r->_M_refdata());
00939         }
00940       else if (__how_much && __len1 != __len2)
00941         {
00942           // Work in-place.
00943           _M_move(_M_data() + __pos + __len2,
00944                   _M_data() + __pos + __len1, __how_much);
00945         }
00946       _M_rep()->_M_set_length_and_sharable(__new_size);
00947     }
00948 
00949   template<typename _CharT, typename _Traits, typename _Alloc>
00950     void
00951     basic_string<_CharT, _Traits, _Alloc>::
00952     reserve(size_type __res)
00953     {
00954       if (__res != this->capacity() || _M_rep()->_M_is_shared())
00955         {
00956           // Make sure we don't shrink below the current size
00957           if (__res < this->size())
00958             __res = this->size();
00959           const allocator_type __a = get_allocator();
00960           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
00961           _M_rep()->_M_dispose(__a);
00962           _M_data(__tmp);
00963         }
00964     }
00965 
00966   template<typename _CharT, typename _Traits, typename _Alloc>
00967     void
00968     basic_string<_CharT, _Traits, _Alloc>::
00969     swap(basic_string& __s)
00970     _GLIBCXX_NOEXCEPT_IF(allocator_traits<_Alloc>::is_always_equal::value)
00971     {
00972       if (_M_rep()->_M_is_leaked())
00973         _M_rep()->_M_set_sharable();
00974       if (__s._M_rep()->_M_is_leaked())
00975         __s._M_rep()->_M_set_sharable();
00976       if (this->get_allocator() == __s.get_allocator())
00977         {
00978           _CharT* __tmp = _M_data();
00979           _M_data(__s._M_data());
00980           __s._M_data(__tmp);
00981         }
00982       // The code below can usually be optimized away.
00983       else
00984         {
00985           const basic_string __tmp1(_M_ibegin(), _M_iend(),
00986                                     __s.get_allocator());
00987           const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
00988                                     this->get_allocator());
00989           *this = __tmp2;
00990           __s = __tmp1;
00991         }
00992     }
00993 
00994   template<typename _CharT, typename _Traits, typename _Alloc>
00995     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
00996     basic_string<_CharT, _Traits, _Alloc>::_Rep::
00997     _S_create(size_type __capacity, size_type __old_capacity,
00998               const _Alloc& __alloc)
00999     {
01000       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01001       // 83.  String::npos vs. string::max_size()
01002       if (__capacity > _S_max_size)
01003         __throw_length_error(__N("basic_string::_S_create"));
01004 
01005       // The standard places no restriction on allocating more memory
01006       // than is strictly needed within this layer at the moment or as
01007       // requested by an explicit application call to reserve().
01008 
01009       // Many malloc implementations perform quite poorly when an
01010       // application attempts to allocate memory in a stepwise fashion
01011       // growing each allocation size by only 1 char.  Additionally,
01012       // it makes little sense to allocate less linear memory than the
01013       // natural blocking size of the malloc implementation.
01014       // Unfortunately, we would need a somewhat low-level calculation
01015       // with tuned parameters to get this perfect for any particular
01016       // malloc implementation.  Fortunately, generalizations about
01017       // common features seen among implementations seems to suffice.
01018 
01019       // __pagesize need not match the actual VM page size for good
01020       // results in practice, thus we pick a common value on the low
01021       // side.  __malloc_header_size is an estimate of the amount of
01022       // overhead per memory allocation (in practice seen N * sizeof
01023       // (void*) where N is 0, 2 or 4).  According to folklore,
01024       // picking this value on the high side is better than
01025       // low-balling it (especially when this algorithm is used with
01026       // malloc implementations that allocate memory blocks rounded up
01027       // to a size which is a power of 2).
01028       const size_type __pagesize = 4096;
01029       const size_type __malloc_header_size = 4 * sizeof(void*);
01030 
01031       // The below implements an exponential growth policy, necessary to
01032       // meet amortized linear time requirements of the library: see
01033       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
01034       // It's active for allocations requiring an amount of memory above
01035       // system pagesize. This is consistent with the requirements of the
01036       // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
01037       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
01038         __capacity = 2 * __old_capacity;
01039 
01040       // NB: Need an array of char_type[__capacity], plus a terminating
01041       // null char_type() element, plus enough for the _Rep data structure.
01042       // Whew. Seemingly so needy, yet so elemental.
01043       size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
01044 
01045       const size_type __adj_size = __size + __malloc_header_size;
01046       if (__adj_size > __pagesize && __capacity > __old_capacity)
01047         {
01048           const size_type __extra = __pagesize - __adj_size % __pagesize;
01049           __capacity += __extra / sizeof(_CharT);
01050           // Never allocate a string bigger than _S_max_size.
01051           if (__capacity > _S_max_size)
01052             __capacity = _S_max_size;
01053           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
01054         }
01055 
01056       // NB: Might throw, but no worries about a leak, mate: _Rep()
01057       // does not throw.
01058       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
01059       _Rep *__p = new (__place) _Rep;
01060       __p->_M_capacity = __capacity;
01061       // ABI compatibility - 3.4.x set in _S_create both
01062       // _M_refcount and _M_length.  All callers of _S_create
01063       // in basic_string.tcc then set just _M_length.
01064       // In 4.0.x and later both _M_refcount and _M_length
01065       // are initialized in the callers, unfortunately we can
01066       // have 3.4.x compiled code with _S_create callers inlined
01067       // calling 4.0.x+ _S_create.
01068       __p->_M_set_sharable();
01069       return __p;
01070     }
01071 
01072   template<typename _CharT, typename _Traits, typename _Alloc>
01073     _CharT*
01074     basic_string<_CharT, _Traits, _Alloc>::_Rep::
01075     _M_clone(const _Alloc& __alloc, size_type __res)
01076     {
01077       // Requested capacity of the clone.
01078       const size_type __requested_cap = this->_M_length + __res;
01079       _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
01080                                   __alloc);
01081       if (this->_M_length)
01082         _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
01083 
01084       __r->_M_set_length_and_sharable(this->_M_length);
01085       return __r->_M_refdata();
01086     }
01087 
01088   template<typename _CharT, typename _Traits, typename _Alloc>
01089     void
01090     basic_string<_CharT, _Traits, _Alloc>::
01091     resize(size_type __n, _CharT __c)
01092     {
01093       const size_type __size = this->size();
01094       _M_check_length(__size, __n, "basic_string::resize");
01095       if (__size < __n)
01096         this->append(__n - __size, __c);
01097       else if (__n < __size)
01098         this->erase(__n);
01099       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
01100     }
01101 
01102   template<typename _CharT, typename _Traits, typename _Alloc>
01103     template<typename _InputIterator>
01104       basic_string<_CharT, _Traits, _Alloc>&
01105       basic_string<_CharT, _Traits, _Alloc>::
01106       _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
01107                           _InputIterator __k2, __false_type)
01108       {
01109         const basic_string __s(__k1, __k2);
01110         const size_type __n1 = __i2 - __i1;
01111         _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
01112         return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
01113                                __s.size());
01114       }
01115 
01116   template<typename _CharT, typename _Traits, typename _Alloc>
01117     basic_string<_CharT, _Traits, _Alloc>&
01118     basic_string<_CharT, _Traits, _Alloc>::
01119     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
01120                    _CharT __c)
01121     {
01122       _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
01123       _M_mutate(__pos1, __n1, __n2);
01124       if (__n2)
01125         _M_assign(_M_data() + __pos1, __n2, __c);
01126       return *this;
01127     }
01128 
01129   template<typename _CharT, typename _Traits, typename _Alloc>
01130     basic_string<_CharT, _Traits, _Alloc>&
01131     basic_string<_CharT, _Traits, _Alloc>::
01132     _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
01133                     size_type __n2)
01134     {
01135       _M_mutate(__pos1, __n1, __n2);
01136       if (__n2)
01137         _M_copy(_M_data() + __pos1, __s, __n2);
01138       return *this;
01139     }
01140 
01141     template<typename _CharT, typename _Traits, typename _Alloc>
01142     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01143     basic_string<_CharT, _Traits, _Alloc>::
01144     copy(_CharT* __s, size_type __n, size_type __pos) const
01145     {
01146       _M_check(__pos, "basic_string::copy");
01147       __n = _M_limit(__pos, __n);
01148       __glibcxx_requires_string_len(__s, __n);
01149       if (__n)
01150         _M_copy(__s, _M_data() + __pos, __n);
01151       // 21.3.5.7 par 3: do not append null.  (good.)
01152       return __n;
01153     }
01154 #endif  // !_GLIBCXX_USE_CXX11_ABI
01155    
01156   template<typename _CharT, typename _Traits, typename _Alloc>
01157     basic_string<_CharT, _Traits, _Alloc>
01158     operator+(const _CharT* __lhs,
01159               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01160     {
01161       __glibcxx_requires_string(__lhs);
01162       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
01163       typedef typename __string_type::size_type   __size_type;
01164       const __size_type __len = _Traits::length(__lhs);
01165       __string_type __str;
01166       __str.reserve(__len + __rhs.size());
01167       __str.append(__lhs, __len);
01168       __str.append(__rhs);
01169       return __str;
01170     }
01171 
01172   template<typename _CharT, typename _Traits, typename _Alloc>
01173     basic_string<_CharT, _Traits, _Alloc>
01174     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01175     {
01176       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
01177       typedef typename __string_type::size_type   __size_type;
01178       __string_type __str;
01179       const __size_type __len = __rhs.size();
01180       __str.reserve(__len + 1);
01181       __str.append(__size_type(1), __lhs);
01182       __str.append(__rhs);
01183       return __str;
01184     }
01185 
01186   template<typename _CharT, typename _Traits, typename _Alloc>
01187     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01188     basic_string<_CharT, _Traits, _Alloc>::
01189     find(const _CharT* __s, size_type __pos, size_type __n) const
01190     _GLIBCXX_NOEXCEPT
01191     {
01192       __glibcxx_requires_string_len(__s, __n);
01193       const size_type __size = this->size();
01194 
01195       if (__n == 0)
01196         return __pos <= __size ? __pos : npos;
01197       if (__pos >= __size)
01198         return npos;
01199 
01200       const _CharT __elem0 = __s[0];
01201       const _CharT* const __data = data();
01202       const _CharT* __first = __data + __pos;
01203       const _CharT* const __last = __data + __size;
01204       size_type __len = __size - __pos;
01205 
01206       while (__len >= __n)
01207         {
01208           // Find the first occurrence of __elem0:
01209           __first = traits_type::find(__first, __len - __n + 1, __elem0);
01210           if (!__first)
01211             return npos;
01212           // Compare the full strings from the first occurrence of __elem0.
01213           // We already know that __first[0] == __s[0] but compare them again
01214           // anyway because __s is probably aligned, which helps memcmp.
01215           if (traits_type::compare(__first, __s, __n) == 0)
01216             return __first - __data;
01217           __len = __last - ++__first;
01218         }
01219       return npos;
01220     }
01221 
01222   template<typename _CharT, typename _Traits, typename _Alloc>
01223     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01224     basic_string<_CharT, _Traits, _Alloc>::
01225     find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
01226     {
01227       size_type __ret = npos;
01228       const size_type __size = this->size();
01229       if (__pos < __size)
01230         {
01231           const _CharT* __data = _M_data();
01232           const size_type __n = __size - __pos;
01233           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
01234           if (__p)
01235             __ret = __p - __data;
01236         }
01237       return __ret;
01238     }
01239 
01240   template<typename _CharT, typename _Traits, typename _Alloc>
01241     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01242     basic_string<_CharT, _Traits, _Alloc>::
01243     rfind(const _CharT* __s, size_type __pos, size_type __n) const
01244     _GLIBCXX_NOEXCEPT
01245     {
01246       __glibcxx_requires_string_len(__s, __n);
01247       const size_type __size = this->size();
01248       if (__n <= __size)
01249         {
01250           __pos = std::min(size_type(__size - __n), __pos);
01251           const _CharT* __data = _M_data();
01252           do
01253             {
01254               if (traits_type::compare(__data + __pos, __s, __n) == 0)
01255                 return __pos;
01256             }
01257           while (__pos-- > 0);
01258         }
01259       return npos;
01260     }
01261 
01262   template<typename _CharT, typename _Traits, typename _Alloc>
01263     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01264     basic_string<_CharT, _Traits, _Alloc>::
01265     rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
01266     {
01267       size_type __size = this->size();
01268       if (__size)
01269         {
01270           if (--__size > __pos)
01271             __size = __pos;
01272           for (++__size; __size-- > 0; )
01273             if (traits_type::eq(_M_data()[__size], __c))
01274               return __size;
01275         }
01276       return npos;
01277     }
01278 
01279   template<typename _CharT, typename _Traits, typename _Alloc>
01280     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01281     basic_string<_CharT, _Traits, _Alloc>::
01282     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
01283     _GLIBCXX_NOEXCEPT
01284     {
01285       __glibcxx_requires_string_len(__s, __n);
01286       for (; __n && __pos < this->size(); ++__pos)
01287         {
01288           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
01289           if (__p)
01290             return __pos;
01291         }
01292       return npos;
01293     }
01294 
01295   template<typename _CharT, typename _Traits, typename _Alloc>
01296     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01297     basic_string<_CharT, _Traits, _Alloc>::
01298     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
01299     _GLIBCXX_NOEXCEPT
01300     {
01301       __glibcxx_requires_string_len(__s, __n);
01302       size_type __size = this->size();
01303       if (__size && __n)
01304         {
01305           if (--__size > __pos)
01306             __size = __pos;
01307           do
01308             {
01309               if (traits_type::find(__s, __n, _M_data()[__size]))
01310                 return __size;
01311             }
01312           while (__size-- != 0);
01313         }
01314       return npos;
01315     }
01316 
01317   template<typename _CharT, typename _Traits, typename _Alloc>
01318     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01319     basic_string<_CharT, _Traits, _Alloc>::
01320     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
01321     _GLIBCXX_NOEXCEPT
01322     {
01323       __glibcxx_requires_string_len(__s, __n);
01324       for (; __pos < this->size(); ++__pos)
01325         if (!traits_type::find(__s, __n, _M_data()[__pos]))
01326           return __pos;
01327       return npos;
01328     }
01329 
01330   template<typename _CharT, typename _Traits, typename _Alloc>
01331     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01332     basic_string<_CharT, _Traits, _Alloc>::
01333     find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
01334     {
01335       for (; __pos < this->size(); ++__pos)
01336         if (!traits_type::eq(_M_data()[__pos], __c))
01337           return __pos;
01338       return npos;
01339     }
01340 
01341   template<typename _CharT, typename _Traits, typename _Alloc>
01342     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01343     basic_string<_CharT, _Traits, _Alloc>::
01344     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
01345     _GLIBCXX_NOEXCEPT
01346     {
01347       __glibcxx_requires_string_len(__s, __n);
01348       size_type __size = this->size();
01349       if (__size)
01350         {
01351           if (--__size > __pos)
01352             __size = __pos;
01353           do
01354             {
01355               if (!traits_type::find(__s, __n, _M_data()[__size]))
01356                 return __size;
01357             }
01358           while (__size--);
01359         }
01360       return npos;
01361     }
01362 
01363   template<typename _CharT, typename _Traits, typename _Alloc>
01364     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01365     basic_string<_CharT, _Traits, _Alloc>::
01366     find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
01367     {
01368       size_type __size = this->size();
01369       if (__size)
01370         {
01371           if (--__size > __pos)
01372             __size = __pos;
01373           do
01374             {
01375               if (!traits_type::eq(_M_data()[__size], __c))
01376                 return __size;
01377             }
01378           while (__size--);
01379         }
01380       return npos;
01381     }
01382 
01383   template<typename _CharT, typename _Traits, typename _Alloc>
01384     int
01385     basic_string<_CharT, _Traits, _Alloc>::
01386     compare(size_type __pos, size_type __n, const basic_string& __str) const
01387     {
01388       _M_check(__pos, "basic_string::compare");
01389       __n = _M_limit(__pos, __n);
01390       const size_type __osize = __str.size();
01391       const size_type __len = std::min(__n, __osize);
01392       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
01393       if (!__r)
01394         __r = _S_compare(__n, __osize);
01395       return __r;
01396     }
01397 
01398   template<typename _CharT, typename _Traits, typename _Alloc>
01399     int
01400     basic_string<_CharT, _Traits, _Alloc>::
01401     compare(size_type __pos1, size_type __n1, const basic_string& __str,
01402             size_type __pos2, size_type __n2) const
01403     {
01404       _M_check(__pos1, "basic_string::compare");
01405       __str._M_check(__pos2, "basic_string::compare");
01406       __n1 = _M_limit(__pos1, __n1);
01407       __n2 = __str._M_limit(__pos2, __n2);
01408       const size_type __len = std::min(__n1, __n2);
01409       int __r = traits_type::compare(_M_data() + __pos1,
01410                                      __str.data() + __pos2, __len);
01411       if (!__r)
01412         __r = _S_compare(__n1, __n2);
01413       return __r;
01414     }
01415 
01416   template<typename _CharT, typename _Traits, typename _Alloc>
01417     int
01418     basic_string<_CharT, _Traits, _Alloc>::
01419     compare(const _CharT* __s) const _GLIBCXX_NOEXCEPT
01420     {
01421       __glibcxx_requires_string(__s);
01422       const size_type __size = this->size();
01423       const size_type __osize = traits_type::length(__s);
01424       const size_type __len = std::min(__size, __osize);
01425       int __r = traits_type::compare(_M_data(), __s, __len);
01426       if (!__r)
01427         __r = _S_compare(__size, __osize);
01428       return __r;
01429     }
01430 
01431   template<typename _CharT, typename _Traits, typename _Alloc>
01432     int
01433     basic_string <_CharT, _Traits, _Alloc>::
01434     compare(size_type __pos, size_type __n1, const _CharT* __s) const
01435     {
01436       __glibcxx_requires_string(__s);
01437       _M_check(__pos, "basic_string::compare");
01438       __n1 = _M_limit(__pos, __n1);
01439       const size_type __osize = traits_type::length(__s);
01440       const size_type __len = std::min(__n1, __osize);
01441       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
01442       if (!__r)
01443         __r = _S_compare(__n1, __osize);
01444       return __r;
01445     }
01446 
01447   template<typename _CharT, typename _Traits, typename _Alloc>
01448     int
01449     basic_string <_CharT, _Traits, _Alloc>::
01450     compare(size_type __pos, size_type __n1, const _CharT* __s,
01451             size_type __n2) const
01452     {
01453       __glibcxx_requires_string_len(__s, __n2);
01454       _M_check(__pos, "basic_string::compare");
01455       __n1 = _M_limit(__pos, __n1);
01456       const size_type __len = std::min(__n1, __n2);
01457       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
01458       if (!__r)
01459         __r = _S_compare(__n1, __n2);
01460       return __r;
01461     }
01462 
01463   // 21.3.7.9 basic_string::getline and operators
01464   template<typename _CharT, typename _Traits, typename _Alloc>
01465     basic_istream<_CharT, _Traits>&
01466     operator>>(basic_istream<_CharT, _Traits>& __in,
01467                basic_string<_CharT, _Traits, _Alloc>& __str)
01468     {
01469       typedef basic_istream<_CharT, _Traits>            __istream_type;
01470       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
01471       typedef typename __istream_type::ios_base         __ios_base;
01472       typedef typename __istream_type::int_type         __int_type;
01473       typedef typename __string_type::size_type         __size_type;
01474       typedef ctype<_CharT>                             __ctype_type;
01475       typedef typename __ctype_type::ctype_base         __ctype_base;
01476 
01477       __size_type __extracted = 0;
01478       typename __ios_base::iostate __err = __ios_base::goodbit;
01479       typename __istream_type::sentry __cerb(__in, false);
01480       if (__cerb)
01481         {
01482           __try
01483             {
01484               // Avoid reallocation for common case.
01485               __str.erase();
01486               _CharT __buf[128];
01487               __size_type __len = 0;          
01488               const streamsize __w = __in.width();
01489               const __size_type __n = __w > 0 ? static_cast<__size_type>(__w)
01490                                               : __str.max_size();
01491               const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc());
01492               const __int_type __eof = _Traits::eof();
01493               __int_type __c = __in.rdbuf()->sgetc();
01494 
01495               while (__extracted < __n
01496                      && !_Traits::eq_int_type(__c, __eof)
01497                      && !__ct.is(__ctype_base::space,
01498                                  _Traits::to_char_type(__c)))
01499                 {
01500                   if (__len == sizeof(__buf) / sizeof(_CharT))
01501                     {
01502                       __str.append(__buf, sizeof(__buf) / sizeof(_CharT));
01503                       __len = 0;
01504                     }
01505                   __buf[__len++] = _Traits::to_char_type(__c);
01506                   ++__extracted;
01507                   __c = __in.rdbuf()->snextc();
01508                 }
01509               __str.append(__buf, __len);
01510 
01511               if (_Traits::eq_int_type(__c, __eof))
01512                 __err |= __ios_base::eofbit;
01513               __in.width(0);
01514             }
01515           __catch(__cxxabiv1::__forced_unwind&)
01516             {
01517               __in._M_setstate(__ios_base::badbit);
01518               __throw_exception_again;
01519             }
01520           __catch(...)
01521             {
01522               // _GLIBCXX_RESOLVE_LIB_DEFECTS
01523               // 91. Description of operator>> and getline() for string<>
01524               // might cause endless loop
01525               __in._M_setstate(__ios_base::badbit);
01526             }
01527         }
01528       // 211.  operator>>(istream&, string&) doesn't set failbit
01529       if (!__extracted)
01530         __err |= __ios_base::failbit;
01531       if (__err)
01532         __in.setstate(__err);
01533       return __in;
01534     }
01535 
01536   template<typename _CharT, typename _Traits, typename _Alloc>
01537     basic_istream<_CharT, _Traits>&
01538     getline(basic_istream<_CharT, _Traits>& __in,
01539             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
01540     {
01541       typedef basic_istream<_CharT, _Traits>            __istream_type;
01542       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
01543       typedef typename __istream_type::ios_base         __ios_base;
01544       typedef typename __istream_type::int_type         __int_type;
01545       typedef typename __string_type::size_type         __size_type;
01546 
01547       __size_type __extracted = 0;
01548       const __size_type __n = __str.max_size();
01549       typename __ios_base::iostate __err = __ios_base::goodbit;
01550       typename __istream_type::sentry __cerb(__in, true);
01551       if (__cerb)
01552         {
01553           __try
01554             {
01555               __str.erase();
01556               const __int_type __idelim = _Traits::to_int_type(__delim);
01557               const __int_type __eof = _Traits::eof();
01558               __int_type __c = __in.rdbuf()->sgetc();
01559 
01560               while (__extracted < __n
01561                      && !_Traits::eq_int_type(__c, __eof)
01562                      && !_Traits::eq_int_type(__c, __idelim))
01563                 {
01564                   __str += _Traits::to_char_type(__c);
01565                   ++__extracted;
01566                   __c = __in.rdbuf()->snextc();
01567                 }
01568 
01569               if (_Traits::eq_int_type(__c, __eof))
01570                 __err |= __ios_base::eofbit;
01571               else if (_Traits::eq_int_type(__c, __idelim))
01572                 {
01573                   ++__extracted;                  
01574                   __in.rdbuf()->sbumpc();
01575                 }
01576               else
01577                 __err |= __ios_base::failbit;
01578             }
01579           __catch(__cxxabiv1::__forced_unwind&)
01580             {
01581               __in._M_setstate(__ios_base::badbit);
01582               __throw_exception_again;
01583             }
01584           __catch(...)
01585             {
01586               // _GLIBCXX_RESOLVE_LIB_DEFECTS
01587               // 91. Description of operator>> and getline() for string<>
01588               // might cause endless loop
01589               __in._M_setstate(__ios_base::badbit);
01590             }
01591         }
01592       if (!__extracted)
01593         __err |= __ios_base::failbit;
01594       if (__err)
01595         __in.setstate(__err);
01596       return __in;
01597     }
01598 
01599   // Inhibit implicit instantiations for required instantiations,
01600   // which are defined via explicit instantiations elsewhere.
01601 #if _GLIBCXX_EXTERN_TEMPLATE
01602   // The explicit instantiations definitions in src/c++11/string-inst.cc
01603   // are compiled as C++14, so the new C++17 members aren't instantiated.
01604   // Until those definitions are compiled as C++17 suppress the declaration,
01605   // so C++17 code will implicitly instantiate std::string and std::wstring
01606   // as needed.
01607 # if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0
01608   extern template class basic_string<char>;
01609 # elif ! _GLIBCXX_USE_CXX11_ABI
01610   // Still need to prevent implicit instantiation of the COW empty rep,
01611   // to ensure the definition in libstdc++.so is unique (PR 86138).
01612   extern template basic_string<char>::size_type
01613     basic_string<char>::_Rep::_S_empty_rep_storage[];
01614 # endif
01615 
01616   extern template
01617     basic_istream<char>&
01618     operator>>(basic_istream<char>&, string&);
01619   extern template
01620     basic_ostream<char>&
01621     operator<<(basic_ostream<char>&, const string&);
01622   extern template
01623     basic_istream<char>&
01624     getline(basic_istream<char>&, string&, char);
01625   extern template
01626     basic_istream<char>&
01627     getline(basic_istream<char>&, string&);
01628 
01629 #ifdef _GLIBCXX_USE_WCHAR_T
01630 # if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0
01631   extern template class basic_string<wchar_t>;
01632 # elif ! _GLIBCXX_USE_CXX11_ABI
01633   extern template basic_string<wchar_t>::size_type
01634     basic_string<wchar_t>::_Rep::_S_empty_rep_storage[];
01635 # endif
01636 
01637   extern template
01638     basic_istream<wchar_t>&
01639     operator>>(basic_istream<wchar_t>&, wstring&);
01640   extern template
01641     basic_ostream<wchar_t>&
01642     operator<<(basic_ostream<wchar_t>&, const wstring&);
01643   extern template
01644     basic_istream<wchar_t>&
01645     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
01646   extern template
01647     basic_istream<wchar_t>&
01648     getline(basic_istream<wchar_t>&, wstring&);
01649 #endif // _GLIBCXX_USE_WCHAR_T
01650 #endif // _GLIBCXX_EXTERN_TEMPLATE
01651 
01652 _GLIBCXX_END_NAMESPACE_VERSION
01653 } // namespace std
01654 
01655 #endif