hashtable
-
//下面介绍一下hashtabl迭代器的主要功能函数operator++ template<class Value, class Key, class HashFen, class ExtractKey, class EqualKey, class Alloc> _hashtable_iterator< Value, Key, HashFen, ExtractKey, EqualKey, Alloc>& _hashtable_iterator< Value, Key, HashFen, ExtractKey, EqualKey, Alloc>::operator++(){ const node* lod=cur;//保存当前节点的指针 cur=cur->next;//如果存在,就返回其下一节点的引用,如果不存在,也就是说该节点位于list的尾端,需要跳向下一个bucket if(!cur){ size_type bucket=ht->bket_num(old->val);//获取当前bucket的位置 while(!cur&&++bucket<buckets.size()) cur=ht->buckets[bucket]; //这里实现的就是bucket的跳跃 } return *this; }
-
//hashtable部分源代码 template<class Value, //节点的实值类别 class Key, //节点的键值类别 class HashFcn,//hash funtion的函数类别 class ExtractKey,//从节点中取出键值的方法(函数,仿函数) class EqualKey,//判断键值相等与否的方法(函数,仿函数) class Alloc=alloc> class hashtable { 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; vector<node*, Alloc> buckets; // 保存桶的vector size_type num_elements; public: size_type bucket_count() const { return buckets.size(); } }; template<class Value>//节点类 struct __hashtable_node { __hashtable_node *next; Value val; }; //迭代器类 template<class Value, class Key, class HashFen, class ExtractKey, class EqualKey, class Alloc> struct __hashtable_iterator { node *cur; hashtable *ht; };
-
//hashtable提前准备好28个质数用来设置表格大小(桶的多少),并提供函数查询 static const unsigned long __stl_prime_list[__stl_num_primes] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473ul, 4294967291ul};
-
hashtable无法处理例如string,float,double这些类型的元素,如果需要处理,则需要自己定义hash funtion
-
hash_set,hash_map是以hashtable 为底层机制,所以他们的操作行为,只是调用hashtable的操作行为,他们的插入操作调用的是hashtable的insert_unique()
-
hash_multiset,hash_multimap,同样是以hashtable为底层机制,只不过他们的插入操作采用的是hashtable的insert_equal()
-
c++11中hash_set/hash_map改名为unordered_map/unordered_set
其底层依旧封装了hashtable,用法与set/map一致