Iterators.. why use them?

Question

In the STL library some containers have iterators and it is commonly held that they are a superior way of iterating through these containers rather than simple for loops e.g.

for ( int i=0; i < vecVector.size(); i++ )
{

..

}

Can anyone tell me why and in what cases I should use iterators and in what cases the code snippet above please?

Answer 1

Using iterators allows your code to be agnostic about the implementation of your container. If random access for your container is cheap, there isn't much difference performance-wise.

But in lots of cases you won't know whether that is the case. If you try do use your method on a linked list, for example, with subscripting, the container is going to have to walk the list on every iteration to find your element.

So unless you know for sure that random access to your container is cheap, use an iterator.

Answer 2

Repeat: http://stackoverflow.com/questions/131241/why-use-iterators-instead-of-array-indices

Answer 3

In your example, the call to vecVector.size() is less efficient than using an iterator. The iterator essentially encapsulates you from having to worry about the size of the container being iterated upon. Furthermore, the iterator does not necessary have to go in sequential order. It simply has to respond to a .next call in whatever way it sees fit.

Answer 4

Well, for one thing the above will no longer work if you turn that vector into a list.

Iterators allow you to create function templates that don't need to know the type of container they work on. You can even do the following:

#include <algorithm>

void printvalue(double s)
{
    // Do something with s
}

int _tmain(int argc, _TCHAR* argv[])
{
    double s[20] = {0};

    std::for_each(s, s+20, printvalue);

    return 0;
}

That's because a standard pointer is also a valid iterator for for_each.

Dave

Answer 5

Note that the usually implementation of vector won't use an "int" as the type of the index/size. So you're code will at the very least provoke compiler warnings.

Genericity

Iterators increase the genericity of your code.

For example:

typedef std::vector<int> Container ;

void doSomething(Container & p_aC)
{
    for(Container::iterator it = p_aC.begin(), itEnd = p_aC.end(); it != itEnd; ++it)
    {
       int & i = *it ; // i is now a reference to the value iterated
       // do something with "i"
    }
}

Now, let's imagine you change the vector into a list (because in your case, the list is now better). You only need to change the typedef declaration, and recompile the code.

Should you have used your code instead, it would have needed to be re-written.

Access

The iterator should be viewed like a kind of super pointer. It "points" to the value (or, in case of maps, to the pair of key/values).

But it has methods to move to the next item in the container. Or the previous. Some containers offer even random access (the vector and the deque).

Algorithms

Most STL algorithms work on iterators or on ranges of iterators (again, because of genericity). You won't be able to use an index, here.

Answer 6

If you use iterators as the arguments to your function you can decouple it from the type of "container" used. For example, you might direct the results of a function to console output rather than a vector (example below). This trick can be enormously powerful for reducing coupling between your classes. Loosely coupled classes are much easier to test.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename InputIterator, typename OutputIterator>
void AddOne(InputIterator begin, InputIterator end, OutputIterator dest)
{
    while (begin != end)
    {
        *dest = *begin + 1;
        ++dest;
        ++begin;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    vector<int> data;
    data.push_back(1);
    data.push_back(2);
    data.push_back(3);

    // Compute intermediate results vector and dump to console
    vector<int> results;
    AddOne(data.begin(), data.end(), back_inserter(results));
    copy(results.begin(), results.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    // Compute results and send directly to console, no intermediate vector required
    AddOne(data.begin(), data.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    return 0;
}

Answer 7

The iterator is mostly a higher level of abstraction.

Your snippet assumes that the container can be indexed. This is true for std::vector<> and some other containers, for instance raw arrays.

But std::set<> lacks indexing completely and the index operator of std::map<> will insert whatever argument is supplied to it into the map - not the expected behavior in your for-loop.

Also, performance issues are only issues when measured and proved so.