Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
, an iterator is an object that enables a programmer to traverse a container
Container (data structure)
In computer science, a container is a class, a data structure, or an abstract data type whose instances are collections of other objects. In other words; they are used for storing objects in an organized way following specific access rules...
. Various types of iterators are often provided via a container's interface. Though the interface and semantics of a given iterator are fixed, iterators are often implemented in terms of the structures underlying a container implementation and are often tightly coupled to the container to enable the operational semantics of the iterator. Note that an iterator performs traversal and also gives access to data elements in a container, but does not perform iteration (i.e., not without some significant liberty taken with that concept or with trivial use of the terminology). An iterator is behaviorally similar to a database
Database
A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
In computer science and technology, a database cursor is a control structure that enables traversal over the records in a database. Cursors facilitate subsequent processing in conjunction with the traversal, such as retrieval, addition and removal of database records...
.
External iterators and the iterator pattern
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.
In software engineering, a loop counter is the term often used to refer to the variable that controls the iterations of a loop...
is sometimes also referred to as a loop iterator. A loop counter
Loop counter
In software engineering, a loop counter is the term often used to refer to the variable that controls the iterations of a loop...
, however, only provides the traversal functionality and not the element access functionality.
Generators
One way of implementing iterators is to use a special kind of subroutine
Subroutine
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
, known as a generator, that can yield values to its caller multiple times (instead of returning just once). Most iterators are naturally expressible as generators, but because generators preserve their local state between invocations, they're particularly well-suited for complicated, stateful iterators, such as tree traversers
Tree traversal
In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited...
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
's yield statement can be seen below.
def fibonacci:
a, b = 0, 1
while True:
yield a
a, b = b, a+b
for number in fibonacci: # Use the generator as an iterator
print number
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
Object Pascal refers to a branch of object-oriented derivatives of Pascal, mostly known as the primary programming language of Embarcadero Delphi.-Early history at Apple:...
provide an intrinsic way of iterating through the elements of a container object without the introduction of an explicit iterator object. An actual iterator object may exist in reality, but if it does it is not exposed within the source code of the language.
Implicit iterators are often manifested by a "foreach
Foreach
For each is a computer language idiom for traversing items in a collection. Foreach is usually used in place of a standard for statement. Unlike other for loop constructs, however, foreach loops usually maintain no explicit counter: they essentially say "do this to everything in this set",...
" statement (or equivalent), such as in the following Python example:
for value in iterable:
print value
Or other times they may be created by the collection object itself, as in this Ruby example:
iterable.each do |value|
puts value
end
This iteration style is sometimes called "internal iteration" because its code fully executes within the context of the iterable object (which controls all aspects of iteration), and the programmer only provides the operation to execute at each step (using an anonymous function
Anonymous function
In programming language theory, an anonymous function is a function defined, and possibly called, without being bound to an identifier. Anonymous functions are convenient to pass as an argument to a higher-order function and are ubiquitous in languages with first-class functions such as Haskell...
).
Languages that support list comprehensions or similar constructs may also make use of implicit iterators during the construction of the result list, as in Python:
names = [person.name for person in roster if person.male]
Sometimes the implicit hidden nature is only partial. The C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
language has a few function templates, such as for_each, that allow for similar implicit iteration. However they still require explicit iterator objects as their initial input. But once initialized the subsequent iteration happens implicitly without the continued use of any exposed iterator object.
In computer science, an index can be:# an integer that identifies an array element# a data structure that enables sublinear-time lookup -Array element identifier:...
In software engineering, a loop counter is the term often used to refer to the variable that controls the iterations of a loop...
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 some advantages:
Counting loops are not suitable to all data structures, in particular to data structures with no or slow random access
Random access
In computer science, random access is the ability to access an element at an arbitrary position in a sequence in equal time, independent of sequence size. The position is arbitrary in the sense that it is unpredictable, thus the use of the term "random" in "random access"...
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.
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
The Standard Template Library is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. More specifically, the C++ Standard Library is based on the STL published by SGI. Both include some...
, which provides several different kinds of iterators, including forward iterators, bidirectional iterators, and random access iterators. 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
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
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.
std::vector items;
items.push_back(1); // Append integer value '1' to vector 'items'
items.push_back(2); // Append integer value '2' to vector 'items'
items.push_back(3); // Append integer value '3' to vector 'items'
for (std::vector::iterator i = items.begin; i != items.end; ++i) { // Iterate through 'items'
std::cout << *i; // And print current index of 'items'
}
//Prints 123
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.
Implicit iteration is also partially supported by C++ through the use of standard function templates, such as std::for_each, std::copy
and std::accumulate.
When used they must be initialized with existing iterators, usually begin and end, that define the range over which iteration occurs. But no explicit iterator object is subsequently exposed as the iteration proceeds. This example shows the use of for_each.
ContainerType C; // Any standard container type of ItemType elements
void ProcessItem(const ItemType& I) { // Function which will process each item of the collection
std::cout << I << std::endl;
}
std::for_each(C.begin, C.end, ProcessItem); // A for-each iteration loop
The same can be achieved using std::copy and std::ostream_iterator:
std::copy(C.begin, C.end, std::ostream_iterator(std::cout, "\n"));
A limitation is that this technique does not allow the body of the for-each loop to be declared inline, requiring a function pointer
Function pointer
A function pointer is a type of pointer in C, C++, D, and other C-like programming languages, and Fortran 2003. When dereferenced, a function pointer can be used to invoke a function and pass it arguments just like a normal function...
A function object, also called a functor, functional, or functionoid, is a computer programming construct allowing an object to be invoked or called as though it were an ordinary function, usually with the same syntax.-Description:...
to be declared elsewhere and passed as an argument. This can be partially compensated for by using a library such as Boost
Boost library
Boost is a set of free software libraries that extend the functionality of C++.-Overview:Most of the Boost libraries are licensed under the Boost Software License, designed to allow Boost to be used with both free and proprietary software projects...
and using lambda to implicitly generate function objects with familiar infix operator syntax. However, because Boost is implemented at the library level, rather than intrinsically in the language, certain operations have to be done via workarounds.
The current standard of C++, C++11, natively supports lambda function syntax, allowing the function template body to be declared inline.
Here is an example of for-each iteration using a lambda function:
ContainerType C; // Any standard container type of ItemType elements
// A for-each iteration loop with a lambda function
std::for_each(C.begin, C.end, [](const ItemType& I){ std::cout << I << std::endl; });
The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...
are called "enumerators" and represented by the IEnumerator interface. IEnumerator provides a MoveNext method, which advances to the next element and indicates whether the end of the collection has been reached; a Current property, to obtain the value of the element currently being pointed at; and an optional Reset method, to rewind the enumerator back to its initial position. The enumerator initially points to a special value before the first element, so a call to MoveNext is required to begin iterating.
Enumerators are typically obtained by calling the GetEnumerator method of an object implementing the IEnumerable interface. Container classes typically implement this interface. However, the foreach
Foreach
For each is a computer language idiom for traversing items in a collection. Foreach is usually used in place of a standard for statement. Unlike other for loop constructs, however, foreach loops usually maintain no explicit counter: they essentially say "do this to everything in this set",...
statement in C# can operate on any object providing such a method, even if it doesn't implement IEnumerable. Both interfaces were expanded into generic
Generic programming
In a broad definition, generic programming is a style of computer programming in which algorithms are written in terms of to-be-specified-later types that are then instantiated when needed for specific types provided as parameters...
versions in .NET 2.0.
The following shows a simple use of iterators in C# 2.0:
// explicit version
IEnumerator iter = list.GetEnumerator;
while (iter.MoveNext)
Console.WriteLine(iter.Current);
// implicit version
foreach (MyType value in list)
Console.WriteLine(value);
C# 2.0 also supports generators: a method which is declared as returning IEnumerator (or IEnumerable), but uses the "yield return" statement to produce a sequence of elements instead of returning an object instance, will be transformed by the compiler into a new class implementing the appropriate interface.
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
JDK 1.2 release, the interface allows the iteration of container classes. Each Iterator provides a and method, and may optionally support a method. Iterators are created by the corresponding container class, typically by a method named iterator.
The next method advances the iterator and returns the value pointed to by the 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 iter = list.iterator;
//Iterator iter = list.iterator; in J2SE 5.0
while (iter.hasNext) {
System.out.println(iter.next);
}
For collection types which support it, the remove method of the iterator removes the most recently visited element from the container. Most other types of modification to the container while iterating are unsafe.
Additionally, for there is a with a similar API but that allows forward and backward iteration, provides its current index in the list and allows setting of the list element at its position.
Java Platform, Standard Edition or Java SE is a widely used platform for programming in the Java language. It is the Java Platform used to deploy portable applications for general use...
5.0 release of Java introduced the interface to support an enhanced for (foreach
Foreach
For each is a computer language idiom for traversing items in a collection. Foreach is usually used in place of a standard for statement. Unlike other for loop constructs, however, foreach loops usually maintain no explicit counter: they essentially say "do this to everything in this set",...
) loop for iterating over collections and arrays. Iterable defines the method that returns an Iterator. Using the enhanced for loop, the preceding example can be rewritten as
for (MyType obj : list) {
System.out.print(obj);
}
Ruby
Ruby implements iterators quite differently; all iterations are done by means of passing callback closures to container methods - this way Ruby not only implements basic iteration but also several patterns of iteration like function mapping, filters and reducing. Ruby also supports an alternative syntax for the basic iterating method each, the following three examples are equivalent:
(0...42).each do |n|
puts n
end
...and...
for n in 0...42
puts n
end
or even shorter
42.times do |n|
puts n
end
Ruby can also iterate over fixed lists by using Enumerators and either calling their #next method or doing a for each on them, as above.
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
are a fundamental part of the language and in many cases go unseen as they are implicitly used in the for (foreach
Foreach
For each is a computer language idiom for traversing items in a collection. Foreach is usually used in place of a standard for statement. Unlike other for loop constructs, however, foreach loops usually maintain no explicit counter: they essentially say "do this to everything in this set",...
) statement, in list comprehensions, and in generator expressions. All of Python's standard built-in sequence types support iteration, as well as many classes which are part of the standard library. The following example shows typical implicit iteration over a sequence:
In computer science, an associative array is an abstract data type composed of a collection of pairs, such that each possible key appears at most once in the collection....
) can also be directly iterated over, when the dictionary keys are returned; or the items method of a dictionary can be iterated over where it yields corresponding key,value pairs as a tuple:
for key in dictionary:
value = dictionary[key]
print(key, value)
for key, value in dictionary.items:
print(key, value)
Iterators however can be used and defined explicitly. For any iterable sequence type or class, the built-in function iter is used to create an iterator object. The iterator object can then be iterated with the next function, which uses the __next__ method internally, which returns the next element in the container. (The previous statement applies to Python 3.x. In Python 2.x, the next method is equivalent.) A StopIteration exception will be raised when no more elements are left. The following example shows an equivalent iteration over a sequence using explicit iterators:
it = iter(sequence)
while True:
try:
value = it.next # in Python 2.x
value = next(it) # in Python 3.x
except StopIteration:
break
print(value)
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's generators implement this iteration protocol
Protocol (object-oriented programming)
In object-oriented programming, a protocol or interface is a common means for unrelated objects to communicate with each other. These are definitions of methods and values which the objects agree upon in order to cooperate....
PHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document...
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
and some other languages. This simply gives an easy way to iterate over arrays. foreach works only on arrays in PHP 4, and will issue an error when you try to use it on a variable with a different data type or an uninitialized variable.
In PHP 5, foreach is allowed on object iterating through all the public members.
There are two syntaxes; the second is a minor but useful extension of the first.
Example A
foreach (array_expression as $value) {
echo "$value\n";
}
Example B
foreach (array_expression as $key => $value) {
echo "($key)$value\n";
}
The Example A loops over the array given by array_expression. On each loop, the value of the current element is assigned to $value and the internal array pointer is advanced by one (so on the next loop, you'll be looking at the next element).
The Example B has the same functionality as above. Additionally, the current element's key (in this case, array_expression) will be assigned to the variable $key on each loop.
The Iterator interface is pre-defined in PHP 5 and objects can be customized to handle iteration.
class MyIterator implements Iterator {
private $var = array;
public function __construct($array) {
if (is_array($array)) {
$this->var = $array;
}
}
public function rewind {
echo "rewinding\n";
reset($this->var);
}
public function current {
$var = current($this->var);
echo "current: $var\n";
return $var;
}
public function key {
$var = key($this->var);
echo "key: $var\n";
return $var;
}
public function next {
$var = next($this->var);
echo "next: $var\n";
return $var;
}
public function valid {
$var = $this->current ! false;
echo "valid: {$var}\n";
return $var;
}
}
?>
These methods are all being used in a complete foreach($obj AS $key=>$value) sequence.
The methods of Iterators are executed in the following order:
1. rewind
2. while valid {
2.1 current in $value
2.3 key in $key
2.4 next
}
MATLAB is a numerical computing environment and fourth-generation programming language. Developed by MathWorks, MATLAB allows matrix manipulations, plotting of functions and data, implementation of algorithms, creation of user interfaces, and interfacing with programs written in other languages,...
supports both external and internal implicit iteration using either "native" arrays or cell arrays. In the case of external iteration where the onus is on the user to advance the traversal and request next elements, one can define a set of elements within an array storage structure and traverse the elements using the for-loop construct. For example,
% Define an array of integers
myArray = [1,3,5,7,11,13];
for n = myArray
% ... do something with n
disp(n) % Echo integer to Command Window
end
traverses an array of integers using the for keyword.
In the case of internal iteration where the user can supply an operation to the iterator to perform over every element of a collection, many built-in operators and MATLAB functions are overloaded to execute over every element of an array and return a corresponding output array implicitly. Furthermore, the arrayfun and cellfun functions can be leveraged for performing custom or user defined operations over "native" arrays and cell arrays respectively. For example,
function simpleFun
% Define an array of integers
myArray = [1,3,5,7,11,13];
% Perform a custom operation over each element
myNewArray = arrayfun(@(a)myCustomFun(a),myArray);
% Echo resulting array to Command Window
myNewArray
function outScalar = myCustomFun(inScalar)
% Simply multiply by 2
outScalar = 2*inScalar;
defines a primary function simpleFun which implicitly applies custom subfunction myCustomFun to each element of an array using built-in function arrayfun.
Alternatively, it may be desirable to abstract the mechanisms of the array storage container from the user by defining a custom object-oriented MATLAB implementation of the Iterator Pattern. Such an implementation supporting external iteration is demonstrated in MATLAB Central File Exchange item Design Pattern: Iterator (Behavioral). This is written in the new class-definition syntax introduced with MATLAB software version 7.6 (R2008a)
and features a one-dimensional cell array realization of the List Abstract Data Type (ADT) as the mechanism for storing a heterogeneous (in data type) set of elements. It provides the functionality for explicit forward List traversal with the hasNext, next and reset methods for use in a while-loop.
See also
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
In object-oriented programming, the iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container's elements...
In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure on which it operates. A practical result of this separation is the ability to add new operations to existing object structures without modifying those...
In computer science, the term range may refer to one of three things:# The possible values that may be stored in a variable.# The upper and lower bounds of an array.# An alternative to iterator.-Range of a variable:...
In software engineering, a design pattern is a general reusable solution to a commonly occurring problem within a given context in software design. A design pattern is not a finished design that can be transformed directly into code. It is a description or template for how to solve a problem that...
