Editing Standard Template Library (section)

=== Iterators ===
The STL implements five different types of [[iterator]]s. These are ''input iterators'' (that can only be used to read a sequence of values), ''output iterators'' (that can only be used to write a sequence of values), ''forward iterators'' (that can be read, written to, and move forward), ''bidirectional iterators'' (that are like forward iterators, but can also move backwards) and ''{{visible anchor|random-access iterator}}s'' (that can move freely any number of steps in one operation).

A fundamental STL concept is a ''range'' which is a pair of iterators that designate the beginning and end of the computation, and most of the library's algorithmic templates that operate on data structures have interfaces that use ranges.<ref>{{cite web |url=http://stepanovpapers.com/STL/DOC.PDF |title=The Standard Template Library |first1=Alexander | last1=Stepanov | first2=Meng | last2=Lee|date=31 October 1995|access-date=16 December 2018|quote="Most of the library’s algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. [...] in general, a range [i, j) refers to the elements in the data structure starting with the one pointed to by i and up to but not including the one pointed to by j. Range [i, j) is valid if and only if j is reachable from i."}}</ref>

It is possible to have bidirectional iterators act like random-access iterators, so moving forward ten steps could be done by simply moving forward a step at a time a total of ten times. However, having distinct random-access iterators offers efficiency advantages. For example, a vector would have a random-access iterator, but a list only a bidirectional iterator.

Iterators are the major feature that allow the generality of the STL. For example, an algorithm to reverse a sequence can be implemented using bidirectional iterators, and then the same implementation can be used on lists, vectors and [[deque]]s. User-created [[Container (data structure)|containers]] only have to provide an iterator that implements one of the five standard iterator interfaces, and all the algorithms provided in the STL can be used on the container.

This generality also comes at a price at times. For example, performing a search on an [[associative container]] such as a map or set can be much slower using iterators than by calling member functions offered by the container itself. This is because an associative container's methods can take advantage of knowledge of the internal structure, which is opaque to algorithms using iterators.