【C++】关联式容器
目录
前言：
一，set容器
二，multiset容器
三，map容器
四，multimap容器
前言：
在C++中，STL中的部分容器，比如：vector、list、deque、 forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。然而，在C++的STL中还存在关联式容器，它也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。
键值对用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和 value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。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总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用二叉搜索树(准确来说是红黑树，即平衡二叉搜索树)作为其底层结果，容器中的元素是一个有序的序列。
一，set容器
set综合使用文档：set的使用
注意：
1，与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对。
2，set中插入元素时，只需要插入value即可，不需要构造键值对。
3，set中的元素不可以重复(因此可以使用set进行去重)。
4，使用set的迭代器遍历set中的元素，可以得到有序序列
5，set中的元素默认按照小于来比较
6，set中查找某个元素，时间复杂度为：log n
7，set中的元素不允许修改，因为它是一个关联式容器，如果允许修改里面的元素，那么可能会破坏内部排序
8，set中的底层使用二叉搜索树(红黑树)来实现
set的模板参数列表
T：set中存放元素的类型，实际在底层存储的键值对。
Compare：set中元素默认按照小于来比较。
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理。(非必要情况可不用管)
set的构造
set的功能
C++STL容器中很多必要功能都是一样的，如迭代器、反向迭代器、常量迭代器、empty、size等。这里我们只介绍下set与之需要注意的功能接口，具体其它简单的功能查看文档即可。
| 函数声明 | 功能介绍 |
| 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的元素的个数 |
set的使用
#include
using namespace std;
void settest()
{
//set不存在相同数据
set s;
//插入时不会插入重复数据
s.insert(5);
s.insert(5);
s.insert(1);
s.insert(1);
s.insert(9);
s.insert(2);
s.insert(3);
for (auto e : s) {
cout
