C++中的无序集合交集

Question

这是我的代码,想知道任何想法让它更快？我的实现是蛮力,对于a中的任何元素,尝试查找它是否也在b中,如果是,则放入结果集c.任何更聪明的想法都表示赞赏.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> a = {1,2,3,4,5};
    std::unordered_set<int> b = {3,4,5,6,7};
    std::unordered_set<int> c;
    for (auto i = a.begin(); i != a.end(); i++) {
        if (b.find(*i) != b.end()) c.insert(*i);
    }
    for (int v : c) {
        std::printf("%d \n", v);
    }
}

Answer 1

渐近地,您的算法尽可能好.

在实践中,我会添加一个检查来循环两个中较小的一组,并在较大的一组中进行查找.假设合理均匀分布的哈希值,则查找std::unoredered_set需要恒定的时间.这样,您将执行更少的此类查找.

Answer 2

您可以使用 std::copy_if() 来完成

std::copy_if(a.begin(), a.end(), std::inserter(c, c.begin()), [b](const int element){return b.count(element) > 0;} );