c++ - C++ 中一组集合的高效集合交集

Question

我有一个 std::set 的集合。我想以最快的方式找到这个集合中所有集合的交集。集合中的集合数量通常很少(~5-10)，每个集合中的元素数量通常少于 1000，但偶尔会增加到 10000 左右。但我需要做这些交集数十数千次，尽可能快。我尝试对一些方法进行基准测试，如下所示:

1. 在最初复制第一组的 std::set 对象中就地交集。然后对于后续集合，它遍历自身的所有元素和集合的第 i 个集合，并根据需要从自身中删除项目。
2. 使用 std::set_intersection 进入临时 std::set，将内容交换到当前集合，然后再次找到当前集合与下一个集合的交集插入临时集，等等。
3. 像 1) 一样手动遍历所有集合的所有元素，但使用 vector 而不是 std::set 作为目标容器。
4. 与 4 相同，但使用 std::list 而不是 vector，怀疑 list 会提供更快的从中间。
5. 使用哈希集 (std::unordered_set) 并检查所有集中的所有项目。

事实证明，当每个集合中的元素数量较少时，使用 vector 会稍微快一些，而对于较大的集合，list 会稍微快一些。就地使用 set 比两者都慢得多，其次是 set_intersection 和哈希集。是否有更快的算法/数据结构/技巧来实现这一目标？如果需要，我可以发布代码片段。谢谢!

Answer 1

您可能想尝试 std::set_intersection() 的泛化:算法是对所有集合使用迭代器:

1. 如果任何迭代器到达其对应集合的 end()，则您完成了。因此，可以假定所有迭代器都是有效的。
2. 取第一个迭代器的值作为下一个候选值x。
3. 在迭代器列表中移动，std::find_if() 第一个元素至少与 x 一样大。
4. 如果该值大于x，则将其作为新的候选值并在迭代器序列中再次搜索。
5. 如果所有迭代器都在值 x 上，您找到了交集的一个元素:记录它，递增所有迭代器，重新开始。