【C++】unordered系列容器使用及封装
目录
一、unordered_map和unordered_set的使用
1.1 unordered_set和unordered_multiset参考文档
1.5 unordered_multimap/unordered_multiset
二、用哈希表封装myunordered_map和myunordered_set
2. 模拟实现unordered_map和unordered_set
2.4 bit::unordered_map和bit::unordered_set代码实现
一、unordered_map和unordered_set的使用
1. unordered_set系列的使用
1.1 unordered_set和unordered_multiset参考文档
<unordered_set> - C++ Reference
1.2 unordered_set类的介绍
• unordered_set的声明如下，Key就是unordered_set底层关键字的类型
• unordered_set默认要求Key支持转换为整形，如果不支持或者想按自己的需求走可以自行实现支持将Key转成整形的仿函数传给第二个模板参数
• unordered_set默认要求Key支持比较相等，如果不支持或者想按自己的需求走可以自行实现支持将Key比较相等的仿函数传给第三个模板参数
• unordered_set底层是用哈希桶实现，增删查平均效率是 O(1),迭代器遍历无序。
因为unordered系列容器底层是通过哈希桶实现，因为要支持哈希函数、以及处理哈希冲突的方式，所以Key要支持转换成整形并且要求支持比较相等，并且针对不能转换成整形的类型，支持通过传入仿函数进行转换。
• unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第四个参数，一般情况下，我们都不需要传后三个模板参数。
其实一开始STL库先提供了map/set容器（红黑树封装实现），不过后来鉴于哈希桶实现的map和set确实有自身优势，STL就又提供相关哈希桶实现容器，不过因为map、set的命名已经确定了，如果以hashmap/hashset新容器命名，无法很好凸显不同容器的特点。因为红黑树实现的map、set迭代器遍历有序，哈希表实现的遍历不再有序，所以STL中取名为unordered_set/unordered_map。
前面部分我们已经学习了set容器的使用，set和unordered_set的功能高度相似，只是底层结构不同，有一些性能和使用的差异，这里我们只讲他们的差异部分。
template < class Key, // unordered_set::key_type / value_type class Hash = hash<Key>, // unordered_set::hasher class Pred = equal_to<Key>, // unordered_set::key_equal class Alloc = allocator<Key> // unordered_set::allocator_type > class unordered_set;1.3 unordered_set和set的使用差异
• 查看文档我们会发现unordered_set的支持增删查且跟set的使用一模一样，关于使用我们这里就不再赘述和演示了。
• unordered_set和set的第一个差异是对key的要求不同，set要求Key支持小于比较，而
unordered_set要求Key支持转成整形且支持等于比较，要理解unordered_set的这个两点要求要我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。
• unordered_set和set的第二个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set是单向迭代器，其次set底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以set迭代器遍历是有序+去重。而unordered_set底层是哈希表，迭代器遍历是无序+去重。
• unordered_set和set的第三个差异是性能的差异，整体而言大多数场景下，unordered_set的增删查改更快一些，因为红黑树增删查改效率是，而哈希表增删查平均效率是O(1) ，具体可以参看下面代码的演示的对比差异。
pair<iterator, bool> insert(const value_type& val); size_type erase(const key_type& k); iterator find(const key_type& k); #include<unordered_set> #include<unordered_map> #include<set> #include<iostream> using namespace std; int test_set2() { const size_t N = 1000000; unordered_set<int> us; set<int> s; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; ++i) { //v.push_back(rand()); // N比较大时，重复值比较多 v.push_back(rand() + i); // 重复值相对少 //v.push_back(i); // 没有重复，有序 } // 21:15 size_t begin1 = clock(); for (auto e : v) { s.insert(e); } size_t end1 = clock(); cout << "set insert:" << end1 - begin1 << endl; size_t begin2 = clock(); us.reserve(N); for (auto e : v) { us.insert(e); } size_t end2 = clock(); cout << "unordered_set insert:" << end2 - begin2 << endl; int m1 = 0; size_t begin3 = clock(); for (auto e : v) { auto ret = s.find(e); if (ret != s.end()) { ++m1; } } size_t end3 = clock(); cout << "set find:" << end3 - begin3 << "->" << m1 << endl; int m2 = 0; size_t begin4 = clock(); for (auto e : v) { auto ret = us.find(e); if (ret != us.end()) { ++m2; } } size_t end4 = clock(); cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl; cout << "插入数据个数：" << s.size() << endl; cout << "插入数据个数：" << us.size() << endl << endl; size_t begin5 = clock(); for (auto e : v) { s.erase(e); } size_t end5 = clock(); cout << "set erase:" << end5 - begin5 << endl; size_t begin6 = clock(); for (auto e : v) { us.erase(e); } size_t end6 = clock(); cout << "unordered_set erase:" << end6 - begin6 << endl << endl; return 0; } int main() { test_set2(); return 0; }1.4 unordered_map和map的使用差异
• 查看文档我们会发现unordered_map的支持增删查改且跟map的使用一模一样，关于使用我们这里就不再赘述和演示了。
• unordered_map和map的第一个差异是对key的要求不同，map要求Key支持小于比较，而unordered_map要求Key支持转成整形且支持等于比较，要理解unordered_map的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。
• unordered_map和map的第二个差异是迭代器的差异，map的iterator是双向迭代器，
unordered_map是单向迭代器，其次map底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以map迭代器遍历是Key有序+去重。而unordered_map底层是哈希表，迭代器遍历是Key无序+去重。
• unordered_map和map的第三个差异是性能的差异，整体而言大多数场景下，unordered_map的增删查改更快一些，因为红黑树增删查改效率是O(logN) ，而哈希表增删查平均效率是 O(1)，具体可以参看下面代码的演示的对比差异。
pair<iterator, bool> insert(const value_type& val); size_type erase(const key_type& k); iterator find(const key_type& k); mapped_type& operator[] (const key_type& k);1.5 unordered_multimap/unordered_multiset
• unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似，支持Key冗余。
• unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个方面的差异，
key的要求的差异，iterator及遍历顺序的差异，性能的差异。
1.6 unordered_xxx的哈希相关接口
Buckets和Hash policy系列的接口分别是跟哈希桶和负载因子相关的接口，日常使用的角度我们不需要太关注。
| Buckets | 接口说明 |
|---|---|
| bucket_count | 返回容器中的桶数量 |
| max_bucket_count | 返回容器可以拥有的最大桶数 |
| bucket_size | 返回桶 n 中的元素数量 |
| bucket | 返回元素值 k 所在的桶号 |
| Hash policy | 接口说明 |
|---|---|
| load_factor | 返回容器中的当前负载因子 |
| max_load_factor | 获取或设置最大负载因子 |
| rehash | 将容器中的桶数量设置为 n 或更多，如果 n 大于容器中当前的桶数量（bucket_count），则会强制执行重新散列。新的桶数量可以等于或大于 n；如果 n 小于容器中当前的桶数量（bucket_count），该函数可能对桶数量没有影响，也可能不会强制执行重新散列，这取决于底层实现。rehash是哈希表的重建：容器中的所有元素将根据其哈希值重新排列到新的桶集中。这可能改变容器内元素的迭代顺序，当容器的负载因子即将超过其最大负载因子时，容器会自动执行rehash，请注意，此函数需要桶的数量作为参数。存在一个类似的函数 unordered_set::reserve，它需要容器中元素的数量作为参数。 |
| reserve | 将容器中的桶数量（bucket_count）设置为最适合至少包含 n 个元素的数量，如果 n 大于当前 bucket_count 乘以 max_load_factor，则容器中的 bucket_count 会增加，并强制进行重新哈希，如果 n 小于这个值，该函数可能没有任何效果(这取决于底层实现)。 |
二、用哈希表封装myunordered_map和myunordered_set
1. 源码及框架分析
SGI-STL30版本源代码中没有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL版本，这两个容器是C++11之后才更新的。但是SGI-STL30实现了哈希表，只容器的名字是hash_map和hash_set，他是作为非标准的容器出现的，非标准是指非C++标准规定必须实现的，源代码在hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h中hash_map和hash_set的实现结构框架核心部分截取出来如下：
// stl_hash_set template <class Value, class HashFcn = hash<Value>, class EqualKey = equal_to<Value>, class Alloc = alloc> class hash_set { private: typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht; ht rep; public: typedef typename ht::key_type key_type; typedef typename ht::value_type value_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::const_iterator iterator; typedef typename ht::const_iterator const_iterator; hasher hash_funct() const { return rep.hash_funct(); } key_equal key_eq() const { return rep.key_eq(); } }; // stl_hash_map template <class Key, class T, class HashFcn = hash<Key>, class EqualKey = equal_to<Key>, class Alloc = alloc> class hash_map { private: typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T> >, EqualKey, Alloc> ht; ht rep; public: typedef typename ht::key_type key_type; typedef T data_type; typedef T mapped_type; typedef typename ht::value_type value_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::iterator iterator; typedef typename ht::const_iterator const_iterator; }; // stl_hashtable.h template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> class hashtable { public: typedef Key key_type; typedef Value value_type; typedef HashFcn hasher; typedef EqualKey key_equal; private: hasher hash; key_equal equals; ExtractKey get_key; typedef __hashtable_node<Value> node; vector<node*, Alloc> buckets; size_type num_elements; public: typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator; pair<iterator, bool> insert_unique(const value_type& obj); const_iterator find(const key_type& key) const; }; template <class Value> struct __hashtable_node { __hashtable_node* next; Value val; };• 这里我们就不再画图分析了，通过源码可以看到，结构上hash_map和hash_set跟map和set的完全类似，复用同一个hashtable实现key和key/value结构，hash_set传给hash_table的是两个key，hash_map传给hash_table的是pair<const key, value>
• 需要注意的是源码里面跟map/set源码类似，命名风格比较乱。下面我们模拟一份自己的出来，就按自己的风格走了。
2. 模拟实现unordered_map和unordered_set
2.1 实现出复用哈希表的框架，并支持insert
• 参考源码框架，unordered_map和unordered_set复用之前我们实现的哈希表。
• 我们这里相比源码调整一下，key参数就用K，value参数就用V，哈希表中的数据类型，我们使用T。
• 其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂一点，但是大框架和思路是完全类似的。因为HashTable实现泛型时从内部无法知道模版参数T是K，还是pair<K, V>，并且insert内部进行插入时要用K对象转换成整形取模和K比较相等，因为pair的value不参与计算取模，且默认支持的是key和value一起比较相等，我们任何时候只需要比较K对象，所以我们在unordered_map和unordered_set层分别实现一个MapKeyOfT和SetKeyOfT的仿函数传给HashTable的KeyOfT，然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象，再转换成整形取模和K比较相等，具体细节参考如下代码实现。
// MyUnorderedSet.h namespace zlr { template<class K, class Hash = HashFunc<K>> class unordered_set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: bool insert(const K& key) { return _ht.Insert(key); } private: hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht; }; } // MyUnorderedMap.h namespace zlr { template<class K, class V, class Hash = HashFunc<K>> class unordered_map { struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: bool insert(const pair<K, V>& kv) { return _ht.Insert(kv); } private: hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht; }; } // HashTable.h template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; namespace hash_bucket { template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) { } }; // 实现步骤： // 1、实现哈希表 // 2、封装unordered_map和unordered_set的框架 解决KeyOfT // 3、iterator // 4、const_iterator // 5、key不支持修改的问题 // 6、operator[] template<class K, class T, class KeyOfT, class Hash> class HashTable { typedef HashNode<T> Node; inline unsigned long __stl_next_prime(unsigned long n) { static const int __stl_num_primes = 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, 3221225473, 4294967291 }; const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } public: HashTable() { _tables.resize(__stl_next_prime(_tables.size()), nullptr); } ~HashTable() { // 依次把每个桶释放 for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } } bool Insert(const T& data) { KeyOfT kot; if (Find(kot(data))) return false; Hash hs; size_t hashi = hs(kot(data)) % _tables.size(); // 负载因子==1扩容 if (_n == _tables.size()) { vector<Node*> newtables(__stl_next_prime(_tables.size()), nullptr); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // 旧表中结点，挪动新表重新映射的位置 size_t hashi = hs(kot(cur->_data)) % newtables.size(); // 头插到新表 cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtables); } // 头插 Node* newnode = new Node(data); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return true; } private: vector<Node*> _tables; // 指针数组 size_t _n = 0; // 表中存储数据个数 }; }2.2 支持iterator的实现
iterator核心源代码
template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> struct __hashtable_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; node* cur; hashtable* ht; __hashtable_iterator(node* n, hashtable* tab) : cur(n), ht(tab) {} __hashtable_iterator() {} reference operator*() const { return cur->val; } #ifndef __SGI_STL_NO_ARROW_OPERATOR pointer operator->() const { return &(operator*()); } #endif /* __SGI_STL_NO_ARROW_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 V, 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 (!cur) { size_type bucket = ht->bkt_num(old->val); while (!cur && ++bucket < ht->buckets.size()) cur = ht->buckets[bucket]; } return *this; }iterator实现思路分析
• iterator实现的大框架跟list的iterator思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为，要注意的是哈希表的迭代器是单向迭代器。
• 这里的难点是operator++的实现。iterator中有一个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下一个结点即可。如果当前桶走完了，则需要想办法计算找到下一个桶。这里的难点是反而是结构设计的问题，参考上面的源码，我们可以看到iterator中除了有结点的指针，还有哈希表对象的指针，这样当前桶走完了，要计算下一个桶就相对容易多了，用key值计算出当前桶位置，依次往后找下一个不为空的桶即可。
• begin()返回第一个桶中第一个节点指针构造的迭代器，我们需要遍历找到第一个节点然后返回，这里我们可以判断下如果哈希表内没有节点直接结束。这里end()返回迭代器可以用空表示。
• unordered_set的iterator也不支持修改，因此这里我们就参考前面set/map的设计，我们把unordered_set的第二个模板参数改成const K即可， HashTable<K, const K, SetKeyOfT, Hash> _ht;
• unordered_map的iterator不支持修改key但是可以修改value，我们把unordered_map的第二个模板参数pair的第一个参数改成const K即可， HashTable<K, pair<const K, V>,
MapKeyOfT, Hash> _ht;
在封装迭代器时，与前文map/set中不同，这里因为operator++()遍历，我们需要根据哈希表的数组、哈希函数确定桶的位置，而后面封装的哈希表接口又会返回迭代器，所以这里实际上相互包含，我们需要在迭代器上方声明一下哈希表。
// HashTable.h template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; // 特化 template<> struct HashFunc<string> { size_t operator()(const string& key) { size_t hash = 0; for (auto e : key) { hash *= 131; hash += e; } return hash; } }; //封装的哈希桶 namespace hash_bucket { template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) { } }; // 因为哈希表、迭代器实现内部相互包含，这里需要添加前置声明 template<class K, class T, class KeyOfT, class Hash> class HashTable; template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash> struct HTIterator { typedef HashNode<T> Node; typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self; Node* _node; const HashTable<K, T, KeyOfT, Hash>* _pht; HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht) :_node(node) , _pht(pht) { } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& s) { return _node != s._node; } Self& operator++() { if (_node->_next) { // 当前桶还有节点 _node = _node->_next; } else { // 当前桶走完了，找下一个不为空的桶 KeyOfT kot; Hash hs; //取出key,并转换成整形 size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size(); ++hashi; while (hashi < _pht->_tables.size()) { if (_pht->_tables[hashi]) { break; } ++hashi; } if (hashi == _pht->_tables.size()) { _node = nullptr; // end() } else { _node = _pht->_tables[hashi]; } } return *this; } }; //封装实现的哈希表内部功能 template<class K, class T, class KeyOfT, class Hash> class HashTable { // 友元声明 template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash> friend struct HTIterator; typedef HashNode<T> Node; public: typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator; typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator; Iterator Begin() { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) { return Iterator(cur, this); } } return End(); } Iterator End() { return Iterator(nullptr, this); } ConstIterator Begin() const { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) { return ConstIterator(cur, this); } } return End(); } ConstIterator End() const { return ConstIterator(nullptr, this); } inline unsigned long __stl_next_prime(unsigned long n) { static const int __stl_num_primes = 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, 3221225473, 4294967291 }; const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } HashTable() { _tables.resize(__stl_next_prime(_tables.size()), nullptr); } ~HashTable() { // 依次把每个桶释放 for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } } pair<Iterator, bool> Insert(const T& data) { KeyOfT kot; Iterator it = Find(kot(data)); if (it != End()) return make_pair(it, false); Hash hs; size_t hashi = hs(kot(data)) % _tables.size(); // 负载因子==1扩容 if (_n == _tables.size()) { vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // 旧表中节点，挪动新表重新映射的位置 size_t hashi = hs(kot(cur->_data)) % newtables.size(); // 头插到新表 cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtables); } // 头插 Node* newnode = new Node(data); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return make_pair(Iterator(newnode, this), true); } Iterator Find(const K& key) { KeyOfT kot; Hash hs; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { return Iterator(cur, this); } cur = cur->_next; } return End(); } bool Erase(const K& key) { KeyOfT kot; Hash hs; size_t hashi = hs(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { if (prev == nullptr) { _tables[hashi] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_n; return true; } prev = cur; cur = cur->_next; } return false; } private: vector<Node*> _tables; // 指针数组 size_t _n = 0; // 表中存储数据个数 }; }2.3 map支持[]
• unordered_map要支持[]主要需要修改insert返回值支持，修改HashTable中的insert返回值为
pair<Iterator, bool> Insert(const T& data)。
• 有了insert支持[]实现就很简单了，具体参考下面代码实现
pair<Iterator, bool> Insert(const T& data) { KeyOfT kot; Iterator it = Find(kot(data)); if (it != End()) return make_pair(it, false); Hash hs; size_t hashi = hs(kot(data)) % _tables.size(); // 负载因子==1扩容 if (_n == _tables.size()) { vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // 旧表中节点，挪动新表重新映射的位置 size_t hashi = hs(kot(cur->_data)) % newtables.size(); // 头插到新表 cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtables); } // 头插 Node* newnode = new Node(data); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return make_pair(Iterator(newnode, this), true); }2.4 bit::unordered_map和bit::unordered_set代码实现
有了哈希表及其迭代器的封装后，我们在这基础上再封装一层来实现unordered系列容器
// MyUnorderedSet.h namespace zlr { template<class K, class Hash = HashFunc<K>> class unordered_set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator; typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const_iterator begin() const { return _ht.Begin(); } const_iterator end() const { return _ht.End(); } pair<iterator, bool> insert(const K& key) { return _ht.Insert(key); } iterator Find(const K& key) { return _ht.Find(key); } bool Erase(const K& key) { return _ht.Erase(key); } private: hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht; }; void test_set() { unordered_set<int> s; int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3,3,15 }; for (auto e : a) { s.insert(e); } for (auto e : s) { cout << e << " "; } cout << endl; unordered_set<int>::iterator it = s.begin(); while (it != s.end()) { // 不支持修改 //*it += 1; cout << *it << " "; ++it; } cout << endl; } } // MyUnorderedMap.h namespace zlr { template<class K, class V, class Hash = HashFunc<K>> class unordered_map { struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator; typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator; iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const_iterator begin() const { return _ht.Begin(); } const_iterator end() const { return _ht.End(); } pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); } V& operator[](const K& key) { pair<iterator, bool> ret = _ht.Insert(make_pair(key, V())); return ret.first->second; } iterator Find(const K& key) { return _ht.Find(key); } bool Erase(const K& key) { return _ht.Erase(key); } private: hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht; }; void test_map() { unordered_map<string, string> dict; dict.insert({ "sort", "排序" }); dict.insert({ "left", "左边" }); dict.insert({ "right", "右边" }); dict["left"] = "左边，剩余"; dict["insert"] = "插入"; dict["string"]; unordered_map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { // 不能修改first，可以修改second //it->first += 'x'; it->second += 'x'; cout << it->first << ":" << it->second << endl; ++it; } cout << endl; } } // HashTable.h template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; // 特化 template<> struct HashFunc<string> { size_t operator()(const string& key) { size_t hash = 0; for (auto e : key) { hash *= 131; hash += e; } return hash; } }; namespace hash_bucket { template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) { } }; // 前置声明 template<class K, class T, class KeyOfT, class Hash> class HashTable; template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash> struct HTIterator { typedef HashNode<T> Node; typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self; Node* _node; const HashTable<K, T, KeyOfT, Hash>* _pht; HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht) :_node(node) , _pht(pht) { } Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } bool operator!=(const Self& s) { return _node != s._node; } Self& operator++() { if (_node->_next) { // 当前桶还有节点 _node = _node->_next; } else { // 当前桶走完了，找下一个不为空的桶 KeyOfT kot; Hash hs; size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size(); ++hashi; while (hashi < _pht->_tables.size()) { if (_pht->_tables[hashi]) { break; } ++hashi; } if (hashi == _pht->_tables.size()) { _node = nullptr; // end() } else { _node = _pht->_tables[hashi]; } } return *this; } }; template<class K, class T, class KeyOfT, class Hash> class HashTable { // 友元声明 template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash> friend struct HTIterator; typedef HashNode<T> Node; public: typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator; typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator; Iterator Begin() { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) { return Iterator(cur, this); } } return End(); } Iterator End() { return Iterator(nullptr, this); } ConstIterator Begin() const { if (_n == 0) return End(); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) { return ConstIterator(cur, this); } } return End(); } ConstIterator End() const { return ConstIterator(nullptr, this); } inline unsigned long __stl_next_prime(unsigned long n) { static const int __stl_num_primes = 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, 3221225473, 4294967291 }; const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } HashTable() { _tables.resize(__stl_next_prime(_tables.size()), nullptr); } ~HashTable() { // 依次把每个桶释放 for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } } pair<Iterator, bool> Insert(const T& data) { KeyOfT kot; Iterator it = Find(kot(data)); if (it != End()) return make_pair(it, false); Hash hs; size_t hashi = hs(kot(data)) % _tables.size(); // 负载因子==1扩容 if (_n == _tables.size()) { vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // 旧表中节点，挪动新表重新映射的位置 size_t hashi = hs(kot(cur->_data)) % newtables.size(); // 头插到新表 cur->_next = newtables[hashi]; newtables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtables); } // 头插 Node* newnode = new Node(data); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return make_pair(Iterator(newnode, this), true); } Iterator Find(const K& key) { KeyOfT kot; Hash hs; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { return Iterator(cur, this); } cur = cur->_next; } return End(); } bool Erase(const K& key) { KeyOfT kot; Hash hs; size_t hashi = hs(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { if (prev == nullptr) { _tables[hashi] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_n; return true; } prev = cur; cur = cur->_next; } return false; } private: vector<Node*> _tables; // 指针数组 size_t _n = 0; // 表中存储数据个数 }; } 
