【C++进阶】用哈希表封装unordered_set和unordered

【C++进阶】用哈希表封装unordered_set和unordered_map

在这里插入图片描述

👦个人主页：@Weraphael
✍🏻作者简介：目前学习C++和算法
✈️专栏：C++航路
🐋 希望大家多多支持，咱一起进步！😁
如果文章对你有帮助的话
欢迎评论💬 点赞👍🏻 收藏 📂 加关注✨

一、改造哈希表

1.1 解决 k/v 参数冲突问题

在模拟实现map和set时，我们知道set是<K,K>模型的红黑树，map是<K，pair>模型的红黑树，而真正决定树里存储什么，是由第二个模板参数决定的，这也就是为什么map和set可以共用一颗树。

unordered系列容器也是如此，其中unordered_set是<K,K>模型的哈希表，unordered_map是<K，pair>模型的哈希表

【Unordered_set.h】

在这里插入图片描述

【Unordered_map.h】

在这里插入图片描述

由于unordered系列的底层使用的也是同一个哈希表，因此，真正决定表里存储什么，也是依靠第二个模板参数决定。

【OpenHashTable.h】

在这里插入图片描述

1.2 插入操作的改造

首先我们来分析插入的模板参数应该是什么？对于unordered_set就是key；对于unordered_map则是pair。那么参数类型应该用第二个模板参数V接收。

在这里插入图片描述

但这里就遇到了一个尴尬的问题：对于unordered_map来说，kv.first就是key；而对于set来说，kv就是key。

因此，解决方法和map/set一样：写一个仿函数。首先在unordered_map和unordered_set里面写两个内部类，这个内部类重载运算符()。对于unordered_map返回pair的first，对于unordered_set返回它本身，也就是key。

【Unordered_set.h】

在这里插入图片描述

【Unordered_map.h】

在这里插入图片描述

这下就可以对哈希表进行改造了

【OpenHashTable.h】

在这里插入图片描述

1.3 查找操作的改造

在这里插入图片描述

1.4 删除操作的改造

在这里插入图片描述

二、迭代器

2.1 封装正向迭代器

哈希表的正向迭代器和链表类似，实际上就是对哈希结点指针进行了封装。

在这里插入图片描述

但是由于在实现++运算符重载时，可能在当前坑位就有非空结点，那么_node = _node->_next来遍历下一个非空结点，也有可能下一个就是空结点了，因此就需要在哈希表中去寻找下一个非空坑位，因此每一个正向迭代器中还都应该存储哈希表的地址（指针）来帮助我们判断表中的下一个坑位是否为空。

在这里插入图片描述

然后再在迭代器类__HTIterator中实现operator!=、operator*、operator->，那么遍历操作就已经完成一半了

在这里插入图片描述

接着在类HashTable中封装begin()和end()

在这里插入图片描述

最后分别在Unordered_map.h和Unordered_set.h中调用begin()和end()

【Unordered_map.h】

在这里插入图片描述

【Unordered_set.h】

在这里插入图片描述

当运行时发现编译不通过！！

在这里插入图片描述

这里其实存在相互依赖的问题，也就是说这里存在相互使用

在这里插入图片描述

什么意思呢？假设是unordered_set使用哈希表迭代器，那么迭代器的定义要在哈希表之前，因为代码会向上搜索；而又因为迭代器类要用到哈希表，而代码向上搜索时没发现哈希表的定义，因此在迭代器类中typedef HashTable<K, V, GetKey, HashFunc> HashPtr其实是未定义的。

解决方式：在迭代器类前声明哈希表即可。但是要注意声明格式：参数列表 + class类名

在这里插入图片描述

接下来运行看看结果：

在这里插入图片描述

可是又报错了，原因是在__HTIterator中，访问了类HashTable的私有成员_table（类外不允许访问私有成员）
在这里插入图片描述

解决方法：友元声明。迭代器是哈希表的友元

在这里插入图片描述

【测试结果】

在这里插入图片描述

这里我们对unordered_map遍历使用范围for，因为范围for的底层就是迭代器

在这里插入图片描述

2.2 const迭代器

但是以上代码还是不完美，不管是unordered_set和unordered_map，都可以修改key，一旦修改了，那么就意味着这表已经乱了。

回想一下当时模拟实现map/set：

在这里插入图片描述

因此，unordered系列也可以模仿以上操作：对迭代器类增加两个模板参数来控制迭代器的operator*和operator->的返回值

首先修改迭代器类在哈希表的声明，并增加const版本的begin和end接口供unordered系列容器调用：

在这里插入图片描述

当然了，咱们自定义类型的迭代器也得修改

在这里插入图片描述

【Unordered_Set.h】

在这里插入图片描述

先来简单测试一下：

在这里插入图片描述

接下来再来测试const迭代器遍历

在这里插入图片描述

通过排查，是哈希表封装的begin和end出问题了

在这里插入图片描述

原因如下：

在这里插入图片描述

解决办法很简单，由于迭代器不会修改哈希表的内容，因此对哈希表指针用const修饰

在这里插入图片描述

【Unordered_Map.h】

在这里插入图片描述

2.3 unordered_map 新增 operator[]

在这里插入图片描述

operator[]原理是：通过调用insert来查找键值key来返回实值value的引用。

如果键值key已经在表里，那么就返回表里面key所在结点的迭代器
如果键值key不在表里，那么就返回新插入key所在结点的迭代器

所以还得将insert的返回值再进一步完善

在这里插入图片描述

【OpenHashTable.h】

首先由于insert操作中有用到Find函数，因此要Find函数的返回值改为迭代器

在这里插入图片描述

接下来可以修改insert的返回值了

在这里插入图片描述

接着再重新修改unordered_map和unordered_set封装insert的返回值

【Unordered_map.h】

在这里插入图片描述

【Unordered_set.h】

在这里插入图片描述

当编译的时候发现还是不通过

在这里插入图片描述

这是当时我们封装map和set一样的问题：_ht是一个普通对象，去调用哈希表的insert，那么返回的是普通的迭代器；而在unordered_set中，迭代器都是const迭代器。

就这么说吧，以上代码在编译器眼中其实是这样的：

在这里插入图片描述

又由于pair是一个类模板，类模板实例化不同的模板参数就是不同的类型。例如定义vector<int> vi，vector<char> vc，将vc赋值给vi成立吗？显然不可能！

在这里插入图片描述

那么如何解决呢？可以想想不同类型的内置类型是如何相互转化的？

在这里插入图片描述
因此，可以对迭代器类写一个拷贝构造函数：将普通迭代器构造成const迭代器

这种list容器其实也有一样的玩法：

在这里插入图片描述

如上代码，普通对象l调用begin返回普通迭代器，然后再赋值普通迭代器合情合理，但是也可以赋值给const迭代器，按常理普通迭代器赋值给const迭代器是不允许的！如果允许将普通迭代器赋值给常量迭代器，那么就可能导致通过常量迭代器意外地修改数据，违反了常量迭代器的设计初衷。

因此，我们可以简单看看list的底层：

在这里插入图片描述

也就是说：list底层有一个拷贝构造函数，支持普通迭代器转化为const迭代器。

理论部分解释完了，那么现在就对__HTIterator类添加一个拷贝构造函数

【OpenHashTable.h】

在这里插入图片描述

如果__HTIterator实例化成普通迭代器，重命名的iterator永远是一个普通迭代器，那么这个拷贝构造函数其实就是一个赋值。
如果__HTIterator实例化成const迭代器，重命名的iterator永远是一个普通迭代器，那么iterator对象就会隐式转化为__HTIterator类型，也就实现了普通迭代器转化为const迭代器

自此，unordered_set最终insert接口如下：

在这里插入图片描述

解释：第一行_ht调用哈希表中的insert返回的是普通迭代器；第二行再通过pair的构造，对于first和second成员变量都会走初始化列表初始化，而这里的first恰好是一个自定义类型，那么自定义类型在初始化列表初始化必须调用它的构造函数，因此就可以实现普通迭代器转化为const迭代器。

最后就可以在unordered_map封装operator[]

在这里插入图片描述