前言：
首先我们要知道unordered_map和unordered_set的底层是用hash表实现的，也就是说它们底层成员就是一个哈希类的对象，完成了对它的封装，为两个关联容器，即以hash的模版，对应两者传模版参数完成调用工作，下面我们根据这两个的不同调用工作来模拟实现以下。
一·哈希表的调用：
这里我们采用的是链地址发来实现的hash表，也就说这是一个基本的模版hash表，但是我们不能直接用，因为如果是为了适应unordered_map和unordered_set，还需要有迭代器，比较真实的key值完成增删等一系列操作，故下面我们会对它进行调整，下面就是对应修改前的链地址hash：
pragma once
include
include
include
using namespace std;
namespace hash_bucket
{
enum State
{
EXIST,
EMPTY,
DELETE
};
//仿函数把不同类型的hash值转化整数：
template
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
// BKDR
size_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
struct HashNode
{
T _data;
HashNode* _next;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
首先我们要明白所谓的这样的迭代器其实就是一个类封装了指针（其他的根据具体用到的来实现），然后就是对应类去调用这个iterator类完成操作等。
首先先上模版参数，后面我们再解释：
template>
看起来有点多，是的，所谓模版参数就是当我们在这个类内完成相关操作所用到的（可以让我们传不同类型都能完成同一操作的匹配值）
下面对它们为什么这么设计来具体解释一下：
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 HashTable;//前置声明，否则下面无法识别HashTable：因为HashTable在其下面，编译器还不认识，故要声明一下
这里我们在后面对hash类的模版添加了模版参数class Hash = HashFunc，由于缺省参数出现一次就好故上面不用写缺省参数了。
下面是我们因为类型名太长而typedef：
typedef HashNode Node;
using HT = HashTable>;
using self=HTIterator ;
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 > //缺省参数只能定义一次（不能重复定义）
这里我们声明不能写在public之外，否则就是私有了。
相关报错：
更改一下：
typedef HTIterator Iterator;
typedef HTIterator ConstIterator;
using Node = HashNode;//这里typedef不能在上面，因为类内默认私有，导致封装后的unordered_map,set，无法访问私有
这里我们可以发现在上面实现的iterator的operator++操作的时候会用_ht访问里面的_tables，iterator类相当于hash这个类是外部，不能访问器其内部私有成员，要么搞一个get私有的函数，要么友元类一下。
相关报错：
因此我们把iterator搞成hash类的友元类。
//友元声明：
template
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这个缺省值放在了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::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 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 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& kv)
{
return kv.first;
}
};
然后多重载了一下operator[] ：
V& operator
{
pair 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 insert(const pair& 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，可以修改second
it->second += " + second";
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
四·相关头文件汇总：
4.1 hash_table.h：
pragma once
include
include
include
using namespace std;
namespace hash_bucket
{ //把key搞成数字的仿函数：
template
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
// BKDR
size_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那么就是k
struct 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 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//这里把默认的缺省值放在外面。里面默认是hash
class unordered_map
{
struct getkeyoft
{
const K& operator()(const pair& 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，可以修改second
it->second += " + second";
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
}
以后的山高路远，我们一同加油！！！！
