c++ - 减去两个对象的无序 std::vector

Question

我有两个对象 vector 。像这样的东西:

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

我想获得包含good_things 的第三个 vector 。换句话说，all_thing 中不属于 bad_things 的每个对象:

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

关于如何以最有效和标准的方式实现减法的任何想法。

P.S vector 可以NOT 排序，因为类thing 没有任何可以排序的东西。谢谢!

编辑:而且我不想对 all_things 进行任何更改。例如

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

Answer 1

从评论中，您的thing可以对 s 进行排序，但排序方式毫无意义。

没关系。

对它们进行无意义的排序。

写一个接受两个 thing 的函数s 并给它们一个无意义的一致顺序，并且两个事物只有在相等时才会相互比较。

称之为 bool arb_order_thing(thing const&, thing const&) .

现在std::sort两个 vector 并使用 std::set_difference .

现在，如果复制的东西很昂贵，这可能会很昂贵。因此，改为创建两个 vector thing const* , 写 bool arb_order_thing_ptr(thing const*, thing const*) (使用无意义的顺序取消引用和比较)，使用它对指针 vector 进行排序，使用它使用 set_difference，然后转换回 vector<thing> .

或者，考虑写一个 thing const*散列器(不是 std::hash<thing*> ，因为它是全局的且粗鲁的)并使用 unordered_set<thing const*>让我们手动完成这项工作。散列两个 vector 中较小的一个，然后执行 std::copy_if针对另一个 vector 上的哈希进行测试。