Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. // Components for manipulating sequences of characters -*- C++ -*-
  2.  
  3. // Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 2, or (at your option)
  9. // any later version.
  10.  
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. // GNU General Public License for more details.
  15.  
  16. // You should have received a copy of the GNU General Public License along
  17. // with this library; see the file COPYING.  If not, write to the Free
  18. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19. // USA.
  20.  
  21. // As a special exception, you may use this file as part of a free software
  22. // library without restriction.  Specifically, if other files instantiate
  23. // templates or use macros or inline functions from this file, or you compile
  24. // this file and link it with other files to produce an executable, this
  25. // file does not by itself cause the resulting executable to be covered by
  26. // the GNU General Public License.  This exception does not however
  27. // invalidate any other reasons why the executable file might be covered by
  28. // the GNU General Public License.
  29.  
  30. //
  31. // ISO C++ 14882: 21  Strings library
  32. //
  33.  
  34. // This file is included by <string>.  It is not meant to be included
  35. // separately.
  36.  
  37. // Written by Jason Merrill based upon the specification by Takanori Adachi
  38. // in ANSI X3J16/94-0013R2.  Rewritten by Nathan Myers to ISO-14882.
  39.  
  40. #ifndef _CPP_BITS_STRING_TCC
  41. #define _CPP_BITS_STRING_TCC 1
  42.  
  43. namespace std
  44. {
  45.   template<typename _CharT, typename _Traits, typename _Alloc>
  46.     const _CharT
  47.     basic_string<_CharT, _Traits, _Alloc>::
  48.     _Rep::_S_terminal = _CharT();
  49.  
  50.   template<typename _CharT, typename _Traits, typename _Alloc>
  51.     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
  52.     basic_string<_CharT, _Traits, _Alloc>::
  53.     _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4;
  54.  
  55.   template<typename _CharT, typename _Traits, typename _Alloc>
  56.     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
  57.     basic_string<_CharT, _Traits, _Alloc>::npos;
  58.  
  59.   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
  60.   // at static init time (before static ctors are run).
  61.   template<typename _CharT, typename _Traits, typename _Alloc>
  62.     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  63.     basic_string<_CharT, _Traits, _Alloc>::_S_empty_rep_storage[
  64.     (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
  65.  
  66.   // NB: This is the special case for Input Iterators, used in
  67.   // istreambuf_iterators, etc.
  68.   // Input Iterators have a cost structure very different from
  69.   // pointers, calling for a different coding style.
  70.   template<typename _CharT, typename _Traits, typename _Alloc>
  71.     template<typename _InIter>
  72.       _CharT*
  73.       basic_string<_CharT, _Traits, _Alloc>::
  74.       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
  75.                    input_iterator_tag)
  76.       {
  77.         if (__beg == __end && __a == _Alloc())
  78.           return _S_empty_rep()._M_refcopy();
  79.         // Avoid reallocation for common case.
  80.         _CharT __buf[100];
  81.         size_type __i = 0;
  82.         while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT))
  83.           {
  84.             __buf[__i++] = *__beg;
  85.             ++__beg;
  86.           }
  87.         _Rep* __r = _Rep::_S_create(__i, __a);
  88.         traits_type::copy(__r->_M_refdata(), __buf, __i);
  89.         __r->_M_length = __i;
  90.         try
  91.           {
  92.             // NB: this loop looks precisely this way because
  93.             // it avoids comparing __beg != __end any more
  94.             // than strictly necessary; != might be expensive!
  95.             for (;;)
  96.               {
  97.                 _CharT* __p = __r->_M_refdata() + __r->_M_length;
  98.                 _CharT* __last = __r->_M_refdata() + __r->_M_capacity;
  99.                 for (;;)
  100.                   {
  101.                     if (__beg == __end)
  102.                       {
  103.                         __r->_M_length = __p - __r->_M_refdata();
  104.                         *__p = _Rep::_S_terminal;       // grrr.
  105.                         return __r->_M_refdata();
  106.                       }
  107.                     if (__p == __last)
  108.                       break;
  109.                     *__p++ = *__beg;
  110.                     ++__beg;
  111.                   }
  112.                 // Allocate more space.
  113.                 size_type __len = __p - __r->_M_refdata();
  114.                 _Rep* __another = _Rep::_S_create(__len + 1, __a);
  115.                 traits_type::copy(__another->_M_refdata(),
  116.                                   __r->_M_refdata(), __len);
  117.                 __r->_M_destroy(__a);
  118.                 __r = __another;
  119.                 __r->_M_length = __len;
  120.               }
  121.           }
  122.         catch(...)
  123.           {
  124.             __r->_M_destroy(__a);
  125.             __throw_exception_again;
  126.           }
  127.         return 0;
  128.       }
  129.  
  130.   template<typename _CharT, typename _Traits, typename _Alloc>
  131.     template <class _InIter>
  132.       _CharT*
  133.       basic_string<_CharT,_Traits,_Alloc>::
  134.       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
  135.                    forward_iterator_tag)
  136.       {
  137.         size_type __dnew = static_cast<size_type>(distance(__beg, __end));
  138.  
  139.         if (__beg == __end && __a == _Alloc())
  140.           return _S_empty_rep()._M_refcopy();
  141.  
  142.         // Check for out_of_range and length_error exceptions.
  143.         _Rep* __r = _Rep::_S_create(__dnew, __a);
  144.         try
  145.           { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
  146.         catch(...)
  147.           {
  148.             __r->_M_destroy(__a);
  149.             __throw_exception_again;
  150.           }
  151.         __r->_M_length = __dnew;
  152.  
  153.         __r->_M_refdata()[__dnew] = _Rep::_S_terminal;  // grrr.
  154.         return __r->_M_refdata();
  155.       }
  156.  
  157.   template<typename _CharT, typename _Traits, typename _Alloc>
  158.     _CharT*
  159.     basic_string<_CharT,_Traits, _Alloc>::
  160.     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
  161.     {
  162.       if (__n == 0 && __a == _Alloc())
  163.         return _S_empty_rep()._M_refcopy();
  164.  
  165.       // Check for out_of_range and length_error exceptions.
  166.       _Rep* __r = _Rep::_S_create(__n, __a);
  167.       try
  168.         {
  169.           if (__n)
  170.             traits_type::assign(__r->_M_refdata(), __n, __c);
  171.         }
  172.       catch(...)
  173.         {
  174.           __r->_M_destroy(__a);
  175.           __throw_exception_again;
  176.         }
  177.       __r->_M_length = __n;
  178.       __r->_M_refdata()[__n] = _Rep::_S_terminal;  // grrr
  179.       return __r->_M_refdata();
  180.     }
  181.  
  182.   template<typename _CharT, typename _Traits, typename _Alloc>
  183.     basic_string<_CharT, _Traits, _Alloc>::
  184.     basic_string(const basic_string& __str)
  185.     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()),
  186.                  __str.get_allocator())
  187.     { }
  188.  
  189.   template<typename _CharT, typename _Traits, typename _Alloc>
  190.     basic_string<_CharT, _Traits, _Alloc>::
  191.     basic_string(const _Alloc& __a)
  192.     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
  193.     { }
  194.  
  195.   template<typename _CharT, typename _Traits, typename _Alloc>
  196.     basic_string<_CharT, _Traits, _Alloc>::
  197.     basic_string(const basic_string& __str, size_type __pos, size_type __n)
  198.     : _M_dataplus(_S_construct(__str._M_check(__pos),
  199.                                __str._M_fold(__pos, __n), _Alloc()), _Alloc())
  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,
  205.                  size_type __n, const _Alloc& __a)
  206.     : _M_dataplus(_S_construct(__str._M_check(__pos),
  207.                                __str._M_fold(__pos, __n), __a), __a)
  208.     { }
  209.  
  210.   template<typename _CharT, typename _Traits, typename _Alloc>
  211.     basic_string<_CharT, _Traits, _Alloc>::
  212.     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
  213.     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
  214.     { }
  215.  
  216.   template<typename _CharT, typename _Traits, typename _Alloc>
  217.     basic_string<_CharT, _Traits, _Alloc>::
  218.     basic_string(const _CharT* __s, const _Alloc& __a)
  219.     : _M_dataplus(_S_construct(__s, __s + traits_type::length(__s), __a), __a)
  220.     { }
  221.  
  222.   template<typename _CharT, typename _Traits, typename _Alloc>
  223.     basic_string<_CharT, _Traits, _Alloc>::
  224.     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
  225.     : _M_dataplus(_S_construct(__n, __c, __a), __a)
  226.     { }
  227.  
  228.   template<typename _CharT, typename _Traits, typename _Alloc>
  229.     template<typename _InputIter>
  230.     basic_string<_CharT, _Traits, _Alloc>::
  231.     basic_string(_InputIter __beg, _InputIter __end, const _Alloc& __a)
  232.     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
  233.     { }
  234.  
  235.   template<typename _CharT, typename _Traits, typename _Alloc>
  236.     basic_string<_CharT, _Traits, _Alloc>&
  237.     basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str)
  238.     {
  239.       if (_M_rep() != __str._M_rep())
  240.         {
  241.           // XXX MT
  242.           allocator_type __a = this->get_allocator();
  243.           _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
  244.           _M_rep()->_M_dispose(__a);
  245.           _M_data(__tmp);
  246.         }
  247.       return *this;
  248.     }
  249.  
  250.   template<typename _CharT, typename _Traits, typename _Alloc>
  251.     void
  252.     basic_string<_CharT, _Traits, _Alloc>::_Rep::
  253.     _M_destroy(const _Alloc& __a) throw ()
  254.     {
  255.       size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT);
  256.       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
  257.     }
  258.  
  259.   template<typename _CharT, typename _Traits, typename _Alloc>
  260.     void
  261.     basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
  262.     {
  263.       if (_M_rep()->_M_is_shared())
  264.         _M_mutate(0, 0, 0);
  265.       _M_rep()->_M_set_leaked();
  266.     }
  267.  
  268.   template<typename _CharT, typename _Traits, typename _Alloc>
  269.     void
  270.     basic_string<_CharT, _Traits, _Alloc>::
  271.     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
  272.     {
  273.       size_type       __old_size = this->size();
  274.       const size_type __new_size = __old_size + __len2 - __len1;
  275.       const _CharT*        __src = _M_data()  + __pos + __len1;
  276.       const size_type __how_much = __old_size - __pos - __len1;
  277.      
  278.       if (_M_rep()->_M_is_shared() || __new_size > capacity())
  279.         {
  280.           // Must reallocate.
  281.           allocator_type __a = get_allocator();
  282.           _Rep* __r = _Rep::_S_create(__new_size, __a);
  283.           try
  284.             {
  285.               if (__pos)
  286.                 traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
  287.               if (__how_much)
  288.                 traits_type::copy(__r->_M_refdata() + __pos + __len2,
  289.                                   __src, __how_much);
  290.             }
  291.           catch(...)
  292.             {
  293.               __r->_M_dispose(get_allocator());
  294.               __throw_exception_again;
  295.             }
  296.           _M_rep()->_M_dispose(__a);
  297.           _M_data(__r->_M_refdata());
  298.       }
  299.       else if (__how_much && __len1 != __len2)
  300.         {
  301.           // Work in-place
  302.           traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
  303.         }
  304.       _M_rep()->_M_set_sharable();
  305.       _M_rep()->_M_length = __new_size;
  306.       _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
  307.     // You cannot leave those LWG people alone for a second.
  308.     }
  309.  
  310.   template<typename _CharT, typename _Traits, typename _Alloc>
  311.     void
  312.     basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
  313.     {
  314.       if (__res > this->capacity() || _M_rep()->_M_is_shared())
  315.         {
  316.           if (__res > this->max_size())
  317.             __throw_length_error("basic_string::reserve");
  318.           allocator_type __a = get_allocator();
  319.           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
  320.           _M_rep()->_M_dispose(__a);
  321.           _M_data(__tmp);
  322.         }
  323.     }
  324.  
  325.   template<typename _CharT, typename _Traits, typename _Alloc>
  326.     void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
  327.     {
  328.       if (_M_rep()->_M_is_leaked())
  329.         _M_rep()->_M_set_sharable();
  330.       if (__s._M_rep()->_M_is_leaked())
  331.         __s._M_rep()->_M_set_sharable();
  332.       if (this->get_allocator() == __s.get_allocator())
  333.         {
  334.           _CharT* __tmp = _M_data();
  335.           _M_data(__s._M_data());
  336.           __s._M_data(__tmp);
  337.         }
  338.       // The code below can usually be optimized away.
  339.       else
  340.         {
  341.           basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator());
  342.           basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
  343.                               this->get_allocator());
  344.           *this = __tmp2;
  345.           __s = __tmp1;
  346.         }
  347.     }
  348.  
  349. #ifdef _GLIBCPP_ALLOC_CONTROL
  350.   template<typename _CharT, typename _Traits, typename _Alloc>
  351.     bool (*basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_excess_slop)
  352.     (size_t, size_t) =
  353.     basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_default_excess;
  354. #endif
  355.  
  356.   template<typename _CharT, typename _Traits, typename _Alloc>
  357.     basic_string<_CharT, _Traits, _Alloc>::_Rep*
  358.     basic_string<_CharT, _Traits, _Alloc>::_Rep::
  359.     _S_create(size_t __capacity, const _Alloc& __alloc)
  360.     {
  361.       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
  362. #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
  363.       // 83.  String::npos vs. string::max_size()
  364.       if (__capacity > _S_max_size)
  365. #else
  366.       if (__capacity == npos)
  367. #endif
  368.         __throw_length_error("basic_string::_S_create");
  369.  
  370.       // NB: Need an array of char_type[__capacity], plus a
  371.       // terminating null char_type() element, plus enough for the
  372.       // _Rep data structure. Whew. Seemingly so needy, yet so elemental.
  373.       size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
  374.       // NB: Might throw, but no worries about a leak, mate: _Rep()
  375.       // does not throw.
  376.       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
  377.       _Rep *__p = new (__place) _Rep;
  378.       __p->_M_capacity = __capacity;
  379.       __p->_M_set_sharable();  // one reference
  380.       __p->_M_length = 0;
  381.       return __p;
  382.     }
  383.  
  384.   template<typename _CharT, typename _Traits, typename _Alloc>
  385.     _CharT*
  386.     basic_string<_CharT, _Traits, _Alloc>::_Rep::
  387.     _M_clone(const _Alloc& __alloc, size_type __res)
  388.     {
  389.       _Rep* __r = _Rep::_S_create(_M_length + __res, __alloc);
  390.       if (_M_length)
  391.         {
  392.           try
  393.             { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); }
  394.           catch(...)  
  395.             {
  396.               __r->_M_destroy(__alloc);
  397.               __throw_exception_again;
  398.             }
  399.         }
  400.       __r->_M_length = _M_length;
  401.       return __r->_M_refdata();
  402.     }
  403.  
  404.   template<typename _CharT, typename _Traits, typename _Alloc>
  405.   inline bool
  406. #ifdef _GLIBCPP_ALLOC_CONTROL
  407.     basic_string<_CharT, _Traits, _Alloc>::_Rep::
  408.     _S_default_excess(size_t __s, size_t __r)
  409. #else
  410.     basic_string<_CharT, _Traits, _Alloc>::_Rep::
  411.     _S_excess_slop(size_t __s, size_t __r)
  412. #endif
  413.     {
  414.       return 2 * (__s <= 16 ? 16 : __s) < __r;
  415.     }
  416.  
  417.   template<typename _CharT, typename _Traits, typename _Alloc>
  418.     void
  419.     basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
  420.     {
  421.       if (__n > max_size())
  422.         __throw_length_error("basic_string::resize");
  423.       size_type __size = this->size();
  424.       if (__size < __n)
  425.         this->append(__n - __size, __c);
  426.       else if (__n < __size)
  427.         this->erase(__n);
  428.       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
  429.     }
  430.  
  431.   template<typename _CharT, typename _Traits, typename _Alloc>
  432.     template<typename _InputIter>
  433.       basic_string<_CharT, _Traits, _Alloc>&
  434.       basic_string<_CharT, _Traits, _Alloc>::
  435.       _M_replace(iterator __i1, iterator __i2, _InputIter __k1,
  436.                  _InputIter __k2, input_iterator_tag)
  437.       {
  438.         basic_string __s(__k1, __k2);
  439.         return this->replace(__i1, __i2, __s._M_ibegin(), __s._M_iend());
  440.       }
  441.  
  442.   template<typename _CharT, typename _Traits, typename _Alloc>
  443.     template<typename _ForwardIter>
  444.       basic_string<_CharT, _Traits, _Alloc>&
  445.       basic_string<_CharT, _Traits, _Alloc>::
  446.       _M_replace(iterator __i1, iterator __i2, _ForwardIter __k1,
  447.                  _ForwardIter __k2, forward_iterator_tag)
  448.       {
  449.         size_type __dold = __i2 - __i1;
  450.         size_type __dmax = this->max_size();
  451.         size_type __dnew = static_cast<size_type>(distance(__k1, __k2));
  452.  
  453.         if (__dmax <= __dnew)
  454.           __throw_length_error("basic_string::_M_replace");
  455.         size_type __off = __i1 - _M_ibegin();
  456.         _M_mutate(__off, __dold, __dnew);
  457.         // Invalidated __i1, __i2
  458.         if (__dnew)
  459.           _S_copy_chars(_M_data() + __off, __k1, __k2);
  460.        
  461.         return *this;
  462.       }
  463.  
  464.   template<typename _CharT, typename _Traits, typename _Alloc>
  465.     basic_string<_CharT, _Traits, _Alloc>&
  466.     basic_string<_CharT, _Traits, _Alloc>::
  467.     replace(size_type __pos1, size_type __n1, const basic_string& __str,
  468.             size_type __pos2, size_type __n2)
  469.     {
  470.       return this->replace(_M_check(__pos1), _M_fold(__pos1, __n1),
  471.                            __str._M_check(__pos2),
  472.                            __str._M_fold(__pos2, __n2));
  473.     }
  474.  
  475.   template<typename _CharT, typename _Traits, typename _Alloc>
  476.     basic_string<_CharT,_Traits,_Alloc>&
  477.     basic_string<_CharT,_Traits,_Alloc>::
  478.     append(const basic_string& __str)
  479.     {
  480.       // Iff appending itself, string needs to pre-reserve the
  481.       // correct size so that _M_mutate does not clobber the
  482.       // iterators formed here.
  483.       size_type __size = __str.size();
  484.       size_type __len = __size + this->size();
  485.       if (__len > this->capacity())
  486.         this->reserve(__len);
  487.       return this->replace(_M_iend(), _M_iend(), __str._M_ibegin(),
  488.                            __str._M_iend());
  489.     }
  490.  
  491.   template<typename _CharT, typename _Traits, typename _Alloc>
  492.     basic_string<_CharT,_Traits,_Alloc>&
  493.     basic_string<_CharT,_Traits,_Alloc>::
  494.     append(const basic_string& __str, size_type __pos, size_type __n)
  495.     {
  496.       // Iff appending itself, string needs to pre-reserve the
  497.       // correct size so that _M_mutate does not clobber the
  498.       // iterators formed here.
  499.       size_type __len = min(__str.size() - __pos, __n) + this->size();
  500.       if (__len > this->capacity())
  501.         this->reserve(__len);
  502.       return this->replace(_M_iend(), _M_iend(), __str._M_check(__pos),
  503.                            __str._M_fold(__pos, __n));
  504.     }
  505.  
  506.   template<typename _CharT, typename _Traits, typename _Alloc>
  507.     basic_string<_CharT,_Traits,_Alloc>&
  508.     basic_string<_CharT,_Traits,_Alloc>::
  509.     append(const _CharT* __s, size_type __n)
  510.     {
  511.       size_type __len = __n + this->size();
  512.       if (__len > this->capacity())
  513.         this->reserve(__len);
  514.       return this->replace(_M_iend(), _M_iend(), __s, __s + __n);
  515.     }
  516.  
  517.   template<typename _CharT, typename _Traits, typename _Alloc>
  518.     basic_string<_CharT,_Traits,_Alloc>&
  519.     basic_string<_CharT,_Traits,_Alloc>::
  520.     append(size_type __n, _CharT __c)
  521.     {
  522.       size_type __len = __n + this->size();
  523.       if (__len > this->capacity())
  524.         this->reserve(__len);
  525.        return this->replace(_M_iend(), _M_iend(), __n, __c);
  526.     }
  527.  
  528.   template<typename _CharT, typename _Traits, typename _Alloc>
  529.     basic_string<_CharT,_Traits,_Alloc>
  530.     operator+(const _CharT* __lhs,
  531.              const basic_string<_CharT,_Traits,_Alloc>& __rhs)
  532.     {
  533.       typedef basic_string<_CharT,_Traits,_Alloc> __string_type;
  534.       typedef typename __string_type::size_type   __size_type;
  535.       __size_type __len = _Traits::length(__lhs);
  536.       __string_type __str;
  537.       __str.reserve(__len + __rhs.size());
  538.       __str.append(__lhs, __lhs + __len);
  539.       __str.append(__rhs);
  540.       return __str;
  541.     }
  542.  
  543.   template<typename _CharT, typename _Traits, typename _Alloc>
  544.     basic_string<_CharT,_Traits,_Alloc>
  545.     operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs)
  546.     {
  547.       typedef basic_string<_CharT,_Traits,_Alloc> __string_type;
  548.       typedef typename __string_type::size_type   __size_type;
  549.       __string_type __str;
  550.       __size_type __len = __rhs.size();
  551.       __str.reserve(__len + 1);
  552.       __str.append(__size_type(1), __lhs);
  553.       __str.append(__rhs);
  554.       return __str;
  555.     }
  556.  
  557.   template<typename _CharT, typename _Traits, typename _Alloc>
  558.     basic_string<_CharT, _Traits, _Alloc>&
  559.     basic_string<_CharT, _Traits, _Alloc>::
  560.     replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c)
  561.     {
  562.       size_type __n1 = __i2 - __i1;
  563.       size_type __off1 = __i1 - _M_ibegin();
  564.       if (max_size() - (this->size() - __n1) <= __n2)
  565.         __throw_length_error("basic_string::replace");
  566.       _M_mutate (__off1, __n1, __n2);
  567.       // Invalidated __i1, __i2
  568.       if (__n2)
  569.         traits_type::assign(_M_data() + __off1, __n2, __c);
  570.       return *this;
  571.     }
  572.  
  573.   template<typename _CharT, typename _Traits, typename _Alloc>
  574.     basic_string<_CharT, _Traits, _Alloc>::size_type
  575.     basic_string<_CharT, _Traits, _Alloc>::
  576.     copy(_CharT* __s, size_type __n, size_type __pos) const
  577.     {
  578.       if (__pos > this->size())
  579.         __throw_out_of_range("basic_string::copy");
  580.      
  581.       if (__n > this->size() - __pos)
  582.         __n = this->size() - __pos;
  583.      
  584.       traits_type::copy(__s, _M_data() + __pos, __n);
  585.       // 21.3.5.7 par 3: do not append null.  (good.)
  586.       return __n;
  587.     }
  588.  
  589.   template<typename _CharT, typename _Traits, typename _Alloc>
  590.     basic_string<_CharT, _Traits, _Alloc>::size_type
  591.     basic_string<_CharT, _Traits, _Alloc>::
  592.     find(const _CharT* __s, size_type __pos, size_type __n) const
  593.     {
  594.       size_type __size = this->size();
  595.       size_t __xpos = __pos;
  596.       const _CharT* __data = _M_data();
  597.       for (; __xpos + __n <= __size; ++__xpos)
  598.         if (traits_type::compare(__data + __xpos, __s, __n) == 0)
  599.           return __xpos;
  600.       return npos;
  601.     }
  602.  
  603.   template<typename _CharT, typename _Traits, typename _Alloc>
  604.     basic_string<_CharT, _Traits, _Alloc>::size_type
  605.     basic_string<_CharT, _Traits, _Alloc>::
  606.     find(_CharT __c, size_type __pos) const
  607.     {
  608.       size_type __size = this->size();
  609.       size_type __ret = npos;
  610.       if (__pos < __size)
  611.         {
  612.           const _CharT* __data = _M_data();
  613.           size_type __n = __size - __pos;
  614.           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
  615.           if (__p)
  616.             __ret = __p - __data;
  617.         }
  618.       return __ret;
  619.     }
  620.  
  621.  
  622.   template<typename _CharT, typename _Traits, typename _Alloc>
  623.     basic_string<_CharT, _Traits, _Alloc>::size_type
  624.     basic_string<_CharT, _Traits, _Alloc>::
  625.     rfind(const _CharT* __s, size_type __pos, size_type __n) const
  626.     {
  627.       size_type __size = this->size();
  628.       if (__n <= __size)
  629.         {
  630.           __pos = std::min(__size - __n ,__pos);
  631.           const _CharT* __data = _M_data();
  632.           do
  633.             {
  634.               if (traits_type::compare(__data + __pos, __s, __n) == 0)
  635.                 return __pos;
  636.             }
  637.           while (__pos-- > 0);
  638.         }
  639.       return npos;
  640.     }
  641.  
  642.   template<typename _CharT, typename _Traits, typename _Alloc>
  643.     basic_string<_CharT, _Traits, _Alloc>::size_type
  644.     basic_string<_CharT, _Traits, _Alloc>::
  645.     rfind(_CharT __c, size_type __pos) const
  646.     {
  647.       size_type __size = this->size();
  648.       if (__size)
  649.         {
  650.           size_t __xpos = __size - 1;
  651.           if (__xpos > __pos)
  652.             __xpos = __pos;
  653.      
  654.           for (++__xpos; __xpos-- > 0; )
  655.             if (traits_type::eq(_M_data()[__xpos], __c))
  656.               return __xpos;
  657.         }
  658.       return npos;
  659.     }
  660.  
  661.   template<typename _CharT, typename _Traits, typename _Alloc>
  662.     basic_string<_CharT, _Traits, _Alloc>::size_type
  663.     basic_string<_CharT, _Traits, _Alloc>::
  664.     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
  665.     {
  666.       for (; __n && __pos < this->size(); ++__pos)
  667.         {
  668.           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
  669.           if (__p)
  670.             return __pos;
  671.         }
  672.       return npos;
  673.     }
  674.  
  675.   template<typename _CharT, typename _Traits, typename _Alloc>
  676.     basic_string<_CharT, _Traits, _Alloc>::size_type
  677.     basic_string<_CharT, _Traits, _Alloc>::
  678.     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
  679.     {
  680.       size_type __size = this->size();
  681.       if (__size && __n)
  682.         {
  683.           if (--__size > __pos)
  684.             __size = __pos;
  685.           do
  686.             {
  687.               if (traits_type::find(__s, __n, _M_data()[__size]))
  688.                 return __size;
  689.             }
  690.           while (__size-- != 0);
  691.         }
  692.       return npos;
  693.     }
  694.  
  695.   template<typename _CharT, typename _Traits, typename _Alloc>
  696.     basic_string<_CharT, _Traits, _Alloc>::size_type
  697.     basic_string<_CharT, _Traits, _Alloc>::
  698.     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
  699.     {
  700.       size_t __xpos = __pos;
  701.       for (; __n && __xpos < this->size(); ++__xpos)
  702.         if (!traits_type::find(__s, __n, _M_data()[__xpos]))
  703.           return __xpos;
  704.       return npos;
  705.     }
  706.  
  707.   template<typename _CharT, typename _Traits, typename _Alloc>
  708.     basic_string<_CharT, _Traits, _Alloc>::size_type
  709.     basic_string<_CharT, _Traits, _Alloc>::
  710.     find_first_not_of(_CharT __c, size_type __pos) const
  711.     {
  712.       size_t __xpos = __pos;
  713.       for (; __xpos < this->size(); ++__xpos)
  714.         if (!traits_type::eq(_M_data()[__xpos], __c))
  715.           return __xpos;
  716.       return npos;
  717.     }
  718.  
  719.   template<typename _CharT, typename _Traits, typename _Alloc>
  720.     basic_string<_CharT, _Traits, _Alloc>::size_type
  721.     basic_string<_CharT, _Traits, _Alloc>::
  722.     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
  723.     {
  724.       size_type __size = this->size();
  725.       if (__size && __n)
  726.         {
  727.           if (--__size > __pos)
  728.             __size = __pos;
  729.           do
  730.             {
  731.               if (!traits_type::find(__s, __n, _M_data()[__size]))
  732.                 return __size;
  733.             }
  734.           while (__size--);
  735.         }
  736.       return npos;
  737.     }
  738.  
  739.   template<typename _CharT, typename _Traits, typename _Alloc>
  740.     basic_string<_CharT, _Traits, _Alloc>::size_type
  741.     basic_string<_CharT, _Traits, _Alloc>::
  742.     find_last_not_of(_CharT __c, size_type __pos) const
  743.     {
  744.       size_type __size = this->size();
  745.       if (__size)
  746.         {
  747.           if (--__size > __pos)
  748.             __size = __pos;
  749.           do
  750.             {
  751.               if (!traits_type::eq(_M_data()[__size], __c))
  752.                 return __size;
  753.             }
  754.           while (__size--);
  755.         }
  756.       return npos;
  757.     }
  758.  
  759.   template<typename _CharT, typename _Traits, typename _Alloc>
  760.     int
  761.     basic_string<_CharT, _Traits, _Alloc>::
  762.     compare(size_type __pos, size_type __n, const basic_string& __str) const
  763.     {
  764.       size_type __size = this->size();
  765.       size_type __osize = __str.size();
  766.       if (__pos > __size)
  767.         __throw_out_of_range("basic_string::compare");
  768.      
  769.       size_type __rsize= min(__size - __pos, __n);
  770.       size_type __len = min(__rsize, __osize);
  771.       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
  772.       if (!__r)
  773.         __r = __rsize - __osize;
  774.       return __r;
  775.     }
  776.  
  777.   template<typename _CharT, typename _Traits, typename _Alloc>
  778.     int
  779.     basic_string<_CharT, _Traits, _Alloc>::
  780.     compare(size_type __pos1, size_type __n1, const basic_string& __str,
  781.             size_type __pos2, size_type __n2) const
  782.     {
  783.       size_type __size = this->size();
  784.       size_type __osize = __str.size();
  785.       if (__pos1 > __size || __pos2 > __osize)
  786.         __throw_out_of_range("basic_string::compare");
  787.      
  788.       size_type __rsize = min(__size - __pos1, __n1);
  789.       size_type __rosize = min(__osize - __pos2, __n2);
  790.       size_type __len = min(__rsize, __rosize);
  791.       int __r = traits_type::compare(_M_data() + __pos1,
  792.                                      __str.data() + __pos2, __len);
  793.       if (!__r)
  794.         __r = __rsize - __rosize;
  795.       return __r;
  796.     }
  797.  
  798.  
  799.   template<typename _CharT, typename _Traits, typename _Alloc>
  800.     int
  801.     basic_string<_CharT, _Traits, _Alloc>::
  802.     compare(const _CharT* __s) const
  803.     {
  804.       size_type __size = this->size();
  805.       int __r = traits_type::compare(_M_data(), __s, __size);
  806.       if (!__r)
  807.         __r = __size - traits_type::length(__s);
  808.       return __r;
  809.     }
  810.  
  811.  
  812.   template<typename _CharT, typename _Traits, typename _Alloc>
  813.     int
  814.     basic_string <_CharT,_Traits,_Alloc>::
  815.     compare(size_type __pos, size_type __n1, const _CharT* __s) const
  816.     {
  817.       size_type __size = this->size();
  818.       if (__pos > __size)
  819.         __throw_out_of_range("basic_string::compare");
  820.      
  821.       size_type __osize = traits_type::length(__s);
  822.       size_type __rsize = min(__size - __pos, __n1);
  823.       size_type __len = min(__rsize, __osize);
  824.       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
  825.       if (!__r)
  826.         __r = __rsize - __osize;
  827.       return __r;
  828.     }
  829.  
  830.   template<typename _CharT, typename _Traits, typename _Alloc>
  831.     int
  832.     basic_string <_CharT,_Traits,_Alloc>::
  833.     compare(size_type __pos, size_type __n1, const _CharT* __s,
  834.             size_type __n2) const
  835.     {
  836.       size_type __size = this->size();
  837.       if (__pos > __size)
  838.         __throw_out_of_range("basic_string::compare");
  839.      
  840.       size_type __osize = min(traits_type::length(__s), __n2);
  841.       size_type __rsize = min(__size - __pos, __n1);
  842.       size_type __len = min(__rsize, __osize);
  843.       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
  844.       if (!__r)
  845.         __r = __rsize - __osize;
  846.       return __r;
  847.     }
  848.  
  849.   template <class _CharT, class _Traits, class _Alloc>
  850.     void
  851.     _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str,
  852.                    _CharT* __buf, typename _Alloc::size_type __bufsiz)
  853.     {
  854.       typedef typename _Alloc::size_type size_type;
  855.       size_type __strsize = __str.size();
  856.       size_type __bytes = min(__strsize, __bufsiz - 1);
  857.       _Traits::copy(__buf, __str.data(), __bytes);
  858.       __buf[__bytes] = _CharT();
  859.     }
  860. } // namespace std
  861.  
  862. #endif
  863.