【C++】unordered_set、unordered_map超详细封装过程，处理底层细节

🕗 发布于 2024-10-19 03:31 c++ 哈希算法散列表

🚀个人主页：@小羊 🚀所属专栏：C++ 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~

动图描述

前言

上篇文章我们简单地实现了哈希表，本篇文章将基于开散列实现的哈希表封装出unordered_set和unordered_map的基本功能。
本文不再从头实现哈希表，而是着重介绍封装unordered_set、unordered_map中的细节问题，如果小伙伴对哈希表的实现还不太熟悉的话请先阅读上篇文章。

1、数据泛型

基于封装set和map的经验，我们首先把哈希表中节点的模版参数修改一下，用于存储不同类型的K和pair<K, V>，同时底层的代码也要做相应的修改。

namespace hash_bucket
{
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)
{
size_t hash = 0;
for (auto e : s)
{
hash = hash * 31 + e;
}
return hash;
}
};

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

T _data;
HashNode<T>* _next;
};

template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable
{
typedef HashNode<T> Node;
public:
HashTable()
{
//提前开10个位置，多次扩容
_tables.resize(10, nullptr);
}

~HashTable()
{
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
Node* next = pcur->_next;
delete pcur;
pcur = next;
}
_tables[i] = nullptr;
}
}

bool Insert(const T& data)
{
Hash hs;
KeyOfT kot;
//扩容
if (_n == _tables.size())
{
vector<Node*> newtables(2 * _tables.size(), nullptr);
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
size_t hashi = hs(kot(pcur->data)) % newtables.size();
Node* next = pcur->_next;
pcur->_next = newtables[hashi];
newtables[hashi] = pcur;
pcur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(kot(data)) & _tables.size();

//头插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}

Node* Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* pcur = _tables[hashi];
while (pcur)
{
if (kot(pcur->_data) == key)
{
return pcur;
}
pcur = pcur->_next;
}
return End();
}

bool Erase(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _tables.size();
Node* pcur = _tables[hashi];
Node* prev = nullptr;
while (pcur)
{
if (kot(pcur->_data) == key)
{
if (prev == nullptr)
{
_tables[hashi] = pcur->_next;
}
else
{
prev->_next = pcur->_next;
}
delete pcur;
--_n;
return true;
}
prev = pcur;
pcur = pcur->_next;
}
return false;
}
private:
vector<Node*> _tables;
size_t _n = 0;//哈希表中实际元素个数
};
}

这里的析构函数不能用默认生成的析构函数，虽然vector会调用它的析构函数，但是其中的节点确不能被释放，因此还需要我们手动地进行释放。只需要遍历哈希表，如果有节点先记录下一个节点的地址，再释放，直到遍历完表。

2、迭代器

unordered_set和unordered_map迭代器的实现，是封装unordered_set和unordered_map的重中之重，也是比较复杂的地方。

template<class T>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<T> Self;

HTIterator(Node* node)
:_node(node)
{}

T& operator*()
{
return _node->_data;
}

T* operator->()
{
return &_node->_data;
}

bool operator!=(const Self& s)
{
return _node != s._node;
}

Node* _node;
};

2.1 ++重载

你可能会想，哈希表中哈希桶是一个链表，只需要pcur = pcur->_next就能得到下一个节点的迭代器，如果你真这样想我不禁要发出灵魂拷问：如果当前迭代器是当前桶的最后一个节点呢？

所以说，哈希表迭代器++前有两种情况：

当前迭代器不是当前桶的最后一个节点
当前迭代器是当前桶的最后一个节点

我们都知道第一种情况倒是好解决，但是第二种情况就很让人挠头。因为单就论两个链表而言，我们无法直接从一个链表上走到另一个链表上，这就阻挡了迭代器想要前进的脚步，怎么办呢？

聪明的你肯定注意到了我们说的是无法直接走，那我们就不直接走呗。单论两个链表确实找不到交集，但别忘了无论它们两个相距多远，哪怕相隔银河，它们也始终都在同一个哈希表中，所以当一个链表走到头时，我们可以借助哈希表找到下一个不为空的链表。
但是当前的迭代器中并没有哈希表，这也就意味着我们的迭代器中还需要有一个哈希表的指针（对象也可以，不过相对麻烦一点）。

//前置声明
template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
class HashTable;

template<class K, class T, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, KeyOfT, Hash> Self;

HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pth)
:_node(node)
,_pht(pht)
{}

T& operator*()
{
return _node->_data;
}

T* operator->()
{
return &_node->_data;
}

bool operator!=(const Self& s)
{
return _node != s._node;
}

Self& operator++()
{}

Node* _node;
HashTable<K, T, KeyOfT, Hash>* _pht;
};

这一步需要注意的反而是模版参数的对应问题

上面的代码中哈希表和迭代器有相互相互依赖的问题，因为我们的哈希表和迭代器肯定是定义一个在前一个在后，而我们知道编译器只会向上查找，所以不管谁定义在前面都不可避免，解决这个问题需要前置声明。

两种情况我们都有了应对之策，接下来就着手重载++。如果当前桶还没有走完，就返回下一个节点的迭代器；如果当前桶走完了，先通过迭代器指向的节点确定当前桶在哈希表中的映射位置，然后向后走找第一个不为空的桶，第一个不为空的桶的头节点就是我们要找的节点。
这里还需要处理一个特殊情况，就是后面的桶都为空，此时迭代器++得到end()。

Self& operator++()
{
//当前桶不为空
if (_node->_next)
{
_node = _node->_next;
}
else//当前桶已空
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(kot(_node->data)) % _pht->_tables.size();
++hashi;
while (hashi < _pht->_tables.size())
{
if (_pht->_tables[hashi])
{
break;
}
++hashi;
}
if (hashi == _pht->_tables.size())
{
_node = nullptr;
}
else
{
_node = _pht->_tables[hashi];
}
}
return *this;
}

如果你用上面的代码去测试会发现还是跑不通，哪里又有问题呢？通过报错不难发现，问题出现在哈希表中的 _tables是一个私有成员，在哈希表外是不能直接访问的，解决这个问题也简单，只需要将迭代器作为哈希表的友元类即可。

友元的类模版声明时需要带上模版参数。

2.2 begin、end

返回哈希表的起始迭代器，只需要遍历哈希表找到哈希表的第一个不为空的桶，桶中的头节点的迭代器就是哈希表的起始迭代器。如果哈希表中没有数据就不需要遍历哈希表了。end迭代器我们还是用nullptr构造。
构造迭代器除了传节点指针外，还需要传哈希表的指针，那哈希表的指针怎么传呢？没错，在哈希表中this就是哈希表的指针。

Iterator Begin()
{
if (_n == 0)
{
return End();
}
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
if (pcur)
{
return Iterator(pcur, this);
}
}
return End();
}

Iterator End()
{
return Iterator(nullptr, this);
}

2.3 const迭代器

const迭代器还是和红黑树的封装一样，增加两个模版参数来实现对普通迭代器类的复用。

template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;

HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* pht)
:_node(node)
,_pht(pht)
{}

//...
}

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

typedef HashNode<T> Node;
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;

//...

ConstIterator Begin() const
{
if (_n == 0)
{
return End();
}
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
if (pcur)
{
return ConstIterator(pcur, this);
}
}
return End();
}

ConstIterator End() const
{
return ConstIterator(nullptr, this);
}

private:
vector<Node*> _tables;
size_t _n = 0;
};

const迭代器完成后我们用下面的函数测试一下：

void Print(const unordered_set<int>& s)
{
unordered_set<int>::const_iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}

编译运行还是有问题，原因是上面的begin返回的是const迭代器，其函数内部的成员都是const成员，包括哈希表，所以其this指针也应该是被const修饰的，但是我们实现的迭代器的构造函数形参中哈希表的指针并没有const修饰，有权限放大的错误。具体如下图所示：

在这里插入图片描述

因此下面这两个地方都需要const修饰才行。

在这里插入图片描述

和set、map一样，unordered_set、unordered_map的key同样不能修改，这里也可以仿照set和map的封装一样给单独K加上const修饰就行。

2.4 unordered_map中[]重载

map中的[]重载是复用的insert函数，主要是利用其返回值，unordered_map也不例外。迭代器实现的差不多后我们将Find、Insert等函数的返回值就可以完善了。

pair<Iterator, bool> Insert(const T& data)
{
KeyOfT kot;
if (Find(kot(data)) != End())
{
return make_pair(Find(kot(data)), false);
}
Hash hs;
size_t hashi = hs(kot(data)) % _tables.size();

//负载因子==1就扩容
if (_n == _tables.size())
{
vector<Node*> newtables(2 * _tables.size(), nullptr);
for (int i = 0; i < _tables.size(); i++)
{
Node* pcur = _tables[i];
while (pcur)
{
Node* next = pcur->_next;//记录下一个节点
size_t hashi = hs(kot(pcur->_data)) % newtables.size();//映射新表的相对位置
pcur->_next = newtables[hashi];//头插
newtables[hashi] = pcur;
pcur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
Node* newnode = new Node(data);

//头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return make_pair(Iterator(newnode, this), true);
}

Iterator Find(const K& key)
{
KeyOfT kot;
Hash hs;
size_t hashi = hs(key) % _tables.size();
Node* pcur = _tables[hashi];
while (pcur)
{
if (key == kot(pcur->_data))
{
return Iterator(pcur, this);
}
pcur = pcur->_next;
}
return End();
}

最后重载[]，[]的调用等价于：

（*（（this->insert（make_pair（k，mapped_type（））））.first））.second

key存在，返回对应的value；key不存在，插入key和value（默认）。
所以我们可以复用insert函数插入新元素，然后不管是否插入成功都返回迭代器的second。

V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}

3、特殊类型

其实上面我们只考虑了整型、浮点型、字符串等做key的情况，如果key是一个特殊类型，比如我们熟悉的日期类，则上面的取模操作还是有问题的，并且还不是再实现一个仿函数的问题，而是我们的包装有问题。

在这里插入图片描述

问题就出现在这里，小伙伴们可以思考一下我们能在这里给缺省值吗？
是不可以的，因为我们现在是在实现封装，因此不可能越过unordered_set和unordered_map去直接操作哈希表，那在这里给缺省值就写死了，当遇到日期类这种特殊类型时我们需要自己实现相应的仿函数来支持取模，而我们在哈希表内部实现了无符号整型的强转和字符串的整形变化是因为它们都是非常常见的。

在这里插入图片描述

我们应该在unordered_set和unordered_map的层面加仿函数的缺省值，这样如果遇到日期类这种特殊类型的需求，我们就可以按需传仿函数完成整型的转换。

另外为了防止像1月2号和2月1号这种产生冲突的情况，可以仿照字符串哈希函数的处理方法，给年月日乘以31这样的特殊数字来减少冲突。

在这里插入图片描述

总结

unordered_set和unordered_map的封装相较于set和map的封装还是相对较复杂的，其中复杂之处主要在于模版参数间的对应关系，如果某处做修改一般都会牵扯到多个地方，因此封装时必须时刻清晰各个板块之间的依赖关系。
一些不支持修改也就是const修饰的地方，往往还存在着权限放大的问题，也要时刻小心。

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

原文地址：https://blog.csdn.net/2301_78843337/article/details/142966793

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：《Spring Boot 应用开发研究》
下一篇：通过比较list与vector在简单模拟实现时的不同进一步理解STL的底层

为何选择 C++：深入剖析其优势与适用场景
例如，在一个企业级应用开发中，可以通过类的设计来构建不同的业务模块，每个模块之间通过清晰的接口进行交互，当业务需求发生变化时，只需要对相应的模块进行修改，而不会影响整个系统的稳定性。许多底层的硬件驱动
阅读更多2024-10-19
Python代码的静态分析工具-Pylint
此外，Pylint还能够识别一些常见的安全问题，并将它们归类为CWE（Common Weakness Enumeration），提醒开发者潜在的安全隐患。Pylint利用多种静态代码分析技术检查Pyt
阅读更多2024-10-19
Redis中String类型常见的应用场景
主要介绍了使⽤ Redis 的字符串数据类型可以使⽤的几个场景
阅读更多2024-10-19
LeetCode题练习与总结：二维区域和检索 - 矩阵不可变--304
本文详细介绍了如何使用前缀和矩阵解决二维矩阵子矩形范围内元素总和的计算问题，包括解题思路、具体代码实现以及时间复杂度和空间复杂度分析，为高效处理此类问题提供了有效方法。
阅读更多2024-10-19
Vue 3为什么移除过滤器功能以及替代方案（如何使用计算属性代替过滤器、讨论使用过滤器的最佳实践、如何在Vue 3中实现类似过滤器的功能）
在Vue 2中，过滤器（`filter`）常用于模板中对数据进行简单的格式化处理。然而，在Vue 3中，过滤器被移除了。本文将探讨Vue 3中去掉过滤器的原因，并讨论如何使用计算属性等方式替代过滤器功
阅读更多2024-10-19
013_django基于大数据的高血压人群分析系统2024_dcb7986h_055
博主介绍：CodeMentor毕业设计领航者、全网关注者30W+群落，InfoQ特邀专栏作家、技术博客领航者、InfoQ新星培育计划导师、Web开发领域杰出贡献者，博客领航之星、开发者头条/腾讯云/A
阅读更多2024-10-19
JavaSE之String类
字符串String类的一些常用方法，StringBuilder和StringBuffer的用法及区别
阅读更多2024-10-19
基于langchain.js快速搭建AI-Agent
如何基于langchain，快速搭建属于自己的AI智能体
阅读更多2024-10-19
G1 GAN生成MNIST手写数字图像
生成对抗网络 (GAN) 是一种通过“对抗性”学习生成数据的深度学习模型，通常用于生成图像、视频等数据。生成器 (Generator)：用于生成假的数据样本，试图让判别器无法分辨其为假的。判别器 (D
阅读更多2024-10-19
centos 安装达梦数据库
2.1、下载的压缩包(dm8_20240712_x86_rh7_64.zip)上传到服务器。2.9、数据库使用（默认账户/密码：SYSDBA/SYSDBA）2.5、安装完成，通过脚本进行配置(切换到r
阅读更多2024-10-19

【C++】unordered_set、unordered_map超详细封装过程，处理底层细节

目录

前言

1、数据泛型

2、迭代器

2.1 ++重载

2.2 begin、end

2.3 const迭代器

2.4 unordered_map中[]重载

3、特殊类型

总结

相关文章