stl容器中的end()操作是否会耗费大量资源?

20

https://doc-snapshots.qt.io/qtcreator-extending/coding-style.html上推荐按照以下方式编写for循环:

Container::iterator end = large.end();
for (Container::iterator it = large.begin(); it != end; ++it) {
        //...;
}

取代

for (Container::iterator it = large.begin(); it != large.end(); ++it) {
        //...;
}

由于我很少在代码中看到这种风格,所以我想知道对于遍历STL容器的大型循环,连续调用end()是否会增加明显的运行时开销,或者编译器是否已经优化了这种情况。

编辑: 正如许多非常好的评论所指出的:仅当循环内的代码不修改end迭代器时,此问题才有效。否则,重复调用end是必需的。


12
顺便提一下:我甚至会选择使用 for (Container::iterator it = large.begin(), end = large.end(); it != end; ++it) { ... },以便将变量 end 的范围限制在仅限于 for 循环中。 - haffax
C#和Java开发人员编写此类循环以让JITer进行优化(每次迭代少一次检查)。但似乎对于C++并非如此。 - Lukasz Madon
4
C++开发者只需编写for_each(begin(c), end(c), [](){});,循环是给库编写者用的 :P - MSalters
1
@MSalter:假设是C+11开发人员。使用例如boost的lambda表达式并不适合胆小的人。 - Martin
7个回答

18

C++11标准(§ 23.2.1)规定end的复杂度为O(1),因此符合规范的实现将具有相同的性能特征。

尽管如此,除非编译器可以证明end的返回值永远不会改变,否则将end从循环中提取出来可能会比一些固定数量快(正如Steve Jessop所评论的那样,有许多变量可能会影响是否正确)。

尽管在某些特定情况下绝对没有性能差异,但将这种测试从循环中提取出来是一个好习惯。正如@pmr所说,更好的习惯是利用标准算法,从而完全避免了这个问题。


7
即使编译器无法证明end的值是循环不变的,提升它可能也不会更快。原因是即使它被提升了,该值仍然必须存储在一个变量中,这个变量可能存在于堆栈中。容器可能也存在于堆栈中,在这种情况下,从容器的某个数据成员中读取其 end 值很可能与从变量中读取提升后的 end 值完全相同。如果容器是通过引用传递的,则可能会有额外的间接性,这可能会稍微慢一些。 - Steve Jessop
@SteveJessop:感谢您的深入评论,我已经更改措辞,以避免可能留下错误印象。除此之外,在我看来,我们(人类)真的不应该把这件事分得太细,因为几乎不可能预测出如此微小差距的性能差异。 - Jon
2
我同意我们无法预测这些微小的差异。我并不完全同意把这些测试提升上去是一个好习惯。对于某些人来说,这可能会提高可读性(两行短小明了,而不是一行很长),否则,这只是一种投机的优化,不值得为此混乱代码。如果提升减少了整个操作的复杂度或者明显将成为循环中执行的重要工作的一部分,那么我会有所投机地做。否则,我不会这样做,尽管当使用算法或基于范围的 for 循环时,我也不反对免费使用。 - Steve Jessop
感谢您的详细回答:由于评论中也包含非常好的信息(感谢Steve),因此我选择了这个答案。在阅读Steve的笔记后,我有一个想法:由于C++11允许在常量迭代器上进行删除操作(在我看来非常好),如果将end放在循环外部,可能会引入错误,如果以后有人决定在循环内修改容器。虽然这种情况不太可能发生,但仍然是一种可能的错误来源,可以避免。 - Martin
@Martin:我一直认为,即使代码有错误,它也至少是明确错误的。而对于注释,却不能这样说。 ;^) - mcmcc
显示剩余2条评论

7

这与 end 很耗费时间的说法无关,更多是关于编译器能否看到 end 在循环体中不会因为副作用而改变(它是循环不变量)。

按照标准要求,end 的复杂度必须是常数。请参见N3337中的表格96和23.2.1节。

使用标准库算法可以很好地规避整个困境。


3

如果您计划在迭代时修改集合,则必须使用第二种方式(末尾可以更改)-否则,第一种方式在理论上稍微快一点。不过我怀疑这不会有什么明显的区别。


2
实际上,end()方法是内联的。第二个不要每次都调用它,我认为end()不会造成任何性能延迟。

0

std::vector.end() (例如) 返回一个迭代器。在第二个循环中,您在每次循环时创建一个对象。编码标准告诉您,如果不需要创建对象,则不要创建对象。编译器可能会聪明地为您优化代码,但这并不保证。更好的解决方案是使用STL算法。它们已经被优化过了,您的代码将更易读。请注意,仅当您不修改集合时,两个循环才是等效的。

P.S. 很可能性能差异非常小


1
调用 end() 的可能是内联的,operator!= 的调用也是如此。在这个层面上,我们正在比较两个指针。拥有一个单独的副本不太可能提高性能。 - Bo Persson
我同意最终的性能结果不会有太大的差异,但是我喜欢关注对象的增殖这个想法。 - Alessandro Teruzzi

0

对于现在阅读此文的任何人来说,这个问题已经成为了一个无关紧要的问题,因为C++11已经解决了这个问题。

我不确定这个回答是否合格,因为它实际上并没有回答问题的重点。但是我认为指出这里提出的问题在C++11程序员的实践中很少遇到是有效的,而且几年前我肯定会觉得这个回答很有用。因此,这个回答是针对那些只想知道STL容器(vectorlistdeque等)中迭代所有元素的最佳方法的读者。

假设OP想要访问容器中的每个元素,我们可以通过编写基于范围的for循环轻松地绕过整个定义end是否比调用Container::end()更快的问题:

Container container; // my STL container that has been filled with stuff

// (note that you can replace Container::value_type with the value in the container)

// the standard way
for (Container::value_type element : container) {
    // access each element by 'element' rather than by '*it'
}

// or, if Container::value_type is large
Container container; // fill it with something
for (Container::value_type& element : container) {
    //
}

// if you're lazy
Container container; // fill it with something
for (auto element : container) {
    //
}

楼主问的是在简洁性和声明变量end并在每次迭代时进行比较的性能之间的权衡是否值得。由于基于范围的for循环提供了一个简单、易于编写和阅读的替代方案,而且在内部声明了一个end迭代器,而不是在每一步调用Container::end()方法,因此我们需要考虑这个问题的情况已经减少到了有限的情况。

根据cppreference.com的说法,基于范围的for循环将产生与以下代码具有相同的副作用:

{
  auto && __range = range_expression ; 
  for (auto __begin = begin_expr,
        __end = end_expr; 
      __begin != __end; ++__begin) { 
    range_declaration = *__begin; 
    loop_statement 
  } 
} 

-3

这取决于具体的实现方式,但我认为end()不会导致太大的性能延迟。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接