C++ 迭代器和循环优化

C++ iterators & loop optimization

提问by Quantum7

I see a lot of c++ code that looks like this:

我看到很多 C++ 代码看起来像这样：

for( const_iterator it = list.begin(),
     const_iterator ite = list.end();
     it != ite; ++it)

As opposed to the more concise version:

与更简洁的版本相反：

for( const_iterator it = list.begin();
     it != list.end(); ++it)

Will there be any difference in speed between these two conventions? Naively the first will be slightly faster since list.end() is only called once. But since the iterator is const, it seems like the compiler will pull this test out of the loop, generating equivalent assembly for both.

这两个约定在速度上会有什么区别吗？因为 list.end() 只被调用一次，所以第一个会稍微快一点。但是由于迭代器是 const，编译器似乎会将这个测试拉出循环，为两者生成等效的程序集。

采纳答案by j_random_hacker

I'll just mention for the record that the C++ standard mandates that calling begin()and end()on anycontainer type (be it vector, list, mapetc.) must take only constant time. In practice, these calls will almost certainly be inlined to a single pointer comparison if you compile with optimisations turned on.

我就提了，在C ++标准授权呼叫记录begin()，并end()在任何容器类型（可能是vector，list，map等）必须采取唯一不变的时间。在实践中，如果您在打开优化的情况下编译，这些调用几乎肯定会被内联到单个指针比较中。

Note that this guarantee does not necessarily hold for additional vendor-supplied "containers" that do not actually obey the formal requirements of being a container laid out in the chapter 23 of the standard (e.g. the singly-linked list slist).

请注意，此保证不一定适用于其他供应商提供的“容器”，这些“容器”实际上不符合标准第 23 章中规定的容器的正式要求（例如单向链表slist）。

回答by newacct

The two versions are not the same though. In the second version it compares the iterator against list.end()every time, and what list.end()evaluates to might change over the course of the loop. Now of course, you cannot modify listthrough the const_iterator it; but nothing prevents code inside the loop from just calling methods on listdirectly and mutating it, which could (depending on what kind of data structure listis) change the end iterator. It might therefore be incorrect in some circumstances to store the end iterator beforehand, because that may no longer be the correct end iterator by the time you get to it.

不过这两个版本不太一样。在第二个版本中，它list.end()每次都将迭代器与迭代器进行比较，并且list.end()评估结果可能会在循环过程中发生变化。现在当然，您不能通过listconst_iterator 进行修改it；但是没有什么可以阻止循环内的代码list直接调用方法并对其进行变异，这可能（取决于数据结构的list类型）改变结束迭代器。因此，在某些情况下，预先存储结束迭代器可能是不正确的，因为当您到达它时，它可能不再是正确的结束迭代器。

回答by Adam Rosenfield

The first one will probably almost always be faster, but if you think this will make a difference, always profile firstto see which is faster and by how much.

第一个可能几乎总是更快，但如果您认为这会有所作为，请始终首先分析哪个更快，速度更快。

The compiler will probably be able to inline the call to end()in both cases, although if end()is sufficiently complicated, it may opt not to inline it. However, the key optimization is whether or not the compiler can perform loop-invariant code motion. I would posit that in most cases, the compiler can't be certain that the value of end()won't change during the iteration of the loop, in which case it has no choice but to call end()after each iteration.

编译器可能能够end()在两种情况下内联对 的调用，但如果end()足够复杂，它可能会选择不内联它。然而，关键的优化是编译器是否可以执行循环不变代码运动。我认为在大多数情况下，编译器不能确定 的值end()在循环迭代期间不会改变，在这种情况下，它别无选择，只能end()在每次迭代后调用。

回答by Greg Hewgill

I would choose the option that is most concise and readable. Don't try to second guess the compiler and the optimisations it might perform. Remember that the vast majority of your code will have absolutely no effect on overall performance, so only if this is in a performance critical section of code should you spend the time to profile it and choose an appropriately efficient source representation.

我会选择最简洁易读的选项。不要试图再次猜测编译器及其可能执行的优化。请记住，您的绝大多数代码绝对不会对整体性能产生影响，因此只有当这是代码的性能关键部分时，您才应该花时间对其进行分析并选择适当有效的源代码表示。

With specific reference to your example, the first version makes a copyof the end()iterator, invoking whatever code runs for the copy constructor of the iterator object. STL containers generally contain inline end()functions, so the compiler has plenty of opportunity to optimise the second version even if you're not trying to help it out. Which one is best? Measure them.

具体参照你的例子，第一个版本做一个副本中的end()迭代器，调用任何代码运行的迭代器对象的拷贝构造函数。STL 容器通常包含内联end()函数，因此编译器有很多机会优化第二个版本，即使您不试图帮助它。哪一个最好？测量它们。

回答by Mark Ransom

You can make the first version more concise and get the best of both:

您可以使第一个版本更简洁并充分利用两者：

for( const_iterator it = list.begin(), ite = list.end();
     it != ite; ++it)

P.S. The iterators aren't const, they're iterators to a const reference. There's a big difference.

PS 迭代器不是常量，它们是常量引用的迭代器。有很大的不同。

回答by Shing Yip

Consider this example:

考虑这个例子：

for (const_iterator it = list.begin(); it != list.end(); ++list)
{
    if (moonFull())
        it = insert_stuff(list);
    else
        it = erase_stuff(list);
}

in this case, you NEED to call list.end() in the loop, and the compiler isn't going to optimize that away.

在这种情况下，您需要在循环中调用 list.end()，并且编译器不会对其进行优化。

Other cases where the compiler can prove that end() is always returning the same value, optimization can take place.

在编译器可以证明 end() 始终返回相同值的其他情况下，可以进行优化。

If we are talking about STL containers, than i think any good compiler can optimize away multiple end() calls when multiple end() calls is not needed for the programming logic. However, if you have a custom container and implementation of end() is not in the same translation unit, than optimization will have to happen at link time. I know very little about link time optimization, but i'll bet most linkers will not do such optimization.

如果我们谈论的是 STL 容器，那么当编程逻辑不需要多个 end() 调用时，我认为任何好的编译器都可以优化多个 end() 调用。但是，如果您有自定义容器并且 end() 的实现不在同一个翻译单元中，则必须在链接时进行优化。我对链接时间优化知之甚少，但我敢打赌大多数链接器不会进行此类优化。

回答by Avery Lee

The compiler might be able to optimize the second into the first, but that assumes that the two are equivalent, i.e. end() actually is constant. A slightly more problematic issue is that the compiler may be unable to deduce that the end iterator is constant due to possible aliasing. However, assuming that the call to end() is inlined, the difference is just a memory load.

编译器可能能够将第二个优化为第一个，但前提是两者是等价的，即 end() 实际上是常量。一个稍微有点问题的问题是，由于可能存在别名，编译器可能无法推断出结束迭代器是常量。然而，假设对 end() 的调用是内联的，区别只是内存负载。

Note that this assumes that the optimizer is enabled. If the optimizer is not enabled, as is often done in debug builds, then the second formulation will involve N-1 more function calls. In current versions of Visual C++, debug builds will also incur additional hits due to function prolog/epilog checks and heavier debug iterators. Therefore, in STL heavy code, defaulting to the first case can prevent code from being disproportionately slow in debug builds.

请注意，这假定优化器已启用。如果未启用优化器，就像在调试版本中经常做的那样，那么第二个公式将涉及 N-1 多个函数调用。在当前版本的 Visual C++ 中，由于函数 prolog/epilog 检查和更重的调试迭代器，调试版本也会产生额外的命中。因此，在 STL 繁重的代码中，默认为第一种情况可以防止代码在调试版本中异常缓慢。

Insertion and removal within the loop are a possibility, as others have pointed out, but with this style of loop I find that unlikely. For one thing, node-based containers -- list, set, map -- don't invalidate end() on either operation. Second, the iterator increment frequently has to be moved in-loop to avoid invalidation problems:

正如其他人所指出的那样，在循环中插入和移除是可能的，但是对于这种循环，我发现不太可能。一方面，基于节点的容器——list、set、map——不会使 end() 对任一操作无效。其次，迭代器增量必须经常在循环中移动以避免失效问题：

   // assuming list -- cannot cache end() for vector
   iterator it(c.begin()), end(c.end());
   while(it != end) {
       if (should_remove(*it))
           it = c.erase(it);
       else
           ++it;
   }

Thus, I consider a loop that claims to call end() for mutate-during-loop reasons and still has ++it in the loop header to be suspect.

因此，我认为一个循环由于循环中的 mutate-during-loop 原因而声称调用 end() 并且在循环头中仍然有 ++it 值得怀疑。

回答by user15071

Aah, people seem to be making guesses. Open up your code in the debugger & you will see that the calls to begin(), end() etc everything is optimized away. There is no need to use version 1. Tested with Visual C++ compiler fullopt.

啊，人们似乎在猜测。在调试器中打开您的代码，您将看到对 begin()、end() 等所有内容的调用都被优化掉了。无需使用版本 1。已使用 Visual C++ 编译器 fullopt 进行测试。

回答by Mike Dunlavey

1. Sample it under stress conditions and see if you're in ** this code very often ***.
   If not, it doesn't matter.

2. If you are, look at the disassembly, or single-step it.
   That's how you can tell which is faster.

1. 在压力条件下对其进行采样，看看您是否经常使用 ** 这段代码 ***。
   如果没有，也没关系。

2. 如果你是，看看拆卸，或单步执行。
   这样你就可以知道哪个更快。

You gotta be careful of these iterators.
They may get optimized into nice machine code, but often enough they don't, and become time hogs.

你必须小心这些迭代器。
它们可能会被优化为漂亮的机器代码，但通常情况下它们不会，并成为时间猪。

** (Where "in" means actually in it, or being called from it.)

**（其中“in”的意思是实际在其中，或从其中调用。）

*** (Where "often" means a significant percentage of the time.)

***（其中“经常”是指大部分时间。）

ADDED: Don't just see how many times per second the code is executed. It could be 1,000 times a second and still be using less than 1% of the time.

补充：不要只看代码每秒执行多少次。它可能是每秒 1,000 次，但仍然使用不到 1% 的时间。

Don't time how long it takes either. It could take a millisecond and still be using less than 1% of the time.

也不要计算需要多长时间。它可能需要一毫秒，并且仍然使用不到 1% 的时间。

You could multiply the two, to get a better idea, but that only works if they're not too skewed.

您可以将两者相乘，以获得更好的主意，但这仅在它们不太倾斜时才有效。

Sampling the call stackwill tell you if it uses a high enough percentage of time to matter.

对调用堆栈进行采样将告诉您它是否使用了足够高的时间百分比。

回答by aJ.

I always preferred the first one. Though with inline functions, compiler optimizations and relatively smaller container size ( in my case it's normally max 20-25 items) it really does not make any large difference with respect to performace.

我一直更喜欢第一个。尽管使用内联函数、编译器优化和相对较小的容器大小（在我的情况下，通常最多 20-25 个项目），它在性能方面确实没有太大区别。

const_iterator it = list.begin();
const_iterator endIt = list.end();

for(; it != endIt ; ++it)
{//do something
}

But recently I am using more of std::for_eachwherever it's possible. Its optimized looping which helps to make the code look more readable than other two.

但最近我在任何可能的地方使用更多的std::for_each。它的优化循环有助于使代码看起来比其他两个更具可读性。

std::for_each(list.begin(), list.end(), Functor());

I will use the loop only when std::for_eachcannot be used. (for ex: std::for_eachdoes not allow you to break the loop unless an exception is thrown).

我只会在std::for_each无法使用时使用循环。（例如：std::for_each除非抛出异常，否则不允许您中断循环）。