In computer programming , an iterator is an object that progressively provides access to each item of a collection , in order.
41-420: 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
82-439: A stream is a sequence of potentially unlimited data elements made available over time. A stream can be thought of as items on a conveyor belt being processed one at a time rather than in large batches. Streams are processed differently from batch data . Normal functions cannot operate on streams as a whole because they have potentially unlimited data. Formally, streams are codata (potentially unlimited), not data (which
123-447: A collection while applying a function to each element. For example, Python's map function applies a caller-defined function to each element: 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 collection without an explicit iterator. An iterator object may exist, but
164-464: A common base trait - scala.collection.TraversableOnce . However, because of the rich set of methods available in the Scala collections library, such as map , collect , filter 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
205-446: 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
246-458: A lambda function: Introduced in the Java JDK 1.2 release, the java.util.Iterator interface allows the iteration of container classes. Each Iterator provides a next() and hasNext() method, and may optionally support a remove() method. Iterators are created by the corresponding container class, typically by a method named iterator() . The next() method advances
287-501: A method, even if it does not implement IEnumerable ( 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: C# 2.0 also supports generators : a method that is declared as returning IEnumerator (or IEnumerable ), but uses the " yield return " statement to produce a sequence of elements instead of returning an object instance, will be transformed by
328-403: A separate const_iterator 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 const_iterator is used) can be done using iterators alone. But container types may also provide methods like insert or erase that modify
369-449: A singly linked list instead of a vector) would be a better choice (globally more efficient) if the stability of the iterators is needed. Iterators can be categorised according to their functionality. Here is a (non-exhaustive) list of iterator categories: Different languages or libraries used with these languages define iterator types. Some of them are Iterators in the .NET Framework (i.e. C#) are called "enumerators" and represented by
410-496: Is a java.util.ListIterator 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 Iterable interface to support an enhanced for ( foreach ) loop for iterating over collections and arrays. Iterable defines the iterator() method that returns an Iterator . Using
451-409: Is a data type that acts as an abstraction of a class . It describes a set of method signatures , the implementations of which may be provided by multiple classes that are otherwise not necessarily related to each other. A class which provides the methods listed in a protocol is said to adopt the protocol, or to implement the interface. If objects are fully encapsulated then the protocol
SECTION 10
#1732798078023492-466: 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 std::for_each() , std::copy() and std::accumulate() . When used they must be initialized with existing iterators, usually begin and end , that define the range over which iteration occurs. But no explicit iterator object
533-431: Is designed to resemble that of C 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
574-402: Is finite). Functions that operate on a stream producing another stream are known as filters and can be connected in pipelines in a manner analogous to function composition . Filters may operate on one item of a stream at a time or may base an item of output on multiple items of input such as a moving average . The term "stream" is used in a number of similar ways: Streams can be used as
615-408: 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
656-580: Is known as duck typing . For example, in Python , any class can implement an __iter__ method and be used as a collection . Type classes in languages like Haskell , or module signatures in ML and OCaml , are used for many of the things that protocols are used for. In Rust , interfaces are called trait s. This computer-programming -related article is a stub . You can help Misplaced Pages by expanding it . Input stream In computer science ,
697-423: 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: In Ruby, iteration requires accessing an iterator property: 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
738-672: Is sometimes also referred to as a loop iterator. A loop counter , however, only provides the traversal functionality and not the element access functionality. 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
779-399: Is subsequently exposed as the iteration proceeds. This example shows the use of for_each . The same can be achieved using std::copy , passing a std::ostream_iterator value as third iterator: 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
820-1083: Is the only way in which they may be accessed by other objects. For example, in Java , the Comparable interface specifies a method compareTo() which implementing classes must implement. This means that a sorting method, for example, can sort a collection of any objects of types which implement the Comparable interface, without having to know anything about the inner nature of the class (except that two of these objects can be compared by means of compareTo() ). Some programming languages provide explicit language support for protocols ( Ada , C# , D , Dart , Delphi , Go , Java , Logtalk , Object Pascal , Objective-C , OCaml , PHP , Racket , Seed7 , Swift , Python 3.8). In languages supporting multiple inheritance , such as C++ , interfaces are implemented as abstract classes . In languages without explicit support, protocols are often still present as conventions. This
861-473: 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 collection (for example
SECTION 20
#1732798078023902-473: 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
943-481: The remove() 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 ( hasNext() has previously returned false). Additionally, for java.util.List there
984-461: The std::vector<T> container type allows traversal either using (raw) pointers to its elements (of type *<T> ), or values of a special type std::vector<T>::iterator , 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
1025-483: The CLU programming language in 1974. An iterator provides access to an element of a collection ( element access ) and can change its internal state to provide access to the next element ( element traversal ). 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
1066-422: 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
1107-578: The compiler into a new class implementing the appropriate interface. 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
1148-414: The enhanced for loop, the preceding example can be rewritten as Some containers also use the older (since 1.0) Enumeration class. It provides hasMoreElements() and nextElement() methods but has no methods to modify the container. 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
1189-599: 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
1230-408: The iterator and returns the value pointed to by the iterator. The first element is obtained upon the first call to next() . To determine when all the elements in the container have been visited the hasNext() test method is used. The following example shows a simple use of iterators: To show that hasNext() can be called repeatedly, we use it to insert commas between the elements but not after
1271-414: 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
Iterator - Misplaced Pages Continue
1312-435: 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,
1353-418: The limiting iterators, in terms of the number of applications of the operator ++ 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
1394-570: 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: 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
1435-441: The range, but rather just beyond the end of the range. For traversal of an entire container, the begin() method provides the lower limit, and end() 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. Iterator types are separate from the container types they are used with, though
1476-463: The single line to the file. The JavaConversions 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 would not. Interface (object-oriented programming) In object-oriented programming , an interface or protocol type
1517-426: 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
1558-503: The subsequent iteration does not expose an iterator object to the user. 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 . Instead of using an iterator, many languages allow
1599-401: 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
1640-438: 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: 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
1681-471: 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: An internal iterator is a higher order function (often taking anonymous functions ) that traverses