c++ - 两组的有效交集

Question

我有两组（或地图），需要有效地处理它们的交集。我知道有两种方法可以做到这一点：

• 迭代两个映射，如 std::set_intersection: O(n1+n2)
• 遍历一张地图并在另一张地图中查找元素：O(n1*log(n2))

根据大小，这两个解决方案中的任何一个都明显更好（已计时），因此我需要根据大小在这些算法之间切换（这有点混乱） - 或者找到一个优于两者的解决方案，例如使用一些map.find() 的变体将前一个迭代器作为提示（类似于 map.emplace_hint(...)） - 但我找不到这样的函数。

问题：是否可以直接使用 STL 或某些兼容库来结合两种解决方案的性能特征？

请注意，性能要求使得这与之前的问题不同，例如 有效的集合交集？

标签： c++algorithmdata-structures

Answer 1

几乎在任何情况下std::set_intersection都将是最佳选择。仅当集合包含非常少量的元素时，另一种解决方案可能会更好。由于原木的性质以二为底。比例为：

n = 2, log(n)= 1
n = 4, log(n)= 2
n = 8, log(n)= 3
.....
n = 1024 log(n) = 10

如果集合的长度超过 5-10 个元素，则 O(n1*log(n2) 比 O(n1 + n2) 复杂得多。

将此类功能添加到 STL 并以这种方式实现是有原因的。它还将使代码更具可读性。

对于长度小于 20 的集合，选择排序比合并或快速排序要快，但很少使用。