vcl_hashtable.h

来自「DTMK软件开发包,此为开源软件,是一款很好的医学图像开发资源.」· C头文件 代码 · 共 1,014 行 · 第 1/3 页

  vcl_hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
 friend struct
  vcl_hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;

 public:
  vcl_hashtable(size_type n,
                const HashFcn&    hf,
                const EqualKey&   eql,
                const ExtractKey& ext)
    : hashfun(hf), equals(eql), get_key(ext)
  {
    VCL_debug_do(safe_init(this));
    initialize_buckets(n);
  }

  vcl_hashtable(size_type n,
                const HashFcn&    hf,
                const EqualKey&   eql)
    : hashfun(hf), equals(eql), get_key(ExtractKey())
  {
    VCL_debug_do(safe_init(this));
    initialize_buckets(n);
  }

  vcl_hashtable(const self& ht)
    : hashfun(ht.hashfun), equals(ht.equals), get_key(ht.get_key)
  {
    VCL_debug_do(safe_init(this));
    copy_from(ht);
  }

  self& operator= (const self& ht)
  {
    if (&ht != this) {
      hashfun = ht.hashfun;
      equals = ht.equals;
      get_key = ht.get_key;
      clear();
      buckets.clear();
      copy_from(ht);
    }
    return *this;
  }

  ~vcl_hashtable() {}

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

  void swap(self& ht)
  {
    vcl_swap(hashfun, ht.hashfun);
    vcl_swap(equals, ht.equals);
    vcl_swap(get_key, ht.get_key);
    buckets.swap(ht.buckets);
    vcl_swap(num_elements, ht.num_elements);
    VCL_debug_do(swap_owners(ht));
  }

  iterator begin()
  {
    for (size_type n = 0; n < buckets.size(); ++n)
      if (buckets[n])
        return iterator(buckets[n], this);
    return end();
  }

  iterator end() { return iterator((node*)0, this); }

  const_iterator begin() const
  {
    for (size_type n = 0; n < buckets.size(); ++n)
      if (buckets[n])
        return const_iterator(buckets[n], this);
    return end();
  }

  const_iterator end() const { return const_iterator((node*)0, this); }

  bool operator== VCL_NULL_TMPL_ARGS (const self& ht2) const
  {
    if (buckets.size() != ht2.buckets.size())
      return false;
    for (int n = 0; n < buckets.size(); ++n) {
      typename node* cur1 = buckets[n];
      typename node* cur2 = ht2.buckets[n];
      for (; cur1 && cur2 && cur1->val == cur2->val;
            cur1 = cur1->next, cur2 = cur2->next)
        {}
      if (cur1 || cur2)
        return false;
    }
    return true;
  }

 public:

  size_type bucket_count() const { return buckets.size(); }

  size_type max_bucket_count() const
    { return VCL_prime_list[VCL_num_primes - 1]; }

  size_type elems_in_bucket(size_type bucket) const
  {
    size_type result = 0;
    for (node* cur = buckets[bucket]; cur; cur = cur->next)
      result += 1;
    return result;
  }

  vcl_pair<iterator, bool> insert_unique(const value_type& obj)
  {
    resize(num_elements + 1);
    return insert_unique_noresize(obj);
  }

  iterator insert_equal(const value_type& obj)
  {
    resize(num_elements + 1);
    return insert_equal_noresize(obj);
  }

  inline vcl_pair<iterator, bool> insert_unique_noresize(const value_type& obj);
  inline iterator insert_equal_noresize(const value_type& obj);

  void insert_unique(const value_type* f, const value_type* l)
  {
    size_type n = l - f;
    resize(num_elements + n);
    for (; n > 0; --n)
      insert_unique_noresize(*f++);
  }

  void insert_equal(const value_type* f, const value_type* l)
  {
    size_type n = l - f;
    resize(num_elements + n);
    for (; n > 0; --n)
      insert_equal_noresize(*f++);
  }

#if defined(VCL_WIN32)
  static void vcl_distance(const_iterator f, const_iterator l, size_type& n) {
    while (f != l) { ++f; ++n; }
  }
#endif


  void insert_unique(const_iterator f, const_iterator l)
  {
    size_type n = 0;
    vcl_distance(f, l, n);
    resize(num_elements + n);
    for (; n > 0; --n)
      insert_unique_noresize(*f++);
  }

  void insert_equal(const_iterator f, const_iterator l)
  {
    size_type n = 0;
    vcl_distance(f, l, n);
    resize(num_elements + n);
    for (; n > 0; --n)
      insert_equal_noresize(*f++);
  }

  inline reference find_or_insert(const value_type& obj);

  iterator find(const key_type& key)
  {
    size_type n = bkt_num_key(key);
    node* first;
    for ( first = buckets[n];
          first && !equals(get_key(first->val), key);
          first = first->next)
      {}
    return iterator(first, this);
  }

  const_iterator find(const key_type& key) const
  {
    size_type n = bkt_num_key(key);
    const node* first;
    for ( first = buckets[n];
          first && !equals(get_key(first->val), key);
          first = first->next)
      {}
    return const_iterator(first, this);
  }

  size_type count(const key_type& key) const
  {
    const size_type n = bkt_num_key(key);
    size_type result = 0;

    for (const node* cur = buckets[n]; cur; cur = cur->next)
      if (equals(get_key(cur->val), key))
        ++result;
    return result;
  }

  inline vcl_pair<iterator, iterator> equal_range(const key_type& key);
  inline vcl_pair<const_iterator, const_iterator> equal_range(const key_type& key) const;

  inline size_type erase(const key_type& key);
  inline void erase(const iterator& it);
  inline void erase(iterator first, iterator last);

  inline void erase(const const_iterator& it);
  inline void erase(const_iterator first, const_iterator last);

  inline void resize(size_type num_elements_hint);
  void clear() { super::clear(); VCL_debug_do(invalidate_all()); }
 private:
  size_type next_size(size_type n) const { return VCL_next_prime(n); }

  void initialize_buckets(size_type n)
  {
    const size_type n_buckets = next_size(n);
    buckets.reserve(n_buckets);
    buckets.insert(buckets.end(), n_buckets, (node*) 0);
    num_elements = 0;
  }
  size_type bkt_num_key(const key_type& key) const{ return bkt_num_key(key, buckets.size()); }

  size_type bkt_num(const value_type& obj) const { return bkt_num_key(get_key(obj)); }

  size_type bkt_num_key(const key_type& key, vcl_size_t n) const { return hashfun(key) % n; }

  size_type bkt_num(const value_type& obj, vcl_size_t n) const { return bkt_num_key(get_key(obj), n); }
  inline void erase_bucket(const size_type n, node* first, node* last);
  inline void erase_bucket(const size_type n, node* last);
};

// fbp: these defines are for outline methods definitions.
// needed to definitions to be portable. Should not be used in method bodies.

# if defined ( __STL_NESTED_TYPE_PARAM_BUG )
#  define __difference_type__ vcl_ptrdiff_t
#  define __size_type__       vcl_size_t
#  define __value_type__      Value
#  define __key_type__        Key
#  define __node__            vcl_hashtable_node<Value>
#  define __reference__       Value&
# else
#  define __difference_type__  vcl_hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::difference_type
#  define __size_type__        vcl_hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::size_type
#  define __value_type__       vcl_hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::value_type
#  define __key_type__         vcl_hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::key_type
#  define __node__             vcl_hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::node
#  define __reference__        vcl_hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::reference
# endif

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
inline vcl_hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&
vcl_hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++()
{
  const node* old = cur;
  VCL_verbose_assert(old!=0,__STL_MSG_INVALID_ADVANCE);
  cur = cur->next;
  if (!cur) {
    size_type bucket = ht->bkt_num(old->val);
    while (!cur && ++bucket < ht->buckets.size())
      cur = ht->buckets[bucket];
  }
  return *this;
}

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
inline vcl_hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
vcl_hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++(int)
{
  iterator tmp = *this;
  ++*this;
  return tmp;
}

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
inline vcl_hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&
vcl_hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++()
{
  const node* old = cur;
  VCL_verbose_assert(old!=0,__STL_MSG_INVALID_ADVANCE);
  cur = cur->next;
  if (!cur) {
    size_type bucket = ht->bkt_num(old->val);
    while (!cur && ++bucket < ht->buckets.size())
      cur = ht->buckets[bucket];
  }
  return *this;
}

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
inline vcl_hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
vcl_hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++(int)
{
  const_iterator tmp = *this;
  ++*this;
  return tmp;
}

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
inline vcl_forward_iterator_tag
iterator_category (const vcl_hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
{
  return vcl_forward_iterator_tag();
}

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
inline Value*
value_type(const vcl_hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
{
  return (Value*) 0;
}

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
inline vcl_ptrdiff_t*
distance_type(const vcl_hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
{
  return (vcl_ptrdiff_t*) 0;
}

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
inline vcl_forward_iterator_tag
iterator_category (const vcl_hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
{
  return vcl_forward_iterator_tag();
}

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
inline Value*
value_type(const vcl_hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
{
  return (Value*) 0;
}

template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>