set

底层实现是用红黑树。

set 建立

set<int> s; // 不可重，默认升序
set<int,less> s; // 不可重，升序
set<int,greater> s; // 不可重，降序
multiset<int> s; // 可重集

set 也可以重载，利用结构体实现。

重载方式同 priority_queue 。

set 插入及访问

set<int>::iterator it;
s.insert(x); // 插入元素 x
s.begin(); // 最前面的迭代器
s.end(); // 最后一个元素之后的迭代器（实则空）
s.rbegin(); // 最后一个迭代器
s.rend(); // 最前面的前一个迭代器

pair<set<int>::iterator,bool> it=s.insert(x);
if(it.second) { 插入成功 }
else { 插入失败 }

set 大小

s.size(); //返回容器中元素的数目
s.empty(); //判断容器是否为空

set 的删除操作

s.clear(); //清除所有元素
s.erase(it); //删除 it 迭代器所指的元素，返回下一个元素的迭代器。
s.erase(l,r); //删除区间 [l,r) 的所有元素，返回下一个元素的迭代器。
s.erase(x); //删除容器中值为 x 的元素。

有的时候为了避免删除一个空的位置，在删除是可以采用以下操作：

s.erase(s.find(*it));

set 的查找操作

s.find(x); //查找 x 元素，返回指向 x 元素的迭代器。
s.count(x); //返回容器中值为 x 的元素个数。对 set 来说，要么是 0，要么是 1。对 multiset 来说，值可能大于 1。
s.lower_bound(x); //返回第一个 >=x 元素的迭代器
s.upper_bound(x); // 返回第一个 >x 元素的迭代器。
s.equal_range(x); //返回容器中与 x 相等的上下限的两个迭代器。上限是闭区间，下限是开区间，如 [l,r) 。