用哈希表封裝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;};}

由此可見封裝的好處。我們只需要實現好底層。上層只需要調用對應接口即可操作。