string

c++ STL source code, hash and vector etc

    if (__first != __last) {
                                // The move includes the terminating null.
      _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.
#ifdef __STL_MEMBER_TEMPLATES
  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());
  }
#else /* __STL_MEMBER_TEMPLATES */
  basic_string& replace(iterator __first, iterator __last,
                        const _CharT* __f, const _CharT* __l);
#endif /* __STL_MEMBER_TEMPLATES */

private:                        // Helper functions for replace.

#ifdef __STL_MEMBER_TEMPLATES

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

#endif /* __STL_MEMBER_TEMPLATES */

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

public:                        // Helper function 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));
  }
};



// ------------------------------------------------------------
// Non-inline declarations.

template <class _CharT, class _Traits, class _Alloc> 
const basic_string<_CharT,_Traits,_Alloc>::size_type 
basic_string<_CharT,_Traits,_Alloc>::npos 
  = (basic_string<_CharT,_Traits,_Alloc>::size_type) -1;

// Change the string's capacity so that it is large enough to hold
//  at least __res_arg elements, plus the terminating null.  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);
    _M_construct_null(__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 {
      _M_construct_null(_M_finish + __n);
    }
    __STL_UNWIND(destroy(_M_finish + 1, _M_finish + __n));
    _Traits::assign(*_M_finish, __c);
    _M_finish += __n;
  }
  return *this;
}

#ifdef __STL_MEMBER_TEMPLATES

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();
    difference_type __n = 0;
    distance(__first, __last, __n);
    if (static_cast<size_type>(__n) > max_size() ||
        __old_size > max_size() - static_cast<size_type>(__n))
      _M_throw_length_error();
    if (__old_size + static_cast<size_type>(__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);
        _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 {
      _ForwardIter __f1 = __first;
      ++__f1;
      uninitialized_copy(__f1, __last, _M_finish + 1);