What Makes the Iterator a Design Pattern?

Question

I have been wondering what it is that makes the Iterator special when compared to other similar constructs, and that made the Gang of Four list it as a design pattern.

The Iterator is based on polymorphism (a hierarchy of collections with a common interface) and separation of concerns (iterating over the collections should be independent from the way the data is structured).

But what if we replace the hierarchy of collections with, for example, a hierarchy of mathematical objects (integer, float, complex, matrix etc.) and the iterator by a class representing some related operations on these objects, for example power functions. The class diagram would be the same.

We could probably find many more similar examples like Writer, Painter, Encoder, and probably better ones, that work the same way. However I have never heard any of these being called a Design Pattern.

So what makes the Iterator special?

Is it the fact that it is more complicated because it requires mutable state for storing the current position within the collection? But then, mutable state is usually not being considered desirable.

---

To clarify my point, let me give a more detailed example.

Here's our design problem:

Let's say we have a hierarchy of classes and an operation defined on the objects of these classes. The interface of this operation is the same for each class, but the implementations can be completely different. It is also assumed that it makes sense to apply the operation multiple times on the same object, say with different parameters.

Here's a sensible solution for our design problem (practically a generalization of the iterator pattern):

For separation of concerns, the implementations of the operation should not be added as functions to the original class hierarchy (operand objects). Since we want to apply the operation multiple times on the same operand, it should be represented by an object holding a reference to the operand, not just by a function. Therefore the operand object should provide a function that returns the object representing the operation. This object provides a function that performs the actual operation.

An example:

There's a base class or interface MathObject (stupid name, I know, maybe someone has a better idea.) with derived classes MyInteger and MyMatrix. For each MathObject an operation Power should be defined that allows calculation of square, cube and so on. So we could write (in Java):

MathObject i = new MyInteger(5);
Power powerOfFive = i.getPower();
MyInteger square = powerOfFive.calculate(2); // should return 25
MyInteger cube = powerOfFive.calculate(3); // should return 125

Answer 1

Most of the patterns from the GoF book have the following things in common:

• they solve basic design problems, using object-oriented means
• people often face these kind problems in arbitrary programs, indepently from the domain or business
• they are recipes for making the code more reusable, often by making it more SOLID
• they present canonic solutions to these problems

The problems solved by these patterns are so basic that many developers understand them mainly as workarounds for missing programming language features, which is IMHO a valid point of view (note that the GoF book is from 1995, where Java and C++ did not offer so many features as today).

The iterator pattern fits well into this description: it solves a basic problem which occurs very often, independently from any specific domain, and as you wrote by yourself it is a good example for "separation of concerns". As you surely know, direct iterator support is something you find in a lot of contempary programming languages today.

Now compare this to the problems you picked:

• writing to a file - that is IMHO simply not "basic" enough. It is a very specific problem. Nor is there a good, canonic solution - there are lots of different approaches how to write to a file, and no clear "best practice".
• Painter, Encoder: whatever you have in mind with that, those problems look even less basic to me, and not even domain independent.
• having the "power" function available for different kind of objects: at a first glance, that could be worth beeing a pattern, but your proposed solution does not convince me - it looks more like an attempt to shoehorn the power function into something similar to the iterator pattern. I implemented a lot of code with engineering calculations, but I cannot remember a situation where an approach similar to your power function object would have helped me (however, iterators is something I have to deal with on a daily basis).

Moreover, I do not see anything in your power function example which could not be interpreted as an application of the strategy pattern or the command pattern, which means those basic parts are already in the GoF book. A better solution might contain either operator overloading or extension methods, but those are things are subject to language features, and that is exactly what the "OO means" used by the "Gang" could not provide.

Answer 2

The Gang of Four quote Christopher Alexander's pattern definition:

Each pattern describes a problem which occurs over and over again in our environment, and then describes the core of the solution to that problem […]

What is the problem solved by iterators?

Intent: Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation.

…

Applicability: Use the Iterator pattern

• to access an aggregate object's contents without exposing its internal representation
• to support multiple traversals of aggregate objects
• to provide a uniform interface for traversing different aggregate structures (that is, to support polymorphic iteration).

So one could argue that the iterator pattern is by definition domain-specific to collections. And that is perfectly OK. Other patterns like the interpreter pattern are domain-specific to domain-specific-languages, the factory patterns are domain-specific to object creation, …. Of course this is a rather silly understanding of “domain-specific”. As long as it's a reoccurring problem–solution pair, we may call it a pattern.

And it's good that the Iterator pattern exists. Bad things happen if you don't use it. My favourite anti-example is Perl. Here, each collection (array or hash) includes the iterator state as part of the collection. Why is this bad? We can easily iterate over a hash with a while–each loop:

while (my ($key, $value) = each %$hash) {
  say "$key => $value";
}

But what if we call a function in the loop body?

while (my ($key, $value) = each %$hash) {
  do_something_with($key, $value, $hash);
}

This function may now do pretty much whatever it wants, except:

• add or delete hash entries, since these would alter the iteration order unpredictably (in C++-speak, these would invalidate the iterator).
• iterate the same hash table without doing a copy, since that would consume the same iteration state. Oops.

If the called function should use the iterator, the behaviour of our loop becomes undefined. That is a problem. And the iterator pattern has a solution: put all the iteration state in a separate object that's created per-iteration.

Yes, of course the iterator pattern is related to other patterns. For example, how is the iterator instantiated? In Java, we have a generic Iterable<T> and Iterator<T> interface. A concrete iterable like ArrayList<T> creates a particular kind of iterator, whereas a HashSet<T> might supply a completely different iterator type. That reminds me very much of the abstract factory pattern, where the Iterable<T> is the abstract factory and the Iterator is the product.

A polymorphic iterator can also be interpreted as an example of the strategy pattern. E.g. a tree might offer different kinds of iterators (pre-order, in-order, post-order, …). Externally, these would all share an iterator interface and yield elements in some sequence. Client code only needs to depend on the iterator interface, not on any particular tree traversal algorithm.

Patterns do not exist in isolation, independent from each other. Some patterns are different solutions to the same problem, and some patterns describe the same solution in different contexts. Some patterns imply another. Also, the pattern space is not closed when you turn the last page of the Design Patterns book (see also your earlier question Did the Gang of Four thoroughly explore “Pattern Space”?). The patterns described in the Design Patterns book are very flexible and broad, open to infinite variation, and definitively not the only patterns in existence.

The concepts you list (writing, painting, encoding) aren't patterns because they don't describe a problem–solution combination. A task like “I need to write data” or “I need to encode data” isn't really a design problem and does not include a solution; a “solution” that just consists of “I know, I'll create a Writer class” is meaningless. But if we have a problem like “I don't want half-rendered graphics to be painted on the screen”, then a pattern may exist: “I know, I'll use double-buffered graphics!”