Iterator

An iterator is an object that enables traversa of a container, mostly lists. Iterators are often provided via a container's interface. Though the interface and is 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.

Internal iterators are higher order functions (often taking anonymous functions, but not necessarily) such as map(), reduce() etc., implementing the traversal across a container, applying the given function to every element in turn. An example might be Python's map function:

digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

squared_digits = map(lambda x: x**2, digits) # Iterating over this iterator would result in 0, 1, 4, 9, 16, ..., 81.

An external iterator may be thought of as a pointer with 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.

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.

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 yield 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)