libstdc++
basic_string.tcc
Go to the documentation of this file.
00001 // Components for manipulating sequences of characters -*- C++ -*-
00002 
00003 // Copyright (C) 1997-2015 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_erase(__n, __size - __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, size_type __n)
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, __n)
00629                                + __pos, _Alloc()), _Alloc())
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,
00635                  size_type __n, const _Alloc& __a)
00636     : _M_dataplus(_S_construct(__str._M_data()
00637                                + __str._M_check(__pos,
00638                                                 "basic_string::basic_string"),
00639                                __str._M_data() + __str._M_limit(__pos, __n)
00640                                + __pos, __a), __a)
00641     { }
00642 
00643   // TBD: DPG annotate
00644   template<typename _CharT, typename _Traits, typename _Alloc>
00645     basic_string<_CharT, _Traits, _Alloc>::
00646     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
00647     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
00648     { }
00649 
00650   // TBD: DPG annotate
00651   template<typename _CharT, typename _Traits, typename _Alloc>
00652     basic_string<_CharT, _Traits, _Alloc>::
00653     basic_string(const _CharT* __s, const _Alloc& __a)
00654     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
00655                                __s + npos, __a), __a)
00656     { }
00657 
00658   template<typename _CharT, typename _Traits, typename _Alloc>
00659     basic_string<_CharT, _Traits, _Alloc>::
00660     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
00661     : _M_dataplus(_S_construct(__n, __c, __a), __a)
00662     { }
00663 
00664   // TBD: DPG annotate
00665   template<typename _CharT, typename _Traits, typename _Alloc>
00666     template<typename _InputIterator>
00667     basic_string<_CharT, _Traits, _Alloc>::
00668     basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
00669     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
00670     { }
00671 
00672 #if __cplusplus >= 201103L
00673   template<typename _CharT, typename _Traits, typename _Alloc>
00674     basic_string<_CharT, _Traits, _Alloc>::
00675     basic_string(initializer_list<_CharT> __l, const _Alloc& __a)
00676     : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a)
00677     { }
00678 #endif
00679 
00680   template<typename _CharT, typename _Traits, typename _Alloc>
00681     basic_string<_CharT, _Traits, _Alloc>&
00682     basic_string<_CharT, _Traits, _Alloc>::
00683     assign(const basic_string& __str)
00684     {
00685       if (_M_rep() != __str._M_rep())
00686         {
00687           // XXX MT
00688           const allocator_type __a = this->get_allocator();
00689           _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
00690           _M_rep()->_M_dispose(__a);
00691           _M_data(__tmp);
00692         }
00693       return *this;
00694     }
00695 
00696   template<typename _CharT, typename _Traits, typename _Alloc>
00697     basic_string<_CharT, _Traits, _Alloc>&
00698     basic_string<_CharT, _Traits, _Alloc>::
00699     assign(const _CharT* __s, size_type __n)
00700     {
00701       __glibcxx_requires_string_len(__s, __n);
00702       _M_check_length(this->size(), __n, "basic_string::assign");
00703       if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
00704         return _M_replace_safe(size_type(0), this->size(), __s, __n);
00705       else
00706         {
00707           // Work in-place.
00708           const size_type __pos = __s - _M_data();
00709           if (__pos >= __n)
00710             _M_copy(_M_data(), __s, __n);
00711           else if (__pos)
00712             _M_move(_M_data(), __s, __n);
00713           _M_rep()->_M_set_length_and_sharable(__n);
00714           return *this;
00715         }
00716      }
00717 
00718   template<typename _CharT, typename _Traits, typename _Alloc>
00719     basic_string<_CharT, _Traits, _Alloc>&
00720     basic_string<_CharT, _Traits, _Alloc>::
00721     append(size_type __n, _CharT __c)
00722     {
00723       if (__n)
00724         {
00725           _M_check_length(size_type(0), __n, "basic_string::append");     
00726           const size_type __len = __n + this->size();
00727           if (__len > this->capacity() || _M_rep()->_M_is_shared())
00728             this->reserve(__len);
00729           _M_assign(_M_data() + this->size(), __n, __c);
00730           _M_rep()->_M_set_length_and_sharable(__len);
00731         }
00732       return *this;
00733     }
00734 
00735   template<typename _CharT, typename _Traits, typename _Alloc>
00736     basic_string<_CharT, _Traits, _Alloc>&
00737     basic_string<_CharT, _Traits, _Alloc>::
00738     append(const _CharT* __s, size_type __n)
00739     {
00740       __glibcxx_requires_string_len(__s, __n);
00741       if (__n)
00742         {
00743           _M_check_length(size_type(0), __n, "basic_string::append");
00744           const size_type __len = __n + this->size();
00745           if (__len > this->capacity() || _M_rep()->_M_is_shared())
00746             {
00747               if (_M_disjunct(__s))
00748                 this->reserve(__len);
00749               else
00750                 {
00751                   const size_type __off = __s - _M_data();
00752                   this->reserve(__len);
00753                   __s = _M_data() + __off;
00754                 }
00755             }
00756           _M_copy(_M_data() + this->size(), __s, __n);
00757           _M_rep()->_M_set_length_and_sharable(__len);
00758         }
00759       return *this;
00760     }
00761 
00762   template<typename _CharT, typename _Traits, typename _Alloc>
00763     basic_string<_CharT, _Traits, _Alloc>&
00764     basic_string<_CharT, _Traits, _Alloc>::
00765     append(const basic_string& __str)
00766     {
00767       const size_type __size = __str.size();
00768       if (__size)
00769         {
00770           const size_type __len = __size + this->size();
00771           if (__len > this->capacity() || _M_rep()->_M_is_shared())
00772             this->reserve(__len);
00773           _M_copy(_M_data() + this->size(), __str._M_data(), __size);
00774           _M_rep()->_M_set_length_and_sharable(__len);
00775         }
00776       return *this;
00777     }    
00778 
00779   template<typename _CharT, typename _Traits, typename _Alloc>
00780     basic_string<_CharT, _Traits, _Alloc>&
00781     basic_string<_CharT, _Traits, _Alloc>::
00782     append(const basic_string& __str, size_type __pos, size_type __n)
00783     {
00784       __str._M_check(__pos, "basic_string::append");
00785       __n = __str._M_limit(__pos, __n);
00786       if (__n)
00787         {
00788           const size_type __len = __n + this->size();
00789           if (__len > this->capacity() || _M_rep()->_M_is_shared())
00790             this->reserve(__len);
00791           _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n);
00792           _M_rep()->_M_set_length_and_sharable(__len);    
00793         }
00794       return *this;
00795     }
00796 
00797    template<typename _CharT, typename _Traits, typename _Alloc>
00798      basic_string<_CharT, _Traits, _Alloc>&
00799      basic_string<_CharT, _Traits, _Alloc>::
00800      insert(size_type __pos, const _CharT* __s, size_type __n)
00801      {
00802        __glibcxx_requires_string_len(__s, __n);
00803        _M_check(__pos, "basic_string::insert");
00804        _M_check_length(size_type(0), __n, "basic_string::insert");
00805        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
00806          return _M_replace_safe(__pos, size_type(0), __s, __n);
00807        else
00808          {
00809            // Work in-place.
00810            const size_type __off = __s - _M_data();
00811            _M_mutate(__pos, 0, __n);
00812            __s = _M_data() + __off;
00813            _CharT* __p = _M_data() + __pos;
00814            if (__s  + __n <= __p)
00815              _M_copy(__p, __s, __n);
00816            else if (__s >= __p)
00817              _M_copy(__p, __s + __n, __n);
00818            else
00819              {
00820                const size_type __nleft = __p - __s;
00821                _M_copy(__p, __s, __nleft);
00822                _M_copy(__p + __nleft, __p + __n, __n - __nleft);
00823              }
00824            return *this;
00825          }
00826      }
00827 
00828    template<typename _CharT, typename _Traits, typename _Alloc>
00829      typename basic_string<_CharT, _Traits, _Alloc>::iterator
00830      basic_string<_CharT, _Traits, _Alloc>::
00831      erase(iterator __first, iterator __last)
00832      {
00833        _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
00834                                 && __last <= _M_iend());
00835 
00836        // NB: This isn't just an optimization (bail out early when
00837        // there is nothing to do, really), it's also a correctness
00838        // issue vs MT, see libstdc++/40518.
00839        const size_type __size = __last - __first;
00840        if (__size)
00841          {
00842            const size_type __pos = __first - _M_ibegin();
00843            _M_mutate(__pos, __size, size_type(0));
00844            _M_rep()->_M_set_leaked();
00845            return iterator(_M_data() + __pos);
00846          }
00847        else
00848          return __first;
00849      }
00850 
00851    template<typename _CharT, typename _Traits, typename _Alloc>
00852      basic_string<_CharT, _Traits, _Alloc>&
00853      basic_string<_CharT, _Traits, _Alloc>::
00854      replace(size_type __pos, size_type __n1, const _CharT* __s,
00855              size_type __n2)
00856      {
00857        __glibcxx_requires_string_len(__s, __n2);
00858        _M_check(__pos, "basic_string::replace");
00859        __n1 = _M_limit(__pos, __n1);
00860        _M_check_length(__n1, __n2, "basic_string::replace");
00861        bool __left;
00862        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
00863          return _M_replace_safe(__pos, __n1, __s, __n2);
00864        else if ((__left = __s + __n2 <= _M_data() + __pos)
00865                 || _M_data() + __pos + __n1 <= __s)
00866          {
00867            // Work in-place: non-overlapping case.
00868            size_type __off = __s - _M_data();
00869            __left ? __off : (__off += __n2 - __n1);
00870            _M_mutate(__pos, __n1, __n2);
00871            _M_copy(_M_data() + __pos, _M_data() + __off, __n2);
00872            return *this;
00873          }
00874        else
00875          {
00876            // Todo: overlapping case.
00877            const basic_string __tmp(__s, __n2);
00878            return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
00879          }
00880      }
00881 
00882   template<typename _CharT, typename _Traits, typename _Alloc>
00883     void
00884     basic_string<_CharT, _Traits, _Alloc>::_Rep::
00885     _M_destroy(const _Alloc& __a) throw ()
00886     {
00887       const size_type __size = sizeof(_Rep_base) +
00888                                (this->_M_capacity + 1) * sizeof(_CharT);
00889       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
00890     }
00891 
00892   template<typename _CharT, typename _Traits, typename _Alloc>
00893     void
00894     basic_string<_CharT, _Traits, _Alloc>::
00895     _M_leak_hard()
00896     {
00897 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
00898       if (_M_rep() == &_S_empty_rep())
00899         return;
00900 #endif
00901       if (_M_rep()->_M_is_shared())
00902         _M_mutate(0, 0, 0);
00903       _M_rep()->_M_set_leaked();
00904     }
00905 
00906   template<typename _CharT, typename _Traits, typename _Alloc>
00907     void
00908     basic_string<_CharT, _Traits, _Alloc>::
00909     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
00910     {
00911       const size_type __old_size = this->size();
00912       const size_type __new_size = __old_size + __len2 - __len1;
00913       const size_type __how_much = __old_size - __pos - __len1;
00914 
00915       if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
00916         {
00917           // Must reallocate.
00918           const allocator_type __a = get_allocator();
00919           _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
00920 
00921           if (__pos)
00922             _M_copy(__r->_M_refdata(), _M_data(), __pos);
00923           if (__how_much)
00924             _M_copy(__r->_M_refdata() + __pos + __len2,
00925                     _M_data() + __pos + __len1, __how_much);
00926 
00927           _M_rep()->_M_dispose(__a);
00928           _M_data(__r->_M_refdata());
00929         }
00930       else if (__how_much && __len1 != __len2)
00931         {
00932           // Work in-place.
00933           _M_move(_M_data() + __pos + __len2,
00934                   _M_data() + __pos + __len1, __how_much);
00935         }
00936       _M_rep()->_M_set_length_and_sharable(__new_size);
00937     }
00938 
00939   template<typename _CharT, typename _Traits, typename _Alloc>
00940     void
00941     basic_string<_CharT, _Traits, _Alloc>::
00942     reserve(size_type __res)
00943     {
00944       if (__res != this->capacity() || _M_rep()->_M_is_shared())
00945         {
00946           // Make sure we don't shrink below the current size
00947           if (__res < this->size())
00948             __res = this->size();
00949           const allocator_type __a = get_allocator();
00950           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
00951           _M_rep()->_M_dispose(__a);
00952           _M_data(__tmp);
00953         }
00954     }
00955 
00956   template<typename _CharT, typename _Traits, typename _Alloc>
00957     void
00958     basic_string<_CharT, _Traits, _Alloc>::
00959     swap(basic_string& __s)
00960     {
00961       if (_M_rep()->_M_is_leaked())
00962         _M_rep()->_M_set_sharable();
00963       if (__s._M_rep()->_M_is_leaked())
00964         __s._M_rep()->_M_set_sharable();
00965       if (this->get_allocator() == __s.get_allocator())
00966         {
00967           _CharT* __tmp = _M_data();
00968           _M_data(__s._M_data());
00969           __s._M_data(__tmp);
00970         }
00971       // The code below can usually be optimized away.
00972       else
00973         {
00974           const basic_string __tmp1(_M_ibegin(), _M_iend(),
00975                                     __s.get_allocator());
00976           const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
00977                                     this->get_allocator());
00978           *this = __tmp2;
00979           __s = __tmp1;
00980         }
00981     }
00982 
00983   template<typename _CharT, typename _Traits, typename _Alloc>
00984     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
00985     basic_string<_CharT, _Traits, _Alloc>::_Rep::
00986     _S_create(size_type __capacity, size_type __old_capacity,
00987               const _Alloc& __alloc)
00988     {
00989       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00990       // 83.  String::npos vs. string::max_size()
00991       if (__capacity > _S_max_size)
00992         __throw_length_error(__N("basic_string::_S_create"));
00993 
00994       // The standard places no restriction on allocating more memory
00995       // than is strictly needed within this layer at the moment or as
00996       // requested by an explicit application call to reserve().
00997 
00998       // Many malloc implementations perform quite poorly when an
00999       // application attempts to allocate memory in a stepwise fashion
01000       // growing each allocation size by only 1 char.  Additionally,
01001       // it makes little sense to allocate less linear memory than the
01002       // natural blocking size of the malloc implementation.
01003       // Unfortunately, we would need a somewhat low-level calculation
01004       // with tuned parameters to get this perfect for any particular
01005       // malloc implementation.  Fortunately, generalizations about
01006       // common features seen among implementations seems to suffice.
01007 
01008       // __pagesize need not match the actual VM page size for good
01009       // results in practice, thus we pick a common value on the low
01010       // side.  __malloc_header_size is an estimate of the amount of
01011       // overhead per memory allocation (in practice seen N * sizeof
01012       // (void*) where N is 0, 2 or 4).  According to folklore,
01013       // picking this value on the high side is better than
01014       // low-balling it (especially when this algorithm is used with
01015       // malloc implementations that allocate memory blocks rounded up
01016       // to a size which is a power of 2).
01017       const size_type __pagesize = 4096;
01018       const size_type __malloc_header_size = 4 * sizeof(void*);
01019 
01020       // The below implements an exponential growth policy, necessary to
01021       // meet amortized linear time requirements of the library: see
01022       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
01023       // It's active for allocations requiring an amount of memory above
01024       // system pagesize. This is consistent with the requirements of the
01025       // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
01026       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
01027         __capacity = 2 * __old_capacity;
01028 
01029       // NB: Need an array of char_type[__capacity], plus a terminating
01030       // null char_type() element, plus enough for the _Rep data structure.
01031       // Whew. Seemingly so needy, yet so elemental.
01032       size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
01033 
01034       const size_type __adj_size = __size + __malloc_header_size;
01035       if (__adj_size > __pagesize && __capacity > __old_capacity)
01036         {
01037           const size_type __extra = __pagesize - __adj_size % __pagesize;
01038           __capacity += __extra / sizeof(_CharT);
01039           // Never allocate a string bigger than _S_max_size.
01040           if (__capacity > _S_max_size)
01041             __capacity = _S_max_size;
01042           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
01043         }
01044 
01045       // NB: Might throw, but no worries about a leak, mate: _Rep()
01046       // does not throw.
01047       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
01048       _Rep *__p = new (__place) _Rep;
01049       __p->_M_capacity = __capacity;
01050       // ABI compatibility - 3.4.x set in _S_create both
01051       // _M_refcount and _M_length.  All callers of _S_create
01052       // in basic_string.tcc then set just _M_length.
01053       // In 4.0.x and later both _M_refcount and _M_length
01054       // are initialized in the callers, unfortunately we can
01055       // have 3.4.x compiled code with _S_create callers inlined
01056       // calling 4.0.x+ _S_create.
01057       __p->_M_set_sharable();
01058       return __p;
01059     }
01060 
01061   template<typename _CharT, typename _Traits, typename _Alloc>
01062     _CharT*
01063     basic_string<_CharT, _Traits, _Alloc>::_Rep::
01064     _M_clone(const _Alloc& __alloc, size_type __res)
01065     {
01066       // Requested capacity of the clone.
01067       const size_type __requested_cap = this->_M_length + __res;
01068       _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
01069                                   __alloc);
01070       if (this->_M_length)
01071         _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
01072 
01073       __r->_M_set_length_and_sharable(this->_M_length);
01074       return __r->_M_refdata();
01075     }
01076 
01077   template<typename _CharT, typename _Traits, typename _Alloc>
01078     void
01079     basic_string<_CharT, _Traits, _Alloc>::
01080     resize(size_type __n, _CharT __c)
01081     {
01082       const size_type __size = this->size();
01083       _M_check_length(__size, __n, "basic_string::resize");
01084       if (__size < __n)
01085         this->append(__n - __size, __c);
01086       else if (__n < __size)
01087         this->erase(__n);
01088       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
01089     }
01090 
01091   template<typename _CharT, typename _Traits, typename _Alloc>
01092     template<typename _InputIterator>
01093       basic_string<_CharT, _Traits, _Alloc>&
01094       basic_string<_CharT, _Traits, _Alloc>::
01095       _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
01096                           _InputIterator __k2, __false_type)
01097       {
01098         const basic_string __s(__k1, __k2);
01099         const size_type __n1 = __i2 - __i1;
01100         _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
01101         return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
01102                                __s.size());
01103       }
01104 
01105   template<typename _CharT, typename _Traits, typename _Alloc>
01106     basic_string<_CharT, _Traits, _Alloc>&
01107     basic_string<_CharT, _Traits, _Alloc>::
01108     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
01109                    _CharT __c)
01110     {
01111       _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
01112       _M_mutate(__pos1, __n1, __n2);
01113       if (__n2)
01114         _M_assign(_M_data() + __pos1, __n2, __c);
01115       return *this;
01116     }
01117 
01118   template<typename _CharT, typename _Traits, typename _Alloc>
01119     basic_string<_CharT, _Traits, _Alloc>&
01120     basic_string<_CharT, _Traits, _Alloc>::
01121     _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
01122                     size_type __n2)
01123     {
01124       _M_mutate(__pos1, __n1, __n2);
01125       if (__n2)
01126         _M_copy(_M_data() + __pos1, __s, __n2);
01127       return *this;
01128     }
01129 
01130     template<typename _CharT, typename _Traits, typename _Alloc>
01131     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01132     basic_string<_CharT, _Traits, _Alloc>::
01133     copy(_CharT* __s, size_type __n, size_type __pos) const
01134     {
01135       _M_check(__pos, "basic_string::copy");
01136       __n = _M_limit(__pos, __n);
01137       __glibcxx_requires_string_len(__s, __n);
01138       if (__n)
01139         _M_copy(__s, _M_data() + __pos, __n);
01140       // 21.3.5.7 par 3: do not append null.  (good.)
01141       return __n;
01142     }
01143 #endif  // !_GLIBCXX_USE_CXX11_ABI
01144    
01145   template<typename _CharT, typename _Traits, typename _Alloc>
01146     basic_string<_CharT, _Traits, _Alloc>
01147     operator+(const _CharT* __lhs,
01148               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01149     {
01150       __glibcxx_requires_string(__lhs);
01151       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
01152       typedef typename __string_type::size_type   __size_type;
01153       const __size_type __len = _Traits::length(__lhs);
01154       __string_type __str;
01155       __str.reserve(__len + __rhs.size());
01156       __str.append(__lhs, __len);
01157       __str.append(__rhs);
01158       return __str;
01159     }
01160 
01161   template<typename _CharT, typename _Traits, typename _Alloc>
01162     basic_string<_CharT, _Traits, _Alloc>
01163     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
01164     {
01165       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
01166       typedef typename __string_type::size_type   __size_type;
01167       __string_type __str;
01168       const __size_type __len = __rhs.size();
01169       __str.reserve(__len + 1);
01170       __str.append(__size_type(1), __lhs);
01171       __str.append(__rhs);
01172       return __str;
01173     }
01174 
01175   template<typename _CharT, typename _Traits, typename _Alloc>
01176     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01177     basic_string<_CharT, _Traits, _Alloc>::
01178     find(const _CharT* __s, size_type __pos, size_type __n) const
01179     {
01180       __glibcxx_requires_string_len(__s, __n);
01181       const size_type __size = this->size();
01182       const _CharT* __data = _M_data();
01183 
01184       if (__n == 0)
01185         return __pos <= __size ? __pos : npos;
01186 
01187       if (__n <= __size)
01188         {
01189           for (; __pos <= __size - __n; ++__pos)
01190             if (traits_type::eq(__data[__pos], __s[0])
01191                 && traits_type::compare(__data + __pos + 1,
01192                                         __s + 1, __n - 1) == 0)
01193               return __pos;
01194         }
01195       return npos;
01196     }
01197 
01198   template<typename _CharT, typename _Traits, typename _Alloc>
01199     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01200     basic_string<_CharT, _Traits, _Alloc>::
01201     find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
01202     {
01203       size_type __ret = npos;
01204       const size_type __size = this->size();
01205       if (__pos < __size)
01206         {
01207           const _CharT* __data = _M_data();
01208           const size_type __n = __size - __pos;
01209           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
01210           if (__p)
01211             __ret = __p - __data;
01212         }
01213       return __ret;
01214     }
01215 
01216   template<typename _CharT, typename _Traits, typename _Alloc>
01217     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01218     basic_string<_CharT, _Traits, _Alloc>::
01219     rfind(const _CharT* __s, size_type __pos, size_type __n) const
01220     {
01221       __glibcxx_requires_string_len(__s, __n);
01222       const size_type __size = this->size();
01223       if (__n <= __size)
01224         {
01225           __pos = std::min(size_type(__size - __n), __pos);
01226           const _CharT* __data = _M_data();
01227           do
01228             {
01229               if (traits_type::compare(__data + __pos, __s, __n) == 0)
01230                 return __pos;
01231             }
01232           while (__pos-- > 0);
01233         }
01234       return npos;
01235     }
01236 
01237   template<typename _CharT, typename _Traits, typename _Alloc>
01238     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01239     basic_string<_CharT, _Traits, _Alloc>::
01240     rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
01241     {
01242       size_type __size = this->size();
01243       if (__size)
01244         {
01245           if (--__size > __pos)
01246             __size = __pos;
01247           for (++__size; __size-- > 0; )
01248             if (traits_type::eq(_M_data()[__size], __c))
01249               return __size;
01250         }
01251       return npos;
01252     }
01253 
01254   template<typename _CharT, typename _Traits, typename _Alloc>
01255     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01256     basic_string<_CharT, _Traits, _Alloc>::
01257     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
01258     {
01259       __glibcxx_requires_string_len(__s, __n);
01260       for (; __n && __pos < this->size(); ++__pos)
01261         {
01262           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
01263           if (__p)
01264             return __pos;
01265         }
01266       return npos;
01267     }
01268 
01269   template<typename _CharT, typename _Traits, typename _Alloc>
01270     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01271     basic_string<_CharT, _Traits, _Alloc>::
01272     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
01273     {
01274       __glibcxx_requires_string_len(__s, __n);
01275       size_type __size = this->size();
01276       if (__size && __n)
01277         {
01278           if (--__size > __pos)
01279             __size = __pos;
01280           do
01281             {
01282               if (traits_type::find(__s, __n, _M_data()[__size]))
01283                 return __size;
01284             }
01285           while (__size-- != 0);
01286         }
01287       return npos;
01288     }
01289 
01290   template<typename _CharT, typename _Traits, typename _Alloc>
01291     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01292     basic_string<_CharT, _Traits, _Alloc>::
01293     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
01294     {
01295       __glibcxx_requires_string_len(__s, __n);
01296       for (; __pos < this->size(); ++__pos)
01297         if (!traits_type::find(__s, __n, _M_data()[__pos]))
01298           return __pos;
01299       return npos;
01300     }
01301 
01302   template<typename _CharT, typename _Traits, typename _Alloc>
01303     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01304     basic_string<_CharT, _Traits, _Alloc>::
01305     find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
01306     {
01307       for (; __pos < this->size(); ++__pos)
01308         if (!traits_type::eq(_M_data()[__pos], __c))
01309           return __pos;
01310       return npos;
01311     }
01312 
01313   template<typename _CharT, typename _Traits, typename _Alloc>
01314     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01315     basic_string<_CharT, _Traits, _Alloc>::
01316     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
01317     {
01318       __glibcxx_requires_string_len(__s, __n);
01319       size_type __size = this->size();
01320       if (__size)
01321         {
01322           if (--__size > __pos)
01323             __size = __pos;
01324           do
01325             {
01326               if (!traits_type::find(__s, __n, _M_data()[__size]))
01327                 return __size;
01328             }
01329           while (__size--);
01330         }
01331       return npos;
01332     }
01333 
01334   template<typename _CharT, typename _Traits, typename _Alloc>
01335     typename basic_string<_CharT, _Traits, _Alloc>::size_type
01336     basic_string<_CharT, _Traits, _Alloc>::
01337     find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
01338     {
01339       size_type __size = this->size();
01340       if (__size)
01341         {
01342           if (--__size > __pos)
01343             __size = __pos;
01344           do
01345             {
01346               if (!traits_type::eq(_M_data()[__size], __c))
01347                 return __size;
01348             }
01349           while (__size--);
01350         }
01351       return npos;
01352     }
01353 
01354   template<typename _CharT, typename _Traits, typename _Alloc>
01355     int
01356     basic_string<_CharT, _Traits, _Alloc>::
01357     compare(size_type __pos, size_type __n, const basic_string& __str) const
01358     {
01359       _M_check(__pos, "basic_string::compare");
01360       __n = _M_limit(__pos, __n);
01361       const size_type __osize = __str.size();
01362       const size_type __len = std::min(__n, __osize);
01363       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
01364       if (!__r)
01365         __r = _S_compare(__n, __osize);
01366       return __r;
01367     }
01368 
01369   template<typename _CharT, typename _Traits, typename _Alloc>
01370     int
01371     basic_string<_CharT, _Traits, _Alloc>::
01372     compare(size_type __pos1, size_type __n1, const basic_string& __str,
01373             size_type __pos2, size_type __n2) const
01374     {
01375       _M_check(__pos1, "basic_string::compare");
01376       __str._M_check(__pos2, "basic_string::compare");
01377       __n1 = _M_limit(__pos1, __n1);
01378       __n2 = __str._M_limit(__pos2, __n2);
01379       const size_type __len = std::min(__n1, __n2);
01380       int __r = traits_type::compare(_M_data() + __pos1,
01381                                      __str.data() + __pos2, __len);
01382       if (!__r)
01383         __r = _S_compare(__n1, __n2);
01384       return __r;
01385     }
01386 
01387   template<typename _CharT, typename _Traits, typename _Alloc>
01388     int
01389     basic_string<_CharT, _Traits, _Alloc>::
01390     compare(const _CharT* __s) const
01391     {
01392       __glibcxx_requires_string(__s);
01393       const size_type __size = this->size();
01394       const size_type __osize = traits_type::length(__s);
01395       const size_type __len = std::min(__size, __osize);
01396       int __r = traits_type::compare(_M_data(), __s, __len);
01397       if (!__r)
01398         __r = _S_compare(__size, __osize);
01399       return __r;
01400     }
01401 
01402   template<typename _CharT, typename _Traits, typename _Alloc>
01403     int
01404     basic_string <_CharT, _Traits, _Alloc>::
01405     compare(size_type __pos, size_type __n1, const _CharT* __s) const
01406     {
01407       __glibcxx_requires_string(__s);
01408       _M_check(__pos, "basic_string::compare");
01409       __n1 = _M_limit(__pos, __n1);
01410       const size_type __osize = traits_type::length(__s);
01411       const size_type __len = std::min(__n1, __osize);
01412       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
01413       if (!__r)
01414         __r = _S_compare(__n1, __osize);
01415       return __r;
01416     }
01417 
01418   template<typename _CharT, typename _Traits, typename _Alloc>
01419     int
01420     basic_string <_CharT, _Traits, _Alloc>::
01421     compare(size_type __pos, size_type __n1, const _CharT* __s,
01422             size_type __n2) const
01423     {
01424       __glibcxx_requires_string_len(__s, __n2);
01425       _M_check(__pos, "basic_string::compare");
01426       __n1 = _M_limit(__pos, __n1);
01427       const size_type __len = std::min(__n1, __n2);
01428       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
01429       if (!__r)
01430         __r = _S_compare(__n1, __n2);
01431       return __r;
01432     }
01433 
01434   // 21.3.7.9 basic_string::getline and operators
01435   template<typename _CharT, typename _Traits, typename _Alloc>
01436     basic_istream<_CharT, _Traits>&
01437     operator>>(basic_istream<_CharT, _Traits>& __in,
01438                basic_string<_CharT, _Traits, _Alloc>& __str)
01439     {
01440       typedef basic_istream<_CharT, _Traits>            __istream_type;
01441       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
01442       typedef typename __istream_type::ios_base         __ios_base;
01443       typedef typename __istream_type::int_type         __int_type;
01444       typedef typename __string_type::size_type         __size_type;
01445       typedef ctype<_CharT>                             __ctype_type;
01446       typedef typename __ctype_type::ctype_base         __ctype_base;
01447 
01448       __size_type __extracted = 0;
01449       typename __ios_base::iostate __err = __ios_base::goodbit;
01450       typename __istream_type::sentry __cerb(__in, false);
01451       if (__cerb)
01452         {
01453           __try
01454             {
01455               // Avoid reallocation for common case.
01456               __str.erase();
01457               _CharT __buf[128];
01458               __size_type __len = 0;          
01459               const streamsize __w = __in.width();
01460               const __size_type __n = __w > 0 ? static_cast<__size_type>(__w)
01461                                               : __str.max_size();
01462               const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc());
01463               const __int_type __eof = _Traits::eof();
01464               __int_type __c = __in.rdbuf()->sgetc();
01465 
01466               while (__extracted < __n
01467                      && !_Traits::eq_int_type(__c, __eof)
01468                      && !__ct.is(__ctype_base::space,
01469                                  _Traits::to_char_type(__c)))
01470                 {
01471                   if (__len == sizeof(__buf) / sizeof(_CharT))
01472                     {
01473                       __str.append(__buf, sizeof(__buf) / sizeof(_CharT));
01474                       __len = 0;
01475                     }
01476                   __buf[__len++] = _Traits::to_char_type(__c);
01477                   ++__extracted;
01478                   __c = __in.rdbuf()->snextc();
01479                 }
01480               __str.append(__buf, __len);
01481 
01482               if (_Traits::eq_int_type(__c, __eof))
01483                 __err |= __ios_base::eofbit;
01484               __in.width(0);
01485             }
01486           __catch(__cxxabiv1::__forced_unwind&)
01487             {
01488               __in._M_setstate(__ios_base::badbit);
01489               __throw_exception_again;
01490             }
01491           __catch(...)
01492             {
01493               // _GLIBCXX_RESOLVE_LIB_DEFECTS
01494               // 91. Description of operator>> and getline() for string<>
01495               // might cause endless loop
01496               __in._M_setstate(__ios_base::badbit);
01497             }
01498         }
01499       // 211.  operator>>(istream&, string&) doesn't set failbit
01500       if (!__extracted)
01501         __err |= __ios_base::failbit;
01502       if (__err)
01503         __in.setstate(__err);
01504       return __in;
01505     }
01506 
01507   template<typename _CharT, typename _Traits, typename _Alloc>
01508     basic_istream<_CharT, _Traits>&
01509     getline(basic_istream<_CharT, _Traits>& __in,
01510             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
01511     {
01512       typedef basic_istream<_CharT, _Traits>            __istream_type;
01513       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
01514       typedef typename __istream_type::ios_base         __ios_base;
01515       typedef typename __istream_type::int_type         __int_type;
01516       typedef typename __string_type::size_type         __size_type;
01517 
01518       __size_type __extracted = 0;
01519       const __size_type __n = __str.max_size();
01520       typename __ios_base::iostate __err = __ios_base::goodbit;
01521       typename __istream_type::sentry __cerb(__in, true);
01522       if (__cerb)
01523         {
01524           __try
01525             {
01526               __str.erase();
01527               const __int_type __idelim = _Traits::to_int_type(__delim);
01528               const __int_type __eof = _Traits::eof();
01529               __int_type __c = __in.rdbuf()->sgetc();
01530 
01531               while (__extracted < __n
01532                      && !_Traits::eq_int_type(__c, __eof)
01533                      && !_Traits::eq_int_type(__c, __idelim))
01534                 {
01535                   __str += _Traits::to_char_type(__c);
01536                   ++__extracted;
01537                   __c = __in.rdbuf()->snextc();
01538                 }
01539 
01540               if (_Traits::eq_int_type(__c, __eof))
01541                 __err |= __ios_base::eofbit;
01542               else if (_Traits::eq_int_type(__c, __idelim))
01543                 {
01544                   ++__extracted;                  
01545                   __in.rdbuf()->sbumpc();
01546                 }
01547               else
01548                 __err |= __ios_base::failbit;
01549             }
01550           __catch(__cxxabiv1::__forced_unwind&)
01551             {
01552               __in._M_setstate(__ios_base::badbit);
01553               __throw_exception_again;
01554             }
01555           __catch(...)
01556             {
01557               // _GLIBCXX_RESOLVE_LIB_DEFECTS
01558               // 91. Description of operator>> and getline() for string<>
01559               // might cause endless loop
01560               __in._M_setstate(__ios_base::badbit);
01561             }
01562         }
01563       if (!__extracted)
01564         __err |= __ios_base::failbit;
01565       if (__err)
01566         __in.setstate(__err);
01567       return __in;
01568     }
01569 
01570   // Inhibit implicit instantiations for required instantiations,
01571   // which are defined via explicit instantiations elsewhere.
01572 #if _GLIBCXX_EXTERN_TEMPLATE > 0
01573   extern template class basic_string<char>;
01574   extern template
01575     basic_istream<char>&
01576     operator>>(basic_istream<char>&, string&);
01577   extern template
01578     basic_ostream<char>&
01579     operator<<(basic_ostream<char>&, const string&);
01580   extern template
01581     basic_istream<char>&
01582     getline(basic_istream<char>&, string&, char);
01583   extern template
01584     basic_istream<char>&
01585     getline(basic_istream<char>&, string&);
01586 
01587 #ifdef _GLIBCXX_USE_WCHAR_T
01588   extern template class basic_string<wchar_t>;
01589   extern template
01590     basic_istream<wchar_t>&
01591     operator>>(basic_istream<wchar_t>&, wstring&);
01592   extern template
01593     basic_ostream<wchar_t>&
01594     operator<<(basic_ostream<wchar_t>&, const wstring&);
01595   extern template
01596     basic_istream<wchar_t>&
01597     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
01598   extern template
01599     basic_istream<wchar_t>&
01600     getline(basic_istream<wchar_t>&, wstring&);
01601 #endif
01602 #endif
01603 
01604 _GLIBCXX_END_NAMESPACE_VERSION
01605 } // namespace std
01606 
01607 #endif