C++ 循环中 vector::size() 的性能问题 [英] Performance issue for vector::size() in a loop in C++

问题描述

在以下代码中:

std::vector<int> var;
for (int i = 0; i < var.size(); i++);

size() 成员函数是为每次循环迭代调用还是只调用一次?

Is the size() member function called for each loop iteration, or only once?

推荐答案

理论上，每次都会调用，因为for循环:

In theory, it is called each time, since a for loop:

for(initialization; condition; increment)
    body;

被扩展为类似

{
    initialization;
    while(condition)
    {
        body;
        increment;
    }
}

(注意大括号，因为初始化已经在内部范围内)

(notice the curly braces, because initialization is already in an inner scope)

在实践中，如果编译器理解你的条件的一部分在循环的所有持续时间内是不变的，并且它没有副作用，它可以足够聪明将其移出.这通常使用 strlen 和类似的东西(编译器很清楚)在没有写入其参数的循环中完成.

In practice, if the compiler understands that a piece of your condition is invariant through all the duration of the loop and it does not have side-effects, it can be smart enough to move it out. This is routinely done with strlen and things like that (that the compiler knows well) in loops where its argument isn't written.

但是必须注意，最后一个条件并不总是很容易证明；一般来说，如果容器是函数的本地容器并且从不传递给外部函数，那么这很容易；如果容器不是本地的(例如它是通过引用传递的 - 即使它是 const)并且循环体包含对其他函数的调用，编译器通常必须假设这些函数可能会改变它，从而阻塞吊装长度计算.

However it must be noted that this last condition isn't always trivial to prove; in general, it's easy if the container is local to the function and is never passed to external functions; if the container is not local (e.g. it's passed by reference - even if it's const) and the loop body contains calls to other functions, the compiler often has to assume that such functions may alter it, thus blocking the hoisting of the length calculation.

如果您知道条件的一部分评估起来昂贵"，那么手动进行优化是值得的(而这种条件通常不是，因为它通常归结为指针减法，这几乎肯定是内联的).

Doing that optimization by hand is worthy if you know that a part of your condition is "expensive" to evaluate (and such condition usually isn't, since it usually boils down to a pointer subtraction, which is almost surely inlined).

正如其他人所说，一般来说，容器最好使用迭代器，但对于 vectors，它不是那么重要，因为通过 operator[] 保证为 O(1)；实际上，对于向量，它通常是指针和(向量基数+索引)和取消引用与指针增量(前元素+1)和迭代器的取消引用.由于目标地址仍然相同，我认为您无法从缓存局部性方面从迭代器中获得任何东西(即使如此，如果您不是在紧密循环中遍历大数组，您甚至不应该注意到这样的某种改进).

as others said, in general with containers it's better to use iterators, but for vectors it's not so important, because random access to elements via operator[] is guaranteed to be O(1); actually with vectors it usually is a pointer sum (vector base+index) and dereference vs the pointer increment (preceding element+1) and dereference of iterators. Since the target address is still the same, I don't think that you can gain something from iterators in terms of cache locality (and even if so, if you're not walking big arrays in tight loops you shouldn't even notice such kind of improvements).

对于列表和其他容器，相反，使用迭代器而不是随机访问可能真的很重要，因为使用随机访问可能意味着每次遍历列表，而增加迭代器只是一个指针解引用.

For lists and other containers, instead, using iterators instead of random access can be really important, since using random access may mean walk every time the list, while incrementing an iterator is just a pointer dereference.

这篇关于C++ 循环中 vector::size() 的性能问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！