Iterator

Description

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.

Contrasting with indexing

In procedural languages it is common to use indexing to loop through all the elements in a sequence such as an array. Although indexing may also be used with some object-oriented containers, the use of iterators may have advantages.

• 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 insuring 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 invaliding 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.

Implicit iterators

Some object-oriented languages such as Perl or Python provide an intrinsic way of iterating through the elements of a container object without the introduction of an explicit iterator object. This is often manifested by some sort of "for-each" operator, such as in the following examples:

# Perl, implicit iteration foreach $val (@list) { print "$val\ "; } # Python, implicit iteration for Value in List: print Value The C++ language also has a std::for_each() function template which allows for similar implicit iteratation, but it still requires explicit iterator objects as initial input.

Generators

A generator is a special kind of iterator in which the container object is not fully realized. This allows abstract or even infinite collections to be processed one element at a time. Generators are common in functional programming languages, or languages which borrow some functional concepts. Generators are often implemented in terms of continuations.

Iterators in different programming languages

C++

The C++ language makes wide use of iterators in its Standard Template Library. All of the standard container template types provide a rich and consistent set of iterator types. The syntax of standard iterators is designed to resemble that of ordinary C pointer arithmetic, where the * and -> operators are used to reference the element to which the iterator points, and pointer arithmetic operators like ++ are used to advance the iterator to the next element.

Iterators are usually used in pairs, where one is used for the actual iteration and the second serves to mark the end of the collection.
The iterators are created by the corresponding container class using standard methods such as begin() and end().
The iterator returned by begin() points to the first element, while the iterator returned by end() is a special value that does not reference any element.

When an iterator is advanced beyond the last element it is by definition equal to the special end iterator value.
The following example shows a typical use of an iterator.

ContainerType C; // Any standard container type, like std::list ContainerType::iterator A = C.begin(); ContainerType::iterator Z = C.end(); while( A != Z ) { ContainerType::value_type value = *A; std::cout << value << std::endl; ++A; } There are many varieties of iterators each with slightly different behavior, including: forward, reverse, and bidirectional iterators; random-access iterators; input and output iterators; and const iterators (which protect the container or its elements from modification).
However not every type of container supports every type of iterator.
It is possible for users to create their own iterator types by deriving subclasses from the standard std::iterator class template.

Iterator safety is defined separately for the different types of standard containers, in some cases the iterator is very permissive in allowing the container to change while iterating.

Java

Introduced in the Java 1.2 standard, the java.util.Iterator interface allows one to iterate container classes. Each Iterator provides a next() and hasNext() method, and may optionally support a remove() method. Iterators are created by the method iterator() provided by the corresponding container class.

The next() method will advance the iterator and then return the value pointed to by that iterator. When first created an iterator points to a special value before the first element, so that the first element is obtained upon the first call to next(). To determine when all the elements in the container have been visited the hasNext() test method is used. The following example shows a simple use of iterators:

Iterator it = list.iterator(); while (it.hasNext()) { Object val = it.next(); System.out.println(val.toString()); } For collection types which support it, the remove() method of the iterator may be used to remove the most recently visited element from the container. Most other types of modification to the container while iterating are unsafe.

Python

Iterators in Python are a fundamental part of the language and in many cases go unseen as they are implicitly used with the for-statement.
All of Python's standard built-in sequence types support iteratation, as well as many classes which are part of the standard library.
The following example shows typical implicit iteration over a sequence:

for value in sequence: print value Iterators however can be used and defined explicitly.
For any iteratable sequence type or class, the builtin function iter() is used to create an iterator object.
The iterator object then provides a next() method which returns the next element in the container.
It will raise a StopIteration error when no more elements are left.
The following example shows an equivalent iteration over a sequence using explicit iterators:

it = iter(sequence) try: while(True): val = it.next() print val except StopIteration: pass Any user defined class can support standard iteration (either implicit or explicit) by defining an __iter__() method which creates an iterator object.
The iterator object then needs to define both an __iter__() method as well as a next() method.

Python also supports generators, which are a special type of iterator over some unrealized collection.
A generator is used just like an iterator, except that there is no collection class.
Instead the set of elements is computed or generated on the fly.

See also