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

您可以将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 回答