C ++中的无序集合交集

本文介绍了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.