c++ - 减去包含重复元素的 vector

Question

是否有任何优雅的方法来减去包含重复元素的 std::vector？

---

例子:

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 

但这有点容易出错，在我看来并不优雅。

还有其他想法吗？

Answer 1

你可以使用 std::copy_if使用一元谓词检查元素是否在第二个 vector 中。或者，如果您不支持 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);

您可以修改仿函数以保留引用 vector 的排序版本，并使用唯一条目以允许进行二分搜索，但总体思路是相同的。