[c++] Why use iterators instead of array indices?


Answers

because you are not tying your code to the particular implementation of the some_vector list. if you use array indices, it has to be some form of array; if you use iterators you can use that code on any list implementation.

Question

Take the following two lines of code:

for (int i = 0; i < some_vector.size(); i++)
{
    //do stuff
}

And this:

for (some_iterator = some_vector.begin(); some_iterator != some_vector.end();
    some_iterator++)
{
    //do stuff
}

I'm told that the second way is preferred. Why exactly is this?




Imagine some_vector is implemented with a linked-list. Then requesting an item in the i-th place requires i operations to be done to traverse the list of nodes. Now, if you use iterator, generally speaking, it will make its best effort to be as efficient as possible (in the case of a linked list, it will maintain a pointer to the current node and advance it in each iteration, requiring just a single operation).

So it provides two things:

  • Abstraction of use: you just want to iterate some elements, you don't care about how to do it
  • Performance



Because it is more object-oriented. if you are iterating with an index you are assuming:

a) that those objects are ordered
b) that those objects can be obtained by an index
c) that the index increment will hit every item
d) that that index starts at zero

With an iterator, you are saying "give me everything so I can work with it" without knowing what the underlying implementation is. (In Java, there are collections that cannot be accessed through an index)

Also, with an iterator, no need to worry about going out of bounds of the array.




Several good points already. I have a few additional comments:

  1. Assuming we are talking about the C++ standard library, "vector" implies a random access container that has the guarantees of C-array (random access, contiguos memory layout etc). If you had said 'some_container', many of the above answers would have been more accurate (container independence etc).

  2. To eliminate any dependencies on compiler optimization, you could move some_vector.size() out of the loop in the indexed code, like so:

    const size_t numElems = some_vector.size();
    for (size_t i = 0; i 
  3. Always pre-increment iterators and treat post-increments as exceptional cases.

for (some_iterator = some_vector.begin(); some_iterator != some_vector.end(); ++some_iterator){ //do stuff }

So assuming and indexable std::vector<> like container, there is no good reason to prefer one over other, sequentially going through the container. If you have to refer to older or newer elemnent indexes frequently, then the indexed version is more appropropriate.

In general, using the iterators is preferred because algorithms make use of them and behavior can be controlled (and implicitly documented) by changing the type of the iterator. Array locations can be used in place of iterators, but the syntactical difference will stick out.




You might want to use an iterator if you are going to add/remove items to the vector while you are iterating over it.

some_iterator = some_vector.begin(); 
while (some_iterator != some_vector.end())
{
    if (/* some condition */)
    {
        some_iterator = some_vector.erase(some_iterator);
        // some_iterator now positioned at the element after the deleted element
    }
    else
    {
        if (/* some other condition */)
        {
            some_iterator = some_vector.insert(some_iterator, some_new_value);
            // some_iterator now positioned at new element
        }
        ++some_iterator;
    }
}

If you were using indices you would have to shuffle items up/down in the array to handle the insertions and deletions.




I always use array index because many application of mine require something like "display thumbnail image". So I wrote something like this:

some_vector[0].left=0;
some_vector[0].top =0;<br>

for (int i = 1; i < some_vector.size(); i++)
{

    some_vector[i].left = some_vector[i-1].width +  some_vector[i-1].left;
    if(i % 6 ==0)
    {
        some_vector[i].top = some_vector[i].top.height + some_vector[i].top;
        some_vector[i].left = 0;
    }

}



Even better than "telling the CPU what to do" (imperative) is "telling the libraries what you want" (functional).

So instead of using loops you should learn the algorithms present in stl.




The second form represents what you're doing more accurately. In your example, you don't care about the value of i, really - all you want is the next element in the iterator.




STL iterators are mostly there so that the STL algorithms like sort can be container independent.

If you just want to loop over all the entries in a vector just use the index loop style.

It is less typing and easier to parse for most humans. It would be nice if C++ had a simple foreach loop without going overboard with template magic.

for( size_t i = 0; i < some_vector.size(); ++i )
{
   T& rT = some_vector[i];
   // now do something with rT
}
'



Aside from all of the other excellent answers... int may not be large enough for your vector. Instead, if you want to use indexing, use the size_type for your container:

for (std::vector<Foo>::size_type i = 0; i < myvector.size(); ++i)
{
    Foo& this_foo = myvector[i];
    // Do stuff with this_foo
}



Indexing requires an extra mul operation. For example, for vector v, the compiler converts v[i] into &v + sizeof(int) * i.




  • If you like being close to the metal / don't trust their implementation details, don't use iterators.
  • If you regularly switch out one collection type for another during development, use iterators.
  • If you find it difficult to remember how to iterate different sorts of collections (maybe you have several types from several different external sources in use), use iterators to unify the means by which you walk over elements. This applies to say switching a linked list with an array list.

Really, that's all there is to it. It's not as if you're going to gain more brevity either way on average, and if brevity really is your goal, you can always fall back on macros.




Links