C ++中的无序集合交集 [英] unordered set intersection in C++

问题描述

这是我的代码，想知道有什么想法可以使它更快?我的实现是蛮力的，对于a中的任何元素，请尝试查找是否也在b中，如果是，则将其放入结果集c中.任何更聪明的想法都将受到赞赏.

Here is my code, wondering any ideas to make it faster? My implementation is brute force, which is for any elements in a, try to find if it also in b, if so, put in result set c. Any smarter ideas is appreciated.

#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);
    }
}

推荐答案

渐近而言，您的算法已尽其所能.

Asymptotically, your algorithm is as good as it can get.

在实践中，我将添加一个检查以循环访问两组中较小的一组，并在较大的一组中进行查找.假设哈希值合理地均匀分布，则在 std :: unoredered_set 中进行查找需要花费固定的时间.这样，您将减少执行此类查找的次数.

In practice, I'd add a check to loop over the smaller of the two sets and do lookups in the larger one. Assuming reasonably evenly distributed hashes, a lookup in a std::unoredered_set takes constant time. So this way, you'll be performing fewer such lookups.

这篇关于C ++中的无序集合交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！