c++STL——哈希表封装：实现高效unordered_map与unordered_set

用哈希表封装unordered_map和unordered_set

在前面我们已经学过如何实现哈希表了。这篇文章我们将着重于使用哈希表对unordered_map和unordered_set这两个容器进行封装。

我们已经有了使用红黑树对map和set封装的经验了，所以这一次使用哈希表封装就不会再过多阐述细节。将对重点部分进行讲解。

此外还需要提及一下的是，c++STL库的这两个容器，底层也是使用哈希桶进行实现的。本篇文章也将使用哈希桶进行实现。因为哈希桶能很大程度上解决哈希冲突的问题。提高效率。

改进底层框架

首先我们需要做一件事情，就是改进一下底层哈希表的框架。

之前为了方便理解原理，每个节点中的数据类型我们都设定为pair类。这样子是默认了哈希表支持的是unordered_map。如果还要实现unordered_set还得在写一份类似的。这里面临的问题和红黑树封装map和set是一样的。这肯定是不太好。所以需要改进一下。

所以第一步是先泛化数据类型，我们统一让数据类型的模板参数为T：

template<class T>
struct HashNode {T _data;HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}
};

然后就是对底层的哈希表框架进行改进了。

但是现在就面临着第一个问题，由于现在数据类型又被泛化，在写代码的时候我们也不知道当前传的是什么数据类型，也就是不知道是Key模式还是Key_Value模式。解决方案我们早已见识过，就是多一个模板参数KeyofT，这个模板参数是专门用来提取出传入数据的关键字的。

其实也就是实现哈希表文章中提到的这张图。无论什么数据类型，我们都需要提取出他的关键字Key(可能本身就是)，然后再通过Hash这个仿函数转成整形。

相比于上节课哈希桶的实现的改进，也就是数据类型泛化：

template<class K, class T, class KeyOfT, class Hash>
class HashTable {
public:using Node = HashNode<T>;//质数表inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.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():_table(__stl_next_prime(0), nullptr),_NodeNum(0){}pair<Iterator, bool> Insert(const T& data) {Hash hash;KeyOfT kot;Iterator it = Find(kot(data));if (it._node != nullptr) {return {it, false};}size_t hashNum = hash(kot(data));//负载因子为1的时候就进行扩容if (_NodeNum == Capacity()) {vector<Node*> newtables(__stl_next_prime(Capacity() + 1), nullptr);for (size_t i = 0; i < Capacity(); i++) {Node* cur = _table[i];while (cur) {Node* next = cur->_next;// 旧表中节点，挪动新表重新映射的位置size_t New_hashi = hash(kot(cur->_data)) % newtables.size();// 头插到新表cur->_next = newtables[New_hashi];newtables[New_hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtables);}size_t hashi = hashNum % Capacity();//头插Node* newnode = new Node(data);newnode->_next = _table[hashi];_table[hashi] = newnode;++_NodeNum;return { Iterator(newnode, this), true};}iterator find(const K& key) {return _ht.Find(key);}bool Erase(const K& key) {if (Find(key) == nullptr)return false;Hash hash;KeyOfT kot;size_t hashi = hash(key) % Capacity();Node* prev = nullptr;Node* cur = _table[hashi];while (cur) {if (kot(cur->_data) == key) {//删除操作if (prev == nullptr)//头删_table[hashi] = cur->_next;elseprev->_next = cur->_next;delete cur;--_NodeNum;return true;}prev = cur;cur = cur->_next;}return false;}size_t Capacity() const{return _table.size();}size_t Size() const{return _NodeNum;}private:vector<Node*> _table;size_t _NodeNum = 0;
};

当然，这里的版本是实现了迭代器的。但是并不要紧。对框架的初步改进其实就是改进一下处理数据类型泛化的逻辑。也就是使用仿函数对象kot取出数据中的关键字key而已。这些东西都已经在用红黑树封装的时候就介绍过了。所以这里就不再赘述。

前面也提到过，库里面在实现的时候其实还有一个模板参数Equal。用来支持关键字Key的相等比较的。但是这个我们以理解原理为主，默认所有的数据类型都有支持相等比较。所以这就得保证我们测试的时候传入的数据类型的Key是支持比较的，可能需要自行重载实现。

迭代器实现

这个部分是和红黑树封装最大的不同之处。对于哈希桶的迭代器遍历其实就是从表头的第一个位置的第一个节点开始，按照顺序往下遍历。如果这个桶没了就紧接下一个桶。

我们还是一样的，在哈希表这一层实现好迭代器。上层的容器的迭代器就是调用下层的接口。

当我们打开文档后会发现：unordered_map和unordered_set都是没有反向迭代器的。也就是说，它们的底层哈希表的迭代器是一个单项迭代器。这其实很好理解。我们实现的哈希桶挂的是单链表。单链表总表头走到表尾很简单，顺着指针链接顺序往后走就可以。但是单链表是很难往前走的。在迭代器的分类里，单链表的迭代器是属于单向迭代器。

很多人会说，这个好办，让哈希表底层的vector存储的是一个个的list容器不就好了。这样不就可以做到双向迭代器了吗？可以是可以，但是这样子会把事情复杂化。这样子迭代器就很不好实现了。除此之外，使用list效率也一般。这些就不多说了，感兴趣可以去查查。

况且标准库里面的实现都是用单链表的，所以就跟着标准走了。

实现思路

假设有一个这样的哈希表，怎么样通过迭代器走到下一个节点呢？

我们首先得理解迭代器的本质是什么？我们学过list的实现，实现过红黑树，迭代器其实都是一个指向节点的指针，只不过把它封装到一个类里面去。然后根据结构的不同，对迭代器的一些造作进行特殊的重载。这里也是一样的，迭代器的底层就是指向节点的指针。

然后我们再来看，应该怎么样通过迭代器遍历到下一个节点呢？
如果当前节点的下一个节点不为空，那直接走到紧跟着的下一个节点就好了。
但是如果下一个节点为空呢？那就要换一个桶进行遍历了。但是当前只有一个指向节点的指针，怎么样找到下一个桶呢？桶在哈希表里面。这怎么办呢？

我们来看看库里面是怎么玩的：

库里面在实现迭代器的时候，不仅仅有指向节点的指针，还有一个指向整个哈希表的指针。这就解决了前面那个难题，如何访问哈希表中其它的桶。当下一个节点为空的时候，直接往后找非空桶，如果后续全是空桶，就可以确定到结尾位置了。结尾该怎么处理呢？

还是一样的，让结尾位置的迭代器内部的指针置空就好了。

这个实现方式其实早已接触。早在实现红黑树的迭代器的时候，为了支持迭代器在结尾处还能往前走的逻辑，就需要传入整个树的根节点。要不然没有办法找到整个树对应的最右节点。

迭代器框架

//提前声名一下
template<class K, class T, class KeyOfT, class Hash>
class HashTable;template<class K, class T, class KeyOfT, class Hash, class Ref, class Ptr>
struct HT_Iterator {using Node = HashNode<T>;using Self = HT_Iterator<K, T, KeyOfT, Hash, Ref, Ptr>;Node* _node;const HashTable<K, T, KeyOfT, Hash>* _pht;HT_Iterator(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& self) {return _node == self._node;}bool operator!=(const Self& self) {return !(_node == self._node);}
};

这里也是为了实现两种不同版本的迭代器，需要Ref和Ptr这两个模板参数来区分。因为普通迭代器和const迭代器的本质差别就在解引用的时候。这可以减少多写一份冗余的代码。

由于迭代器内部有一个哈希表指针，哈希表又是一个类模板，所以需要把哈希表的模板参数一起拿过来构成迭代器的模板参数。所以这就是为什么哈希表的迭代器的模板参数有这么多。

眼尖的也会发现，最前面竟然多了点东西，提前声名了哈希表和它的模板参数。这是为何？这是因为迭代器和哈希表这两个类互相包含了。你中有我我中有你的情况。c++的编译器是执行向上巡查的进行编译的。而把迭代器写在哈希表的上面，想上找肯定是找不到哈希表的结构的。所以编译器会不认识，所以需要提前声名一下。把迭代器写在哈希表下面也是不可行的。因为到时候哈希表内会通过迭代器实现接口，写在下面一样是找不到。

注意：
这里指向哈希表的指针加了const修饰，这是必要的。库里面是写了两份代码来区分两种不同版本的迭代器。而且库里面的const迭代器内哈希表指针也是const修饰的。

这里我们先不作解释，埋个伏笔，等到迭代器接口实现的时候再来讲解。

迭代器重载operator++

由于迭代器是单项迭代器，是不支持–操作的，也不支持随机迭代器的+/-操作。所以最重要的操作就是实现出++操作。本部分将重点讲解。

前面说到了，哈希表的迭代器就是对一个个节点进行遍历。如果下一个节点不为空，那就走到下一个。下一个为空，就得通过哈希表去找到下一个不为空的桶。反之返回结束位置。

第一种情况非常好办，第二种怎么操作呢？

这个也简单，把当前节点在哈希表vector的下标找出来就好了。然后往后找。况且迭代器这个类的模板参数中是有哈希表所需要的所有模板参数的。也就是说，迭代器内可以使用取出关键字的KeyOfT仿函数，也可以使用将关键字转整形的Hash仿函数，所以这不是很难的事情。

所以来直接看代码：

Self& operator++() {//下一个节点不为空，直接走到下一个节点if (_node->_next) _node = _node->_next;else {Hash hash; KeyOfT kot;//找到当前哈希表所处位置size_t hashi = hash(kot(_node->_data)) % _pht->_table.size();//因为下一个节点为空，得换一个桶，从当前桶的下一个位置开始查找++hashi;size_t i = 0;for (i = hashi; i < _pht->_table.size(); ++i) {Node* cur = _pht->_table[i];if (cur) break;}//这里必须要经过下面判断逻辑，因为不知道是什么方式退出循环的//如果下一个节点不存在(后续全为空桶)if (i == _pht->_table.size())_node = nullptr;else _node = _pht->_table[i];       }return *this;
}//后置++调用前置的逻辑就可以了
Self operator++(int) {Self s = *this;++(*this);return s;
}

所以哈希表迭代器的operator++操作也不是很难。跟着逻辑走就可以了。

哈希表中获取迭代器位置

这个时候就得在哈希表中来写获取迭代器位置的接口了：

using Iterator = HT_Iterator<K, T, KeyOfT, Hash, T&, T*>;
using ConstIterator = HT_Iterator<K, T, KeyOfT, Hash, const T&, const T*>;

在哈希表内部需要区分一下迭代器的版本，所以需要声名一下。当然这也是为了书写代码的方便。在哈希表内部进行两种迭代器的区分如上。

然后需要编写获取迭代器开始位置的接口：

Iterator Begin() {//找到第一个不为空的桶//如果全是空桶就返回End()if (_NodeNum == 0)return End();size_t i = 0;for (i = 0; i < Capacity(); ++i) {Node* cur = _table[i];if (cur) return Iterator(cur, this);}return End();}Iterator End() {return Iterator(nullptr, this);
}ConstIterator Begin() const {if (_NodeNum == 0)return End();size_t i = 0;for (i = 0; i < Capacity(); ++i) {Node* cur = _table[i];if (_table[i]) return ConstIterator(cur, this);}return End();
}ConstIterator End() const { return ConstIterator(nullptr, this);
}

这个时候来讲解一下为什么，在哈希表迭代器内的哈希表指针需要使用const进行修饰。

首先，获取迭代器接口的时候，会有两个版本，一个是普通迭代器，一个是const迭代器。返回值不一样。但是它们的函数名一样，这会构成重载。但是重载的条件是参数不同。返回值不同是没办法构成重载的。所以为了区分，在实现const迭代器的接口的时候，必须修饰成const成员函数。因为const修饰成员函数本质是将隐式参数this指针从类名 * const this变成const 类名 * const this。限制的是this指向的内容不能被修改。隐式参数也是参数，参数不一样，所以构成重载。所以必须对const迭代器的接口修饰成const成员函数。

其次，正是这个原因，导致必须要让迭代器内部的那个哈希表指针修饰为const HashTable*。因为要传哈希表的指针，就是传this指针。但是如果是const迭代器的接口内，由于this指针被const修饰，如果传给迭代器构造函数里面那个哈希表指针参数不加const修饰，就会引起权限放大的问题。之前说过，权限只可以平移或者缩小，不能放大。所以迭代器类里面的哈希表指针必须加const修饰。就算是普通迭代器也可以用，因为权限可以缩小。

这点是我们以前没有见识过的。因为以往的所有迭代器的实现中，都不需要传入迭代器指向的类。比如list，map，set。都是不需要的。而这里需要传入this指针，那就必然会有这个问题。

有人会提出一个疑问，就是哈希表指针修饰成const的了，也就是指向内容不能改变了。那怎么通过迭代器进行修改呢？这就是对const修饰指针理解错误了：
const放在指针*的左边确实是限制了指向内容不能被修改。但是并不是真的说指向的内容再也不能修改了。而是说不能通过被const修饰的那个指针进行修改，也不能将其权限放大给另一个指针修改。事实上，再另整一个与被const修饰的那个指针无关的指针就可以对数据修改了。举个例子看看就知道了：

还要注意的是，这里我使用接口Capacity()来代替_table.size()。是为了代码能写的清楚一点。我自己每次写_table.size()觉得有点累。这里必须实现成const成员函数(如果只实现一个Capacity()接口的情况下，当然一般实现两个版本的)。原因也是一样的，因为const迭代器接口里面调用了，调用接口是通过this指针调用。而经过const修饰的this指针只能调用到const成员函数。正常的this指针既可以调const成员函数，也可以调非const的成员函数。

这里有个问题：普通迭代器的Begin()接口和const版本的接口有点冗余。写的太重复了，能不能复用一下接口呢？
这里是不可以的。因为this指针的缘故，在const版本的迭代器中调用iterator it = Begin()接口，想通过普通迭代器来找。但是这个代码的本质是const 类名* const this ->Begin()。这个返回值是ConstIterator，it的类型是iterator，我们并没有支持这二者的转换。会报错。

哈希表的默认成员函数

unordered_map和unordered_set是适配器模式，底层适配了一个哈希表。此外再无其他变量和 资源。所以上层的一些成员函数就可以不用自行编写了，只需要调用一下下层的接口。因为本质操作的都是底层的哈希表。

//默认构造
HashTable():_table(__stl_next_prime(0), nullptr),_NodeNum(0)
{}//拷贝构造
//说明一下：这里的深拷贝会导致哈希桶的顺序反过来（但是仍能满足深拷贝的要求）
//如果不是特殊要求要保持原来数据这样子就可以了
//因为这样子效率会高的多
//并且哈希桶每个桶中的节点数量其实不会太多，反过来其实不会影响效率
HashTable(const HashTable<K, T, KeyOfT, Hash>& Htable) {//提前扩容 减少移动数据_table.resize(Htable._table.size());for (size_t i = 0; i < Htable.Capacity(); ++i) {Node* cur = Htable._table[i];while (cur) {Insert(cur->_data);cur = cur->_next;}}
}//赋值重载
//使用现代写法 赋值后也是桶反序(因为调用了拷贝构造)
HashTable<K, T, KeyOfT, Hash>& operator=(HashTable<K, T, KeyOfT, Hash> Htable) {_table.swap(Htable._table);std::swap(_NodeNum, Htable._NodeNum);return *this;
}//析构函数
~HashTable() {for (size_t i = 0; i < Capacity(); ++i) {Node* cur = _table[i];while (cur) {Node* curnext = cur->_next;delete cur;cur = curnext;}}
}

这里的拷贝构造就需要一个个的开节点进行映射了。只不过这里有一个问题，如果按照每个桶从上到下，表从左到右的顺序去深拷贝，会发现一个问题，就是每个桶的顺序倒过来了。这是必然的。自己去画图理解一下就知道了。但是这个不要紧。

因为这样子也算是深拷贝。因为每个桶的节点不多，对查找个别数据的影响并没有多大影响。如果想要保证桶的顺序一致，那么对新表的操作就是尾插。对于单链表而言，尾插效率不高。所以一般不是什么特殊的需求的情况下，这样子做就可以了。

赋值重载也是一样的，调用了拷贝构造(传参部分)。所以也是反序。

析构函数只需要一个个释放节点就好了。对于vector本身，因为它已经自行实现析构函数了。编译器会自行调用的。所以不需要去释放vector。

修改后的哈希表的代码

namespace myspace {template<class T>struct HashNode {T _data;HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}};template<class K>struct HashFunc {size_t operator()(const K& key) {return (size_t)key;}};template<>struct HashFunc<string> {size_t operator()(const string& str) {size_t hash = 0;for (auto ch : str) {hash += ch;hash *= 131;}return hash;}};//提前声名一下template<class K, class T, class KeyOfT, class Hash>class HashTable;//迭代器实现template<class K, class T, class KeyOfT, class Hash, class Ref, class Ptr>struct HT_Iterator {using Node = HashNode<T>;using Self = HT_Iterator<K, T, KeyOfT, Hash, Ref, Ptr>;Node* _node; const HashTable<K, T, KeyOfT, Hash>* _pht;HT_Iterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht):_node(node),_pht(pht){}Self& operator++() {if (_node->_next) _node = _node->_next;else {Hash hash; KeyOfT kot;size_t hashi = hash(kot(_node->_data)) % _pht->_table.size();++hashi;size_t i = 0;for (i = hashi; i < _pht->_table.size(); ++i) {Node* cur = _pht->_table[i];if (cur) break;}//如果下一个节点不存在if (i == _pht->_table.size())_node = nullptr;else _node = _pht->_table[i];       }return *this;}Self operator++(int) {Self s = *this;++(*this);return s;}Ref operator*() {return _node->_data;}Ptr operator->() {return &(_node->_data);}bool operator==(const Self& self) {return _node == self._node;}bool operator!=(const Self& self) {return !(_node == self._node);}};//其实正常来讲还有一个支持key的相等比较的，因为不知道外界传入的key到底支不支持比较//但是这里默认是有的了，没有的话再加入一个仿函数从Equal就可以了template<class K, class T, class KeyOfT, class Hash>class HashTable {public:using Node = HashNode<T>;//友元声名template<class K, class T, class KeyOfT, class Hash, class Ref, class Ptr>friend struct HT_Iterator; //迭代器using Iterator = HT_Iterator<K, T, KeyOfT, Hash, T&, T*>;using ConstIterator = HT_Iterator<K, T, KeyOfT, Hash, const T&, const T*>;Iterator Begin() {//找到第一个不为空的桶//如果全是空桶就返回End()if (_NodeNum == 0)return End();size_t i = 0;for (i = 0; i < Capacity(); ++i) {Node* cur = _table[i];if (cur) return Iterator(cur, this);}return End();}Iterator End() {return Iterator(nullptr, this);}ConstIterator Begin() const {if (_NodeNum == 0)return End();size_t i = 0;for (i = 0; i < Capacity(); ++i) {Node* cur = _table[i];if (_table[i]) return ConstIterator(cur, this);}return End();}ConstIterator End() const { return ConstIterator(nullptr, this);}//质数表inline unsigned long __stl_next_prime(unsigned long n){// Note: assumes long is at least 32 bits.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():_table(__stl_next_prime(0), nullptr),_NodeNum(0){}//拷贝构造//说明一下：这里的深拷贝会导致哈希桶的顺序反过来（但是仍能满足深拷贝的要求）//如果不是特殊要求要保持原来数据这样子就可以了//因为这样子效率会高的多//并且哈希桶每个桶中的节点数量其实不会太多，反过来其实不会影响效率HashTable(const HashTable<K, T, KeyOfT, Hash>& Htable) {//提前扩容 减少移动数据_table.resize(Htable._table.size());for (size_t i = 0; i < Htable.Capacity(); ++i) {Node* cur = Htable._table[i];while (cur) {Insert(cur->_data);cur = cur->_next;}}}//赋值重载//使用现代写法 赋值后也是桶反序(因为调用了拷贝构造)HashTable<K, T, KeyOfT, Hash>& operator=(HashTable<K, T, KeyOfT, Hash> Htable) {_table.swap(Htable._table);std::swap(_NodeNum, Htable._NodeNum);return *this;}//析构函数~HashTable() {for (size_t i = 0; i < Capacity(); ++i) {Node* cur = _table[i];while (cur) {Node* curnext = cur->_next;delete cur;cur = curnext;}}}pair<Iterator, bool> Insert(const T& data) {Hash hash;KeyOfT kot;Iterator it = Find(kot(data));if (it._node != nullptr) {return {it, false};}size_t hashNum = hash(kot(data));//负载因子为1的时候就进行扩容if (_NodeNum == Capacity()) {vector<Node*> newtables(__stl_next_prime(Capacity() + 1), nullptr);for (size_t i = 0; i < Capacity(); i++) {Node* cur = _table[i];while (cur) {Node* next = cur->_next;// 旧表中节点，挪动新表重新映射的位置size_t New_hashi = hash(kot(cur->_data)) %newtables.size();// 头插到新表cur->_next = newtables[New_hashi];newtables[New_hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtables);}size_t hashi = hashNum % Capacity();//头插Node* newnode = new Node(data);newnode->_next = _table[hashi];_table[hashi] = newnode;++_NodeNum;return { Iterator(newnode, this), true};}Iterator Find(const K& key) {Hash hash;KeyOfT kot;size_t hashi = hash(key) % Capacity();Node* cur = _table[hashi];while (cur) {if (kot(cur->_data) == key)return Iterator(cur, this);cur = cur->_next;}return Iterator(nullptr, this);}ConstIterator Find(const K& key) const {Hash hash;KeyOfT kot;size_t hashi = hash(key) % Capacity();Node* cur = _table[hashi];while (cur) {if (kot(cur->_data) == key)return ConstIterator(cur, this);cur = cur->_next;}return ConstIterator(nullptr, this);}bool Erase(const K& key) {if (Find(key) == nullptr)return false;Hash hash;KeyOfT kot;size_t hashi = hash(key) % Capacity();Node* prev = nullptr;Node* cur = _table[hashi];while (cur) {if (kot(cur->_data) == key) {//删除操作if (prev == nullptr)//头删_table[hashi] = cur->_next;elseprev->_next = cur->_next;delete cur;--_NodeNum;return true;}prev = cur;cur = cur->_next;}return false;}size_t Capacity() const{return _table.size();}size_t Size() const{return _NodeNum;}private:vector<Node*> _table;size_t _NodeNum = 0;};}

这里Insert()接口的返回值改成了pair类，这是因为后续要支持unordered_map的operator[]重载。

封装至上层容器

接下来的封装就很简单了，就和红黑树封装map和set一样，就不再多赘述：

封装unordered_map：

namespace myspace {//把Hash转化整形函数的默认值给到上层，这样子上层可以使用默认值 要不然上层也得传template<class K, class V, class Hash = HashFunc<K>>class unordered_map {struct umKeyOfT {const K& operator()(const pair<K, V>& kv) {return kv.first;}};public:using Node = HashNode<pair<const K, V>>;typedef typename HashTable<K, pair<const K, V>, umKeyOfT, Hash>::Iterator iterator;typedef typename HashTable<K, pair<const K, V>, umKeyOfT, Hash>::ConstIterator const_iterator;iterator begin() {return _ht.Begin();}const_iterator begin() const {return _ht.Begin();}iterator end() {return _ht.End();}const_iterator end() const {return _ht.End();}pair<iterator, bool> insert(const pair<K, V>& kv) {return _ht.Insert(kv);}iterator find(const K& key) {return _ht.Find(key);}const_iterator find(const K& key) const {return _ht.Find(key);}V& operator[](const K& key) { pair<iterator, bool> ret = _ht.Insert({ key, V() });iterator it = ret.first; return it->second;  }private:HashTable<K, pair<const K, V>, umKeyOfT, Hash> _ht;};}

这里的unordered_map支持operator[]的方式和map中的是一模一样的。但这知只是表面一样，因为封装导致的。但其实底层的实现差别很大。

封装unordered_set：

namespace myspace {//把Hash转化整形函数的默认值给到上层，这样子上层可以使用默认值 要不然上层也得传template<class K, class Hash = HashFunc<K>>class unordered_set {struct usKeyOfT {const K& operator()(const K& key) {return key;}};public:using Node = HashNode<const K>;typedef  typename HashTable<K, const K, usKeyOfT, Hash>::Iterator iterator;typedef  typename HashTable<K, const K, usKeyOfT, Hash>::ConstIterator const_iterator;iterator begin() {return _ht.Begin();}const_iterator begin() const {return _ht.Begin();}iterator end() {return _ht.End();}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);}const_iterator find(const K& key) const {return _ht.Find(key);}private:HashTable<K, const K, usKeyOfT, Hash> _ht;};}

由此可见封装的好处。我们只需要实现好底层。上层只需要调用对应接口即可操作。