在无序集上执行set_difference

Question

该set_difference算法需要以下

范围内的元素应按照相同的标准进行排序

哈希表不是这种情况.

我正在考虑根据std::remove_copy移除标准在集合B中是否存在A的元素来实现集合差异AB .

是否有标准有效,最快最安全的方法？

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(); });