Why use iterators instead of array indices?

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?

Answer 1

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.

Answer 2

I don't think it makes much difference for a vector. I prefer to use an index myself as I consider it to be more readable and you can do random access like jumping forward 6 items or jumping backwards if needs be.

I also like to make a reference to the item inside the loop like this so there are not a lot of square brackets around the place:

for(size_t i = 0; i < myvector.size(); i++)
{
    MyClass &item = myvector[i];

    // Do stuff to "item".
}

Using an iterator can be good if you think you might need to replace the vector with a list at some point in the future and it also looks more stylish to the STL freaks but I can't think of any other reason.

Answer 3

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.

Answer 4

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

Answer 5

The first form is efficient only if vector.size() is a fast operation. This is true for vectors, but not for lists, for example. Also, what are you planning to do within the body of the loop? If you plan on accessing the elements as in

T elem = some_vector[i];

then you're making the assumption that the container has operator[]() defined. Again, this is true for vector but not for other containers.

The use of iterators bring you closer to container independence. You're not making assumptions about random-access ability or fast size() operation, only that the container has iterator capabilities.

You could enhance your code further by using standard algorithms. Depending on what it is you're trying to achieve, you may elect to use std::for_each(), std::transform() and so on. By using a standard algorithm rather than an explicit loop you're avoiding re-inventing the wheel. Your code is likely to be more efficient (given the right algorithm is chosen), correct and reusable.

Answer 6

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.

Answer 7

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.

Answer 8

It's part of the modern C++ indoctrination process. Iterators are the only way to iterate most containers, so you use it even with vectors just to get yourself into the proper mindset. Seriously, that's the only reason I do it - I don't think I've ever replaced a vector with a different kind of container.

---

Wow, this is still getting downvoted after three weeks. I guess it doesn't pay to be a little tongue-in-cheek.

I think the array index is more readable. It matches the syntax used in other languages, and the syntax used for old-fashioned C arrays. It's also less verbose. Efficiency should be a wash if your compiler is any good, and there are hardly any cases where it matters anyway.

Even so, I still find myself using iterators frequently with vectors. I believe the iterator is an important concept, so I promote it whenever I can.

Answer 9

During iteration you don't need to know number of item to be processed. You just need the item and iterators do such things very good.

Answer 10

I'm going to be the devils advocate here, and not recommend iterators. The main reason why, is all the source code I've worked on from Desktop application development to game development have i nor have i needed to use iterators. All the time they have not been required and secondly the hidden assumptions and code mess and debugging nightmares you get with iterators make them a prime example not to use it in any applications that require speed.

Even from a maintence stand point they're a mess. Its not because of them but because of all the aliasing that happen behind the scene. How do i know that you haven't implemented your own virtual vector or array list that does something completely different to the standards. Do i know what type is currently now during runtime? Did you overload a operator I didn't have time to check all your source code. Hell do i even know what version of the STL your using?

The next problem you got with iterators is leaky abstraction, though there are numerous web sites that discuss this in detail with them.

Sorry, I have not and still have not seen any point in iterators. If they abstract the list or vector away from you, when in fact you should know already what vector or list your dealing with if you don't then your just going to be setting yourself up for some great debugging sessions in the future.

Answer 11

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.

Answer 12

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;

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;
    }

}

Answer 13

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.

Answer 14

For container independence

Answer 15

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
}
'

Answer 16

I probably should point out you can also call

std::for_each(some_vector.begin(), some_vector.end(), &do_stuff);

Answer 17

Separation of Concerns

It's very nice to separate the iteration code from the 'core' concern of the loop. It's almost a design decision.

Indeed, iterating by index ties you to the implementation of the container. Asking the container for a begin and end iterator, enables the loop code for use with other container types.

Also, in the std::for_each way, you TELL the collection what to do, instead of ASKing it something about its internals

The 0x standard is going to introduce closures, which will make this approach much more easy to use - have a look at the expressive power of e.g. Ruby's [1..6].each { |i| print i; }...

Performance

But maybe a much overseen issue is that, using the for_each approach yields an opportunity to have the iteration parallelized - the intel threading blocks can distribute the code block over the number of processors in the system!

Note: after discovering the algorithms library, and especially foreach, I went through two or three months of writing ridiculously small 'helper' operator structs which will drive your fellow developers crazy. After this time, I went back to a pragmatic approach - small loop bodies deserve no foreach no more :)

A must read reference on iterators is the book "Extended STL".

The GoF have a tiny little paragraph in the end of the Iterator pattern, which talks about this brand of iteration; it's called an 'internal iterator'. Have a look here, too.

Answer 18

After having learned a little more on the subject of this answer, I realize it was a bit of an oversimplification. The difference between this loop:

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

And this loop:

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

Is fairly minimal. In fact, the syntax of doing loops this way seems to be growing on me:

while (it != end){
    //do stuff
    ++it;
}

Iterators do unlock some fairly powerful declarative features, and when combined with the STL algorithms library you can do some pretty cool things that are outside the scope of array index administrivia.

Answer 19

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

Answer 20

I don't use iterators for the same reason I dislike foreach-statements. When having multiple inner-loops it's hard enough to keep track of global/member variables without having to remember all the local values and iterator-names as well. What I find useful is to use two sets of indices for different occasions:

for(int i=0;i<anims.size();i++)
  for(int j=0;j<bones.size();j++)
  {
     int animIndex = i;
     int boneIndex = j;


     // in relatively short code I use indices i and j
     ... animation_matrices[i][j] ...

     // in long and complicated code I use indices animIndex and boneIndex
     ... animation_matrices[animIndex][boneIndex] ...


  }

I don't even want to abbreviate things like "animation_matrices[i]" to some random "anim_matrix"-named-iterator for example, because then you can't see clearly from which array this value is originated.