行业知识
【C++】树形关联式容器set、multiset、map和multimap的介绍与使用
���梓慕：个人主页
个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》
每一个不曾起舞的日子，都是对生命的辜负
目录
前言
1.关联式容器
2.键值对
3.树形结构的关联式容器
3.1set
3.1.1set的特性
3.1.2set的构造
3.1.3set的使用
3.1.4set的使用示例
3.2multiset
3.3map
3.3.1map的特性
3.3.2map的构造
3.3.3map的使用
有关insert
有关[]运算符
3.4multimap
前言
本篇文章博主会与大家共同探索STL库中的set与map，其中涉及set与map的使用与一些特性的讲解介绍。
欢迎大家收藏以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。
=========================================================================
GITEE相关代码：樊飞 (fanfei_c) - Gitee.com
=========================================================================
1.关联式容器
前面学习的vector、list、deque等容器统称为『 序列式容器』，插入方式一般为『 push』。
因为他们的底层均为线性序列的结构，且存储的均为元素本身，并没有什么特殊含义。
而今天所学习的map、set、multimap、multiset等都为『 关联式容器』，插入方式一般为『 insert』。
他们的区别在与『 关联式容器』里面存储的是结构的『 键值对』，在数据检索时比序列式容器效率更高。
2.键值对
『 键值对』用来表示具有『 一一对应』关系的一种结构，该结构中一般只包含两个成员变量Key和Value，key代表键值，value代表与键值key对应的信息。
我们来观察下SGI-STL中关于『 键值对』的定义：
template 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){}}; 很容易的我们看到在STL中『 键值对』就是pair这种结构。
pair的first代表的就是key，second代表的就是value。
注：我们可以采用make_pair()来构建『 键值对』。
那在实际的应用中我们有不同的方法来构建pair，这个我们后面在谈，这里先简单介绍一下。
3.树形结构的关联式容器
在STL中有两种不同结构的关联式容器。
| 关联式容器 | 容器结构 | 底层实现 | 特点 |
|---|---|---|---|
| set、map、multiset、multimap | 树型 | 平衡搜索树（红黑树） | 有序 |
| unordered_set、unordered_map、unordered_multiset、unordered_multimap | 哈希 | 哈希表 | 无序 |
这里我们只谈树形结构。
可以看到树形结构的关联式容器都采用『 平衡搜索树（红黑树）』作为底层实现方式。
其中multiset和multimap允许键值冗余，即允许不同value对应的key值重复。
3.1set
3.1.1set的特性
- set是按照一定次序存储元素的容器，使用set的迭代器遍历set中的元素，可以得到有序序列。
- 在set中，元素的value也标识它(value就是key，类型为T)，所以set中插入元素时，只需要插入value即可，不需要构造键值对，并且每个value必须是唯一的，所以set中的元素不可以重复(因此可以使用set进行去重)。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
- 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序，当不传入内部比较对象时，set中的元素默认按照小于来比较。
- set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
- set在底层是用二叉搜索树(红黑树)实现的，所以查找的时间复杂度为logN。
注意：与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对。
3.1.2set的构造
（1）构造
set s1;
（2） 拷贝构造。
set s2(s1);
（3）迭代器区间构造。
set s3(s2.begin(), s2.end());
（4） 采用大于的排序准则进行排序，默认为less小于即升序。
set s4;
3.1.3set的使用
pair insert (const value_type& x ) 在set中插入元素x，实际插入的是构成的键值对，如果插入成功，返回,如果插入失败，说明x在set中已经存在，返回 void erase ( iterator position ) 删除set中position位置上的元素 size_type erase ( const key_type& x ) 删除set中值为x的元素，返回删除的元素的个数 void erase ( iterator first, iterator last ) 删除set中[first, last)区间中的元素 void swap ( set& st ); 交换set中的元素 void clear ( ) 将set中的元素清空 iterator find ( const key_type& x ) const 返回set中值为x的元素的位置 size_type count ( const key_type& x ) const 返回set中值为x的元素的个数 bool empty ( ) const 检测set是否为空，空返回true，否则返回true size_type size() const 返回set中有效元素的个数 迭代器等 ... 3.1.4set的使用示例
#include void TestSet(){// 用数组array中的元素构造setint array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,6, 8, 0 };// 迭代器区间构造set s(array, array + sizeof(array) / sizeof(array));cout
