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

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
   }
   

From stackoverflow andreas buykx

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

  From QBziZ

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

  Guvante : Forgot to mention performance, generally it is safe to assume that the indexed loop would have better performance, but the performance would be very similar in both cases.

  QBziZ : I cannot say I agree. The body of the loop might contain other code that does dereference the iterator. Iterators are not meant to make your code simpler, they make your code more generic. By using the iterators you can swap the vector for list and it would still work.

  Doug T. : Also, std::map or std::set iterators are far from stupid. If I looped over all possible keys, it would probably take forever. Also, I'd have to do a O(log(n)) lookup on every key. So my loop would take O(m*log(n)). Using an iterator I could loop over the collection in O(n) time.
  From Guvante

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

  From Luc Touraille

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

  From MSalters

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

  From Alan

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

  Carl

  From Carl Seleborg

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

  From tfinniga