2

std::vector重複した要素を含む sを減算するエレガントな方法はありますか?

例：

v1 = { 3, 1, 2, 1, 2, 2 }
v2 = { 2, 4, 3, 3, 3 }
result1 = ??( v1, v2 )
result2 = ??( v2, v1 )

結果を次のようにしたい：

result1 = { 1, 1 }
result2 = { 4 }

私の現在の（そして非常に遅い）解決策：

1) sort v1 and v2
2) use std::unique_copy to v1_uniq, v2_uniq
3) intersect the new vectors with std::set_intersection
4) iterate over v1 and v2 and remove all elements, that are in the intersection 3)

私の他のアイデアは次のとおりです。

1) sort v1 and v2
2) iterate over v1 and v2 and remove duplicates in parallel

しかし、これはちょっとエラーが発生しやすいので、私にはエレガントに見えません。

他のアイデアはありますか？

4

2 に答える 2

4

要素が 2 番目のベクトルにあるかどうかをチェックする単項述語でstd::copy_ifを使用できます。または、C++11 をサポートしていない場合は、述語のロジックを適切に変更してstd::remove_copy_ifを使用します。

単項述語の場合:

struct Foo {

  Foo(const std::vector& v) : v_(v) {}
  bool operator() (int i) const {
    // return true if i is in v_
  }
  const std::vector<int>& v_;

};

次のようにインスタンス化できます。

Foo f(v2);

ファンクターを変更して、参照ベクトルのソート済みバージョンを保持し、一意のエントリを使用してバイナリ検索を実行できますが、一般的な考え方は同じです。

于 2012-06-10T11:39:38.977 に答える
2

私はかなり単純なアルゴリズムを持っていますが、その複雑さは O(n²) です。ただし、並べ替え (O(n log n)) を使用すると高速になります。ここにあります：

substract s from v
    for all elements of v
        for all elements of s
            if element i-th of v == element j-th of s
                then remove it from v and break the loop on s

他の構造では、おそらくそれはより高速になる可能性があります。たとえば、要素が共有されている場合、s と共有されている v のすべての要素を O(n) の複雑さで切り離すことができます。

于 2012-06-10T11:55:13.903 に答える