end() 能否成为 stl 容器的昂贵操作

2022-01-24 00:00:00 performance containers c++ stl

关于 https://doc-snapshots.qt.io/qtcreator-extending/coding-style.html 推荐写for循环如下:

On https://doc-snapshots.qt.io/qtcreator-extending/coding-style.html it is recommended to write for loops like the following:

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 容器上的大型循环增加了明显的运行时开销,或者编译器是否已经优化了这种情况.

Since I have rarely seen this style in any code, I would like to know whether the consecutive call of end() really adds a noticeable run-time overhead for large loops over stl containers or whether compilers already optimize such cases.

正如许多非常好的评论所指出的那样:这个问题只有在循环内的代码不修改结束迭代器时才有效.否则,end 的重复调用当然是强制性的.

As many of to very good comments pointed out: This question is only valid if the code inside the loop does not modify the end iterator. Otherwise of course the repeated call of end is mandatory.

推荐答案

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

The C++11 standard (§ 23.2.1) mandates that end has O(1) complexity, so a conforming implementation would have the same performance characteristics for both versions.

也就是说,除非编译器可以证明 end 的返回值永远不会改变,否则将 end 拉出循环可能以一定数量的速度更快(正如史蒂夫・杰索普所说,有很多变量可以影响这是否正确).

That said, unless the compiler can prove that the return value of end will never change then pulling end out of the loop might be faster by some constant quantity (as Steve Jessop comments, there are lots of variables that can influence whether this is true or not).

尽管如此,即使在某个特定情况下绝对没有性能差异,将此类测试排除在循环之外也是一个好习惯.一个更好的习惯是使用@pmr 所说的标准算法,这完全回避了这个问题.

Still, even if in one particular case there is absolutely no performance difference, pulling such tests out of the loop is a good habit to get into. An even better habit to get into is to utilize standard algorithms as @pmr says, which sidesteps the issue entirely.

相关文章