std::set の erase は、単純に「要素を削除する関数」として扱われがちですが、実際には 指定方法の違いによる挙動差、戻り値、計算量、イテレータの無効化規則など、理解しておくべきポイントが多く存在します。
特に実務コードや競技プログラミングでは、これらを正しく把握していないとバグやパフォーマンス劣化の原因になります。
以下では、std::set::erase を仕様ベースで整理し、誤解されやすい点も含めて詳しく解説します。
std::set の基本的な性質
std::set は以下の特徴を持つ連想コンテナです。
- 要素は常にソートされた状態で保持される
- 同一の値は1つしか格納できない
- 内部実装は一般に平衡二分探索木（多くは赤黒木）
- 探索・挿入・削除はいずれも対数時間が基本となる
この「木構造で管理されている」という点が、erase の計算量やイテレータの扱いを理解するうえで重要になります。
set::erase の3つの指定方法
std::set の erase は、指定方法によって3種類に分かれます。
- 値（キー）を指定して削除する方法
- イテレータを指定して1要素を削除する方法
- イテレータの範囲を指定して複数要素を削除する方法
それぞれ挙動や戻り値、計算量が異なるため、使い分けが重要です。
値を指定して削除する erase(key)
この形式では、指定した値と等しい要素を削除します。
- 指定した値が存在すれば削除される
- 存在しなければ何も起きない
- 戻り値は「削除された要素数」
std::set は重複を許さないため、戻り値は常に 0 または 1 になります。
この性質を利用すると、「要素が存在していたかどうか」の判定を簡潔に行うことができます。
計算量は 対数時間 が保証されており、要素数が増えても安定した性能を維持できます。
イテレータを指定して削除する erase(pos)
この形式では、削除対象の位置がすでに分かっている状態で要素を削除します。
イテレータの無効化に注意
- 指定したイテレータは削除後に無効化される
- ただし、その 次の要素を指すイテレータが戻り値として返る（C++11以降）
この仕様により、ループ中で安全に要素を削除することが可能になります。
計算量の注意点
この形式の erase は、償却定数時間とされています。
つまり、削除位置が特定できている場合、探索コストを含まず、非常に効率よく削除が行われます。
「set の削除は常に O(log N)」と覚えていると誤解しやすいポイントなので注意が必要です。
範囲を指定して削除する erase(first, last)
この形式では、指定したイテレータ範囲に含まれる要素をまとめて削除します。
- 範囲は 半開区間（最初の位置は含むが、最後の位置は含まない）
- 戻り値は、削除後に「次に処理すべき位置」を指すイテレータ
- 実質的には、指定した
lastと同じ位置を指すことが多い
計算量
削除される要素数に比例した時間がかかります。
より厳密には「対数時間＋削除範囲の長さ」と考えるとよく、範囲が広いほど処理時間も増えます。
ループ中に erase を使う際の重要ルール
std::set では、要素を削除すると その要素を指していたイテレータは無効化されます。
そのため、ループ変数として使っているイテレータをそのまま削除し、次に進もうとすると未定義動作になります。
この問題を回避するためには、
- 削除時は
eraseの戻り値（次のイテレータ）を利用する - 削除しない場合のみイテレータを進める
というパターンを徹底する必要があります。
これは set だけでなく、map、multiset、multimap でも共通の重要な考え方です。
vector::erase との混同に注意
std::set と std::vector の erase は、同じ名前でも性質が大きく異なります。
set：木構造の再構成が行われるvector：要素の詰め直しが発生する
この違いにより、vector の erase は要素数に比例した時間がかかりますが、set は要素数が増えても比較的安定した性能を保ちます。
両者を同じ感覚で扱うと、パフォーマンス面で問題が出やすくなります。
multiset との挙動の違い
補足として multiset との違いも重要です。
set：同じ値は1つだけmultiset：同じ値を複数保持できる
このため、multiset で値を指定して erase を行うと、指定した値と等しい要素がすべて削除される点に注意が必要です。
戻り値は削除された要素数になります。
まとめ
std::set::erase を正しく使うために押さえておくべきポイントは以下の通りです。
- 値指定の削除は「削除数」が戻り値になる
- イテレータ指定の削除は「次のイテレータ」が返る
- イテレータ指定の削除は償却定数時間で高速
- 範囲削除は半開区間で、削除数に比例した時間がかかる
- ループ中の削除ではイテレータの無効化に必ず注意する
vectorやmultisetと挙動を混同しない
これらを理解しておくことで、std::set を安全かつ効率的に扱えるようになります。
以上、C++のset eraseについてでした。
最後までお読みいただき、ありがとうございました。
