11

重複の可能性:
std::map と同等の remove_if

私は文字列のセットを持っています:

set <wstring> strings;
// ...

述語に従って文字列を削除したい、例えば:

std::remove_if ( strings.begin(), strings.end(), []( const wstring &s ) -> bool { return s == L"matching"; });

これを試みると、次のコンパイラ エラーが発生します。

c:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\include\algorithm(1840): error C2678: binary '=' : no operator found which takes a left-hand operand of type 'const std::basic_string<_Elem,_Traits,_Ax>'

このエラーはstd::string、値によるコピー コンストラクターがないことを示しているようです (これは違法です)。std::remove_ifで使用するのはどういうわけか悪いstd::setですか？を数回繰り返すなど、代わりに何か他のことをする必要がありますset::find()かset::erase()？

4

2 に答える 2

21

std::remove_if(またはstd::erase) は、範囲のメンバーの値を再割り当てすることによって機能します。std::setがデータを整理する方法や、内部ツリー データ構造からノードを削除する方法を理解していません。set実際、オブジェクト自体を持たずに、ノードへの参照のみを使用してこれを行うことは不可能です。

標準アルゴリズムは、透過的な (または少なくとも一貫して覚えやすい) 計算の複雑さを持つように設計されています。a から要素を選択的に削除する関数はset、ツリーのバランスを取り直す必要があるため、O(N log N) になります。これは、 を呼び出すループに勝るものはありませんmy_set.remove()。したがって、標準はそれを提供していません。それはあなたが書く必要があるものです。

一方、アイテムをvector1 つずつ削除する単純なハンドコーディング ループは O(N^2)ですが、 std::remove_ifO(N) です。したがって、その場合、ライブラリは具体的なメリットを提供します。

典型的なループ (C++03 スタイル):

for ( set_t::iterator i = my_set.begin(); i != my_set.end(); ) {
    if ( condition ) {
        my_set.erase( i ++ ); // strict C++03
        // i = my_set.erase( i ); // more modern, typically accepted as C++03
    } else {
        ++ i; // do not include ++ i inside for ( )
    }
}

編集（4年後！）：i ++疑わしいようです。後置インクリメント オペレータが更新する前にerase無効化するとどうなりますか? ただし、組み込みの演算子ではなくiオーバーロードされているため、これは問題ありません。この関数はその場でoperator++安全に更新し、元の値のコピーを返します。i

于 2012-06-21T15:37:34.397 に答える
10

エラーメッセージは言う

' const std::basic_string<_Elem,_Traits,_Ax>'型の左側のオペランドを取る演算子が見つかりません

定数に注意してください。const オブジェクトで呼び出すことができるをstd::wstring持たないコンパイラは正しいです。operator=

文字列が const なのはなぜですか? 答えはstd::set、セット内の値は順序付けられており、値を変更するとセット内の順序が変更され、セットが無効になる可能性があるため、a 内の値は不変であるということです。

コンパイラがセットの値をコピーしようとするのはなぜですか?

std::remove_if（およびstd::remove）実際には何も消去しません（コンテナーがなく、イテレーターしかないため、消去できません）。それらが行うことは、基準に一致しない範囲内のすべての値を範囲の先頭にコピーし、一致する要素の後の次の要素に反復子を返すことです。次に、返されたイテレータから範囲の終わりまでを手動で消去する必要があります。セットは要素を順番に保持するため、要素を移動するのは正しくないためremove_if、セット (またはその他の連想コンテナー) では使用できません。

つまり、次のようにstd::find_ifandのループを使用する必要があります。set::erase

template<class V, class P>
void erase_if(std::set<V>& s, P p)
{
  std::set<V>::iterator e = s.begin();
  for (;;)
  {
    e = std::find_if(e, s.end(), p);
    if (e == s.end())
      break;
    e = s.erase(e);
  }
}
于 2012-06-21T16:02:08.733 に答える