home *** CD-ROM | disk | FTP | other *** search
/ H4CK3R 14 / hacker14.iso / programacao / cwin / c.exe / $INSTDIR / include / c++ / bits / basic_string.tcc < prev    next >
Encoding:
Text File  |  2003-12-15  |  32.9 KB  |  977 lines
  1. // Components for manipulating sequences of characters -*- C++ -*-
  2.  
  3. // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002
  4. // Free Software Foundation, Inc.
  5. //
  6. // This file is part of the GNU ISO C++ Library.  This library is free
  7. // software; you can redistribute it and/or modify it under the
  8. // terms of the GNU General Public License as published by the
  9. // Free Software Foundation; either version 2, or (at your option)
  10. // any later version.
  11.  
  12. // This library is distributed in the hope that it will be useful,
  13. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. // GNU General Public License for more details.
  16.  
  17. // You should have received a copy of the GNU General Public License along
  18. // with this library; see the file COPYING.  If not, write to the Free
  19. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  20. // USA.
  21.  
  22. // As a special exception, you may use this file as part of a free software
  23. // library without restriction.  Specifically, if other files instantiate
  24. // templates or use macros or inline functions from this file, or you compile
  25. // this file and link it with other files to produce an executable, this
  26. // file does not by itself cause the resulting executable to be covered by
  27. // the GNU General Public License.  This exception does not however
  28. // invalidate any other reasons why the executable file might be covered by
  29. // the GNU General Public License.
  30.  
  31. //
  32. // ISO C++ 14882: 21  Strings library
  33. //
  34.  
  35. // This file is included by <string>.  It is not meant to be included
  36. // separately.
  37.  
  38. // Written by Jason Merrill based upon the specification by Takanori Adachi
  39. // in ANSI X3J16/94-0013R2.  Rewritten by Nathan Myers to ISO-14882.
  40.  
  41. #ifndef _CPP_BITS_STRING_TCC
  42. #define _CPP_BITS_STRING_TCC 1
  43.  
  44. #pragma GCC system_header
  45.  
  46. namespace std
  47. {
  48.   template<typename _CharT, typename _Traits, typename _Alloc>
  49.     const typename basic_string<_CharT, _Traits, _Alloc>::size_type 
  50.     basic_string<_CharT, _Traits, _Alloc>::
  51.     _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4;
  52.  
  53.   template<typename _CharT, typename _Traits, typename _Alloc>
  54.     const _CharT 
  55.     basic_string<_CharT, _Traits, _Alloc>::
  56.     _Rep::_S_terminal = _CharT();
  57.  
  58.   template<typename _CharT, typename _Traits, typename _Alloc>
  59.     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
  60.     basic_string<_CharT, _Traits, _Alloc>::npos;
  61.  
  62.   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
  63.   // at static init time (before static ctors are run).
  64.   template<typename _CharT, typename _Traits, typename _Alloc>
  65.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  66.     basic_string<_CharT, _Traits, _Alloc>::_S_empty_rep_storage[
  67.     (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
  68.  
  69.   // NB: This is the special case for Input Iterators, used in
  70.   // istreambuf_iterators, etc.
  71.   // Input Iterators have a cost structure very different from
  72.   // pointers, calling for a different coding style.
  73.   template<typename _CharT, typename _Traits, typename _Alloc>
  74.     template<typename _InIter>
  75.       _CharT*
  76.       basic_string<_CharT, _Traits, _Alloc>::
  77.       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
  78.            input_iterator_tag)
  79.       {
  80.     if (__beg == __end && __a == _Alloc())
  81.       return _S_empty_rep()._M_refcopy();
  82.     // Avoid reallocation for common case.
  83.     _CharT __buf[100];
  84.     size_type __i = 0;
  85.     while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT))
  86.       { 
  87.         __buf[__i++] = *__beg; 
  88.         ++__beg; 
  89.       }
  90.     _Rep* __r = _Rep::_S_create(__i, __a);
  91.     traits_type::copy(__r->_M_refdata(), __buf, __i);
  92.     __r->_M_length = __i;
  93.     try 
  94.       {
  95.         // NB: this loop looks precisely this way because
  96.         // it avoids comparing __beg != __end any more
  97.         // than strictly necessary; != might be expensive!
  98.         for (;;)
  99.           {
  100.         _CharT* __p = __r->_M_refdata() + __r->_M_length;
  101.         _CharT* __last = __r->_M_refdata() + __r->_M_capacity;
  102.         for (;;)
  103.           {
  104.             if (__beg == __end)
  105.               {
  106.             __r->_M_length = __p - __r->_M_refdata();
  107.             *__p = _Rep::_S_terminal;       // grrr.
  108.             return __r->_M_refdata();
  109.               }
  110.             if (__p == __last)
  111.               break;
  112.             *__p++ = *__beg; 
  113.             ++__beg;
  114.           }
  115.         // Allocate more space.
  116.         size_type __len = __p - __r->_M_refdata();
  117.         _Rep* __another = _Rep::_S_create(__len + 1, __a);
  118.         traits_type::copy(__another->_M_refdata(), 
  119.                   __r->_M_refdata(), __len);
  120.         __r->_M_destroy(__a);
  121.         __r = __another;
  122.         __r->_M_length = __len;
  123.           }
  124.       }
  125.     catch(...) 
  126.       {
  127.         __r->_M_destroy(__a); 
  128.         __throw_exception_again;
  129.       }
  130.     return 0;
  131.       }
  132.   
  133.   template<typename _CharT, typename _Traits, typename _Alloc>
  134.     template <class _InIter>
  135.       _CharT*
  136.       basic_string<_CharT, _Traits, _Alloc>::
  137.       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a, 
  138.            forward_iterator_tag)
  139.       {
  140.     size_type __dnew = static_cast<size_type>(distance(__beg, __end));
  141.  
  142.     // NB: Not required, but considered best practice.
  143.     if (__builtin_expect(__beg == _InIter(), 0))
  144.       __throw_logic_error("attempt to create string with null pointer");
  145.     
  146.     if (__beg == __end && __a == _Alloc())
  147.       return _S_empty_rep()._M_refcopy();
  148.  
  149.     // Check for out_of_range and length_error exceptions.
  150.     _Rep* __r = _Rep::_S_create(__dnew, __a);
  151.     try 
  152.       { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
  153.     catch(...) 
  154.       { 
  155.         __r->_M_destroy(__a); 
  156.         __throw_exception_again;
  157.       }
  158.     __r->_M_length = __dnew;
  159.  
  160.     __r->_M_refdata()[__dnew] = _Rep::_S_terminal;  // grrr.
  161.     return __r->_M_refdata();
  162.       }
  163.  
  164.   template<typename _CharT, typename _Traits, typename _Alloc>
  165.     _CharT*
  166.     basic_string<_CharT, _Traits, _Alloc>::
  167.     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
  168.     {
  169.       if (__n == 0 && __a == _Alloc())
  170.     return _S_empty_rep()._M_refcopy();
  171.  
  172.       // Check for out_of_range and length_error exceptions.
  173.       _Rep* __r = _Rep::_S_create(__n, __a);
  174.       try 
  175.     { 
  176.       if (__n) 
  177.         traits_type::assign(__r->_M_refdata(), __n, __c); 
  178.     }
  179.       catch(...) 
  180.     { 
  181.       __r->_M_destroy(__a); 
  182.       __throw_exception_again;
  183.     }
  184.       __r->_M_length = __n;
  185.       __r->_M_refdata()[__n] = _Rep::_S_terminal;  // grrr
  186.       return __r->_M_refdata();
  187.     }
  188.  
  189.   template<typename _CharT, typename _Traits, typename _Alloc>
  190.     basic_string<_CharT, _Traits, _Alloc>::
  191.     basic_string(const basic_string& __str)
  192.     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()),
  193.          __str.get_allocator())
  194.     { }
  195.  
  196.   template<typename _CharT, typename _Traits, typename _Alloc>
  197.     basic_string<_CharT, _Traits, _Alloc>::
  198.     basic_string(const _Alloc& __a)
  199.     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
  200.     { }
  201.  
  202.   template<typename _CharT, typename _Traits, typename _Alloc>
  203.     basic_string<_CharT, _Traits, _Alloc>::
  204.     basic_string(const basic_string& __str, size_type __pos, size_type __n)
  205.     : _M_dataplus(_S_construct(__str._M_check(__pos), 
  206.                    __str._M_fold(__pos, __n), _Alloc()), _Alloc())
  207.     { }
  208.  
  209.   template<typename _CharT, typename _Traits, typename _Alloc>
  210.     basic_string<_CharT, _Traits, _Alloc>::
  211.     basic_string(const basic_string& __str, size_type __pos,
  212.          size_type __n, const _Alloc& __a)
  213.     : _M_dataplus(_S_construct(__str._M_check(__pos), 
  214.                    __str._M_fold(__pos, __n), __a), __a)
  215.     { }
  216.  
  217.   template<typename _CharT, typename _Traits, typename _Alloc>
  218.     basic_string<_CharT, _Traits, _Alloc>::
  219.     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
  220.     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
  221.     { }
  222.  
  223.   template<typename _CharT, typename _Traits, typename _Alloc>
  224.     basic_string<_CharT, _Traits, _Alloc>::
  225.     basic_string(const _CharT* __s, const _Alloc& __a)
  226.     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : 0, 
  227.                    __a), __a)
  228.     { }
  229.  
  230.   template<typename _CharT, typename _Traits, typename _Alloc>
  231.     basic_string<_CharT, _Traits, _Alloc>::
  232.     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
  233.     : _M_dataplus(_S_construct(__n, __c, __a), __a)
  234.     { }
  235.  
  236.   template<typename _CharT, typename _Traits, typename _Alloc>
  237.     template<typename _InputIter>
  238.     basic_string<_CharT, _Traits, _Alloc>::
  239.     basic_string(_InputIter __beg, _InputIter __end, const _Alloc& __a)
  240.     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
  241.     { }
  242.  
  243.   template<typename _CharT, typename _Traits, typename _Alloc>
  244.     basic_string<_CharT, _Traits, _Alloc>&
  245.     basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str)
  246.     {
  247.       if (_M_rep() != __str._M_rep())
  248.     {
  249.       // XXX MT
  250.       allocator_type __a = this->get_allocator();
  251.       _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
  252.       _M_rep()->_M_dispose(__a);
  253.       _M_data(__tmp);
  254.     }
  255.       return *this;
  256.     }
  257.   
  258.   template<typename _CharT, typename _Traits, typename _Alloc>
  259.     void
  260.     basic_string<_CharT, _Traits, _Alloc>::_Rep::
  261.     _M_destroy(const _Alloc& __a) throw ()
  262.     {
  263.       size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT);
  264.       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
  265.     }
  266.  
  267.   template<typename _CharT, typename _Traits, typename _Alloc>
  268.     void
  269.     basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
  270.     {
  271.       if (_M_rep()->_M_is_shared()) 
  272.     _M_mutate(0, 0, 0);
  273.       _M_rep()->_M_set_leaked();
  274.     }
  275.  
  276.   // _M_mutate and, below, _M_clone, include, in the same form, an exponential
  277.   // growth policy, necessary to meet amortized linear time requirements of
  278.   // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
  279.   // The policy is active for allocations requiring an amount of memory above
  280.   // system pagesize. This is consistent with the requirements of the standard:
  281.   // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
  282.   template<typename _CharT, typename _Traits, typename _Alloc>
  283.     void
  284.     basic_string<_CharT, _Traits, _Alloc>::
  285.     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
  286.     {
  287.       size_type       __old_size = this->size();
  288.       const size_type __new_size = __old_size + __len2 - __len1;
  289.       const _CharT*        __src = _M_data()  + __pos + __len1;
  290.       const size_type __how_much = __old_size - __pos - __len1;
  291.       
  292.       if (_M_rep()->_M_is_shared() || __new_size > capacity())
  293.     {
  294.       // Must reallocate.
  295.       allocator_type __a = get_allocator();
  296.       // See below (_S_create) for the meaning and value of these
  297.       // constants.
  298.       const size_type __pagesize = 4096;
  299.       const size_type __malloc_header_size = 4 * sizeof (void*);
  300.       // The biggest string which fits in a memory page
  301.       const size_type __page_capacity = (__pagesize - __malloc_header_size
  302.                          - sizeof(_Rep) - sizeof(_CharT)) 
  303.                              / sizeof(_CharT);
  304.       _Rep* __r;
  305.       if (__new_size > capacity() && __new_size > __page_capacity)
  306.         // Growing exponentially.
  307.         __r = _Rep::_S_create(__new_size > 2*capacity() ?
  308.                   __new_size : 2*capacity(), __a);
  309.       else
  310.         __r = _Rep::_S_create(__new_size, __a);
  311.       try 
  312.         {
  313.           if (__pos)
  314.         traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
  315.           if (__how_much)
  316.         traits_type::copy(__r->_M_refdata() + __pos + __len2, 
  317.                   __src, __how_much);
  318.         }
  319.       catch(...) 
  320.         { 
  321.           __r->_M_dispose(get_allocator()); 
  322.           __throw_exception_again;
  323.         }
  324.       _M_rep()->_M_dispose(__a);
  325.       _M_data(__r->_M_refdata());
  326.       }
  327.       else if (__how_much && __len1 != __len2)
  328.     {
  329.       // Work in-place
  330.       traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
  331.     }
  332.       _M_rep()->_M_set_sharable();
  333.       _M_rep()->_M_length = __new_size;
  334.       _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
  335.     // You cannot leave those LWG people alone for a second.
  336.     }
  337.   
  338.   template<typename _CharT, typename _Traits, typename _Alloc>
  339.     void
  340.     basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
  341.     {
  342.       if (__res > this->capacity() || _M_rep()->_M_is_shared())
  343.         {
  344.       if (__res > this->max_size())
  345.         __throw_length_error("basic_string::reserve");
  346.       // Make sure we don't shrink below the current size
  347.       if (__res < this->size())
  348.         __res = this->size();
  349.       allocator_type __a = get_allocator();
  350.       _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
  351.       _M_rep()->_M_dispose(__a);
  352.       _M_data(__tmp);
  353.         }
  354.     }
  355.   
  356.   template<typename _CharT, typename _Traits, typename _Alloc>
  357.     void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
  358.     {
  359.       if (_M_rep()->_M_is_leaked()) 
  360.     _M_rep()->_M_set_sharable();
  361.       if (__s._M_rep()->_M_is_leaked()) 
  362.     __s._M_rep()->_M_set_sharable();
  363.       if (this->get_allocator() == __s.get_allocator())
  364.     {
  365.       _CharT* __tmp = _M_data();
  366.       _M_data(__s._M_data());
  367.       __s._M_data(__tmp);
  368.     }
  369.       // The code below can usually be optimized away.
  370.       else 
  371.     {
  372.       basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator());
  373.       basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 
  374.                   this->get_allocator());
  375.       *this = __tmp2;
  376.       __s = __tmp1;
  377.     }
  378.     }
  379.  
  380.   template<typename _CharT, typename _Traits, typename _Alloc>
  381.     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
  382.     basic_string<_CharT, _Traits, _Alloc>::_Rep::
  383.     _S_create(size_t __capacity, const _Alloc& __alloc)
  384.     {
  385.       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
  386. #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
  387.       // 83.  String::npos vs. string::max_size()
  388.       if (__capacity > _S_max_size)
  389. #else
  390.       if (__capacity == npos)
  391. #endif
  392.     __throw_length_error("basic_string::_S_create");
  393.  
  394.       // NB: Need an array of char_type[__capacity], plus a
  395.       // terminating null char_type() element, plus enough for the
  396.       // _Rep data structure. Whew. Seemingly so needy, yet so elemental.
  397.       size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
  398.  
  399.       // The standard places no restriction on allocating more memory
  400.       // than is strictly needed within this layer at the moment or as
  401.       // requested by an explicit application call to reserve().  Many
  402.       // malloc implementations perform quite poorly when an
  403.       // application attempts to allocate memory in a stepwise fashion
  404.       // growing each allocation size by only 1 char.  Additionally,
  405.       // it makes little sense to allocate less linear memory than the
  406.       // natural blocking size of the malloc implementation.
  407.       // Unfortunately, we would need a somewhat low-level calculation
  408.       // with tuned parameters to get this perfect for any particular
  409.       // malloc implementation.  Fortunately, generalizations about
  410.       // common features seen among implementations seems to suffice.
  411.  
  412.       // __pagesize need not match the actual VM page size for good
  413.       // results in practice, thus we pick a common value on the low
  414.       // side.  __malloc_header_size is an estimate of the amount of
  415.       // overhead per memory allocation (in practice seen N * sizeof
  416.       // (void*) where N is 0, 2 or 4).  According to folklore,
  417.       // picking this value on the high side is better than
  418.       // low-balling it (especially when this algorithm is used with
  419.       // malloc implementations that allocate memory blocks rounded up
  420.       // to a size which is a power of 2).
  421.       const size_t __pagesize = 4096; // must be 2^i * __subpagesize
  422.       const size_t __subpagesize = 128; // should be >> __malloc_header_size
  423.       const size_t __malloc_header_size = 4 * sizeof (void*);
  424.       if ((__size + __malloc_header_size) > __pagesize)
  425.     {
  426.       size_t __extra =
  427.         (__pagesize - ((__size + __malloc_header_size) % __pagesize))
  428.         % __pagesize;
  429.       __capacity += __extra / sizeof(_CharT);
  430.       __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
  431.     }
  432.       else if (__size > __subpagesize)
  433.     {
  434.       size_t __extra =
  435.         (__subpagesize - ((__size + __malloc_header_size) % __subpagesize))
  436.         % __subpagesize;
  437.       __capacity += __extra / sizeof(_CharT);
  438.       __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
  439.     }
  440.  
  441.       // NB: Might throw, but no worries about a leak, mate: _Rep()
  442.       // does not throw.
  443.       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
  444.       _Rep *__p = new (__place) _Rep;
  445.       __p->_M_capacity = __capacity;
  446.       __p->_M_set_sharable();  // One reference.
  447.       __p->_M_length = 0;
  448.       return __p;
  449.     }
  450.  
  451.   template<typename _CharT, typename _Traits, typename _Alloc>
  452.     _CharT*
  453.     basic_string<_CharT, _Traits, _Alloc>::_Rep::
  454.     _M_clone(const _Alloc& __alloc, size_type __res)
  455.     {
  456.       // Requested capacity of the clone.
  457.       const size_type __requested_cap = _M_length + __res;
  458.       // See above (_S_create) for the meaning and value of these constants.
  459.       const size_type __pagesize = 4096;
  460.       const size_type __malloc_header_size = 4 * sizeof (void*);
  461.       // The biggest string which fits in a memory page.
  462.       const size_type __page_capacity =
  463.         (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT))
  464.         / sizeof(_CharT);
  465.       _Rep* __r;
  466.       if (__requested_cap > _M_capacity && __requested_cap > __page_capacity)
  467.         // Growing exponentially.
  468.         __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ?
  469.                               __requested_cap : 2*_M_capacity, __alloc);
  470.       else
  471.         __r = _Rep::_S_create(__requested_cap, __alloc);
  472.       
  473.       if (_M_length)
  474.     {
  475.       try 
  476.         { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); }
  477.       catch(...)  
  478.         { 
  479.           __r->_M_destroy(__alloc); 
  480.           __throw_exception_again;
  481.         }
  482.     }
  483.       __r->_M_length = _M_length;
  484.       return __r->_M_refdata();
  485.     }
  486.   
  487.   template<typename _CharT, typename _Traits, typename _Alloc>
  488.     void
  489.     basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
  490.     {
  491.       if (__n > max_size())
  492.     __throw_length_error("basic_string::resize");
  493.       size_type __size = this->size();
  494.       if (__size < __n)
  495.     this->append(__n - __size, __c);
  496.       else if (__n < __size)
  497.     this->erase(__n);
  498.       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
  499.     }
  500.   
  501.  
  502.   // This is the general replace helper, which currently gets instantiated both
  503.   // for input iterators and reverse iterators. It buffers internally and then
  504.   // calls _M_replace_safe.
  505.   template<typename _CharT, typename _Traits, typename _Alloc>
  506.     template<typename _InputIter>
  507.       basic_string<_CharT, _Traits, _Alloc>&
  508.       basic_string<_CharT, _Traits, _Alloc>::
  509.       _M_replace(iterator __i1, iterator __i2, _InputIter __k1, 
  510.          _InputIter __k2, input_iterator_tag)
  511.       {
  512.     // Save concerned source string data in a temporary.
  513.     basic_string __s(__k1, __k2);
  514.     return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend());
  515.       }
  516.  
  517.   // This is a special replace helper, which does not buffer internally
  518.   // and can be used in "safe" situations involving forward iterators,
  519.   // i.e., when source and destination ranges are known to not overlap.
  520.   template<typename _CharT, typename _Traits, typename _Alloc>
  521.     template<typename _ForwardIter>
  522.       basic_string<_CharT, _Traits, _Alloc>&
  523.       basic_string<_CharT, _Traits, _Alloc>::
  524.       _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1, 
  525.               _ForwardIter __k2)
  526.       {
  527.     size_type __dnew = static_cast<size_type>(distance(__k1, __k2));
  528.     size_type __dold = __i2 - __i1;
  529.     size_type __dmax = this->max_size();
  530.  
  531.     if (__dmax <= __dnew)
  532.       __throw_length_error("basic_string::_M_replace");
  533.     size_type __off = __i1 - _M_ibegin();
  534.     _M_mutate(__off, __dold, __dnew);
  535.  
  536.     // Invalidated __i1, __i2
  537.         if (__dnew)
  538.       _S_copy_chars(_M_data() + __off, __k1, __k2);
  539.  
  540.     return *this;
  541.       }
  542.  
  543.   template<typename _CharT, typename _Traits, typename _Alloc>
  544.     basic_string<_CharT, _Traits, _Alloc>&
  545.     basic_string<_CharT, _Traits, _Alloc>::
  546.     replace(size_type __pos1, size_type __n1, const basic_string& __str,
  547.         size_type __pos2, size_type __n2)
  548.     {
  549.       const size_type __strsize = __str.size();
  550.       if (__pos2 > __strsize)
  551.     __throw_out_of_range("basic_string::replace");
  552.       const bool __testn2 = __n2 < __strsize - __pos2;
  553.       const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2;
  554.       return this->replace(__pos1, __n1,
  555.                __str._M_data() + __pos2, __foldn2);      
  556.     }
  557.  
  558.   template<typename _CharT, typename _Traits, typename _Alloc>
  559.     basic_string<_CharT, _Traits, _Alloc>&
  560.     basic_string<_CharT, _Traits, _Alloc>::
  561.     append(const basic_string& __str)
  562.     {
  563.       // Iff appending itself, string needs to pre-reserve the
  564.       // correct size so that _M_mutate does not clobber the
  565.       // iterators formed here.
  566.       size_type __size = __str.size();
  567.       size_type __len = __size + this->size();
  568.       if (__len > this->capacity())
  569.     this->reserve(__len);
  570.       return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(),
  571.                  __str._M_iend());
  572.     }
  573.  
  574.   template<typename _CharT, typename _Traits, typename _Alloc>
  575.     basic_string<_CharT, _Traits, _Alloc>&
  576.     basic_string<_CharT, _Traits, _Alloc>::
  577.     append(const basic_string& __str, size_type __pos, size_type __n)
  578.     {
  579.       // Iff appending itself, string needs to pre-reserve the
  580.       // correct size so that _M_mutate does not clobber the
  581.       // iterators formed here.
  582.       size_type __len = min(__str.size() - __pos, __n) + this->size();
  583.       if (__len > this->capacity())
  584.     this->reserve(__len);
  585.       return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos),
  586.                  __str._M_fold(__pos, __n));
  587.     }
  588.  
  589.   template<typename _CharT, typename _Traits, typename _Alloc>
  590.     basic_string<_CharT, _Traits, _Alloc>&
  591.     basic_string<_CharT, _Traits, _Alloc>::
  592.     append(const _CharT* __s, size_type __n)
  593.     {
  594.       size_type __len = __n + this->size();
  595.       if (__len > this->capacity())
  596.     this->reserve(__len);
  597.       return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n);
  598.     }
  599.  
  600.   template<typename _CharT, typename _Traits, typename _Alloc>
  601.     basic_string<_CharT, _Traits, _Alloc>&
  602.     basic_string<_CharT, _Traits, _Alloc>::
  603.     append(size_type __n, _CharT __c)
  604.     {
  605.       size_type __len = __n + this->size();
  606.       if (__len > this->capacity())
  607.     this->reserve(__len);
  608.        return this->replace(_M_iend(), _M_iend(), __n, __c);
  609.     }
  610.  
  611.   template<typename _CharT, typename _Traits, typename _Alloc>
  612.     basic_string<_CharT, _Traits, _Alloc>
  613.     operator+(const _CharT* __lhs,
  614.           const basic_string<_CharT, _Traits, _Alloc>& __rhs)
  615.     {
  616.       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
  617.       typedef typename __string_type::size_type      __size_type;
  618.       __size_type __len = _Traits::length(__lhs);
  619.       __string_type __str;
  620.       __str.reserve(__len + __rhs.size());
  621.       __str.append(__lhs, __lhs + __len);
  622.       __str.append(__rhs);
  623.       return __str;
  624.     }
  625.  
  626.   template<typename _CharT, typename _Traits, typename _Alloc>
  627.     basic_string<_CharT, _Traits, _Alloc>
  628.     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
  629.     {
  630.       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
  631.       typedef typename __string_type::size_type      __size_type;
  632.       __string_type __str;
  633.       __size_type __len = __rhs.size();
  634.       __str.reserve(__len + 1);
  635.       __str.append(__size_type(1), __lhs);
  636.       __str.append(__rhs);
  637.       return __str;
  638.     }
  639.  
  640.   template<typename _CharT, typename _Traits, typename _Alloc>
  641.     basic_string<_CharT, _Traits, _Alloc>&
  642.     basic_string<_CharT, _Traits, _Alloc>::
  643.     replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c)
  644.     {
  645.       size_type __n1 = __i2 - __i1;
  646.       size_type __off1 = __i1 - _M_ibegin();
  647.       if (max_size() - (this->size() - __n1) <= __n2)
  648.     __throw_length_error("basic_string::replace");
  649.       _M_mutate (__off1, __n1, __n2);
  650.       // Invalidated __i1, __i2
  651.       if (__n2)
  652.     traits_type::assign(_M_data() + __off1, __n2, __c);
  653.       return *this;
  654.     }
  655.   
  656.   template<typename _CharT, typename _Traits, typename _Alloc>
  657.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  658.     basic_string<_CharT, _Traits, _Alloc>::
  659.     copy(_CharT* __s, size_type __n, size_type __pos) const
  660.     {
  661.       if (__pos > this->size())
  662.     __throw_out_of_range("basic_string::copy");
  663.       
  664.       if (__n > this->size() - __pos)
  665.     __n = this->size() - __pos;
  666.       
  667.       traits_type::copy(__s, _M_data() + __pos, __n);
  668.       // 21.3.5.7 par 3: do not append null.  (good.)
  669.       return __n;
  670.     }
  671.  
  672.   template<typename _CharT, typename _Traits, typename _Alloc>
  673.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  674.     basic_string<_CharT, _Traits, _Alloc>::
  675.     find(const _CharT* __s, size_type __pos, size_type __n) const
  676.     {
  677.       size_type __size = this->size();
  678.       size_t __xpos = __pos;
  679.       const _CharT* __data = _M_data();
  680.       for (; __xpos + __n <= __size; ++__xpos)
  681.     if (traits_type::compare(__data + __xpos, __s, __n) == 0)
  682.       return __xpos;
  683.       return npos;
  684.     }
  685.  
  686.   template<typename _CharT, typename _Traits, typename _Alloc>
  687.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  688.     basic_string<_CharT, _Traits, _Alloc>::
  689.     find(_CharT __c, size_type __pos) const
  690.     {
  691.       size_type __size = this->size();
  692.       size_type __ret = npos;
  693.       if (__pos < __size)
  694.     {
  695.       const _CharT* __data = _M_data();
  696.       size_type __n = __size - __pos;
  697.       const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
  698.       if (__p)
  699.         __ret = __p - __data;
  700.     }
  701.       return __ret;
  702.     }
  703.  
  704.  
  705.   template<typename _CharT, typename _Traits, typename _Alloc>
  706.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  707.     basic_string<_CharT, _Traits, _Alloc>::
  708.     rfind(const _CharT* __s, size_type __pos, size_type __n) const
  709.     {
  710.       size_type __size = this->size();
  711.       if (__n <= __size)
  712.     {
  713.       __pos = std::min(__size - __n, __pos);
  714.       const _CharT* __data = _M_data();
  715.       do 
  716.         {
  717.           if (traits_type::compare(__data + __pos, __s, __n) == 0)
  718.         return __pos;
  719.         } 
  720.       while (__pos-- > 0);
  721.     }
  722.       return npos;
  723.     }
  724.   
  725.   template<typename _CharT, typename _Traits, typename _Alloc>
  726.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  727.     basic_string<_CharT, _Traits, _Alloc>::
  728.     rfind(_CharT __c, size_type __pos) const
  729.     {
  730.       size_type __size = this->size();
  731.       if (__size)
  732.     {
  733.       size_t __xpos = __size - 1;
  734.       if (__xpos > __pos)
  735.         __xpos = __pos;
  736.       
  737.       for (++__xpos; __xpos-- > 0; )
  738.         if (traits_type::eq(_M_data()[__xpos], __c))
  739.           return __xpos;
  740.     }
  741.       return npos;
  742.     }
  743.   
  744.   template<typename _CharT, typename _Traits, typename _Alloc>
  745.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  746.     basic_string<_CharT, _Traits, _Alloc>::
  747.     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
  748.     {
  749.       for (; __n && __pos < this->size(); ++__pos)
  750.     {
  751.       const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
  752.       if (__p)
  753.         return __pos;
  754.     }
  755.       return npos;
  756.     }
  757.  
  758.   template<typename _CharT, typename _Traits, typename _Alloc>
  759.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  760.     basic_string<_CharT, _Traits, _Alloc>::
  761.     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
  762.     {
  763.       size_type __size = this->size();
  764.       if (__size && __n)
  765.     { 
  766.       if (--__size > __pos) 
  767.         __size = __pos;
  768.       do
  769.         {
  770.           if (traits_type::find(__s, __n, _M_data()[__size]))
  771.         return __size;
  772.         } 
  773.       while (__size-- != 0);
  774.     }
  775.       return npos;
  776.     }
  777.   
  778.   template<typename _CharT, typename _Traits, typename _Alloc>
  779.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  780.     basic_string<_CharT, _Traits, _Alloc>::
  781.     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
  782.     {
  783.       size_t __xpos = __pos;
  784.       for (; __xpos < this->size(); ++__xpos)
  785.     if (!traits_type::find(__s, __n, _M_data()[__xpos]))
  786.       return __xpos;
  787.       return npos;
  788.     }
  789.  
  790.   template<typename _CharT, typename _Traits, typename _Alloc>
  791.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  792.     basic_string<_CharT, _Traits, _Alloc>::
  793.     find_first_not_of(_CharT __c, size_type __pos) const
  794.     {
  795.       size_t __xpos = __pos;
  796.       for (; __xpos < this->size(); ++__xpos)
  797.     if (!traits_type::eq(_M_data()[__xpos], __c))
  798.       return __xpos;
  799.       return npos;
  800.     }
  801.  
  802.   template<typename _CharT, typename _Traits, typename _Alloc>
  803.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  804.     basic_string<_CharT, _Traits, _Alloc>::
  805.     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
  806.     {
  807.       size_type __size = this->size();
  808.       if (__size)
  809.     { 
  810.       if (--__size > __pos) 
  811.         __size = __pos;
  812.       do
  813.         {
  814.           if (!traits_type::find(__s, __n, _M_data()[__size]))
  815.         return __size;
  816.         } 
  817.       while (__size--);
  818.     }
  819.       return npos;
  820.     }
  821.  
  822.   template<typename _CharT, typename _Traits, typename _Alloc>
  823.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  824.     basic_string<_CharT, _Traits, _Alloc>::
  825.     find_last_not_of(_CharT __c, size_type __pos) const
  826.     {
  827.       size_type __size = this->size();
  828.       if (__size)
  829.     { 
  830.       if (--__size > __pos) 
  831.         __size = __pos;
  832.       do
  833.         {
  834.           if (!traits_type::eq(_M_data()[__size], __c))
  835.         return __size;
  836.         } 
  837.       while (__size--);
  838.     }
  839.       return npos;
  840.     }
  841.   
  842.   template<typename _CharT, typename _Traits, typename _Alloc>
  843.     int
  844.     basic_string<_CharT, _Traits, _Alloc>::
  845.     compare(size_type __pos, size_type __n, const basic_string& __str) const
  846.     {
  847.       size_type __size = this->size();
  848.       size_type __osize = __str.size();
  849.       if (__pos > __size)
  850.     __throw_out_of_range("basic_string::compare");
  851.       
  852.       size_type __rsize= min(__size - __pos, __n);
  853.       size_type __len = min(__rsize, __osize);
  854.       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
  855.       if (!__r)
  856.     __r = __rsize - __osize;
  857.       return __r;
  858.     }
  859.  
  860.   template<typename _CharT, typename _Traits, typename _Alloc>
  861.     int
  862.     basic_string<_CharT, _Traits, _Alloc>::
  863.     compare(size_type __pos1, size_type __n1, const basic_string& __str,
  864.         size_type __pos2, size_type __n2) const
  865.     {
  866.       size_type __size = this->size();
  867.       size_type __osize = __str.size();
  868.       if (__pos1 > __size || __pos2 > __osize)
  869.     __throw_out_of_range("basic_string::compare");
  870.       
  871.       size_type __rsize = min(__size - __pos1, __n1);
  872.       size_type __rosize = min(__osize - __pos2, __n2);
  873.       size_type __len = min(__rsize, __rosize);
  874.       int __r = traits_type::compare(_M_data() + __pos1, 
  875.                      __str.data() + __pos2, __len);
  876.       if (!__r)
  877.     __r = __rsize - __rosize;
  878.       return __r;
  879.     }
  880.  
  881.  
  882.   template<typename _CharT, typename _Traits, typename _Alloc>
  883.     int
  884.     basic_string<_CharT, _Traits, _Alloc>::
  885.     compare(const _CharT* __s) const
  886.     {
  887.       size_type __size = this->size();
  888.       int __r = traits_type::compare(_M_data(), __s, __size);
  889.       if (!__r)
  890.     __r = __size - traits_type::length(__s);
  891.       return __r;
  892.     }
  893.  
  894.  
  895.   template<typename _CharT, typename _Traits, typename _Alloc>
  896.     int
  897.     basic_string <_CharT, _Traits, _Alloc>::
  898.     compare(size_type __pos, size_type __n1, const _CharT* __s) const
  899.     {
  900.       size_type __size = this->size();
  901.       if (__pos > __size)
  902.     __throw_out_of_range("basic_string::compare");
  903.       
  904.       size_type __osize = traits_type::length(__s);
  905.       size_type __rsize = min(__size - __pos, __n1);
  906.       size_type __len = min(__rsize, __osize);
  907.       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
  908.       if (!__r)
  909.     __r = __rsize - __osize;
  910.       return __r;
  911.     }
  912.  
  913.   template<typename _CharT, typename _Traits, typename _Alloc>
  914.     int
  915.     basic_string <_CharT, _Traits, _Alloc>::
  916.     compare(size_type __pos, size_type __n1, const _CharT* __s, 
  917.         size_type __n2) const
  918.     {
  919.       size_type __size = this->size();
  920.       if (__pos > __size)
  921.     __throw_out_of_range("basic_string::compare");
  922.       
  923.       size_type __osize = min(traits_type::length(__s), __n2);
  924.       size_type __rsize = min(__size - __pos, __n1);
  925.       size_type __len = min(__rsize, __osize);
  926.       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
  927.       if (!__r)
  928.     __r = __rsize - __osize;
  929.       return __r;
  930.     }
  931.  
  932.   template <class _CharT, class _Traits, class _Alloc>
  933.     void
  934.     _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str,
  935.            _CharT* __buf, typename _Alloc::size_type __bufsiz)
  936.     {
  937.       typedef typename _Alloc::size_type size_type;
  938.       size_type __strsize = __str.size();
  939.       size_type __bytes = min(__strsize, __bufsiz - 1);
  940.       _Traits::copy(__buf, __str.data(), __bytes);
  941.       __buf[__bytes] = _CharT();
  942.     }
  943.  
  944.   // Inhibit implicit instantiations for required instantiations,
  945.   // which are defined via explicit instantiations elsewhere.  
  946.   // NB: This syntax is a GNU extension.
  947.   extern template class basic_string<char>;
  948.   extern template 
  949.     basic_istream<char>& 
  950.     operator>>(basic_istream<char>&, string&);
  951.   extern template 
  952.     basic_ostream<char>& 
  953.     operator<<(basic_ostream<char>&, const string&);
  954.   extern template 
  955.     basic_istream<char>& 
  956.     getline(basic_istream<char>&, string&, char);
  957.   extern template 
  958.     basic_istream<char>& 
  959.     getline(basic_istream<char>&, string&);
  960.  
  961.   extern template class basic_string<wchar_t>;
  962.   extern template 
  963.     basic_istream<wchar_t>& 
  964.     operator>>(basic_istream<wchar_t>&, wstring&);
  965.   extern template 
  966.     basic_ostream<wchar_t>& 
  967.     operator<<(basic_ostream<wchar_t>&, const wstring&);
  968.   extern template 
  969.     basic_istream<wchar_t>& 
  970.     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
  971.   extern template 
  972.     basic_istream<wchar_t>& 
  973.     getline(basic_istream<wchar_t>&, wstring&);
  974. } // namespace std
  975.  
  976. #endif
  977.