When to write an iterator?

Question

I know this is probably a silly question.. When would I need to write my own iterator? Is it just when designing my own container class? Are there any other times when I would want to create my own iterator?

Examples would be appropriated.

-Jon

Answer 1

You need to write own iterator for your own container class or if you need non-standard behaviour when iterating through standard containers.

Answer 2

When you have a class (most likely a container) and you want to allow your users to traverse it conveniently without exposing implementation details, you'll want to create an iterator.

This is even more true for when you have a family of classes (again, most likely containers) and you want to provide your users with a uniform iteration/traversal interface for all of them, even if their implementations are very different (i.e. linked list versus an array).

Answer 3

Yes, there are other times. For a few examples:

1. A filter_iterator that only returned a filtered subset of the items in a container.
2. A select iterator that returned only part of an object.
3. An ostream_iterator that puts separators before or between items, instead of after them.

Answer 4

I can see two cases where you would like to create a new iterator:

• For your own container class (as you point out yourself).
• An iterator with custom behaviour for an existing container class. STL for example has backwards iterators. Maybe you would like a every_3rd_iterator which only returns every third element? Such an iterator would probably be implemented as an adapter around an existing iterator.

Answer 5

Any time you need to iterate over a sequence of data, and an iterator isn't already defined that suits your needs.

Often, you use iterators to traverse containers, but that's far from the only use.

An iterator could also traverse the results of a database query, or input read from a stream (std::istream_iterator and std::istreambuf_iterator already do this, however), or perhaps you need a special traversal order or strategy. Perhaps you want to iterate over "every member of this vector, whose index is divisible by four", or "every capital letter in this string", or whatever else you can think of.

Answer 6

Apart from filter and selection iterators the only time I have written iterators in c++ is to get 3rd party container classes to play nice with stl algorithms. For example

• A random access iterator for a CORBA sequence
• A back inserter for a CORBA sequence
• A bidirectional iterator for the XML Dom, this converted a dom node to an iterator that enabled me to use foreach and transform on the nodes siblings.

In general I don't like writing iterators because they are hard, there are a lot of things to take care of. This task however is made much easier with the boost iterator library.

Answer 7

You might also want to use them for iterating over numerical sequences, such as Fibonacci numbers or maybe primes. These could be done other ways, probably more easily, but there may be times when the use of an iterator for such things makes sense.

Answer 8

Implementing iterators can be extremely useful and I have done so quite often. An iterator is a simple concept that everybody knows how to use. Iterators let you use the STL algorithms.

Often, you can implement iterators to simplify the usage of frequently used operating system APIs like Windows' FindNextFile

When you write a file_iterator (already exists in boost), you can suddenly do:

file_iterator itBegin; // initialize appropriately
file_iterator itEnd;
std::vector< HANDLE > vecFiles( itBegin, itEnd );

to get a list of handles to all matching files. Without the iterator, the necessary API calls would have made your code harder to read.

Think of iterators as simple concepts that let you write what you really mean to say and abstract away the nitty gritty details. If you have to implement a complex algorithm that is difficult to understand by itself, you want to reduce code clutter.

If you have a two dimensional structure, e.g. std::vector< std::vector >, in other words a table, in which every inner vector is required to have the same length, you might need to iterate over every n-th element of the inner vectors. If this happens frequently enough, your code may become a lot simpler when you implement an iterator instead of spreading nested for-loops throughout the code.