More C++ Idioms/消去・削除(Erase-Remove)

消去・削除(Erase-Remove)

意図

STL コンテナから要素を取り除き、サイズを削減する。

動機

std::remove アルゴリズムはコンテナから要素を取り除かない！ 単純に、要素をコンテナの末尾に隔離するだけである。 これは、std::remove アルゴリズムが前方反復子(forward iterator)の対(反復子対(Iterator Pair)イディオム)のみを用いて動作し、一般化された前方反復子のコンセプトは、任意のデータ構造から要素を取り除くする方法を提供しないからである。 コンテナの内部データ構造を知っているのはメンバ関数のみであるため、メンバ関数のみがコンテナから要素を取り除ける。 消去・削除(Erase-Remove)イディオムは、コンテナから実際に要素を取り除くために使用される。

解法とサンプルコード

std::remove アルゴリズムは、「削除」された要素群の範囲の先頭を指す反復子を返す。 この時、コンテナの end() 反復子も、サイズも変更されない。 コンテナから実際に要素を削除するために、erase メンバ関数を以下のような慣用的な方法で使用できる。

std::vector<int> v; 
// 何らかの方法で、v を埋める
v.erase(std::remove(v.begin(), v.end(), 99), v.end()); // 値 99 の要素を全て実際に削除する

v.end() と std::remove の呼び出しとの評価順序はここでは重要ではない。 なぜなら、std::remove アルゴリズムが end() 反復子を変更しないからである。

既知の利用

• Boost.Rangeライブラリ
  • remove_erase関数
  • remove_erase_if関数

References

Effective STL, Item 32 - Scott Meyers