[洛谷日报第7期]STL整理之set
Set是什么？
Set是C++STL中提供的容器，set是数学上的集合——具有唯一性，即每个元素只出现一次，而multiset则是可重集，两者的内部实现是一棵红黑树，它们支持的函数基本相同
Set的相关操作
头文件与声明
像这样：
就像其他需要排序的数据类型一样，为一个结构体的set，需要重载小于号
set.size()
统计set中元素个数，函数返回一个整形变量，表示set中元素个数，时间复杂度O(1)
set.empty()
检查set是否为空，返回一个bool型变量，1表示set为空，否则为非空，时间复杂度O(1)
set.clear()
清空set，无返回值
set.count(x)
返回set或multiset中值为x的元素个数，时间复杂度为O(log n)
迭代器
- 双向访问迭代器，不支持随机访问，支持星号解除引用，仅支持“++”，“--”这两个算术操作
引用和操作：
若把it++，则it将会指向“下一个”元素。这里的下一个是指在key从小到大排序的结果中，排在it下一名的元素。同理，若把it--，则it会指向排在上一个的元素
“++”，“--”操作的复杂度均为O(log n)
- 遍历set及访问其中的元素
set.begin()
返回集合的首迭代器，即指向集合中最小元素的迭代器，时间复杂度为O(1)
set.end()
返回集合的尾迭代器，众所周知，STL中区间都是左闭右开的，那么end()函数返回的迭代器即为指向集合中最大元素的下一个位置的迭代器，因此--s.end()才是指向集合中最大元素的迭代器，时间复杂度为O(1)
set.insert(x)
在set中插入元素，返回插入地址的迭代器和是否插入成功的bool并成的pair，时间复杂度为O(log n)
PS：set在进行插入的时候是不允许有重复的键值的，如果新插入的键值与原有的键值重复则插入无效（multiset可以重复）
set.erase(参数)
删除，参数可以是元素或者迭代器，返回下一个元素的迭代器，时间复杂度为O(log n)，注意在multiset中s.erase(x)会删除所有值为x的元素
set.find(x)
在set中查找值为x的元素，并返回指向该元素的迭代器，若不存在，返回set.end()，时间复杂度为O(log n)
set.lower_bound(x)/upper_bound(x)
两个神奇的东西，决定把他们放在一块谈一谈
用法与find类似，但查找的条件略有不同，时间复杂度O(log n)
s.lower_bound(x)表示查找>=x的元素中最小的一个，并返回指向该元素的迭代器
s.upper_bound(x)表示查找>x的元素中最小的一个，并返回指向该元素的迭代器
举个例子：
在set{3,5,7,8,13,16}中，
对于在set中存在的元素，比如8，
s.lower_bound(8)返回8所在位置的迭代器。
s.upper_bound(8)返回13所在位置的迭代器。
对于在set中不存在的元素，比如12，
两个函数返回的则都是13所在位置的迭代器。
特殊地，
对于比set中最大的元素大的元素，比如20，
两个函数返回的都是s.end()。
本文发布于洛谷日报，特约作者：communist
原文地址：https://www.luogu.org/blog/communist/stl-zheng-li-zhi-set