【C++】7000字介绍map容器和set容器的功能和使用
目录
前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家
点击跳转到网站
一、关联式容器和序列式容器
1、序列式容器：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。2、关联式容器：也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高
二、键值对<key, value>
通过key去找value用来表示具有一 一 对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一 一对应的关系，即通过该单词，在词典中就可以找到与其对应的中文含义。
三、树形结构的关联式容器
根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列（中序遍历）。
四、set容器（key模型）
1、文档官网
set - C++ Reference
2、功能介绍：
（1）、set是按照一定次序存储元素的容器（2）、在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。（3）、在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。（4）、 set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。（5）、set在底层是用二叉搜索树(红黑树)实现的。
3、注意事项：
（1）、与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放 value，但在底层实际存放的是由<value, value>构成的键值对。（2）、set中插入元素时，只需要插入value即可，不需要构造键值对。（3）、set中的元素不可以重复(因此可以使用set进行去重)。（4）、使用set的迭代器遍历set中的元素，可以得到有序序列（排序）（5）、set中的元素默认按照小于来比较（二叉搜索树的中序遍历）（6）、set中查找某个元素，时间复杂度为：【log_2 n】（7）、set中的元素不允许修改，因为底层是二叉搜索树，如果对元素进行修改，就可能不满足二叉搜索树的结构。（8）、set中的底层使用二叉搜索树(红黑树)来实现 （9）、头文件：<set>.
4、基本使用，更多接口可查看官网：
（1）、插入一组数字并用迭代器遍历。
我们需要先查看文档学习相关接口和函数的介绍。迭代器对于各大容器都是一回事，所以使用方法是相同的。
（2）、习惯用set进行排序和去重操作：
根据上面的描述可知，set是根据搜索二叉树的中序遍历进行插入的，所以可以对一组数进行排序，并且不会插入相同的数，所以可以达到去重的功能。
（3）、三种erase（删除）的区别：
set提供了三种删除
第一种是删除某个迭代器位置：如果存在就删除，如果不存则报错：
这里涉及一个find函数：find函数为查找某个数，并返回该位置，若没找到则返回end();
因为找不到会报错，所以需要用一个if语句进行判断，否则会如下：
第二种是删除某个val值，并返回删除的个数；
第三种是删除一个迭代器区间，左闭右开；
这里涉及两个操作：
lower_bound：返回大于等于k的位置
upper_bound：返回大于k的位置
利用上述两个函数得到一个左闭右开区间在进行删除。
假设我们删除区间[3，6]，因为erase的参数为左闭右开区间，所以我们需要得到区间
[3，7)，所以lower_bound可以得到左闭，upper_bound可以得到右开：
五、multiset容器（允许插入重复值）
1、文档官网：
multiset - C++ Reference
2、介绍：
（1）、multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。（2）、 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。（3）、在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。（4）、multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。（5）、 multiset底层结构为二叉搜索树(红黑树)。
3、基本使用：
multiset容器和set容器是类似的，最大的区别就是set不能存储重复的数据，而multiset容器可以存储重复的数据
3、因为可以插入重复值，所以有些接口也有所区别：
（1）、第二种删除方式的返回值：
上面我们知道第二种删除时有返回值的，返回的就是删除元素的个数，在set容器中，返回值无非就是0和1，实际使用在这里才能体现出来：
（2）、count函数：
该函数的作用为：返回val值在容器中的个数，在set中返回值也无非就是0和1，在multiset容器中才能更好使用。
（3）、find函数
set中的find函数作用为：查找val值，存在则返回该位置，不存在则返回end()；而mulitset容器可能存在多个重复值，所以功能会有所不同：mulitset容器中find函数为： 找中序遍历中出现的第一个val值，并返回位置。
六、map容器（kvalue模型：<key，value>）
1、文档官网
map - C++ Reference
2、介绍：
（1）、 map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。（2）、在map中，键值key通常用于排序和惟一的标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型 pair 绑定在一起，为其取别名称为value_type :typedef pair<const key, T> value_type;（3）、在内部，map中的元素总是按照键值key进行比较排序的。（4）、map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。（5）、map支持下标访问符，即在[ ]中放入key，就可以找到与key对应的value。（6）、map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。（7）、头文件：<map>
3、pair模板类：
因为map的成员是pair模版类对象，所以先学习pair模板类；
（1）、文档官网：
pair - C++ Reference
（2）、定义：
pair是一个模板类，定义在<utility>头文件中。它用于将两个不同类型的值组合成一个单一的对象（键值对）。这两个值可以是相同类型，也可以是不同类型。
（3）、make_pair函数：
该函数的作用就是构建一个pair对象：
4、map的基本使用，更多接口可以查看官网进行学习：
（1）、map模版参数的说明：
（1）、key: 键值对中key的类型（2）、T： 键值对中value的类型（3）、Compare: （仿函数）比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)（4）、Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器（5）、注意：在使用map时，需要包含头文件<map>
（2）、插入函数insert：
我们常用第一种方式，即参数是一个value_type类型的引用，而value_type是pair<T1,T2>的别名，所以实际参数是一个pair对象。返回值下面再介绍。打印时的注意事项：这里不能直接解引用访问，因为map的成员变量为pair对象，是自定义类型，没有重载"<<"运算符，所以只能用结构体的两种访问方式：点（.）和' -> '。 介意范围for加上引用，因为拷贝的代价有点大：
5、map是根据键值去重的：
与set类似，map也有排序和去重的功能，并且是根据键值k进行操作的：如果是字符串，排序则依次根据首字母的ascll码值进行排序。
七、multimap容器
与set和mulitset类似，map也有一个与之对应的容器mulitmap容器
其他接口与上述类似，区别就是mulitmap容器可以插入重复值。插入是根据键值k来判断的，所以重复值即重复的键值k。
八、map容器的[ ]（重要）
为了方便理解，我们以一个场景下进行讲解：计算水果出现的次数：
1、使用迭代器和find函数：
2、使用insert函数的返回值
查看官网我们发现，使用map的[ ]时，会转化为如下：
我们可以看到是复用了insert函数，并运用了insert函数的返回值。所以首先我们需要理解insert的返回值是什么？
查看官网可以发现insert的返回值是一个pair<iterator，bool>的类模板类型：
因为不想新构造类模板，所以这里复用了pair类模板，pair类模板是一个单独的类模版，不是map独有的，所以每个地方都可以使用。
返回值模版参数的介绍：
（1）、bool：插入成功则为true，插入失败则为false（有重复键值K,则插入失败）；
（2）、iterator：插入成功，则指向新插入元素所在的结点；插入失败，则指向map中与之键值k重复的那个结点。
知道了返回值的含义，我们就可以使用insert完成上述功能：
3、使用map的[ ]
上述说明使用map的[ ]时，会转化为如下：
这样不方便观察，所以简化如下：
也就是说其实是复用了insert的返回值，来找到对应map结点位置的second。
其中，V()是默认构造的缺省值，（如int()），V为int，则默认值为0，V为指针，则默认值为nullptr。
所以可以使用[ ]完成水果计数：
参数e用键值key的引用进行接收，然后调用insert函数，若插入成功，则返回值pair对象的模版参数iterator就指向新插入这个结点，若插入失败，则指向map中重复键值K那个结点，最后返回该结点的second，所以我们在外面对mapCount[e]进行++，其实就是对键值K为e的那个结点的second进行++，以此达到计数的功能。
因为[ ]复用了insert函数，所以[ ]还能完成下述功能：
