Initial revision

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@22182 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 1960 insertions, 0 deletions

diff --git a/libstdc++/stl/string b/libstdc++/stl/string
new file mode 100644
index 00000000000..24cfc20940f
--- /dev/null
+++ b/libstdc++/stl/string
@@ -0,0 +1,1960 @@
+/*
+ * Copyright (c) 1997,1998
+ * Silicon Graphics Computer Systems, Inc.
+ *
+ * Permission to use, copy, modify, distribute and sell this software
+ * and its documentation for any purpose is hereby granted without fee,
+ * provided that the above copyright notice appear in all copies and
+ * that both that copyright notice and this permission notice appear
+ * in supporting documentation.  Silicon Graphics makes no
+ * representations about the suitability of this software for any
+ * purpose.  It is provided "as is" without express or implied warranty.
+ */ 
+
+#ifndef __SGI_STL_STRING
+#define __SGI_STL_STRING
+
+#include <ctype.h>        
+#include <stdexcept>      // Includes stl_string_fwd.h and stl_config.h
+#include <char_traits.h>  // This header name is an extension.
+#include <iterator>
+#include <functional>
+#include <memory>
+#include <algorithm>
+
+// Standard C++ string class.  This class has performance
+// characteristics very much like vector<>, meaning, for example, that
+// it does not perform reference-count or copy-on-write, and that
+// concatenation of two strings is an O(N) operation. 
+
+// There are three reasons why basic_string is not identical to
+// vector.  First, basic_string always stores a null character at the
+// end; this makes it possible for c_str to be a fast operation.
+// Second, the C++ standard requires basic_string to copy elements
+// using char_traits<>::assign, char_traits<>::copy, and
+// char_traits<>::move.  This means that all of vector<>'s low-level
+// operations must be rewritten.  Third, basic_string<> has a lot of
+// extra functions in its interface that are convenient but, strictly
+// speaking, redundant.
+
+// Additionally, the C++ standard imposes a major restriction: according
+// to the standard, the character type _CharT must be a POD type.  This
+// implementation weakens that restriction, and allows _CharT to be a
+// a user-defined non-POD type.  However, _CharT must still have a
+// default constructor.
+
+__STL_BEGIN_NAMESPACE
+
+#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
+#pragma set woff 1174
+#pragma set woff 1375
+#endif
+
+// Helper classes that turn char_traits into function objects.
+
+template <class _Traits>
+struct _Eq_traits
+  : public binary_function<typename _Traits::char_type,
+                           typename _Traits::char_type,
+                           bool>
+{
+  bool operator()(const typename _Traits::char_type& __x,
+                  const typename _Traits::char_type& __y) const
+    { return _Traits::eq(__x, __y); }
+};
+
+template <class _Traits>
+struct _Lt_traits
+  : public binary_function<typename _Traits::char_type,
+                           typename _Traits::char_type,
+                           bool>
+{
+  bool operator()(const typename _Traits::char_type& __x,
+                  const typename _Traits::char_type& __y) const
+    { return _Traits::lt(__x, __y); }
+};
+
+template <class _Traits>
+struct _Not_within_traits
+  : public unary_function<typename _Traits::char_type, bool>
+{
+  typedef const typename _Traits::char_type* _Pointer;
+  const _Pointer _M_first;
+  const _Pointer _M_last;
+
+  _Not_within_traits(_Pointer __f, _Pointer __l) 
+    : _M_first(__f), _M_last(__l) {}
+
+  bool operator()(const typename _Traits::char_type& __x) const {
+    return find_if(_M_first, _M_last, 
+                   bind1st(_Eq_traits<_Traits>(), __x)) == _M_last;
+  }
+};
+
+// ------------------------------------------------------------
+// Class _String_base.  
+
+// _String_base is a helper class that makes it it easier to write an
+// exception-safe version of basic_string.  The constructor allocates,
+// but does not initialize, a block of memory.  The destructor
+// deallocates, but does not destroy elements within, a block of
+// memory.  The destructor assumes that _M_start either is null, or else
+// points to a block of memory that was allocated using _String_base's 
+// allocator and whose size is _M_end_of_storage - _M_start.
+
+// Additionally, _String_base encapsulates the difference between
+// old SGI-style allocators and standard-conforming allocators.
+
+#ifdef __STL_USE_STD_ALLOCATORS
+
+// General base class.
+template <class _Tp, class _Alloc, bool _S_instanceless>
+class _String_alloc_base {
+public:
+  typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
+  allocator_type get_allocator() const { return _M_data_allocator; }
+
+  _String_alloc_base(const allocator_type& __a)
+    : _M_data_allocator(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
+    {}
+
+protected:
+  _Tp* _M_allocate(size_t __n)
+    { return _M_data_allocator.allocate(__n); }
+  void _M_deallocate(_Tp* __p, size_t __n) {
+    if (__p)
+      _M_data_allocator.deallocate(__p, __n); 
+  }
+
+protected:
+  allocator_type _M_data_allocator;
+
+  _Tp* _M_start;
+  _Tp* _M_finish;
+  _Tp* _M_end_of_storage;
+};
+
+// Specialization for instanceless allocators.
+template <class _Tp, class _Alloc>
+class _String_alloc_base<_Tp,_Alloc,true> {
+public:
+  typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
+  allocator_type get_allocator() const { return allocator_type(); }
+
+  _String_alloc_base(const allocator_type&)
+    : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
+
+protected:
+  typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Alloc_type;
+  _Tp* _M_allocate(size_t __n)
+    { return _Alloc_type::allocate(__n); }
+  void _M_deallocate(_Tp* __p, size_t __n)
+    { _Alloc_type::deallocate(__p, __n); }
+
+protected:
+  _Tp* _M_start;
+  _Tp* _M_finish;
+  _Tp* _M_end_of_storage;
+};
+
+template <class _Tp, class _Alloc>
+class _String_base 
+  : public _String_alloc_base<_Tp, _Alloc,
+                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
+{
+protected:
+  typedef _String_alloc_base<_Tp, _Alloc,
+                             _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
+          _Base;
+  typedef typename _Base::allocator_type allocator_type;
+
+  void _M_allocate_block(size_t __n) { 
+    if (__n <= max_size()) {
+      _M_start  = _M_allocate(__n);
+      _M_finish = _M_start;
+      _M_end_of_storage = _M_start + __n;
+    }
+    else
+      _M_throw_length_error();
+  }
+
+  void _M_deallocate_block() 
+    { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
+  
+  size_t max_size() const { return (size_t(-1) / sizeof(_Tp)) - 1; }
+
+  _String_base(const allocator_type& __a) : _Base(__a) { }
+  
+  _String_base(const allocator_type& __a, size_t __n) : _Base(__a)
+    { _M_allocate_block(__n); }
+
+  ~_String_base() { _M_deallocate_block(); }
+
+  void _M_throw_length_error() const;
+  void _M_throw_out_of_range() const;
+};
+
+#else /* __STL_USE_STD_ALLOCATORS */
+
+template <class _Tp, class _Alloc> class _String_base {
+protected:
+  typedef simple_alloc<_Tp, _Alloc> _Alloc_type;
+  typedef _Alloc allocator_type;
+  allocator_type get_allocator() const { return allocator_type(); }
+
+  _Tp* _M_start;
+  _Tp* _M_finish;
+  _Tp* _M_end_of_storage;
+                                // Precondition: 0 < __n <= max_size().
+
+  _Tp* _M_allocate(size_t __n) { return _Alloc_type::allocate(__n); }
+  void _M_deallocate(_Tp* __p, size_t __n) {
+    if (__p)
+      _Alloc_type::deallocate(__p, __n); 
+  }
+
+  void _M_allocate_block(size_t __n) { 
+    if (__n <= max_size()) {
+      _M_start  = _M_allocate(__n);
+      _M_finish = _M_start;
+      _M_end_of_storage = _M_start + __n;
+    }
+    else
+      _M_throw_length_error();
+  }
+
+  void _M_deallocate_block() 
+    { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
+  
+  size_t max_size() const { return (size_t(-1) / sizeof(_Tp)) - 1; }
+
+  _String_base(const allocator_type&)
+    : _M_start(0), _M_finish(0), _M_end_of_storage(0) { }
+  
+  _String_base(const allocator_type&, size_t __n)
+    : _M_start(0), _M_finish(0), _M_end_of_storage(0)
+    { _M_allocate_block(__n); }
+
+  ~_String_base() { _M_deallocate_block(); }
+
+  void _M_throw_length_error() const;
+  void _M_throw_out_of_range() const;
+};
+
+#endif /* __STL_USE_STD_ALLOCATORS */
+
+template <class _Tp, class _Alloc> 
+void _String_base<_Tp,_Alloc>::_M_throw_length_error() const {
+  __STL_THROW(length_error("basic_string"));
+}
+
+template <class _Tp, class _Alloc> 
+void _String_base<_Tp, _Alloc>::_M_throw_out_of_range() const {
+  __STL_THROW(out_of_range("basic_string"));
+}
+
+// ------------------------------------------------------------
+// Class basic_string.  
+
+// Class invariants:
+// (1) [start, finish) is a valid range.
+// (2) Each iterator in [start, finish) points to a valid object
+//     of type value_type.
+// (3) *finish is a valid object of type value_type; in particular,
+//     it is value_type().
+// (4) [finish + 1, end_of_storage) is a valid range.
+// (5) Each iterator in [finish + 1, end_of_storage) points to 
+//     unininitialized memory.
+
+// Note one important consequence: a string of length n must manage
+// a block of memory whose size is at least n + 1.  
+
+
+template <class _CharT, class _Traits, class _Alloc> 
+class basic_string : private _String_base<_CharT,_Alloc> {
+public:
+  typedef _CharT value_type;
+  typedef _Traits traits_type;
+
+  typedef value_type* pointer;
+  typedef const value_type* const_pointer;
+  typedef value_type& reference;
+  typedef const value_type& const_reference;
+  typedef size_t size_type;
+  typedef ptrdiff_t difference_type;
+
+  typedef const value_type*                const_iterator;
+  typedef value_type*                      iterator;
+  typedef reverse_iterator<const_iterator> const_reverse_iterator;
+  typedef reverse_iterator<iterator>       reverse_iterator;
+
+  static const size_type npos = -1;
+
+  typedef _String_base<_CharT,_Alloc> _Base;
+
+public:                         // Constructor, destructor, assignment.
+  typedef typename _Base::allocator_type allocator_type;
+#ifdef __STL_USE_NAMESPACES
+  using _Base::get_allocator;
+#endif /* __STL_USE_NAMESPACES */
+
+  explicit basic_string(const allocator_type& __a = allocator_type())
+    : _Base(__a, 8) { construct(_M_finish); }
+
+  struct _Reserve_t {};
+  basic_string(_Reserve_t, size_t __n,
+               const allocator_type& __a = allocator_type())
+    : _Base(__a, __n + 1) { construct(_M_finish); }
+
+  basic_string(const basic_string& __s) : _Base(__s.get_allocator()) 
+    { _M_range_initialize(__s.begin(), __s.end()); }
+
+  basic_string(const basic_string& __s, size_type __pos, size_type __n = npos,
+               const allocator_type& __a = allocator_type()) 
+    : _Base(__a) {
+    if (__pos > __s.size())
+      _M_throw_out_of_range();
+    else
+      _M_range_initialize(__s.begin() + __pos,
+                          __s.begin() + __pos + min(__n, __s.size() - __pos));
+  }
+
+  basic_string(const _CharT* __s, size_type __n,
+               const allocator_type& __a = allocator_type()) 
+    : _Base(__a) 
+    { _M_range_initialize(__s, __s + __n); }
+
+  basic_string(const _CharT* __s,
+               const allocator_type& __a = allocator_type())
+    : _Base(__a) 
+    { _M_range_initialize(__s, __s + _Traits::length(__s)); }
+
+  basic_string(size_type __n, _CharT __c,
+               const allocator_type& __a = allocator_type())
+    : _Base(__a, __n + 1)
+  {
+    _M_finish = uninitialized_fill_n(_M_start, __n, __c);
+    _M_terminate_string();
+  }
+
+  // Check to see if _InputIterator is an integer type.  If so, then
+  // it can't be an iterator.
+  template <class _InputIterator>
+  basic_string(_InputIterator __f, _InputIterator __l,
+               const allocator_type& __a = allocator_type())
+    : _Base(__a)
+  {
+    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
+    _M_initialize_dispatch(__f, __l, _Integral());
+  }
+
+  ~basic_string() { destroy(_M_start, _M_finish + 1); }
+    
+  basic_string& operator=(const basic_string& __s) {
+    if (&__s != this) 
+      assign(__s.begin(), __s.end());
+    return *this;
+  }
+
+  basic_string& operator=(const _CharT* __s) 
+    { return assign(__s, __s + _Traits::length(__s)); }
+
+  basic_string& operator=(_CharT __c)
+    { return assign(static_cast<size_type>(1), __c); }
+
+private:                        // Protected members inherited from base.
+#ifdef __STL_HAS_NAMESPACES
+  using _Base::_M_allocate;
+  using _Base::_M_deallocate;
+  using _Base::_M_allocate_block;
+  using _Base::_M_deallocate_block;
+  using _Base::_M_throw_length_error;
+  using _Base::_M_throw_out_of_range;
+
+  using _Base::_M_start;
+  using _Base::_M_finish;
+  using _Base::_M_end_of_storage;
+#endif /* __STL_HAS_NAMESPACES */
+
+private:                        
+  // Helper functions used by constructors.  It is a severe error for
+  // any of them to be called anywhere except from within constructors.
+
+  void _M_terminate_string() {
+    __STL_TRY {
+      construct(_M_finish);
+    }
+    __STL_UNWIND(destroy(_M_start, _M_finish));
+  }
+    
+  template <class _InputIter>
+  void _M_range_initialize(_InputIter __f, _InputIter __l,
+                           input_iterator_tag) {
+    _M_allocate_block(8);
+    construct(_M_finish);
+    __STL_TRY {
+      append(__f, __l);
+    }
+    __STL_UNWIND(destroy(_M_start, _M_finish + 1));
+  }
+
+  template <class _ForwardIter>
+  void _M_range_initialize(_ForwardIter __f, _ForwardIter __l, 
+                           forward_iterator_tag) {
+    typename iterator_traits<_ForwardIter>::difference_type __n
+      = distance(__f, __l);
+    _M_allocate_block(__n + 1);
+    _M_finish = uninitialized_copy(__f, __l, _M_start);
+    _M_terminate_string();
+  }
+
+  template <class _InputIter>
+  void _M_range_initialize(_InputIter __f, _InputIter __l) {
+    typedef typename iterator_traits<_InputIter>::iterator_category _Category;
+    _M_range_initialize(__f, __l, _Category());
+  }
+
+  template <class _Integer>
+  void _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) {
+    _M_allocate_block(__n + 1);
+    _M_finish = uninitialized_fill_n(_M_start, __n, __x);
+    _M_terminate_string();
+  }
+
+  template <class _InputIter>
+  void _M_initialize_dispatch(_InputIter __f, _InputIter __l, __false_type) {
+     _M_range_initialize(__f, __l);
+  }
+    
+
+public:                         // Iterators.
+  iterator begin()             { return _M_start; }
+  iterator end()               { return _M_finish; }
+  const_iterator begin() const { return _M_start; }
+  const_iterator end()   const { return _M_finish; }  
+
+  reverse_iterator rbegin()             
+    { return reverse_iterator(_M_finish); }
+  reverse_iterator rend()               
+    { return reverse_iterator(_M_start); }
+  const_reverse_iterator rbegin() const 
+    { return const_reverse_iterator(_M_finish); }
+  const_reverse_iterator rend()   const 
+    { return const_reverse_iterator(_M_start); }
+
+public:                         // Size, capacity, etc.
+  size_type size() const { return _M_finish - _M_start; }
+  size_type length() const { return size(); }
+#ifdef __STL_USE_NAMESPACES
+  using _Base::max_size;
+#endif /* __STL_USE_NAMESPACES */
+
+  void resize(size_type __n, _CharT __c = _CharT()) {
+    if (__n <= size())
+      erase(begin() + __n, end());
+    else
+      append(__n - size(), __c);
+  }
+
+  void reserve(size_type = 0);
+
+  size_type capacity() const { return (_M_end_of_storage - _M_start) - 1; }
+
+  void clear() {
+    if (!empty()) {
+      _Traits::assign(*_M_start, _CharT());
+      destroy(_M_start+1, _M_finish+1);
+      _M_finish = _M_start;
+    }
+  } 
+
+  bool empty() const { return _M_start == _M_finish; }    
+
+public:                         // Element access.
+
+  const_reference operator[](size_type __n) const
+    { return *(_M_start + __n); }
+  reference operator[](size_type __n)
+    { return *(_M_start + __n); }
+
+  const_reference at(size_type __n) const {
+    if (__n >= size())
+      _M_throw_out_of_range();
+    return *(_M_start + __n);
+  }
+
+  reference at(size_type __n) {
+    if (__n >= size())
+      _M_throw_out_of_range();
+    return *(_M_start + __n);
+  }
+
+public:                         // Append, operator+=, push_back.
+
+  basic_string& operator+=(const basic_string& __s) { return append(__s); }
+  basic_string& operator+=(const _CharT* __s) { return append(__s); }
+  basic_string& operator+=(_CharT __c) { push_back(__c); return *this; }
+
+  basic_string& append(const basic_string& __s) 
+    { return append(__s.begin(), __s.end()); }
+
+  basic_string& append(const basic_string& __s,
+                       size_type __pos, size_type __n)
+  {
+    if (__pos > __s.size())
+      _M_throw_out_of_range();
+    return append(__s.begin() + __pos,
+                  __s.begin() + __pos + min(__n, __s.size() - __pos));
+  }
+
+  basic_string& append(const _CharT* __s, size_type __n) 
+    { return append(__s, __s+__n); }
+
+  basic_string& append(const _CharT* __s) 
+    { return append(__s, __s + _Traits::length(__s)); }
+
+  basic_string& append(size_type __n, _CharT __c);
+
+  // Check to see if _InputIterator is an integer type.  If so, then
+  // it can't be an iterator.
+  template <class _InputIter>
+  basic_string& append(_InputIter __first, _InputIter __last) {
+    typedef typename _Is_integer<_InputIter>::_Integral _Integral;
+    return _M_append_dispatch(__first, __last, _Integral());
+  }
+
+  void push_back(_CharT __c) {
+    if (_M_finish + 1 == _M_end_of_storage)
+      reserve(size() + max(size(), static_cast<size_type>(1)));
+    construct(_M_finish + 1);
+    _Traits::assign(*_M_finish, __c);
+    ++_M_finish;
+  }
+
+  void pop_back() {
+    _Traits::assign(*(_M_finish - 1), _CharT());
+    destroy(_M_finish);
+    --_M_finish;
+  }
+
+private:                        // Helper functions for append.
+
+  template <class _InputIter>
+  basic_string& append(_InputIter __f, _InputIter __l, input_iterator_tag);
+
+  template <class _ForwardIter>
+  basic_string& append(_ForwardIter __f, _ForwardIter __l, 
+                       forward_iterator_tag);
+
+  template <class _Integer>
+  basic_string& _M_append_dispatch(_Integer __n, _Integer __x, __true_type) {
+    return append((size_type) __n, (_CharT) __x);
+  }
+
+  template <class _InputIter>
+  basic_string& _M_append_dispatch(_InputIter __f, _InputIter __l,
+                                   __false_type) {
+    typedef typename iterator_traits<_InputIter>::iterator_category _Category;
+    return append(__f, __l, _Category());
+  }
+
+public:                         // Assign
+  
+  basic_string& assign(const basic_string& __s) 
+    { return assign(__s.begin(), __s.end()); }
+
+  basic_string& assign(const basic_string& __s, 
+                       size_type __pos, size_type __n) {
+    if (__pos > __s.size())
+      _M_throw_out_of_range();
+    return assign(__s.begin() + __pos, 
+                  __s.begin() + __pos + min(__n, __s.size() - __pos));
+  }
+
+  basic_string& assign(const _CharT* __s, size_type __n)
+    { return assign(__s, __s + __n); }
+
+  basic_string& assign(const _CharT* __s)
+    { return assign(__s, __s + _Traits::length(__s)); }
+
+  basic_string& assign(size_type __n, _CharT __c);
+
+  // Check to see if _InputIterator is an integer type.  If so, then
+  // it can't be an iterator.
+  template <class _InputIter>
+  basic_string& assign(_InputIter __first, _InputIter __last) {
+    typedef typename _Is_integer<_InputIter>::_Integral _Integral;
+    return _M_assign_dispatch(__first, __last, _Integral());
+  }
+
+  basic_string& assign(const _CharT* __f, const _CharT* __l);
+
+private:                        // Helper functions for assign.
+
+  template <class _Integer>
+  basic_string& _M_assign_dispatch(_Integer __n, _Integer __x, __true_type) {
+    return assign((size_type) __n, (_CharT) __x);
+  }
+
+  template <class _InputIter>
+  basic_string& _M_assign_dispatch(_InputIter __f, _InputIter __l,
+                                   __false_type);
+
+public:                         // Insert
+
+  basic_string& insert(size_type __pos, const basic_string& __s) {
+    if (__pos > size())
+      _M_throw_out_of_range();
+    if (size() > max_size() - __s.size())
+      _M_throw_length_error();
+    insert(_M_start + __pos, __s.begin(), __s.end());
+    return *this;
+  }
+
+  basic_string& insert(size_type __pos, const basic_string& __s,
+                       size_type __beg, size_type __n) {
+    if (__pos > size() || __beg > __s.size())
+      _M_throw_out_of_range();
+    size_type __len = min(__n, __s.size() - __beg);
+    if (size() > max_size() - __len)
+      _M_throw_length_error();
+    insert(_M_start + __pos,
+           __s.begin() + __beg, __s.begin() + __beg + __len);
+    return *this;
+  }
+
+  basic_string& insert(size_type __pos, const _CharT* __s, size_type __n) {
+    if (__pos > size())
+      _M_throw_out_of_range();
+    if (size() > max_size() - __n)
+      _M_throw_length_error();
+    insert(_M_start + __pos, __s, __s + __n);
+    return *this;
+  }
+
+  basic_string& insert(size_type __pos, const _CharT* __s) {
+    if (__pos > size())
+      _M_throw_out_of_range();
+    size_type __len = _Traits::length(__s);
+    if (size() > max_size() - __len)
+      _M_throw_length_error();
+    insert(_M_start + __pos, __s, __s + __len);
+    return *this;
+  }
+    
+  basic_string& insert(size_type __pos, size_type __n, _CharT __c) {
+    if (__pos > size())
+      _M_throw_out_of_range();
+    if (size() > max_size() - __n)
+      _M_throw_length_error();
+    insert(_M_start + __pos, __n, __c);
+    return *this;
+  }
+
+  iterator insert(iterator __p, _CharT __c) {
+    if (__p == _M_finish) {
+      push_back(__c);
+      return _M_finish - 1;
+    }
+    else
+      return _M_insert_aux(__p, __c);
+  }
+
+  void insert(iterator __p, size_t __n, _CharT __c);
+
+  // Check to see if _InputIterator is an integer type.  If so, then
+  // it can't be an iterator.
+  template <class _InputIter>
+  void insert(iterator __p, _InputIter __first, _InputIter __last) {
+    typedef typename _Is_integer<_InputIter>::_Integral _Integral;
+    _M_insert_dispatch(__p, __first, __last, _Integral());
+  }
+
+private:                        // Helper functions for insert.
+  template <class _InputIter>
+  void insert(iterator __p, _InputIter, _InputIter, input_iterator_tag);
+
+  template <class _ForwardIter>
+  void insert(iterator __p, _ForwardIter, _ForwardIter, forward_iterator_tag);
+
+
+  template <class _Integer>
+  void _M_insert_dispatch(iterator __p, _Integer __n, _Integer __x,
+                          __true_type) {
+    insert(__p, (size_type) __n, (_CharT) __x);
+  }
+
+  template <class _InputIter>
+  void _M_insert_dispatch(iterator __p, _InputIter __first, _InputIter __last,
+                          __false_type) {
+    typedef typename iterator_traits<_InputIter>::iterator_category _Category;
+    insert(__p, __first, __last, _Category());
+  }
+
+  iterator _M_insert_aux(iterator, _CharT);
+
+  template <class _InputIterator>
+  void 
+  _M_copy(_InputIterator __first, _InputIterator __last, iterator __result) {
+    for ( ; __first != __last; ++__first, ++__result)
+      _Traits::assign(*__result, *__first);
+  }
+
+  void 
+  _M_copy(const _CharT* __first, const _CharT* __last, _CharT* __result) {
+    _Traits::copy(__result, __first, __last - __first);
+  }
+
+public:                         // Erase.
+
+  basic_string& erase(size_type __pos = 0, size_type __n = npos) {
+    if (__pos > size())
+      _M_throw_out_of_range();
+    erase(_M_start + __pos, _M_start + __pos + min(__n, size() - __pos));
+    return *this;
+  }  
+
+  iterator erase(iterator __position) {
+                                // The move includes the terminating _CharT().
+    _Traits::move(__position, __position + 1, _M_finish - __position);
+    destroy(_M_finish);
+    --_M_finish;
+    return __position;
+  }
+
+  iterator erase(iterator __first, iterator __last) {
+    if (__first != __last) {
+                                // The move includes the terminating _CharT().
+      _Traits::move(__first, __last, (_M_finish - __last) + 1);
+      const iterator __new_finish = _M_finish - (__last - __first);
+      destroy(__new_finish + 1, _M_finish + 1);
+      _M_finish = __new_finish;
+    }
+    return __first;
+  }
+
+public:                         // Replace.  (Conceptually equivalent
+                                // to erase followed by insert.)
+  basic_string& replace(size_type __pos, size_type __n, 
+                        const basic_string& __s) {
+    if (__pos > size())
+      _M_throw_out_of_range();
+    const size_type __len = min(__n, size() - __pos);
+    if (size() - __len >= max_size() - __s.size())
+      _M_throw_length_error();
+    return replace(_M_start + __pos, _M_start + __pos + __len, 
+                   __s.begin(), __s.end());
+  }
+
+  basic_string& replace(size_type __pos1, size_type __n1,
+                        const basic_string& __s,
+                        size_type __pos2, size_type __n2) {
+    if (__pos1 > size() || __pos2 > __s.size())
+      _M_throw_out_of_range();
+    const size_type __len1 = min(__n1, size() - __pos1);
+    const size_type __len2 = min(__n2, __s.size() - __pos2);
+    if (size() - __len1 >= max_size() - __len2)
+      _M_throw_length_error();
+    return replace(_M_start + __pos1, _M_start + __pos1 + __len1,
+                   __s._M_start + __pos2, __s._M_start + __pos2 + __len2);
+  }
+
+  basic_string& replace(size_type __pos, size_type __n1,
+                        const _CharT* __s, size_type __n2) {
+    if (__pos > size())
+      _M_throw_out_of_range();
+    const size_type __len = min(__n1, size() - __pos);
+    if (__n2 > max_size() || size() - __len >= max_size() - __n2)
+      _M_throw_length_error();
+    return replace(_M_start + __pos, _M_start + __pos + __len,
+                   __s, __s + __n2);
+  }
+
+  basic_string& replace(size_type __pos, size_type __n1,
+                        const _CharT* __s) {
+    if (__pos > size())
+      _M_throw_out_of_range();
+    const size_type __len = min(__n1, size() - __pos);
+    const size_type __n2 = _Traits::length(__s);
+    if (__n2 > max_size() || size() - __len >= max_size() - __n2)
+      _M_throw_length_error();
+    return replace(_M_start + __pos, _M_start + __pos + __len,
+                   __s, __s + _Traits::length(__s));
+  }
+
+  basic_string& replace(size_type __pos, size_type __n1,
+                        size_type __n2, _CharT __c) {
+    if (__pos > size())
+      _M_throw_out_of_range();
+    const size_type __len = min(__n1, size() - __pos);
+    if (__n2 > max_size() || size() - __len >= max_size() - __n2)
+      _M_throw_length_error();
+    return replace(_M_start + __pos, _M_start + __pos + __len, __n2, __c);
+  }
+
+  basic_string& replace(iterator __first, iterator __last, 
+                        const basic_string& __s) 
+    { return replace(__first, __last, __s.begin(), __s.end()); }
+
+  basic_string& replace(iterator __first, iterator __last,
+                        const _CharT* __s, size_type __n) 
+    { return replace(__first, __last, __s, __s + __n); }
+
+  basic_string& replace(iterator __first, iterator __last,
+                        const _CharT* __s) {
+    return replace(__first, __last, __s, __s + _Traits::length(__s));
+  }
+
+  basic_string& replace(iterator __first, iterator __last, 
+                        size_type __n, _CharT __c);
+
+  // Check to see if _InputIterator is an integer type.  If so, then
+  // it can't be an iterator.
+  template <class _InputIter>
+  basic_string& replace(iterator __first, iterator __last,
+                        _InputIter __f, _InputIter __l) {
+    typedef typename _Is_integer<_InputIter>::_Integral _Integral;
+    return _M_replace_dispatch(__first, __last, __f, __l,  _Integral());
+  }
+
+private:                        // Helper functions for replace.
+
+  template <class _Integer>
+  basic_string& _M_replace_dispatch(iterator __first, iterator __last,
+                                    _Integer __n, _Integer __x,
+                                    __true_type) {
+    return replace(__first, __last, (size_type) __n, (_CharT) __x);
+  }
+
+  template <class _InputIter>
+  basic_string& _M_replace_dispatch(iterator __first, iterator __last,
+                                    _InputIter __f, _InputIter __l,
+                                    __false_type) {
+    typedef typename iterator_traits<_InputIter>::iterator_category _Category;
+    return replace(__first, __last, __f, __l, _Category());
+  }
+
+  template <class _InputIter>
+  basic_string& replace(iterator __first, iterator __last,
+                        _InputIter __f, _InputIter __l, input_iterator_tag);
+
+  template <class _ForwardIter>
+  basic_string& replace(iterator __first, iterator __last,
+                        _ForwardIter __f, _ForwardIter __l, 
+                        forward_iterator_tag);
+
+public:                         // Other modifier member functions.
+
+  size_type copy(_CharT* __s, size_type __n, size_type __pos = 0) const {
+    if (__pos > size())
+      _M_throw_out_of_range();
+    const size_type __len = min(__n, size() - __pos);
+    _Traits::copy(__s, _M_start + __pos, __len);
+    return __len;
+  }
+
+  void swap(basic_string& __s) {
+    __STD::swap(_M_start, __s._M_start);
+    __STD::swap(_M_finish, __s._M_finish);
+    __STD::swap(_M_end_of_storage, __s._M_end_of_storage);
+  }
+
+public:                         // Conversion to C string.
+
+  const _CharT* c_str() const { return _M_start; }
+  const _CharT* data()  const { return _M_start; }
+
+public:                         // find.
+
+  size_type find(const basic_string& __s, size_type __pos = 0) const 
+    { return find(__s.begin(), __pos, __s.size()); }
+
+  size_type find(const _CharT* __s, size_type __pos = 0) const 
+    { return find(__s, __pos, _Traits::length(__s)); }
+
+  size_type find(const _CharT* __s, size_type __pos, size_type __n) const;
+  size_type find(_CharT __c, size_type __pos = 0) const;
+
+public:                         // rfind.
+
+  size_type rfind(const basic_string& __s, size_type __pos = npos) const 
+    { return rfind(__s.begin(), __pos, __s.size()); }
+
+  size_type rfind(const _CharT* __s, size_type __pos = npos) const 
+    { return rfind(__s, __pos, _Traits::length(__s)); }
+
+  size_type rfind(const _CharT* __s, size_type __pos, size_type __n) const;
+  size_type rfind(_CharT __c, size_type __pos = npos) const;
+
+public:                         // find_first_of
+  
+  size_type find_first_of(const basic_string& __s, size_type __pos = 0) const 
+    { return find_first_of(__s.begin(), __pos, __s.size()); }
+
+  size_type find_first_of(const _CharT* __s, size_type __pos = 0) const 
+    { return find_first_of(__s, __pos, _Traits::length(__s)); }
+
+  size_type find_first_of(const _CharT* __s, size_type __pos, 
+                          size_type __n) const;
+
+  size_type find_first_of(_CharT __c, size_type __pos = 0) const 
+    { return find(__c, __pos); }
+
+public:                         // find_last_of
+
+  size_type find_last_of(const basic_string& __s,
+                         size_type __pos = npos) const
+    { return find_last_of(__s.begin(), __pos, __s.size()); }
+
+  size_type find_last_of(const _CharT* __s, size_type __pos = npos) const 
+    { return find_last_of(__s, __pos, _Traits::length(__s)); }
+
+  size_type find_last_of(const _CharT* __s, size_type __pos, 
+                         size_type __n) const;
+
+  size_type find_last_of(_CharT __c, size_type __pos = npos) const {
+    return rfind(__c, __pos);
+  }
+
+public:                         // find_first_not_of
+
+  size_type find_first_not_of(const basic_string& __s, 
+                              size_type __pos = 0) const 
+    { return find_first_not_of(__s.begin(), __pos, __s.size()); }
+
+  size_type find_first_not_of(const _CharT* __s, size_type __pos = 0) const 
+    { return find_first_not_of(__s, __pos, _Traits::length(__s)); }
+
+  size_type find_first_not_of(const _CharT* __s, size_type __pos,
+                              size_type __n) const;
+
+  size_type find_first_not_of(_CharT __c, size_type __pos = 0) const;
+
+public:                         // find_last_not_of
+
+  size_type find_last_not_of(const basic_string& __s, 
+                             size_type __pos = npos) const
+    { return find_last_not_of(__s.begin(), __pos, __s.size()); }
+
+  size_type find_last_not_of(const _CharT* __s, size_type __pos = npos) const
+    { return find_last_not_of(__s, __pos, _Traits::length(__s)); }
+
+  size_type find_last_not_of(const _CharT* __s, size_type __pos,
+                             size_type __n) const;
+
+  size_type find_last_not_of(_CharT __c, size_type __pos = npos) const;
+
+public:                         // Substring.
+
+  basic_string substr(size_type __pos = 0, size_type __n = npos) const {
+    if (__pos > size())
+      _M_throw_out_of_range();
+    return basic_string(_M_start + __pos, 
+                        _M_start + __pos + min(__n, size() - __pos));
+  }
+
+public:                         // Compare
+
+  int compare(const basic_string& __s) const 
+    { return _M_compare(_M_start, _M_finish, __s._M_start, __s._M_finish); }
+
+  int compare(size_type __pos1, size_type __n1,
+              const basic_string& __s) const {
+    if (__pos1 > size())
+      _M_throw_out_of_range();
+    return _M_compare(_M_start + __pos1, 
+                      _M_start + __pos1 + min(__n1, size() - __pos1),
+                      __s._M_start, __s._M_finish);
+  }
+    
+  int compare(size_type __pos1, size_type __n1,
+              const basic_string& __s,
+              size_type __pos2, size_type __n2) const {
+    if (__pos1 > size() || __pos2 > __s.size())
+      _M_throw_out_of_range();
+    return _M_compare(_M_start + __pos1, 
+                      _M_start + __pos1 + min(__n1, size() - __pos1),
+                      __s._M_start + __pos2, 
+                      __s._M_start + __pos2 + min(__n2, size() - __pos2));
+  }
+
+  int compare(const _CharT* __s) const {
+    return _M_compare(_M_start, _M_finish, __s, __s + _Traits::length(__s));
+  }
+
+  int compare(size_type __pos1, size_type __n1, const _CharT* __s) const {
+    if (__pos1 > size())
+      _M_throw_out_of_range();
+    return _M_compare(_M_start + __pos1, 
+                      _M_start + __pos1 + min(__n1, size() - __pos1),
+                      __s, __s + _Traits::length(__s));
+  }
+
+  int compare(size_type __pos1, size_type __n1, const _CharT* __s,
+              size_type __n2) const {
+    if (__pos1 > size())
+      _M_throw_out_of_range();
+    return _M_compare(_M_start + __pos1, 
+                      _M_start + __pos1 + min(__n1, size() - __pos1),
+                      __s, __s + __n2);
+  }
+
+private:                        // Helper functions for compare.
+  
+  static int _M_compare(const _CharT* __f1, const _CharT* __l1,
+                        const _CharT* __f2, const _CharT* __l2) {
+    const ptrdiff_t __n1 = __l1 - __f1;
+    const ptrdiff_t __n2 = __l2 - __f2;
+    const int cmp = _Traits::compare(__f1, __f2, min(__n1, __n2));
+    return cmp != 0 ? cmp : (__n1 < __n2 ? -1 : (__n1 > __n2 ? 1 : 0));
+  }
+
+  friend bool operator< __STL_NULL_TMPL_ARGS (const basic_string&,
+                                              const basic_string&);
+  friend bool operator< __STL_NULL_TMPL_ARGS (const _CharT*,
+                                              const basic_string&);
+  friend bool operator< __STL_NULL_TMPL_ARGS (const basic_string&,
+                                              const _CharT*);
+};
+
+
+
+// ------------------------------------------------------------
+// Non-inline declarations.
+
+template <class _CharT, class _Traits, class _Alloc> 
+const basic_string<_CharT,_Traits,_Alloc>::size_type 
+basic_string<_CharT,_Traits,_Alloc>::npos;
+
+// Change the string's capacity so that it is large enough to hold
+//  at least __res_arg elements, plus the terminating _CharT().  Note that,
+//  if __res_arg < capacity(), this member function may actually decrease
+//  the string's capacity.
+template <class _CharT, class _Traits, class _Alloc> 
+void basic_string<_CharT,_Traits,_Alloc>::reserve(size_type __res_arg) {
+  if (__res_arg > max_size())
+    _M_throw_length_error();
+
+  size_type __n = max(__res_arg, size()) + 1;
+  pointer __new_start = _M_allocate(__n);
+  pointer __new_finish = __new_start;
+
+  __STL_TRY {
+    __new_finish = uninitialized_copy(_M_start, _M_finish, __new_start);
+    construct(__new_finish);
+  }
+  __STL_UNWIND((destroy(__new_start, __new_finish), 
+                _M_deallocate(__new_start, __n)));
+
+  destroy(_M_start, _M_finish + 1);
+  _M_deallocate_block();
+  _M_start = __new_start;
+  _M_finish = __new_finish;
+  _M_end_of_storage = __new_start + __n;
+}
+
+template <class _CharT, class _Traits, class _Alloc> 
+basic_string<_CharT,_Traits,_Alloc>& 
+basic_string<_CharT,_Traits,_Alloc>::append(size_type __n, _CharT __c) {
+  if (__n > max_size() || size() > max_size() - __n)
+    _M_throw_length_error();
+  if (size() + __n > capacity())
+    reserve(size() + max(size(), __n));
+  if (__n > 0) {
+    uninitialized_fill_n(_M_finish + 1, __n - 1, __c);
+    __STL_TRY {
+      construct(_M_finish + __n);
+    }
+    __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n));
+    _Traits::assign(*_M_finish, __c);
+    _M_finish += __n;
+  }
+  return *this;
+}
+
+template <class _Tp, class _Traits, class _Alloc> 
+template <class _InputIterator>
+basic_string<_Tp, _Traits, _Alloc>& 
+basic_string<_Tp, _Traits, _Alloc>::append(_InputIterator __first, 
+                                          _InputIterator __last,
+                                          input_iterator_tag) {
+  for ( ; __first != __last ; ++__first)
+    push_back(*__first);
+  return *this;
+}
+
+template <class _Tp, class _Traits, class _Alloc> 
+template <class _ForwardIter>
+basic_string<_Tp, _Traits, _Alloc>& 
+basic_string<_Tp, _Traits, _Alloc>::append(_ForwardIter __first, 
+                                           _ForwardIter __last,
+                                           forward_iterator_tag) {
+  if (__first != __last) {
+    const size_type __old_size = size();
+    typename iterator_traits<_ForwardIter>::difference_type __n 
+      = distance(__first, __last);
+    if (__n > max_size() || __old_size > max_size() - __n)
+      _M_throw_length_error();
+    if (__old_size + __n > capacity()) {
+      const size_type __len = __old_size +
+                            max(__old_size, static_cast<size_type>(__n)) + 1;
+      pointer __new_start = _M_allocate(__len);
+      pointer __new_finish = __new_start;
+      __STL_TRY {
+        __new_finish = uninitialized_copy(_M_start, _M_finish, __new_start);
+        __new_finish = uninitialized_copy(__first, __last, __new_finish);
+        construct(__new_finish);
+      }
+      __STL_UNWIND((destroy(__new_start,__new_finish),
+                    _M_deallocate(__new_start,__len)));
+      destroy(_M_start, _M_finish + 1);
+      _M_deallocate_block();
+      _M_start = __new_start;
+      _M_finish = __new_finish;
+      _M_end_of_storage = __new_start + __len; 
+    }
+    else {
+      _ForwardIter __f1 = __first;
+      ++__f1;
+      uninitialized_copy(__f1, __last, _M_finish + 1);
+      __STL_TRY {
+        construct(_M_finish + __n);
+      }
+      __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n));
+      _Traits::assign(*_M_finish, *__first);
+      _M_finish += __n;
+    }
+  }
+  return *this;  
+}
+
+template <class _CharT, class _Traits, class _Alloc> 
+basic_string<_CharT,_Traits,_Alloc>& 
+basic_string<_CharT,_Traits,_Alloc>::assign(size_type __n, _CharT __c) {
+  if (__n <= size()) {
+    _Traits::assign(_M_start, __n, __c);
+    erase(_M_start + __n, _M_finish);
+  }
+  else {
+    _Traits::assign(_M_start, size(), __c);
+    append(__n - size(), __c);
+  }
+  return *this;
+}
+
+template <class _CharT, class _Traits, class _Alloc> 
+template <class _InputIter>
+basic_string<_CharT,_Traits,_Alloc>& basic_string<_CharT,_Traits,_Alloc>
+  ::_M_assign_dispatch(_InputIter __f, _InputIter __l, __false_type)
+{
+  pointer __cur = _M_start;
+  while (__f != __l && __cur != _M_finish) {
+    _Traits::assign(*__cur, *__f);
+    ++__f;
+    ++__cur;
+  }
+  if (__f == __l)
+    erase(__cur, _M_finish);
+  else
+    append(__f, __l);
+  return *this;
+}
+
+template <class _CharT, class _Traits, class _Alloc> 
+basic_string<_CharT,_Traits,_Alloc>& 
+basic_string<_CharT,_Traits,_Alloc>::assign(const _CharT* __f, 
+                                            const _CharT* __l)
+{
+  const ptrdiff_t __n = __l - __f;
+  if (__n <= size()) {
+    _Traits::copy(_M_start, __f, __n);
+    erase(_M_start + __n, _M_finish);
+  }
+  else {
+    _Traits::copy(_M_start, __f, size());
+    append(__f + size(), __l);
+  }
+  return *this;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+basic_string<_CharT,_Traits,_Alloc>::iterator 
+basic_string<_CharT,_Traits,_Alloc>
+  ::_M_insert_aux(basic_string<_CharT,_Traits,_Alloc>::iterator __p,
+                  _CharT __c)
+{
+  iterator __new_pos = __p;
+  if (_M_finish + 1 < _M_end_of_storage) {
+    construct(_M_finish + 1);
+    _Traits::move(__p + 1, __p, _M_finish - __p);
+    _Traits::assign(*__p, __c);
+    ++_M_finish;
+  }
+  else {
+    const size_type __old_len = size();
+    const size_type __len = __old_len +
+                            max(__old_len, static_cast<size_type>(1)) + 1;
+    iterator __new_start = _M_allocate(__len);
+    iterator __new_finish = __new_start;
+    __STL_TRY {
+      __new_pos = uninitialized_copy(_M_start, __p, __new_start);
+      construct(__new_pos, __c);
+      __new_finish = __new_pos + 1;
+      __new_finish = uninitialized_copy(__p, _M_finish, __new_finish);
+      construct(__new_finish);
+    }
+    __STL_UNWIND((destroy(__new_start,__new_finish), 
+                  _M_deallocate(__new_start,__len)));
+    destroy(_M_start, _M_finish + 1);
+    _M_deallocate_block();
+    _M_start = __new_start;
+    _M_finish = __new_finish;
+    _M_end_of_storage = __new_start + __len;
+  }
+  return __new_pos;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+void basic_string<_CharT,_Traits,_Alloc>
+  ::insert(basic_string<_CharT,_Traits,_Alloc>::iterator __position,
+           size_t __n, _CharT __c)
+{
+  if (__n != 0) {
+    if (size_type(_M_end_of_storage - _M_finish) >= __n + 1) {
+      const size_type __elems_after = _M_finish - __position;
+      iterator __old_finish = _M_finish;
+      if (__elems_after >= __n) {
+        uninitialized_copy((_M_finish - __n) + 1, _M_finish + 1,
+                           _M_finish + 1);
+        _M_finish += __n;
+        _Traits::move(__position + __n,
+                      __position, (__elems_after - __n) + 1);
+        _Traits::assign(__position, __n, __c);
+      }
+      else {
+        uninitialized_fill_n(_M_finish + 1, __n - __elems_after - 1, __c);
+        _M_finish += __n - __elems_after;
+        __STL_TRY {
+          uninitialized_copy(__position, __old_finish + 1, _M_finish);
+          _M_finish += __elems_after;
+        }
+        __STL_UNWIND((destroy(__old_finish + 1, _M_finish), 
+                      _M_finish = __old_finish));
+        _Traits::assign(__position, __elems_after + 1, __c);
+      }
+    }
+    else {
+      const size_type __old_size = size();        
+      const size_type __len = __old_size + max(__old_size, __n) + 1;
+      iterator __new_start = _M_allocate(__len);
+      iterator __new_finish = __new_start;
+      __STL_TRY {
+        __new_finish = uninitialized_copy(_M_start, __position, __new_start);
+        __new_finish = uninitialized_fill_n(__new_finish, __n, __c);
+        __new_finish = uninitialized_copy(__position, _M_finish,
+                                          __new_finish);
+        construct(__new_finish);
+      }
+      __STL_UNWIND((destroy(__new_start,__new_finish),
+                    _M_deallocate(__new_start,__len)));
+      destroy(_M_start, _M_finish + 1);
+      _M_deallocate_block();
+      _M_start = __new_start;
+      _M_finish = __new_finish;
+      _M_end_of_storage = __new_start + __len;    
+    }
+  }
+}
+
+template <class _Tp, class _Traits, class _Alloc>
+template <class _InputIter>
+void basic_string<_Tp, _Traits, _Alloc>::insert(iterator __p,
+                                                _InputIter __first, 
+                                                _InputIter __last,
+                                                input_iterator_tag)
+{
+  for ( ; __first != __last; ++__first) {
+    __p = insert(__p, *__first);
+    ++__p;
+  }
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+template <class _ForwardIter>
+void 
+basic_string<_CharT,_Traits,_Alloc>::insert(iterator __position,
+                                           _ForwardIter __first, 
+                                           _ForwardIter __last,
+                                           forward_iterator_tag)
+{
+  if (__first != __last) {
+    const difference_type __n = distance(__first, __last);
+    if (_M_end_of_storage - _M_finish >= __n + 1) {
+      const difference_type __elems_after = _M_finish - __position;
+      iterator __old_finish = _M_finish;
+      if (__elems_after >= __n) {
+        uninitialized_copy((_M_finish - __n) + 1, _M_finish + 1,
+                           _M_finish + 1);
+        _M_finish += __n;
+        _Traits::move(__position + __n,
+                      __position, (__elems_after - __n) + 1);
+        _M_copy(__first, __last, __position);
+      }
+      else {
+        _ForwardIter __mid = __first;
+        advance(__mid, __elems_after + 1);
+        uninitialized_copy(__mid, __last, _M_finish + 1);
+        _M_finish += __n - __elems_after;
+        __STL_TRY {
+          uninitialized_copy(__position, __old_finish + 1, _M_finish);
+          _M_finish += __elems_after;
+        }
+        __STL_UNWIND((destroy(__old_finish + 1, _M_finish), 
+                      _M_finish = __old_finish));
+        _M_copy(__first, __mid, __position);
+      }
+    }
+    else {
+      const size_type __old_size = size();        
+      const size_type __len
+        = __old_size + max(__old_size, static_cast<size_type>(__n)) + 1;
+      pointer __new_start = _M_allocate(__len);
+      pointer __new_finish = __new_start;
+      __STL_TRY {
+        __new_finish = uninitialized_copy(_M_start, __position, __new_start);
+        __new_finish = uninitialized_copy(__first, __last, __new_finish);
+        __new_finish
+          = uninitialized_copy(__position, _M_finish, __new_finish);
+        construct(__new_finish);
+      }
+      __STL_UNWIND((destroy(__new_start,__new_finish),
+                    _M_deallocate(__new_start,__len)));
+      destroy(_M_start, _M_finish + 1);
+      _M_deallocate_block();
+      _M_start = __new_start;
+      _M_finish = __new_finish;
+      _M_end_of_storage = __new_start + __len; 
+    }
+  }
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+basic_string<_CharT,_Traits,_Alloc>&
+basic_string<_CharT,_Traits,_Alloc>
+  ::replace(iterator __first, iterator __last, size_type __n, _CharT __c)
+{
+  const size_type __len = static_cast<size_type>(__last - __first);
+  if (__len >= __n) {
+    _Traits::assign(__first, __n, __c);
+    erase(__first + __n, __last);
+  }
+  else {
+    _Traits::assign(__first, __len, __c);
+    insert(__last, __n - __len, __c);
+  }
+  return *this;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+template <class _InputIter>
+basic_string<_CharT,_Traits,_Alloc>&
+basic_string<_CharT,_Traits,_Alloc>
+  ::replace(iterator __first, iterator __last, _InputIter __f, _InputIter __l,
+            input_iterator_tag) 
+{
+  for ( ; __first != __last && __f != __l; ++__first, ++__f)
+    _Traits::assign(*__first, *__f);
+
+  if (__f == __l)
+    erase(__first, __last);
+  else
+    insert(__last, __f, __l);
+  return *this;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+template <class _ForwardIter>
+basic_string<_CharT,_Traits,_Alloc>&
+basic_string<_CharT,_Traits,_Alloc>
+  ::replace(iterator __first, iterator __last,
+            _ForwardIter __f, _ForwardIter __l,
+            forward_iterator_tag) 
+{
+    const typename iterator_traits<_ForwardIter>::difference_type __n =
+      distance(__f, __l);
+    const difference_type __len = __last - __first;
+    if (__len >= __n) {
+      _M_copy(__f, __l, __first);
+      erase(__first + __n, __last);
+    }
+    else {
+      _ForwardIter m = __f;
+      advance(m, __len);
+      _M_copy(__f, m, __first);
+      insert(__last, m, __l);
+    }
+    return *this;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+basic_string<_CharT,_Traits,_Alloc>::size_type
+basic_string<_CharT,_Traits,_Alloc>
+  ::find(const _CharT* __s, size_type __pos, size_type __n) const 
+{
+  if (__pos >= size())
+    return npos;
+  else {
+    const const_iterator __result =
+      search(_M_start + __pos, _M_finish, 
+             __s, __s + __n, _Eq_traits<_Traits>());
+    return __result != _M_finish ? __result - begin() : npos;
+  }
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+basic_string<_CharT,_Traits,_Alloc>::size_type
+basic_string<_CharT,_Traits,_Alloc>
+  ::find(_CharT __c, size_type __pos) const 
+{
+  if (__pos >= size())
+    return npos;
+  else {
+    const const_iterator __result =
+      find_if(_M_start + __pos, _M_finish,
+              bind2nd(_Eq_traits<_Traits>(), __c));
+    return __result != _M_finish ? __result - begin() : npos;
+  }
+}    
+
+template <class _CharT, class _Traits, class _Alloc>
+basic_string<_CharT,_Traits,_Alloc>::size_type
+basic_string<_CharT,_Traits,_Alloc>
+  ::rfind(const _CharT* __s, size_type __pos, size_type __n) const 
+{
+  const size_t __len = size();
+
+  if (__n > __len)
+    return npos;
+  else if (__n == 0)
+    return min(__len, __pos);
+  else {
+    const const_iterator __last = begin() + min(__len - __n, __pos) + __n;
+    const const_iterator __result = find_end(begin(), __last,
+                                           __s, __s + __n,
+                                           _Eq_traits<_Traits>());
+    return __result != __last ? __result - begin() : npos;
+  }
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+basic_string<_CharT,_Traits,_Alloc>::size_type
+basic_string<_CharT,_Traits,_Alloc>
+  ::rfind(_CharT __c, size_type __pos) const 
+{
+  const size_type __len = size();
+
+  if (__len < 1)
+    return npos;
+  else {
+    const const_iterator __last = begin() + min(__len - 1, __pos) + 1;
+    const_reverse_iterator __rresult =
+      find_if(const_reverse_iterator(__last), rend(),
+              bind2nd(_Eq_traits<_Traits>(), __c));
+    return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
+  }
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+basic_string<_CharT,_Traits,_Alloc>::size_type
+basic_string<_CharT,_Traits,_Alloc>
+  ::find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
+{
+  if (__pos >= size())
+    return npos;
+  else {
+    const const_iterator __result = std::find_first_of(begin() + __pos, end(),
+                                                     __s, __s + __n,
+                                                     _Eq_traits<_Traits>());
+    return __result != _M_finish ? __result - begin() : npos;
+  }
+}
+
+
+template <class _CharT, class _Traits, class _Alloc>
+basic_string<_CharT,_Traits,_Alloc>::size_type
+basic_string<_CharT,_Traits,_Alloc>
+  ::find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
+{
+  const size_type __len = size();
+
+  if (__len < 1)
+    return npos;
+  else {
+    const const_iterator __last = _M_start + min(__len - 1, __pos) + 1;
+    const const_reverse_iterator __rresult =
+      std::find_first_of(const_reverse_iterator(__last), rend(),
+                         __s, __s + __n,
+                         _Eq_traits<_Traits>());
+    return __rresult != rend() ? (__rresult.base() - 1) - _M_start : npos;
+  }
+}
+
+
+template <class _CharT, class _Traits, class _Alloc>
+basic_string<_CharT,_Traits,_Alloc>::size_type
+basic_string<_CharT,_Traits,_Alloc>
+  ::find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
+{
+  if (__pos > size())
+    return npos;
+  else {
+    const_iterator __result = find_if(_M_start + __pos, _M_finish,
+                                _Not_within_traits<_Traits>(__s, __s + __n));
+    return __result != _M_finish ? __result - _M_start : npos;
+  }
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+basic_string<_CharT,_Traits,_Alloc>::size_type
+basic_string<_CharT,_Traits,_Alloc>
+  ::find_first_not_of(_CharT __c, size_type __pos) const
+{
+  if (__pos > size())
+    return npos;
+  else {
+    const_iterator __result
+      = find_if(begin() + __pos, end(),
+                not1(bind2nd(_Eq_traits<_Traits>(), __c)));
+    return __result != _M_finish ? __result - begin() : npos;
+  }
+}    
+
+template <class _CharT, class _Traits, class _Alloc>
+basic_string<_CharT,_Traits,_Alloc>::size_type
+basic_string<_CharT,_Traits,_Alloc>
+  ::find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 
+{
+
+  const size_type __len = size();
+
+  if (__len < 1)
+    return npos;
+  else {
+    const const_iterator __last = begin() + min(__len - 1, __pos) + 1;
+    const const_reverse_iterator __rresult =
+      find_if(const_reverse_iterator(__last), rend(),
+              _Not_within_traits<_Traits>(__s, __s + __n));
+    return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
+  }
+}
+
+template <class _Tp, class _Traits, class _Alloc>
+basic_string<_Tp, _Traits, _Alloc>::size_type
+basic_string<_Tp, _Traits, _Alloc>
+  ::find_last_not_of(_Tp __c, size_type __pos) const 
+{
+  const size_type __len = size();
+
+  if (__len < 1)
+    return npos;
+  else {
+    const const_iterator __last = begin() + min(__len - 1, __pos) + 1;
+    const_reverse_iterator __rresult =
+      find_if(const_reverse_iterator(__last), rend(),
+              not1(bind2nd(_Eq_traits<_Traits>(), __c)));
+    return __rresult != rend() ? (__rresult.base() - 1) - begin() : npos;
+  }
+}
+
+// ------------------------------------------------------------
+// Non-member functions.
+
+// Operator+
+
+template <class _CharT, class _Traits, class _Alloc>
+inline basic_string<_CharT,_Traits,_Alloc>
+operator+(const basic_string<_CharT,_Traits,_Alloc>& __x,
+          const basic_string<_CharT,_Traits,_Alloc>& __y)
+{
+  typedef basic_string<_CharT,_Traits,_Alloc> _Str;
+  typedef typename _Str::_Reserve_t _Reserve_t;
+  _Str __result(_Reserve_t(), __x.size() + __y.size(), __x.get_allocator());
+  __result.append(__x);
+  __result.append(__y);
+  return __result;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline basic_string<_CharT,_Traits,_Alloc>
+operator+(const _CharT* __s,
+          const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  typedef basic_string<_CharT,_Traits,_Alloc> _Str;
+  typedef typename _Str::_Reserve_t _Reserve_t;
+  const size_t __n = _Traits::length(__s);
+  _Str __result(_Reserve_t(), __n + __y.size());
+  __result.append(__s, __s + __n);
+  __result.append(__y);
+  return __result;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline basic_string<_CharT,_Traits,_Alloc>
+operator+(_CharT __c,
+          const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  typedef basic_string<_CharT,_Traits,_Alloc> _Str;
+  typedef typename _Str::_Reserve_t _Reserve_t;
+  _Str __result(_Reserve_t(), 1 + __y.size());
+  __result.push_back(__c);
+  __result.append(__y);
+  return __result;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline basic_string<_CharT,_Traits,_Alloc>
+operator+(const basic_string<_CharT,_Traits,_Alloc>& __x,
+          const _CharT* __s) {
+  typedef basic_string<_CharT,_Traits,_Alloc> _Str;
+  typedef typename _Str::_Reserve_t _Reserve_t;
+  const size_t __n = _Traits::length(__s);
+  _Str __result(_Reserve_t(), __x.size() + __n, __x.get_allocator());
+  __result.append(__x);
+  __result.append(__s, __s + __n);
+  return __result;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline basic_string<_CharT,_Traits,_Alloc>
+operator+(const basic_string<_CharT,_Traits,_Alloc>& __x,
+          const _CharT __c) {
+  typedef basic_string<_CharT,_Traits,_Alloc> _Str;
+  typedef typename _Str::_Reserve_t _Reserve_t;
+  _Str __result(_Reserve_t(), __x.size() + 1, __x.get_allocator());
+  __result.append(__x);
+  __result.push_back(__c);
+  return __result;
+}
+
+// Operator== and operator!=
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator==(const basic_string<_CharT,_Traits,_Alloc>& __x,
+           const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  return __x.size() == __y.size() &&
+         _Traits::compare(__x.data(), __y.data(), __x.size()) == 0;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator==(const _CharT* __s,
+           const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  size_t __n = _Traits::length(__s);
+  return __n == __y.size() && _Traits::compare(__s, __y.data(), __n) == 0;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator==(const basic_string<_CharT,_Traits,_Alloc>& __x,
+           const _CharT* __s) {
+  size_t __n = _Traits::length(__s);
+  return __x.size() == __n && _Traits::compare(__x.data(), __s, __n) == 0;
+}
+
+#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator!=(const basic_string<_CharT,_Traits,_Alloc>& __x,
+           const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  return !(__x == __y);
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator!=(const _CharT* __s,
+           const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  return !(__s == __y);
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator!=(const basic_string<_CharT,_Traits,_Alloc>& __x,
+           const _CharT* __s) {
+  return !(__x == __s);
+}
+
+#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
+
+// Operator< (and also >, <=, and >=).
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator<(const basic_string<_CharT,_Traits,_Alloc>& __x,
+          const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  return basic_string<_CharT,_Traits,_Alloc>
+    ::_M_compare(__x.begin(), __x.end(), __y.begin(), __y.end()) < 0;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator<(const _CharT* __s,
+          const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  size_t __n = _Traits::length(__s);
+  return basic_string<_CharT,_Traits,_Alloc>
+    ::_M_compare(__s, __s + __n, __y.begin(), __y.end()) < 0;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator<(const basic_string<_CharT,_Traits,_Alloc>& __x,
+          const _CharT* __s) {
+  size_t __n = _Traits::length(__s);
+  return basic_string<_CharT,_Traits,_Alloc>
+    ::_M_compare(__x.begin(), __x.end(), __s, __s + __n) < 0;
+}
+
+#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator>(const basic_string<_CharT,_Traits,_Alloc>& __x,
+          const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  return __y < __x;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator>(const _CharT* __s,
+          const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  return __y < __s;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator>(const basic_string<_CharT,_Traits,_Alloc>& __x,
+          const _CharT* __s) {
+  return __s < __x;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator<=(const basic_string<_CharT,_Traits,_Alloc>& __x,
+           const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  return !(__y < __x);
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator<=(const _CharT* __s,
+           const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  return !(__y < __s);
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator<=(const basic_string<_CharT,_Traits,_Alloc>& __x,
+           const _CharT* __s) {
+  return !(__s < __x);
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator>=(const basic_string<_CharT,_Traits,_Alloc>& __x,
+           const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  return !(__x < __y);
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator>=(const _CharT* __s,
+           const basic_string<_CharT,_Traits,_Alloc>& __y) {
+  return !(__s < __y);
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+inline bool
+operator>=(const basic_string<_CharT,_Traits,_Alloc>& __x,
+           const _CharT* __s) {
+  return !(__x < __s);
+}
+
+#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
+
+// Swap.
+
+#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
+
+template <class _CharT, class _Traits, class _Alloc>
+inline void swap(basic_string<_CharT,_Traits,_Alloc>& __x,
+                 basic_string<_CharT,_Traits,_Alloc>& __y) {
+  __x.swap(__y);
+}
+
+#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
+
+// I/O.  (Using istream and ostream only, as opposed to the 
+// basic_istream and basic_ostream templates.  The result is that
+// these functions really don't make all that much sense except
+// for basic_string<char>.)
+
+inline void __sgi_string_fill(ostream& __o, size_t __n)
+{
+  char __f = __o.fill();
+  size_t __i;
+
+  for (__i = 0; __i < __n; __i++) __o.put(__f);
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+ostream& operator<<(ostream& __os, 
+                    const basic_string<_CharT,_Traits,_Alloc>& __s)
+{
+  size_t __n = __s.size();
+  size_t __pad_len = 0;
+  const bool __left = bool(__os.flags() & ios::left);
+  const size_t __w = __os.width();
+
+  if (__w > 0) {
+    __n = min(__w, __n);
+    __pad_len = __w - __n;
+  }
+    
+  if (!__left)
+    __sgi_string_fill(__os, __pad_len);
+  
+  const size_t __nwritten = __os.rdbuf()->sputn(__s.data(), __n);
+
+  if (__left)
+    __sgi_string_fill(__os, __pad_len);
+
+  if (__nwritten != __n)
+    __os.clear(__os.rdstate() | ios::failbit);
+
+  __os.width(0);
+  return __os;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+istream& operator>>(istream& __is, basic_string<_CharT,_Traits,_Alloc>& __s)
+{
+
+  if (__is.flags() & ios::skipws) {
+    _CharT __c;
+    do 
+      __is.get(__c);
+    while (__is && isspace(__c));
+    if (__is)
+      __is.putback(__c);
+  }
+
+  // If we arrive at end of file (or fail for some other reason) while
+  // still discarding whitespace, then we don't try to read the string.
+  if (__is) {
+    __s.clear();
+
+    size_t __n = __is.width();
+    if (__n == 0)
+      __n = static_cast<size_t>(-1);
+    else
+      __s.reserve(__n);
+
+    while (__n-- > 0) {
+      _CharT __c;
+      __is.get(__c);
+      if (!__is) 
+        break;
+      else if (isspace(__c)) {
+        __is.putback(__c);
+        break;
+      }
+      else
+        __s.push_back(__c);
+    }
+    
+    // If we have successfully read some characters, and then arrive
+    // at end of file, the stream should still be marked good.  Note
+    // that we only clear errors that are due to EOF, not other kinds 
+    // of errors.
+    if (__s.size() != 0 && __is.eof())
+      __is.clear((~ios::eofbit & ~ios::failbit) & __is.rdstate());
+  }
+
+  __is.width(0);
+  return __is;
+}
+
+template <class _CharT, class _Traits, class _Alloc>    
+istream& getline(istream& __is,
+                 basic_string<_CharT,_Traits,_Alloc>& __s,
+                 _CharT __delim = '\n') {
+  size_t __nread = 0;
+  if (__is) {
+    __s.clear();
+
+    _CharT __c;
+    while (__nread < __s.max_size() && __is.get(__c)) {
+      ++__nread;
+      if (!_Traits::eq(__c, __delim)) 
+        __s.push_back(__c);
+      else
+        break;                  // Character is extracted but not appended.
+    }
+  }
+
+  if (__nread == 0 || __nread >= __s.max_size())
+    __is.clear(__is.rdstate() | ios::failbit);
+  return __is;
+}
+
+template <class _CharT, class _Traits, class _Alloc>
+void _S_string_copy(const basic_string<_CharT,_Traits,_Alloc>& __s,
+                    _CharT* __buf,
+                    size_t __n)
+{
+  if (__n > 0) {
+    const size_t __n = min(__n - 1, __s.size());
+    copy(__s.begin(), __s.begin() + __n, __buf);
+    __buf[__n] = _CharT();
+  }
+}
+
+// ------------------------------------------------------------
+// Typedefs
+
+typedef basic_string<char> string;
+typedef basic_string<wchar_t> wstring;
+
+
+#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
+#pragma reset woff 1174
+#pragma reset woff 1375
+#endif
+
+__STL_END_NAMESPACE
+
+#include <stl_hash_fun.h>
+
+__STL_BEGIN_NAMESPACE
+
+template <class _CharT, class _Traits, class _Alloc>
+struct hash<basic_string<_CharT,_Traits,_Alloc> > {
+  size_t operator()(const basic_string<_CharT,_Traits,_Alloc>& __s) const {
+    unsigned long __h = 0; 
+    for (basic_string<_CharT,_Traits,_Alloc>::const_iterator __i
+           = __s.begin();
+         __i != __s.end();
+         ++__i)
+      __h = 5*__h + *__i;
+    return size_t(__h);
+  }
+};
+
+__STL_END_NAMESPACE
+
+#endif /* __SGI_STL_STRING */
+
+
+// Local Variables:
+// mode:C++
+// End:
+