目錄

前言

源碼怎么說

為什么要兼容？

兼容的具體做法？

為什么要把Key轉(zhuǎn)為整數(shù)（HashFcn）？

模擬實現(xiàn)

一、建立框架

二、迭代器

++運算符重載

?迭代器兼容大法

三、[ ]重載

四、實現(xiàn)不能修改key

實現(xiàn)及測試代碼

HashTable.h

unordered_set.h

unordered_map.h

test.cpp

---

前言

本篇博客我會利用上一篇博客以鏈地址法實現(xiàn)的哈希表對unordered_map和unordered_set進行封裝，大家如果想了解鏈地址法實現(xiàn)哈希表可以移步我的上一篇博客~

C++進階——哈希思想及實現(xiàn)-CSDN博客

源碼怎么說

我們之前用紅黑樹封裝map和set的時候，就用到了兼容的思想，思路就是紅黑樹存儲的結(jié)點由key、value轉(zhuǎn)變成key、pair<key, value>，然后這兩個統(tǒng)一以一個模板參數(shù)T(data)代替，set就是直接用key即可，map就是使用KeyOfT仿函數(shù)把key提取出來。

我們用哈希表封裝unordered_map和unordered_set，原理同樣如此。

大家和我一起來分析源碼，用到的源碼是SGI-STL30版本。

由于這個版本在C++11之前，也就是還沒有unordered_map和unordered_set，所以里面的命名為hash_map和hash_set,大家明白是什么就好。

一些可能會出現(xiàn)的困惑：

為什么要兼容？

對于unordered_map和unordered_set，底層都是哈希表，如果要為他們都單獨設計出一個哈希表出來，那么這兩個哈希表的結(jié)構(gòu)除了結(jié)點存儲的數(shù)據(jù)不同，其它的邏輯基本上都一樣，這樣就會出現(xiàn)很多的代碼冗余問題，如果我們想辦法設計出一個哈希表，可以讓unordered_map和unordered_set底層都調(diào)用它，就很好的解決了這個問題。

畢竟對于寫源碼的那些大佬而言，大量的重復代碼不夠優(yōu)雅~

兼容的具體做法？

前面我們說到，unordered_map和unordered_set需要用到的哈希表的核心不同就是存儲的數(shù)據(jù)類型不同，那么我們只要讓這個哈希表能存儲這兩種數(shù)據(jù)不就行了。具體怎么做，那當然是用模板，把桶結(jié)點的模板類型寫成T（T實例化出data）即可。

當unordered_set需要使用時，T就是key

當unordered_map需要使用時，T就是pair<K, V>

這樣產(chǎn)生出來的問題就是我們在插入桶結(jié)點時，傳入T不能直接拿到key的值了，而我們的unordered_map和unordered_set既然使用的是同一個哈希表模板，當然也不能去T.first去取key，不然unordered_set肯定會出錯。

所以我們就需要設計出兩個仿函數(shù)（各一個），這個仿函數(shù)由unordered_map和unordered_set傳入哈希表，如果T是key，就返回key，如果T是pair<K, V>，就把其中的key提取并返回。

為什么要把Key轉(zhuǎn)為整數(shù)（HashFcn）？

因為對于unordered_map和unordered_set而言，他們的key值最終都要轉(zhuǎn)換為整數(shù)取映射到哈希表中然后存儲（除法散列法），而他們的key值可能是非整形如一些自定義類型，這些編譯器不能幫我們轉(zhuǎn)變成整形的，我們就需要手動寫一個仿函數(shù)來將其轉(zhuǎn)變?yōu)檎巍?/p>

這樣將這個仿函數(shù)傳入到哈希表里面，哈希表就能處理key值并根據(jù)其自身的size進行相應的映射了。

提示：SGI-STL30版本的默認仿函數(shù)只能處理常見的char、int、long等整形類別（char就返回ascll值，其它返回原值）以及string，其余的類型如果我們想用作為key都需要自己造一個仿函數(shù)

模擬實現(xiàn)

一、建立框架

以下的代碼都是基于我上述對于源碼的分析及之前的實現(xiàn)而來，只是命名風格可能有略微變化

#pragma once
#include <iostream>
#include <vector>
#include <string>
using namespace std;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
};inline unsigned long __stl_next_prime(unsigned long n)
{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;
}template<class K>
struct KeyToInt
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct KeyToInt<string>
{size_t operator()(const string& key){size_t ret = 0;for (auto& e : key){ret += e;ret *= 131;}return ret;}
};// 鏈地址法-哈希表-兼容版
namespace MyHashMS
{// 哈希表的桶結(jié)點//          pair或keytemplate<class T>struct HashNode{HashNode(const T& data):_data(data),_next(nullptr){}T _data;HashNode* _next;};// 編譯器為了提升效率，查找只會向上，迭代器要用到HashTable，故需要前置聲明template<class K, class T, class KeyToInt, class KeyOfT>class HashTable;// 迭代器template<class K, class T, class Ref, class Ptr, class KeyToInt, class KeyOfT >struct HashTable_Iterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyToInt, KeyOfT> HashTable;typedef HashTable_Iterator<K, T, Ref, Ptr, KeyToInt, KeyOfT> Self;HashTable_Iterator(Node* cur, const HashTable* ht):_cur(cur),_ht(ht){}// 迭代器存儲當前結(jié)點指針和其對應的哈希表指針（其實_hashtable也可以）Node* _cur;const HashTable* _ht;// 前置++Self& operator++()Ref operator*()Ptr operator->()bool operator==(const Self& other)bool operator!=(const Self& other)};//        key    pair或key    KeyToInt由上層傳，這樣修改轉(zhuǎn)整數(shù)的邏輯比較方便//                                KeyOfT也是從上層傳，set傳直接返回key的，map傳pair<>.first的template<class K, class T, class KeyToInt, class KeyOfT>class HashTable{// 結(jié)構(gòu)體的友元聲明需要帶著模板參數(shù)// 這里友元聲明是因為HashTable_Iterator里需要用HashTable的指針去訪問其私有成員template<class K, class T, class Ref, class Ptr, class KeyToInt, class KeyOfT >friend struct HashTable_Iterator;typedef HashNode<T> Node;public:typedef HashTable_Iterator<K, T, T&, T*, KeyToInt, KeyOfT> iterator;typedef HashTable_Iterator<K, T, const T&, const T*, KeyToInt, KeyOfT> const_iterator;public:HashTable():_hashtable(__stl_next_prime(0)),_n(0){}iterator begin()iterator end()const_iterator begin() const const_iterator end() const// 清除數(shù)據(jù)，釋放結(jié)點，便于析構(gòu)和賦值運算符重載復用void clear()// 有new申請的結(jié)點，這些結(jié)點是自定義類型，需要手動寫析構(gòu)函數(shù)~HashTable(){clear();}// 拷貝構(gòu)造HashTable(const HashTable& other)// 賦值運算符重載HashTable& operator=(const HashTable& other)pair<iterator, bool> Insert(const T& data)iterator Find(const K& key)bool Erase(const K& key)private:vector<Node*> _hashtable;size_t _n;};
}

// unordered_set.h#pragma once
#include "HashTable.h"namespace MyHashMS
{template<class K, class KeyToInt = KeyToInt<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};typedef HashTable<K, K, KeyToInt, SetKeyOfT> HashTable;typedef typename HashTable::iterator iterator;typedef typename HashTable::const_iterator const_iterator;public: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)iterator find(const K& key)bool erase(const K& key)void print()private:// 關于KeyToInt和SetKeyOfT要不要傳模板類型的問題// 模板參數(shù)是要傳類型的，而前兩者K，K都是類型，顯然沒問題// KeyToInt是unordered_set模板參數(shù)里定義好的類型，也沒問題// SetKeyOfT是在unordered_set類里面定義的一個結(jié)構(gòu)體，也可以直接作為類型HashTable _ht;// 當實例化 unordered_set<int> 時，K 就會被推導為 int，然后 SetKeyOfT 就會根據(jù) K（即 int）來創(chuàng)建一個實例};}

// unordered_map.h#pragma once#include "HashTable.h"namespace MyHashMS{template<class K, class V, class KeyToInt = KeyToInt<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};typedef HashTable<K, pair<K, V>, KeyToInt, MapKeyOfT> HashTable;typedef typename HashTable::iterator iterator;typedef typename HashTable::const_iterator const_iterator;public:iterator begin() { return _ht.begin(); }iterator end() { return _ht.end(); }const_iterator begin() const { return _ht.begin(); }const_iterator end() const { return _ht.end(); }V& operator[](const K& key)pair<iterator, bool> insert(const pair<K, V>& kv)iterator find(const K& key)bool erase(const K& key)void print()private:HashTable _ht;};}

二、迭代器

我們要實現(xiàn)迭代器，只需要給哈希表實現(xiàn)迭代器，然后外面套一層殼就可以實現(xiàn)unordered_map和unordered_set的迭代器啦~

我們要實現(xiàn)的迭代器為單向迭代器，因為之前的一個哈希桶的結(jié)點是由單向鏈表串起來的。

我們實現(xiàn)哈希表的迭代器，就需要一個指向哈希表桶結(jié)點的指針和指向哈希表的指針，這樣才能進行遍歷操作

++運算符重載

我們要實現(xiàn)單向迭代器，核心工程就是實現(xiàn)++運算符的重載。

如果讓我們?nèi)崿F(xiàn)該單向迭代器的++運算符重載，大部分人的第一反應就是，從第一個桶開始作為begin，遍歷該桶的所有結(jié)點，然后再去找下一個桶，到最后一個桶遍歷結(jié)束的下一個結(jié)點為end（nullptr）。

實際上庫里面也是這么做的：

// 前置++
Self& operator++()
{	if (!_cur) return *this;KeyToInt kti;KeyOfT kot;const Node* old = _cur;_cur = _cur->_next;if (!_cur){// cur為nullptr，說明當前桶的結(jié)點已經(jīng)都走過了，去尋找下一個桶的第一個結(jié)點size_t hashi = kti(kot(old->_data)) % _ht->_hashtable.size() + 1;for (; hashi < _ht->_hashtable.size(); ++hashi){if (_ht->_hashtable[hashi]){_cur = _ht->_hashtable[hashi];break;}}}return *this;
}

?迭代器兼容大法

const迭代器和非const迭代器之間的區(qū)別就在于其對于容器的訪問權(quán)限，通過迭代器訪問容器的元素肯定需要使用的是迭代器的 * 以及 -> 運算符，所以我們只需要控制好這兩個運算符的返回類型，就能控制迭代器對容器的訪問權(quán)限。

// 迭代器
template<class K, class T, class Ref, class Ptr, class KeyToInt, class KeyOfT >
struct HashTable_Iterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyToInt, KeyOfT> HashTable;typedef HashTable_Iterator<K, T, Ref, Ptr, KeyToInt, KeyOfT> Self;HashTable_Iterator(Node* cur, const HashTable* ht):_cur(cur), _ht(ht){}Node* _cur;const HashTable* _ht;Ref operator*(){return _cur->_data;}Ptr operator->(){return &(operator*());}};

我們利用模板參數(shù)來控制operator*以及operator->的返回值，來達到一份迭代器代碼兼容兩種版本迭代器的效果。

template<class K, class T, class KeyToInt, class KeyOfT>
class HashTable
{// 結(jié)構(gòu)體的友元聲明需要帶著模板參數(shù)// 這里友元聲明是因為HashTable_Iterator里需要用HashTable的指針去訪問其私有成員template<class K, class T, class Ref, class Ptr, class KeyToInt, class KeyOfT >friend struct HashTable_Iterator;typedef HashNode<T> Node;public:// 通過模板參數(shù)來控制operator*以及operator->的返回值，來達到一份迭代器代碼兼容兩種版本迭代器的效果。typedef HashTable_Iterator<K, T, T&, T*, KeyToInt, KeyOfT> iterator;typedef HashTable_Iterator<K, T, const T&, const T*, KeyToInt, KeyOfT> const_iterator;public:HashTable():_hashtable(__stl_next_prime(0)), _n(0){}private:vector<Node*> _hashtable;size_t _n;
};

三、[ ]重載

在進行[ ]重載之前，我們要先對我們之前版本的HashTable的一些函數(shù)的返回值做修改，使其返回值提供的信息更豐富起來。

?

我就不詳細粘貼代碼了，所有代碼都會在博客結(jié)尾給出 。

庫里面對[ ]重載的效果是達到了既能實現(xiàn)插入又能實現(xiàn)修改(key不存在為插入，key存在為修改)。

[ ]的重載只對unordered_map有意義，所以我們只實現(xiàn)這一個版本即可。

namespace MyHashMS
{template<class K, class V, class KeyToInt = KeyToInt<K>>class unordered_map{// ...typedef HashTable<K, pair<K, V>, KeyToInt, MapKeyOfT> HashTable;typedef typename HashTable::iterator iterator;typedef typename HashTable::const_iterator const_iterator;public:V& operator[](const K& key){// ret拿到插入數(shù)據(jù)的返回值auto ret = insert({ key,V() });// 如果插入成功，返回value的引用    （ 插入功能 ）// 如果插入失敗，也就是原本就存在，返回原本就在的kv的value的引用   （ 修改功能 ）return ret.first->second;}private:HashTable _ht;};}

四、實現(xiàn)不能修改key

數(shù)據(jù)是通過key來定位到哈希表中的，所以如果我們把key修改掉，會造成數(shù)據(jù)查找不到、數(shù)據(jù)完整性及安全性等問題，所以實現(xiàn)這個功能還是很有必要的。

在外層，用戶通過只能迭代器拿到key，所以我們需要保證Ptr operator->()以及Ref operator*()返回的data中的key值為const，所以需要修改data存儲的數(shù)據(jù)類型中的key為const，所以我們直接定位到哈希表的結(jié)點。

template<class T>
struct HashNode
{HashNode(const T& data):_data(data),_next(nullptr){}T _data; // 對于 unordered_map，T 是 pair<const K, V>；對于 unordered_set，T 是 const KHashNode* _next;
};

而T又是從外層的unordered_map和unordered_set傳入：

?如此我們便實現(xiàn)了不能修改key的功能。

實現(xiàn)及測試代碼

下面是我本博客最終實現(xiàn)好的所有代碼，供大家參考。

HashTable.h

#pragma once
#include <iostream>
#include <vector>
#include <string>
using namespace std;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
};inline unsigned long __stl_next_prime(unsigned long n)
{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;
}template<class K>
struct KeyToInt
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct KeyToInt<string>
{size_t operator()(const string& key){size_t ret = 0;for (auto& e : key){ret += e;ret *= 131;}return ret;}
};// 鏈地址法-哈希表-兼容版
namespace MyHashMS
{// 哈希表的桶結(jié)點//          pair或keytemplate<class T>struct HashNode{HashNode(const T& data):_data(data),_next(nullptr){}T _data; // 對于 unordered_map，T 是 pair<const K, V>；對于 unordered_set，T 是 const KHashNode* _next;};// 編譯器為了提升效率，查找只會向上，迭代器要用到HashTable，故需要前置聲明template<class K, class T, class KeyToInt, class KeyOfT>class HashTable;// 迭代器template<class K, class T, class Ref, class Ptr, class KeyToInt, class KeyOfT >struct HashTable_Iterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyToInt, KeyOfT> HashTable;typedef HashTable_Iterator<K, T, Ref, Ptr, KeyToInt, KeyOfT> Self;HashTable_Iterator(Node* cur, HashTable* ht):_cur(cur),_ht(ht){}// 迭代器存儲當前結(jié)點指針和其對應的哈希表指針（其實_hashtable也可以）Node* _cur;HashTable* _ht;// 前置++Self& operator++(){	if (!_cur) return *this;KeyToInt kti;KeyOfT kot;const Node* old = _cur;_cur = _cur->_next;if (!_cur){// cur為nullptr，說明當前桶的結(jié)點已經(jīng)都走過了，去尋找下一個桶的第一個結(jié)點size_t hashi = kti(kot(old->_data)) % _ht->_hashtable.size() + 1;for (; hashi < _ht->_hashtable.size(); ++hashi){if (_ht->_hashtable[hashi]){_cur = _ht->_hashtable[hashi];break;}}}return *this;}Ref operator*(){return _cur->_data;}Ptr operator->(){return &(operator*());}bool operator==(const Self& other){return _cur == other._cur && _ht == other._ht;}bool operator!=(const Self& other){return !(*this == other);}};//        key    pair或key    KeyToInt由上層傳，這樣修改轉(zhuǎn)整數(shù)的邏輯比較方便//                                KeyOfT也是從上層傳，set傳直接返回key的，map傳pair<>.first的template<class K, class T, class KeyToInt, class KeyOfT>class HashTable{// 結(jié)構(gòu)體的友元聲明需要帶著模板參數(shù)// 這里友元聲明是因為HashTable_Iterator里需要用HashTable的指針去訪問其私有成員template<class K, class T, class Ref, class Ptr, class KeyToInt, class KeyOfT >friend struct HashTable_Iterator;typedef HashNode<T> Node;public:typedef HashTable_Iterator<K, T, T&, T*, KeyToInt, KeyOfT> iterator;typedef HashTable_Iterator<K, T, const T&, const T*, KeyToInt, KeyOfT> const_iterator;public:HashTable():_hashtable(__stl_next_prime(0)),_n(0){}iterator begin(){for (auto& e : _hashtable){if (e)return { e,this };}return	end();}iterator end(){return { nullptr, this };}const_iterator begin() const {for (auto& e : _hashtable){if (e)return { e,this };}return	end();}const_iterator end() const{return { nullptr, this };}// 清除數(shù)據(jù)，釋放結(jié)點，便于析構(gòu)和賦值運算符重載復用void clear(){// 走個循環(huán)就好for (size_t i = 0; i < _hashtable.size(); ++i){// 查找每個桶有無需要釋放的結(jié)點，有則釋放，沒有就看下一個桶Node* cur = _hashtable[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_hashtable[i] = nullptr;}}// 有new申請的結(jié)點，這些結(jié)點是自定義類型，需要手動寫析構(gòu)函數(shù)~HashTable(){clear();}// 拷貝構(gòu)造HashTable(const HashTable& other):_hashtable(other._hashtable.size()), _n(0){// 初始化列表是先走的，這里用_hashtable的size不用擔心 for (size_t i = 0; i < _hashtable.size(); ++i){Node* cur = other._hashtable[i];while (cur){Insert(cur->_data);cur = cur->_next;}}}// 賦值運算符重載HashTable& operator=(const HashTable& other){// 自我賦值檢測if(other != *this){// 先清除原來的數(shù)據(jù)clear();// 調(diào)整大小_hashtable.resize(other._hashtable.size());_n = 0;// 復制數(shù)據(jù)for (size_t i = 0; i < _hashtable.size(); ++i){Node* cur = other._hashtable[i];while (cur){Insert(cur->_data);cur = cur->_next;}}}return *this;}pair<iterator, bool> Insert(const T& data){KeyToInt kti;KeyOfT kot;// 不允許重復auto ret = Find(kot(data));if (ret != end())return { ret, false };// 擴容if (_n * 10 / _hashtable.size() >= 10){HashTable newHashTable;newHashTable._hashtable.resize(__stl_next_prime(_hashtable.size() + 1));for (size_t i = 0; i < _hashtable.size(); ++i){Node* cur = _hashtable[i];while (cur){size_t hashi = kti(kot(cur->_data)) % newHashTable._hashtable.size();newHashTable.Insert(cur->_data);cur = cur->_next;}}_hashtable.swap(newHashTable._hashtable);}Node* newnode = new Node(data);size_t hashi = kti(kot(data)) % _hashtable.size();// 頭插newnode->_next = _hashtable[hashi];_hashtable[hashi] = newnode;++_n;return { { newnode,this }, true };}iterator Find(const K& key){KeyToInt kti;KeyOfT kot;size_t hashi = kti(key) % _hashtable.size();Node* cur = _hashtable[hashi];while (cur && kot(cur->_data) != key){cur = cur->_next;}return { cur,this };}bool Erase(const K& key){KeyToInt kti;KeyOfT kot;size_t hashi = kti(key) % _hashtable.size();Node* cur = _hashtable[hashi];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){// 頭刪/不是頭刪prev == nullptr ? _hashtable[hashi] = cur->_next : prev->_next = cur->_next;delete cur;--_n;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector<Node*> _hashtable;size_t _n;};
}

unordered_set.h

#pragma once
#include "HashTable.h"namespace MyHashMS
{template<class K, class KeyToInt = KeyToInt<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};typedef HashTable<K, const K, KeyToInt, SetKeyOfT> HashTable;typedef typename HashTable::iterator iterator;typedef typename HashTable::const_iterator const_iterator;public: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);}void print(){for (auto& e : _ht){cout << e << endl;}}private:// 關于KeyToInt和SetKeyOfT要不要傳模板類型的問題// 模板參數(shù)是要傳類型的，而前兩者K，K都是類型，顯然沒問題// KeyToInt是unordered_set模板參數(shù)里定義好的類型，也沒問題// SetKeyOfT是在unordered_set類里面定義的一個結(jié)構(gòu)體，也可以直接作為類型HashTable _ht;// 當實例化 unordered_set<int> 時，K 就會被推導為 int，然后 SetKeyOfT 就會根據(jù) K（即 int）來創(chuàng)建一個實例};}

unordered_map.h

	#pragma once#include "HashTable.h"namespace MyHashMS{template<class K, class V, class KeyToInt = KeyToInt<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};typedef HashTable<K, pair<const K, V>, KeyToInt, MapKeyOfT> HashTable;typedef typename HashTable::iterator iterator;typedef typename HashTable::const_iterator const_iterator;public:iterator begin() { return _ht.begin(); }iterator end() { return _ht.end(); }const_iterator begin() const { return _ht.begin(); }const_iterator end() const { return _ht.end(); }V& operator[](const K& key){// ret拿到插入數(shù)據(jù)的返回值auto ret = insert({ key,V() });// 如果插入成功，返回value的引用    （ 插入功能 ）// 如果插入失敗，也就是原本就存在，返回原本就在的kv的value的引用   （ 修改功能 ）return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}void print(){for (auto& e : _ht){cout << e.first << " " << e.second << endl;}}private:HashTable _ht;};}

test.cpp

#include "unordered_set.h"
#include "unordered_map.h"void umap_test()
{MyHashMS::unordered_map<string, string> umap;string s[] = { "abcd", "thatgirl", "hahaha", "ohye", "handsome", "apple", "oppo", "vivo","svip" };for (auto& e : s){umap.insert({ e, e });}// 修改和插入umap["thatgirl"] = "那個女孩";umap["sort"] = "算法";umap.print();cout << endl;if (umap.find("sort") != umap.end())cout << "find it!" << endl;cout << endl;umap.erase("sort");if (umap.find("sort") == umap.end())cout << "don't find!" << endl;cout << endl;umap.print();// 測試不能修改keyauto it = umap.find("apple");// it->first = "pear";it->second = "pear";}void uset_test()
{MyHashMS::unordered_set<string> uset;string s[] = { "abcd", "thatgirl", "hahaha", "ohye", "handsome", "apple", "oppo", "vivo","svip" };for (auto& e : s){uset.insert(e);}uset.print();cout << endl;if (uset.find("ohye") != uset.end())cout << "find!" << endl;uset.erase("ohye");cout << endl;if (uset.find("ohye") == uset.end())cout << "don't find!" << endl;cout << endl;uset.print();// 測試不能修改keyauto it = uset.find("apple");// *it = "pear";}// main函數(shù)不能放到命名空間之中，不然編譯器找不到程序的入口
int main()
{umap_test();// uset_test();//hash<int> int_hasher;//hash<string> s_hasher;//cout << int_hasher(123) << endl;//cout << s_hasher("acsjak") << endl;return 0;
}

---

完結(jié)撒花啦~

(??????)??