Iterator pattern

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

The pattern is known as the cursor. It is sometimes implied by the choice of one or the other term is a difference in behavior.

Use

In practice, objects are often combined to form a collection. To the elements of such a collection will be accessible as possible generically, without regard to implementation details.

UML diagram

The diagram can be seen as a gross example. The actual implementation may vary greatly:

• Instead of the derivative such as arrows may be the realization of a concept. That is, there is no base class, only a non-binding target.
• Navigation arrows between KonkretesAggregat and KonkreterIterator can only go in one direction or omissions.

Actors

• Iterator defines the interface to access to the elements and to traverse the aggregate.
• Concrete iterator implements this interface and stores the position in the aggregate.
• Unit defines the interface for creating an iterator. Often, the interface also includes methods for generating iterators that point to specific elements, such as the first, last, or a member with certain properties.
• Concrete aggregate implements this interface.

Benefits

Disadvantages

Depending on the variant of the implementation, disadvantages due to increased run-time and memory costs may result.

• In polymorphic iterators have to pay the price for the virtual methods.
• If the iterator knows his unit and / or the aggregate of his book takes iterators, especially the creation and destruction of aggregates expensive. ( In return, you get a higher security )

Implementation

Due to some design decisions, iterator variants are derived with different characteristics:

Who controls the iteration?

For an external iterator, the client controls the iteration. The client must ensure that the iterator advances.

An internal iterator does this itself this, the operation must be handed over to him that he should apply to the current element. Internal iterators are often not recognized as such or designated, as the iteration is not visible or is but accomplished using external iterators.

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

Traversionsalgorithmus

The Traversionsalgorithmus can be specified by the iterator or the aggregate. In the latter case there is often talk of a cursor.

Robustness

If the unit is changed during the Traversion, which can lead to incorrect results or even a program crash. A robust iterator is secured against modifications of the aggregate. Typically, the iterators are to be registered with the unit. This leads to higher costs in producing the iterators, but also when changing the unit.

Polymorphism

Polymorphic iterators provide a high flexibility. Since iterators are mostly used in loops, the cost, however, are for very high.

Nulliteratoren

Depending on the implementation, it can give analogous to the null pointer, a Nulliterator. This signaled the end of an iteration, or an invalid iterator. This is quite convenient to use, since you an iterator valid " looks ", but the implementation is thereby may more complicated.

Therefore, this alternative was chosen in the C standard library, for example. Every unit has its own Nulliterator with which you must then compare the respective iterator.

Privileges

An iterator can have privileged access to the internals of the unit. That is not to avoid the case of complex data structures partially. However, by the implementation of new Traversionsalgorithmen is hampered, if not prevented.

Example

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

Class ObjectIterator {    private Object [ ] m_source;    private int m_current;      public ObjectIterator ( Object [ ] source ) {      m_source = source;    }      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 of 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 ( Object Handler handler) {      while ( hasNext ()) {        handler.handle ( next () );      }    } }   Object Handler interface {    public void handle (Object o ); } application:

MyObjectHandler class implements Object Handler {    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 and makes it so the whole program easily and consistently reusable without having to reprogram it again and again as in the case of an external iterator. By using the strategy design pattern, the algorithm can also be easily replaced, as shown in the last example line.

Although these examples are content with sequential access, of course, random access iterators are possible. Many implementations also offer the possibility to change the iterated collection directly, such as by removing the current element.

The STL contains iterators for their container.

Related Design Patterns

• Compound, as a variant of a compound object, requires iterators for traversing.
• Polymorphic iterators are created by factory methods.