c++set
1. 关联式容器
vector、list、deque、forward_list(C++11) 等STL容器，其底层为线性序列的数据结构，里面存储的是元素本身，这样的容器被统称为序列式容器。而 map、set 是一种关联式容器，关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器里面存储的是 <key, value> 结构的键值对，在数据检索时比序列式容器效率更高。map 和 set 的键是唯一的，但是 mutimap 和 multiset 支持多个同名且有不同映射的键共存。
2. 键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value, key 代表键值，value 表示与 key 对应的信息。比如：学生的姓名和他的学号是一一对应的，那么就可以通过查找学生的姓名来查找到对应的学号。set 容器是 key 结构。set 不允许存在相同的 key（multiset除外），且 key 不可修改（因为会破坏内部的红黑树结构）。
3.set容器
形参含义：
T：键值对应 value 的类型。
Compare：比较器的类型，缺省情况下按照小于来比较，一般情况下（内置类型元索）该参数不需要传递，如果无法比较时（自定义类型），需要用户自己显式传递比较规则（一般情况下按照函数指针或者仿函数来传递）。
Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器。
4.set的成员函数
4.1 map的成员函数介绍
set的构造：
| 函数声明 | 功能介绍 |
|---|---|
| sets() | 构造一个空的set |
set的迭代器：
| 函数声明 | 功能介绍 |
|---|---|
| begin()和end() | begin:首元素的位置；end：下一个元素的位置 |
| cbegin()和cend() | c指const，cbegin和cend指向的内容不能修改 |
| rbegin()和rend() | 反向迭代器，rbegin从end开始，rend从begin开始，其++和–的方向相反 |
| crbegin()和crend() | 与前一个功能相同，但指向的内容不能修改 |
set的容量与元素访问：
| 函数名 | 函数声明 | 功能介绍 |
|---|---|---|
| empty | bool empty() const | 检测set中的元素是否为空，为空返回ture，不为空返回false |
| size | size_type size() const | 返回set中有效元素的个数 |
set的修改：
| 函数名 | 函数声明 | 功能介绍 |
|---|---|---|
| insert | pair<iterator,bool> insert (const value_type& val) | 在 set 中插入键值对 x，注意 x 是一个键值对，返回值也是键值对；iterator 代表新插入元素的位置，bool 代表插入成功 |
| erase | void erase (iterator position) size_type erase (const value_type& val) void erase (iterator first, iterator last) | 删除 position 位置上的元素 删除键值为 x 的元素 删除 [first,last) 区间中的元素 |
| swap | void swap (set& x) | 交换两个 set 中的元素 |
| clear | void clear() | 删除 set 里所有的元素 |
set的操作：
| 函数名 | 函数声明 | 功能介绍 |
|---|---|---|
| find | iterator find (const value_type& val) const | 搜索set里键等于k的元素，如果找到返回一个映射的迭代器，找不到返回end的迭代器,find函数默认查找中序的第一个相等的值 |
| count | size_type count (const value_type& val) const | 搜索set里键等于k的元素，找到返回1，找不到返回0 |
| lower_bound | iterator lower_bound (const value_type& val) const | 在set里找>=k的元素，返回符合情况的最小键的迭代器 |
| upper_bound | iterator upper_bound (const value_type& val) const | 在set里找>k的元素，返回符合情况的最小键的迭代器 |
| equal_range | pair<iterator,iterator> equal_range (const value_type& val) const |
5. set的特点
STL 里的 map 和 set 用的是同一颗红黑树来实现的。
set：
注意：Rb_tree 里有一个 key_type 和一个 value_type，但 set 应该是 key 和 key 的映射关系，所以在成员变量里，STL 把 key_type和 value_type 都定义了为 _key
map：
而在 STL 的 map 里，value_type 则定义了一个 pair ，这样做的目的就是为了复用同一颗红黑树。
所以从set和map的底层来看，它们的实现方法分别是：
set<K.> ⟶ \longrightarrow ⟶ rb_tree<K, K>
map<K, V> ⟶ \longrightarrow ⟶ rb_tree<K ,pair<const K, V>>
这种写法实际上是由 stl_tree.h 文件中的 val 模板决定你是 key 的 set，还是 key/value 的map：
6. set的复现
C++ 的 STL 库通过 map 和 set 复用同一颗红黑树实现代码的复用，这里给出 map 的复现链接C++STL容器之map的使用及复现，set 只需要把 map.h 中 key,value 的格式改成 key,key 即可。
