目录
四、封装 unordered_map 和 unordered_set 的接口
一、unordered系列关联式容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到log_2 N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered 系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍，unordered_multimap和unordered_multiset学生可查看文档介绍。
1、unordered_map
1. unordered_map是存储键值对的关联式容器，其允许通过keys快速的索引到与其对应的value。 2. 在unordered_map中，键值通常用于唯一地标识元素，而映射值是一个对象，其内容与此键关联。键和映射值的类型可能不同。
3. 在内部,unordered_map没有对按照任何特定的顺序排序, 为了能在常数范围内找到key所对应的value，unordered_map 将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问 value。 6. 它的迭代器至少是前向迭代器【unordered_map官方文档】
2、unordered_map的接口
①unordered_map的构造
| 函数声明 | 功能介绍 |
| 构造不同格式的unordered_map对象 |
②unordered_map的容量
| 函数声明 | 功能介绍 |
| bool empty() const | 检测unordered_map是否为空 |
| size_t size() const | 获取unordered_map的有效元素个数 |
③unordered_map的迭代器
| 函数声明 | 功能介绍 |
| begin | 返回unordered_map第一个元素的迭代器 |
| end | 返回unordered_map最后一个元素下一个位置的迭代器 |
| cbegin | 返回unordered_map第一个元素的const迭代器 |
| cend | 返回unordered_map最后一个元素下一个位置的const迭代器 |
④unordered_map的元素访问
| 函数声明 | 功能介绍 |
| operator[] | 返回与key对应的value，没有一个默认值 |
注意：该函数中实际调用哈希桶的插入操作，用参数key与V()构造一个默认值往底层哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失败，说明key已经在哈希桶中， 将key对应的value返回。
⑤unordered_map的查询
| 函数声明 | 功能介绍 |
| iterator find(const K&key) | 返回key在哈希桶中的位置 |
| size_t count(K& key) | 返回哈希桶中关键码为key的键值对的个数 |
注意：unordered_map中key是不能重复的，因此count函数的返回值最大为1
⑥unordered_map的修改操作
| 函数声明 | 功能介绍 |
| insert | 向容器中插入键值对 |
| erase | 删除容器中的键值对 |
| void clear() | 清空容器中有效元素个数 |
| void swap() | 交换两个容器中的元素 |
⑦unordered_map的桶操作
| 函数声明 | 功能介绍 |
| size_t bucket_count()const | 返回哈希桶中桶的总个数 |
| size_t bucket_size(size_t n)const | 返回n号桶中有效元素的总个数 |
| size_t bucket(const K& key) | 返回元素key所在的桶号 |
3、unordered_set
自行查阅文档【unordered_set在线文档说明】
二、哈希表的改造
我们要对哈希表进行改造，因为unordered_map和unordered_set底层用的都是哈希表，虽然不是同一个哈希表，但是是同一个模板实例化出来的哈希表。我们要让哈希表可以适配存储不同的数据类型，因为unordered_set里面存的是K类型，而unordered_map里面存的是pair<K,V>类型。
所以我们可以用来 T 表示。当传的模板参数是K类型，哈希表就实例化存的就是K类型，当传的模板参数是pair<K,V>类型，哈希表实例化存的就是pair<K,V>类型，所以我们可以通过传不同的模板参数来决定哈希表里存的是什么数据类型。
🔴【问题】
这里不管是插入还是查找还是删除第一步都是需要将数据的哈希地址找到，而哈希地址是利用除留余数法计算得到的，是利用key值进行取模的，但这里一旦适配泛型后，我们就不知道具体的类型是K类型还是pair<K,V>类型，如果是K类型那么就可以直接取模，如果是pair<K,V>类型，那是不可以直接取模的，需要将里面的key值取出来。
🟢【解答】
我们可以利用一个仿函数，这个仿函数的功能是可以将数据里的Key类型数据取出来。那么我们可以给哈希表增加一个模板参数，给仿函数用。一旦遇到要计算哈希地址或者比较的操作时，我们就可以将数据里的K值取出来进行计算比较。
仿函数实现的原理：当T类型是K类型数据时，直接返回K值即可，当T类型是pair<K,V>数据时，返回里面的first数据即可(就是K值)。
三、哈希表的迭代器
哈希表的迭代器是一个自定义类型，因为原生的结点指针不能满足我们想要的操作，所以我们就直接将结点的指针封装起来，然后自定义一个类型，对这个结点指针增加一些操作来完成我们想要的效果。
首先哈希表的迭代器里肯定要封装一个结点的指针，++后找到下一个结点，在一个哈希桶里，++就代表着找链表下面的结点即可，那么如果该结点就是链表最后一个结点呢？怎么找到下一个不为空的桶呢？又或者你是如何找到第一个不为空的桶的呢？
所以这里我们还需要一个指向哈希表的指针，这样我们才可以找到桶与桶之间的关系，而结点指针是用来找结点与结点之间的关系的。
哈希表的迭代器里封装两个对象，一个是结点指针，一个哈希表指针。
1、const 迭代器
与链表的const迭代器实现原理一样，我们通过三个模板参数(template <class T,class Ref,class Ptr>)来控制函数的返回值，从而控制返回的是普通类型的迭代器还是const类型的迭代器。这里也就是泛型适配，适配多种类型 。
Ref 控制解引用函数的返回值，当Ref为T&时，返回的就是普通迭代器，当Ref 为 const T&时，返回的就是 const 迭代器。
Ptr 控制的 -> 重载函数的返回值，当 Ptr 为T时，返回的就是普通迭代器，当 Ptr 为 const T时，返回的就是const迭代器。
2、 operator++
实现原理：
①假设当前结点在一个没有走完的桶里，那么直接找下一个结点即可
②如果这个结点是桶里最后一个节点，即桶走完了，那么我们就要找下一个不为空的桶
③如何找到下一个不为空的桶呢？首先将当前结点的哈希地址计算出来，然后将哈希地址++，再利用一个循环，查找后面的桶是否为空，如果不为空，那么这个桶就是最终结果，如果为空就再找后面的桶。
🔴【问题1】
这里存在一个相互依赖关系问题，因为在哈希表里我们使用了迭代器，在迭代器里我们又使用了哈希表。
🟢【解答1】
我们需要在这里使用前置声明告诉编译器，我们是有哈希表，只不过哈希表在后面。这样就不会报错啦。
🔴【问题2】
在迭代器的++里我们在计算当前结点的哈希地址时，取模时，利用哈希指针找到了哈希表里的vector<Node*> _tables 的元素，并访问了它的函数，这里我们在外面调用哈希表的私有成员，这样是不可行
🟢【解答2】让迭代器成为哈希表的友元类，这样在迭代器里就可以使用哈希表的私有成员了。
3、begin()/end()
begin()就是找哈希表里第一个不为空的桶。
end()就是找最后一个不为空的桶的下一个位置，也就是空
🔴 【问题】编译会提示没有构造函数可以接收，或者构造函数重载不明确。这是为什么呢？
🟢【解答】
问题在于const修饰begin()和const修饰end()。因为const修饰了this指针，导致指向哈希表的指针变成const类型了，而迭代器的构造里，是用普通迭代器构造的。所以当this指针传过去构造时，const是不能传给普通类型的，权限放大了。所以这里我们只需要重载一个参数类型是const类型的哈希表指针即可。
4、实现map[]运算符重载
map的[ ]运算符重载，底层实现本质是调用了 insert 函数。然后通过insert函数返回的pair<iterator,bool>类型数据来找到Value值。
所以在实现[ ]运算符重载时，我们需要对哈希表里的 insert 进行改造，因为原来的 insert 的返回值是布尔值，我们需要pair类型返回值。
哈希表的insert改造后，那么 set 和 map 里的insert都需要修改，因为底层用的就是调用用哈希表的insert。
🔴【问题】
我们之前让普通迭代变成const迭代器，而这里的pair<iterator,bool>中的iterator其实本质上是const_iterator。
是pair<const_itearto,bool>类型的。而哈希表里的insert返回的是普通迭代器，也就是pair<iterator,bool>类型的。这是两个不同的类型，无法直接将pair<iterator,bool>类型转换成pair<const_itearto,bool>类型的。所以会报错。
🟢【解答】
我们需要的是让普通迭代器能够拷贝给const迭代器。所以我们需要自己增加拷贝函数。库里的设计很妙，库里重新定义了一个 iterator，作为拷贝对象，而这个iterator固定了就是普通的迭代器，不会随着调用对象而改变类型。所以当普通迭代器调用时，就会将普通iterator拷贝给它。当const迭代器调用时，就会将普通迭代器iterator拷贝给它。所以我们需要对哈希表的迭代器添加拷贝构造。用普通迭代器iteartor作为拷贝对象。
四、封装 unordered_map 和 unordered_set 的接口
1、unordered_map
unordered_map中存储的是pair的键值对，K为key的类型，V为value的类型，HashFunc哈希函数类型 。unordered_map在实现时，只需将hash_bucket中的接口重新封装即可。
2、unordered_set
底层封装一个哈希表，哈希表里存的是K类型。
3、封装map和 set 迭代器
只有哈希表里的迭代器完成了，才可以封装map和set里的迭代器。
封装set的迭代器，本质就是调用哈希表的迭代器接口。
1.不过要注意的是，在重命名红黑树里的迭代器时，需要在类名前面加上typename，如果不加上typename是不行的，因为这时类模板还没有实例化出对象出来，就算实例化了，也有部分类型没有实例，因为编译器也不知道这个是内置类型还是静态变量，加上typename是告诉编译器这个是类型，这个类型在类模板里定义，等类模板实例化后再找。
2.定义好普通迭代和const迭代器后，就可以实现begin()和end()了。
五、解决 key 不能修改的问题
1、set
🔴【存在问题】
迭代器的解引用是可以修改的，一旦修改可能不是二叉树：
set 的 key 值、使用迭代器修改：
🟢【解决方法】
set 里存储的值就只有Key值，索性我们直接让这个存储的数据无法被修改，只能访问读取，无法修改。所以我们让普通迭代器变成const迭代器即可。所以在set里，我们将普通迭代器和const迭代器都设为const迭代器。
但此时会遇到一个问题，begin() 和 end() 的返回类型是const 迭代器，但是_t.begin()是普通迭代器，这样就会类型不匹配。因此我们需要定义一个构造函数将普通迭代器和const迭代器相转换。
2、map
🟢map的解决原理
在存储的时候就让K值无法修改。
因为我们知道map里存储的数据是pair<K，V>类型，我们不能想set那个让普通迭代器变成const迭代器，因为map要求Value的值还是可以修改的，所以不让pair<K,V>类型无法修改，而是单纯的让里面的K值无法修改，也就是在里面用const修饰K，那么这样K值就不能被修改，V值可以被修改。
pair是可以修改的，但是里面的K是无法被修改的！
六、完整代码
HashTable.h
#pragma once
#include<vector>
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
//HashFunc<string>
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
// BKDR
size_t hash = 0;
for (auto e : key)
{
hash *= 31;
hash += e;
}
//cout << key << ":" << hash << endl;
return hash;
}
};
namespace hash_bucket
{
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
// 前置声明
//这里存在问题，迭代器里要用哈希，哈希里面要有迭代器，相互依赖关系
//我们这里用前置声明告诉编译器，我们要是有哈希表，这个表是存在的，在后面
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct __HTIterator
{
typedef HashNode<T> Node;
typedef __HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
//底层封装着一个结点指针
Node* _node;
//底层还封装着一个哈希表指针
//这里可以加const因为我们不是根据pht来找到哈希表来修改哈希表里的内容
const HashTable<K, T, KeyOfT, Hash>* _pht;
size_t _hashi;
__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
:_node(node)
, _pht(pht)
, _hashi(hashi)
{}
__HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht, size_t hashi)
:_node(node)
, _pht(pht)
, _hashi(hashi)
{}
Self& operator++()
{
if (_node->_next)
{
// 当前桶还有节点，走到下一个节点
_node = _node->_next;
}
else
{
// 当前桶已经走完了，找下一个桶开始
//KeyOfT kot;
//Hash hf;
//size_t hashi = hf(kot(_node->_data)) % _pht._tables.size();
++_hashi;
while (_hashi < _pht->_tables.size())
{
if (_pht->_tables[_hashi])
{
_node = _pht->_tables[_hashi];
break;
}
++_hashi;
}
if (_hashi == _pht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
// unordered_set -> Hashtable<K, K>
// unordered_map -> Hashtable<K, pair<K, V>>
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
typedef HashNode<T> Node;
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct __HTIterator;
public:
//适配普通迭代器
typedef __HTIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
//适配const迭代器
typedef __HTIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return iterator(_tables[i], this, i);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this, -1);
}
const_iterator begin() const
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return const_iterator(_tables[i], this, i);
}
}
return end();
}
// this-> const HashTable<K, T, KeyOfT, Hash>*
const_iterator end() const
{
return const_iterator(nullptr, this, -1);
}
HashTable()
{
_tables.resize(10);
}
~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;
}
}
pair<iterator, bool> Insert(const T& data)
{
Hash hf;
KeyOfT kot;
iterator it = Find(kot(data));
if (it != end())
return make_pair(it, false);
// 负载因子最大到1
if (_n == _tables.size())
{
vector<Node*> newTables;
newTables.resize(_tables.size() * 2, nullptr);
// 遍历旧表
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
// 挪动到映射的新表
size_t hashi = hf(kot(cur->_data)) % newTables.size();
cur->_next = newTables[i];
newTables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTables);
}
size_t hashi = hf(kot(data)) % _tables.size();
Node* newnode = new Node(data);
// 头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return make_pair(iterator(newnode, this, hashi), true);
}
iterator Find(const K& key)
{
Hash hf;
KeyOfT kot;
size_t hashi = hf(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur, this, hashi);
}
cur = cur->_next;
}
return end();
}
bool Erase(const K& key)
{
Hash hf;
KeyOfT kot;
size_t hashi = hf(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0;
};
}unoederedMap.h
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include"HashTable.h"
namespace zhou
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
/*typedef typename hash_bucket<K, pair<K, V>, MapKeyOfT>::iterator iterator;
typedef typename hash_bucket<K, pair< K, V>, MapKeyOfT>::const_iterator const_iterator;*/
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
const V& operator[](const K& key) const
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}unorderedSet.h
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include"HashTable.h"
namespace zhou
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT, Hash>::const_iterator 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<const_iterator, bool> insert(const K& key)
{
auto ret = _ht.Insert(key);
return pair<const_iterator, bool>(const_iterator(ret.first._node, ret.first._pht, ret.first._hashi), ret.second);
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool erase(const K& key)
{
return _ht.Erase(key);
}
private:
hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;
};
//void test_set()
//{
// unordered_set<int> us;
// us.insert(5);
// us.insert(15);
// us.insert(52);
// us.insert(3);
// unordered_set<int>::iterator it = us.begin();
// while (it != us.end())
// {
// //*it += 5;
// cout << *it << " ";
// ++it;
// }
// cout << endl;
// for (auto e : us)
// {
// cout << e << " ";
// }
// cout << endl;
//}
}