我有一个收藏std::set。我想以最快的方式找到这个集合中所有集合的交集。集合中的集合数量通常非常小（~5-10），每个集合中的元素数量通常小于 1000，但偶尔会达到 10000 左右。但是我需要进行数十次这些交集数千次，尽可能快。我尝试对以下几种方法进行基准测试：
- 就地交叉点
std::set最初复制第一组的对象。然后，对于后续集合，它会迭代自身和集合的第 i 个集合的所有元素，并根据需要从自身中删除项目。
- Using
std::set_intersection进入暂时的std::set，将内容交换到当前集合，然后再次查找当前集合与下一个集合的交集并插入到临时集合中，依此类推。
- 像 1) 一样手动迭代所有集合的所有元素，但使用
vector作为目标容器而不是std::set.
- 与 4 相同，但使用
std::list代替vector，怀疑一个list将从中间提供更快的删除。
- 使用哈希集（
std::unordered_set）并检查所有集合中的所有项目。
事实证明，使用vector当每个集合中的元素数量很小时，速度会稍微快一些，并且list对于较大的集合来说稍微快一些。就地使用set比两者慢得多，其次是set_intersection和哈希集。是否有更快的算法/数据结构/技巧来实现这一目标？如果需要，我可以发布代码片段。谢谢！
您可能想尝试概括一下std::set_intersection()：算法是对所有集合使用迭代器：
- 如果任何迭代器已经到达
end()其相应的集合，你就完成了。因此，可以假设所有迭代器都是有效的。
- 将第一个迭代器的值作为下一个候选值
x.
- 遍历迭代器列表并
std::find_if()第一个元素至少和x.
- 如果该值大于
x使其成为新的候选值并在迭代器序列中再次搜索。
- 如果所有迭代器都有值
x你找到了交集的一个元素：记录它，增加所有迭代器，重新开始。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
