41

指定された値を持っている、またはいくつかの条件を満たすSTLコンテナーから要素を消去するにはどうすればよいですか?

さまざまな種類のコンテナに対してそれを行う単一の共通または統一された方法はありますか?

4

1 に答える 1

59

残念ながら、 STL コンテナーから要素を消去するための単一の統一されたインターフェイスまたはパターンはありません。しかし、次の 3 つの動作が発生します。

std::vector パターン

から特定の条件を満たす要素を消去するためstd::vectorの一般的な手法は、いわゆる消去削除イディオムです。

vが のインスタンスでstd::vector、ベクトルから値を持つ要素を消去したい場合x、次のようなコードを使用できます。

// Erase elements having value "x" from vector "v"
v.erase( std::remove(v.begin(), v.end(), x), v.end() );

要素を消去するために満たす基準が、単純な「消去する要素 == x」よりも複雑な場合は、次の代わりにstd::remove_if()アルゴリズムを使用できますstd::remove()。

// Erase elements matching "erasing_condition" from vector "v"
v.erase( std::remove_if(v.begin(), v.end(), erasing_condition), v.end() );

whereerasing_conditionは単項述語であり、いくつかの形式で表現できます。たとえば、ベクトル要素の型を入力として受け取る - をbool返す関数にすることができます (したがって、戻り値が のtrue場合、要素はベクトルから消去されます。それが の場合false、勝ちました) 't); または、ラムダとしてインラインで表現できます。functorにすることができます。等

(std::remove()とは両方ともヘッダーstd::remove_if()の汎用アルゴリズムです。)<algorithm>

ウィキペディアからの明確な説明は次のとおりです。

algorithmライブラリは、このための および アルゴリズムを提供しremoveますremove_if 。これらのアルゴリズムは、2 つの前方反復子によって示される要素の範囲で動作するため、基になるコンテナーまたはコレクションについての知識がありません。したがって、コンテナから要素が実際に削除されることはありません。むしろ、削除基準に適合しないすべての要素が、同じ相対順序で範囲の先頭にまとめられます。残りの要素は有効ですが、指定されていない状態のままです。これが完了すると、削除されていないremove最後の要素の 1 つ後ろを指すイテレータを返します。

コンテナーから要素を実際に削除するにremoveは、コンテナーのメンバー関数と組み合わせeraseます。そのため、"erase-remove idiom" という名前が付けられています。

基本的に、消去基準を満たさない要素を範囲の先頭 (つまり の先頭) にstd::remove()圧縮std::remove_if()し、残りの要素を実際にコンテナーから削除します。vectorerase()

このパターンは、 などの他のコンテナーにも適用されますstd::deque。

std::list パターン

から要素を消去するにはstd::list、単純なメソッドremove()とremove_if()メソッドが利用可能です:

// Erase elements having value "x" from list "l"
l.remove( x )

// Erase elements satisfying "erasing_condition" from list "l"
l.remove_if( erasing_condition );

erasing_condition(上記のセクションで説明したのと同じ特性を持つ、単項述語はどこにありますかstd::remove_if()。)

のような同様のコンテナに同じパターンを適用できますstd::forward_list。

連想コンテナ (std::map、std::set など) パターン

std::map、std::set、などの連想コンテナstd::unordered_mapは、ここで説明する一般的なパターンに従います。

  1. 消去条件が単純なキー マッチングの場合 (つまり、「キー x を持つ要素を消去する」 )、単純なerase()メソッドを呼び出すことができます。

    // Erase element having key "k" from map "m":
m.erase( k );

  2. 消去条件がより複雑で、カスタムの単項述語 (例: "erase all odd elements" ) で表される場合は、forループを使用できます (ループ本体で明示的な消去条件チェックを行い、erase(iterator)メソッドを呼び出します)。

    //
// Erase all elements from associative container "c", satisfying "erasing_condition":
//
for (auto it = c.begin(); it != c.end(); /* "it" updated inside loop body */ )
{
    if ( erasing_condition(*it) )
    {   
        // Erase the element matching the specified condition 
        // from the associative container.
        it = c.erase(it);

        // Note:
        // erase() returns an iterator to the element 
        // that follows the last element removed, 
        // so we can continue the "for" loop iteration from that position.
    }
    else
    {
        // Current element does _not_ satisfy erasing condition,
        // so we can just move on to the next element.
        ++it;
    }       
}

統一されたアプローチの必要性

上記の分析からわかるように、残念ながら、STL コンテナーから要素を消去するための統一された一般的なアプローチはありません。

次の表は、前述のパターンをまとめたものです。

----------------+------------------------------------------             
   Container    |            Erasing Pattern
----------------+------------------------------------------                
                |
 vector         |    Use erase-remove idiom.
 deque          |
                |
----------------+------------------------------------------               
                |
 list           |    Call remove()/remove_if() methods.
 forward_list   |
                |
----------------+------------------------------------------  
                |
 map            |    Simple erase(key) method call, 
 set            |    or 
 unordered_map  |    loop through the container,
 multimap       |    and call erase(iterator) on matching
                |    condition.
 ...            |
                |
----------------+------------------------------------------

特定のコンテナーに基づいて異なる特定のコードを記述すると、エラーが発生しやすく、保守が難しく、読みにくくなります。

ただし、さまざまなコンテナー タイプに対してオーバーロードerase()された共通名 (および などerase_if())を使用して関数テンプレートを記述し、それらの関数に前述のパターン実装を埋め込むことは可能です。 そのため、クライアントは単純にこれらの汎用関数を呼び出すことができ、コンパイラはコンテナーの種類に基づいて、 (コンパイル時に)適切な実装に呼び出しをディスパッチします。
erase()erase_if()

テンプレートのメタプログラミング手法を使用した、より洗練されたアプローチは、 Stephan T. Lavavejによってここで紹介されています。

于 2013-04-15T11:03:13.680 に答える