Nikos Athanasiou Nikos Athanasiou - 1 year ago 105
C++ Question

Performing set_difference on unordered sets

The set_difference algorithm requires the following

The elements in the ranges shall already be ordered according to this same criterion

which is not the case for hash tables.

I'm thinking of implementing a set difference A-B in terms of
where the removal criterion would be the existence of an element of A in the set B.

Is there a standard-valid-fastest-safest way to do it?

Answer Source

If you have two hash tables, the most efficient way should be to iterate over one of them, looking up each element in the other hash table. Then insert the ones you do not find into some third container. A rough sketch might look like this:

std::vector<int> result;
std::copy_if(lhs.begin(), lhs.end(), std::back_inserter(result),
    [&rhs] (int needle) { return rhs.find(needle) == rhs.end(); });
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download