Вычесть векторы, содержащие дублированные элементы

Question

Есть ли элегантный способ вычесть 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 

Но это своего рода подвержены ошибкам не выглядеть элегантно мне.

Любые другие идеи?

Answer 1

Вы можете использовать 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); 

Вы можете изменить функтор сохранить отсортированный версию эталонного вектора, с уникальными записями, чтобы позволить делать двоичный поиск, но общая идея такая же.

Answer 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 

С другими структурами, возможно, это может быть быстрее. Например, если элементы были разделены, вы можете отделить все элементы v, которые совместно используются с s, с сложностью O (n).