Question

In a "i < vector.size()" loop condition, is size() called each iteration?

In the following code:

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

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

 45  27810  45
1 Jan 1970

Solution

 51

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

for(initialization; condition; increment)
    body;

is expanded to something like

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

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

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.

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).

Edit: 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.

2010-10-10

Solution

 12

The size() member function is called each time, but it would be a really bad implementation that wouldn't inline it, and a strange one where it wouldn't be a simple access of a fixed datum or a subtraction of two pointers.
Anyway, you shouldn't worry yourself with such trivialities until you have profiled your application and found out that this is a bottleneck.

However, what you should pay attention to is:

  1. The correct type for a vector's index is std::vector<T>::size_type.
  2. There are types (some iterators, for example) where i++ might be slower than ++i.

Therefore, the loop should be:

for(vector<int>::size_type i=0; i<var.size(); ++i)
  ...
2010-10-10