C++·set与map容器(上)
我们可能听到过这样两个概念：序列式容器、关联式容器。其中，序列式容器就是像 vector、list 这种数据在逻辑上是连续存在的容器，而关联式容器的数据之间是有很强关联性的，其位置是不能随意更改的，就比如我们本节要学习的set与map
1. 树形结构的关联式容器
根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树形结构与哈希结构。树形结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器都是用平衡搜索树，即红黑树作为其底层结果，multi型的容器比非multi型的多了一个可以存储相同元素的功能。
2. set容器 与 multiset容器
2.1 set容器
官网资料：set - C++ Reference
set 是一个基于红黑树写的一个K模型，也就是说key和value是同一个值。
首先我们可以看到set容器的模板参数只有一个需要我们填的，就是存储元素的类型，第二给模板参数是仿函数，第三个是空间配置器，后两个一般都不需要我们操作，可能作为排序方法的仿函数有时需要我们自定义一下。
说到排序，其实我们上节搜索二叉树的时候就有提到过，这个排序并不是容器的任务，而是附带的一种效果，中序时产生出来的效果就是有序的。set有两个效果：去重+排序，而multiset因为允许键值冗余，就是关键值可重复的意思，他只有排序一个效果。
它的构造函数默认构造，迭代区间构造和拷贝构造，其中默认构造和迭代区间构造我们都可以通过控制第二个模板参数来确定中序遍历时的排序效果是升序(less)，还是降序(greater)。
2.1.1 迭代器
这些迭代器我们都见过，也都知道怎么用，这里唯一要提醒的就是他这个迭代器 begin() 是从最左下值开始启动的，然后顺序成长到最右下值
就是说它的底层我们知道是从根开始中序遍历的，但是上层表现出来的效果就是一个去重+排序的效果。
2.1.2 内容更改操作
swap交换两容器的内容，clear清空容器，emplace系列我们不看
2.1.2.1 insert
官网资料:set::insert - C++ Reference
第二种插入没啥用，我们就用第一个和第三个，直接插入键值，或者用迭代区间选择一段键值插入。
返回值也是一种pair，第一个成员变量是插入位置的迭代器，如果插入失败就返回失败位置的迭代器，也就是该键值所在位置，第二个成员变量是个bool值用来标注是否插入成功
2.1.2.2 erase
官网资料：set::erase - C++ Reference
这个可以用迭代器指定删除，迭代区间删除，还可以指定数据删除。如果指定数据删除的话会返回一个无符号整形代表删除了几个数据，这个可以用来判断有没有删除数据，或者在multiset中得知删除了几个数据，因为multiset允许多个重复数据存在的嘛。
可以看到即使没有成功删除数据它也不会有什么跳脸报错，还是很温柔的。
2.1.3 其他操作
2.1.3.1 find
官网资料：set::find - C++ Reference
这个就是你给find一个数据，然后它能返回数据所在位置的迭代器，如果是multiset容器的话就返回要查找的那些数据中最左下角的数据的迭代器。
库函数中还有一个find，不过那个find的逻辑就是暴力遍历迭代器，其效果为O(N)，远低于我们这个set内置find O(logN) 的查找效果
2.1.3.2 count
官网资料：set::count - C++ Reference
你给定一个参数，count返回容器中这个参数的个数，在set中它没有太多计数的作用，顶多用它返回值是1还是0判断一下有没有这个参数。
只有在multiset中才有计数的效果，记这个参数出现了多少次。
2.1.3.3 lower_bound 与 upper_bound
看名字就能看出来，下边界和上边界。
lower_bound返回第一个 大于等于val 的数据的迭代器；upper_bound返回第一个大于val的数据的迭代器，为什么是大于？因为这个边界是用来画迭代区间的，而迭代区间要求左闭右开，这样就可以删掉upper_bound中指定的参数。
可以看到把3至6的所有内容都删掉了。
2.2 multiset 容器
multiset容器和set容器的所有接口都是一致的，不同的是multiset容器可以存储相同键值也就是允许键值冗余，也就是说它的效果只有排序没有去重了。但是我们不要忘记本节的所有容器都是为搜索服务的。
可以看到multiset相比set容器多出的允许键值冗余的效果。
因为这两个容器的接口是完全一致的因此我们就不赘述了，就把几个有点区别的接口说一下。
1. find
返回中序遍历出的第一个要查找的值，也就是该值中最左下角的值的迭代器
这么返回的好处很大，就比如count就可以复用find然后自增迭代器就可以实现计数的功能了
2. erase
删除所有相同元素
3. equal_range
官网资料：multiset::equal_range - C++ Reference
返回一个左闭右开的迭代区间，用来框选出给定键值的出现范围
3. map容器 与 multimap容器
3.1 map容器
官网资料：map - C++ Reference
可以从这里看到map容器中比set多存了一个T这也就是我们之前说的value只是叫法不一样而已。
key值用来排序，并且映射到T值上形成一对相关联的数据，因此map在插入数据的时候是将这两个值合并成一个叫pair的结构体进行统一操作。
官网资料：pair - C++ Reference
pair结构体内部大致类似于这样
实际应用中我们只需要记住它有两个公有成员变量，first和second，我们可以让first存key至，让second存T(value)值
map的构造情况和set相同，都是只支持无参构造，迭代范围构造和拷贝构造，C++11还支持了一个initializer list构造。因为C++11之后有一个一切构造或者赋值都可用 { } 的宗旨，因此我们可以看到所有内置类型或者容器都可以用 { } 进行初始化。
3.1.1 insert
官网资料：map::insert - C++ Reference
我们可以看到插入的参数类型是value_type而这个类型就是typedef后的pair，也就是说插入传参时要用pair类型变量。
传pair类型变量我们有四种方案：1.构造一个有名pair对象传参，2.直接传匿名pair对象，3.使用 make_pair 函数传参，4.使用多参数隐式类型转换传参。
make_pair函数就是你给它两个元素，然后它就能帮你把这两个元素合成为一个pair元素。
官网资料：make_pair - C++ Reference
在插入的时候更推荐后两个插入方式。
3.1.2 遍历与容器内容输出
遍历这里选择用 initializer list 构造dict 但是实在是太长了就不都截下来了。
我们手写迭代器遍历，但是it的类型名过长了，因此我们可以选择用auto来作为it的类型名。
因为pair变量并没有进行流插入流提取的操作符，因此我们只能选择一个成员变量一个成员变量的打印。
我们还可以选择使用范围for，进行遍历打印。
但是要注意e的类型不能是简单的auto了，因为dict的迭代器解引用，相当于 *it 给到 e，但是*it 里面还有一个pair结构体，这个东西给到e的时候是要深拷贝的，因此我们选择引用接收避免深拷贝消耗。
3.1.3 operator[ ]
官网资料：https://legacy.cplusplus.com/reference/map/map/operator[]/
operator[ ] 当树中没有这个key值k的话就插入一个pair，其中的value使用默认构造，返回这个value的引用供用户设定value。如果树中有这个key值k的话就返回key值对应value的引用供用户修改。
也就是说使用operator[ ] 时，如果没有这个要查找的key值就会插入，有key值就相当于查找。因此使用时要谨慎，不要把不想插入的东西插入进去了。
3.2 multimap
multimap允许键值冗余。
但是取消了operator[ ]，其他接口保持一致
原文地址：https://blog.csdn.net/atlanteep/article/details/140549004
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！