对于stl容器,end()是一个昂贵的操作

Question

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

代替

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

由于我很少在任何代码中看到这种风格,我想知道end()的连续调用是否真的为stl容器上的大型循环添加了明显的运行时开销,或者编译器是否已经优化了这种情况.

编辑:许多非常好的评论指出:这个问题仅在循环内的代码不修改结束迭代器时才有效.否则,当然重复的结束呼叫是强制性的.

Answer 1

C++ 11标准(第23.2.1节)要求end具有O(1)复杂性,因此符合标准的实现对两个版本都具有相同的性能特征.

也就是说,除非编译器能够证明返回值end永远不会改变,否则拉出end循环可能会更快一些不变量(正如Steve Jessop评论的那样,有很多变量可以影响这是否真实) .

尽管如此,即使在一个特定情况下绝对没有性能差异,将这些测试拉出循环是一个很好的习惯.一个更好的习惯就是利用@pmr所说的标准算法,它完全回避了这个问题.

即使编译器无法证明`end`的值是循环不变的,提升它仍然可能不会更快.原因只是即使它被提升,该值仍然必须存储在一个变量中,该变量很可能在堆栈中.容器也可能在堆栈中,在这种情况下,从容器中的某个数据成员读取它的`end`可能与从变量中读取提升的`end`完全相同.如果容器已经通过引用传递,那么可能存在额外的间接,并且可能稍微慢一些. (7认同)
我同意我们无法预测这些微小差异.我真的不同意提升这些测试是个好习惯.对于某些人来说,它可能会提高可读性(2个较短的行而不是1个较长的行),否则它是一个推测性的优化,并不值得为IMO的代码混乱.如果提升机降低了整个操作的复杂性,或者它显然将成为循环中所做工作的重要部分,那么我会以推测的方式进行.否则我不会,虽然我也不反对在使用算法或基于范围的时候"免费"使用它. (2认同)

Answer 2

这不仅仅是end代价高昂,更多的是关于编译器看到end不会因循环体中的副作用而改变的能力(它是一个循环不变量).

end标准要求复杂性不变.见N3337中的表96 23.2.1.

使用标准库算法很好地避免了整个困境.