_hashtable.h

来自「stl的源码」· C头文件 代码 · 共 659 行 · 第 1/2 页

  hashtable(const _Self& __ht)
    : _M_hash(__ht._M_hash),
      _M_equals(__ht._M_equals),
      _M_elems(__ht.get_allocator()),
      _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(), _BucketType*)),
      _M_num_elements(0),
      _M_max_load_factor(1.0f)
  { _M_copy_from(__ht); }

#if !defined (_STLP_NO_MOVE_SEMANTIC)
  hashtable(__move_source<_Self> src)
    : _M_hash(_STLP_PRIV _AsMoveSource(src.get()._M_hash)),
      _M_equals(_STLP_PRIV _AsMoveSource(src.get()._M_equals)),
      _M_elems(__move_source<_ElemsCont>(src.get()._M_elems)),
      _M_buckets(__move_source<_BucketVector>(src.get()._M_buckets)),
      _M_num_elements(src.get()._M_num_elements),
      _M_max_load_factor(src.get()._M_max_load_factor) {}
#endif

  _Self& operator= (const _Self& __ht) {
    if (&__ht != this) {
      clear();
      _M_hash = __ht._M_hash;
      _M_equals = __ht._M_equals;
      _M_copy_from(__ht);
    }
    return *this;
  }

  ~hashtable() { clear(); }

  size_type size() const { return _M_num_elements; }
  size_type max_size() const { return size_type(-1); }
  bool empty() const { return size() == 0; }

  void swap(_Self& __ht) {
    _STLP_STD::swap(_M_hash, __ht._M_hash);
    _STLP_STD::swap(_M_equals, __ht._M_equals);
    _M_elems.swap(__ht._M_elems);
    _M_buckets.swap(__ht._M_buckets);
    _STLP_STD::swap(_M_num_elements, __ht._M_num_elements);
    _STLP_STD::swap(_M_max_load_factor, __ht._M_max_load_factor);
  }

  iterator begin() { return _M_elems.begin(); }
  iterator end() { return _M_elems.end(); }
  local_iterator begin(size_type __n) { return _ElemsIte(_M_buckets[__n]); }
  local_iterator end(size_type __n) { return _ElemsIte(_M_buckets[__n + 1]); }

  const_iterator begin() const { return __CONST_CAST(_ElemsCont&, _M_elems).begin(); }
  const_iterator end() const { return __CONST_CAST(_ElemsCont&, _M_elems).end(); }
  const_local_iterator begin(size_type __n) const { return _ElemsIte(_M_buckets[__n]); }
  const_local_iterator end(size_type __n) const { return _ElemsIte(_M_buckets[__n + 1]); }

  //static bool _STLP_CALL _M_equal (const _Self&, const _Self&);

public:
  //The number of buckets is size() - 1 because the last bucket always contains
  //_M_elems.end() to make algo easier to implement.
  size_type bucket_count() const { return _M_buckets.size() - 1; }
  size_type max_bucket_count() const { return _STLP_PRIV _Stl_prime_type::_S_max_nb_buckets(); }
  size_type elems_in_bucket(size_type __bucket) const
  { return _STLP_STD::distance(_ElemsIte(_M_buckets[__bucket]), _ElemsIte(_M_buckets[__bucket + 1])); }

  _STLP_TEMPLATE_FOR_CONT_EXT
  size_type bucket(const _KT& __k) const { return _M_bkt_num_key(__k); }

  // hash policy
  float load_factor() const { return (float)size() / (float)bucket_count(); }
  float max_load_factor() const { return _M_max_load_factor; }
  void max_load_factor(float __z) {
    _M_max_load_factor = __z;
    _M_resize();
  }

  pair<iterator, bool> insert_unique(const value_type& __obj) {
    _M_enlarge(_M_num_elements + 1);
    return insert_unique_noresize(__obj);
  }

  iterator insert_equal(const value_type& __obj) {
    _M_enlarge(_M_num_elements + 1);
    return insert_equal_noresize(__obj);
  }

protected:
  iterator _M_insert_noresize(size_type __n, const value_type& __obj);
public:
  pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
  iterator insert_equal_noresize(const value_type& __obj);

#if defined (_STLP_MEMBER_TEMPLATES)
  template <class _InputIterator>
  void insert_unique(_InputIterator __f, _InputIterator __l)
  { insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }

  template <class _InputIterator>
  void insert_equal(_InputIterator __f, _InputIterator __l)
  { insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }

  template <class _InputIterator>
  void insert_unique(_InputIterator __f, _InputIterator __l,
                     const input_iterator_tag &) {
    for ( ; __f != __l; ++__f)
      insert_unique(*__f);
  }

  template <class _InputIterator>
  void insert_equal(_InputIterator __f, _InputIterator __l,
                    const input_iterator_tag &) {
    for ( ; __f != __l; ++__f)
      insert_equal(*__f);
  }

  template <class _ForwardIterator>
  void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
                     const forward_iterator_tag &) {
    size_type __n = _STLP_STD::distance(__f, __l);
    _M_enlarge(_M_num_elements + __n);
    for ( ; __n > 0; --__n, ++__f)
      insert_unique_noresize(*__f);
  }

  template <class _ForwardIterator>
  void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
                    const forward_iterator_tag &) {
    size_type __n = _STLP_STD::distance(__f, __l);
    _M_enlarge(_M_num_elements + __n);
    for ( ; __n > 0; --__n, ++__f)
      insert_equal_noresize(*__f);
  }

#else /* _STLP_MEMBER_TEMPLATES */
  void insert_unique(const value_type* __f, const value_type* __l) {
    size_type __n = __l - __f;
    _M_enlarge(_M_num_elements + __n);
    for ( ; __n > 0; --__n, ++__f)
      insert_unique_noresize(*__f);
  }

  void insert_equal(const value_type* __f, const value_type* __l) {
    size_type __n = __l - __f;
    _M_enlarge(_M_num_elements + __n);
    for ( ; __n > 0; --__n, ++__f)
      insert_equal_noresize(*__f);
  }

  void insert_unique(const_iterator __f, const_iterator __l) {
    size_type __n = _STLP_STD::distance(__f, __l);
    _M_enlarge(_M_num_elements + __n);
    for ( ; __n > 0; --__n, ++__f)
      insert_unique_noresize(*__f);
  }

  void insert_equal(const_iterator __f, const_iterator __l) {
    size_type __n = _STLP_STD::distance(__f, __l);
    _M_enlarge(_M_num_elements + __n);
    for ( ; __n > 0; --__n, ++__f)
      insert_equal_noresize(*__f);
  }
#endif /*_STLP_MEMBER_TEMPLATES */

  //reference find_or_insert(const value_type& __obj);

private:
  _STLP_TEMPLATE_FOR_CONT_EXT
  _ElemsIte _M_find(const _KT& __key) const {
    size_type __n = _M_bkt_num_key(__key);
    _ElemsIte __first(_M_buckets[__n]);
    _ElemsIte __last(_M_buckets[__n + 1]);
    for ( ; (__first != __last) && !_M_equals(_M_get_key(*__first), __key); ++__first);
    if (__first != __last)
      return __first;
    else
      return __CONST_CAST(_ElemsCont&, _M_elems).end();
  }

public:
  _STLP_TEMPLATE_FOR_CONT_EXT
  iterator find(const _KT& __key) { return _M_find(__key); }
  _STLP_TEMPLATE_FOR_CONT_EXT
  const_iterator find(const _KT& __key) const { return _M_find(__key); }

  _STLP_TEMPLATE_FOR_CONT_EXT
  size_type count(const _KT& __key) const {
    const size_type __n = _M_bkt_num_key(__key);

    _ElemsIte __cur(_M_buckets[__n]);
    _ElemsIte __last(_M_buckets[__n + 1]);
    for (; __cur != __last; ++__cur) {
      if (_M_equals(_M_get_key(*__cur), __key)) {
        size_type __result = 1;
        for (++__cur;
             __cur != __last && _M_equals(_M_get_key(*__cur), __key);
             ++__result, ++__cur);
        return __result;
      }
    }
    return 0;
  }

  _STLP_TEMPLATE_FOR_CONT_EXT
  pair<iterator, iterator> equal_range(const _KT& __key) {
    typedef pair<iterator, iterator> _Pii;
    const size_type __n = _M_bkt_num_key(__key);

    for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
         __first != __last; ++__first) {
      if (_M_equals(_M_get_key(*__first), __key)) {
        _ElemsIte __cur(__first);
        for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
        return _Pii(__first, __cur);
      }
    }
    return _Pii(end(), end());
  }

  _STLP_TEMPLATE_FOR_CONT_EXT
  pair<const_iterator, const_iterator> equal_range(const _KT& __key) const {
    typedef pair<const_iterator, const_iterator> _Pii;
    const size_type __n = _M_bkt_num_key(__key);

    for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
         __first != __last; ++__first) {
      if (_M_equals(_M_get_key(*__first), __key)) {
        _ElemsIte __cur(__first);
        for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
        return _Pii(__first, __cur);
      }
    }
    return _Pii(end(), end());
  }

  size_type erase(const key_type& __key);
  void erase(const_iterator __it);
  void erase(const_iterator __first, const_iterator __last);

private:
  void _M_enlarge(size_type __n);
  void _M_reduce();
  void _M_resize();
  void _M_rehash(size_type __num_buckets);
#if defined (_STLP_DEBUG)
  void _M_check() const;
#endif

public:
  void rehash(size_type __num_buckets_hint);
  void resize(size_type __num_buckets_hint)
  { rehash(__num_buckets_hint); }
  void clear();

  // this is for hash_map::operator[]
  reference _M_insert(const value_type& __obj);

private:
  //__n is set to the first bucket that has to be modified if any
  //erase/insert operation is done after the returned iterator.
  iterator _M_before_begin(size_type &__n) const;

  static iterator _S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
                                  size_type &__n);

  void _M_initialize_buckets(size_type __n) {
    const size_type __n_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__n) + 1;
    _M_buckets.reserve(__n_buckets);
    _M_buckets.assign(__n_buckets, __STATIC_CAST(_BucketType*, 0));
  }

  _STLP_TEMPLATE_FOR_CONT_EXT
  size_type _M_bkt_num_key(const _KT& __key) const
  { return _M_bkt_num_key(__key, bucket_count()); }

  size_type _M_bkt_num(const value_type& __obj) const
  { return _M_bkt_num_key(_M_get_key(__obj)); }

  _STLP_TEMPLATE_FOR_CONT_EXT
  size_type _M_bkt_num_key(const _KT& __key, size_type __n) const
  { return _M_hash(__key) % __n; }

  size_type _M_bkt_num(const value_type& __obj, size_t __n) const
  { return _M_bkt_num_key(_M_get_key(__obj), __n); }

  void _M_copy_from(const _Self& __ht);
};

#if defined (_STLP_DEBUG)
#  undef hashtable
_STLP_MOVE_TO_STD_NAMESPACE
#endif

_STLP_END_NAMESPACE

#if !defined (_STLP_LINK_TIME_INSTANTIATION)
#  include <stl/_hashtable.c>
#endif

#if defined (_STLP_DEBUG)
#  include <stl/debug/_hashtable.h>
#endif

_STLP_BEGIN_NAMESPACE

#define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
#define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
#include <stl/_relops_hash_cont.h>
#undef _STLP_TEMPLATE_CONTAINER
#undef _STLP_TEMPLATE_HEADER

#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
struct __move_traits<hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> > {
  //Hashtables are movable:
  typedef __true_type implemented;

  //Completeness depends on many template parameters, for the moment we consider it not complete:
  typedef __false_type complete;
};
#endif

_STLP_END_NAMESPACE

#endif /* _STLP_INTERNAL_HASHTABLE_H */

// Local Variables:
// mode:C++
// End: