首页 > 代码库 > 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
- SGI STL的hash_set是以hashtable为底层机制的,几乎所有的hash_set操作行为,都只是调用hashtable的操作行为而已;
- 因为RB-tree有自动排序功能而hashtable没有,所以set的元素有自动排序功能而hash_set没有;
- hash_set的使用方式,与set完全相同。
5.9 hash_map
- SGI STL的hash_map是以hashtable为底层机制的,几乎所有的hash_map操作行为,都只是调用hashtable的操作行为而已;
- 因为RB-tree有自动排序功能而hashtable没有,所以map的元素有自动排序功能而hash_map没有;
- 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 关联式容器(下)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。