PS:本文仅起一个备忘的作用。

set

set 指的是有序的不可重集,与数学上的定义类似。

常用操作:

  • p.insert(x):在 \(p\) 中插入 \(x\),若 \(p\) 中已有 \(x\) 则返回 false,否则返回 true
  • p.erase(x):在 \(p\) 中删除值为 \(x\) 的元素,返回删除的元素个数
  • p.erase(pos):在 \(p\) 中删除迭代器为 \(pos\) 的元素
  • p.clear():清空 \(p\)
  • p.begin():返回指向 \(p\) 首元素的迭代器
  • p.rbegin():返回指向 \(p\) 末尾元素 的迭代器
  • p.end():返回指向 \(p\) 最后的占位符的迭代器,没有元素
  • p.count(x):返回 \(p\) 内值为 \(x\) 的元素个数,因为 set 中元素不可重复,所以其返回值只能为 0 或 1
  • p.empty()\(p\) 是否为空
  • p.size():返回 \(p\) 内元素个数
  • p.find(x):返回指向 \(p\) 内值为 \(x\) 的元素的迭代器,若不存在则返回 p.end()
  • p.lower_bound(x):返回 \(p\) 中首个大于等于 \(x\) 的值的迭代器,若不存在则返回 p.end()
  • p.upper_bound(x):返回 \(p\) 中首个大于 \(x\) 的值的迭代器,若不存在则返回 p.end()

PS:set 内置的 lower_bound()/upper_bound() 复杂度为 \(O(\log n)\),但是如果使用 algorithm 中的 lower_bound()/upper_bound() 复杂度则为 \(O(n)\)

PS:set 不支持修改

multiset

multiset 指的是有序的可重集。其操作和 set 基本相同。只不过由于其可以有相同元素,所以部分操作可能有变化。multiset 同样不支持修改。