Subtract vectors, that contain duplicated elements

Question

Is there any elegant way to subtract std::vectors, that contain duplicated elements?

---

Example:

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

and I want the result to be:

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

---

My current (and very slow) solution:

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)

My other idea is:

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

But this is kinda error-prone doesn't look elegant to me.

Any other ideas?

Answer 1

You could use std::copy_if with a unary predicate that checks whether the element is in the second vector. Or, if you don't have C++11 support, use std::remove_copy_if with the predicate's logic suitably changed.

For the unary predicate:

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_;

};

which can be instantiated like this:

Foo f(v2);

You could modify the functor to keep a sorted version of the reference vector, with unique entries to allow to do a binary search, but the general idea is the same.

Answer 2

I have a rather simple algorithm, which complexity is O(n²). However, it can be faster with a sort (O(n log n)). Here it is:

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

With other structures, maybe it could be faster. For example, if elements were shared, you could detach all elements of v that are shared with s, with a O(n) complexity.