TITLE: styles of iteration


PROBLEM: jccote@andrew.sca.usherb.ca

What is an iterator member function???


RESPONSE: martelli@cadlab.it (Alex Martelli)

One way to design a container whose contents can be accessed
sequentially is by conceptualizing the container as having a "current"
member, and providing methods (==member functions) to "reset the
current member to the first one", "advance it to the next one",
as well as to return a reference to the current member and to
test whether there are any more members (these functionalities
are often merged, e.g. "return a pointer the current member,
zero if at end, and as a side effect advance to the next one").

These member functions, particularly the "advance to next" one,
can be called "iterator methods" of the container object.

Whether this is a good way to design a container, as opposed
to it having a member function that returns a *separate*
iterator *object*, is somewhat controversial -- me, I'd go
for iterator objects most of the time.


RESPONSE: kanze@lts.sel.alcatel.de (James Kanze), 5 Dec 95

I've always thought that an interator member function would be more
along the lines of `foreach', and take a pointer to function (or more
likely, a function object) as parameter.

In general, I think that there are three ways to implement iteration
over a container:

1. Provide a first and a next function, as Alex describes above.
IMHO, this is always the wrong solution.  Implement iteration like
this, and it will come back to haunt you.

2. Provide an iterator class/object.  This is currently the classical
solution, although there is some discussion about what exactly this
object should support.  My iterator objects generally support indexing
semantics, for example (which makes the distinction between const and
non-const containers easier to handle), whereas most of the other
iterators I've seen (including those in the STL) use pointer
semantics.  (This requires two different iterator types: one for const
containers, and one for non-const.)  Another open discussion is the
behavior of the iterator with regards to changes in the container.

3. Provide an iterator function, as I describe above.  This solution
is particularly attractive in the case of complex data structures,
like some trees and graphs, where the information necessary to
maintain the position requires a stack.  Note that a well written
iterator function poses many of the same problems as a well written
iterator object: the user provided operator may delete the element
from the container, or even invoke foreach again on the same
container.

One variant that I've often used in iterator functions (but it could
be used equally well with iterator objects) is to provide a filter
function.  Basically, the iterator function takes a reference to a
operator function object, and a reference to a filtering function
object.  The filtering function object is called for each element; if
it returns true, the operator function is called.  The filtering
function object has a default, passAll, which simply returns true.

The reason for the separation is that there are often a very few
frequently used filtering functions, which can be provided by the
container.  Thus, for example, a FileTree container might have filters
like isDirectory or isWritable.  I've not tried it yet, but there was
an article in C++ Report a couple of issues back about using templates
to evaluate expressions (at compile time); something like this might
allow writing:

	FileTree            ft( "/home/kanze" ,
                                FileTree::followSymLinks ) ;
	ft.visit( myOperator ,
                  FileTree::isDirectory && ! FileTree::isWritable ) ;

This will call myOperator on all of the write-protected directories in
the tree.  I'll have to give this a try sometime when I get time.