Iterator

The term iterator comes from the field of software development and describes a pointer with which the elements of a set can be iterated (e.g. a list). The term is derived from the mathematical method of iteration . The iterator is usually called the cursor , especially in the database field .

description

An iterator is a special pointer that can be used within a program by the software developer to access elements of a set, in other words a list. Iterators work on the basic principle "If there is another element in the list, then make it available."

In simplified terms, this can be compared to reading a text that is a list of words: “If there is a next word, read it. If there is no more word to follow, the text is finished. ”In each access step called iteration, exactly one word of the text is available for editing.

Many of the iterators used in programming practice provide mechanisms beyond the read access option that remove a currently read element from the list or add a new element to the list, just as words can be inserted or deleted when editing a text.

External iterators and the iterator design pattern

→ Main article : Iterator (design pattern)

An external iterator can be viewed as a kind of pointer that has two primary functions: to reference a certain element in a set of objects (called element access ) and to point to the next element in the set by self-modification (called element traversal ) . Depending on the programming language used and the application, iterators can have additional functionality and different behavior.

The main purpose of the iterator is to allow the user to access any element in a set while isolating them from the set's data structure. This enables the crowd to manage the items in every possible way while acting to the user as if it were a simple sequence or list. An iterator class is designed in close coordination with its container class, i.e. its set. The container class usually provides the functions that are used to create iterators. A counter in a loop (also called a loop counter) is sometimes called a loop iterator. It should be noted that such a counter only maps the element traversal functionality and not the element access functionality.

Implicit iterators

Several object-oriented languages ​​such as Perl , Python , C # , Ruby and newer Java and Delphi versions provide an intrinsic way of iterating through elements without using an explicit iterator object . However, this can also be present, but is not available in the code of the respective programming language if this should be the case.

Implicit iterators are often manifested through the foreach command or its equivalents, as shown in the Python example below:

for value in iterable:
    print(value)

The set / list iterableis run through using the forloop; in each loop pass the variable valuecontains the current element iterable.

Sometimes iterators are also generated directly from the data collection object, as shown in the Ruby example below:

iterable.each do |value|
    puts value
end

Calling the method of eachthe set / list iterablesupplies an iterator, which the doloop steps through element by element. The loop body is puts valueexecuted for each element , with the variable valuecontaining the current element.

This iteration style is also called internal iteration because its code is completely executed in the context of the object to be iterated. This controls all aspects of the iteration, the respective user or programmer only provides the operation for the individual iteration steps by using an anonymous subroutine .

Languages ​​that support so-called list extensions or similar constructs also use the implicit iterators during the creation of the result list, analogous to Python:

names = [person.name for person in roster if person.male]

for ... in ...here is the "loop" above the quantity / list rosterwith "current element variable" person. For each element it is checked whether a condition (for the element) applies ( if person.male), so the quantity is filtered. The remaining elements are copied person.nameto the result nameslist - a list of names.

Sometimes the implicit, hidden nature is only partially present. The programming language C ++ provides the for_each functionality via function templates , this allows the implicit iteration.

The opposite of indexing

The iterator is in contrast to an index or key :

• An iterator can be used to access the associated element directly without knowing the data structure itself. With an index you always need an index and a data structure.
• An iterator is only valid for exactly one data structure. An index can be transferred to other data structures.
• Iterators cannot be serialized . To do this, they must first be converted into an index.

The ability of a container to self-modify while iterating through its elements has proven important in modern, object-oriented programming languages. The interrelationships between the individual objects and the effects of their operations are no longer clear in such languages. Iterators are used to solve this problem.

Generators

A generator is a special form of a coroutine that returns one (or more) element (s) of a sequence each time it is called. This sequence can be a given list, in which case the generator largely corresponds to an iterator. A generator can also only generate the (next) elements when they are called - then it does not need an existing list, as is necessary for the iterator.

Most iterators can be implemented in a natural, intuitive way by generators. Because generators maintain their local state between function calls, they are ideal for implementing complex stateful iterators such as binary tree traversers .

Example of a generator that creates elements instead of reading them from a list:

( Fibonacci sequence ; "return" of the respective value using the Python command yield)

# Ein Generator für die Fibonacci-Folge
def fibonacci(limit_anzahl_elemente):
    a, b = 0, 1

    for _ in range(limit_anzahl_elemente):
        a, b = b, a + b
        yield a

# Die ersten Zahlen der Folge werden berechnet und ausgegeben
for number in fibonacci(100):
    print(number)

Iterators in different programming languages

C # and other .NET languages

Iterators in the .NET framework are called enumerators and are represented by the interface IEnumerator. IEnumeratorprovides a function called MoveNext()which goes to the next element of the set and shows when the end has been reached, as well as a property called Currentto get the value of the current element. Furthermore, an optional Reset()function is offered to return to the beginning. The enumerator returns a special value as an initialization value that marks the beginning. For this reason, it is necessary to MoveNext()execute after initialization .

Enumerators are typically returned by a GetEnumerator()function associated with an object that IEnumerableimplements the interface. The foreach command in C # operates on any such function, even if it does not come from an object that IEnumerableimplements the interface. The following example shows a simple use of iterators in C # 2.0:

// explizite Version
IEnumerator<MyType> iter = list.GetEnumerator();
while (iter.MoveNext())
    Console.WriteLine(iter.Current);

// implizite Version
foreach (MyType item in list)
    Console.WriteLine(item);

C # 2.0 also supports generators: a function that returns as IEnumerable(or also IEnumerator) but yield returnuses the command is automatically converted by the compiler into a new class that implements the appropriate interface.

C ++

The C ++ programming language uses iterators on a large scale and provides iterators of various types such as forward iterators , bidirectional iterators and random access iterators via the C ++ standard library . Each of the standard container classes has iterator types. The syntax of the standard iterators was based on the pointer arithmetic of C. The operators and are used to reference the elements. Other operators such as are used to navigate through the elements. *->++

Iterators are usually used in pairs. One iterator represents the current iteration, while the other represents the end of the iteration. The iterators are generated by the corresponding container class using the standard functions begin()and end(). The iterator that is begin()returned by points to the first element, while the iterator that is end()returned by points to a special value that does not reference any element. If an iterator is placed after the last element, it returns the special value of end(). The following example shows the typical use of an iterator in C ++:

ContainerType c; // Ein beliebiger Standard-Containertyp, wie std::list<sometype>

for (ContainerType::const_iterator constIt = c.begin(); constIt != c.end(); ++constIt) {
    std::cout << *constIt << '\n';
}

There are many different types of iterators with slightly different behavior. Not every type of iterator supports every type of container. However, it is possible for programmers to define their own iterator types by deriving a class from the template std::iterator. The iterator security is defined separately for the different types. The implicit iteration is partially available in C ++ and is provided by the functions std::for_each(), std::copy()and std::accumulate(). Iterators, however, always need an explicit object to initialize them, usually those that are returned by begin()and end(). Once this has been done, the iteration is done implicitly without using the iterator object. The example below shows the use of for_each:

// Ein beliebiger Standard-Containertyp jedes ItemType Elements
ContainerType<ItemType> c;

// Funktion, die Zugriff auf jedes Element besitzt
void processItem(const ItemType& i) {
    std::cout << i << '\n';
}

// Eine for-each-Iterationsschleife
std::for_each(c.begin(), c.end(), processItem);

The same thing can be achieved by using std::copyand std::ostream_iterator:

std::copy(C.begin(), C.end(), std::ostream_iterator<ItemType>(std::cout, "\n"));

One limitation of this technique is that it does not allow the hull to be declared inline. In addition, this requires a function pointer, which has to be declared elsewhere and passed as a parameter. This can be partially compensated for by the use of libraries such as Boost and the use of Lambda, which are used to generate function objects with related infix syntax. Since this functionality is only made available via external libraries, various workarounds , also known as workarounds , must be used.

Java

The interface java.util.Iterator, which was introduced in the Java JDK 1.2, allows the iterating of container classes. Each Iteratorprovides functions called next(), hasNext()as well as an optional function called remove(). Iterators are usually iterator()generated by a function called , which is made available by the corresponding container class. An iterator returns a special value as the initialization value, which marks the beginning. For this reason it is necessary to next()execute after the initialization which returns the first element. The function hasNext()is used to find out whether the last element has already been returned. The following example shows a simple use of iterators in Java:

Iterator iter = list.iterator();

while (iter.hasNext())
    System.out.println(iter.next());

For collections that support it, the optional feature removes remove()the last item that was accessed. Most other such modifications are unsafe. In addition, java.util. Listan iterator named ListIterator, which provides a similar interface that allows forward and backward iteration, returns the index of the current element and can insert the element at a given position.

With J2SE 5.0, the interface was Iterableintroduced, which represents an extended for loop in the sense of foreach. Iterabledefines the function iterator()that Iteratorreturns you. Using the extended for loop, the previous example can be written in the following way:

for (MyType obj: list)
    System.out.print(obj);

MATLAB

MATLAB supports external as well as internal iterators. In the case of an external iteration, in which the user is obliged to provide the next element, several elements can be defined and then run through with a for loop, as the following example shows:

% Definition eines an integer arrays
myArray = [1, 3, 5, 7, 11, 13];

for n = myArray
   % ... etwas mit n machen...
   disp(n) %Integerausgabe zur Kommandozeile
end

In the case of an internal iteration, the user can pass an operation to the iterator to access each element in an array. Many native operators and MATLAB functions are overloaded in order to receive a corresponding output array as an implicit return value. Furthermore, the functions arrayfunand can be used cellfunfor user-defined operations via native and so-called cell arrays .

function simpleFun
% Definition eines an integer arrays
myArray = [1, 3, 5, 7, 11, 13];

% Benutzerdefinierte Operation für jedes Element durchführen
myNewArray = arrayfun(@(a)myCustomFun(a), myArray);

% Arrayausgabe zur Kommandozeile
myNewArray

function outScalar = myCustomFun(inScalar)
% Mit 2 multiplizieren
outScalar = 2 * inScalar;

Alternatively, it may be desirable to abstract the storage mechanisms of the array from programming by providing a custom, object-oriented implementation of the iterator design pattern. Such an implementation, which supports the external iteration, is offered in the MATLAB Central File Exchange item. This design pattern is written according to the new class definition syntax which was introduced with MATLAB version 7.6 (R2008a). Furthermore, a one-dimensional cell array implementation of the List Abstract Data Type is included in order to carry out a heterogeneous storage of each data type. It provides the functionality to process a list with hasNext(), next()and reset()in a while loop.

PHP

With PHP4 a foreachconstruct was introduced that was structured similarly to Perl and many other programming languages. This construct allows a simple way of iterating over arrays. The foreachcommand only works with arrays in PHP4 and will throw an error if you try to use it over another data type or an uninitialized variable. In PHP5 the foreachcommand to iterate over all public members is allowed. The following example shows two different notations, the second is a useful extension of the first notation:

Example A

foreach (array_expression as $value)
    echo "$value\n"

Example B.

foreach (array_expression as $key => $value)
    echo "($key)$value\n";

In example A, an array which is represented by array_expression is iterated over. With each loop pass, the value of the array element is $valueassigned and the internal pointer of the array is pushed forward by one. The next array element is thus returned on the next loop pass. Example B has the same functionality as example A. In addition, the index of the element is assigned to the variable with each loop $keypass.

In PHP5 the iterator interface is predefined, objects can be changed to handle the 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 functions are all used in a complete foreach($obj as $key=>$value)sequence. The iterator methods run in the following order:

  1. rewind()
  2. while valid()
     {
          2.1 current() in $value
          2.3 key() in $key
          2.4 next()
     }

python

Iterators in Python represent a fundamental part of the language, but they are often used implicitly and thus invisibly hidden in language commands. Such commands are e.g. B. for(foreach) in so-called list comprehensions and in generator expressions. All sequential base types as well as many classes of the standard library in Python support iterations. The following example shows a typical iteration over a sequence:

for value in sequence:
    print(value)

Python Dictionaries , a form of associative array, allows it to be iterated directly over itself when the so-called dictionary keys are returned. It can also be iterated over the items function of a dictionary, where it returns the values ​​for key and value according to the following example:

for key in dictionary:
    value = dictionary[key]
    print(key, value)

for key, value in dictionary.items():
    print(key, value)

Iterators in Python can also be explicitly defined and used. For every iterable sequence type or every iterable class, the built-in iter()function is available to generate an iterator object. The iterator object can be used to navigate to the next element with the functions next(), or __next__(). If the end of the set is reached, an StopIterationerror is raised. The following example shows an equivalent implementation of explicit iterators:

it = iter(sequence)

while True:
    try:
        value = it.next()
    except StopIteration:
        break

    print(value)

Every user-defined class can support the standard iteration if a _iter__()function has been defined which generates an iterator object, the iterator must then __next__()define a function that returns the next element. The Python generators implement this iteration protocol.

Ruby

The implementation of the iterators in Ruby differs from most other programming languages: All iterations follow the idea of ​​passing through so-called callback closures to container methods. In this way, Ruby not only implements a basic functionality of iterators, but also maps many iterator design patterns such as: B. so-called function mapping , filters and so-called reducing .

Ruby also supports an alternative syntax for each basic function for iteration:

(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

See also

• Iterator design pattern

Web links

• Joshua Gatcomb: Understanding and Using Iterators . (English)
• A Technique for Generic Iteration and Its Optimization . (PDF; English; 216 kB)
• STL iterators . (English)
• What are iterators? - Reference description. (English)
• Interface IteratorJava API
• .NET interface in MSDN
• Boost C ++ Iterator Library (English)
• PHP: Object Iteration (English)

Individual evidence

1. ↑ std::for_each()
2. ↑ std::copy()
3. ↑ std::accumulate()
4. ↑ std::ostream_iterator
5. ↑ java.util.Iterator Java API Specification
6. ↑ next() Java API Specification
7. ↑ hasNext() Java API Specification
8. ↑ remove() Java API Specification
9. ↑ java.util.List Java API Specification
10. ↑ java.util.ListIterator Java API Specification
11. ↑ Iterable Java API Specification
12. ↑ iterator() Java API Specification
13. ↑ Design Pattern: Iterator (Behavior)