Incrementing Iterators: Is ++It More Efficient Than It++

How is incrementing and dereferencing the iterator faster than incrementing a separate variable and indexing it into the array?

The only way it MAY be faster, at least in unoptimized code is because you call size() member function at beginning of every iteration and it's really depends on container and type of iterator it uses. Otherwise using iterators for array-like container is same as using pointer arithmetics and which order is faster depends on optimization. Also it would help if i would be of appropriate type size to not confuse compiler by different width of values.

Range-based for loop got more invalidation issues than index-based though if you're in process of modifying same container. Because it coded in this way:

The range-based for statement

for ( for-range-declaration : for-range-initializer ) statement

is equivalent to

{
    auto &&__range = for-range-initializer ;
    auto __begin = begin-expr ;   
    auto __end = end-expr ;
    for ( ; __begin != __end; ++__begin ) {
        for-range-declaration = *__begin;
        statement
    }
}

As you see, iterators for begin and end of range are evaluated before loop and any actions taken upon the range which invalidates them would invoke an UB.

If we speak of generic idea of container and not just std::vector, for some containers operator[] may be way more expensive than iterator increment. Only a few number of standard containers have constant cost of operator[] and in case of views\ranges its cost is generally larger, non-constant or non-linear. Cost of incrementing iterators tends to be constant or linear. Costs are usually declared or can be found out during performance tests.

So main issue is not performance but correctness of code, and use of range-based for loop suggests that range wasn't changed in it. It makes harder to cause such change deliberately because all that you have access to is a reference or a copy of an element. An attempt to do so would be obvious, it would be some usage of original range. It also saves from boilerplate code of begin-expr/end-expr.

In common for-loop calling size in i < v.size() may suggest that size() could change during execution. If it's true and happens in middle of loop's body, you may find out that index is out of bound from that point.

When reviewing code not knowing author of code, If I look for source of such change, every such loop is a suspect in detected bug or crash on out-of-bound access from the moment I saw its first line followed by some non-transparent code.

Performance difference between ++iterator and iterator++?

Postincrement must return the value the iterator had BEFORE it was incrementing; so, that previous value needs to be copied somewhere before altering it with the increment proper, so it's available to return. The extra work may be a little or a lot, but it certainly can't be less than zero, compared to a preincrement, which can simply perform the incrementing and then return the just-altered value -- no copying // saving // etc necessary.

So, unless you specifically MUST have postincrement (because you're using the "value before increment" in some way), you should always use preincrement instead.

What happens if you increment an iterator that is equal to the end iterator of an STL container

Following is the quote from Nicolai Josuttis book:

Note that advance() does not check
whether it crosses the end() of a
sequence (it can't check because
iterators in general do not know the
containers on which they operate).
Thus, calling this function might
result in undefined behavior because
calling operator ++ for the end of a
sequence is not defined

In other words, the responsibility of maintaining the iterator within the range lies totally with the caller.

Why use the prefix increment form for iterators?

Why doesn't this first iterate it, then start the loop (at v.begin() + 1)?

The iteration statement is always executed at the end of each iteration. That is regardless of the type of increment operator you use, or whether you use an increment operator at all.

The result of the iteration statement expression is not used, so it has no effect on how the loop behaves. The statement:

++it;

Is functionally equivalent to the statement:

it++;

Postfix and prefix increment expressions have different behaviour only when the result of the expression is used.

---

Why use the prefix increment form for iterators?

Because the postfix operation implies a copy. Copying an iterator is generally at least as slow, but potentially slower than not copying an iterator.

A typical implementation of postfix increment:

iterator tmp(*this); // copy
++(*this);           // prefix increment
return tmp;          // return copy of the temporary
                     // (this copy can be elided by NRVO)

When the result is not used, even the first copy can be optimized away but only if the operation is expanded inline. But that is not guaranteed.

---

I wouldn't blindly use the rule "always use prefix increment with itrators". Some algorithms are clearer to express with postfix, although that is just my opinion. An example of an algorithm suitable for postfix increment:

template<class InIter, class OutIter>
OutIter copy(InIter first, InIter last, OutIter out) {
    while(first != last)
        *out++ = *first++;
    return out;
}

Why is ++i more efficient than i++?

i++ increments i and returns the initial value of i. Which means:

int i = 1;
i++; // == 1 but i == 2

But ++i returns the actual incremented value:

int i = 1;
++i; // == 2 and i == 2 too, so no need for a temporary variable

In the first case, the compiler has to create a temporary variable (when used) for returning 1 instead of 2 (in the case where it's not a constant of course but a dynamic value, a return from a call for example).

In the second case, it does not have to. So the second case is guaranteed to be at least as effective.

Often, the compiler will be able to optimize the first case into the second case, but sometimes it may not be able to.

Anyway, we're talking about highly negligible impact.

But on more complicated objects such as iterators-like objects, having a temporary state may be pretty slower if iterated millions of times.

Rule of thumb

Use prefix version unless you specifically want the postfix semantics.

What's faster, iterating an STL vector with vector::iterator or with at()?

Why not write a test and find out?

Edit: My bad - I thought I was timing the optimised version but wasn't. On my machine, compiled with g++ -O2, the iterator version is slightly slower than the operator[] version, but probably not significantly so.

#include <vector>
#include <iostream>
#include <ctime>
using namespace std;

int main() {
    const int BIG = 20000000;
    vector <int> v;
    for ( int i = 0; i < BIG; i++ ) {
        v.push_back( i );
    }

    int now = time(0);
    cout << "start" << endl;
    int n = 0;
    for(vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
        n += *it;
    }

    cout << time(0) - now << endl;
    now = time(0);
    for(size_t i = 0; i < v.size(); ++i) {
        n += v[i];
    }
    cout << time(0) - now << endl;

    return n != 0;
}

++it or it++ when iterating over a map?

Putting it to the test, I made three source files:

#include <map>

struct Foo { int a; double b; char c; };

typedef std::map<int, Foo> FMap;

### File 1 only ###

void Set(FMap & m, const Foo & f)
{
  for (FMap::iterator it = m.begin(), end = m.end(); it != end; ++it)
    it->second = f;
}

### File 2 only ###

void Set(FMap & m, const Foo & f)
{
  for (FMap::iterator it = m.begin(); it != m.end(); ++it)
    it->second = f;
}

### File 3 only ###

void Set(FMap & m, const Foo & f)
{
  for (FMap::iterator it = m.begin(); it != m.end(); it++)
    it->second = f;
}

### end ###

After compiling with g++ -S -O3, GCC 4.6.1, I find that version 2 and 3 produce identical assembly, and version 1 differs only in one instruction, cmpl %eax, %esi vs cmpl %esi, %eax.

So, take your pick and use whatever suits your style. Prefix increment ++it is probably best because it expresses your requirements most accurately, but don't get hung up about it.

Post-incrementing an iterator after de-referencing - *iter++. How is it evaluated?

I couldn't quite understand your question, but to respond to the understanding you listed: Your understanding may be correct on a particular compiler/day/build. It is unspecified whether you will insert at begin or begin + 1 (which then results in the value returned from insert being one of two different possible values) because the compiler may evaluate the arguments to insert in any order it likes. Instead of trying to work out exactly what will happen, split the code into appropriate pieces the make it perfectly clear what you're trying to do and let the optimizer take care of things for you. Almost certainly the reason it core dumped is because when you increment by two you skip over end and never detect that you passed the end of the container.

I feel I should also point out that "luckily" there's a sequence point after the evaluation of function arguments, or begin = target.insert(begin, *begin++); would be undefined behavior with two writes to begin and no intervening sequence point (for example i = i++ is UB).

---

Related Topics