string

c++ STL source code, hash and vector etc

basic_string<_CharT,_Traits,_Alloc>
  ::replace(iterator __first, iterator __last,
            const _CharT* __f, const _CharT* __l)
{
  const ptrdiff_t         __n = __l - __f;
  const difference_type __len = __last - __first;
  if (__len >= __n) {
    _M_copy(__f, __l, __first);
    erase(__first + __n, __last);
  }
  else {
    const _CharT* __m = __f + __len;
    _M_copy(__f, __m, __first);
    insert(__last, __m, __l);
  }
  return *this;
}

#endif /* __STL_MEMBER_TEMPLATES */

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 + __n > 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_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;
  _Reserve_t __reserve;
  _Str __result(__reserve, __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;
  _Reserve_t __reserve;
  const size_t __n = _Traits::length(__s);
  _Str __result(__reserve, __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;
  _Reserve_t __reserve;
  _Str __result(__reserve, 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;
  _Reserve_t __reserve;
  const size_t __n = _Traits::length(__s);
  _Str __result(__reserve, __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;
  _Reserve_t __reserve;
  _Str __result(__reserve, __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>
in