Learning C++ No.25【开散列封装unordered_set和unordered

这篇具有很好参考价值的文章主要介绍了Learning C++ No.25【开散列封装unordered_set和unordered_map】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

引言：

北京时间：2023/5/29/7:05，上星期更文一篇，且该篇博客在周三就写完了，所以充分体现，咱这个星期摆烂充分，哈哈哈！现在的内心情感没有以前那么从容了，这次摆的时间是有点久了，但本质影响不大，因为我现在还在码字，三天不学习，或者说是没有踏实学习，目前给我的感觉很难受，就像是好久好久没有学习过一样，感觉三天前学的东西，已经忘的差不多了，但，不慌，因为我们有写博客进行总结，可以让我们第一时间将相关知识回顾，所以这也是写博客最大的好处之一，并且在这三天的摆烂中，不是连续性的，而是间断性，可能这个间断性，也是我摆烂的重要原因之一，并且摆烂的过程还是那么朴实无华，王者荣耀，快4个月没玩，一开始玩的不怎样，后来手感越来越好，逐渐疯狂，一路连胜，把把c，这也可能就是为什么能持续摆烂的原因吧！So，简简单单，由于我们上篇博客的内容是哈希表的自我封装，所以该篇博客的内容就是unordered_set和unordered_map的封装 ，希望这不是我周末摆烂的开始，并且摆烂可以，但是一定需要在有一定的学习内容之后，充分反省，希望以后看到该篇博客的引言时，不是以今天这种较为落寞的情绪吧！

Learning C++ No.25【开散列封装unordered_set和unordered_map】

STL中有关unordered_set和unordered_map的知识

在上篇博客中，我们自己封装实现了哈希表，明白了许多有关哈希表的知识，如：哈希函数，哈希地址，哈希下标，哈希值等！那么哈希表有什么用呢？当我们谈到哈希表的用处之时，最好的回答方向就是从哈希表的优势出发，哈希表在查找和访问数据方面具有超高的效率（O(1)），就算是红黑树在查找方面也是远远不如，当然，不同的场景，红黑树和哈希表都各具风骚，否则肯定是一山不容二虎，其中一个早就被淘汰了，其中从之前我们使用红黑树封装set和map的博客中也能看出，红黑树在生活中的许多领域都应用广泛，所以人们特地的将红黑树进行了一定的封装，也就是set和map，同理，哈希表也被人们广泛使用，也被封装成了STL中的某种数据结构（关联式容器），也就是该篇博客的重点内容，unordered_set和unordered_map，所以接下来就让我们一起看看unordered_set和unordered_map的具体使用方法和自我封装吧！如下：

unordered_set和unordered_map的具体使用方法

unordered_set使用方法

unordered_set使用文档
通过文档我们可以看出，unordered_set和我们之前学习的set的使用方式是相同的，本质没有什么区别，所以这里我们不多做分析，具体直接看如下代码：
Learning C++ No.25【开散列封装unordered_set和unordered_map】
简简单单，同理就是插入、查找、删除这些基础接口和迭代器的使用，唯一值得注意的是：此时使用哈希表实现的unordered_set它不同于红黑树实现的set，一个是有序的，一个是无序的，当然，红黑树肯定是中序遍历有序的那一个，哈希表无序，且set是一个双向迭代器，而unordered_set是一个单向迭代器，具体为什么unordered_set设计成单向迭代器，而不设计成双向迭代器，原因如下：

对应数据在插入和删除的时候，可能会改变原哈希表中相关数据的链接关系，所以很难确保双向迭代器始终能够访问到对应的数据
因为哈希表中的数据是通过哈希地址控制，且哈希地址是通过哈希函数和对应的哈希值得到，所以哈希表中的数据都是随机无序存储，具有不可预测的性质
在哈希表结构中（开散列），数据之间是通过链式结构连接在一起的，所以我们可以直接通过对应的哈希地址去访问到对应的链表，再直接遍历链表，找到目标元素，而不需要按照固定的顺序去遍历整个哈希表，效率更高

unordered_map使用方法

unordered_map使用文档
多的不说，少的不唠，同理map使用方法，直接看代码，如下：
Learning C++ No.25【开散列封装unordered_set和unordered_map】
使用方法，同理map相关知识，且具体注意事项，在上述unordered_set已经强调，多了也没有，唯一值得注意的是和unordered_set最大的区别，也就是方括号运算符的使用，当然在map中方括号的实现和使用我们已经详细讲解过了，这里就不多加描述，接下来直接进入unordered_set和unordered_map的封装，如下代码所示：

unordered_set和unordered_map的封装

1.解决不同模型问题
第一点，同理红黑树实现set和map，还是数据类型问题，unordered_set和unordered_map也具有该方面的问题，如何使用同一份哈希表的代码同时实现unordered_set和unordered_map，类比红黑树实现set和map，这里依然使用泛型编程，当然也就是模板来解决该问题，基本原理就是将哈希表的哈希结点设计成一个模板类型，不管是unordered_set还是unordered_map，只要想要调用哈希表就需要把对应类型的模板参数传过来，所以这样我们就可以很好的解决Key模型和Key/Value模型使用同一份哈希代码的问题，具体代码如下：
Learning C++ No.25【开散列封装unordered_set和unordered_map】
如上图所示，总的来说，就是在使用unordered_set和unordered_map这两个模板类的时候，这两个模板类会去调用哈希表构造出一个对象，使用该对象去调用哈希表中的公共成员函数，并且此时传模板参数的时候，unordered_set传的是Key键，而unordered_map 传的是键值对pair结构体，并且注意：该pair结构中的数据也是模板类型，最后将模板参数传递给哈希表之后，哈希表在实例化的过程中，就会将对应的哈希结点给示例化成对应的数据类型，也就是你传Key，那么哈希结点就是Key类型，你传键值对，那么哈希结点就是键值对类型，这就是泛型编程的一大优点

2.解决泛型编程获取Key值问题
搞定了上述有关类型传参问题，此时我们正式开始封装，并且在红黑树中，我们对源码的写法已经有了教深的研究，此时我们就不再去看对应的源码了，因为本质都是换汤不换药，在红黑树封装set和map的博客中，我们已经将有关传模板参数导致不能确定类型的问题给解决了，也就是因为我们传的是模板参数，所以在编写红黑树代码的时候，不能使用具体的类型去访问数据，例：在进行比较大小的时候，unordered_set可以直接使用Key去比较大小，但是unordered_map却不行，因为unordered_map是一个键值对，是一个pair结构体，我们期望比较大小的方法是使用pair结构体中的Key去比较，而不是整个pair结构去比较，所以此时这个问题需要解决，解决的方法就是在unordered_set和unordered_map中构造一个内部类，该类实现一个仿函数，用于返回对应不同模型的Key值，最后再将该内部类作为一个模板参数传递到哈希表中，供给哈希表使用，哈希表再根据该模板参数取构造一个对象，使用该对象去调用对应的仿函数，最终利用仿函数获取到对应模型的Key值，如下代码所示：
Learning C++ No.25【开散列封装unordered_set和unordered_map】
如上图所示，通过上述文字和图示，应该可以很好的搞定该块知识点，本质就是想要获取到键值对pair结构体中的Key值而已，多了的没有，谁让我们想让unordered_set和unordered_map在一个桌子上吃饭呢？

3.解决存储数据类型的问题
OK，这个问题肯定是该篇博客的一个新知识点，虽然我们在哈希表实现的时候，已经详细的讲解过了，但是对于红黑树实现set和map来说，这个知识点是哈希表特有的，所以在此应该是属于新鲜货，值得我们重点讲解，同理哈希表中讲的，哈希表不是为了单单存储整形数据，而是希望可以存储任何类型的数据，无论是字符串类型还是自定义类型，所以为了解决这个问题，那么在进行哈希编码的时候，也就是使用哈希值进行哈希运算计算对应哈希地址的时候，我们需要将每种类型的数据都映射成一个整形数据，因为只有整形数据才可以符合哈希运算要求，但同理我们的数据类型使用的是模板类型，所以想要获取到这个数据类型映射出来的整形值，肯定不能在哈希表中获得，当然也不是在unordered_set或者unordered_map中获得，而是在我们调用unordered_set或者unordered_map进行传参时，通过一定的哈希函数实现获得，从而间接通过unordered_set和unordered_map
将该模板参数传递给哈希表，并且供给哈希表使用，让哈希表可以完成各种类型的哈希运算，从而在相应的哈希地址上存储各种类型的数据，如下图所示：
Learning C++ No.25【开散列封装unordered_set和unordered_map】

正式进入unordered_set和unordered_map的封装

搞定了上述有关泛型编程的知识，此时我们正式进入unordered_set和unordered_map的封装，本质没有什么太新奇的知识点，大致和set、map那块是类似的，也就是基础接口的封装和普通迭代器、const迭代器这些知识，并且基础接口的实现，就是去调用哈希表中对应的接口而已，所以不需要我们多讲，我们同样是把重点放在迭代器上，主要还是因为unordered_set的普通迭代器和const迭代器都是const迭代器，所以这块知识比较细化，需要我们琢磨一下

哈希表中迭代器相关知识

上篇博客，自我封装哈希表中，我们只实现了相关基础接口，并没有实现迭代器，所以因为此时unordered_set和unordered_map需要使用迭代器，此时我们就需要把哈希表的迭代器给实现，具体如下代码所示：
Learning C++ No.25【开散列封装unordered_set和unordered_map】
搞定了哈希表中有关迭代器的知识，此时我们就可以正式进入 unordered_set和 unordered_map的封装啦！如下：

unordered_set的封装

唯一值得注意的是，unordered_set的普通迭代器和const迭代器本质都是const迭代器，所以在实现迭代器时，一定需要格外小心，非常容易因为const导致出错，具体代码如下所示：
Learning C++ No.25【开散列封装unordered_set和unordered_map】

unordered_map的封装

同理，但不同的是此时unordered_map的普通迭代器就是普通迭代器，所以没什么需要特别注意的地方，如果有的话，那么就是键值对pair结构体中的Key值，我们要给成const类型，因为Key值坚决不允许被修改的，具体代码如下：
Learning C++ No.25【开散列封装unordered_set和unordered_map】文章来源地址https://www.toymoban.com/news/detail-465398.html