哈希表模拟封装unordered_map和unordered_set

    杀马特主页：羑悻的小杀马特.-CSDN博客

 ------ ->欢迎阅读                欢迎阅读                           欢迎阅读                              欢迎阅读 <-------         

目录

前言：

一·哈希表的调用：

二·底层hash的修改操作：

2·1iterator类的实现：

2·1·1初始化：

2·1·2iterator的相关重载函数： 

2.2hash类内部的更改实现：

2·2·1begin()和end()的实现：

2·2·2 查找的修改：

2·2·3 插入的修改：

2·2·4 删除的修改：

三·封装哈希:

3·1封装成unordered_set:

3·2封装成unordered_map:

四·相关头文件汇总：

4.1 hash_table.h：

4.2 my_unordered_set.h:

4.3 my_unordered_map.h:

---

---

前言：

首先我们要知道unordered_map和unordered_set的底层是用hash表实现的，也就是说它们底层成员就是一个哈希类的对象，完成了对它的封装，为两个关联容器，即以hash的模版，对应两者传模版参数完成调用工作，下面我们根据这两个的不同调用工作来模拟实现以下。

一·哈希表的调用：

这里我们采用的是链地址发来实现的hash表，也就说这是一个基本的模版hash表，但是我们不能直接用，因为如果是为了适应unordered_map和unordered_set，还需要有迭代器，比较真实的key值完成增删等一系列操作，故下面我们会对它进行调整，下面就是对应修改前的链地址hash：

#pragma once
#include<iostream>
#include<vector>
#include<algorithm>using namespace std;namespace hash_bucket
{enum State{EXIST,EMPTY,DELETE};//仿函数把不同类型的hash值转化整数：template<class K>struct HashFunc{size_t operator()(const K& key){return (size_t)key;}};template<>struct HashFunc<string>{size_t operator()(const string& s){// BKDRsize_t hash = 0;for (auto ch : s){hash += ch;hash *= 131;}return hash;}};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;}template<class K, class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{using Node = HashNode<K, V>;public:HashTable():_tables(8), _n(0){}HashTable &operator=( HashTable& x) {this->_n = x._n;vector<Node*> tmp(x._tables.size());for (int i = 0; i < tmp.size(); i++) {if (x._tables[i]) {Node* cur = x._tables[i];while (cur) {Node* bptr = new Node(cur->_kv);bptr->_next = tmp[i];tmp[i] = bptr;cur = cur->_next;}}}this->_tables.swap(tmp);return *this;}/*void swap( HashTable& x) {HashTable tmp;tmp = *this;*this = x;x = tmp;}*/HashTable(HashTable& x) {*this = x;}~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 pair<K, V>& kv){if (Find(kv.first))return false;Hash hash;//扩容：if (_n == _tables.size()) {vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur) {//这里不能直接把一串搞到新的vector因为，扩容后size改变对应的映射关系会和之前不一样Node* next = cur->_next;size_t hashi = hash(cur->_kv.first) % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTable);}///头插:size_t hashi=hash(kv.first)% _tables.size();Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi]=newnode;_n++;return true;}Node* Find(const K& key){Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];Node* pre= nullptr;while (cur) {if (pre == nullptr && cur->_kv.first == key) {_tables[hashi] = cur->_next;delete cur;cur = nullptr;--_n;return true;}else if (cur->_kv.first == key) {pre->_next = cur->_next;delete cur;cur = nullptr;--_n;return true;}else {pre = cur;cur = cur->_next;}}return false;}private:vector<Node*> _tables;size_t _n = 0;};};

这里我们对它内部基本的函数完成了实现，以及因为它有资源的使用，故我们也给他增加可显示析构，拷构等操作，故下一步就是对它等一下修改操作了。

二·底层hash的修改操作：

2·1iterator类的实现：

这里我们默认iterator内部封装的是一个节点类型的指针也就是node*（当然这里封装了hash类型的对象指针，后面会介绍到）

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

首先我们要明白所谓的这样的迭代器其实就是一个类封装了指针（其他的根据具体用到的来实现），然后就是对应类去调用这个iterator类完成操作等。

首先先上模版参数，后面我们再解释：

template<class K, class T,class getkeyoft, class Ref, class Ptr ,class Hash = HashFunc<K>>

看起来有点多，是的，所谓模版参数就是当我们在这个类内完成相关操作所用到的（可以让我们传不同类型都能完成同一操作的匹配值） 

下面对它们为什么这么设计来具体解释一下：

T类型要么是pair要么是key，后面会出现K，这个是根据T的取值而判断，如果T是pair就是其first，为Key那么就是k。

然后我们的getkeyoft其实我们实现的一个仿函数（他可以根据我们的T类型的数据（可能是pair也可能是key），在我们封装的不同类中完成相应转化，让我们取到它真实的key完成像增删查等用到key（不能修改相当于它自身的性质）的工作）->因为我们无法判断T的具体类型，故要新设置一个模版参数完成对应工作是的K对应的就是它的真实key。

后面就是我们的Ref和Ptr：这里我们封装的是一个iterator的类但是后面我们还要封装const_iterator，这时我们会发现它们有很多相似的地方，只不过对它所指向的数据等不能修改而相当于加了个const而已，这时只有两个不一样一个是重载的解引用和operator ->；这时我们就可以用到这个模版了，到时候给模版传参不就获得了正反迭代器了嘛。

最后一个Hash是我们上面hash类实现的一个可以帮我们实现对应key转化成无符号整型放入

hash表的一个仿函数了。

这里我们顺便说一句，防止后面当构建时候忘记了： 

我们在写完iterator类以及后面更改完hash后会发现，它们互相产生了依赖关系：也就是说当编译器在处理阶段，从上往下识别这个iterator这个类的时候，里面出现了我们后面定义的hash类，这时它无法识别就会这样报错：

故如果设想一下我们写了好多，突然这一步出现这么多错误，我们却想不到它仅仅是一个添加声明的事情，故我们当写这个iterator类的时候就应该发现并添加声明：

template<class K, class T,  class getkeyoft, class Hash >//缺省参数只能定义一次（不能重复定义）
class HashTable;//前置声明，否则下面无法识别HashTable：因为HashTable在其下面，编译器还不认识，故要声明一下

这里我们在后面对hash类的模版添加了模版参数class Hash = HashFunc<K>，由于缺省参数出现一次就好故上面不用写缺省参数了。

下面是我们因为类型名太长而typedef：

typedef HashNode<T> Node;
using HT = HashTable<K, T, getkeyoft, HashFunc<K>>;
using self=HTIterator<K, T, getkeyoft ,Ref,Ptr > ;

iterator的成员：

//成员变量：
Node* _node;
const HT*_ht;

2·1·1初始化：

HTIterator(Node* node, const HT* ht):_node(node)//不写析构，因为此时节点已经在HashTable中开辟出，会由它析构等释放掉, _ht(ht)
{}

2·1·2iterator的相关重载函数： 

这里有operator ->,* ,!=,还有++；这里我们主要说一下++（这里我们只实现对应的前置++（这里没有设置int类型参数））

我们加加的时候要注意如果当前桶的下一个不为空，我们就修改它的_node成下一个，否则就是下一个为空，那么此时我们就需要找下一个不为空的桶：那么怎么找呢？,我们不是有当前桶挂的末尾数据的一个（假定此时不为空的情况，否则更改为空），可以连着调用我们上面的两个仿函数获得对应的hashi，找到下一个，如果是nulllptr，然后保证不越界的情况继续往后走就行了，如果找不到就构建空就可以了。

提一下重载的operator -> ：这里iterator相当于指针，->后就拿到了它节点里的data的地址（也就是指向data的指针）这里重载是为了data是自定义类型服务的：正常是->()->a;假设自定义data类型内成员是a，重载后就可以这样访问了：->a:相当于省略一个->。

operator一系列重载函数实现：

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 {getkeyoft gkot;Hash hash;size_t hashi=hash(gkot(_node->_data))% _ht->_tables.size();hashi++;while (hashi < _ht->_tables.size()) {if (_ht->_tables[hashi]) {_node = _ht->_tables[hashi];break;}else {++hashi;}}//走到最后都没发现不是空的，故当成end（）返回空if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}

2.2hash类内部的更改实现：

下面我们来谈一下hash类要怎么修改。

首先就是模版参数：

template<class K,class T, class getkeyoft, class Hash = HashFunc<K>  > //缺省参数只能定义一次（不能重复定义）

这里我们声明不能写在public之外，否则就是私有了。

相关报错：

更改一下：

typedef HTIterator<K, T, getkeyoft, T&, T*> Iterator;
typedef HTIterator<K, T, getkeyoft, const T&, const T*> ConstIterator;
using Node = HashNode<T>;//这里typedef不能在上面，因为类内默认私有，导致封装后的unordered_map,set，无法访问私有

这里我们可以发现在上面实现的iterator的operator++操作的时候会用_ht访问里面的_tables，iterator类相当于hash这个类是外部，不能访问器其内部私有成员，要么搞一个get私有的函数，要么友元类一下。

相关报错：

因此我们把iterator搞成hash类的友元类。

//友元声明：
template<class K, class T, class Ref, class Ptr, class KeyOfT,class Hash >
friend struct HTIterator;

2·2·1begin()和end()的实现：

下面我们构造，析构等什么的都不需要改，只需要加一下相关调用对象的begin，end来对迭代器操作的接口函数就行。

首先来说end()就不用说了，构建个_node*为空的指针，外加本对象的_ht指针就行了。

下面说一下begin()实现操作：

就是需要我们找到这个hash表的vector中第一个节点不为nullptr 的指针构建就好了，遍历这个_tables，如果发现有节点不为空就拿它构建iterator对象，走到最后也没发现不是空的就直接返回end()即可

const_iterator也是如此，只不过我们给它const限制一下，并返回这个类型的迭代器就行了。

//迭代器的begin和end：Iterator begin()
{   //如果hash表未放入数据，相当于空故直接nullptr（end()）：if (_n == 0) return end();//如果不是空，那就遍历hash表找到第一个不为空的指针拿它构造迭代器：for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){Node* cur = _tables[i];return Iterator(cur, this);}}}
Iterator end()
{return Iterator(nullptr, this);
}ConstIterator begin()const
{   //如果hash表未放入数据，相当于空故直接nullptr（end()）：if (_n == 0) return end();//如果不是空，那就遍历hash表找到第一个不为空的指针拿它构造迭代器：for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){Node* cur = _tables[i];return ConstIterator(cur, this);}}}
ConstIterator end()const
{return ConstIterator(nullptr, this);
}

2·2·2 查找的修改：

这里我们要知道我们查找找到了，要把原来的返回值从bool到此位置的迭代器了，但是其中我们由于不知道T的类型，还要比较真实的key，故此时我们就要调用当时写的仿函数getkeyoft这个类了。

修改后代码：

	Iterator  Find(const K& key){Hash hash;getkeyoft gkot;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (gkot(cur->_data) == key){return {cur,this};}cur = cur->_next;}return end();}

2·2·3 插入的修改：

这里的插入操作里面就配合了上面实现的查找操作了；注意这里返回的虽然也是一个pair，但是里面first是此处迭代器（存在就是此处迭代器，否则就是插入位置的迭代器），second（插入成功就是true，否则就是false），里面还是配合了相关上面所述的仿函数。

修改后代码： 

	pair<Iterator,bool> Insert(const T& data){//发现存在返回end():getkeyoft gkot;if (Find(gkot(data))!= end()) return { Find(gkot(data)) ,false };Hash hash;//扩容：if (_n == _tables.size()) {vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur) {//这里不能直接把一串搞到新的vector因为，扩容后size改变对应的映射关系会和之前不一样Node* next = cur->_next;size_t hashi = hash(gkot(cur->_data)) % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTable);}///头插:size_t hashi = hash(gkot(data)) % _tables.size();Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return { Iterator(newnode,this),true};//Iterator的匿名对象}

2·2·4 删除的修改：

删除操作类型什么的都不用改，只不过内部用一下getkeyoft的仿函数得到相关key即可。

修改后代码：

	bool Erase(const K& key){Hash hash;getkeyoft gkot;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];Node* pre = nullptr;while (cur) {if (pre == nullptr && gkot(cur->_data) == key) {_tables[hashi] = cur->_next;delete cur;cur = nullptr;--_n;return true;}else if (gkot(cur->_data) == key) {pre->_next = cur->_next;delete cur;cur = nullptr;--_n;return true;}else {pre = cur;cur = cur->_next;}}return false;}

 这里大差不大我们的hash类就修改完了，后面就开始对它进行封装成两个类了。

三·封装哈希:

3·1封装成unordered_set:

此时需要我们把刚才修改后的hash类头文件包含以及展开，然后对应我们只让它传一个类型的参数，故把对应的 HashFunc<K>这个缺省值放在了hash类里面直接让它缺省就完成了。

首先我们在修改hash类的时候说封装的时候写这个仿函数的类，因此下面完成getkeyoft（对于单纯的key类型）：

struct getkeyoft
{const K& operator()(const K& key){return key;}

所包含的成员就是hash类的一个对象，这里无需初始化，因为自定义类型自己调用初始化:

	HashTable<K, const K, getkeyoft> _ht;

下面我们这个封装的类用的iterator就是我们修改后hash类里面的迭代器了；这里由于类型太长故typedef一下（也可以用auto）： 

//为了编译器区分类型还是变量（typename也可auto）
typedef typename hash_bucket::HashTable<K, const K, getkeyoft >::Iterator iterator;

这里如果把hash类内的迭代器typedef放在public外，此时再这样就显示无法访问了，因此当时要写在类里。 

 下面就是简单的调用成员_ht对象的类内的函数即可：

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 test_set1()
{int a[] = {  3,11,999,7,193,82,1,9,5,62333,7,6  };unordered_set<int> s;for (auto e : a){s.insert(e);}unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it = 1; 迭代器解引用是key类型不准修改cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;}

  

3·2封装成unordered_map:

这里和上面封装的unordered_set很多一样，只不过是把getkeyoft是pair类型，取一下first即可：

struct getkeyoft
{const K& operator()(const pair<K, V>& kv){return kv.first;}
};

然后多重载了一下operator[] ：

V& operator[](const K& key)
{pair<iterator, bool> ret=insert({ key,V()});return ret.first->second;//这里迭代器->的重载省略了一个-> 原型是ret.first.operator ->()->second：//返回迭代器（指针）所指向成员的地址（data地址（指针））
}

其他相同函数:

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);
}iterator Find(const K& key)
{return _ht.Find(key);
}bool Erase(const K& key)
{return _ht.Erase(key);
}

 测试接口函数： 

void test_map1(){unordered_map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "字符串", "string" });dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });dict["left"] = "左左边";dict["insert"] = "插入";dict["string"];for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}cout << endl;unordered_map<string, string>::iterator it = dict.begin();while (it != dict.end()){// 不能修改first，可以修改secondit->second += " + second";cout << it->first << ":" << it->second << endl;++it;}cout << endl;}

四·相关头文件汇总：

4.1 hash_table.h：

#pragma once
#include<iostream>
#include<string>
#include<vector>using namespace std;
namespace hash_bucket
{   //把key搞成数字的仿函数：template<class K>struct HashFunc{size_t operator()(const K& key){return (size_t)key;}};template<>struct HashFunc<string>{size_t operator()(const string& s){// BKDRsize_t hash = 0;for (auto ch : s){hash += ch;hash *= 131;}return hash;}};//根据素数表判断如何扩容：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;}template<class T>//初始化hash内的节点 ：T类型要么是pair要么是key，后面会出现K，这个是根据T的取值而判断，如果T是pair就是其first，为Key那么就是kstruct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K, class T,  class getkeyoft, class Hash >//缺省参数只能定义一次（不能重复定义）class HashTable;//前置声明，否则下面无法识别HashTable：因为HashTable在其下面，编译器还不认识，故要声明一下template<class K, class T,class getkeyoft, class Ref, class Ptr ,class Hash = HashFunc<K>>struct HTIterator//把迭代器当成指针故里面封装的也让它是指针{typedef HashNode<T> Node;using HT = HashTable<K, T, getkeyoft, HashFunc<K>>;using self=HTIterator<K, T, getkeyoft ,Ref,Ptr > ;//成员变量：Node* _node;const HT*_ht;HTIterator(Node* node, const HT* ht):_node(node)//不写析构，因为此时节点已经在HashTable中开辟出，会由它析构等释放掉, _ht(ht){}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 {getkeyoft gkot;Hash hash;size_t hashi=hash(gkot(_node->_data))% _ht->_tables.size();hashi++;while (hashi < _ht->_tables.size()) {if (_ht->_tables[hashi]) {_node = _ht->_tables[hashi];break;}else {++hashi;}}//走到最后都没发现不是空的，故当成end（）返回空if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}};template<class K,class T, class getkeyoft, class Hash = HashFunc<K>  > //缺省参数只能定义一次（不能重复定义）class HashTable{public:typedef HTIterator<K, T, getkeyoft, T&, T*> Iterator;typedef HTIterator<K, T, getkeyoft, const T&, const T*> ConstIterator;using Node = HashNode<T>;//这里typedef不能在上面，因为类内默认私有，导致封装后的unordered_map,set，无法访问私有//友元声明：template<class K, class T, class Ref, class Ptr, class KeyOfT,class Hash >friend struct HTIterator;HashTable():_tables(__stl_next_prime(0)), _n(0){}HashTable& operator=(HashTable& x) {this->_n = x._n;vector<Node*> tmp(x._tables.size());for (int i = 0; i < tmp.size(); i++) {if (x._tables[i]) {Node* cur = x._tables[i];while (cur) {Node* bptr = new Node(cur->_kv);bptr->_next = tmp[i];tmp[i] = bptr;cur = cur->_next;}}}this->_tables.swap(tmp);return *this;}HashTable(HashTable& x) {*this = x;}~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;}}//迭代器的begin和end：Iterator begin(){   //如果hash表未放入数据，相当于空故直接nullptr（end()）：if (_n == 0) return end();//如果不是空，那就遍历hash表找到第一个不为空的指针拿它构造迭代器：for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){Node* cur = _tables[i];return Iterator(cur, this);}}}Iterator end(){return Iterator(nullptr, this);}ConstIterator begin()const{   //如果hash表未放入数据，相当于空故直接nullptr（end()）：if (_n == 0) return end();//如果不是空，那就遍历hash表找到第一个不为空的指针拿它构造迭代器：for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){Node* cur = _tables[i];return ConstIterator(cur, this);}}}ConstIterator end()const{return ConstIterator(nullptr, this);}pair<Iterator,bool> Insert(const T& data){//发现存在返回end():getkeyoft gkot;if (Find(gkot(data))!= end()) return { Find(gkot(data)) ,false };Hash hash;//扩容：if (_n == _tables.size()) {vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur) {//这里不能直接把一串搞到新的vector因为，扩容后size改变对应的映射关系会和之前不一样Node* next = cur->_next;size_t hashi = hash(gkot(cur->_data)) % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTable);}///头插:size_t hashi = hash(gkot(data)) % _tables.size();Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return { Iterator(newnode,this),true};//Iterator的匿名对象}Iterator  Find(const K& key){Hash hash;getkeyoft gkot;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (gkot(cur->_data) == key){return {cur,this};}cur = cur->_next;}return end();}bool Erase(const K& key){Hash hash;getkeyoft gkot;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];Node* pre = nullptr;while (cur) {if (pre == nullptr && gkot(cur->_data) == key) {_tables[hashi] = cur->_next;delete cur;cur = nullptr;--_n;return true;}else if (gkot(cur->_data) == key) {pre->_next = cur->_next;delete cur;cur = nullptr;--_n;return true;}else {pre = cur;cur = cur->_next;}}return false;}private:vector<Node*> _tables; // 指针数组size_t _n = 0;};}

4.2 my_unordered_set.h:

#pragma once
#include"hash_table.h"
using namespace hash_bucket;
namespace my_map_set {template<class K>class unordered_set{  struct getkeyoft{const K& operator()(const K& key){return key;}};public://为了编译器区分类型还是变量（typename也可auto）typedef typename hash_bucket::HashTable<K, const K, getkeyoft >::Iterator iterator;typedef typename hash_bucket::HashTable<K, const K, getkeyoft>::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:HashTable<K, const K, getkeyoft> _ht;};void test_set1(){int a[] = { 3,11,999,7,193,82,1,9,5,62333,7,6 };unordered_set<int> s;for (auto e : a){s.insert(e);}unordered_set<int>::iterator it = s.begin();while (it != s.end()){//*it = 1; 迭代器解引用是key类型不准修改cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;}
}

4.3 my_unordered_map.h:

#pragma once
#include"hash_table.h"
using namespace hash_bucket;
namespace my_map_set {template<class K, class V>//这里把默认的缺省值放在外面。里面默认是hashclass unordered_map{struct getkeyoft{const K& operator()(const pair<K, V>& kv){return kv.first;}};public://为了编译器区分类型还是变量（typename也可auto）typedef typename hash_bucket::HashTable<K, pair<const K, V>, getkeyoft>::Iterator iterator;typedef typename hash_bucket::HashTable<K, const pair<const K, V>, getkeyoft>::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();}V& operator[](const K& key){pair<iterator, bool> ret=insert({ key,V()});return ret.first->second;//这里迭代器->的重载省略了一个-> 原型是ret.first.operator ->()->second：//返回迭代器（指针）所指向成员的地址（data地址（指针））}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);}private:HashTable<K, pair<const K, V>, getkeyoft> _ht;};void test_map1(){unordered_map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "字符串", "string" });dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });dict["left"] = "左左边";dict["insert"] = "插入";dict["string"];for (auto& kv : dict){cout << kv.first << ":" << kv.second << endl;}cout << endl;unordered_map<string, string>::iterator it = dict.begin();while (it != dict.end()){// 不能修改first，可以修改secondit->second += " + second";cout << it->first << ":" << it->second << endl;++it;}cout << endl;}
}

                                       

                                     以后的山高路远，我们一同加油！！！！