Iterator Pattern

Intent: Provide an object which traverses some aggregate structure, abstracting away assumptions about the implementation of that structure.

The simplest iterator has a "next element" method, which returns elements in some sequential order until there are no more. More sophisticated iterators might allow several directions and types of movement through a complex structure.

Typically an iterator has three tasks that might or might not be implemented in separate methods:

Bidirectional iterators might have additional methods for checking and advancing the reverse direction.

The simplest iterator merges these three tasks in one method, returning nil, null or whatever the language at hand provides to detect the end. Java iterators merge task 2 and 3 (advancement and access). C++ STL iterators have separate methods.

Robert Klemme


An iterator encapsulates the code required to move around your list. So I can just call next() on the iterator, and it gets me the next value. That may involve a simple index increment, or it may involve a complicated navigation around a structure (e.g. a depth-first search of a tree). The point is that the detail can be hidden behind a simple function call. If the iterator is defined in the class itself, then it is easier to ensure that any changes to the class are reflected in the iterator. In any case, a client, who just wants to get the next value (or whatever) needn't worry about how it is done. This can save a lot of code, and therefore saves a lot of chances for a mistake. It also saves a lot of work since I can change my class (from an array to a linked list say), and simply update the iterator code once. All code which uses the iterator will still work. Does that make sense? --RichardHenderson.


In C++ advancing is done using the ++ operator. For most iterators one comes in both flavors, pre-increment and post-increment and unlike normal loops that use simple types for positioning iterators should be advanved with the pre-increment operator to avoid creating a copy of the iterator. Iterator creation is typically done by calling a begin() method and the end of iteration can be detected by comparing the iterator to the element behind the elements, typically there is a method end(). Beware to use operator != for comparison because in some situations there is no == operator available. The data access can be done using iterator operators -> or * while -> might not always be implemented.

Example:

 std::vector<int> v;
 v.push_back(1);
 v.push_back(2);
 for( std::vector<int>::const_iterator it = v.begin() // creation
    ;it != end()  // detect end
    ;++it) // advancing
 {
    std::cout << *it << std::endl;
 }

In PHP Iteration is controlled by the Interfaces Iterator and IteratorAggregate? which basically match directly to the Code Pattern described by the Gang of Four. The IteratorAggregate? is responsible to create an external Iterator and the looping is doen by an Iterator. If you only want internal Iteration then your objects do not need to implement IteratorAggregate? and can directly implement Iterator. The SPL extension offers some advanced Iterator functionality by encasulating sstandard problems as abstracted algorithmns in iterator classes.

Example:

 <?php
 class MinMaxIterator? implements Iterator
 {
protected $min, $max;
protected $pos = 0;

public function __construct($min, $max) { // we don't need to initialize pos here because rewind() is responsible for that $this->min = $min; $this->max = $max; }

public function rewind() { // restart the looping process $this->pos = $this->min; }

public function valid() { // test for end of loop return $this->pos <= $this->max; }

public function key() { // php iterators are associative, but we don't provide a specialized key here return $this->pos; }

public function current() { // access the current element return $this->pos; }

public function next() { // advance to the next element $this->pos++; } }

class MinMax? implements IteratorAggregate? { protected $min, $max;

public function __construct($min, $max) { $this->min = $min; $this->max = $max; }

public function getIterator() { // creates an external iterator, called from foreach return new MinMaxIterator?($this->min, $this->max); } }

$minmax = new MinMax?(2, 6);

foreach ($minmax as $v) // calls $minmax->getIterator and then iterates over the result { print $v . "\n"; }

?>

Marcus Börger


The simplest iterator merges these three tasks in one method, returning nil, null or whatever the language at hand provides to detect the end.

Or by throwing an exception. In Python, iterators raise StopIteration?, and 'for loops' (iterations over a container or generator) are actually implemented in terms of exceptions.


Links: - http://wiki.cs.uiuc.edu/patternStories/IteratorPattern


CategoryPattern | CategoryStructuralPatterns

See ExternalIterator InternalIterator EmbeddedIterator


EditText of this page (last edited December 14, 2006) or FindPage with title or text search