常常用于维护颜色段。随机数据下表现优秀,但构造数据随便卡。一定要看是否保证了数据随机。
前置
STL之set
。
set
内部是红黑树,内部不会出现值相同的元素。可重集使用multiset
,用法基本与set
一致。
插入删除
以下简写set<type>::iterator
为iter
-
s.insert(x)
,插入值为x
的元素,返回pair<iter,bool>
类型,前一个是指向插入元素的指针,后一个是返回插入是否成功(set
中已有等值元素时插入失败)。 -
s.erase(x)
,删除值为x
的所有元素,返回删除的元素个数。 -
s.erase(iter p)
,删除迭代器为p
的元素,要求迭代器合法。 -
s.erase(iter l,iter r)
,删除迭代器在\([l,r)\)的元素。 -
s.clear()
,清空s
。
迭代器
-
begin()/cbegin()
,指向首元素的迭代器。 -
end()/cend()
,指向尾端占位符的迭代器,注意此处没有元素。 -
rbegin()/crbegin()
,指向逆向的首元素,可以理解为最后一个元素。 -
rend()/crend()
,指向逆向的尾端占位符,对应正向首元素的前一个位置,注意此处没有元素。
以上带c
的迭代器为只读类型。
查找
-
s.count(x)
,返回键值为x
的元素个数。 -
s.find(x)
,返回值为x
的元素的迭代器,如果不存在则返回end()
。 -
s.lower_bound(x)
,返回s
中首个不小于x
的元素的迭代器,如果不存在则返回end()
。\(O(\log n)\),但是如果用lower_bound(s.begin(),s.end(),x)
则\(O(n)\)。 -
s.upper_bound(x)
,返回s
中首个大于x
的元素的迭代器,如果不存在则返回end()
。复杂度同上。 -
set
没有自带的nth_element
,于是只能手写平衡树或者权值线段树或者pb_ds
来\(O(\log n)\)查询第\(k\)大。直接使用nth_element(s.begin(),s.end(),k)
是\(O(n)\)的。 -
s.empty()
,返回容器是否为空;s.size()
,返回容器内元素个数。