subtract two order-less std::vector of objects

Question

I have two vectors of object. Something like:

std::vector<thing> all_things;
std::vector<thing> bad_things;

I want to obtain a third vector that contains the good_things. In other words, every object in all_thing that is not belong to bad_things:

std::vector<thing> good_things=subtract(all_things,bad_things);

Any Ideas about how to implement subtract in most efficient and standard way.

P.S the vectors can NOT be ordered because the class thing does not have any thing to be ordered by. Thanks!

Edit: and I do not want to make any change to all_things. e.g.

void substract(const std::vector<thing>& a, const std::vector<thing>& b);

Answer 1

From the comments, your things can be sorted, but in a meaningless way.

And that is ok.

Sort them meaninglessly.

Write a function that takes two things and give them a meaningless order that is consistent, and two things only compare not-less-than each other if they are equal.

Call this bool arb_order_thing(thing const&, thing const&).

Now std::sort both vectors and use std::set_difference.

Now, this can be expensive if things are expensive to copy. So instead create two vectors of thing const*, write bool arb_order_thing_ptr(thing const*, thing const*) (which dereferences and compares using the meaningless ordering), sort the vectors-of-pointers using that, use set_difference using that, then convert back to a vector<thing>.

Alternatively, consider writing a thing const* hasher (not a std::hash<thing*>, because that is global and rude) and use unordered_set<thing const*>s to do the work manually. Hash the smaller of the two vectors, then do a std::copy_if testing against the hash on the other vector.

Answer 2

If you can't order them, you can use the brute force way. Just compare the vectors. E.g:

std::vector<Thing> all;
std::vector<Thing> bad;
std::vector<Thing> good (all.size());
auto it = std::copy_if (all.begin(), all.end(), good.begin(), 
    [&bad](const Thing& t){return std::find(bad.begin(), bad.end(), t) == bad.end();} );
all.resize(std::distance(all.begin(),it));