減去包含重複元素的向量

是否有任何減法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

但是，這是有點容易出錯看起來不優雅了我。

還有其他想法嗎？

來源

2012-06-10 Kiril Kirov

你是否總是想用兩種方式執行操作？（即，你是否需要'result1'和'result2'？） –

@DavidRodríguez-dribeas - 是的，我做 –

您可以使用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-10 11:39:38 juanchopanza

這應該如何與一元謂詞一起工作？爲了做我想做的事，我必須使用二元謂詞 - 一個參數爲當前元素，另一個爲另一個向量，對嗎？（我不會使其他矢量全局變量..） –

@KirilKirov我添加了一個未經測試的例子。顯然你可以使仿函數成爲模板類。 – juanchopanza

傻我！我完全忘了函子可以在構造函數中接受參數..非常感謝！這是完美的。 –

我有一個相當簡單的算法，其複雜性是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-10 11:55:13 Synxis

是的，這是微不足道的方法，但它似乎是這裏最好的解決方案。我會等待其他想法，如果沒有更好的，我會接受你的方式。謝謝，我的+1。 –

我敢肯定，你可以通過首先排序將其降至O（n log n）。 –

@KonradRudolph - 是的，這是我的第二個解決方案，在我的問題的描述。 –

減去包含重複元素的向量

回答

相關問題