Iterator
container, particularly lists.[1][2][3] 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)[citation needed ].
An iterator is behaviorally similar to a database cursor. Iterators date to the CLU programming language in 1974. DescriptionInternal IteratorsInternal iterators are 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.
External iterators and the iterator patternAn 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).[4] 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.[2] 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 , however, only provides the traversal functionality and not the element access functionality.
GeneratorsOne way of implementing iterators is to use a restricted form of 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)
Implicit iteratorsSome 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.[4][6] 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 StreamsIterators 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.[7] Alternative implementations of stream include data-driven languages, such as AWK and sed .
Contrasting with indexingIn 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:[8]
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 iteratorsIterator categoriesIterators can be categorised according to their functionality. Here is a (non-exhaustive) list of iterator categories:[9][10]
Iterator typesDifferent languages or libraries used with these languages define iterator types. Some of them are[12]
In different programming languagesC# and other .NET languagesIterators in the .NET Framework are called "enumerators" and represented by the Enumerators are typically obtained by calling the 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 C++The 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 modify iterators in the 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 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'.
}
// Both of the for 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. One same container type can have more than one associated iterator type; for instance the Simple traversal of a container object or a range of its elements (including modification of those elements unless a Implicit iteration is also partially supported by C++ through the use of standard function templates, such as When used they must be initialized with existing iterators, usually 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 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; });
JavaIntroduced in the Java JDK 1.2 release, the The 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 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 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 (hasNext() has previously returned false).
Additionally, for The foreach) loop for iterating over collections and arrays. : 266 Using the enhanced Iterable defines the iterator() method that returns an Iterator .[18]for 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) ScalaIn 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 - 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 MATLABMATLAB supports both external and internal implicit iteration using either "native" arrays or % 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 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 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 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 List traversal with the hasNext() , next() and reset() methods for use in a while -loop.
PHPStandard PHP Library provides several classes to work with special iterators.[23] PHP also supports Generators since 5.5.[24]
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 (
The next example illustrates a PHP class that implements the 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.
}
PythonIterators in 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 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 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 Python's protocol .
RakuIterators in Raku are a fundamental part of the language, although usually users do not have to care about iterators. Their usage is hidden behind iteration APIs such as the The following example shows typical implicit iteration over a collection of values: my @values = 1, 2, 3;
for @values -> $value {
say $value
}
# OUTPUT:
# 1
# 2
# 3
Raku hashes can also be directly iterated over; this yields key-value my %word-to-number = 'one' => 1, 'two' => 2, 'three' => 3;
for %word-to-number -> $pair {
say $pair;
}
# OUTPUT:
# three => 3
# one => 1
# two => 2
for %word-to-number.kv -> $key, $value {
say "$key: $value"
}
# OUTPUT:
# three: 3
# one: 1
# two: 2
for %word-to-number.keys -> $key {
say "$key => " ~ %word-to-number{$key};
}
# OUTPUT:
# three => 3
# one => 1
# two => 2
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 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;
}
# OUTPUT:
# 1
# 2
# 3
All iterable types in Raku compose the The subset Strand of Str where { .match(/^^ <[ACGT]>+ $$/) and .chars %% 3 };
class DNA does Iterable {
has $.chain;
method new(Strand:D $chain) {
self.bless: :$chain
}
method iterator(DNA:D:){ $.chain.comb.rotor(3).iterator }
};
for DNA.new('GATTACATA') {
.say
}
# OUTPUT:
# (G A T)
# (T A C)
# (A T A)
say DNA.new('GATTACATA').map(*.join).join('-');
# OUTPUT:
# GAT-TAC-ATA
The 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 iterator { self }
method pull-one(--> Mu){
if $!count <= $!times {
$!count += 1;
return $!item
}
else {
return IterationEnd
}
}
}
for Repeater.new("Hello", 3) {
.say
}
# OUTPUT:
# Hello
# Hello
# Hello
RubyRuby 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 (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 RustRust makes use of external iterators throughout the standard library, including in its for i in 0..42 {
println!("{}", i);
}
// Prints the numbers 0 to 41
Specifically, the All collections provided by the standard library implement the Iterators support various adapters ( Users can create custom iterators by creating a type implementing the struct Fibonacci(u64, u64);
impl Fibonacci {
pub fn new() -> Self {
Self(0, 1)
}
}
impl Iterator for Fibonacci {
type Item = u64;
fn next(&mut self) -> Option<Self::Item> {
let next = self.0;
self.0 = self.1;
self.1 = self.0 + next;
Some(next)
}
}
let fib = Fibonacci::new();
for n in fib.skip(1).step_by(2).take(4) {
println!("{n}");
}
// Prints 1, 2, 5, and 13
See also
References
External linksLook up iterator in Wiktionary, the free dictionary.
|