C++笔记-set和map的使用(包含multiset和multimap的讲解)

1.序列式容器和关联式容器

前面我们已经接触过STL中的部分容器如:string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
本章节讲解的map和set底层是红黑树，红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构， map是key/value搜索场景的结构。

1.set系列的使用

1.1set的介绍

set就是我们上篇所实现的二叉搜索树的key搜索场景，它默认就是不存在重复数据的二叉搜索树，尔汗有重复数据的就是后面要讲的mutiset。

从上图可以看出，set的模板参数中含有三个不同的类型，第一个想必大家都知道，就是里面存储数据的类型。

第二个我们之前也讲过，就是仿函数，可以控制数据的输出顺序。

第三个是内存池，这部分知识我们还没有了解，这里就先跳过。

从以上图片可以看出，和我们之前所学的其它容器还是比较相似的，使用起来也非常相似：

这里可以看到set自动就对所传入的数据进行去重，并且按照升序排序的方式，而我们如果想让其输出的方式是从大到小，也可以利用仿函数：

并且我们是不能修改set中的值：

不能修改的原因呢我们上一篇已经讲过，会破坏二叉搜索树的结构，如果能修改那么二叉搜索树就失去了意义。

下面来讲解set中一些接口的使用方法。

1.2find

set中的find接口通过传入的值进行查找，如果找到了就返回相应的迭代器，也就是对应数据的位置，如果没有找到，就返回end()迭代器。

这里我们通过find接口来找5这个数据，结果显示找到了，说明此时返回的迭代器并不是end()。

而如果我们来找1这个数据，结果并没有找到，说明此时find返回的就是end()。

1.3erase

erase和我们之前所学容器的erase有些不一样，从上图对set的介绍可以看出，除了我们常见的void返回值以外，还有个size_type做返回值的。

而在set中这个size_type就是0或者1，删除成功返回1，删除失败就返回0，而这样设计的原因是为了和mutiset相照应。

可以看出此时的返回值时1，说明删除成功，我们通过再次打印出set中的数据也可以看到2已经被删除。

这里我们要删除1，发现删除失败，此时erase的返回值就为0。

1.4count

count接口就是来查找某个数据有几个，而在set中我们知道数据要么没有，要么只有一个，所以在set中count主要用来判断传入的数据在不在。

count的返回值依旧是1或者0，我们可以利用count的这个功能来写一种题型：

比如就像力扣上的这种题，我们就可以利用set来解决会更加的简单：

因为一个数组中蛊蛾可能会有重复的数据，所以利用set的去重特性以及count判断数据在不在，这道题写起来就极为简单。

1.5low_bound和upper_bound

low_bound的作用是对于所传入的数据找出set中大于等于这个数据的第一个值的位置，所以返回值也是迭代器。

upper_bound的作用是对于所传入的数据找出set中大于这个数据的第一个值的位置。

两者的区别就是一个是>=，一个是>。

那么这两个功能有什么用呢？

这两个配合着erase接口就可以实现删除set中的某段内容，就如上面的例子所示，>=30的第一个数就是30，而>70的第一个数就是80，但是为什么没有删除80呢？
因为在c++中的删除范围都是左闭右开，在这里就是[30，80)，所以删除的就是30到70这几个数据，当然我们也可以改一下数据再看看到底是不是这样：

可以看出，这里我传的并不是set中的数据，和上面一样>=25的第一个数就是30，>75的第一个数是80，所以结果是一样的。

2.multiset

multiset和set差不多，无非就是一个不去重，一个去重。从上图也可以看出，mutiset和set接口都一模一样，我们下面来看一下mutiset的基本使用：

可以看出multiset并没有去重，并且和set一样都是升序排列。

当然。multiset和set的区别并不是只有这一点，在某些接口中也有细微的差别。

2.1find

find呢，在multiset返回的是某个数据在中序中的第一个位置，何为在中序中的第一个位置呢？

就如上面所查找的4，中序中的第一个4就是最左的那个位置，从上面找到后继续查找4也可以看出找的就是第一个位置，所以才能将后面的4都打印出来。

2.3erase

此时在multiset中erase返回就不只是0或1了，所以上面的set中的erase返回值也是size_type，就是为了和multiset相照应，而是返回这个数据有几个被删掉了。

当然，如果只想删除一个，我们就要指定对应的位置进行删除，比如：

这里我们利用find找到了第一个4所在的位置，并将其传给erase，这样就可以只删除一个4。

2.4count

在multiset中count就真正变为统计每个数有几个，这里可以看出统计了4，2，6的数量。

3.map

3.1map的介绍

map就是我们之前讲的key/value搜索场景，在map的解释中呢我们可以看到有一个pair的模板，这个pair是什么呢？

pair其实是一个结构体，里面保存着key和value，那么可能有人会有疑惑：为什么不和我们上一篇所讲的放在一块呢？

因为我们要对map的迭代器进行解引用啊，如果放在一起，解引用能解出来两个值吗？

显然是不行的，所以就没有放在一块，它多写个结构体就是这样：

就是把之前的key和val更换为pair，就是多加了一步。

而我们使用insert赋值时最简单的方法就是利用隐式类型转换，另外注意我们在打印出key和val时是上述的方式来打印，利用迭代器也是一样：

当然，也可以用下面这种方式：

这也是我们之前讲的->符号重载。

我们是无法直接对迭代器进行解引用，为什么呢？
因为底层的pair并没有重载流插入<<和流提取>>，所以我们是不能直接对迭代器直接接引用进行使用。

3.2[]符号重载

看到这个接口，可能有人会有疑惑：[]符号不是底层是数组才会用[]来进行下标访问吗？

是的，不过map的[]并不是用来进行下标访问的，而是另有用处：

通过看[]符号重载的基本格式我们可以看出，[]符号传入的值是key，而返回的值却是value，而要理解[]符号重载的原理我们先看一个例子：

比如我们要插入上述的几种水果并统计它们的次数，按照正常的逻辑我们应该用上面的代码来写对吧，但是我们再看：

而当我们利用[]来写时，一行代码就搞定了，有人会有疑惑：为什么这么写就和前面是一样的效果呢？

其实原理就和前面的代码是一样的，其实[]符号重载就是利用insert接口来实现的，大家可以设想一下，我来查找这个数据返回的是它的second，如果有的情况下++即可，但是没有的话怎么办？

那肯定得先插入这个数据对吧，所以才要利用insert来实现，那现在我们再看insert接口：

我们来看insert的第一种方式，这里也有一个pair，并且和我们上面讲的pair参数并不一样，确实是这样的，大家不要将两者混为一谈，这是两个不同pair。

而第二张图呢就是对这个pair的解释，意思是：根据你传入的key，第一个参数iterator指向的是新插入的数据的位置或者是已经在map中存在的数据的位置，而第二个参数bool在是插入新的数据时默认是true，而如果要插入的数据已经存在，那么就是false。

也就是说，不管你传入的key是否存在，pair中的第一个参数iterator都会获得一个位置，这也是[]符号重载能实现的关键。

现在我们大概来看看[]符号重载是怎么实现的：

大概就是这么个逻辑，这里要注意insert的第二个参数我们可以传匿名对象，这样就会去调用相应的默认构造函数，比如：int就会默认是0等。

而当我们通过第一段代码得到pair时，我们就可以访问其中的第一个参数iterator得到对应的位置，而第二段代码中的ret.first就是iterator，再通过->来访问结构体中的second，也就是水果的次数。

通过[]符号重载，我们既实现了插入新的数据，又能统计每个水果出现的次数。

基于[]的这个特性，我们还可以这样写：

再插入数据时我们可以不直接调用insert接口，而是利用[]符号重载来实现。

4.multimap

multimap和map也是几乎没什么区别，和上面的set/multiset情况是一样的，multimap可以插入重复的数据。

并且我们可以看到multimap是没有[]符号重载的，没有的原因大家想想都应该清楚，如果支持的话并且其中有重复值，那么我该返回哪个的second呢？

multimap剩下的接口和map是一模一样的，这里我再讲一个接口：equal_range

equal_range这个接口的功能就是返回key值相等的一段区间，从它的返回值也可以看出也是pair，第一个参数就是起始位置的iterator，第二个参数就是最后一个位置的下一个位置的iterator，因为是左闭右开嘛。

这就是equal_range的基本应用场景，而在map中这个方法显然只能返回一个元素。

这个接口包括multimap用的都不多，了解一下即可。

以上就是set和map的使用的内容。