c++ - 两组的有效交集

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

像 std::set_intersection 一样遍历两个映射:O(n1+n2)

迭代一个映射并在另一个映射中查找元素:O(n1*log(n2))

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

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

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

最佳答案

对于实现为二叉树的集合，实际上有一种算法结合了您提到的两个过程的优点。本质上，您进行了类似于 std::set_intersection 的合并，但是在在一棵树中进行迭代时，您会跳过所有小于另一棵树中当前值的分支。

由此产生的交集需要 O(min(n1 log n2, n2 log n1, n1 + n2) ，这正是您想要的。

不幸的是，我很确定 std::set 不提供可以支持此操作的接口(interface)。

我过去做过几次，在处理加入倒排索引和类似的事情时。通常我会使用 skipTo(x) 操作来制作迭代器，该操作将前进到下一个元素 >= x。为了满足我 promise 的复杂性，它必须能够在 log(N) 分摊时间内跳过 N 个元素。然后一个交叉点看起来像这样:

void get_intersection(vector<T> *dest, const set<T> set1, const set<T> set2)
{
    auto end1 = set1.end();
    auto end2 = set2.end();
    auto it1 = set1.begin();
    if (it1 == end1)
        return;
    auto it2 = set2.begin();
    if (it2 == end2)
        return;
    for (;;)
    {
        it1.skipTo(*it2);
        if (it1 == end1)
            break;
        if (*it1 == *it2)
        {
            dest->push_back(*it1);
            ++it1;
        }
        it2.skipTo(*it1);
        if (it2 == end2)
            break;
        if (*it2 == *it1)
        {
            dest->push_back(*it2);
            ++it2;
        }
    }
}

它可以使用迭代器 vector 轻松扩展到任意数量的集合，并且几乎任何有序集合都可以扩展以提供所需的迭代器——排序数组、二叉树、b 树、跳过列表等。

关于c++ - 两组的有效交集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50252731/