SUPPORT THE WORK

GetWiki

iterator

ARTICLE SUBJECTS
aesthetics  →
being  →
complexity  →
database  →
enterprise  →
ethics  →
fiction  →
history  →
internet  →
knowledge  →
language  →
licensing  →
linux  →
logic  →
method  →
news  →
perception  →
philosophy  →
policy  →
purpose  →
religion  →
science  →
sociology  →
software  →
truth  →
unix  →
wiki  →
ARTICLE TYPES
essay  →
feed  →
help  →
system  →
wiki  →
ARTICLE ORIGINS
critical  →
discussion  →
forked  →
imported  →
original  →
iterator
[ temporary import ]
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists.WEB
,weblink
, Understanding and Using Iterators
, Gatcomb
, Joshua
, Perl.com
,weblink
, 2005-06-16
, A user-defined iterator usually takes the form of a code reference that, when executed, calculates the next item in a list and returns it. When the iterator reaches the end of the list, it returns an agreed-upon value.
, 2012-08-08
, WEB
,weblink
, A Technique for Generic Iteration and Its Optimization
, Watt
, Stephen M.
, PDF
,
, The University of Western Ontario, Department of Computer Science
,weblink
, 2006-09-16
, Iterators were introduced as constructs to allow looping over abstract data structures without revealing their internal representation.
, 2012-08-08
, WEB
,weblink
, STL Iterators
, Alex Allain
,
, Cprogramming.com - Your resource for C and C++
, You can think of an iterator as pointing to an item that is part of a larger container of items.
, 2012-08-08
, 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). An iterator is behaviorally similar to a database cursor. Iterators date to the CLU programming language in 1974.

Description

{{expert needed|Computer science|2=section|talk=Explicit vs. Implicit, External vs. Internal|date=December 2013}}

Internal Iterators

Internal iterators are higher order functions (often taking anonymous functions) such as map, reduce etc., implementing the traversal across a container, applying the given function to every element in turn.

External iterators and the iterator pattern

An 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).WEB
,weblink
, Difference between an external iterator and an internal iterator
, 2009-04-03
,
, CareerRide.COM
,weblink
, 2009-04-03
, An internal iterator is implemented by the member functions of the class which has the iteration logic. An external iterator is implemented by a separate class which can be attached to the object which has iteration logic. The advantage of external iterator is that, many iterators can be made active simultaneously on the existing or same object.
, 2012-08-08
, 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. 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 is sometimes also referred to as a loop iterator. A loop counter, however, only provides the traversal functionality and not the element access functionality.

Generators

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.WEB
,weblink
, A Technique for Generic Iteration and Its Optimization
, Watt
, Stephen M.
, PDF
,
, The University of Western Ontario, Department of Computer Science
,weblink
, 2006-09-16
, Some authors use the term iterator, and others the term generator. Some make subtle distinctions between the two.
, 2012-08-08
, 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)

Implicit iterators

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 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.JOURNAL
, Freeman
, Eric
,
, Freeman
, Elisabeth
,
, Kathy
, Sierra
,
, Bert
, Bates
,
, Hendrickson
, Mike
,
, Loukides
, Mike
,
, 2004
, Head First Design Patterns
, 1
, 338
, O'REILLY
, paperback
, 978-0-596-00712-6
, 2012-08-09
,weblink
, 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
endThis 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 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.

Streams

{{further|Stream (computing)}}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. Alternative implementations of stream include data-driven languages, such as AWK and sed.

Contrasting with indexing

In 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:WEB
,weblink
, index vs iterator
, Vecerina
, Ivan
,
,
, 2006-02-01
,
, BYTES
,weblink
, 2006-02-01
, An index only can be used for containers that (efficiently) support random access (i.e. direct access to an element at a given position). An iterator is a more general concept. Iterators offer efficient traversal of linked lists, files, and a number of other data structures. It often leads to the generation of more efficient code.
, 2012-08-08
,
  • 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 container 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 container with predictable results. With indexing this is problematic since the index numbers must change.
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 iterators

Iterator categories

Iterators can be categorised according to their functionality. Here is a (non-exhaustive) list of iterator categories:WEB
,weblink
, C++ Iteratoren: Iterator-Kategorien
, Kevin Waterson
,
,
, German
, cppreference.com
,
, 2012-08-09
, WEB
,weblink
, Iterators: Concepts
, Kevin Waterson
,
,
, sgi
,
, 2012-08-09
, {| class="wikitable sortable"! Category !! Languages
| C++
| C++
| C++
| C++
| C++
Standard Template Library>STL)WEB
,weblink
, Types of iterator: Output vs. input vs. forward vs. random access iterator
, larsmans
, 2011-03-06
,
, stackoverflow
,weblink
, 2011-03-06
,
, 2012-08-09
,

Iterator types

Different languages or libraries used with these languages define iterator types. Some of them areWEB
,weblink
, Introduction to SPL: Introduction to Standard PHP Library (SPL)
, Kevin Waterson
,
,
, PHPRO.ORG
,
, 2012-08-09
, {| class="wikitable sortable"! Type !! Languages
PHP, RCOLLIERTITLE=ITERATORS IN RACCESSDATE=16 NOVEMBER 2013,
| PHP
| C++,WEB
,weblink
, concurrent_unordered_set Template Class
,
,
,
, Intel Threading Building Blocks for Open Source
, •The iterator types iterator and const_iterator are of the forward iterator category
, 2012-08-09
, PHP
Python (programming language)>Python
| PHP, R
| PHP
Java (programming language)>Java, R
| PHP
| PHP

In different programming languages

C# and other .NET languages

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. Container classes typically implement this interface. However, the foreach statement in C# can operate on any object providing such a method, even if it doesn't 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:// explicit versionIEnumerator iter = list.GetEnumerator();while (iter.MoveNext())
Console.WriteLine(iter.Current);
// implicit versionforeach (MyType value in list)
Console.WriteLine(value);
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 the compiler into a new class implementing the appropriate interface.

C++

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 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 modify iterators in 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 ++ 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 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 dos 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.std::vector 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 (std::vector::iterator i = items.begin(); i != items.end(); ++i) { // Iterate through 'items'
std::cout


- content above as imported from Wikipedia
- "iterator" does not exist on GetWiki (yet)
- time: 11:48pm EDT - Sun, Sep 23 2018
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 MAY 2016
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
GETWIKI 20 AUG 2014
GETWIKI 19 AUG 2014
GETWIKI 18 AUG 2014
Wikinfo
Culture
CONNECT