Iterator

In object-oriented programming, an iterator is an object (computing) 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 (databases), especially within the context of a Database.

=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 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 Tree data structure.

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.

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 programming language 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 statement, 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 plus plus language also has a std::for_each() function template which allows for similar implicit iteration, but it still requires explicit iterator objects as initial input.

==Generators==

A Generator (computer science) 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 plus plus 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 programming language 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