C++中的无序集交集
C++中的无序集交集
提问于 2017-12-20 08:02:56
这是我的代码，想知道让它更快的方法吗？我的实现是蛮力，对于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);
}
}回答 4
Stack Overflow用户
回答已采纳
发布于 2017-12-20 08:20:01
渐近来说，你的算法是它所能得到的最好的。
在实践中，我会添加一个检查来循环这两个集合中较小的集合，并在较大的集合中进行查找。假定合理分布的散列，std::unoredered_set中的查找需要恒定的时间。因此，这样，您将执行较少这样的查找。
Stack Overflow用户
发布于 2018-12-07 15:29:55
您可以使用std::copy_if()来完成它。
std::copy_if(a.begin(), a.end(), std::inserter(c, c.begin()), [b](const int element){return b.count(element) > 0;} );Stack Overflow用户
发布于 2017-12-20 08:59:35
对于无序集，您的算法是一样好的。但是，如果使用std::set (它使用二叉树作为存储)或更好的排序std::vector，则可以做得更好。算法应该类似于：
- 让迭代器到达
a.begin()和b.begin() - 如果迭代器指向相等的元素，则添加到交集并增加两个迭代器。
- 否则，增加指向最小值的迭代器。
- 去2楼。
两者都应该是O(n)时间，但使用正常集可以避免计算散列或哈希冲突导致的任何性能下降。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/47901339
复制相关文章
相似问题
腾讯云开发者
