メモ：競プロで使う C++ - 忘れても大丈夫

競プロで使う C++ の STL の雑多なメモ

コンテナの要素数を $n$ とする
コンテナ名は d とする

`std::set`　（`#include <set>`）

動的集合で要素の検索，削除，挿入が $O(\log n)$ 時間でできるコンテナ

・ d.lower_bound(x)： $O(\log n)$ 時間
　　 $x$ 以上となる最初の要素を指すイテレータを返す．存在しない場合は end を返す．

・ d.upper_bound(x)： $O(\log n)$ 時間
　　 $x$ より大きい最初の要素を指すイテレータを返す．存在しない場合は end を返す．

・ d.erase(x)： $O(\log n)$ 時間
　　要素 $x$ を削除する．

・ d.erase(iter)： $O(1)$ 時間
　　イテレータ iter が指す要素を削除する（注意．正しくないイテレータの場合はエラー）．

・ d.erase(first, end)： $O(D \log n)$ 時間（ $D$ は区間の要素数）
　　イテレータ [first, end) が指す要素を削除する．

例を表示

set<int> d = {1, 3, 4, 6, 8, 9, 11};
cout << *d.lower_bound(3) << endl; // -> 3
cout << boolalpha << (d.lower_bound(12) == d.end()) << endl; // -> true

cout << *d.upper_bound(3) << endl; // -> 4
cout << boolalpha << (d.upper_bound(11) == d.end()) << endl; // -> true

d.erase(3); // -> d = {1, 4, 6, 8, 9, 11}
d.erase(d.lower_bound(4)); // -> d = {1, 6, 8, 9, 11}

// [4, 10] の要素を削除
d.erase(d.lower_bound(4), d.upper_bound(10)); // -> d = {1, 11}