【C++】使用哈希表模拟实现STL中的unordered_set和unordered_map_unorderset 插入

前言

前面的文章我们学习了unordered_set和unordered_map的使用以及哈希表，并且我们提到了unordered_set和unordered_map的底层结构其实就是哈希表。
那这篇文章我们就对之前我们实现的哈希表（拉链法实现的那个）进行一个改造，并用它模拟实现一下unordered_set和unordered_map。

那在模拟实现之前要声明一下：

我们这里的模拟实现里面所做的操作和前面红黑树模拟实现mapset基本上是一样的，增加和改造的那些模板参数的意义基本都是一样的。
所以这里有些地方我们就不会特别清楚的去说明了，如果某些地方大家看的不能太明白，建议先搞懂这篇文章——使用红黑树模拟实现STL中的map与set
这里面我们是讲的比较清楚的。

一.哈希表模板改造+封装unordered_set和unordered_map

首先可以带大家再来简单看一下库里面的哈希表的源码：

我们来看一下这几个模板参数
第一个value就决定了哈希表里面每个data里面存的数据类型，第二个参数key就是用来获取单独的键值key，因为unordered_map进行查找这些操作的时候是用key进行散列的，需要比较的话也是用key，但他里面存的是pair。
第三个这个HashFcn就是接收一个仿函数，用来将比如字符串这些类型转换为整型的。
第四个的作用就和红黑树封装那里的KeyOfT一样，用来提取key的。
那我们先看这么多。

接下来我们对我们的拉链法的哈希表进行一些改造，因为我们当时是按照KV模型实现的，而现在要变成通用的。

1. 哈希表结构修改

首先结点的结构要改一下：

这样对于unordered_setT就是单独一个key，对于unordered_map就是一个pair。

然后哈希表的结构：

之前Node里面是KV，现在由T决定结点里面存什么
那下面相关的地方都要改一下

那大家看这个地方是不是就需要使用keyOfT那个仿函数了
因为data有可能是单独一个key，也有可能是一个pair，而像查找这些地方要使用Key去查找。
增加一个模板参数

2. unordered_set和unordered_map增加KeyOfT仿函数

然后我们把unordered_set/map能写的先写一写：

3. insert封装及测试

那我们先把insert搞一下，然后测试一下

unordered_map

测试一下：

unordered_set的插入

没问题

然后，unordered_map的插入

没问题。

4. 哈希表迭代器的实现

接着我们来实现一下哈希表的迭代器

我们来思考一下它的迭代器应该怎么搞：

那按照我们以往的经验，它的迭代器应该还是对结点指针的封装，然后顺着每个不为空的哈希桶（链表）进行遍历就行了。
那大家思考一下：

比如现在底层的哈希表是这样的，it在2这个结点的位置。
那++it怎么走？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/849579