What is the best way to obtain an index into a vector when using Iterators to loop over it.

Question

When iterating over elements of a vector it is preferred to use iterators instead of an index (see Why use iterators instead of array indices?).

std::vector<T> vec;
std::vector<T>::iterator it;
for ( it = vec.begin(); it != vec.end(); ++it )
{
   // do work
}

However, it can be necessary to use the index in the body of the loop. Which of the following would be preferable in that case, considering performance and flexibility/extensibility?

1. Revert to the indexed loop

   std::vector vec;
   size_t i;
   for ( i = 0; i < vec.size(); ++i )
   {
      // use i
   }
   

2. Calculate offset

   std::vector vec;
   std::vector::iterator it;
   for ( it = vec.begin(); it != vec.end(); ++it )
   {
      size_t i = it - vec.begin(); 
      // use i
   }
   

3. Use std::distance

   std::vector vec;
   std::vector::iterator it;
   for ( it = vec.begin(); it != vec.end(); ++it )
   {
      size_t i = std::distance( vec.begin(), it );
      // use i
   }
   

Answer 1

Using std::distance is a bit more generic since it works for all iterators, not just random access iterators. And it should be just as fast as It - vec.begin() in case of random access iterators.

It - vec.begin() is basically pointer arithmetic.

Answer 2

Revert to the indexed loop.

Basically in 90% of the cases, iterators are superior, this is one of those 10%. By using a iterator you are making the code more complex and therefore harder to understand, when the entire reason for using the iterator in the first place was to simplify your code.

Answer 3

If you're planning on using exclusively a vector, you may want to switch back to the indexed loop, since it conveys your intent more clearly than iterator-loop. However, if evolution of your program in the future may lead to a change of container, you should stick to the iterators and use std::distance, which is guaranteed to work with all standard iterators.

Answer 4

You're missing one solution: keep an index in case you need it, but don't use it as a loop condition. Works on lists too, and the costs (per loop) are O(n) and an extra register.

Answer 5

I would always tend towards keeping with iterators for future development reasons.

In the above example, if you perhaps decided to swap out std::vector for std::set (maybe you needed a unique collection of elements), using iterators and distance() would continue to work.

I pretty sure that any performance issues would be optimized to the point of it being negligible.

Answer 6

std::distance(vec.begin(), it) will give you the index it is pointing at, assuming it points into vec.

Carl

Answer 7

For vectors, I always use the integer method. Each index into the vector is the same speed as an array lookup. If I'm going to be using the value a lot, I create a reference to it, for convenience.

vector iterators can be slightly faster than an index in theory, since they're using pointer arithmetic to iterate through the list. However, usually I find that the readability is worth the minimal runtime difference.

I use iterators for other container types, and sometimes when you don't need the loop variable. But if you need the loop variable, you're not doing anything except making your loop harder to type. (I cannot wait for c++0x's auto..)