Nov 3, 2018

The Iterator pattern

An iterator is a mechanism that permits all elements of a collection to be accessed sequentially, with some operation being performed on each element. In essence, an iterator provides a means of "looping" over an encapsulated collection of objects. Examples of using iterators include
  • Visit each file in a directory (aka folder) and display its name.
  • Visit each node in a graph and determine whether it is reachable from a given node.
  • Visit each customer in a queue (for instance, simulating a line in a bank) and find out how long he or she has been waiting.
  • Visit each node in a compiler's abstract syntax tree (which is produced by the parser) and perform semantic checking or code generation. (You could also use the Visitor pattern in this context.)

Certain principles hold for the use of iterators: In general, you should be able to have multiple traversals in progress at the same time; that is, an iterator should allow for the concept of nested looping. An iterator should also be nondestructive in the sense that the act of iteration should not, by itself, change the collection. Of course the operation being performed on the elements in a collection could possibly change some of the elements. It might also be possible for an iterator to support removing an element from a collection or inserting a new element at a particular point in the collection, but such changes should be explicit within the program and not a byproduct of the iteration. In some cases, you will also need to have iterators with different traversal methods; for instance, preorder and postorder traversal of a tree, or depth-first and breadth-first traversal of a graph.

Iterators and the Gang of Four design patterns

According to the Gang of Four, the Iterator design pattern is a behavioral pattern, whose key idea is "to take the responsibility for access and traversal out of the list [ed. think collection] object and put it into an iterator object."