Iterator

In computer programming, an iterator is an object that progressively provides access to each item of a collection, in order.
A collection may provide multiple iterators via its interface that provide items in different orders, such as forwards and backwards.
An iterator is often implemented in terms of the structure underlying a collection implementation and is often tightly coupled to the collection to enable the operational semantics of the iterator.
An iterator is behaviorally similar to a database cursor.
Iterators date to the CLU programming language in 1974.

Pattern

An iterator provides access to an element of a collection and can change its internal state to provide access to the next element. It also provides for creation and initialization to a first element and indicates whether all elements have been traversed. In some programming contexts, an iterator provides additional functionality.
An iterator allows a consumer to process each element of a collection while isolating the consumer from the internal structure of the collection. The collection can store elements in any manner while the consumer can access them as a sequence.
In object-oriented programming, an iterator class is usually designed in tight coordination with the corresponding collection class. Usually, the collection 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.

Generator

One way of implementing an iterator is via 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 yield statement follows:

from typing import Generator
def fibonacci -> Generator:
a, b = 0, 1
for _ in range:
yield a
a, b = b, a + b
for number in fibonacci: # The generator constructs an iterator
print

Internal iterator

An internal iterator is a higher-order function that traverses a collection while applying a function to each element. For example, Python's map function applies a caller-defined function to each element:

from typing import Iterator
digits: list =
squared_digits: Iterator = map

Iterating over this iterator would result in 0, 1, 4, 9, 16,..., 81.

Implicit iterator

Some object-oriented languages such as C#, C++, Delphi, Go, Java, Lua, Perl, Python, Ruby provide an intrinsic way of iterating through the elements of a collection without an explicit iterator. An iterator object may exist, but is not represented in the source code.
An implicit iterator is often manifest in language syntax as foreach.
In Python, a collection object can be iterated directly:

for value in iterable:
print

In Ruby, iteration requires accessing an iterator property:

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, and the programmer only provides the operation to execute at each step.
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: list =

Sometimes the implicit hidden nature is only partial. The C++ language has a few function templates for implicit iteration, such as for_each. These functions still require explicit iterator objects as their initial input, but the subsequent iteration does not expose an iterator object to the user.

Stream

Iterators are a useful abstraction of input streams – they provide a potentially infinite iterable 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.

Contrast with indexing

Instead of using an iterator, many languages allow the use of a subscript operator and a loop counter to access each element. Although indexing may be used with collections, the use of iterators may have advantages such as:

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 ensuring that elements cannot be skipped or that a previously visited element cannot be accessed a second time.
An iterator may allow the collection 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 collection with predictable results. With indexing this is problematic since the index numbers must change.

The ability of a collection 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 collection that it does preclude modification of the underlying collection without invalidating itself.
For collections that may move around their data in memory, the only way to not invalidate the iterator is, for the collection, 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 collection, updating them all will drastically impair the complexity guarantee on the collection's operations.
An alternative way to keep the number of updates bound relatively to the collection size would be to use a kind of handle mechanism, that is a collection of indirect pointers to the collection's elements that must be updated with the collection, 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 and efficiency. Most of the time, the added security is not worth the efficiency price to pay for it. Using an alternative collection would be a better choice if the stability of the iterators is needed.

Classification

Types

Different languages or libraries used with these languages define iterator types. Some of them are

Type	Languages
Array iterator	PHP, R
Caching iterator	PHP
Constant iterator	C++, PHP
Directory iterator	PHP, Python
Filter iterator	PHP, R
Limit iterator	PHP
List iterator	C#, Java, R
Recursive array iterator	PHP
XML iterator	PHP

In different programming languages

.NET

Iterators in the.NET Framework 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. a Current property, to obtain the value of the element currently being pointed at;Container classes typically implement this interface. However, the foreach statement in C# can operate on any object providing such a method, even if it does not implement IEnumerable. 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 iter = list.GetEnumerator;
while )
// implicit version
foreach

C# 2.0 also supports generators: a method that is declared as returning IEnumerator, 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.

Category	Languages
Bidirectional iterator	C++, Rust
Forward iterator	C++
Input iterator	C++
Output iterator	C++
Random access iterator	C++
Trivial iterator	C++