6

Visual Studio 2008 C ++ 03アプリケーションがあり、2つの標準コンテナーがあります。一方のコンテナから、もう一方のコンテナ（セットの共通部分）に存在するすべてのアイテムを削除したいと思います。

このようなもの：

std::vector< int > items = /* 1, 2, 3, 4, 5, 6, 7 */;
std::set< int > items_to_remove = /* 2, 4, 5*/;

std::some_algorithm( items.begin, items.end(), items_to_remove.begin(), items_to_remove.end() );

assert( items == /* 1, 3, 6, 7 */ )

これを行う既存のアルゴリズムまたはパターンはありますか、それとも自分でロールする必要がありますか？

ありがとう

4

6 に答える 6

6

試してみてください：

items.erase(
    std::remove_if(
        items.begin(), items.end()
      , std::bind1st(
            std::mem_fun( &std::set< int >::count )
          , items_to_remove
        )
    )
  , items.end()
);

std::remove(_if)コンテナではなくイテレータで機能するため、実際には何も削除されません。範囲の最後で削除する要素を並べ替え、イテレータをコンテナの新しい最後に戻します。次に、呼び出して、新しい終了eraseを過ぎたすべての要素をコンテナから実際に削除します。

更新：正しく思い出せば、実装はデフォルトのパラメーターを関数に追加できるため、標準ライブラリのコンポーネントのメンバー関数へのバインドは標準のC++ではありません。要素が削除するアイテムのセットに含まれているかどうかをチェックする独自の関数または関数オブジェクト述語を作成することで、より安全になります。

于 2012-05-15T14:59:27.153 に答える
3

個人的には、このために小さなヘルパーを作成することを好みます（これは頻繁に再利用します）。

template <typename Container>
class InPredicate {
public:
    InPredicate(Container const& c): _c(c) {}

    template <typename U>
    bool operator()(U const& u) {
        return std::find(_c.begin(), _c.end(), u) != _c.end();
    }

private:
    Container const& _c;
};

// Typical builder for automatic type deduction
template <typename Container>
InPredicate<Container> in(Container const& c) {
    return InPredicate<Container>(c);
}

erase_ifこれは、真のアルゴリズムを持つのにも役立ちます

template <typename Container, typename Predicate>
void erase_if(Container& c, Predicate p) {
    c.erase(std::remove_if(c.begin(), c.end(), p), c.end());
}

その後：

erase_if(items, in(items_to_remove));

これはかなり読みやすいです:)

于 2012-05-15T15:14:22.277 に答える
2

もう1つの解決策：

これに使用できる標準提供のアルゴリズムset_differenceがあります。ただし、結果を保持するには追加のコンテナーが必要です。私は個人的にそれをその場で行うことを好みます。

std::vector< int > items;
//say items = [1,2,3,4,5,6,7,8,9]

std::set<int>items_to_remove;
//say items_to_remove = <2,4,5>

std::vector<int>result(items.size()); //as this algorithm uses output 
                           //iterator not inserter iterator for result.

std::vector<int>::iterator new_end = std::set_difference(items.begin(), 
 items.end(),items_to_remove.begin(),items_to_remove.end(),result.begin());

result.erase(new_end,result.end()); // to erase unwanted elements at the 
                                    // end.
于 2012-05-15T15:56:52.690 に答える
1

std::eraseこれと組み合わせて使用​​できますstd::remove。Erase-Removeイディオムと呼ばれるC++イディオムがあります。これはこれを達成するのに役立ちます。

于 2012-05-15T14:59:30.743 に答える
1

2つのセットがAありB、、から削除したい場合B、の交差点、、は次Iの(A,B)ようI = A^Bになります。 A（そのままの状態で）最終結果は次のようになります。
B' = B-I

完全な理論： http：
//math.comsci.us/sets/difference.html

これは非常に簡単です。

  1. 作成してデータを入力Aし、B
  2. 3番目の中間ベクトルを作成します。I
  3. の内容をにコピーしBますI
  4. 要素を含むの各要素a_jについて、要素を検索します。要素がで見つかった場合は、それを削除しますAjIa_jI

最後に、個々の要素を削除するコードはここにあります：
特定の値を持つstlベクトルからアイテムを削除するにはどうすればよいですか？

そして、アイテムを検索するためのコードはここにあります：
アイテムがstd :: vectorに存在するかどうかを見つける方法は？

幸運を！

于 2012-05-15T15:06:32.117 に答える
0

これは、派手な関数を必要とせず、ベクトルを並べ替える必要もない、より「実践的な」インプレースメソッドです。

#include <vector>

template <class TYPE>
void remove_intersection(std::vector<TYPE> &items, const std::vector<TYPE> &items_to_remove)
{
    for (int i = 0; i < (int)items_to_remove.size(); i++) {
        for (int j = 0; j < (int)items.size(); j++) {
            if (items_to_remove[i] == items[j]) {
                items.erase(items.begin() + j);
                j--;//Roll back the iterator to prevent skipping over
            }
        }
    }
}

各セットの多重度が1（マルチセットではない）であることがわかっている場合は、実際にj--;行をに置き換えてbreak;パフォーマンスを向上させることができます。

于 2015-05-24T11:53:33.837 に答える