template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>&
basic_string<_CharT, _Traits, _Allocator>::
assign (const basic_string &__str, size_type __pos, size_type __n)
{
    _RWSTD_REQUIRES (__pos <= __str.size (),
                     (_RWSTD_ERROR_OUT_OF_RANGE,
                      _RWSTD_FUNC ("basic_string::assign(basic_string&, "
                                   "size_type, size_type)"),
                      __pos, __str.size ()));

    size_type __slen = __str.size() - __pos;
    size_type __rlen = __n < __slen ? __n : __slen; 
    return replace(0, size(), __str, __pos, __rlen);
}


template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>&
basic_string<_CharT, _Traits, _Allocator>::
insert (size_type __pos1, const basic_string& __str, 
        size_type  __pos2,  size_type         __n)
{
    _RWSTD_REQUIRES (__pos1 <= size() && __pos2 <= __str.size (),
                     (_RWSTD_ERROR_OUT_OF_RANGE,
                      _RWSTD_FUNC ("basic_string::insert(size_type, const "
                                   "basic_string&, size_type, size_type)"), 
                      __pos1 > size() ? __pos1:__pos2, __str.size ()));
    
    size_type __slen = __str.size() - __pos2;
    size_type __rlen = __n < __slen ? __n : __slen; 

    _RWSTD_REQUIRES (size () <= max_size () - __rlen,
                     (_RWSTD_ERROR_LENGTH_ERROR,
                      _RWSTD_FUNC ("basic_string::insert(size_type, const "
                                   "basic_string&, size_type, size_type)"), 
                      size (), max_size () - __rlen));

    return replace(__pos1, 0, __str, __pos2, __n);
}

template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>&
basic_string<_CharT, _Traits, _Allocator>::
insert (size_type __pos1, const basic_string &__str)
{
    _RWSTD_REQUIRES (__pos1 <= size (),
                     (_RWSTD_ERROR_OUT_OF_RANGE,
                      _RWSTD_FUNC ("basic_string::insert(size_type, const "
                                   "basic_string&)"), __pos1, size ()));
    
    _RWSTD_REQUIRES (size() <= max_size() - __str.size(),
                     (_RWSTD_ERROR_LENGTH_ERROR,
                      _RWSTD_FUNC ("basic_string::insert(size_type, "
                                   "const basic_string&)"),
                      size (), max_size () - __str.size ()));

    return replace(__pos1, 0, __str);
}


template <class _CharT, class _Traits, class _Allocator>
_TYPENAME basic_string<_CharT, _Traits, _Allocator>::iterator 
basic_string<_CharT, _Traits, _Allocator>::
replace (size_type __pos1, size_type __n1, const_pointer __cs, 
         size_type __cslen, size_type __pos2, size_type __n2)
{
    _RWSTD_REQUIRES (__pos1 <= size () && __pos2 <= __cslen,
                     (_RWSTD_ERROR_OUT_OF_RANGE, 
                      _RWSTD_FUNC ("basic_string::replace(size_type, size_type,"
                                   " const_pointer, size_type, size_type, "
                                   "size_type)"), 
                      __pos1 > size() ? __pos1 : __pos2,
                      size () > __cslen ? size () : __cslen));

    size_type __slen = size() - __pos1;
    size_type __xlen = __n1 < __slen ? __n1 : __slen; 
    size_type __clen = __cslen - __pos2;
    size_type __rlen = __n2 < __clen ? __n2 : __clen; 

    _RWSTD_REQUIRES (size () - __xlen <= max_size () - __rlen,
                     (_RWSTD_ERROR_LENGTH_ERROR,
                      _RWSTD_FUNC ("basic_string::replace(size_type, size_type,"
                                   " const_pointer, size_type, size_type, "
                                   "size_type)"), 
                      size () - __xlen, max_size() - __rlen));

    size_type __len = size() - __xlen + __rlen;  // final string length

    if (!__len) {
        // Special case a substitution that leaves the string empty.
        _C_unlink ();
        _C_data = _C_null ();
    }
    else {
        // Length of bit at end of string
        size_type __rem = size () - __xlen - __pos1;
        // Check for shared representation, insufficient capacity, 
        //  or overlap copy.
        if (   _C_pref()->_C_ref_count () > 1
            || capacity () < __len
            || __cs && __cs >= data () && __cs < data () + size ()) {
            // Need to allocate a new reference.
            size_t __new_capacity = max (_RW::__rw_new_capacity (size(), this),
                                         size_t (__len));
            _C_string_ref_type * __temp = _C_getRep(__new_capacity, __len);
            if (__pos1)
                traits_type::copy (__temp->data (), _C_data, __pos1);

            if (__rlen)
                traits_type::copy (__temp->data() + __pos1,
                                   __cs + __pos2, __rlen);

            if (__rem)
                traits_type::copy (__temp->data() + __pos1 + __rlen,
                                   _C_data + __pos1 + __n1, __rem);
            _C_unlink();
            _C_data = __temp->data();
        }
        else {
            // Current reference has enough room.
            if (__rem)
                traits_type::move (_C_data + __pos1 + __rlen,
                                   _C_data + __pos1 + __n1, __rem);

            if (__rlen)
                traits_type::move (_C_data + __pos1, __cs + __pos2, __rlen);

            traits_type::assign (_C_data [_C_pref()->_C_size = __len],
                                 value_type ());
        }
    }
    return _C_make_iter (_C_data + __pos1);
}


template <class _CharT, class _Traits, class _Allocator>
basic_string<_CharT, _Traits, _Allocator>&
basic_string<_CharT, _Traits, _Allocator>::
replace (size_type __pos, size_type __n, size_type __n2, value_type __c)
{
    _RWSTD_REQUIRES (__pos <= size (),
                     (_RWSTD_ERROR_OUT_OF_RANGE, 
                      _RWSTD_FUNC ("basic_string:::replace(size_type, "
                                   "size_type, size_type, value_type)"),
                      __pos, size ()));
    
    size_type __slen = size() - __pos;
    size_type __xlen = __n < __slen ? __n : __slen; 

    _RWSTD_REQUIRES (size() - __xlen < max_size () - __n2,
                     (_RWSTD_ERROR_LENGTH_ERROR,
                      _RWSTD_FUNC ("basic_string::replace(size_type, "
                                   "size_type, size_type, value_type)"), 
                      size () - __xlen, max_size () - __n2));
    
    size_type __len = size() - __xlen + __n2;  // Final string length.

    if (!__len)
    {
      // Special case a substitution that leaves the string empty.
      _C_unlink();
      _C_data = _C_null ();
    }
    else
    {
      size_type __rem = size () - __xlen - __pos; // length of bit at the end
      // Check for shared representation, insufficient capacity, 
      if ( (_C_pref()->_C_ref_count() > 1) || (capacity() < __len))
      {
        // Need to allocate a new reference.
          size_t __new_capacity = max (_RW::__rw_new_capacity (size(), this),
                                       size_t (__len));
        _C_string_ref_type * __temp = _C_getRep(__new_capacity, __len);
        if (__pos) traits_type::copy(__temp->data(), _C_data, __pos);
        if (__n2) traits_type::assign(__temp->data()+__pos, __n2, __c);
        if (__rem)
            traits_type::copy (__temp->data () + __pos + __n2,
                               _C_data + __pos + __n, __rem);
        _C_unlink();
        _C_data = __temp->data();
      }
      else
      {
        // Current reference has enough room.
        if (__rem) 
            traits_type::move(_C_data+__pos+__n2, _C_data+__pos+__n, __rem);
        if (__n2)
            traits_type::assign(_C_data+__pos, __n2, __c);
        traits_type::assign (_C_data [_C_pref()->_C_size = __len],
                             value_type ());
      }
    }
    return *this;
}


#if     !defined (_RWSTD_NO_MEMBER_TEMPLATES)   \
     && !defined (_RWSTD_NO_CLASS_PARTIAL_SPEC)

template<class _CharT, class _Traits, class _Allocator>
template<class _InputIter>
basic_string<_CharT, _Traits, _Allocator>& 
basic_string<_CharT, _Traits, _Allocator>::
replace (iterator __first1, iterator __last1,
         _InputIter __first2, _InputIter __last2, _RWSTD_DISPATCH_INT (false))
{
    _RWSTD_ASSERT_RANGE (__first1, _C_make_iter (_C_data + size ()));
    _RWSTD_ASSERT_RANGE (__first1, __last1);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

     // use a (probably) faster algorithm if possible
     if (__is_bidirectional_iterator(_RWSTD_ITERATOR_CATEGORY (_InputIter,
                                                               __last2)))
         return __replace_aux (__first1, __last1, __first2, __last2);

     for ( ; __first2 != __last2; ++__first1, ++__first2) {

         size_type __off = __first1 - _C_make_iter (_C_data);

         _RWSTD_REQUIRES (__off <= max_size(),
                          (_RWSTD_ERROR_LENGTH_ERROR,
                           _RWSTD_FUNC ("basic_string::replace(iterator, "
                                        "iterator, InputIterator, "
                                        "InputIterator)"),
                           __first1 - _C_make_iter (_C_data), max_size ()));
         
         // extend the string if necessary
         if (__first1 == __last1) {
             // compute the size of new buffer
             size_t __new_cap = _RW::__rw_new_capacity (size (), this);
             size_t __delta   = __new_cap - size ();

             // allocate a new buffer
             _C_string_ref_type *__tmp = _C_getRep (__new_cap, __new_cap);

             // copy data from old to new, leaving a hole for additions
             traits_type::copy (__tmp->data (), _C_data, __off);
             traits_type::copy (__tmp->data () + __off + __delta,
                                _C_data + __off,
                                _C_make_iter (_C_data + size ()) - __last1);
             _C_unlink ();
             _C_data  = __tmp->data ();
             __first1 = _C_make_iter (_C_data + __off);
             __last1  = __first1 + __delta;
         }

         // copy data over
         traits_type::assign (*__first1, *__first2);
     }

     if (__first1 != __last1)
         replace (__first1 - _C_make_iter (_C_data), __last1 - __first1,
                  0, value_type ());

     return *this;
}

// Special function for random access and bi-directional iterators
// Avoids the possibility of multiple allocations
// We still have to copy characters over one at a time.
template<class _CharT, class _Traits, class _Allocator>
template<class _InputIterator>
basic_string<_CharT, _Traits, _Allocator>& 
basic_string<_CharT, _Traits, _Allocator>::
__replace_aux (iterator __first1, iterator __last1, 
               _InputIterator __first2, _InputIterator __last2)
{
    _RWSTD_ASSERT_RANGE (__first1, _C_make_iter (_C_data + size ()));
    _RWSTD_ASSERT_RANGE (__first1, __last1);
    _RWSTD_ASSERT_RANGE (__first2, __last2);

    difference_type __n2  = _DISTANCE (__first2, __last2, __n2);
    size_type       __n   = __last1 - __first1;
    size_type       __pos = __first1 - _C_make_iter (_C_data);

    _RWSTD_REQUIRES (__pos <= size (),
                     (_RWSTD_ERROR_OUT_OF_RANGE,
                      _RWSTD_FUNC ("basic_string::__replace_aux(iterator, "
                                   "iterator, InputIterator, InputIterator)"),
                      __pos, size ()));

    size_type __slen = size() - __pos;
    size_type __xlen = __n < __slen ? __n : __slen; 

    _RWSTD_REQUIRES (size () - __xlen < max_size() - __n2,
                     (_RWSTD_ERROR_LENGTH_ERROR, 
                      _RWSTD_FUNC ("basic_string::__replace_aux(iterator, "
                                   "iterator, InputIterator, InputIterator)"),
                      size () - __xlen, max_size () - __n2));

    size_type __len = size() - __xlen + __n2;  // Final string length.

    if (!__len) {
        // Special case a substitution that leaves the string empty.
        _C_unlink();
        _C_data = _C_null ();