为什么set <int> s的std :: find(s.begin(),s.end(),val)比s.find(val)慢1000？

Question

我最近开始重新学习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在评论中询问时间,所以我std::find()在Set,List,Vector上定时set.find() (我只测量了查找 - 运行之间的差异低于10%)

Vector比List或Set执行得更好,但是set中的专门查找会获得大数据集.

 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

Answer 1

std::find是一种通用算法,给出一对迭代器可以找到一个值.如果所有它都是一对迭代器,那么找到一个值的最好方法就是线性搜索它,即O(n).

set::find是一个成员函数,std::set因此它知道它搜索的数据结构,因此可以优化搜索.排序,平衡的树具有出色的搜索行为O(log(n))