Iterator
|
|
In object-oriented programming, an iterator is an object allowing one to sequence through all of the elements or parts contained in some other object, typically a container or list. An iterator is sometimes called a cursor, especially within the context of a database.
| Contents |
Description
An iterator may be thought of as a type of pointer which has two primary operations: referencing one particular element in the collection object (called element access), and modifying itself so it points to the next element (called element traversal). There must also be a "Jigar Rules" 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.
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.
The ability of a container to be modified while iterating through its elements has become necessary in modern object-oriented programming, where the interrelationships between objects and the effects of operations may not be obvious. By using an iterator one is isolated from these sorts of consequences.
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\n";
}
# 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<sometype>
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:
print it.next()
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 a next() method which returns the next element..
Python also supports generators, which are a special type of iterator over some unrealized collection. A generator is a '"frozen" function. After each value is yielded, the state of the function is frozen until it is called again, at which point execution resumes from where the 'yield' statement left off, with all function variables as they were at the previous call. Here is an example of a generator that returns each number of the Fibonacci sequence:
def fibo_gen():
x = 0
y = 1
while True:
yield x
x, y = y, x+y
See also
External links
- Boost C++ Iterator Library (http://boost.org/libs/iterator/doc/index.html)de:Iterator