在本篇中，我们将要介绍两个常用的 STL 库中的两个数据结构，set 和 map，这两个函数的底层都是由红黑树实现的。本篇不会实现其底层原理，本篇只会将其其中的要点和使用时应该注意的地方。然后还会介绍关于 set 和 map 的两个扩展容器：multiset 和 multimap。
目录如下：
目录
1. 关联式容器和键值对
关联式容器
对于 STL 容器而言，存在序列式容器，如：vector、list、deque、forward_list等，其底层实现为线性序列数据结构，其中存储是元素本身。
本篇将要介绍是关联式容器 map 和 set，关联式容器也是用来存储数据的，与序列式容器不同的是，其中存储的为 <key, value> 结构的键值对，在数据检索时比序列式容器效率更高。
键值对 pair
在讲解 map 和 set 之前，我们要先介绍一种结构，该结构只包含两种成员变量 key 和 value，key 代表键值， value 代表与 key 对应的关系。其对应关系可以理解为英汉互译的中英文词汇。
SGI-STL中关于键值对的定义：
template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair() : first(T1()) , second(T2()) {} pair(const T1& a, const T2& b) : first(a) , second(b) {} };在下文中，我们将要开始介绍两种树形结构的关联式容器 —— map 和 set。
2. set
以下关于 set 的解释来源于：cplusplus.com/reference/set/set/?kw=set
对于 set 的一些特性如下：
1. set 是按照一定次序存储元素的容器；
2. set 中的元素不能被修改，因为是按照顺序存储的树形结构，修改之后很可能会影响其树形特性，我们只能增加和删除元素；
3. 在树形结构内部，set 中的元素总是按照其内部比较对象所指示的特定严格弱排序准则进行排序；
4. set 底层是用二叉搜索树（红黑树）实现。
5. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
6. set 中的元素不会存在相同键值的元素。
set 的使用
关于 set 的使用，对于 set 的模板参数列表如下：
其中，T：set 中存放的元素类型，实际在底层中存储的是 <value, value> 键值对；
Compare：set 元素默认按照小于来比较（也可以提供其他的仿函数）；
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
关于 set 的使用，我们按照在网站中提供的函数来一步一步的使用，如下：
modified -- set
直接使用有关修改 set 中元素的库函数，关于 set 中的迭代器以及一些其他常用的函数本篇便不在讲解。
如下，关于 insert 函数的使用：
如上所示，当我们将 vector 中的袁术插入 set 中时，对于已经存在元素，并不会存入进去，所以，对于 set 来说，其具有去重的功能。
关于 erase 函数的使用，其中 erase 函数有三个重载函数，其中可以传入的参数可以有迭代器，特定的元素，还有迭代器区间，如下：
如上所示，我们分别可以使用这三个重载函数进行对 set 中的元素进行删除。
关于其他的修改函数（swap、clear……）等函数就不在示例。
otheroperation -- set
现在将介绍一些关于 set 的其余函数的函数的使用，先是 find 函数的使用，如下：
如上所示，当我们的 find 函数找到元素之后，会返回元素的迭代器，当没有找到的时候，会返回 set 的迭代器 end（）。
接下来将要实例的是：lower_bound 和 upper_bound 函数，关于这两个函数，一个返回的是，大于等于传入参数的迭代器，另一个是返回小于传入参数的迭代器，如下：
如上所示，当我们可以找打的时候，返回的就是元素的迭代器，找不到的时候，lower_bound 函数返回的就是迭代器的开始 begin，当 upper_bound 函数找不到的时候，返回的就是迭代器的末尾 end。
3. map
以下关于 map 的解释来自于网站：map - C++ Reference (cplusplus.com)
以下是对 map 特性的一些解释：
1. map 是按照键值对中的键值进行一定次序进行存储的容器。其中 map 对于一个键值，只能存储一个元素，而 mutlimap 可以存储多个相同键值的键值对。
2. map 和 multimap 中的键值对不能被修改（用于建立树形结构），但是键值对应的值我们可以修改。
3. map 和 multimap 的底层是用红黑树实现的。
4. map 支持下标访问符，即在 [ ] 中放入 key，就可以找到与 key 对应的 value。
map 的使用
关于 map 的使用，map 的模板参数如下：
其中，Key：map 中键值对中的键值存储的元素类型；
T：map 中键值对中键值对应关系的元素类型，同 Key 一同存储在 pair 结构中。
Compare：map 中默认按照小于来比较（也可以提供其他的仿函数）
Alloc：map 中元素空间的管理方式，使用 STL 提供的空间配置器管理。
关于 map 的使用，我们按照在网站中提供的函数来进行讲解，如下：
需要补充的一点：关于 map 迭代器的使用，因为 map 中存储的元素是一个键值对，对于使用 *it 这样的访问方式较为麻烦，所以重载了 it->first 这样的运算符重载函数。
modified -- map
对于修改函数，我们只会简略的将其中两个常用函数：insert erase 函数，首先是对于 insert 函数，关于该函数，在C++98下提供三个重载函数，如下：
其中，我们主要使用第一个重载函数，插入一个键值对，然后返回一个键值对，返回的键值对中键值为指向插入元素的迭代器，第二个元素为一个 bool 类型的值，代表插入的值是否插入成功，插入成功为 true，失败为 false。我们可以用这个插入函数来对 map 中的元素进行计数，如下：
如上所示，当我们插入失败的时候，就将键值对中的第二个元素加一。
关于其他两个重载函数：第二个重载函数是在 position 位置前插入一个键值对，若插入成功返回指向元素的迭代器。第三个重载函数进行迭代器区间插入。
接着是 erase 函数，常用的有三个重载函数，如下：
其中第一个重载函数传入一个迭代器，删除该迭代器指向的元素。第二个重载函数，传入的是一个键值，返回值返回的是一个 size_t 类型的整数，表示删除的个数。第三个重载函数，迭代器区间删除，传入迭代器区间，然后进行删除。如下：
如上所示，可以成功的删除元素。
otheroperation -- map
在讲解 map 中的一些其他函数中，我们只会讲 find，lower_bonud，upper_bound 三个函数。首先，我们要介绍的是 find 函数，其中，需要传入的参数为键值对中的第一个元素，返回的是一个指向找到的元素的迭代器，当我们找到元素的时候，会返回迭代器中的 end。如下：
如上所示。
接下来讲 lower_bound 和 upper_bound 函数，关于这两个函数而言，和 set 中的俩个函数一样，lower_bound 函数，返回的是大于等于关键值的迭代器，upper_bound 返回的是小于关键字的迭代器。当没有找到的时候，返回的分别是 begin 和 end，如下：
如上所示。
operator[ ] -- map
接下来将要一个运算符重载 operator[ ]，这个运算符重载和其他的运算符重载存在很大的区别，传入 [ ] 中的不是整型下标，而是一个键值，如下：
函数的返回值是键值对应的值 Value。当我们在 [ ] 传入的参数是 map 中没有的时候，会自动加入，并返回键值对应的 Value，当 [ ] 中传入的参数已经存在的时候，返回的也是键值对应的 Value。所以我们也可以使用 [ ] 进行插入操作（通常不建议只用于插入操作），如下，我们统计次数：
4. multiset multimap
multiset
我们首先介绍 multiset 类，关于这个类其实和 set 类的区别主要在于 multiset 类可以存入重复的元素，但即使存入了重复的元素，我们也并不能直接的修改 multiset 中的元素。
对于 multiset 的函数接口，和 set 基本一致。
既然 multiset 类可以存储重复的元素，那么我们可以利用该容器适配器进行对元素进行排序。如下：
multimap
标签：map,set,函数,迭代,元素,键值 From： https://blog.csdn.net/m0_74830524/article/details/139049973关于 multimap 类和 map 类基本一致，但于 multiset 具有同样的特点，可以存储多个具有一样的键值元素。
但是需要注意的是 multimap 的接口和 map 中的接口相比较，multimap 中的没有重载 [ ]，这是因为当重载之后，返回键值的 value，不知道返回哪一个，会产生冲突。
如下：
