Editing Iterator (section)

==Contrast with indexing==

Instead of using an iterator, many languages allow 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:<ref>{{cite web
 |url          = http://bytes.com/
 |title        = index vs iterator
 |last1        = Vecerina
 |first1       = Ivan
 |date         = 2006-02-01
 |publisher    = BYTES
 |archive-url  = https://web.archive.org/web/20120809083350/http://bytes.com/
 |archive-date = 2012-08-09
 |quote        = 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.
 |access-date  = 2012-08-08
 |url-status   = bot: unknown
}}</ref>

* Counting loops are not suitable to all data structures, in particular to data structures with no or slow [[random access]], like [[List (computing)|lists]] or [[Tree data structure|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 collection 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 collection with predictable results. With indexing this is problematic since the index numbers must change.

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 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 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 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 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 a singly linked list instead of a vector) would be a better choice (globally more efficient) if the stability of the iterators is needed.

===Classification===

====Categories====

Iterators can be categorised according to their functionality. Here is a (non-exhaustive) list of iterator categories:<ref>{{cite web
 | url        = http://www.phpro.org/tutorials/Introduction-to-SPL.html#2
 | title      = C++ Iteratoren: Iterator-Kategorien
 | author     = Kevin Waterson
 | language   = de
 | publisher  = cppreference.com
 | access-date = 2012-08-09
}}</ref><ref>{{cite web
 | url        = http://www.sgi.com/tech/stl/Iterators.html
 | title      = Iterators: Concepts
 | author     = Kevin Waterson
 | publisher  = sgi
 | access-date = 2012-08-09
}}</ref>

{| class="wikitable sortable"
|-
! Category !! Languages
|-
| Bidirectional iterator || [[C++]], [[Rust (programming language)|Rust]]<ref>{{cite web |title=DoubleEndedIterator in std::iter - Rust |url=https://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html |website=doc.rust-lang.org |access-date=11 May 2025}}</ref>
|-
| Forward iterator || C++
|-
| Input iterator || C++
|-
| Output iterator || C++
|-
| Random access iterator || C++
|-
| Trivial iterator || C++ (old [[Standard Template Library|STL]])<ref>{{cite web
 |url          = https://stackoverflow.com/
 |title        = Types of iterator: Output vs. input vs. forward vs. random access iterator
 |author       = larsmans
 |date         = 2011-03-06
 |publisher    = stackoverflow
 |archive-url  = https://web.archive.org/web/20120808230608/http://stackoverflow.com/
 |archive-date = 2012-08-08
 |access-date  = 2012-08-09
 |url-status   = bot: unknown
}}</ref>
|}

====Types====
Different languages or libraries used with these languages define iterator types. Some of them are<ref>{{cite web
 | url        = http://www.phpro.org/tutorials/Introduction-to-SPL.html#2
 | title      = Introduction to SPL: Introduction to Standard PHP Library (SPL)
 | author     = Kevin Waterson
 | publisher  = PHPRO.ORG
 | access-date = 2012-08-09
}}</ref>

{| class="wikitable sortable"
|-
! Type !! Languages
|-
| Array iterator || [[PHP]], R<ref>{{cite web|last=Collier|first=Andrew|title=Iterators in R|url=http://www.exegetic.biz/blog/2013/11/iterators-in-r/|access-date=16 November 2013|archive-date=18 October 2018|archive-url=https://web.archive.org/web/20181018084806/http://www.exegetic.biz/blog/2013/11/iterators-in-r/|url-status=dead}}</ref> 
|-
| Caching iterator || PHP
|-
| Constant iterator || [[C++]],<ref>{{cite web
 | url      = http://threadingbuildingblocks.org/docs/help/reference/containers_overview/concurrent_unordered_set_cls.htm
 | title      = concurrent_unordered_set Template Class
 | publisher      = Intel Threading Building Blocks for Open Source
 | quote      = •The iterator types iterator and const_iterator are of the forward iterator category
 | access-date      = 2012-08-09
 | archive-url      = https://web.archive.org/web/20150501163238/http://threadingbuildingblocks.org/docs/help/reference/containers_overview/concurrent_unordered_set_cls.htm
 | archive-date      = 2015-05-01
 | url-status      = dead
 }}</ref> PHP
|-
| Directory iterator || PHP, [[Python (programming language)|Python]]
|-
| Filter iterator || PHP, R
|-
| Limit iterator || PHP
|-
| List iterator || [[C Sharp (programming language)|C#]], [[Java (programming language)|Java]],<ref name=HFDPIterators /> R
|-
| Recursive array iterator || PHP
|-
| XML iterator || PHP
|}