摘自胡凡的《算法笔记》，仅作记录用！
前言：
set是一个内部自动有序且不含重复元素的容器。
如果要使用set，需要添加set头文件，即#include<set>，除此之外，还需要添加using namespace std;
一、set的定义
- 单独定义一个set，可以使用
set<typename> name;其实类似于vector的定义
- 这里的typename可以是任何基本类型，如int，double，char，结构体等，也可以是STL标准容器，如vector，set，queue等
- 值得注意的是，如果typename也是一个STL容器，定义的时候要记得在>>符号之间加上空格，因为一些使用C++11之前标准的编译器会把它视为移位操作，导致编译错误。
- set数组的定义
-
set<typename> Arrayname[arraySize];，这样Arrayname[0]~Arrayname[arraySize-1]中每一个都是一个set容器
二、set容器内元素的访问
- set只能通过迭代器访问
-
set<typename>::iterator it;定义迭代器，得到了迭代器it之后，可以通过*it来访问set中的元素
- set并不支持*(it+i)的访问方式。
- set内的元素自动递增排序，且自动去除了重复元素。
三、set常用函数
- insert()，时间复杂度为
O
(
N
)
O\left(N\right)
O(N)
-
insert(x)可以将x插入set容器中，并自动递增排序和去重。
- find()，时间复杂度为
O
(
N
)
O\left(N\right)
O(N)
-
find(value)返回set中对应值为value的迭代器
- erase()有两种用法
- 删除单个元素有两种方法：一是
st.erase(it)，it为所需要删除元素的迭代器。可以结合find()函数来使用。时间复杂度为
O
(
1
)
O\left(1\right)
O(1)。二是st.erase(value)，value为所需要删除元素的值，时间复杂度为
O
(
N
)
O\left(N\right)
O(N)
-
st.erase(first,last)可以删除一个区间内的所有元素，其中first为所需要删除区间的其实迭代器，而last为所需要删除区间的末尾迭代器的下一个地址，也即为删除[first,last)。时间复杂度为
O
(
l
a
s
t
−
f
i
r
s
t
)
O\left(last-first\right)
O(last−first)
- size()用来获得set内元素的个数，时间复杂度为
O
(
1
)
O\left(1\right)
O(1)
- clear()用来清空set中的所有元素，时间复杂度为
O
(
1
)
O\left(1\right)
O(1)
四、set的常见用途
- set最主要的作用就是自动去重并按升序排序，因此碰到需要去重却不方便开数组的情况，可以尝试用set。
- set中元素是唯一的，如果需要处理不唯一的情况，则需要使用multiset。另外，C++11标准中还增加了unordered_set，以散列代替set内部的红黑树（一种自平衡二叉树），使其可以用来处理只去重但并不排序的需求，速度比set要快。
