Iterator pattern

"Provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation."

Use when

  • Access to elements is needed without access to the entire representation.
  • Multiple or concurrent traversals of the elements are needed.
  • A uniform interface for traversal is needed.
  • Subtle differences of various iterators.

Jump to examples:

Description

An external iterator may be thought of as a type of pointer that has two primary operations: referencing one particular element in the object collection (called element access), and modifying itself so it points to the next element (called element traversal). There must also be a way to create an iterator so it points to some first element as well as some way to determine when the iterator has exhausted all of the elements in the container. Depending on the language and intended use, iterators may also provide additional operations or exhibit different behaviors.

The primary purpose of an iterator is to allow a user to process every element of a container while isolating the user from the internal structure of the container. This allows the container to store elements in any manner it wishes while allowing the user to treat it as if it were a simple sequence or list. An iterator class is usually designed in tight coordination with the corresponding container class. Usually, the container provides the methods for creating iterators.

Active iterators versus passive iterators

There are two general approaches to implementing an iterator depending on who controls the iteration.

For an active iterator (also known as explicit iterator or external iterator), the client controls the iteration in the sense that the client creates the iterator, tells it when to advance to the next element, tests to see if every element has been visited, and so on. Although iterators in Java have taken different forms, using an active iterator was essentially the only viable option prior to Java 8.

For a passive iterator (also known as an implicit iterator, internal iterator, or callback iterator), the iterator itself controls the iteration. The client essentially says to the iterator, "perform this operation on the elements in the collection." This approach is common in languages like LISP that provide anonymous functions or closures. With the release of Java 8, this approach to iteration is now a reasonable alternative for Java programmers.

Methods defined by the Iterator interface

next() Return element at current pointer and advance pointer.

valid() Confirm that there is an element at the current pointer position.

current() Return element at current pointer position.

key() Return current key (i.e., pointer value).

rewind() Send pointer to start of list.

Examples

PHP

PHP already provides a number of iterators for many day to day tasks. See SPL iterators for a list.

/** @link http://php.net/manual/en/class.iterator.php */
class PurchasesIterator implements \Iterator
{
    protected $values = array();

    public function __construct(array $values = array())
    {
        foreach ($values as $value) {
            $this->values[] = $value;
        }
        $this->rewind();
    }

    public function rewind()
    {
        reset($this->values);
    }

    public function valid()
    {
        return false !== $this->current();
    }

    public function next()
    {
        next($this->values);
    }

    public function current()
    {
        return current($this->values);
    }

    public function key()
    {
        return key($this->values);
    }
}

$iterator = new PurchasesIterator(array('first', 'second', 'third'));

// Usage 1
while ($iterator->valid()) {
    $current = $iterator->current();
    // Do something with current
    $iterator->next();
}

// Usage 2
for (; $iterator->valid(); $iterator->next()) {
    $current = $iterator->current();
    // Do something with current
}

Java

Iteration in the early versions of Java — Enumerations

In Java 1.0 and 1.1, the two primary collection classes were Vector and Hashtable, and the Iterator design pattern was implemented in a class called Enumeration. In retrospect this was a bad name for the class. Do not confuse the class Enumeration with the concept of enum types, which didn't appear until Java 5. Today both Vector and Hashtable are generic classes, but back then generics were not part of the Java language. The code to process a vector of strings using Enumeration would look something like.

Vector names = new Vector();

// ... add some names to the collection

Enumeration enumeration = names.elements();
while (enumeration.hasMoreElements()) {
    String name = (String) enumeration.nextElement();
    System.out.println(name);
}

Iteration in the middle versions of Java — Iterator

Java 1.2 introduced the collection classes that we all know and love, and the Iterator design pattern was implemented in a class appropriately named Iterator. Because we didn't yet have generics in Java 1.2, casting an object returned from an Iterator was still necessary. For Java versions 1.2 through 1.4, iterating over a list of strings might resemble to:

List names = new LinkedList();

// ... add some names to the collection

Iterator iterator = names.iterator();
while (iterator.hasNext()) {
    String name = (String) iterator.next();
    System.out.println(name);
}

Iteration after Java 5 — generics and the enhanced for-loop

Java 5 gave us generics, the interface Iterable, and the enhanced for-loop. The creation of the iterator and calls to its hasNext() and next() methods are not expressed explicitly in the code, but they still take place behind the scenes. Thus, even though the code is more compact, we are still using an active iterator.

List names = new LinkedList();

// ... add some names to the collection

for (String name : names) {
    System.out.println(name);
}

Java 7 gave us the diamond operator, which reduces the verbosity of generics. Gone were the days of having to repeat the type used to instantiate the generic class after invoking the new operator!

List names = new LinkedList<>();

Iteration in Java 8 — the forEach() method

The major new features in Java 8 center on lambda expressions, along with related features such as streams, method references, and functional interfaces. These new features in Java 8 allow us to seriously consider using passive iterators instead of the more conventional active iterators. In particular, the Iterable interface provides a passive iterator in the form of a default method called forEach().

List names = new LinkedList<>();

// ... add some names to the collection

names.forEach(name -> System.out.println(name));

Swift 3.0

The IteratorProtocol protocol is tightly linked with the Sequence protocol. Sequences provide access to their elements by creating an iterator, which keeps track of its iteration process and returns one element at a time as it advances through the sequence.

Whenever you use a for-in loop with an array, set, or any other collection or sequence, you're using that type's iterator. Swift uses a sequence's or collection's iterator internally to enable the for-in loop language construct.

Using a sequence's iterator directly gives you access to the same elements in the same order as iterating over that sequence using a for-in loop. For example, you might typically use a for-in loop to print each of the elements in an array.

let versions = ["N", "Marshmallow", "Lollipop", "KitKat", "Jelly Bean"]
for version in version {
    print(version)
}

Behind the scenes, Swift uses the versions array's iterator to loop over the contents of the array.

var versionIterator = versions.makeIterator()
while let version = versionIterator.next() {
    print(version)
}

Other patterns

Abstract Factory
Adapter
Bridge
Builder
Chain of Responsibility
Command
Composite
Decorator
Factory Method
Facade
Flyweight
Prototype
Interpreter
Mediator
Memento
Observer
Proxy
State
Strategy
Template Method
Visitor