为什么set<int> s的std::find( s.begin()，s.end()，val )比s.find(val)慢1000倍？
为什么set<int> s的std::find( s.begin()，s.end()，val )比s.find(val)慢1000倍？
提问于 2018-08-29 04:47:20
我最近开始重新学习C++，因为我已经十多年没有用C++编写代码了。我很少使用STL，即使我在SGI工作的时候也是如此，我想掌握它。我已经订购了一本书，目前正在运行不同的在线教程。
其中一个教程介绍了std::find(begin(),end(),value)，我对它在我编写的测试代码中的速度感到震惊。经过反复试验，我发现s.find(value)显然是我应该使用的。
为什么代码中的第一个查找速度如此之慢？
set<int> s;
for (int i = 0; i < 100000; i++)
s.insert(rand());
for (int i = 0; i < 10000; i++) {
int r = rand();
//first find is about 1000x slower than the next one
auto iter1 = std::find(s.begin(), s.end(), r);
auto iter2 = s.find(r);
}编辑:添加计时实验结果
@juanchopanza在评论中询问了时间，所以我在Set，List，Vector和set.find()上对std::find()进行了计时(我只测量了find -运行之间的变异小于10%)
Vector的性能比List或Set要好得多，但set中的专业find在大数据集上胜出。
Elements Vector List Set | Set.Find()
10 0.0017 0.0017 0.0020 | 0.0017
100 0.0028 0.0051 0.0120 | 0.0019
1000 0.0105 0.0808 0.1495 | 0.0035
10000 0.0767 0.7486 2.7009 | 0.0068
100000 0.2572 2.4700 6.9636 | 0.0080
1000000 0.2674 2.5922 7.0149 | 0.0082
10000000 0.2728 2.6485 7.0833 | 0.0082回答 1
Stack Overflow用户
回答已采纳
发布于 2018-08-29 04:55:50
std::find是一种通用算法，给定一对迭代器就可以找到一个值。如果给定的只是一对迭代器，那么找到一个值的最好方法就是线性搜索它，即O(n)。
set::find是std::set的一个成员函数，因此它知道它所搜索的数据结构，从而可以优化搜索。排序平衡树具有O(log(n))的优良搜索性能。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52065994
复制相关文章
相似问题