【C++】unordered系列容器的模拟实现
【C++】unordered系列容器的模拟实现
Ⅰ. 前言
由哈希表的知识我们可知开散列其实是比闭散列有优势的，所以下面的实现都是基于开散列的基础实现的！
Ⅱ. 对哈希表的改造
一、模板参数列表的改造
从之前的红黑树改造可知，我们得多传一个 KeyOfT ，因为如果我们的 map 或 set 想存不同的数据类型的话，那么 T 取 Key 的方式就不一样了，比如如果是内置类型则直接取，但是如果是 pair 类型，那我们取的其实是 pair 的 first，所以这里我们得增加一个 KeyOfT 的模板参数：
// K:关键码类型
// T: 不同容器T的类型不同，如果是unordered_map，T代表一个键值对，如果是unordered_set,T 为 K
// KeyOfT: 因为T的类型不同，通过T取key的方式就不同，详细见unordered_map/set的实现
// HashFunc: 哈希函数仿函数对象类型，哈希函数使用除留余数法，需要将Key转换为整形数字才能取模
template <class K, class T, class KeyOfT, class HashFunc = Hash<K>>
class hashtable;这样子的话我们也要对之前哈希表中的节点数据进行修改：
template <class T>
struct HashNode
{
T _data; // 类型为T，变得泛型了
HashNode<T>* _next;
HashNode(const T& data, HashNode<T>* next = nullptr)
:_data(data)
, _next(next)
{}
}; 🔺 注： 记得有了 KeyOfT 后要去改一下 insert 等函数中的一些取 key 的细节，这里以 insert 为例，erase 和 find 都是类似的：
bool insert(const T& data)
{
KeyOfT kt; // 取key的仿函数
// 检测是否有重复元素
Node* ret = find(kt(data)); // 将data中的key取出来
if (ret != nullptr)
return false;
// 检测是否需要扩容
_CheckCapacity();
HashFunc _hs; // 哈希函数
size_t index = _hs(kt(data)) % _tables.size();
Node* newnode = new Node(data);
// 头插
newnode->_next = _tables[index];
_tables[index] = newnode;
++_n;
return true;
}二、哈希表的迭代器
① 迭代器的基础框架
在实现迭代器之前我们想一想，一个开散列结构在迭代时候，其实遍历一个桶是不难的，但是如何做到两个桶之间的切换呢？
解决方法有很多，比如说每次在遍历到一个桶时候就记录下该桶的下标数，等到链表遍历完再切换到下一个桶，或者说迭代器里面再存一个哈希表，用循环遍历该哈希表的所有桶的同时遍历每个桶的元素（但是空间消耗比较大，因为开辟了一个哈希表）…
我们这里采取另一种方法，就是 迭代器里面再存一个哈希表的指针！
template <class K, class T, class Ref, class Ptr, class KeyOfT, class HashFunc>
struct _HTIterator
{
typedef HashNode<T> Node;
typedef _HTIterator<K, T, Ref, Ptr, KeyOfT, HashFunc> iterator;
Node* _node;
hashtable<K, T, KeyOfT, HashFunc>* _pht; // 哈希表的指针
// 构造函数
_HTIterator(Node* node, hashtable<K, T, KeyOfT, HashFunc>* pht)
:_node(node)
, _pht(pht)
{}
}; ❓ 问题来了，我们迭代器是声明在哈希表前面的，也就是说我们的哈希表去 typedef 迭代器没问题，但是当我们在迭代器里面声明一个哈希表指针，显然是需要有声明才行，但是由于位置关系，迭代器就找不到哈希表的声明，就会报错啦，那该咋办？
💡 方法：使用前置声明（要注意的是带有模板参数要将模板参数列表也带上）
这里看似我们把问题解决了，其实里面还隐含着一些其他的问题：
🚅 因为我们还没有实例化对象，所以问题没有被报出来，但是我们其实可以看到，这里的迭代器声明了一个哈希表，也就是说需要去访问哈希表的成员变量，那么按我们之前所学的知识我们可以知道其他类是不能直接访问一个类的 private 成员的，这里没有报错只是我们还没实例化出对象，一旦实例化就会报错权限问题，那我们该怎么办呢？
💡 方法： 使用友元（与上面的前置声明一样，这里也要带上模板参数列表才完整）
② 迭代器的常见函数实现
我们会着重讲解 operator++() 的实现，而其他的都是和其他容器类似的，这里就一步带过：
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}operator++()：
回到主题，我们前面说，遍历一个桶其实就是遍历单链表，这是不难的，难的是我们如何在桶之间切换呢？这里我们就用到了==哈希表的指针==！为什么不是哈希表呢？前面说过如果是指针的话，节省空间哈哈哈！
- 如果
_node->_next不为空，则说明这个桶还没遍历完，所以继续 遍历到链表的下一个元素 即可。 - 如果
_node->_next为空，则说明这个桶已经遍历完了或者不存在元素，则要进行一些处理：- 通过哈希表的指针（因为有了哈希表的指针就能得到哈希表的长度）找到目前桶的位置
index，然后再让其index++就得到下一个桶的位置 - 接着循环判断下一个桶是否为空，或者位置
index是否已经超出了哈希表的长度- 若不为空则让
_node移动到index位置 - 若为空则让
index++，直到找到或者出界
- 若不为空则让
- 最后出了循环后要判断一下位置
index是否出界，若出界说明哈希表遍历完成，则直接让_node = nullptr
- 通过哈希表的指针（因为有了哈希表的指针就能得到哈希表的长度）找到目前桶的位置
Self& operator++()
{
// 不为空说明还没遍历完该桶
if (_node->_next != nullptr)
{
_node = _node->_next;
}
else // 为空则需要切换桶
{
KeyOfT kt;
HashFunc _hs;
// 通过哈希表的指针找到目前桶的位置，然后再让其++就得到下一个桶的位置
size_t index = _hs(kt(_node->_data)) % _pht->_tables.size();
index++;
// 寻找下一个不为空的桶
while (index < _pht->_tables.size())
{
// 不为空则让 _node 移动过来
if (_pht->_tables[index] != nullptr)
{
_node = _pht->_tables[index];
break;
}
else // 为空则继续判断下一个桶
{
index++;
}
}
// 出了循环后要判断是否出界
if (index >= _pht->_tables.size())
_node = nullptr;
}
return *this;
}operator++(int)：
有了 operator++()，我们就可以复用其来实现我们的 后置++ 了，思路和其他容器的迭代器是类似的：
Self operator++(int)
{
Self tmp(this->_node, this->_pht);
++*this;
return tmp;
}🚗 值得注意的是，我们实现的哈希表是没有 operator--() 和 反向迭代器的，所以我们只需要实现正向迭代器的 operator++() 即可，因为哈希表是无序的，迭代只是为了遍历其中的元素，所以拥有反向迭代器的意义是不大的！
③ 哈希表对迭代器的利用
其实就是实现 begin() 和 end()，以及将 insert 的返回值变成 iterator 等等…
- 对于 begin() ：
我们不能直接的返回哈希表的首个元素，因为有可能首个桶中是没有元素的，所以我们对 begin 的定义是 第一次元素出现的位置。
🔴 注：这里构造迭代器的时候，返回的第二个参数的哈希表，我们可以用 this 做为参数！
iterator begin()
{
for (size_t i = 0; i < _tables.size(); ++i)
{
// 若出现不为空则直接返回对应的迭代器
if (_tables[i] != nullptr)
{
return iterator(_tables[i], this);
}
}
return end();
}- 对于 end() ：
iterator end()
{
return iterator(nullptr, this);
}- 对于 insert() ：
🐰 这里有一些细节，就是要将 ret 的类型从 Node* 转化为 iterator，并且将 ret != nullptr 转化为 ret != end()
pair<iterator, bool> insert(const T& data)
{
KeyOfT kt;
// 检测是否有重复元素
iterator ret = find(kt(data));
if (ret != end())
return make_pair(ret, false);
// 检测是否需要扩容
_CheckCapacity();
HashFunc _hs; // 哈希函数
size_t index = _hs(kt(data)) % _tables.size();
Node* newnode = new Node(data);
// 头插
newnode->_next = _tables[index];
_tables[index] = newnode;
++_n;
return make_pair(iterator(newnode, this), true);
}- 对于 find() ：
iterator find(const K& key)
{
if (_tables.size() == 0)
return iterator(nullptr, this);
KeyOfT kt;
HashFunc _hs; // 哈希函数
size_t index = _hs(key) % _tables.size();
Node* cur = _tables[index];
while (cur != nullptr)
{
if (kt(cur->_data) == key)
return iterator(cur, this);
cur = cur->_next;
}
return iterator(nullptr, this);
}☠ 一个小坑，注意在哈希表中 typedef ... iterator 的时候，记得要将 typedef 语句放在 public 权限中，不然 unordered_map/unordered_set 在取 iterator 的时候会没权限！
三、哈希表的桶操作函数
① 返回哈希桶中桶的总个数
// 返回哈希桶中桶的总个数
size_t bucket_count() const
{
return _tables.size();
}② 返回 n 号桶中有效元素的总个数
// 返回n号桶中有效元素的总个数
size_t bucket_size(size_t n) const
{
size_t count = 0;
Node* cur = _tables[n];
while (cur != nullptr)
{
count++;
cur = cur->_next;
}
return count;
}③ 返回元素 key 所在的桶号
// 返回元素key所在的桶号
size_t bucket(const K& key) const
{
HashFunc hs;
return hs(key) % _tables.size();
}四、哈希表的拷贝构造函数与赋值重载
拷贝构造函数：
hashtable(const hashtable<K, T, KeyOfT, HashFunc>& s)
{
_tables.resize(s._tables.size());
for (size_t i = 0; i < _tables.size(); ++i)
{
Node* tmp = s._tables[i];
while (tmp != nullptr)
{
Node* copy = new Node(tmp->_data);
// 头插
copy->_next = _tables[i];
_tables[i] = copy;
tmp = tmp->_next;
}
}
// 记得将有效个数也拷贝过去
_n = s._n;
} 🔴 但是此时我们会发现有报错：
我勒个去，什么情况，我们没删除什么东西啊！为啥会报错勒？
原因其实因为 如果我们写了构造函数（包括拷贝构造函数），那么编译器就不会生成默认的构造函数，那么在 unordered_map 和 unordered_set 中去找 _ht 调用构造函数的时候，就找不到了，自然就无法构造出来！
为了解决这个问题，我们可以自己写个构造函数，但是其实没必要，因为默认生成的构造函数会帮我们去调用 vector 的构造函数，而 _n 则是内置类型给它个缺省值即可，那么我们怎么生成一个编译器默认生成的构造函数呢？
💡 方法如下：
// 告诉编译器使用默认的构造函数
hashtable() = default; 这样子问题就解决了！
赋值重载函数：
赋值重载就不用多说啦，直接用现代写法！
// 赋值重载
hashtable<K, T, KeyOfT, HashFunc>& operator=(hashtable<K, T, KeyOfT, HashFunc> s)
{
swap(_n, s._n);
_tables.swap(s._tables);
return *this;
}五、哈希表的析构函数
我们需要 遍历每个桶里面的元素，将其分别释放：
~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;
}
}Ⅲ. unordered_set的封装
有了哈希表的框架其实我们对两个 unordered 系列的封装就非常简单了，直接调用哈希表的函数去替我们完成即可！
♻️ 这里的重点和细节仍然是 KeyOfT 的用法而已，具体的可以参考 map 和 set 实现的讲解，这里不过多叙述！
#pragma once
#include "HashTables.h"
namespace liren
{
template <class K, class HashFunc = Hash<K>>
class unordered_set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
// 取哈希表中的iterator，因为哈希表还没实例化，所以要用typename指定
typedef typename LinkHash::hashtable<K, K, SetKeyOfT, HashFunc>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
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);
}
size_t bucket_count() const
{
return _ht.bucket_count();
}
size_t bucket_size(size_t n) const
{
return _ht.bucket_size(n);
}
size_t bucket(const K& key)
{
SetKeyOfT kt;
return _ht.bucket(key);
}
private:
LinkHash::hashtable<K, K, SetKeyOfT, Hash<K>> _ht;
};
void testset()
{
unordered_set<int> st;
int a[] = { 4, 24, 14,7,37,27,57,67,34,14,54 };
for (auto e : a)
st.insert(e);
auto it = st.begin();
while (it != st.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : a)
st.erase(e);
}
}Ⅳ. unordered_map的封装
#pragma once
#include "HashTables.h"
namespace liren
{
template <class K, class V, class HashFunc = Hash<K>>
class unordered_map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
// 取哈希表中的iterator，因为哈希表还没实例化，所以要用typename指定
typedef typename LinkHash::hashtable<K, pair<K, V>, MapKeyOfT, HashFunc>::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 = 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);
}
size_t bucket_count() const
{
return _ht.bucket_count();
}
size_t bucket_size(size_t n) const
{
return _ht.bucket_size(n);
}
size_t bucket(const K& key)
{
return _ht.bucket(key);
}
private:
LinkHash::hashtable<K, pair<K, V>, MapKeyOfT, Hash<K>> _ht;
};
void testmap1()
{
unordered_map<int, int> mp;
int a[] = { 4, 24, 14,7,37,27,57,67,34,14,54 };
for (auto e : a)
mp.insert(make_pair(e, e));
auto it = mp.begin();
while (it != mp.end())
{
cout << it->first << ":" << it->second << " ";
++it;
}
cout << endl;
/*for (auto& e : mp)
{
e.second = 1;
cout << e.second << " ";
}*/
//mp[24] = 1;
/*for (auto e : a)
mp.erase(e);*/
it = mp.begin();
while (it != mp.end())
{
cout << it->first << ":" << it->second << " ";
it++;
}
cout << endl;
}
void testmap2()
{
unordered_map<int, int> mp;
int a[] = { 4, 24, 14,7,37,27,57,67,34,14,54 };
for (auto e : a)
mp.insert(make_pair(e, e));
auto it = mp.begin();
while (it != mp.end())
{
cout << it->first << ":" << it->second << " ";
++it;
}
cout << endl;
cout << mp.bucket_count() << endl;
cout << mp.bucket_size(4) << endl;
cout << mp.bucket_size(0) << endl;
it = mp.begin();
while (it != mp.end())
{
cout << mp.bucket(it->first) << endl;
++it;
}
}
}腾讯云开发者
