string

c++ STL source code, hash and vector etc

      __STL_TRY {
        _M_construct_null(_M_finish + __n);
      }
      __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n));
      _Traits::assign(*_M_finish, *__first);
      _M_finish += __n;
    }
  }
  return *this;  
}

#else /* __STL_MEMBER_TEMPLATES */

template <class _Tp, class _Traits, class _Alloc> 
basic_string<_Tp, _Traits, _Alloc>& 
basic_string<_Tp, _Traits, _Alloc>::append(const _Tp* __first,
                                           const _Tp* __last)
{
  if (__first != __last) {
    const size_type __old_size = size();
    ptrdiff_t __n = __last - __first;
    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, (size_t) __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);
        _M_construct_null(__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 {
      const _Tp* __f1 = __first;
      ++__f1;
      uninitialized_copy(__f1, __last, _M_finish + 1);
      __STL_TRY {
        _M_construct_null(_M_finish + __n);
      }
      __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n));
      _Traits::assign(*_M_finish, *__first);
      _M_finish += __n;
    }
  }
  return *this;  
}

#endif /* __STL_MEMBER_TEMPLATES */

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;
}

#ifdef __STL_MEMBER_TEMPLATES

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;
}

#endif /* __STL_MEMBER_TEMPLATES */

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 (static_cast<size_type>(__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) {
    _M_construct_null(_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);
      _M_construct_null(__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);
        _M_construct_null(__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;    
    }
  }
}

#ifdef __STL_MEMBER_TEMPLATES

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) {
    difference_type __n = 0;
    distance(__first, __last, __n);
    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);
        _M_construct_null(__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 /* __STL_MEMBER_TEMPLATES */

template <class _CharT, class _Traits, class _Alloc>
void 
basic_string<_CharT,_Traits,_Alloc>::insert(iterator __position,
                                            const _CharT* __first, 
                                            const _CharT* __last)
{
  if (__first != __last) {
    const ptrdiff_t __n = __last - __first;
    if (_M_end_of_storage - _M_finish >= __n + 1) {
      const ptrdiff_t __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 {
        const _CharT* __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);
        _M_construct_null(__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; 
    }
  }
}

#endif /* __STL_MEMBER_TEMPLATES */

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;
}

#ifdef __STL_MEMBER_TEMPLATES

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) 
{
  difference_type __n = 0;
  distance(__f, __l, __n);
  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;
}

#else /* __STL_MEMBER_TEMPLATES */

template <class _CharT, class _Traits, class _Alloc>
basic_string<_CharT,_Traits,_Alloc>&