Efficiency of vector index access vs iterator access

Question

I have question to correct my understanding of efficiency of accessing elements of a vector by using index access (with operator []) or using an iterator.

My understanding is "iterator" is more efficient than "index access". (also I think vector::end() is more efficient than vector::size()).

Now I wrote sample code measure it (under Windows 7 using Cygwin, with g++ 4.5.3)

The index access loop version (formerly labeled as random access):

int main()
{
  std::vector< size_t > vec ( 10000000 );
  size_t value = 0;

  for( size_t x=0; x<10; ++x )
  {
    for ( size_t idx = 0; idx < vec.size(); ++idx )
    {
      value += vec[idx];
    }
    return value;
  }
}

The iterator loop code is this:

    for (std::vector< size_t >::iterator iter = vec.begin(); iter != vec.end(); ++iter) {
        value = *iter;
    }

I am surprised to see that the "index access" version is much quicker. I used the time command to "measure". The numbers were :

results using g++ source.cpp (no optimizations) index access

real 800ms

iterator access

real 2200ms

Do these numbers make sense? (I repeated the runs multiple times) And I wondered what details I miss and why I am mistaken...

results using g++ -O2 index access, time real: ~200ms

iterator access, time real: ~200ms

I repeated tests on different platform (amd64 w/ g++ and power7 w xlC) and see that all the time I used optimized code the example programs have similar execution time.

edit changed code to add values ( value += *iter ) instead of just using assignment. Added details about compiler options. Added new numbers for using -O2. *edit2 changed title correcting "iterator efficiency" to "accesses efficiency".

Answer 1

Without seeing the test harnesses, the compiler options, and how you measured the time, it's hard to say anything. Also, a good compiler may be able eliminate the loop in one case or the other, since the loop has no effect on the value returned. Still, depending on the implementation, it wouldn't surprise me to see iterators significantly faster than indexing (or vice versa).

With regards to your "understanding", there's nothing inherent about the type of iterator and its performance. You can write forward iterators which are very fast, or very slow, just as you can write random access iterators which are very fast or very slow. Globally, the types of data structures which will support random access iterators are likely to have better locality than those which don't, which might work in favor of random access iterators; but that's really not enough to be able to make any reasonable generalizations.

Answer 2

When I compile both programs with -O2 (Linux, GCC 4.6.1), they run equally fast.

Then: your first program is not using iterators, it is using indices. These are different concepts.

Your second program is in fact using random access iterators, because that is what std::vector<T>::iterators are. The restrictions on std::vector are designed in such a way that an iterator can be implemented as a simple pointer into the dynamic array that a vector encapsulates.

begin should be just as fast as size. The only difference between the two in a typical implementation of std::vector is that end might need to compute begin() + size(), though size might also be implemented as (roughly) end() - begin(). The compiler might optimize both away in the loop, though.