CODEWITHSUNDEEP
c++indexingvectoriterator
andreas buykx
andreas buykx

Reputation: 12960

Obtain an index into a vector using Iterators

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
}

Upvotes: 5

Views: 5419

Answers (7)

tfinniga
tfinniga

Reputation: 6859

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

Upvotes: 0

Carl Seleborg
Carl Seleborg

Reputation: 13305

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

Carl

Upvotes: 6

Alan
Alan

Reputation: 13731

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.

Upvotes: 0

MSalters
MSalters

Reputation: 180303

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.

Upvotes: 1

Luc Touraille
Luc Touraille

Reputation: 82171

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.

Upvotes: 13

Guvante
Guvante

Reputation: 19231

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.

Upvotes: 4

QBziZ
QBziZ

Reputation: 3270

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.

Upvotes: 8

Related Questions