首页 > 代码库 > Ch5 关联式容器(下)

Ch5 关联式容器(下)

5.7 hushtable

5.7.1 hushtable概述

开链:在每一个表格元素中维护一个list;hash function为我们分配某一个list,然后我们在那个list身上执行元素的插入、搜寻、删除等操作。

5.7.3 hashtable的迭代器

template <class Value, class Key, class HashFcn,    class ExtractKey, class EqualKey, class Alloc>struct __hushtable_iterator{    typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable;    typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;    typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> const_iterator;    typedef __hashtable_node<Value> node;    typedef forward_iterator_tag iterator_category;    typedef Value value_type;    typedef ptrdiff_t difference_type;    typdef size_t size_type;    typedef Value& reference;    typedef Value* pointer;    node* cur;    hashtable* ht;  //保持对容器的连结关系(因为可能需要从bucket跳到bucket)    __hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) { }    __hashtable_iterator() { }    reference operator*() const { return cur->val; }    pointer operator->() const { return &(operator*()); }    iterator& operator++();    iterator operator++(int);    bool operator==(const iterator& it) const { return cur==it.cur; }    bool operator!=(const iterator& it) const { return cur!=it.cur; }};template <class T, class K, class HF, class ExK, class EqK, class A>__hashtable_iterator<V, K , HF,ExK, EqK, A>&__hashtable_iterator<V, K , HF,ExK, EqK, A>::operator++() {    const node* old=cur;    cur=cur->next;  //如果存在,结果就是它;否则进入以下if流程    if(!cur){        //根据元素值,定位出下一个bucket,其起头处就是我们的目的地        size_type bucket=ht->bkt_num(old->val);        while(!cur&& ++bucket<ht->buckets.size())            cut=ht->buckets[bucket];    }    return *this;}template <class T, class K, class HF, class ExK, class EqK, class A>__hashtable_iterator<V, K , HF,ExK, EqK, A>&__hashtable_iterator<V, K , HF,ExK, EqK, A>::operator++(int) {    iterator tmp=*this;    ++*this;    return tmp;}}

 

5.7.4 hashtable的数据结构

hashtable的模板参数:

  • Value:节点的实值型别;
  • Key:节点的键值型别;
  • HashFcn:hash function的函数型别;
  • ExtractKey:从节点中取出键值的方法(函数或仿函数);
  • EqualKey:判断键值相同与否的方法(函数或仿函数);
  • Alloc:空间配置器,缺省使用std::alloc。
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc=alloc>class hushtable;//...template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>class hushtable {public:    typedef HashFcn hasher;    typedef EqualKey key_equal;    typedef size_t size_type;private:    hasher hash;    key_equal equals;    ExtractKey get_key;    typedef __hashtable_node<Value> node;    typedef simple_alloc<node, Alloc> node_allocator;    vector<node*, Alloc> buckets;    size_type num_elements;public:    //bucket的个数即buckets vector的大小    size_type bucket_count() const { return buckets.size(); }...};

 

SGI STL以质数来设计表格大小,并且先将28个质数(逐渐呈现大约两倍的关系)计算好,以备随时访问,同时提供一个函数,用来查询在这28个质数之中,“最接近某数并大于某数”的质数。

(本节源代码过多,余下部分借鉴:http://blog.csdn.net/u012062760/article/details/46400953)

 

5.8 hash_set

  1. SGI STL的hash_set是以hashtable为底层机制的,几乎所有的hash_set操作行为,都只是调用hashtable的操作行为而已;
  2. 因为RB-tree有自动排序功能而hashtable没有,所以set的元素有自动排序功能而hash_set没有;
  3. hash_set的使用方式,与set完全相同。

5.9 hash_map

  1. SGI STL的hash_map是以hashtable为底层机制的,几乎所有的hash_map操作行为,都只是调用hashtable的操作行为而已;
  2. 因为RB-tree有自动排序功能而hashtable没有,所以map的元素有自动排序功能而hash_map没有;
  3. hash_map的使用方式,与map完全相同。

5.10 hash_multiset

hash_multiset的特性及用法和hash_set完全相同,唯一的差别在于它允许键值重复,因此它的插入操作采用的是底层机制hashtable的insert_equal()而非insert_unique()。

5.11 hash_multimap

hash_multimap的特性及用法和hash_map完全相同,唯一的差别在于它允许键值重复,因此它的插入操作采用的是底层机制hashtable的insert_equal()而非insert_unique()。

Ch5 关联式容器(下)