目录
1. 前言
set是STL中的容器之一，不同于普通容器，它的查找速度极快，常用来存储各种经常被检索的数据，因为容器的底层是平衡二叉搜索树中的红黑树。除此之外，还可以借助其特殊的性质，解决部分难题
2. 预备知识
2.1 关联式容器
在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque、forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
线性存储：是指元素按照一定的顺序排列，然后元素是连续存储的，或者通过指针构成一条链表
list：
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key,value>结构的键值对，在数据检索时比序列式容器效率更高。
2.2 键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息（实值）。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。
3. set详解
3.1 set是什么
【set】 是按照一定顺序存储的容器
在 set 中，元素的 value 也标识它（value就是key，类型为T），并且每个value必须是唯一的。set中的元素不能在容器中修改（元素总是 const 类型），但是可以从容器中插入或者删除它们。
在内部，set 中的元素总是按照其内部比较对象（类型为Compare）所指示的特定严格弱排序准则进行排序。
set 容器通过 key 访问单个元素的速度比 unordered_set 容器慢，但 set 容器允许根据顺序对子集进行直接迭代
set 在底层是用二叉搜索树（红黑树）实现的。
注意点：
set 中 插入元素时，只需要插入 value 即可，不需要构造键值对
set 中的元素不可以重复（因此可以使用 set 去重）
使用 set 的迭代器遍历 set 中的元素，可以得到有序序列
set 中的元素默认按照 升序 来排序
set 中的查找某个元素，时间复杂度为 ：log N
与 map/multimap不同 ，map/multimap 中存储的时真正的键值对 <key，value>，set 中只放 value，但是底层实际存放的是 <value，const value> ，这个大家先了解后面学到用set复用底层红黑树就能懂了
set 中的元素不允许修改，因为 set 在底层是用二叉搜索树来实现的，若是二叉搜索树当中的某个元素值进行了修改，那么这棵树将不再是二叉查找树。
3.2 set模板参数列表
如下图所示：
- T ： set中存放元素的类型，实际在底层存储 <value, value> 的键值对。
- Compare ：set中元素默认按照小于来比较。
- Alloc ：set中元素空间的管理方式，使用STL提供的空间配置器管理。
3.3 set构造
这里主要有三种方式：
（1）无参构造空容器
set<int> s1; // 构造一个int类型的空容器
（2）使用迭代器区间进行初始化构造
vector<int> v1 = { 1,2,3,4,5 };
set<int> s3(v1.begin(), v1.end()); // 构造vector对象某段区间的复制品（3）拷贝构造某类型容器
set<int> s2(s1); // 拷贝构造int类型s1容器的复制品
3.4 set的使用
使用set要包头文件include <set>
set的成员函数主要分为：迭代器，容量操作，修改操作。
- set的成员函数主要分为：迭代器，容量操作，修改操作。
我这里只举几个常用的，其它可以看文档学习。
3.4.1 insert
在 set 中插入元素 val ，实际插入的是 <val，val> 构成的键值对
- 如果插入成功，返回 <val在set中的位置， true>
- 如果插入失败，说明 val 在set中已经存在,返回 <val在set中的位置， false>
void testset()
{
set<int> s;
// 插入元素
s.insert(4);
s.insert(5);
s.insert(2);
s.insert(2);
s.insert(1);
s.insert(3);
s.insert(3);
// 遍历
for (auto e : s)
{
cout << e << " ";
}
}可以看到当插入元素重复元素时，set 会自动过滤掉，并对已有的元素进行排序
3.4.2 find
代码示例：
void testset()
{
set<int> s;
// 插入元素
s.insert(4);
s.insert(5);
s.insert(2);
s.insert(2);
s.insert(1);
s.insert(3);
s.insert(3);
int x;
cin >> x;
set<int>::iterator pos = s.find(x);
if (pos != s.end())
{
cout << "找到了" << endl;
}
}3.4.3 erase
删除 set 中的元素，这里有3种删除方式
（1）从set容器中删除迭代器指向位置的元素（搭配 find 使用）
void testset()
{
set<int> s;
// 插入元素
s.insert(4);
s.insert(5);
s.insert(2);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(8);
s.insert(7);
// 遍历
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
auto pos = s.find(5);
if (pos != s.end())
{
s.erase(pos); // 删除元素5
cout << "删除成功" << endl;
}
else
{
cout << "删除失败" << endl;
}
// 遍历
for (auto e : s)
{
cout << e << " ";
}
}
注意一点，迭代器删除一定要判断是否是end()，否则会有问题
（2）从set 容器中删除单个元素（直接传入要删除的元素）
void testset()
{
set<int> s;
// 插入元素
s.insert(4);
s.insert(5);
s.insert(2);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(8);
s.insert(7);
s.erase(5);
// 遍历
for (auto e : s)
{
cout << e << " ";
}
}那么它和 第1种 的区别是什么呢?
- erase(x) ：如果x存在就删除；如果不存在，不做任何改变
- erase(pos) ：如果x存在就删除;如果不存在，此时pos位置指向set::end的迭代器，那么程序运行就会报错。
(3) 从 set 容器中删除一组元素（传的是迭代器区间【first，last)）
void testset()
{
set<int> s;
// 插入元素
s.insert(4);
s.insert(5);
s.insert(2);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(8);
s.insert(7);
// 遍历
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
auto pos = s.find(5);
if (pos != s.end())
{
s.erase(pos, s.end()); // 从5开始所有的元素全部删除
cout << "删除成功" << endl;
}
else
{
cout << "删除失败" << endl;
}
// 遍历
for (auto e : s)
{
cout << e << " ";
}
}程序运行结果：
- 可以看到从 5 开始所有的元素都已经被删除了
3.4.4 swap
交换 set 容器中的元素
void testset()
{
set<int> s1;
s1.insert(4);
s1.insert(5);
s1.insert(2);
s1.insert(1);
set<int> s2;
s2.insert(6);
s2.insert(3);
s2.insert(8);
s2.insert(7);
cout << "s1：";
// 遍历
for (auto e1 : s1)
{
cout << e1 << " ";
}
cout << "s2：";
// 遍历
for (auto e2 : s2)
{
cout << e2 << " ";
}
s1.swap(s2);
printf("\n交换后\n");
cout << "s1：";
// 遍历
for (auto e1 : s1)
{
cout << e1 << " ";
}
cout << "s2：";
// 遍历
for (auto e2 : s2)
{
cout << e2 << " ";
}
}
程序运行结果：
3.4.5 empty
判断 set 容器是否为空，空返回 ture，非空返回 false
void testset()
{
set<int> s1;
s1.insert(4);
s1.insert(5);
s1.insert(2);
s1.insert(1);
set<int> s2;
cout << s1.empty() << endl; // s1容器不为空,输出0（表示假）
cout << s2.empty() << endl; // s2容器为空,输出1（表示真）
}3.4.6 size
返回 set 中的有效元素个数
void testset()
{
set<int> s;
// 插入元素
s.insert(4);
s.insert(5);
s.insert(2);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(8);
s.insert(7);
// 打印元素个数
cout << s.size() << endl;
}
3.4.7 count
返回 set 中值为 x 的元素的个数
- 这个接口对于 set 容器其实没有太大用处，因为 set 当中每个value 都是唯一的
3.4.8 lower_bound
返回大于等于val位置的迭代器。
void testset()
{
set<int> s;
// 插入元素
s.insert(4);
s.insert(5);
s.insert(2);
s.insert(1);
s.insert(3);
s.insert(8);
s.insert(7);
// 如果3存在就返回3位置的迭代器
auto lowIt = s.lower_bound(3);
cout << *lowIt << endl;
// 如果6不存在就返回比6大的位置的迭代器
lowIt = s.lower_bound(6);
cout << *lowIt << endl;
}
代码示例二：
3.8.9 upper_bound
不管val存在还是不存在，都返回比val大的那个值位置的迭代器。
void testset()
{
set<int> s;
// 插入元素
s.insert(4);
s.insert(5);
s.insert(2);
s.insert(1);
s.insert(3);
s.insert(8);
s.insert(7);
// 如果3存在就返回大于3位置的迭代器
auto lowIt = s.upper_bound(3);
cout << *lowIt << endl;
// 如果6不存在就返回比6大的位置的迭代器
lowIt = s.upper_bound(6);
cout << *lowIt << endl;
//如果在set中找打不到比val还大的值就会返回end()
//lowIt = s.upper_bound(8);
// 此时去访问迭代器指向的位置就会报错
//cout << *lowIt << endl;
}
- 其实，lower_bound 和 upper_bound 可以搭配使用，删除元素中间的一段区间
void testset()
{
set<int> s;
// 插入元素
s.insert(4);
s.insert(5);
s.insert(2);
s.insert(6);
s.insert(1);
s.insert(3);
s.insert(8);
s.insert(7);
cout << "删除前" << endl;
// 遍历
for (auto e : s)
{
cout << e << " ";
}
// 删除 [3, 7] 这段区间中的所有数
auto leftIt = s.lower_bound(3); // 返回3位置的迭代器
auto rightIt = s.upper_bound(7); // 返回8位置的迭代器
//删除是左闭右开
s.erase(leftIt, rightIt);
cout << endl << "删除后" << endl;
// 遍历
for (auto e : s)
{
cout << e << " ";
}
}
- 注意：erase 删除的迭代器区间是左闭右开，也就是说 right 是 8 位置的迭代器，但是 erase 只会删除到 7。
2.8.10 set降序使用
可以通过改变
set模板参数2的方式，改变其中的顺序为 降序
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main()
{
vector<int> arr = { 7,3,6,9,3,1,6,2 };
set<int, greater<int>> s1(arr.begin(), arr.end());
for (auto e : s1)
cout << e << " ";
return 0;
}4. set 的特点
