在无序集合上执行set_difference

Question

set_difference算法需要满足以下条件：

这些范围的元素必须按照相同的标准进行排序

而哈希表则不满足这个条件。

我正在考虑使用std::remove_copy来实现集合差A-B，其中移除的标准是A中存在于集合B中的元素。

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

- Nikos Athanasiou

---

也许使用临时的std::set对象并向其中插入哈希表数据会更快（我确定更安全）。然后调用set_difference()函数，将结果输出到哈希表中。我主张首先确保事情能够工作，然后再进行必要的优化。 - PaulMcKenzie

如果你真的想做一个临时拷贝，使用std::vector和std::sort，而不是std::set。这样会更快，更节省内存。 - ltjax

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

- John Zwinck

---

我更喜欢使用rhs.count(needle) == 0; 然而，我对你的答案的主要批评是你只是给出了带有代码的算法，但没有说明为什么你认为它是最快的可用方法。 - CashCow

@CashCow：或者在C++20中使用!rhs.contains(needle)，因为TIMTOWTDI（有多种方法可以做到）。 :-) - ShadowRanger

Answer 2

如果您有两个无序集A和B，长度分别为Na和Nb，想要进行集合差运算，即获取A中所有不在B中的元素，则由于在B中查找是常数时间，您仅需迭代A并检查它是否在B中，其复杂度为O（Na）。

如果A是一个无序集合，而B是一个集合（或已排序的向量等），则每次查找都需要log（Nb），因此完整的复杂度将为O（Na * log（Nb））。

先对A进行排序将使其排序成本为（Na * log（Na）），然后进行Na + Nb的合并。如果Na显着小于Nb，则Na*log（Nb）显着小于Na+Nb，反之如果Na逐渐变大，则首先对其进行排序也不会更快。

因此，我认为先对A进行排序没有任何好处（通过首先对其进行排序，我指将其移动到排序的集合中）。

- CashCow