Natural Iterators

Two ways of handling a collection

• Accessor/iteratee:
  provides an access to the current element, and a way to move to the next one
  • must be a friend of a collection
  • must have states: know where it is at
  • the burden of iterating is on you
  
  STL/container iterators are actually accessors

  
  
  

• Iterator:
  collection.for_each( current_element_processor)
  • collection itself does the iteration
  • atomicity of an iteration: no states, no checks
  • a processor always gets the naked current element (value)
  • processor as a closure
  • types: for-each, any?, map

  natural to Scheme/Dylan/ML, but possible in C++ too

an accessor must have an intimate knowledge of the collection itself. Indeed, it has to know how to get to the current element, and move to the next one. An accessor always has a state: it has to be aware where it is at and if it is good. Also, it's you who has to actually write the loop and repeatedly use (call) the iteratee, while not forgetting to check for the termination condition.

Iterator: and I mean really an iterator. That is, it iterates itself. To distinguish it from STL iterators, I call this a real or natural iterator. Here's the template of its usage.

Here, a collection itself drives the iteration; surely the collection knows what it is, so it can plan the iteration (that is, picking of the next element) as efficiently as possible. There may be different types of the for_each methods, each optimized for a particular task. The iteration itself is done in a single statement: it is an "atomic" operation. Therefore, there is no need to have/keep states, and check them. You can think of it as a for() loop being already pre-programmed. Because there are no states, there is no chance it can be wrong/bad. The processor always gets the naked current element (and it has no idea how to get the next one). And it doesn't have to know: the next element would be given to it, if it exists. But this is not to say that the processor is always memoryless: it can keep some information it has gleaned from the previous elements and tune the processing of the current element as necessary. That is, the processor can be a closure. These beasts are very common in other languages, like Scheme, Dylan, ML; it's interesting it's all possible in C++ too.

Next | Table of contents