TITLE: What are iterators?


RESPONSE: rmartin@rcmcon.com (Robert Martin), 13 Apr 94

The question of who invented iterators might be difficult to answer.
For example, the index of a summation symbol in mathematics is an
iterator.    One might point to FORTRAN and the DO statement for the
source of the first formal software iterators, but this the
distinction is dubious at best.

The simplest iterator is simply an integer.

char array[100];
for (int i=0; i<100; i++) array[i] = 0;

Here, 'i' is the iterator.  It uniquely identifies each element in the
container, one at a time.  

Integers work just fine for things like arrays.  But for containers
which do not have any implicit order or size, they are problematic.
For example, one would not want to use an integer to iterate over the
elements of a linked list...  A better iterator would remember a
pointer to the current element and would know how to traverse the
links to the next element.

Still other container types will use different mechanisms for finding
the "next" element to be iterated.  

So, an abstract interface can be created, and can be implemented in
different forms for different container types.

template <class T>
class Iterator
{
  public:
    Iterator(IterableContainer<T>&);
    virtual operator void*() = 0;
    virtual void operator++() = 0;
    virtual T& operator*() = 0;
};

With this interface, one can create, test, increment and access an
iterator as follows:

Set<Garp> mySet;
for(SetIterator<Garp> i(mySet); i; i++)
    (*i).DoSomethingIntelligent();

Of course one can create many iterators at the same time.  This allows
a container to support more than one iteration concurrently.  A
practical result is the following class which uses normal iterators to
create a new kind of iterator which iterates over every possible pair
of elements within a container.

template <class T>
class CombinationIterator 
{
  public:
    CombinationIterator(const MemberContainer<T>& theContainer)
    : itsI(theContainer), itsJ(theContainer)
    {
	itsJ++;
    }
    
    virtual ~CombinationIterator() {}
    CombinationIterator(const CombinationIterator<T>& i)
    : itsI(i.itsI), itsJ(i.itsJ)
    {}
    
    CombinationIterator<T>& operator=(const CombinationIterator<T>& i);
    
    operator void*() const {return (void*)(itsJ);}
    Association<T,T> operator*() {return Association<T,T>(*itsJ, *itsI);}
    void operator++(int);
  private:
    Iterator<T> itsI;
    Iterator<T> itsJ;
};

template <class T>
CombinationIterator<T>&
CombinationIterator<T>::operator=(const CombinationIterator<T>& i)
{
    if (&i != this)
    {
	itsI = i.itsI;
	itsJ = i.itsJ;
    }
    return *this;
}

template <class T>
void CombinationIterator<T>::operator++(int)
{
    if (itsJ)
    {
        itsJ++;
        if (!itsJ)
        {
            itsI++;
	    itsJ = itsI;
	    itsJ++;
        }
    }
}

RESPONSE: p j l @graceland.att.com (Paul J. Lucas)

Exactly the same way as you write an iterator for a non-const
object except that it takes a reference-to-const and all T's
are replaces by T const's.

In my library, there are two iterators per container:
ThingIterator and ThingConstIterator.  You can usually derived
the non-const version from the const version and just cast away
the const.  Doing the inheritance in that order also allows you
to add members to the derived one like Delete().  The
inheritance should be protected, obviously.


RESPONSE: kanze@us-es.sel.de (James Kanze)

I've found an alternative solution that I prefer.  I only have one
iterator; it can be used on both const and non-const objects.  (It
takes a const reference in the constructor.)

The iterator cannot be used to access a member object directly.
Rather, the container class contains two operator[], which takes the
iterator as parameter.  For additional functions, like delete, again,
the function is in the container class, not the iterator, and takes
the iterator as parameter.  Thus, it is always the const-ness of the
container which decides, and nothing to do with the iterator.

I personally find needing two iterators confusing (although not very),
and prefer to think of the iterator as an index rather than a pointer.
There is a very slight run-time overhead; the function (operator[] or
other) is passed the this pointer of the container, which it doesn't
use.  The only cases I can think of where this would be significant,
the function would probably be inline anyway, so the compiler could
optimize this out.