减去两个无顺序的std :: vector对象

Question

我有两个对象向量.就像是:

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

我想获得包含good_things的第三个向量.换句话说,all_thing中的每个对象都不属于bad_things:

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

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

PS向量不能被排序,因为类的东西没有任何东西要排序.谢谢!

编辑:我不想做任何改动all_things.例如

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

Answer 1

从评论中，你的things 可以被排序，但以一种毫无意义的方式。

没关系。

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

编写一个函数，接受两个things 并给它们一个一致的无意义顺序，并且两个事物只有在相等时才比较不小于彼此。

就叫这个吧bool arb_order_thing(thing const&, thing const&)。

现在std::sort向量 和 都使用std::set_difference.

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

或者，考虑编写一个thing const*哈希器（不是 a std::hash<thing*>，因为它是全局的且粗鲁的）并使用unordered_set<thing const*>s 手动完成工作。对两个向量中较小的一个进行散列，然后std::copy_if对另一个向量的散列进行测试。