C++进阶知识10 封装unordered_map和unordered_set

1. 模拟实现unordered_map和unordered_set

1.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⽐较相等，具体细节参考如下代码实现。

namespace bit
{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 bit
{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实现思路分析
• iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算符实现，迭代器像指针⼀样访问的⾏为，要注意的是哈希表的迭代器是单向迭代器。
• 这⾥的难点是operator++的实现。iterator中有⼀个指向结点的指针，如果当前桶下⾯还有结点，则结点的指针指向下⼀个结点即可。如果当前桶⾛完了，则需要想办法计算找到下⼀个桶。如果迭代器只封装了结点的指针，遍历为当前结点的位置所有指针就无法跳转去下一个桶因此iterator中除了有结点的指针，还有哈希表对象的指针，这样当前桶⾛完了，要计算下⼀个桶就相对容易多了，⽤key值计算出当前桶位置，依次往后找下⼀个不为空的桶即可。
• begin()返回第⼀个桶中第⼀个节点指针构造的迭代器，这⾥end()返回迭代器可以⽤空表⽰。
• unordered_set的iterator也不⽀持修改，我们把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;

2.3 map⽀持[
• unordered_map要⽀持[]主要需要修改insert返回值⽀持，修改HashTable中的insert返回值为pair<Iterator, bool> Insert(const T& data)
• 有了insert⽀持[]实现就很简单了，具体参考下⾯代码实现
bit::unordered_map和bit::unordered_set代码实现

namespace bit
{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;};
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()), 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; // 表中存储数据个数 };
}