c++ - 两组的有效交集

Question

我有两个集合(或 map )，需要高效处理它们的交叉点。我知道有两种方法可以做到这一点:

• 像 std::set_intersection 一样遍历两个映射:O(n1+n2)
• 遍历一个映射并在另一个映射中查找元素:O(n1*log(n2))

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

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

请注意，性能要求使其与之前的问题不同，例如 Efficient intersection of sets?

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 的集合，选择排序比合并或快速排序更快，但很少使用。