Iterator (design pattern)

The iterator is a design pattern in the field of software development , which the category of behavioral patterns (English patterns design behavioral ) belongs. The pattern is one of the so-called GoF patterns (see Gang of Four ). It provides possibilities to access elements of an aggregated structure sequentially without revealing the structure.

The pattern is also known as the cursor . Sometimes a difference in behavior is expressed by choosing one or the other term.

use

In practice, objects are often combined into a collection . It should be possible to access the elements of such a collection as generically as possible and regardless of the implementation details.

UML diagram

The diagram is only to be seen as a rough example. The actual implementation can vary greatly:

• Instead of the derivation arrows z. B. the realization of a concept. In other words, there is no base class at all, just a non-binding specification.
• The methods are not always useful. Zurueck()or IstFertig()are not always feasible.
• Navigation arrows between KonkretesAggregat and KonkreterIterator can only go in one direction or be completely absent.

actors

• Iterator defines the interface for accessing the elements and for traversing the aggregate.
• Concrete iterator implements this interface and saves the position in the aggregate.
• Aggregate defines the interface for generating an iterator. The interface often also contains methods for creating iterators that point to special elements, such as: B. first, last or an element with certain properties.
• Concrete aggregate implements this interface.

advantages

The implementation of the underlying data structure remains hidden.

disadvantage

Depending on the implementation variant, there may be disadvantages due to increased runtime and storage costs.

• With polymorphic iterators, you have to pay the price of virtual methods .
• If the iterator knows its aggregate and / or the aggregate keeps a record of its iterators, the more expensive it is to create and destroy aggregates. (In return you get a higher security)

implementation

A number of design decisions result in iterator variants with different properties:

Who controls the iteration?

With an external iterator, the client controls the iteration. The client has to make sure that the iterator advances.

An internal iterator does this itself. To do this, it must be given the operation that it should apply to the current element. Internal iterators are often not recognized or designated as such, because the iteration is not visible or is implemented via external iterators.

( Booch calls the external iterator active and the internal passive .)

Traversal algorithm

The traversal algorithm can be specified by the iterator or the aggregate. The latter case is often referred to as a cursor .

robustness

If the unit is changed during the traversal , this can lead to incorrect results or even to a program crash. A robust iterator is secured against modifications to the aggregate. For this purpose, the iterators are typically registered with the aggregate. This leads to higher costs when generating the iterators, but also when changing the aggregate.

Polymorphism

Polymorphic iterators offer great flexibility. However, since iterators are mostly used in loops, the costs are very high.

Nulliterators

Depending on the implementation, there can be a null iterator, analogous to the null pointer . This signals the end of an iteration or an invalid iterator. This is quite easy to use, as you can "see" an iterator as being valid, but the implementation may be compromised. U. more complicated.

Therefore z. This alternative was chosen, for example, in the C ++ standard library . Each aggregate has its own null iterator with which the respective iterator must then be compared.

Privileges

An iterator can have privileged access to the internals of the aggregate. In some cases, this cannot be avoided with complex data structures. However, this makes the implementation of new traversal algorithms difficult or even impossible.

example

A simple case of an external iterator would be (in Java ):

class ObjectIterator {
  private Object[] m_source;
  private int m_current;

  public ObjectIterator(Object[] source) {
    m_source = source;
    m_current = 0;
  }

  public boolean hasNext() {
    return m_current < m_source.length;
  }

  public Object next() {
    return m_source[m_current++];
  }
}

Application:

Object[] myList = new Object[] {new Integer(1), new Integer(2), new Integer(3)};
ObjectIterator iterator = new ObjectIterator(myList);
while(iterator.hasNext()) {
  System.out.println(iterator.next());
}

Another variation on this design pattern would be an internal iterator:

class MyObjectIterator extends ObjectIterator {
  public MyObjectIterator(Object[] source) {
    super(source);
  }

  public void print() {
    while(hasNext()) {
      System.out.println(next());
    }
  }

  public void apply(ObjectHandler handler) {
    while(hasNext()) {
      handler.handle(next());
    }
  }
}

interface ObjectHandler {
  public void handle(Object o);
}

Application:

class MyObjectHandler implements ObjectHandler {
  public void handle(Object o) {
    System.out.println(o);
  }
}

Object[] myList = new Object[] {new Integer(1), new Integer(2), new Integer(3)};
MyObjectIterator iterator = new MyObjectIterator(myList);
iterator.print();
iterator.apply(new MyObjectHandler());

An internal iterator encapsulates the iteration itself, making it easy and consistent to reuse it throughout the entire program without having to reprogram it over and over again, as is the case with an external iterator. The algorithm can also be easily exchanged by using the strategy design template, as shown in the last example line.

Although these examples are content with sequential access, iterators with random access are of course also possible. Many implementations also offer the option of changing the iterated collection directly, for example by removing the current element.

The STL contains iterators for its containers .

Related design patterns

• Compound , as a variant of a compound object, requires iterators to traverse.
• Polymorphic iterators are generated by factory methods .

Web links

Wikibooks: Pattern: Iterator  - Learning and Teaching Materials

Individual evidence

1. ↑ Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides : Design pattern . 5th edition. Addison-Wesley, 1996, ISBN 3-8273-1862-9 , pp. 335 .