STL

lower_bound() / upper_bound()

lower_bound(begin, end, x); // 返回第一个 >= x 的元素的迭代器
upper_bound(begin, end, x); // 返回第一个 >  x 的元素的迭代器

若未找到，返回 end。在 vector 中求下标：it - vec.begin()。

map / set

mp[key] = val;       // 插入或修改
mp.count(key);       // 查是否存在 (0/1)
mp.erase(key);       // 删除

st.insert(x);        // 插入
st.count(x);         // 查是否存在
st.erase(x);         // 删除

map 和 set 自己实现了 lower_bound 和 upper_bound 方法，注意 map 以 键 为查找依据。

unordered_map / unordered_set

时间：$O(1)$（最坏 $O(N)$）。
区别：不支持 lower_bound，遍历无序。

4. priority_queue

时间：$O(\log N)$。

priority_queue<T> pq;//大根堆
pq.push(x);    // 入队
pq.top();      // 取队首
pq.pop();      // 出队
// 小根堆写法：
priority_queue<T, vector<T>, greater<T>> pq;

5. __gnu_pbds (Tree / 平衡树)

头文件

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;