string
上传用户:nizebo
上传日期:2022-05-14
资源大小:882k
文件大小:74k
源码类别:

STL

开发平台:

Visual C++

  1. /*
  2.  * Copyright (c) 1997-1999
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  */ 
  13. #ifndef __SGI_STL_STRING
  14. #define __SGI_STL_STRING
  15. #include <stl_config.h>
  16. #include <stl_string_fwd.h>
  17. #include <ctype.h>        
  18. #include <functional>
  19. #include <stl_ctraits_fns.h>
  20. #include <stdexcept>      
  21. #include <stl_iterator_base.h>
  22. #include <memory>
  23. #include <algorithm>
  24. #ifdef __STL_USE_NEW_IOSTREAMS
  25. #include <iosfwd>
  26. #else /* __STL_USE_NEW_IOSTREAMS */
  27. #include <char_traits.h>
  28. #endif /* __STL_USE_NEW_IOSTREAMS */
  29. // Standard C++ string class.  This class has performance
  30. // characteristics very much like vector<>, meaning, for example, that
  31. // it does not perform reference-count or copy-on-write, and that
  32. // concatenation of two strings is an O(N) operation. 
  33. // There are three reasons why basic_string is not identical to
  34. // vector.  First, basic_string always stores a null character at the
  35. // end; this makes it possible for c_str to be a fast operation.
  36. // Second, the C++ standard requires basic_string to copy elements
  37. // using char_traits<>::assign, char_traits<>::copy, and
  38. // char_traits<>::move.  This means that all of vector<>'s low-level
  39. // operations must be rewritten.  Third, basic_string<> has a lot of
  40. // extra functions in its interface that are convenient but, strictly
  41. // speaking, redundant.
  42. // Additionally, the C++ standard imposes a major restriction: according
  43. // to the standard, the character type _CharT must be a POD type.  This
  44. // implementation weakens that restriction, and allows _CharT to be a
  45. // a user-defined non-POD type.  However, _CharT must still have a
  46. // default constructor.
  47. __STL_BEGIN_NAMESPACE
  48. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  49. #pragma set woff 1174
  50. #pragma set woff 1375
  51. #endif
  52. // A helper class to use a char_traits as a function object.
  53. template <class _Traits>
  54. struct _Not_within_traits
  55.   : public unary_function<typename _Traits::char_type, bool>
  56. {
  57.   typedef const typename _Traits::char_type* _Pointer;
  58.   const _Pointer _M_first;
  59.   const _Pointer _M_last;
  60.   _Not_within_traits(_Pointer __f, _Pointer __l) 
  61.     : _M_first(__f), _M_last(__l) {}
  62.   bool operator()(const typename _Traits::char_type& __x) const {
  63.     return find_if(_M_first, _M_last, 
  64.                    bind1st(_Eq_traits<_Traits>(), __x)) == _M_last;
  65.   }
  66. };
  67. // ------------------------------------------------------------
  68. // Class _String_base.  
  69. // _String_base is a helper class that makes it it easier to write an
  70. // exception-safe version of basic_string.  The constructor allocates,
  71. // but does not initialize, a block of memory.  The destructor
  72. // deallocates, but does not destroy elements within, a block of
  73. // memory.  The destructor assumes that _M_start either is null, or else
  74. // points to a block of memory that was allocated using _String_base's 
  75. // allocator and whose size is _M_end_of_storage - _M_start.
  76. // Additionally, _String_base encapsulates the difference between
  77. // old SGI-style allocators and standard-conforming allocators.
  78. #ifdef __STL_USE_STD_ALLOCATORS
  79. // General base class.
  80. template <class _Tp, class _Alloc, bool _S_instanceless>
  81. class _String_alloc_base {
  82. public:
  83.   typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
  84.   allocator_type get_allocator() const { return _M_data_allocator; }
  85.   _String_alloc_base(const allocator_type& __a)
  86.     : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
  87.     {}
  88. protected:
  89.   _Tp* _M_allocate(size_t __n)
  90.     { return _M_data_allocator.allocate(__n); }
  91.   void _M_deallocate(_Tp* __p, size_t __n) {
  92.     if (__p)
  93.       _M_data_allocator.deallocate(__p, __n); 
  94.   }
  95. protected:
  96.   allocator_type _M_data_allocator;
  97.   _Tp* _M_start;
  98.   _Tp* _M_finish;
  99.   _Tp* _M_end_of_storage;
  100. };
  101. // Specialization for instanceless allocators.
  102. template <class _Tp, class _Alloc>
  103. class _String_alloc_base<_Tp,_Alloc,true> {
  104. public:
  105.   typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
  106.   allocator_type get_allocator() const { return allocator_type(); }
  107.   _String_alloc_base(const allocator_type&)
  108.     : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
  109. protected:
  110.   typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Alloc_type;
  111.   _Tp* _M_allocate(size_t __n)
  112.     { return _Alloc_type::allocate(__n); }
  113.   void _M_deallocate(_Tp* __p, size_t __n)
  114.     { _Alloc_type::deallocate(__p, __n); }
  115. protected:
  116.   _Tp* _M_start;
  117.   _Tp* _M_finish;
  118.   _Tp* _M_end_of_storage;
  119. };
  120. template <class _Tp, class _Alloc>
  121. class _String_base 
  122.   : public _String_alloc_base<_Tp, _Alloc,
  123.                               _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  124. {
  125. protected:
  126.   typedef _String_alloc_base<_Tp, _Alloc,
  127.                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  128.           _Base;
  129.   typedef typename _Base::allocator_type allocator_type;
  130.   void _M_allocate_block(size_t __n) { 
  131.     if (__n <= max_size()) {
  132.       _M_start  = _M_allocate(__n);
  133.       _M_finish = _M_start;
  134.       _M_end_of_storage = _M_start + __n;
  135.     }
  136.     else
  137.       _M_throw_length_error();
  138.   }
  139.   void _M_deallocate_block() 
  140.     { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
  141.   
  142.   size_t max_size() const { return (size_t(-1) / sizeof(_Tp)) - 1; }
  143.   _String_base(const allocator_type& __a) : _Base(__a) { }
  144.   
  145.   _String_base(const allocator_type& __a, size_t __n) : _Base(__a)
  146.     { _M_allocate_block(__n); }
  147.   ~_String_base() { _M_deallocate_block(); }
  148.   void _M_throw_length_error() const;
  149.   void _M_throw_out_of_range() const;
  150. };
  151. #else /* __STL_USE_STD_ALLOCATORS */
  152. template <class _Tp, class _Alloc> class _String_base {
  153. public:
  154.   typedef _Alloc allocator_type;
  155.   allocator_type get_allocator() const { return allocator_type(); }
  156. protected:
  157.   typedef simple_alloc<_Tp, _Alloc> _Alloc_type;
  158.   _Tp* _M_start;
  159.   _Tp* _M_finish;
  160.   _Tp* _M_end_of_storage;
  161.                                 // Precondition: 0 < __n <= max_size().
  162.   _Tp* _M_allocate(size_t __n) { return _Alloc_type::allocate(__n); }
  163.   void _M_deallocate(_Tp* __p, size_t __n) {
  164.     if (__p)
  165.       _Alloc_type::deallocate(__p, __n); 
  166.   }
  167.   void _M_allocate_block(size_t __n) { 
  168.     if (__n <= max_size()) {
  169.       _M_start  = _M_allocate(__n);
  170.       _M_finish = _M_start;
  171.       _M_end_of_storage = _M_start + __n;
  172.     }
  173.     else
  174.       _M_throw_length_error();
  175.   }
  176.   void _M_deallocate_block() 
  177.     { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
  178.   
  179.   size_t max_size() const { return (size_t(-1) / sizeof(_Tp)) - 1; }
  180.   _String_base(const allocator_type&)
  181.     : _M_start(0), _M_finish(0), _M_end_of_storage(0) { }
  182.   
  183.   _String_base(const allocator_type&, size_t __n)
  184.     : _M_start(0), _M_finish(0), _M_end_of_storage(0)
  185.     { _M_allocate_block(__n); }
  186.   ~_String_base() { _M_deallocate_block(); }
  187.   void _M_throw_length_error() const;
  188.   void _M_throw_out_of_range() const;
  189. };
  190. #endif /* __STL_USE_STD_ALLOCATORS */
  191. // Helper functions for exception handling.
  192. template <class _Tp, class _Alloc> 
  193. void _String_base<_Tp,_Alloc>::_M_throw_length_error() const {
  194.   __STL_THROW(length_error("basic_string"));
  195. }
  196. template <class _Tp, class _Alloc> 
  197. void _String_base<_Tp, _Alloc>::_M_throw_out_of_range() const {
  198.   __STL_THROW(out_of_range("basic_string"));
  199. }
  200. // ------------------------------------------------------------
  201. // Class basic_string.  
  202. // Class invariants:
  203. // (1) [start, finish) is a valid range.
  204. // (2) Each iterator in [start, finish) points to a valid object
  205. //     of type value_type.
  206. // (3) *finish is a valid object of type value_type; in particular,
  207. //     it is value_type().
  208. // (4) [finish + 1, end_of_storage) is a valid range.
  209. // (5) Each iterator in [finish + 1, end_of_storage) points to 
  210. //     unininitialized memory.
  211. // Note one important consequence: a string of length n must manage
  212. // a block of memory whose size is at least n + 1.  
  213. template <class _CharT, class _Traits, class _Alloc> 
  214. class basic_string : private _String_base<_CharT,_Alloc> {
  215. public:
  216.   typedef _CharT value_type;
  217.   typedef _Traits traits_type;
  218.   typedef value_type* pointer;
  219.   typedef const value_type* const_pointer;
  220.   typedef value_type& reference;
  221.   typedef const value_type& const_reference;
  222.   typedef size_t size_type;
  223.   typedef ptrdiff_t difference_type;
  224.   typedef const value_type*                const_iterator;
  225.   typedef value_type*                      iterator;
  226. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  227.   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  228.   typedef reverse_iterator<iterator>       reverse_iterator;
  229. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  230.   typedef reverse_iterator<const_iterator, value_type, const_reference, 
  231.                            difference_type>  
  232.           const_reverse_iterator;
  233.   typedef reverse_iterator<iterator, value_type, reference, difference_type>
  234.           reverse_iterator; 
  235. #endif /* __STL_PARTIAL_SPECIALIZATION */
  236.   static const size_type npos;
  237.   typedef _String_base<_CharT,_Alloc> _Base;
  238. public:                         // Constructor, destructor, assignment.
  239.   typedef typename _Base::allocator_type allocator_type;
  240.   allocator_type get_allocator() const { return _Base::get_allocator(); }
  241.   explicit basic_string(const allocator_type& __a = allocator_type())
  242.     : _Base(__a, 8) { _M_terminate_string(); }
  243.   struct _Reserve_t {};
  244.   basic_string(_Reserve_t, size_t __n,
  245.                const allocator_type& __a = allocator_type())
  246.     : _Base(__a, __n + 1) { _M_terminate_string(); }
  247.   basic_string(const basic_string& __s) : _Base(__s.get_allocator()) 
  248.     { _M_range_initialize(__s.begin(), __s.end()); }
  249.   basic_string(const basic_string& __s, size_type __pos, size_type __n = npos,
  250.                const allocator_type& __a = allocator_type()) 
  251.     : _Base(__a) {
  252.     if (__pos > __s.size())
  253.       _M_throw_out_of_range();
  254.     else
  255.       _M_range_initialize(__s.begin() + __pos,
  256.                           __s.begin() + __pos + min(__n, __s.size() - __pos));
  257.   }
  258.   basic_string(const _CharT* __s, size_type __n,
  259.                const allocator_type& __a = allocator_type()) 
  260.     : _Base(__a) 
  261.     { _M_range_initialize(__s, __s + __n); }
  262.   basic_string(const _CharT* __s,
  263.                const allocator_type& __a = allocator_type())
  264.     : _Base(__a) 
  265.     { _M_range_initialize(__s, __s + _Traits::length(__s)); }
  266.   basic_string(size_type __n, _CharT __c,
  267.                const allocator_type& __a = allocator_type())
  268.     : _Base(__a, __n + 1)
  269.   {
  270.     _M_finish = uninitialized_fill_n(_M_start, __n, __c);
  271.     _M_terminate_string();
  272.   }
  273.   // Check to see if _InputIterator is an integer type.  If so, then
  274.   // it can't be an iterator.
  275. #ifdef __STL_MEMBER_TEMPLATES
  276.   template <class _InputIterator>
  277.   basic_string(_InputIterator __f, _InputIterator __l,
  278.                const allocator_type& __a = allocator_type())
  279.     : _Base(__a)
  280.   {
  281.     typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
  282.     _M_initialize_dispatch(__f, __l, _Integral());
  283.   }
  284. #else /* __STL_MEMBER_TEMPLATES */
  285.   basic_string(const _CharT* __f, const _CharT* __l,
  286.                const allocator_type& __a = allocator_type())
  287.     : _Base(__a)
  288.   {
  289.     _M_range_initialize(__f, __l);
  290.   }
  291. #endif
  292.   ~basic_string() { destroy(_M_start, _M_finish + 1); }
  293.     
  294.   basic_string& operator=(const basic_string& __s) {
  295.     if (&__s != this) 
  296.       assign(__s.begin(), __s.end());
  297.     return *this;
  298.   }
  299.   basic_string& operator=(const _CharT* __s) 
  300.     { return assign(__s, __s + _Traits::length(__s)); }
  301.   basic_string& operator=(_CharT __c)
  302.     { return assign(static_cast<size_type>(1), __c); }
  303. protected:                      // Protected members inherited from base.
  304. #ifdef __STL_HAS_NAMESPACES
  305.   using _Base::_M_allocate;
  306.   using _Base::_M_deallocate;
  307.   using _Base::_M_allocate_block;
  308.   using _Base::_M_deallocate_block;
  309.   using _Base::_M_throw_length_error;
  310.   using _Base::_M_throw_out_of_range;
  311.   using _Base::_M_start;
  312.   using _Base::_M_finish;
  313.   using _Base::_M_end_of_storage;
  314. #endif /* __STL_HAS_NAMESPACES */
  315. private:                        // Helper functions used by constructors
  316.                                 // and elsewhere.
  317.   void _M_construct_null(_CharT* __p) {
  318.     construct(__p);
  319. #   ifdef __STL_DEFAULT_CONSTRUCTOR_BUG
  320.     __STL_TRY {
  321.       *__p = (_CharT) 0;
  322.     }
  323.     __STL_UNWIND(destroy(__p));
  324. #   endif
  325.   }
  326.   static _CharT _M_null() {
  327. #   ifndef __STL_DEFAULT_CONSTRUCTOR_BUG
  328.     return _CharT();
  329. #   else
  330.     return (_CharT) 0;
  331. #   endif
  332.   }
  333. private:                        
  334.   // Helper functions used by constructors.  It is a severe error for
  335.   // any of them to be called anywhere except from within constructors.
  336.   void _M_terminate_string() {
  337.     __STL_TRY {
  338.       _M_construct_null(_M_finish);
  339.     }
  340.     __STL_UNWIND(destroy(_M_start, _M_finish));
  341.   }
  342. #ifdef __STL_MEMBER_TEMPLATES
  343.     
  344.   template <class _InputIter>
  345.   void _M_range_initialize(_InputIter __f, _InputIter __l,
  346.                            input_iterator_tag) {
  347.     _M_allocate_block(8);
  348.     _M_construct_null(_M_finish);
  349.     __STL_TRY {
  350.       append(__f, __l);
  351.     }
  352.     __STL_UNWIND(destroy(_M_start, _M_finish + 1));
  353.   }
  354.   template <class _ForwardIter>
  355.   void _M_range_initialize(_ForwardIter __f, _ForwardIter __l, 
  356.                            forward_iterator_tag) {
  357.     difference_type __n = 0;
  358.     distance(__f, __l, __n);
  359.     _M_allocate_block(__n + 1);
  360.     _M_finish = uninitialized_copy(__f, __l, _M_start);
  361.     _M_terminate_string();
  362.   }
  363.   template <class _InputIter>
  364.   void _M_range_initialize(_InputIter __f, _InputIter __l) {
  365.     typedef typename iterator_traits<_InputIter>::iterator_category _Category;
  366.     _M_range_initialize(__f, __l, _Category());
  367.   }
  368.   template <class _Integer>
  369.   void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
  370.     _M_allocate_block(__n + 1);
  371.     _M_finish = uninitialized_fill_n(_M_start, __n, __x);
  372.     _M_terminate_string();
  373.   }
  374.   template <class _InputIter>
  375.   void _M_initialize_dispatch(_InputIter __f, _InputIter __l, __false_type) {
  376.      _M_range_initialize(__f, __l);
  377.   }
  378.     
  379. #else /* __STL_MEMBER_TEMPLATES */
  380.   void _M_range_initialize(const _CharT* __f, const _CharT* __l) {
  381.     ptrdiff_t __n = __l - __f;
  382.     _M_allocate_block(__n + 1);
  383.     _M_finish = uninitialized_copy(__f, __l, _M_start);
  384.     _M_terminate_string();
  385.   }
  386. #endif /* __STL_MEMBER_TEMPLATES */
  387. public:                         // Iterators.
  388.   iterator begin()             { return _M_start; }
  389.   iterator end()               { return _M_finish; }
  390.   const_iterator begin() const { return _M_start; }
  391.   const_iterator end()   const { return _M_finish; }  
  392.   reverse_iterator rbegin()             
  393.     { return reverse_iterator(_M_finish); }
  394.   reverse_iterator rend()               
  395.     { return reverse_iterator(_M_start); }
  396.   const_reverse_iterator rbegin() const 
  397.     { return const_reverse_iterator(_M_finish); }
  398.   const_reverse_iterator rend()   const 
  399.     { return const_reverse_iterator(_M_start); }
  400. public:                         // Size, capacity, etc.
  401.   size_type size() const { return _M_finish - _M_start; }
  402.   size_type length() const { return size(); }
  403.   size_t max_size() const { return _Base::max_size(); }
  404.   void resize(size_type __n, _CharT __c) {
  405.     if (__n <= size())
  406.       erase(begin() + __n, end());
  407.     else
  408.       append(__n - size(), __c);
  409.   }
  410.   void resize(size_type __n) { resize(__n, _M_null()); }
  411.   void reserve(size_type = 0);
  412.   size_type capacity() const { return (_M_end_of_storage - _M_start) - 1; }
  413.   void clear() {
  414.     if (!empty()) {
  415.       _Traits::assign(*_M_start, _M_null());
  416.       destroy(_M_start+1, _M_finish+1);
  417.       _M_finish = _M_start;
  418.     }
  419.   } 
  420.   bool empty() const { return _M_start == _M_finish; }    
  421. public:                         // Element access.
  422.   const_reference operator[](size_type __n) const
  423.     { return *(_M_start + __n); }
  424.   reference operator[](size_type __n)
  425.     { return *(_M_start + __n); }
  426.   const_reference at(size_type __n) const {
  427.     if (__n >= size())
  428.       _M_throw_out_of_range();
  429.     return *(_M_start + __n);
  430.   }
  431.   reference at(size_type __n) {
  432.     if (__n >= size())
  433.       _M_throw_out_of_range();
  434.     return *(_M_start + __n);
  435.   }
  436. public:                         // Append, operator+=, push_back.
  437.   basic_string& operator+=(const basic_string& __s) { return append(__s); }
  438.   basic_string& operator+=(const _CharT* __s) { return append(__s); }
  439.   basic_string& operator+=(_CharT __c) { push_back(__c); return *this; }
  440.   basic_string& append(const basic_string& __s) 
  441.     { return append(__s.begin(), __s.end()); }
  442.   basic_string& append(const basic_string& __s,
  443.                        size_type __pos, size_type __n)
  444.   {
  445.     if (__pos > __s.size())
  446.       _M_throw_out_of_range();
  447.     return append(__s.begin() + __pos,
  448.                   __s.begin() + __pos + min(__n, __s.size() - __pos));
  449.   }
  450.   basic_string& append(const _CharT* __s, size_type __n) 
  451.     { return append(__s, __s+__n); }
  452.   basic_string& append(const _CharT* __s) 
  453.     { return append(__s, __s + _Traits::length(__s)); }
  454.   basic_string& append(size_type __n, _CharT __c);
  455. #ifdef __STL_MEMBER_TEMPLATES
  456.   // Check to see if _InputIterator is an integer type.  If so, then
  457.   // it can't be an iterator.
  458.   template <class _InputIter>
  459.   basic_string& append(_InputIter __first, _InputIter __last) {
  460.     typedef typename _Is_integer<_InputIter>::_Integral _Integral;
  461.     return _M_append_dispatch(__first, __last, _Integral());
  462.   }
  463. #else /* __STL_MEMBER_TEMPLATES */
  464.   basic_string& append(const _CharT* __first, const _CharT* __last);
  465. #endif /* __STL_MEMBER_TEMPLATES */
  466.   void push_back(_CharT __c) {
  467.     if (_M_finish + 1 == _M_end_of_storage)
  468.       reserve(size() + max(size(), static_cast<size_type>(1)));
  469.     _M_construct_null(_M_finish + 1);
  470.     _Traits::assign(*_M_finish, __c);
  471.     ++_M_finish;
  472.   }
  473.   void pop_back() {
  474.     _Traits::assign(*(_M_finish - 1), _M_null());
  475.     destroy(_M_finish);
  476.     --_M_finish;
  477.   }
  478. private:                        // Helper functions for append.
  479. #ifdef __STL_MEMBER_TEMPLATES
  480.   template <class _InputIter>
  481.   basic_string& append(_InputIter __f, _InputIter __l, input_iterator_tag);
  482.   template <class _ForwardIter>
  483.   basic_string& append(_ForwardIter __f, _ForwardIter __l, 
  484.                        forward_iterator_tag);
  485.   template <class _Integer>
  486.   basic_string& _M_append_dispatch(_Integer __n, _Integer __x, __true_type) {
  487.     return append((size_type) __n, (_CharT) __x);
  488.   }
  489.   template <class _InputIter>
  490.   basic_string& _M_append_dispatch(_InputIter __f, _InputIter __l,
  491.                                    __false_type) {
  492.     typedef typename iterator_traits<_InputIter>::iterator_category _Category;
  493.     return append(__f, __l, _Category());
  494.   }
  495. #endif /* __STL_MEMBER_TEMPLATES */
  496. public:                         // Assign
  497.   
  498.   basic_string& assign(const basic_string& __s) 
  499.     { return assign(__s.begin(), __s.end()); }
  500.   basic_string& assign(const basic_string& __s, 
  501.                        size_type __pos, size_type __n) {
  502.     if (__pos > __s.size())
  503.       _M_throw_out_of_range();
  504.     return assign(__s.begin() + __pos, 
  505.                   __s.begin() + __pos + min(__n, __s.size() - __pos));
  506.   }
  507.   basic_string& assign(const _CharT* __s, size_type __n)
  508.     { return assign(__s, __s + __n); }
  509.   basic_string& assign(const _CharT* __s)
  510.     { return assign(__s, __s + _Traits::length(__s)); }
  511.   basic_string& assign(size_type __n, _CharT __c);
  512. #ifdef __STL_MEMBER_TEMPLATES
  513.   // Check to see if _InputIterator is an integer type.  If so, then
  514.   // it can't be an iterator.
  515.   template <class _InputIter>
  516.   basic_string& assign(_InputIter __first, _InputIter __last) {
  517.     typedef typename _Is_integer<_InputIter>::_Integral _Integral;
  518.     return _M_assign_dispatch(__first, __last, _Integral());
  519.   }
  520. #endif  /* __STL_MEMBER_TEMPLATES */
  521.   basic_string& assign(const _CharT* __f, const _CharT* __l);
  522. private:                        // Helper functions for assign.
  523. #ifdef __STL_MEMBER_TEMPLATES
  524.   template <class _Integer>
  525.   basic_string& _M_assign_dispatch(_Integer __n, _Integer __x, __true_type) {
  526.     return assign((size_type) __n, (_CharT) __x);
  527.   }
  528.   template <class _InputIter>
  529.   basic_string& _M_assign_dispatch(_InputIter __f, _InputIter __l,
  530.                                    __false_type);
  531. #endif  /* __STL_MEMBER_TEMPLATES */
  532. public:                         // Insert
  533.   basic_string& insert(size_type __pos, const basic_string& __s) {
  534.     if (__pos > size())
  535.       _M_throw_out_of_range();
  536.     if (size() > max_size() - __s.size())
  537.       _M_throw_length_error();
  538.     insert(_M_start + __pos, __s.begin(), __s.end());
  539.     return *this;
  540.   }
  541.   basic_string& insert(size_type __pos, const basic_string& __s,
  542.                        size_type __beg, size_type __n) {
  543.     if (__pos > size() || __beg > __s.size())
  544.       _M_throw_out_of_range();
  545.     size_type __len = min(__n, __s.size() - __beg);
  546.     if (size() > max_size() - __len)
  547.       _M_throw_length_error();
  548.     insert(_M_start + __pos,
  549.            __s.begin() + __beg, __s.begin() + __beg + __len);
  550.     return *this;
  551.   }
  552.   basic_string& insert(size_type __pos, const _CharT* __s, size_type __n) {
  553.     if (__pos > size())
  554.       _M_throw_out_of_range();
  555.     if (size() > max_size() - __n)
  556.       _M_throw_length_error();
  557.     insert(_M_start + __pos, __s, __s + __n);
  558.     return *this;
  559.   }
  560.   basic_string& insert(size_type __pos, const _CharT* __s) {
  561.     if (__pos > size())
  562.       _M_throw_out_of_range();
  563.     size_type __len = _Traits::length(__s);
  564.     if (size() > max_size() - __len)
  565.       _M_throw_length_error();
  566.     insert(_M_start + __pos, __s, __s + __len);
  567.     return *this;
  568.   }
  569.     
  570.   basic_string& insert(size_type __pos, size_type __n, _CharT __c) {
  571.     if (__pos > size())
  572.       _M_throw_out_of_range();
  573.     if (size() > max_size() - __n)
  574.       _M_throw_length_error();
  575.     insert(_M_start + __pos, __n, __c);
  576.     return *this;
  577.   }
  578.   iterator insert(iterator __p, _CharT __c) {
  579.     if (__p == _M_finish) {
  580.       push_back(__c);
  581.       return _M_finish - 1;
  582.     }
  583.     else
  584.       return _M_insert_aux(__p, __c);
  585.   }
  586.   void insert(iterator __p, size_t __n, _CharT __c);
  587. #ifdef __STL_MEMBER_TEMPLATES
  588.   // Check to see if _InputIterator is an integer type.  If so, then
  589.   // it can't be an iterator.
  590.   template <class _InputIter>
  591.   void insert(iterator __p, _InputIter __first, _InputIter __last) {
  592.     typedef typename _Is_integer<_InputIter>::_Integral _Integral;
  593.     _M_insert_dispatch(__p, __first, __last, _Integral());
  594.   }
  595. #else /* __STL_MEMBER_TEMPLATES */
  596.   void insert(iterator __p, const _CharT* __first, const _CharT* __last);
  597. #endif /* __STL_MEMBER_TEMPLATES */
  598. private:                        // Helper functions for insert.
  599. #ifdef __STL_MEMBER_TEMPLATES
  600.   template <class _InputIter>
  601.   void insert(iterator __p, _InputIter, _InputIter, input_iterator_tag);
  602.   template <class _ForwardIter>
  603.   void insert(iterator __p, _ForwardIter, _ForwardIter, forward_iterator_tag);
  604.   template <class _Integer>
  605.   void _M_insert_dispatch(iterator __p, _Integer __n, _Integer __x,
  606.                           __true_type) {
  607.     insert(__p, (size_type) __n, (_CharT) __x);
  608.   }
  609.   template <class _InputIter>
  610.   void _M_insert_dispatch(iterator __p, _InputIter __first, _InputIter __last,
  611.                           __false_type) {
  612.     typedef typename iterator_traits<_InputIter>::iterator_category _Category;
  613.     insert(__p, __first, __last, _Category());
  614.   }
  615.   template <class _InputIterator>
  616.   void 
  617.   _M_copy(_InputIterator __first, _InputIterator __last, iterator __result) {
  618.     for ( ; __first != __last; ++__first, ++__result)
  619.       _Traits::assign(*__result, *__first);
  620.   }
  621. #endif /* __STL_MEMBER_TEMPLATES */
  622.   iterator _M_insert_aux(iterator, _CharT);
  623.   void 
  624.   _M_copy(const _CharT* __first, const _CharT* __last, _CharT* __result) {
  625.     _Traits::copy(__result, __first, __last - __first);
  626.   }
  627. public:                         // Erase.
  628.   basic_string& erase(size_type __pos = 0, size_type __n = npos) {
  629.     if (__pos > size())
  630.       _M_throw_out_of_range();
  631.     erase(_M_start + __pos, _M_start + __pos + min(__n, size() - __pos));
  632.     return *this;
  633.   }  
  634.   iterator erase(iterator __position) {
  635.                                 // The move includes the terminating null.
  636.     _Traits::move(__position, __position + 1, _M_finish - __position);
  637.     destroy(_M_finish);
  638.     --_M_finish;
  639.     return __position;
  640.   }
  641.   iterator erase(iterator __first, iterator __last) {
  642.     if (__first != __last) {
  643.                                 // The move includes the terminating null.
  644.       _Traits::move(__first, __last, (_M_finish - __last) + 1);
  645.       const iterator __new_finish = _M_finish - (__last - __first);
  646.       destroy(__new_finish + 1, _M_finish + 1);
  647.       _M_finish = __new_finish;
  648.     }
  649.     return __first;
  650.   }
  651. public:                         // Replace.  (Conceptually equivalent
  652.                                 // to erase followed by insert.)
  653.   basic_string& replace(size_type __pos, size_type __n, 
  654.                         const basic_string& __s) {
  655.     if (__pos > size())
  656.       _M_throw_out_of_range();
  657.     const size_type __len = min(__n, size() - __pos);
  658.     if (size() - __len >= max_size() - __s.size())
  659.       _M_throw_length_error();
  660.     return replace(_M_start + __pos, _M_start + __pos + __len, 
  661.                    __s.begin(), __s.end());
  662.   }
  663.   basic_string& replace(size_type __pos1, size_type __n1,
  664.                         const basic_string& __s,
  665.                         size_type __pos2, size_type __n2) {
  666.     if (__pos1 > size() || __pos2 > __s.size())
  667.       _M_throw_out_of_range();
  668.     const size_type __len1 = min(__n1, size() - __pos1);
  669.     const size_type __len2 = min(__n2, __s.size() - __pos2);
  670.     if (size() - __len1 >= max_size() - __len2)
  671.       _M_throw_length_error();
  672.     return replace(_M_start + __pos1, _M_start + __pos1 + __len1,
  673.                    __s._M_start + __pos2, __s._M_start + __pos2 + __len2);
  674.   }
  675.   basic_string& replace(size_type __pos, size_type __n1,
  676.                         const _CharT* __s, size_type __n2) {
  677.     if (__pos > size())
  678.       _M_throw_out_of_range();
  679.     const size_type __len = min(__n1, size() - __pos);
  680.     if (__n2 > max_size() || size() - __len >= max_size() - __n2)
  681.       _M_throw_length_error();
  682.     return replace(_M_start + __pos, _M_start + __pos + __len,
  683.                    __s, __s + __n2);
  684.   }
  685.   basic_string& replace(size_type __pos, size_type __n1,
  686.                         const _CharT* __s) {
  687.     if (__pos > size())
  688.       _M_throw_out_of_range();
  689.     const size_type __len = min(__n1, size() - __pos);
  690.     const size_type __n2 = _Traits::length(__s);
  691.     if (__n2 > max_size() || size() - __len >= max_size() - __n2)
  692.       _M_throw_length_error();
  693.     return replace(_M_start + __pos, _M_start + __pos + __len,
  694.                    __s, __s + _Traits::length(__s));
  695.   }
  696.   basic_string& replace(size_type __pos, size_type __n1,
  697.                         size_type __n2, _CharT __c) {
  698.     if (__pos > size())
  699.       _M_throw_out_of_range();
  700.     const size_type __len = min(__n1, size() - __pos);
  701.     if (__n2 > max_size() || size() - __len >= max_size() - __n2)
  702.       _M_throw_length_error();
  703.     return replace(_M_start + __pos, _M_start + __pos + __len, __n2, __c);
  704.   }
  705.   basic_string& replace(iterator __first, iterator __last, 
  706.                         const basic_string& __s) 
  707.     { return replace(__first, __last, __s.begin(), __s.end()); }
  708.   basic_string& replace(iterator __first, iterator __last,
  709.                         const _CharT* __s, size_type __n) 
  710.     { return replace(__first, __last, __s, __s + __n); }
  711.   basic_string& replace(iterator __first, iterator __last,
  712.                         const _CharT* __s) {
  713.     return replace(__first, __last, __s, __s + _Traits::length(__s));
  714.   }
  715.   basic_string& replace(iterator __first, iterator __last, 
  716.                         size_type __n, _CharT __c);
  717.   // Check to see if _InputIterator is an integer type.  If so, then
  718.   // it can't be an iterator.
  719. #ifdef __STL_MEMBER_TEMPLATES
  720.   template <class _InputIter>
  721.   basic_string& replace(iterator __first, iterator __last,
  722.                         _InputIter __f, _InputIter __l) {
  723.     typedef typename _Is_integer<_InputIter>::_Integral _Integral;
  724.     return _M_replace_dispatch(__first, __last, __f, __l,  _Integral());
  725.   }
  726. #else /* __STL_MEMBER_TEMPLATES */
  727.   basic_string& replace(iterator __first, iterator __last,
  728.                         const _CharT* __f, const _CharT* __l);
  729. #endif /* __STL_MEMBER_TEMPLATES */
  730. private:                        // Helper functions for replace.
  731. #ifdef __STL_MEMBER_TEMPLATES
  732.   template <class _Integer>
  733.   basic_string& _M_replace_dispatch(iterator __first, iterator __last,
  734.                                     _Integer __n, _Integer __x,
  735.                                     __true_type) {
  736.     return replace(__first, __last, (size_type) __n, (_CharT) __x);
  737.   }
  738.   template <class _InputIter>
  739.   basic_string& _M_replace_dispatch(iterator __first, iterator __last,
  740.                                     _InputIter __f, _InputIter __l,
  741.                                     __false_type) {
  742.     typedef typename iterator_traits<_InputIter>::iterator_category _Category;
  743.     return replace(__first, __last, __f, __l, _Category());
  744.   }
  745.   template <class _InputIter>
  746.   basic_string& replace(iterator __first, iterator __last,
  747.                         _InputIter __f, _InputIter __l, input_iterator_tag);
  748.   template <class _ForwardIter>
  749.   basic_string& replace(iterator __first, iterator __last,
  750.                         _ForwardIter __f, _ForwardIter __l, 
  751.                         forward_iterator_tag);
  752. #endif /* __STL_MEMBER_TEMPLATES */
  753. public:                         // Other modifier member functions.
  754.   size_type copy(_CharT* __s, size_type __n, size_type __pos = 0) const {
  755.     if (__pos > size())
  756.       _M_throw_out_of_range();
  757.     const size_type __len = min(__n, size() - __pos);
  758.     _Traits::copy(__s, _M_start + __pos, __len);
  759.     return __len;
  760.   }
  761.   void swap(basic_string& __s) {
  762.     __STD::swap(_M_start, __s._M_start);
  763.     __STD::swap(_M_finish, __s._M_finish);
  764.     __STD::swap(_M_end_of_storage, __s._M_end_of_storage);
  765.   }
  766. public:                         // Conversion to C string.
  767.   const _CharT* c_str() const { return _M_start; }
  768.   const _CharT* data()  const { return _M_start; }
  769. public:                         // find.
  770.   size_type find(const basic_string& __s, size_type __pos = 0) const 
  771.     { return find(__s.begin(), __pos, __s.size()); }
  772.   size_type find(const _CharT* __s, size_type __pos = 0) const 
  773.     { return find(__s, __pos, _Traits::length(__s)); }
  774.   size_type find(const _CharT* __s, size_type __pos, size_type __n) const;
  775.   size_type find(_CharT __c, size_type __pos = 0) const;
  776. public:                         // rfind.
  777.   size_type rfind(const basic_string& __s, size_type __pos = npos) const 
  778.     { return rfind(__s.begin(), __pos, __s.size()); }
  779.   size_type rfind(const _CharT* __s, size_type __pos = npos) const 
  780.     { return rfind(__s, __pos, _Traits::length(__s)); }
  781.   size_type rfind(const _CharT* __s, size_type __pos, size_type __n) const;
  782.   size_type rfind(_CharT __c, size_type __pos = npos) const;
  783. public:                         // find_first_of
  784.   
  785.   size_type find_first_of(const basic_string& __s, size_type __pos = 0) const 
  786.     { return find_first_of(__s.begin(), __pos, __s.size()); }
  787.   size_type find_first_of(const _CharT* __s, size_type __pos = 0) const 
  788.     { return find_first_of(__s, __pos, _Traits::length(__s)); }
  789.   size_type find_first_of(const _CharT* __s, size_type __pos, 
  790.                           size_type __n) const;
  791.   size_type find_first_of(_CharT __c, size_type __pos = 0) const 
  792.     { return find(__c, __pos); }
  793. public:                         // find_last_of
  794.   size_type find_last_of(const basic_string& __s,
  795.                          size_type __pos = npos) const
  796.     { return find_last_of(__s.begin(), __pos, __s.size()); }
  797.   size_type find_last_of(const _CharT* __s, size_type __pos = npos) const 
  798.     { return find_last_of(__s, __pos, _Traits::length(__s)); }
  799.   size_type find_last_of(const _CharT* __s, size_type __pos, 
  800.                          size_type __n) const;
  801.   size_type find_last_of(_CharT __c, size_type __pos = npos) const {
  802.     return rfind(__c, __pos);
  803.   }
  804. public:                         // find_first_not_of
  805.   size_type find_first_not_of(const basic_string& __s, 
  806.                               size_type __pos = 0) const 
  807.     { return find_first_not_of(__s.begin(), __pos, __s.size()); }
  808.   size_type find_first_not_of(const _CharT* __s, size_type __pos = 0) const 
  809.     { return find_first_not_of(__s, __pos, _Traits::length(__s)); }
  810.   size_type find_first_not_of(const _CharT* __s, size_type __pos,
  811.                               size_type __n) const;
  812.   size_type find_first_not_of(_CharT __c, size_type __pos = 0) const;
  813. public:                         // find_last_not_of
  814.   size_type find_last_not_of(const basic_string& __s, 
  815.                              size_type __pos = npos) const
  816.     { return find_last_not_of(__s.begin(), __pos, __s.size()); }
  817.   size_type find_last_not_of(const _CharT* __s, size_type __pos = npos) const
  818.     { return find_last_not_of(__s, __pos, _Traits::length(__s)); }
  819.   size_type find_last_not_of(const _CharT* __s, size_type __pos,
  820.                              size_type __n) const;
  821.   size_type find_last_not_of(_CharT __c, size_type __pos = npos) const;
  822. public:                         // Substring.
  823.   basic_string substr(size_type __pos = 0, size_type __n = npos) const {
  824.     if (__pos > size())
  825.       _M_throw_out_of_range();
  826.     return basic_string(_M_start + __pos, 
  827.                         _M_start + __pos + min(__n, size() - __pos));
  828.   }
  829. public:                         // Compare
  830.   int compare(const basic_string& __s) const 
  831.     { return _M_compare(_M_start, _M_finish, __s._M_start, __s._M_finish); }
  832.   int compare(size_type __pos1, size_type __n1,
  833.               const basic_string& __s) const {
  834.     if (__pos1 > size())
  835.       _M_throw_out_of_range();
  836.     return _M_compare(_M_start + __pos1, 
  837.                       _M_start + __pos1 + min(__n1, size() - __pos1),
  838.                       __s._M_start, __s._M_finish);
  839.   }
  840.     
  841.   int compare(size_type __pos1, size_type __n1,
  842.               const basic_string& __s,
  843.               size_type __pos2, size_type __n2) const {
  844.     if (__pos1 > size() || __pos2 > __s.size())
  845.       _M_throw_out_of_range();
  846.     return _M_compare(_M_start + __pos1, 
  847.                       _M_start + __pos1 + min(__n1, size() - __pos1),
  848.                       __s._M_start + __pos2, 
  849.                       __s._M_start + __pos2 + min(__n2, size() - __pos2));
  850.   }
  851.   int compare(const _CharT* __s) const {
  852.     return _M_compare(_M_start, _M_finish, __s, __s + _Traits::length(__s));
  853.   }
  854.   int compare(size_type __pos1, size_type __n1, const _CharT* __s) const {
  855.     if (__pos1 > size())
  856.       _M_throw_out_of_range();
  857.     return _M_compare(_M_start + __pos1, 
  858.                       _M_start + __pos1 + min(__n1, size() - __pos1),
  859.                       __s, __s + _Traits::length(__s));
  860.   }
  861.   int compare(size_type __pos1, size_type __n1, const _CharT* __s,
  862.               size_type __n2) const {
  863.     if (__pos1 > size())
  864.       _M_throw_out_of_range();
  865.     return _M_compare(_M_start + __pos1, 
  866.                       _M_start + __pos1 + min(__n1, size() - __pos1),
  867.                       __s, __s + __n2);
  868.   }
  869. public:                        // Helper function for compare.
  870.   static int _M_compare(const _CharT* __f1, const _CharT* __l1,
  871.                         const _CharT* __f2, const _CharT* __l2) {
  872.     const ptrdiff_t __n1 = __l1 - __f1;
  873.     const ptrdiff_t __n2 = __l2 - __f2;
  874.     const int cmp = _Traits::compare(__f1, __f2, min(__n1, __n2));
  875.     return cmp != 0 ? cmp : (__n1 < __n2 ? -1 : (__n1 > __n2 ? 1 : 0));
  876.   }
  877. };
  878. // ------------------------------------------------------------
  879. // Non-inline declarations.
  880. template <class _CharT, class _Traits, class _Alloc> 
  881. const basic_string<_CharT,_Traits,_Alloc>::size_type 
  882. basic_string<_CharT,_Traits,_Alloc>::npos 
  883.   = (basic_string<_CharT,_Traits,_Alloc>::size_type) -1;
  884. // Change the string's capacity so that it is large enough to hold
  885. //  at least __res_arg elements, plus the terminating null.  Note that,
  886. //  if __res_arg < capacity(), this member function may actually decrease
  887. //  the string's capacity.
  888. template <class _CharT, class _Traits, class _Alloc> 
  889. void basic_string<_CharT,_Traits,_Alloc>::reserve(size_type __res_arg) {
  890.   if (__res_arg > max_size())
  891.     _M_throw_length_error();
  892.   size_type __n = max(__res_arg, size()) + 1;
  893.   pointer __new_start = _M_allocate(__n);
  894.   pointer __new_finish = __new_start;
  895.   __STL_TRY {
  896.     __new_finish = uninitialized_copy(_M_start, _M_finish, __new_start);
  897.     _M_construct_null(__new_finish);
  898.   }
  899.   __STL_UNWIND((destroy(__new_start, __new_finish), 
  900.                 _M_deallocate(__new_start, __n)));
  901.   destroy(_M_start, _M_finish + 1);
  902.   _M_deallocate_block();
  903.   _M_start = __new_start;
  904.   _M_finish = __new_finish;
  905.   _M_end_of_storage = __new_start + __n;
  906. }
  907. template <class _CharT, class _Traits, class _Alloc> 
  908. basic_string<_CharT,_Traits,_Alloc>& 
  909. basic_string<_CharT,_Traits,_Alloc>::append(size_type __n, _CharT __c) {
  910.   if (__n > max_size() || size() > max_size() - __n)
  911.     _M_throw_length_error();
  912.   if (size() + __n > capacity())
  913.     reserve(size() + max(size(), __n));
  914.   if (__n > 0) {
  915.     uninitialized_fill_n(_M_finish + 1, __n - 1, __c);
  916.     __STL_TRY {
  917.       _M_construct_null(_M_finish + __n);
  918.     }
  919.     __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n));
  920.     _Traits::assign(*_M_finish, __c);
  921.     _M_finish += __n;
  922.   }
  923.   return *this;
  924. }
  925. #ifdef __STL_MEMBER_TEMPLATES
  926. template <class _Tp, class _Traits, class _Alloc> 
  927. template <class _InputIterator>
  928. basic_string<_Tp, _Traits, _Alloc>& 
  929. basic_string<_Tp, _Traits, _Alloc>::append(_InputIterator __first, 
  930.                                           _InputIterator __last,
  931.                                           input_iterator_tag) {
  932.   for ( ; __first != __last ; ++__first)
  933.     push_back(*__first);
  934.   return *this;
  935. }
  936. template <class _Tp, class _Traits, class _Alloc> 
  937. template <class _ForwardIter>
  938. basic_string<_Tp, _Traits, _Alloc>& 
  939. basic_string<_Tp, _Traits, _Alloc>::append(_ForwardIter __first, 
  940.                                            _ForwardIter __last,
  941.                                            forward_iterator_tag) {
  942.   if (__first != __last) {
  943.     const size_type __old_size = size();
  944.     difference_type __n = 0;
  945.     distance(__first, __last, __n);
  946.     if (static_cast<size_type>(__n) > max_size() ||
  947.         __old_size > max_size() - static_cast<size_type>(__n))
  948.       _M_throw_length_error();
  949.     if (__old_size + static_cast<size_type>(__n) > capacity()) {
  950.       const size_type __len = __old_size +
  951.                             max(__old_size, static_cast<size_type>(__n)) + 1;
  952.       pointer __new_start = _M_allocate(__len);
  953.       pointer __new_finish = __new_start;
  954.       __STL_TRY {
  955.         __new_finish = uninitialized_copy(_M_start, _M_finish, __new_start);
  956.         __new_finish = uninitialized_copy(__first, __last, __new_finish);
  957.         _M_construct_null(__new_finish);
  958.       }
  959.       __STL_UNWIND((destroy(__new_start,__new_finish),
  960.                     _M_deallocate(__new_start,__len)));
  961.       destroy(_M_start, _M_finish + 1);
  962.       _M_deallocate_block();
  963.       _M_start = __new_start;
  964.       _M_finish = __new_finish;
  965.       _M_end_of_storage = __new_start + __len; 
  966.     }
  967.     else {
  968.       _ForwardIter __f1 = __first;
  969.       ++__f1;
  970.       uninitialized_copy(__f1, __last, _M_finish + 1);
  971.       __STL_TRY {
  972.         _M_construct_null(_M_finish + __n);
  973.       }
  974.       __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n));
  975.       _Traits::assign(*_M_finish, *__first);
  976.       _M_finish += __n;
  977.     }
  978.   }
  979.   return *this;  
  980. }
  981. #else /* __STL_MEMBER_TEMPLATES */
  982. template <class _Tp, class _Traits, class _Alloc> 
  983. basic_string<_Tp, _Traits, _Alloc>& 
  984. basic_string<_Tp, _Traits, _Alloc>::append(const _Tp* __first,
  985.                                            const _Tp* __last)
  986. {
  987.   if (__first != __last) {
  988.     const size_type __old_size = size();
  989.     ptrdiff_t __n = __last - __first;
  990.     if (__n > max_size() || __old_size > max_size() - __n)
  991.       _M_throw_length_error();
  992.     if (__old_size + __n > capacity()) {
  993.       const size_type __len = __old_size + max(__old_size, (size_t) __n) + 1;
  994.       pointer __new_start = _M_allocate(__len);
  995.       pointer __new_finish = __new_start;
  996.       __STL_TRY {
  997.         __new_finish = uninitialized_copy(_M_start, _M_finish, __new_start);
  998.         __new_finish = uninitialized_copy(__first, __last, __new_finish);
  999.         _M_construct_null(__new_finish);
  1000.       }
  1001.       __STL_UNWIND((destroy(__new_start,__new_finish),
  1002.                     _M_deallocate(__new_start,__len)));
  1003.       destroy(_M_start, _M_finish + 1);
  1004.       _M_deallocate_block();
  1005.       _M_start = __new_start;
  1006.       _M_finish = __new_finish;
  1007.       _M_end_of_storage = __new_start + __len; 
  1008.     }
  1009.     else {
  1010.       const _Tp* __f1 = __first;
  1011.       ++__f1;
  1012.       uninitialized_copy(__f1, __last, _M_finish + 1);
  1013.       __STL_TRY {
  1014.         _M_construct_null(_M_finish + __n);
  1015.       }
  1016.       __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n));
  1017.       _Traits::assign(*_M_finish, *__first);
  1018.       _M_finish += __n;
  1019.     }
  1020.   }
  1021.   return *this;  
  1022. }
  1023. #endif /* __STL_MEMBER_TEMPLATES */
  1024. template <class _CharT, class _Traits, class _Alloc> 
  1025. basic_string<_CharT,_Traits,_Alloc>& 
  1026. basic_string<_CharT,_Traits,_Alloc>::assign(size_type __n, _CharT __c) {
  1027.   if (__n <= size()) {
  1028.     _Traits::assign(_M_start, __n, __c);
  1029.     erase(_M_start + __n, _M_finish);
  1030.   }
  1031.   else {
  1032.     _Traits::assign(_M_start, size(), __c);
  1033.     append(__n - size(), __c);
  1034.   }
  1035.   return *this;
  1036. }
  1037. #ifdef __STL_MEMBER_TEMPLATES
  1038. template <class _CharT, class _Traits, class _Alloc> 
  1039. template <class _InputIter>
  1040. basic_string<_CharT,_Traits,_Alloc>& basic_string<_CharT,_Traits,_Alloc>
  1041.   ::_M_assign_dispatch(_InputIter __f, _InputIter __l, __false_type)
  1042. {
  1043.   pointer __cur = _M_start;
  1044.   while (__f != __l && __cur != _M_finish) {
  1045.     _Traits::assign(*__cur, *__f);
  1046.     ++__f;
  1047.     ++__cur;
  1048.   }
  1049.   if (__f == __l)
  1050.     erase(__cur, _M_finish);
  1051.   else
  1052.     append(__f, __l);
  1053.   return *this;
  1054. }
  1055. #endif /* __STL_MEMBER_TEMPLATES */
  1056. template <class _CharT, class _Traits, class _Alloc> 
  1057. basic_string<_CharT,_Traits,_Alloc>& 
  1058. basic_string<_CharT,_Traits,_Alloc>::assign(const _CharT* __f, 
  1059.                                             const _CharT* __l)
  1060. {
  1061.   const ptrdiff_t __n = __l - __f;
  1062.   if (static_cast<size_type>(__n) <= size()) {
  1063.     _Traits::copy(_M_start, __f, __n);
  1064.     erase(_M_start + __n, _M_finish);
  1065.   }
  1066.   else {
  1067.     _Traits::copy(_M_start, __f, size());
  1068.     append(__f + size(), __l);
  1069.   }
  1070.   return *this;
  1071. }
  1072. template <class _CharT, class _Traits, class _Alloc>
  1073. basic_string<_CharT,_Traits,_Alloc>::iterator 
  1074. basic_string<_CharT,_Traits,_Alloc>
  1075.   ::_M_insert_aux(basic_string<_CharT,_Traits,_Alloc>::iterator __p,
  1076.                   _CharT __c)
  1077. {
  1078.   iterator __new_pos = __p;
  1079.   if (_M_finish + 1 < _M_end_of_storage) {
  1080.     _M_construct_null(_M_finish + 1);
  1081.     _Traits::move(__p + 1, __p, _M_finish - __p);
  1082.     _Traits::assign(*__p, __c);
  1083.     ++_M_finish;
  1084.   }
  1085.   else {
  1086.     const size_type __old_len = size();
  1087.     const size_type __len = __old_len +
  1088.                             max(__old_len, static_cast<size_type>(1)) + 1;
  1089.     iterator __new_start = _M_allocate(__len);
  1090.     iterator __new_finish = __new_start;
  1091.     __STL_TRY {
  1092.       __new_pos = uninitialized_copy(_M_start, __p, __new_start);
  1093.       construct(__new_pos, __c);
  1094.       __new_finish = __new_pos + 1;
  1095.       __new_finish = uninitialized_copy(__p, _M_finish, __new_finish);
  1096.       _M_construct_null(__new_finish);
  1097.     }
  1098.     __STL_UNWIND((destroy(__new_start,__new_finish), 
  1099.                   _M_deallocate(__new_start,__len)));
  1100.     destroy(_M_start, _M_finish + 1);
  1101.     _M_deallocate_block();
  1102.     _M_start = __new_start;
  1103.     _M_finish = __new_finish;
  1104.     _M_end_of_storage = __new_start + __len;
  1105.   }
  1106.   return __new_pos;
  1107. }
  1108. template <class _CharT, class _Traits, class _Alloc>
  1109. void basic_string<_CharT,_Traits,_Alloc>
  1110.   ::insert(basic_string<_CharT,_Traits,_Alloc>::iterator __position,
  1111.            size_t __n, _CharT __c)
  1112. {
  1113.   if (__n != 0) {
  1114.     if (size_type(_M_end_of_storage - _M_finish) >= __n + 1) {
  1115.       const size_type __elems_after = _M_finish - __position;
  1116.       iterator __old_finish = _M_finish;
  1117.       if (__elems_after >= __n) {
  1118.         uninitialized_copy((_M_finish - __n) + 1, _M_finish + 1,
  1119.                            _M_finish + 1);
  1120.         _M_finish += __n;
  1121.         _Traits::move(__position + __n,
  1122.                       __position, (__elems_after - __n) + 1);
  1123.         _Traits::assign(__position, __n, __c);
  1124.       }
  1125.       else {
  1126.         uninitialized_fill_n(_M_finish + 1, __n - __elems_after - 1, __c);
  1127.         _M_finish += __n - __elems_after;
  1128.         __STL_TRY {
  1129.           uninitialized_copy(__position, __old_finish + 1, _M_finish);
  1130.           _M_finish += __elems_after;
  1131.         }
  1132.         __STL_UNWIND((destroy(__old_finish + 1, _M_finish), 
  1133.                       _M_finish = __old_finish));
  1134.         _Traits::assign(__position, __elems_after + 1, __c);
  1135.       }
  1136.     }
  1137.     else {
  1138.       const size_type __old_size = size();        
  1139.       const size_type __len = __old_size + max(__old_size, __n) + 1;
  1140.       iterator __new_start = _M_allocate(__len);
  1141.       iterator __new_finish = __new_start;
  1142.       __STL_TRY {
  1143.         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  1144.         __new_finish = uninitialized_fill_n(__new_finish, __n, __c);
  1145.         __new_finish = uninitialized_copy(__position, _M_finish,
  1146.                                           __new_finish);
  1147.         _M_construct_null(__new_finish);
  1148.       }
  1149.       __STL_UNWIND((destroy(__new_start,__new_finish),
  1150.                     _M_deallocate(__new_start,__len)));
  1151.       destroy(_M_start, _M_finish + 1);
  1152.       _M_deallocate_block();
  1153.       _M_start = __new_start;
  1154.       _M_finish = __new_finish;
  1155.       _M_end_of_storage = __new_start + __len;    
  1156.     }
  1157.   }
  1158. }
  1159. #ifdef __STL_MEMBER_TEMPLATES
  1160. template <class _Tp, class _Traits, class _Alloc>
  1161. template <class _InputIter>
  1162. void basic_string<_Tp, _Traits, _Alloc>::insert(iterator __p,
  1163.                                                 _InputIter __first, 
  1164.                                                 _InputIter __last,
  1165.                                                 input_iterator_tag)
  1166. {
  1167.   for ( ; __first != __last; ++__first) {
  1168.     __p = insert(__p, *__first);
  1169.     ++__p;
  1170.   }
  1171. }
  1172. template <class _CharT, class _Traits, class _Alloc>
  1173. template <class _ForwardIter>
  1174. void 
  1175. basic_string<_CharT,_Traits,_Alloc>::insert(iterator __position,
  1176.                                             _ForwardIter __first, 
  1177.                                             _ForwardIter __last,
  1178.                                             forward_iterator_tag)
  1179. {
  1180.   if (__first != __last) {
  1181.     difference_type __n = 0;
  1182.     distance(__first, __last, __n);
  1183.     if (_M_end_of_storage - _M_finish >= __n + 1) {
  1184.       const difference_type __elems_after = _M_finish - __position;
  1185.       iterator __old_finish = _M_finish;
  1186.       if (__elems_after >= __n) {
  1187.         uninitialized_copy((_M_finish - __n) + 1, _M_finish + 1,
  1188.                            _M_finish + 1);
  1189.         _M_finish += __n;
  1190.         _Traits::move(__position + __n,
  1191.                       __position, (__elems_after - __n) + 1);
  1192.         _M_copy(__first, __last, __position);
  1193.       }
  1194.       else {
  1195.         _ForwardIter __mid = __first;
  1196.         advance(__mid, __elems_after + 1);
  1197.         uninitialized_copy(__mid, __last, _M_finish + 1);
  1198.         _M_finish += __n - __elems_after;
  1199.         __STL_TRY {
  1200.           uninitialized_copy(__position, __old_finish + 1, _M_finish);
  1201.           _M_finish += __elems_after;
  1202.         }
  1203.         __STL_UNWIND((destroy(__old_finish + 1, _M_finish), 
  1204.                       _M_finish = __old_finish));
  1205.         _M_copy(__first, __mid, __position);
  1206.       }
  1207.     }
  1208.     else {
  1209.       const size_type __old_size = size();        
  1210.       const size_type __len
  1211.         = __old_size + max(__old_size, static_cast<size_type>(__n)) + 1;
  1212.       pointer __new_start = _M_allocate(__len);
  1213.       pointer __new_finish = __new_start;
  1214.       __STL_TRY {
  1215.         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  1216.         __new_finish = uninitialized_copy(__first, __last, __new_finish);
  1217.         __new_finish
  1218.           = uninitialized_copy(__position, _M_finish, __new_finish);
  1219.         _M_construct_null(__new_finish);
  1220.       }
  1221.       __STL_UNWIND((destroy(__new_start,__new_finish),
  1222.                     _M_deallocate(__new_start,__len)));
  1223.       destroy(_M_start, _M_finish + 1);
  1224.       _M_deallocate_block();
  1225.       _M_start = __new_start;
  1226.       _M_finish = __new_finish;
  1227.       _M_end_of_storage = __new_start + __len; 
  1228.     }
  1229.   }
  1230. }
  1231. #else /* __STL_MEMBER_TEMPLATES */
  1232. template <class _CharT, class _Traits, class _Alloc>
  1233. void 
  1234. basic_string<_CharT,_Traits,_Alloc>::insert(iterator __position,
  1235.                                             const _CharT* __first, 
  1236.                                             const _CharT* __last)
  1237. {
  1238.   if (__first != __last) {
  1239.     const ptrdiff_t __n = __last - __first;
  1240.     if (_M_end_of_storage - _M_finish >= __n + 1) {
  1241.       const ptrdiff_t __elems_after = _M_finish - __position;
  1242.       iterator __old_finish = _M_finish;
  1243.       if (__elems_after >= __n) {
  1244.         uninitialized_copy((_M_finish - __n) + 1, _M_finish + 1,
  1245.                            _M_finish + 1);
  1246.         _M_finish += __n;
  1247.         _Traits::move(__position + __n,
  1248.                       __position, (__elems_after - __n) + 1);
  1249.         _M_copy(__first, __last, __position);
  1250.       }
  1251.       else {
  1252.         const _CharT* __mid = __first;
  1253.         advance(__mid, __elems_after + 1);
  1254.         uninitialized_copy(__mid, __last, _M_finish + 1);
  1255.         _M_finish += __n - __elems_after;
  1256.         __STL_TRY {
  1257.           uninitialized_copy(__position, __old_finish + 1, _M_finish);
  1258.           _M_finish += __elems_after;
  1259.         }
  1260.         __STL_UNWIND((destroy(__old_finish + 1, _M_finish), 
  1261.                       _M_finish = __old_finish));
  1262.         _M_copy(__first, __mid, __position);
  1263.       }
  1264.     }
  1265.     else {
  1266.       const size_type __old_size = size();        
  1267.       const size_type __len
  1268.         = __old_size + max(__old_size, static_cast<size_type>(__n)) + 1;
  1269.       pointer __new_start = _M_allocate(__len);
  1270.       pointer __new_finish = __new_start;
  1271.       __STL_TRY {
  1272.         __new_finish = uninitialized_copy(_M_start, __position, __new_start);
  1273.         __new_finish = uninitialized_copy(__first, __last, __new_finish);
  1274.         __new_finish
  1275.           = uninitialized_copy(__position, _M_finish, __new_finish);
  1276.         _M_construct_null(__new_finish);
  1277.       }
  1278.       __STL_UNWIND((destroy(__new_start,__new_finish),
  1279.                     _M_deallocate(__new_start,__len)));
  1280.       destroy(_M_start, _M_finish + 1);
  1281.       _M_deallocate_block();
  1282.       _M_start = __new_start;
  1283.       _M_finish = __new_finish;
  1284.       _M_end_of_storage = __new_start + __len; 
  1285.     }
  1286.   }
  1287. }
  1288. #endif /* __STL_MEMBER_TEMPLATES */
  1289. template <class _CharT, class _Traits, class _Alloc>
  1290. basic_string<_CharT,_Traits,_Alloc>&
  1291. basic_string<_CharT,_Traits,_Alloc>
  1292.   ::replace(iterator __first, iterator __last, size_type __n, _CharT __c)
  1293. {
  1294.   const size_type __len = static_cast<size_type>(__last - __first);
  1295.   if (__len >= __n) {
  1296.     _Traits::assign(__first, __n, __c);
  1297.     erase(__first + __n, __last);
  1298.   }
  1299.   else {
  1300.     _Traits::assign(__first, __len, __c);
  1301.     insert(__last, __n - __len, __c);
  1302.   }
  1303.   return *this;
  1304. }
  1305. #ifdef __STL_MEMBER_TEMPLATES
  1306. template <class _CharT, class _Traits, class _Alloc>
  1307. template <class _InputIter>
  1308. basic_string<_CharT,_Traits,_Alloc>&
  1309. basic_string<_CharT,_Traits,_Alloc>
  1310.   ::replace(iterator __first, iterator __last, _InputIter __f, _InputIter __l,
  1311.             input_iterator_tag) 
  1312. {
  1313.   for ( ; __first != __last && __f != __l; ++__first, ++__f)
  1314.     _Traits::assign(*__first, *__f);
  1315.   if (__f == __l)
  1316.     erase(__first, __last);
  1317.   else
  1318.     insert(__last, __f, __l);
  1319.   return *this;
  1320. }
  1321. template <class _CharT, class _Traits, class _Alloc>
  1322. template <class _ForwardIter>
  1323. basic_string<_CharT,_Traits,_Alloc>&
  1324. basic_string<_CharT,_Traits,_Alloc>
  1325.   ::replace(iterator __first, iterator __last,
  1326.             _ForwardIter __f, _ForwardIter __l,
  1327.             forward_iterator_tag) 
  1328. {
  1329.   difference_type __n = 0;
  1330.   distance(__f, __l, __n);
  1331.   const difference_type __len = __last - __first;
  1332.   if (__len >= __n) {
  1333.     _M_copy(__f, __l, __first);
  1334.     erase(__first + __n, __last);
  1335.   }
  1336.   else {
  1337.     _ForwardIter __m = __f;
  1338.     advance(__m, __len);
  1339.     _M_copy(__f, __m, __first);
  1340.     insert(__last, __m, __l);
  1341.   }
  1342.   return *this;
  1343. }
  1344. #else /* __STL_MEMBER_TEMPLATES */
  1345. template <class _CharT, class _Traits, class _Alloc>
  1346. basic_string<_CharT,_Traits,_Alloc>&
  1347. basic_string<_CharT,_Traits,_Alloc>
  1348.   ::replace(iterator __first, iterator __last,
  1349.             const _CharT* __f, const _CharT* __l)
  1350. {
  1351.   const ptrdiff_t         __n = __l - __f;
  1352.   const difference_type __len = __last - __first;
  1353.   if (__len >= __n) {
  1354.     _M_copy(__f, __l, __first);
  1355.     erase(__first + __n, __last);
  1356.   }
  1357.   else {
  1358.     const _CharT* __m = __f + __len;
  1359.     _M_copy(__f, __m, __first);
  1360.     insert(__last, __m, __l);
  1361.   }
  1362.   return *this;
  1363. }
  1364. #endif /* __STL_MEMBER_TEMPLATES */
  1365. template <class _CharT, class _Traits, class _Alloc>
  1366. basic_string<_CharT,_Traits,_Alloc>::size_type
  1367. basic_string<_CharT,_Traits,_Alloc>
  1368.   ::find(const _CharT* __s, size_type __pos, size_type __n) const 
  1369. {
  1370.   if (__pos + __n > size())
  1371.     return npos;
  1372.   else {
  1373.     const const_iterator __result =
  1374.       search(_M_start + __pos, _M_finish, 
  1375.              __s, __s + __n, _Eq_traits<_Traits>());
  1376.     return __result != _M_finish ? __result - begin() : npos;
  1377.   }
  1378. }
  1379. template <class _CharT, class _Traits, class _Alloc>
  1380. basic_string<_CharT,_Traits,_Alloc>::size_type
  1381. basic_string<_CharT,_Traits,_Alloc>
  1382.   ::find(_CharT __c, size_type __pos) const 
  1383. {
  1384.   if (__pos >= size())
  1385.     return npos;
  1386.   else {
  1387.     const const_iterator __result =
  1388.       find_if(_M_start + __pos, _M_finish,
  1389.               bind2nd(_Eq_traits<_Traits>(), __c));
  1390.     return __result != _M_finish ? __result - begin() : npos;
  1391.   }
  1392. }    
  1393. template <class _CharT, class _Traits, class _Alloc>
  1394. basic_string<_CharT,_Traits,_Alloc>::size_type
  1395. basic_string<_CharT,_Traits,_Alloc>
  1396.   ::rfind(const _CharT* __s, size_type __pos, size_type __n) const 
  1397. {
  1398.   const size_t __len = size();
  1399.   if (__n > __len)
  1400.     return npos;
  1401.   else if (__n == 0)
  1402.     return min(__len, __pos);
  1403.   else {
  1404.     const const_iterator __last = begin() + min(__len - __n, __pos) + __n;
  1405.     const const_iterator __result = find_end(begin(), __last,
  1406.                                            __s, __s + __n,
  1407.                                            _Eq_traits<_Traits>());
  1408.     return __result != __last ? __result - begin() : npos;
  1409.   }
  1410. }
  1411. template <class _CharT, class _Traits, class _Alloc>
  1412. basic_string<_CharT,_Traits,_Alloc>::size_type
  1413. basic_string<_CharT,_Traits,_Alloc>
  1414.   ::rfind(_CharT __c, size_type __pos) const 
  1415. {
  1416.   const size_type __len = size();
  1417.   if (__len < 1)
  1418.     return npos;
  1419.   else {
  1420.     const const_iterator __last = begin() + min(__len - 1, __pos) + 1;
  1421.     const_reverse_iterator __rresult =
  1422.       find_if(const_reverse_iterator(__last), rend(),
  1423.               bind2nd(_Eq_traits<_Traits>(), __c));
  1424.     return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
  1425.   }
  1426. }
  1427. template <class _CharT, class _Traits, class _Alloc>
  1428. basic_string<_CharT,_Traits,_Alloc>::size_type
  1429. basic_string<_CharT,_Traits,_Alloc>
  1430.   ::find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
  1431. {
  1432.   if (__pos >= size())
  1433.     return npos;
  1434.   else {
  1435.     const_iterator __result = __STD::find_first_of(begin() + __pos, end(),
  1436.                                                    __s, __s + __n,
  1437.                                                    _Eq_traits<_Traits>());
  1438.     return __result != _M_finish ? __result - begin() : npos;
  1439.   }
  1440. }
  1441. template <class _CharT, class _Traits, class _Alloc>
  1442. basic_string<_CharT,_Traits,_Alloc>::size_type
  1443. basic_string<_CharT,_Traits,_Alloc>
  1444.   ::find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
  1445. {
  1446.   const size_type __len = size();
  1447.   if (__len < 1)
  1448.     return npos;
  1449.   else {
  1450.     const const_iterator __last = _M_start + min(__len - 1, __pos) + 1;
  1451.     const const_reverse_iterator __rresult =
  1452.       __STD::find_first_of(const_reverse_iterator(__last), rend(),
  1453.                            __s, __s + __n,
  1454.                            _Eq_traits<_Traits>());
  1455.     return __rresult != rend() ? (__rresult.base() - 1) - _M_start : npos;
  1456.   }
  1457. }
  1458. template <class _CharT, class _Traits, class _Alloc>
  1459. basic_string<_CharT,_Traits,_Alloc>::size_type
  1460. basic_string<_CharT,_Traits,_Alloc>
  1461.   ::find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
  1462. {
  1463.   if (__pos > size())
  1464.     return npos;
  1465.   else {
  1466.     const_iterator __result = find_if(_M_start + __pos, _M_finish,
  1467.                                 _Not_within_traits<_Traits>(__s, __s + __n));
  1468.     return __result != _M_finish ? __result - _M_start : npos;
  1469.   }
  1470. }
  1471. template <class _CharT, class _Traits, class _Alloc>
  1472. basic_string<_CharT,_Traits,_Alloc>::size_type
  1473. basic_string<_CharT,_Traits,_Alloc>
  1474.   ::find_first_not_of(_CharT __c, size_type __pos) const
  1475. {
  1476.   if (__pos > size())
  1477.     return npos;
  1478.   else {
  1479.     const_iterator __result
  1480.       = find_if(begin() + __pos, end(),
  1481.                 not1(bind2nd(_Eq_traits<_Traits>(), __c)));
  1482.     return __result != _M_finish ? __result - begin() : npos;
  1483.   }
  1484. }    
  1485. template <class _CharT, class _Traits, class _Alloc>
  1486. basic_string<_CharT,_Traits,_Alloc>::size_type
  1487. basic_string<_CharT,_Traits,_Alloc>
  1488.   ::find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 
  1489. {
  1490.   const size_type __len = size();
  1491.   if (__len < 1)
  1492.     return npos;
  1493.   else {
  1494.     const const_iterator __last = begin() + min(__len - 1, __pos) + 1;
  1495.     const const_reverse_iterator __rresult =
  1496.       find_if(const_reverse_iterator(__last), rend(),
  1497.               _Not_within_traits<_Traits>(__s, __s + __n));
  1498.     return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
  1499.   }
  1500. }
  1501. template <class _Tp, class _Traits, class _Alloc>
  1502. basic_string<_Tp, _Traits, _Alloc>::size_type
  1503. basic_string<_Tp, _Traits, _Alloc>
  1504.   ::find_last_not_of(_Tp __c, size_type __pos) const 
  1505. {
  1506.   const size_type __len = size();
  1507.   if (__len < 1)
  1508.     return npos;
  1509.   else {
  1510.     const const_iterator __last = begin() + min(__len - 1, __pos) + 1;
  1511.     const_reverse_iterator __rresult =
  1512.       find_if(const_reverse_iterator(__last), rend(),
  1513.               not1(bind2nd(_Eq_traits<_Traits>(), __c)));
  1514.     return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
  1515.   }
  1516. }
  1517. // ------------------------------------------------------------
  1518. // Non-member functions.
  1519. // Operator+
  1520. template <class _CharT, class _Traits, class _Alloc>
  1521. inline basic_string<_CharT,_Traits,_Alloc>
  1522. operator+(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1523.           const basic_string<_CharT,_Traits,_Alloc>& __y)
  1524. {
  1525.   typedef basic_string<_CharT,_Traits,_Alloc> _Str;
  1526.   typedef typename _Str::_Reserve_t _Reserve_t;
  1527.   _Reserve_t __reserve;
  1528.   _Str __result(__reserve, __x.size() + __y.size(), __x.get_allocator());
  1529.   __result.append(__x);
  1530.   __result.append(__y);
  1531.   return __result;
  1532. }
  1533. template <class _CharT, class _Traits, class _Alloc>
  1534. inline basic_string<_CharT,_Traits,_Alloc>
  1535. operator+(const _CharT* __s,
  1536.           const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1537.   typedef basic_string<_CharT,_Traits,_Alloc> _Str;
  1538.   typedef typename _Str::_Reserve_t _Reserve_t;
  1539.   _Reserve_t __reserve;
  1540.   const size_t __n = _Traits::length(__s);
  1541.   _Str __result(__reserve, __n + __y.size());
  1542.   __result.append(__s, __s + __n);
  1543.   __result.append(__y);
  1544.   return __result;
  1545. }
  1546. template <class _CharT, class _Traits, class _Alloc>
  1547. inline basic_string<_CharT,_Traits,_Alloc>
  1548. operator+(_CharT __c,
  1549.           const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1550.   typedef basic_string<_CharT,_Traits,_Alloc> _Str;
  1551.   typedef typename _Str::_Reserve_t _Reserve_t;
  1552.   _Reserve_t __reserve;
  1553.   _Str __result(__reserve, 1 + __y.size());
  1554.   __result.push_back(__c);
  1555.   __result.append(__y);
  1556.   return __result;
  1557. }
  1558. template <class _CharT, class _Traits, class _Alloc>
  1559. inline basic_string<_CharT,_Traits,_Alloc>
  1560. operator+(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1561.           const _CharT* __s) {
  1562.   typedef basic_string<_CharT,_Traits,_Alloc> _Str;
  1563.   typedef typename _Str::_Reserve_t _Reserve_t;
  1564.   _Reserve_t __reserve;
  1565.   const size_t __n = _Traits::length(__s);
  1566.   _Str __result(__reserve, __x.size() + __n, __x.get_allocator());
  1567.   __result.append(__x);
  1568.   __result.append(__s, __s + __n);
  1569.   return __result;
  1570. }
  1571. template <class _CharT, class _Traits, class _Alloc>
  1572. inline basic_string<_CharT,_Traits,_Alloc>
  1573. operator+(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1574.           const _CharT __c) {
  1575.   typedef basic_string<_CharT,_Traits,_Alloc> _Str;
  1576.   typedef typename _Str::_Reserve_t _Reserve_t;
  1577.   _Reserve_t __reserve;
  1578.   _Str __result(__reserve, __x.size() + 1, __x.get_allocator());
  1579.   __result.append(__x);
  1580.   __result.push_back(__c);
  1581.   return __result;
  1582. }
  1583. // Operator== and operator!=
  1584. template <class _CharT, class _Traits, class _Alloc>
  1585. inline bool
  1586. operator==(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1587.            const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1588.   return __x.size() == __y.size() &&
  1589.          _Traits::compare(__x.data(), __y.data(), __x.size()) == 0;
  1590. }
  1591. template <class _CharT, class _Traits, class _Alloc>
  1592. inline bool
  1593. operator==(const _CharT* __s,
  1594.            const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1595.   size_t __n = _Traits::length(__s);
  1596.   return __n == __y.size() && _Traits::compare(__s, __y.data(), __n) == 0;
  1597. }
  1598. template <class _CharT, class _Traits, class _Alloc>
  1599. inline bool
  1600. operator==(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1601.            const _CharT* __s) {
  1602.   size_t __n = _Traits::length(__s);
  1603.   return __x.size() == __n && _Traits::compare(__x.data(), __s, __n) == 0;
  1604. }
  1605. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  1606. template <class _CharT, class _Traits, class _Alloc>
  1607. inline bool
  1608. operator!=(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1609.            const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1610.   return !(__x == __y);
  1611. }
  1612. template <class _CharT, class _Traits, class _Alloc>
  1613. inline bool
  1614. operator!=(const _CharT* __s,
  1615.            const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1616.   return !(__s == __y);
  1617. }
  1618. template <class _CharT, class _Traits, class _Alloc>
  1619. inline bool
  1620. operator!=(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1621.            const _CharT* __s) {
  1622.   return !(__x == __s);
  1623. }
  1624. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  1625. // Operator< (and also >, <=, and >=).
  1626. template <class _CharT, class _Traits, class _Alloc>
  1627. inline bool
  1628. operator<(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1629.           const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1630.   return basic_string<_CharT,_Traits,_Alloc>
  1631.     ::_M_compare(__x.begin(), __x.end(), __y.begin(), __y.end()) < 0;
  1632. }
  1633. template <class _CharT, class _Traits, class _Alloc>
  1634. inline bool
  1635. operator<(const _CharT* __s,
  1636.           const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1637.   size_t __n = _Traits::length(__s);
  1638.   return basic_string<_CharT,_Traits,_Alloc>
  1639.     ::_M_compare(__s, __s + __n, __y.begin(), __y.end()) < 0;
  1640. }
  1641. template <class _CharT, class _Traits, class _Alloc>
  1642. inline bool
  1643. operator<(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1644.           const _CharT* __s) {
  1645.   size_t __n = _Traits::length(__s);
  1646.   return basic_string<_CharT,_Traits,_Alloc>
  1647.     ::_M_compare(__x.begin(), __x.end(), __s, __s + __n) < 0;
  1648. }
  1649. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  1650. template <class _CharT, class _Traits, class _Alloc>
  1651. inline bool
  1652. operator>(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1653.           const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1654.   return __y < __x;
  1655. }
  1656. template <class _CharT, class _Traits, class _Alloc>
  1657. inline bool
  1658. operator>(const _CharT* __s,
  1659.           const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1660.   return __y < __s;
  1661. }
  1662. template <class _CharT, class _Traits, class _Alloc>
  1663. inline bool
  1664. operator>(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1665.           const _CharT* __s) {
  1666.   return __s < __x;
  1667. }
  1668. template <class _CharT, class _Traits, class _Alloc>
  1669. inline bool
  1670. operator<=(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1671.            const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1672.   return !(__y < __x);
  1673. }
  1674. template <class _CharT, class _Traits, class _Alloc>
  1675. inline bool
  1676. operator<=(const _CharT* __s,
  1677.            const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1678.   return !(__y < __s);
  1679. }
  1680. template <class _CharT, class _Traits, class _Alloc>
  1681. inline bool
  1682. operator<=(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1683.            const _CharT* __s) {
  1684.   return !(__s < __x);
  1685. }
  1686. template <class _CharT, class _Traits, class _Alloc>
  1687. inline bool
  1688. operator>=(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1689.            const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1690.   return !(__x < __y);
  1691. }
  1692. template <class _CharT, class _Traits, class _Alloc>
  1693. inline bool
  1694. operator>=(const _CharT* __s,
  1695.            const basic_string<_CharT,_Traits,_Alloc>& __y) {
  1696.   return !(__s < __y);
  1697. }
  1698. template <class _CharT, class _Traits, class _Alloc>
  1699. inline bool
  1700. operator>=(const basic_string<_CharT,_Traits,_Alloc>& __x,
  1701.            const _CharT* __s) {
  1702.   return !(__x < __s);
  1703. }
  1704. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  1705. // Swap.
  1706. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  1707. template <class _CharT, class _Traits, class _Alloc>
  1708. inline void swap(basic_string<_CharT,_Traits,_Alloc>& __x,
  1709.                  basic_string<_CharT,_Traits,_Alloc>& __y) {
  1710.   __x.swap(__y);
  1711. }
  1712. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  1713. // I/O.  
  1714. #ifndef __STL_USE_NEW_IOSTREAMS 
  1715. __STL_END_NAMESPACE
  1716. #include <iostream.h>
  1717. __STL_BEGIN_NAMESPACE
  1718. #endif /* __STL_USE_NEW_IOSTREAMS */
  1719. #ifdef __STL_USE_NEW_IOSTREAMS
  1720. template <class _CharT, class _Traits>
  1721. inline bool
  1722. __sgi_string_fill(basic_ostream<_CharT, _Traits>& __os,
  1723.                   basic_streambuf<_CharT, _Traits>* __buf,
  1724.                   size_t __n)
  1725. {
  1726.   _CharT __f = __os.fill();
  1727.   size_t __i;
  1728.   bool __ok = true;
  1729.   for (__i = 0; __i < __n; __i++)
  1730.     __ok = __ok && !_Traits::eq_int_type(__buf->sputc(__f), _Traits::eof());
  1731.   return __ok;
  1732. }
  1733. template <class _CharT, class _Traits, class _Alloc>
  1734. basic_ostream<_CharT, _Traits>&
  1735. operator<<(basic_ostream<_CharT, _Traits>& __os, 
  1736.            const basic_string<_CharT,_Traits,_Alloc>& __s)
  1737. {
  1738.   typename basic_ostream<_CharT, _Traits>::sentry __sentry(__os);
  1739.   bool __ok = false;
  1740.   if (__sentry) {
  1741.     __ok = true;
  1742.     size_t __n = __s.size();
  1743.     size_t __pad_len = 0;
  1744.     const bool __left = (__os.flags() & ios::left) != 0;
  1745.     const size_t __w = __os.width(0);
  1746.     basic_streambuf<_CharT, _Traits>* __buf = __os.rdbuf();
  1747.     if (__w != 0 && __n < __w)
  1748.       __pad_len = __w - __n;
  1749.     
  1750.     if (!__left)
  1751.       __ok = __sgi_string_fill(__os, __buf, __pad_len);    
  1752.     __ok = __ok && 
  1753.            __buf->sputn(__s.data(), streamsize(__n)) == streamsize(__n);
  1754.     if (__left)
  1755.       __ok = __ok && __sgi_string_fill(__os, __buf, __pad_len);
  1756.   }
  1757.   if (!__ok)
  1758.     __os.setstate(ios_base::failbit);
  1759.   return __os;
  1760. }
  1761. template <class _CharT, class _Traits, class _Alloc>
  1762. basic_istream<_CharT, _Traits>& 
  1763. operator>>(basic_istream<_CharT, _Traits>& __is,
  1764.            basic_string<_CharT,_Traits,_Alloc>& __s)
  1765. {
  1766.   typename basic_istream<_CharT, _Traits>::sentry __sentry(__is);
  1767.   if (__sentry) {
  1768.     basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
  1769.     const ctype<_CharT>& __ctype = use_facet<ctype<_CharT> >(__is.getloc());
  1770.     __s.clear();
  1771.     size_t __n = __is.width(0);
  1772.     if (__n == 0)
  1773.       __n = static_cast<size_t>(-1);
  1774.     else
  1775.       __s.reserve(__n);
  1776.     
  1777.     while (__n-- > 0) {
  1778.       typename _Traits::int_type __c1 = __buf->sbumpc();
  1779.       if (_Traits::eq_int_type(__c1, _Traits::eof())) {
  1780.         __is.setstate(ios_base::eofbit);
  1781.         break;
  1782.       }
  1783.       else {
  1784.         _CharT __c = _Traits::to_char_type(__c1);
  1785.         if (__ctype.is(ctype<_CharT>::space, __c)) {
  1786.           if (_Traits::eq_int_type(__buf->sputbackc(__c), _Traits::eof()))
  1787.             __is.setstate(ios_base::failbit);
  1788.           break;
  1789.         }
  1790.         else
  1791.           __s.push_back(__c);
  1792.       }
  1793.     }
  1794.     
  1795.     // If we have read no characters, then set failbit.
  1796.     if (__s.size() == 0)
  1797.       __is.setstate(ios_base::failbit);
  1798.   }
  1799.   else
  1800.     __is.setstate(ios_base::failbit);
  1801.   return __is;
  1802. }
  1803. template <class _CharT, class _Traits, class _Alloc>    
  1804. basic_istream<_CharT, _Traits>& 
  1805. getline(istream& __is,
  1806.         basic_string<_CharT,_Traits,_Alloc>& __s,
  1807.         _CharT __delim)
  1808. {
  1809.   size_t __nread = 0;
  1810.   typename basic_istream<_CharT, _Traits>::sentry __sentry(__is, true);
  1811.   if (__sentry) {
  1812.     basic_streambuf<_CharT, _Traits>* __buf = __is.rdbuf();
  1813.     __s.clear();
  1814.     int __c1;
  1815.     while (__nread < __s.max_size()) {
  1816.       int __c1 = __buf->sbumpc();
  1817.       if (_Traits::eq_int_type(__c1, _Traits::eof())) {
  1818.         __is.setstate(ios_base::eofbit);
  1819.         break;
  1820.       }
  1821.       else {
  1822.         ++__nread;
  1823.         _CharT __c = _Traits::to_char_type(__c1);
  1824.         if (!_Traits::eq(__c, __delim)) 
  1825.           __s.push_back(__c);
  1826.         else
  1827.           break;              // Character is extracted but not appended.
  1828.       }
  1829.     }
  1830.   }
  1831.   if (__nread == 0 || __nread >= __s.max_size())
  1832.     __is.setstate(ios_base::failbit);
  1833.   return __is;
  1834. }
  1835. template <class _CharT, class _Traits, class _Alloc>    
  1836. inline basic_istream<_CharT, _Traits>& 
  1837. getline(basic_istream<_CharT, _Traits>& __is,
  1838.         basic_string<_CharT,_Traits,_Alloc>& __s)
  1839. {
  1840.   return getline(__is, __s, 'n');
  1841. }
  1842. #else /* __STL_USE_NEW_IOSTREAMS */
  1843. inline void __sgi_string_fill(ostream& __os, streambuf* __buf, size_t __n)
  1844. {
  1845.   char __f = __os.fill();
  1846.   size_t __i;
  1847.   for (__i = 0; __i < __n; __i++) __buf->sputc(__f);
  1848. }
  1849. template <class _CharT, class _Traits, class _Alloc>
  1850. ostream& operator<<(ostream& __os, 
  1851.                     const basic_string<_CharT,_Traits,_Alloc>& __s)
  1852. {
  1853.   streambuf* __buf = __os.rdbuf();
  1854.   if (__buf) {
  1855.     size_t __n = __s.size();
  1856.     size_t __pad_len = 0;
  1857.     const bool __left = (__os.flags() & ios::left) != 0;
  1858.     const size_t __w = __os.width();
  1859.     if (__w > 0) {
  1860.       __n = min(__w, __n);
  1861.       __pad_len = __w - __n;
  1862.     }
  1863.     
  1864.     if (!__left)
  1865.       __sgi_string_fill(__os, __buf, __pad_len);
  1866.   
  1867.     const size_t __nwritten = __buf->sputn(__s.data(), __n);
  1868.     if (__left)
  1869.       __sgi_string_fill(__os, __buf, __pad_len);
  1870.     if (__nwritten != __n)
  1871.       __os.clear(__os.rdstate() | ios::failbit);
  1872.     __os.width(0);
  1873.   }
  1874.   else
  1875.     __os.clear(__os.rdstate() | ios::badbit);
  1876.   return __os;
  1877. }
  1878. template <class _CharT, class _Traits, class _Alloc>
  1879. istream& operator>>(istream& __is, basic_string<_CharT,_Traits,_Alloc>& __s)
  1880. {
  1881.   if (!__is)
  1882.     return __is;
  1883.   streambuf* __buf = __is.rdbuf();
  1884.   if (__buf) {
  1885. #ifdef __USLC__
  1886. /* Jochen Schlick '1999  - operator >> modified. Work-around to get the 
  1887.  *                         output buffer flushed (necessary when using 
  1888.  *                         "cout" (without endl or flushing) followed by
  1889.  *                         "cin >>" ...)
  1890.  */
  1891.     if (__is.flags() & ios::skipws) {
  1892.       _CharT __c;
  1893.       do 
  1894.          __is.get(__c);
  1895.       while (__is && isspace(__c));
  1896.       if (__is)
  1897.          __is.putback(__c);
  1898.     }
  1899. #else
  1900.     if (__is.flags() & ios::skipws) {
  1901.       int __c;
  1902.       do {
  1903.         __c = __buf->sbumpc();
  1904.       }
  1905.       while (__c != EOF && isspace((unsigned char)__c));
  1906.       if (__c == EOF) {
  1907.         __is.clear(__is.rdstate() | ios::eofbit | ios::failbit);
  1908.       }
  1909.       else {
  1910.         if (__buf->sputbackc(__c) == EOF)
  1911.           __is.clear(__is.rdstate() | ios::failbit);
  1912.       }
  1913.     }
  1914. #endif
  1915.     // If we arrive at end of file (or fail for some other reason) while
  1916.     // still discarding whitespace, then we don't try to read the string.
  1917.     if (__is) {
  1918.       __s.clear();
  1919.       size_t __n = __is.width();
  1920.       if (__n == 0)
  1921.         __n = static_cast<size_t>(-1);
  1922.       else
  1923.         __s.reserve(__n);
  1924.       while (__n-- > 0) {
  1925.         int __c1 = __buf->sbumpc();
  1926.         if (__c1 == EOF) {
  1927.           __is.clear(__is.rdstate() | ios::eofbit);
  1928.           break;
  1929.         }
  1930.         else {
  1931.           _CharT __c = _Traits::to_char_type(__c1);
  1932.           if (isspace((unsigned char) __c)) {
  1933.             if (__buf->sputbackc(__c) == EOF)
  1934.               __is.clear(__is.rdstate() | ios::failbit);
  1935.             break;
  1936.           }
  1937.           else
  1938.             __s.push_back(__c);
  1939.         }
  1940.       }
  1941.     
  1942.       // If we have read no characters, then set failbit.
  1943.       if (__s.size() == 0)
  1944.         __is.clear(__is.rdstate() | ios::failbit);
  1945.     }
  1946.     __is.width(0);
  1947.   }
  1948.   else                          // We have no streambuf.
  1949.     __is.clear(__is.rdstate() | ios::badbit);
  1950.   return __is;
  1951. }
  1952. template <class _CharT, class _Traits, class _Alloc>    
  1953. istream& getline(istream& __is,
  1954.                  basic_string<_CharT,_Traits,_Alloc>& __s,
  1955.                  _CharT __delim)
  1956. {
  1957.   streambuf* __buf = __is.rdbuf();
  1958.   if (__buf) {
  1959.     size_t __nread = 0;
  1960.     if (__is) {
  1961.       __s.clear();
  1962.       while (__nread < __s.max_size()) {
  1963.         int __c1 = __buf->sbumpc();
  1964.         if (__c1 == EOF) {
  1965.           __is.clear(__is.rdstate() | ios::eofbit);
  1966.           break;
  1967.         }
  1968.         else {
  1969.           ++__nread;
  1970.           _CharT __c = _Traits::to_char_type(__c1);
  1971.           if (!_Traits::eq(__c, __delim)) 
  1972.             __s.push_back(__c);
  1973.           else
  1974.             break;              // Character is extracted but not appended.
  1975.         }
  1976.       }
  1977.     }
  1978.     if (__nread == 0 || __nread >= __s.max_size())
  1979.       __is.clear(__is.rdstate() | ios::failbit);
  1980.   }
  1981.   else
  1982.     __is.clear(__is.rdstate() | ios::badbit);
  1983.   return __is;
  1984. }
  1985. template <class _CharT, class _Traits, class _Alloc>    
  1986. inline istream& 
  1987. getline(istream& __is, basic_string<_CharT,_Traits,_Alloc>& __s)
  1988. {
  1989.   return getline(__is, __s, 'n');
  1990. }
  1991. #endif /* __STL_USE_NEW_IOSTREAMS */
  1992. template <class _CharT, class _Traits, class _Alloc>
  1993. void _S_string_copy(const basic_string<_CharT,_Traits,_Alloc>& __s,
  1994.                     _CharT* __buf,
  1995.                     size_t __n)
  1996. {
  1997.   if (__n > 0) {
  1998.     __n = min(__n - 1, __s.size());
  1999.     copy(__s.begin(), __s.begin() + __n, __buf);
  2000.     _Traits::assign(__buf[__n],
  2001.                     basic_string<_CharT,_Traits,_Alloc>::_M_null());
  2002.   }
  2003. }
  2004. inline const char* __get_c_string(const string& __s) { return __s.c_str(); }
  2005. // ------------------------------------------------------------
  2006. // Typedefs
  2007. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  2008. #pragma reset woff 1174
  2009. #pragma reset woff 1375
  2010. #endif
  2011. __STL_END_NAMESPACE
  2012. #include <stl_hash_fun.h>
  2013. __STL_BEGIN_NAMESPACE
  2014. template <class _CharT, class _Traits, class _Alloc>
  2015. size_t __stl_string_hash(const basic_string<_CharT,_Traits,_Alloc>& __s) {
  2016.   unsigned long __h = 0;
  2017.   for (basic_string<_CharT,_Traits,_Alloc>::const_iterator __i = __s.begin();
  2018.        __i != __s.end();
  2019.        ++__i)
  2020.     __h = 5*__h + *__i;
  2021.   return size_t(__h);
  2022. }
  2023. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  2024. template <class _CharT, class _Traits, class _Alloc>
  2025. struct hash<basic_string<_CharT,_Traits,_Alloc> > {
  2026.   size_t operator()(const basic_string<_CharT,_Traits,_Alloc>& __s) const
  2027.     { return __stl_string_hash(__s); }
  2028. };
  2029. #else
  2030. __STL_TEMPLATE_NULL struct hash<string> {
  2031.   size_t operator()(const string& __s) const
  2032.     { return __stl_string_hash(__s); }
  2033. };
  2034. __STL_TEMPLATE_NULL struct hash<wstring> {
  2035.   size_t operator()(const wstring& __s) const
  2036.     { return __stl_string_hash(__s); }
  2037. };
  2038. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  2039. __STL_END_NAMESPACE
  2040. #endif /* __SGI_STL_STRING */
  2041. // Local Variables:
  2042. // mode:C++
  2043. // End: