set 集合

set 集合 有序的
multiset 多重集合 有序的

支持的操作：

• 加入任意值 s.insert
  • 有返回值，返回 pair<iterator, bool>
  • iterator 表示插入位置的指针
  • bool 表示插入是否成功
• 删除任意值 s.erase
  • 参数可以是 值 或者 iterator
  • 如果 erase 一个值，会把所有这个值都删掉
  • multiset 时，有的时候只想删去一个值，要用 s.erase(s.find(x))
• 询问 lower_bound 和 upper_bound
  • lower_bound >= x 的最小值
  • upper_bound > x 的最小值
• 询问最小值 s.begin()
• 询问最大值 --s.end() 或 s.rbegin()
  • 如果想删去最大值，只能用 s.erase(--s.end())
  • 如果想删去最大值，不能用 s.erase(s.rbegin())
  • 因为 s.rbegin() 是 reverse_iterator 不是 iteratior
• 从小到大遍历所有元素
  • for (auto i : s)
  • for (set<int>::iterator it = s.begin() it != s.end(); it++)
• 从大到小遍历所有元素
  • for (auto it = s.rbegin() it != s.rend(); it++)

不支持的操作

询问第k大值
询问一个值是第几大

priority_queue 能做的，set 都能做，但是 set 慢一些

C++ set = Java TreeSet (sorted set)
C++ unordered_set = Java HashSet
Python 用 SortedList 实现 C++ set 的功能

s.find(x)
如果 x 在 set 中，返回 iterator
如果不在 返回 s.end()

s.lower_bound(x) set 中 >= x 最小的
s.upper_bound(x) set 中 > x 最小的
如果存在，返回 iterator
如果不存在，那么返回 s.end()

如果 x 不在 s 中，那么 lower_bound 和 upper_bound 结果相同（不存在 == x 的位置）

--s.lower_bound(x) set 中 < x 最大的
--s.upper_bound(x) set 中 <= x 最大的
需要注意如果x已经是最小的数字，那么可能出错。

枚举

for (auto i: s)
{

}

加入

可以利用 insert 的返回值判断是否删除成功

删除

multiset 删除一个 要先 find 再 erase