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