c++ - 对无序集执行 set_difference

Question

set_difference算法需要以下内容

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

哈希表不是这种情况。

我正在考虑根据 std::remove_copy 实现集合差异 A-B，其中删除标准是集合 B 中存在 A 的元素。

是否有一种标准、有效、最快、最安全的方法来做到这一点？

Answer 1

如果您有两个哈希表，最有效的方法应该是遍历其中一个，在另一个哈希表中查找每个元素。然后将找不到的那些插入第三个容器中。粗略的草图可能如下所示:

std::vector<int> result;
std::copy_if(lhs.begin(), lhs.end(), std::back_inserter(result),
    [&rhs] (int needle) { return rhs.find(needle) == rhs.end(); });