Design Pattern - (Iterator|Cursor)

> Code - (Programming|Computer) Language > Design Pattern

1 - About

The primary purpose of an iterator is to allow a user to process every element of a collection (container) while isolating the user from the internal structure of the container.

See also: Language - Loop (For, While) - (Break, Continue) … Merge ?

The Iterator pattern works for a collection of objects that you want to:

  • hand out through a common interface
  • in a particular order (with a Comparator behind the scenes)

The consuming code has only to call next() a few times to achieve it's objective.

Iterators date to the CLU programming language in 1974.

An iterator is behaviourally similar to a database cursor.

They're also complicated, stateful iterators, such as tree traversers.


3 - Stream

Iterators are a useful abstraction of input streams that you can see as an infinite iteration.

4 - Loop Implementation

4.1 - Indexing

In procedural languages it is common to use the subscript operator and a loop counter to loop through all the elements in a sequence such as an array.

4.2 - Iterator

The use of iterators may have some advantages against indexing:

  • Counting loops are not suitable to all data structures, in particular to data structures with no or slow random access, like lists or trees.
  • Iterators can provide a consistent way to iterate on data structures of all kinds, and therefore make the code more readable, reusable, and less sensitive to a change in the data structure.
  • An iterator can enforce additional restrictions on access, such as ensuring that elements can not be skipped or that a previously visited element can not be accessed a second time.
  • An iterator may allow the container object to be modified without invalidating the iterator. For instance, once an iterator has advanced beyond the first element it may be possible to insert additional elements into the beginning of the container with predictable results. With indexing this is problematic since the index numbers must change.

4.3 - Trade-off

This is always a trade-off between security (iterators remain always valid) and efficiency. Most of the time, the added security in not worth the efficiency price to pay for it. Using an alternative container (for example a singly linked list instead of a vector) would be a better choice (globally more efficient) if the stability of the iterators is needed.

5 - Documentation / Reference