代码之家 › 专栏 › 技术社区 › Ves

对于集合<int>s,为什么std::find(s.begin(),s.end(),val)比s.find(val)慢1000倍?

std set find c++

Ves · 技术社区 · 6 年前

我最近开始重新学习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);
}

编辑:添加计时实验结果

std::find() 关于集合、列表、向量和 set.find()

Vector的性能比List或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

3 回复 | 直到 6 年前

Mike Vine 6 年前

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

set::find std::set 因此,它知道其搜索的数据结构,因此可以优化搜索。排序后的平衡树具有很好的O(log(n))搜索性能

Quimby 6 年前

来扩展我的评论。

因为 set::find 包含有关搜索范围中元素的详细信息。它知道它(可能)实现为一个排序的二叉树,并且可以在对数时间内搜索它。

std::find 另一方面只有两个 双向的 ~~把电视机还给我了吗 随机存取 迭代器, 标准::查找~~

Community kfsone 4 年前

第一个原因是 std::find std::set.find 以对数时间搜索的形式指定。

但如果你换了 标准::查找 具有 std::equal_range 标准::查找

为什么是 `标准::等量程` 集合迭代器的速度慢得可笑?

std::set 迭代器是双向迭代器。这意味着他们允许前进一步,或者后退一步。

标准::等量程 关于双向迭代器 极其缓慢

这个 标准::集 很快找到元素。它可以,基本上,得到一个范围的中点非常快。

当您访问时,C++不会公开此树结构。 标准::集 通过它的迭代器。如果是的话,可能会有类似的行动 std::somewhere_between( start, finish ) 在O(1)时间内得到一个迭代器 start 和 finish ,返回 完成 如果不存在这样的迭代器。

这样的操作实际上在树结构实现上非常便宜 标准::集 .

但是这个操作并不存在。所以呢 std::equal_range( begin(set), end(set) )

可能不会暴露像 std::somewhere_between 对于排序的关联容器,某些集合/映射实现更高效;许多容器使用特殊节点来替换某些叶大小写。也许你需要访问这个特殊的节点来有效地对树进行二叉搜索。

但我严重怀疑不做手术是否值得。通过这个操作,你可以在 标准::集 或 std::map 没有它,你什么也得不到。

对于集合<int>s,为什么std::find(s.begin(),s.end(),val)比s.find(val)慢1000倍?

为什么是 标准::等量程 集合迭代器的速度慢得可笑?

为什么是 `标准::等量程` 集合迭代器的速度慢得可笑?