string

c++ STL source code, hash and vector etc

#   else
    return (_CharT) 0;
#   endif
  }

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 {
      _M_construct_null(_M_finish);
    }
    __STL_UNWIND(destroy(_M_start, _M_finish));
  }

#ifdef __STL_MEMBER_TEMPLATES
    
  template <class _InputIter>
  void _M_range_initialize(_InputIter __f, _InputIter __l,
                           input_iterator_tag) {
    _M_allocate_block(8);
    _M_construct_null(_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) {
    difference_type __n = 0;
    distance(__f, __l, __n);
    _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);
  }
    
#else /* __STL_MEMBER_TEMPLATES */

  void _M_range_initialize(const _CharT* __f, const _CharT* __l) {
    ptrdiff_t __n = __l - __f;
    _M_allocate_block(__n + 1);
    _M_finish = uninitialized_copy(__f, __l, _M_start);
    _M_terminate_string();
  }

#endif /* __STL_MEMBER_TEMPLATES */

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

  size_t max_size() const { return _Base::max_size(); }


  void resize(size_type __n, _CharT __c) {
    if (__n <= size())
      erase(begin() + __n, end());
    else
      append(__n - size(), __c);
  }

  void resize(size_type __n) { resize(__n, _M_null()); }

  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, _M_null());
      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);

#ifdef __STL_MEMBER_TEMPLATES

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

#else /* __STL_MEMBER_TEMPLATES */

  basic_string& append(const _CharT* __first, const _CharT* __last);

#endif /* __STL_MEMBER_TEMPLATES */

  void push_back(_CharT __c) {
    if (_M_finish + 1 == _M_end_of_storage)
      reserve(size() + max(size(), static_cast<size_type>(1)));
    _M_construct_null(_M_finish + 1);
    _Traits::assign(*_M_finish, __c);
    ++_M_finish;
  }

  void pop_back() {
    _Traits::assign(*(_M_finish - 1), _M_null());
    destroy(_M_finish);
    --_M_finish;
  }

private:                        // Helper functions for append.

#ifdef __STL_MEMBER_TEMPLATES

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

#endif /* __STL_MEMBER_TEMPLATES */

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

#ifdef __STL_MEMBER_TEMPLATES

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

#endif  /* __STL_MEMBER_TEMPLATES */

  basic_string& assign(const _CharT* __f, const _CharT* __l);

private:                        // Helper functions for assign.

#ifdef __STL_MEMBER_TEMPLATES

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

#endif  /* __STL_MEMBER_TEMPLATES */

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

#ifdef __STL_MEMBER_TEMPLATES

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

#else /* __STL_MEMBER_TEMPLATES */

  void insert(iterator __p, const _CharT* __first, const _CharT* __last);

#endif /* __STL_MEMBER_TEMPLATES */

private:                        // Helper functions for insert.

#ifdef __STL_MEMBER_TEMPLATES

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

  template <class _InputIterator>
  void 
  _M_copy(_InputIterator __first, _InputIterator __last, iterator __result) {
    for ( ; __first != __last; ++__first, ++__result)
      _Traits::assign(*__result, *__first);
  }

#endif /* __STL_MEMBER_TEMPLATES */

  iterator _M_insert_aux(iterator, _CharT);

  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 null.
    _Traits::move(__position, __position + 1, _M_finish - __position);
    destroy(_M_finish);
    --_M_finish;
    return __position;
  }

  iterator erase(iterator __first, iterator __last) {