Iterator

In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists. 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. An iterator performs traversal and also gives access to data elements in a container, but does not itself 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 cursor. Iterators date to the CLU programming language in 1974.
Description.
Internal Iterators.
Internal iterators are higher order functions (often taking anonymous functions) such as "map", "reduce" etc., implementing the traversal across a container, applying the given function to every element in turn.
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.
A loop counter is sometimes also referred to as a loop iterator. A loop counter, however, only provides the traversal functionality and not the element access functionality.
Generators.
One way of implementing iterators is to use a restricted form of coroutine, known as a generator. By contrast with a subroutine, a generator coroutine 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. There are subtle differences and distinctions in the use of the terms "generator" and "iterator", which vary between authors and languages. In Python, a generator is an iterator constructor: a function that returns an iterator. An example of a Python generator returning an iterator for the Fibonacci numbers using Python's codice_1 statement follows:
def fibonacci(limit):
 a, b = 0, 1
 for _ in range(limit):
 yield a
 a, b = b, a + b
for number in fibonacci(100): # The generator constructs an iterator
 print(number)
Implicit iterators.
Some object-oriented languages such as C#, C++ (later versions), Delphi (later versions), Go, Java (later versions), Lua, Perl, Python, Ruby 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" statement (or equivalent), such as in the following Python example:
for value in iterable:
 print(value)
In Python, an iterable is an object which can be converted to an iterator, which is then iterated through during the for loop; this is done implicitly.
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 (that controls all aspects of iteration), and the programmer only provides the operation to execute at each step (using an anonymous function).
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++ language has a few function templates for implicit iteration, such as codice_2. These functions still require explicit iterator objects as their initial input, but the subsequent iteration does not expose an iterator object to the user.
Streams.
Iterators are a useful abstraction of input streams – they provide a potentially infinite iterable (but not necessarily indexable) object. Several languages, such as Perl and Python, implement streams as iterators. In Python, iterators are objects representing streams of data. Alternative implementations of stream include data-driven languages, such as AWK and sed.
Contrasting with indexing.
In procedural languages it is common to use the subscript operator and a loop counter 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:
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. This assertion must however be taken with a grain of salt, because more often than not, for efficiency reasons, the iterator implementation is so tightly bound to the container that it does preclude modification of the underlying container without invalidating itself.
For containers that may move around their data in memory, the only way to not invalidate the iterator is, for the container, to somehow keep track of all the currently alive iterators and update them on the fly. Since the number of iterators at a given time may be arbitrarily large in comparison to the size of the tied container, updating them all will drastically impair the complexity guarantee on the container's operations.
An alternative way to keep the number of updates bound relatively to the container size would be to use a kind of handle mechanism, that is a collection of indirect pointers to the container's elements that must be updated with the container, and let the iterators point to these handles instead of directly to the data elements. But this approach will negatively impact the iterator performance, since it must effectuate a double pointer following to access the actual data element. This is usually not desirable, because many algorithms using the iterators invoke the iterators data access operation more often than the advance method. It is therefore especially important to have iterators with very efficient data access.
All in all, this is always a trade-off between security (iterators remain always valid) and efficiency. Most of the time, the added security is not worth the efficiency price to pay for it. Using an alternative container (for example a singly linked list instead of a vector) would be a better choice (globally more efficient) if the stability of the iterators is needed.
Classifying iterators.
Iterator categories.
Iterators can be categorised according to their functionality. Here is a (non-exhaustive) list of iterator categories:
Iterator types.
Different languages or libraries used with these languages define iterator types. Some of them are
In different programming languages.
C# and other .NET languages.
Iterators in the .NET Framework are called "enumerators" and represented by the codice_3 interface. codice_3 provides a codice_5 method, which advances to the next element and indicates whether the end of the collection has been reached; a codice_6 property, to obtain the value of the element currently being pointed at; and an optional codice_7 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 codice_5 is required to begin iterating.
Enumerators are typically obtained by calling the codice_9 method of an object implementing the codice_10 interface. Container classes typically implement this interface. However, the foreach statement in C# can operate on any object providing such a method, even if it doesn't implement codice_10 (duck typing). Both interfaces were expanded into generic versions in .NET 2.0.
The following shows a simple use of iterators in C# 2.0:
// explicit version
IEnumerator<MyType> 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 that is declared as returning codice_3 (or codice_10), but uses the "codice_14" 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.
C++.
The C++ language makes wide use of iterators in its Standard Library, and describes several categories of iterators differing in the repertoire of operations they allow. These include "forward iterators", "bidirectional iterators", and "random access iterators", in order of increasing possibilities. All of the standard container template types provide iterators of one of these categories. Iterators generalize pointers to elements of an array (which indeed can be used as iterators), and their syntax is designed to resemble that of C pointer arithmetic, where the codice_15 and codice_16 operators are used to reference the element to which the iterator points, and pointer arithmetic operators like codice_17 are used modify iterators in traversal of a container.
Traversal using iterators usually involves a single varying iterator, and two fixed iterators that serve to delimit a range to be traversed. The distance between the limiting iterators, in terms of the number of applications of the operator codice_17 needed to transform the lower limit into the upper one, equals the number of items in the designated range; the number of distinct iterator values involved is one more than that. By convention, the lower limiting iterator "points to" the first element in the range, while the upper limiting iterator does not point to any element in the range, but rather just beyond the end of the range.
For traversal of an entire container, the codice_19 method provides the lower limit, and codice_20 the upper limit. The latter does not reference any element of the container at all, but is a valid iterator value that can be compared against.
The following example shows a typical use of an iterator.
std::vector<int> items;
items.push_back(5); // Append integer value '5' to vector 'items'.
items.push_back(2); // Append integer value '2' to vector 'items'.
items.push_back(9); // Append integer value '9' to vector 'items'.
for (auto it = items.begin(); it != items.end(); ++it) { // Iterate through 'items'.
 std::cout « *it; // And print value of 'items' for current index.
// In C++11, the same can be done without using any iterators:
for (auto x : items) {
 std::cout « x; // Print value of each element 'x' of 'items'.
// Each loops print "529".
Iterator types are separate from the container types they are used with, though the two are often used in concert. The category of the iterator (and thus the operations defined for it) usually depends on the type of container, with for instance arrays or vectors providing random access iterators, but sets (which use a linked structure as implementation) only providing bidirectional iterators. A same container type can have more than one associated iterator type; for instance the codice_21 container type allows traversal either using (raw) pointers to its elements (of type codice_22), or values of a special type codice_23, and yet another type is provided for "reverse iterators", whose operations are defined in such a way that an algorithm performing a usual (forward) traversal will actually do traversal in reverse order when called with reverse iterators. Most containers also provide a separate codice_24 type, for which operations that would allow changing the values pointed to are intentionally not defined.
Simple traversal of a container object or a range of its elements (including modification of those elements unless a codice_24 is used) can be done using iterators alone. But container types may also provide methods like codice_26 or codice_27 that modify the structure of the container itself; these are methods of the container class, but in addition require one or more iterator values to specify the desired operation. While it is possible to have multiple iterators pointing into the same container simultaneously, structure-modifying operations may invalidate certain iterator values (the standard specifies for each case whether this may be so); using an invalidated iterator is an error that will lead to undefined behavior, and such errors need not be signaled by the run time system.
Implicit iteration is also partially supported by C++ through the use of standard function templates, such as codice_28,
codice_29
and
codice_30.
When used they must be initialized with existing iterators, usually codice_31 and codice_32, 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 codice_33.
ContainerType<ItemType> c; // Any standard container type of ItemType elements.
void ProcessItem(const ItemType& i) { // Function that 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 codice_34, passing a codice_35 value as third iterator:
std::copy(c.begin(), c.end(), std::ostream_iterator<ItemType>(std::cout, "\n"));
Since C++11, lambda function syntax can be used to specify to operation to be iterated inline, avoiding the need to define a named function. Here is an example of for-each iteration using a lambda function:
ContainerType<ItemType> 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; });
Java.
Introduced in the Java JDK 1.2 release, the interface allows the iteration of container classes. Each codice_36 provides a and method, and may optionally support a method. Iterators are created by the corresponding container class, typically by a method named codice_37.
The codice_38 method advances the iterator and returns the value pointed to by the iterator. The first element is obtained upon the first call to codice_38. To determine when all the elements in the container have been visited the codice_40 test method is used. The following example shows a simple use of iterators:
Iterator iter = list.iterator();
// Iterator<MyType> iter = list.iterator(); // in J2SE 5.0
while (iter.hasNext()) {
 System.out.print(iter.next());
 if (iter.hasNext())
 System.out.print(", ");
To show that codice_40 can be called repeatedly, we use it to insert commas between the elements but not after the last element.
This approach does not properly separate the advance operation from the actual data access. If the data element must be used more than once for each advance, it needs to be stored in a temporary variable. When an advance is needed without data access (i.e. to skip a given data element), the access is nonetheless performed, though the returned value is ignored in this case.
For collection types that support it, the codice_42 method of the iterator removes the most recently visited element from the container while keeping the iterator usable. Adding or removing elements by calling the methods of the container (also from the same thread) makes the iterator unusable. An attempt to get the next element throws the exception. An exception is also thrown if there are no more elements remaining (codice_40 has previously returned false).
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.
The J2SE 5.0 release of Java introduced the interface to support an enhanced codice_44 (foreach) loop for iterating over collections and arrays. codice_45 defines the method that returns an codice_36. Using the enhanced codice_44 loop, the preceding example can be rewritten as
for (MyType obj : list) {
 System.out.print(obj);
Some containers also use the older (since 1.0) codice_48 class. It provides codice_49 and codice_50 methods but has no methods to modify the container.
Scala.
In Scala, iterators have a rich set of methods similar to collections, and can be used directly in for loops. Indeed, both iterators and collections inherit from a common base trait - codice_51. However, because of the rich set of methods available in the Scala collections library, such as codice_52, codice_53, codice_54 etc., it is often not necessary to deal with iterators directly when programming in Scala.
Java iterators and collections can be automatically converted into Scala iterators and collections, respectively, simply by adding the single line
import scala.collection.JavaConversions._
to the file. The codice_55 object provides implicit conversions to do this. Implicit conversions are a feature of Scala: methods that, when visible in the current scope, automatically insert calls to themselves into relevant expressions at the appropriate place to make them typecheck when they otherwise wouldn't.
MATLAB.
MATLAB supports both external and internal implicit iteration using either "native" arrays or codice_56 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 codice_44-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 codice_44 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 codice_59 and codice_60 functions can be leveraged for performing custom or user defined operations over "native" arrays and codice_56 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 codice_62 that implicitly applies custom subfunction codice_63 to each element of an array using built-in function codice_59.
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 codice_56 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 codice_40, codice_38 and codice_68 methods for use in a codice_69-loop.
PHP.
PHP's codice_70 loop was introduced in version 4.0 and made compatible with objects as values in 4.0 Beta 4. However, support for iterators was added in PHP 5 through the introduction of the internal codice_71 interface. The two main interfaces for implementation in PHP scripts that enable objects to be iterated via the codice_70 loop are codice_36 and codice_74. The latter does not require the implementing class to declare all required methods, instead it implements an accessor method (codice_75) that returns an instance of codice_71. The Standard PHP Library provides several classes to work with special iterators. PHP also supports Generators since 5.5.
The simplest implementation is by wrapping an array, this can be useful for type hinting and information hiding.
namespace Wikipedia\Iterator;
final class ArrayIterator extends \Iterator
 private array $array;
 public function __construct(array $array)
 $this->array = $array;
 public function rewind(): void
 echo 'rewinding' , PHP_EOL;
 reset($this->array);
 public function current()
 $value = current($this->array);
 echo "current: {$value}", PHP_EOL;
 return $value;
 public function key()
 $key = key($this->array);
 echo "key: {$key}", PHP_EOL;
 return $key;
 public function next()
 $value = next($this->array);
 echo "next: {$value}", PHP_EOL;
 return $value;
 public function valid(): bool
 $valid = $this->current() !== false;
 echo 'valid: ', ($valid ? 'true' : 'false'), PHP_EOL;
 return $valid;
All methods of the example class are used during the execution of a complete foreach loop (codice_77). The iterator's methods are executed in the following order:
The next example illustrates a PHP class that implements the codice_71 interface, which could be wrapped in an codice_87 class to act upon the data before it is returned to the codice_70 loop. The usage together with the codice_89 constant allows PHP scripts to iterate result sets with billions of rows with very little memory usage. These features are not exclusive to PHP nor to its MySQL class implementations (e.g. the codice_90 class implements the codice_71 interface as well).
mysqli_report(MYSQLI_REPORT_ERROR | MYSQLI_REPORT_STRICT);
$mysqli = new \mysqli('host.example.com', 'username', 'password', 'database_name');
// The \mysqli_result class that is returned by the method call implements the internal Traversable interface.
foreach ($mysqli->query('SELECT `a`, `b`, `c` FROM `table`', MYSQLI_USE_RESULT) as $row) {
 // Act on the returned row, which is an associative array.
Python.
Iterators in Python are a fundamental part of the language and in many cases go unseen as they are implicitly used in the codice_44 (foreach) statement, in list comprehensions, and in generator expressions. All of Python's standard built-in collection types support iteration, as well as many classes that are part of the standard library. The following example shows typical implicit iteration over a sequence:
for value in sequence:
 print(value)
Python dictionaries (a form of associative array) can also be directly iterated over, when the dictionary keys are returned; or the codice_93 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 codice_94 is used to create an iterator object. The iterator object can then be iterated with the codice_38 function, which uses the codice_96 method internally, which returns the next element in the container. (The previous statement applies to Python 3.x. In Python 2.x, the codice_38 method is equivalent.) A codice_98 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 codice_99 method that returns an iterator object. The iterator object then needs to define a codice_96 method that returns the next element.
Python's generators implement this iteration protocol.
Raku.
Iterators in Raku are a fundamental part of the language, although usually users don't have to care about iterators. Their usage is hidden behind iteration APIs such as the codice_44 statement, codice_52, codice_103, list indexing with codice_104, etc. 
The following example shows typical implicit iteration over a collection of values:
my @values = 1, 2, 3;
for @values -> $value {
 say $value
Raku hashes can also be directly iterated over; this yields key-value codice_105 objects. The codice_106 method can be invoked on the hash to iterate over the key and values; the codice_107 method to iterate over the hash's keys; and the codice_108 method to iterate over the hash's values.
my %word-to-number = 'one' => 1, 'two' => 2, 'three' => 3;
for %word-to-number -> $pair {
 say $pair;
for %word-to-number.kv -> $key, $value {
 say "$key: $value" 
for %word-to-number.keys -> $key {
 say "$key => " ~ %word-to-number{$key};
Iterators however can be used and defined explicitly. For any iterable type, there are several methods that control different aspects of the iteration process. For example, the codice_109 method is supposed to return an codice_36 object, and the codice_111 method is supposed to produce and return the next value if possible, or return the sentinel value codice_112 if no more values could be produced. The following example shows an equivalent iteration over a collection using explicit iterators:
my @values = 1, 2, 3;
my $it := @values.iterator; # grab iterator for @values
loop {
 my $value := $it.pull-one; # grab iteration's next value
 last if $value =:= IterationEnd; # stop if we reached iteration's end
 say $value;
All iterable types in Raku compose the codice_45 role, codice_36 role, or both. The codice_45 is quite simple and only requires the codice_109 to be implemented by the composing class. The codice_36 is more complex and provides a series of methods such as codice_111, which allows for a finer operation of iteration in several contexts such as adding or eliminating items, or skipping over them to access other items. Thus, any user-defined class can support standard iteration by composing these roles and implementing the codice_109 and/or codice_111 methods.
The codice_121 class represents a DNA strand and implements the codice_109 by composing the codice_45 role. The DNA strand is split into a group of trinucleotides when iterated over:
subset Strand of Str where { .match(/^^ <[ACGT]>+ $$/) and .chars %% 3 };
class DNA does Iterable {
 has $.chain;
 method new(Strand:D $chain) {
 self.bless: :$chain
 
for DNA.new('GATTACATA') {
 .say
say DNA.new('GATTACATA').map(*.join).join('-');
The codice_124 class composes both the codice_45 and codice_36 roles:
class Repeater does Iterable does Iterator {
 has Any $.item is required;
 has Int $.times is required;
 has Int $!count = 1;
 multi method new($item, $times) {
 self.bless: :$item, :$times;
 
 method pull-one(--> Mu){ 
 if $!count <= $!times {
 $!count += 1;
 return $!item
 else {
 return IterationEnd
for Repeater.new("Hello", 3) {
 .say
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 codice_127, 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 codice_128s and either calling their codice_129 method or doing a for each on them, as above.
Rust.
With Rust one can iterate on element of vectors, or create own iterators. Each iterator has adapters (codice_52, codice_54, codice_132, codice_133, ...).
for n in 0..42 {
 println!("{}", n);
Below the codice_134 function returns a custom iterator.
for i in fibonacci().skip(4).take(4) {
 println!("{}", i);