Iterators are a generalization of pointers that allow a C++ program to work with different data structures
(for example, containers and ranges) in a uniform manner.
To be able to construct template algorithms that work correctly and
efficiently on different types of data structures, the library formalizes not just the interfaces but also the
semantics and complexity assumptions of iterators.
An input iterator
i
supports the expression
*i,
resulting in a value of some object type
T,
called the
value type
of the iterator.
An output iterator i has a non-empty set of types that are
indirectly_writable to the iterator;
for each such type T, the expression *i = o
is valid where o is a value of type T.
Forward iterators meet all the requirements of input
iterators and can be used whenever
an input iterator is specified;
Bidirectional iterators also meet all the requirements of
forward iterators and can be used whenever a forward iterator is specified;
Random access iterators also meet all the requirements of bidirectional
iterators and can be used whenever a bidirectional iterator is specified;
Contiguous iterators also meet all the requirements of random access
iterators and can be used whenever a random access iterator is specified.
Either the iterator type must provide the typedef-names directly
(in which case iterator_traits pick them up automatically), or
an iterator_traits specialization must provide them.
Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element
of the array, so for any iterator type there is an iterator value that points past the last element of a
corresponding sequence.
After the declaration of an uninitialized pointer x
(as with int* x;),
x must always be assumed to have a singular value of a pointer.
— end example
]
Results of most expressions are undefined for singular values;
the only exceptions are destroying an iterator that holds a singular value,
the assignment of a non-singular value to
an iterator that holds a singular value, and, for iterators that meet the
Cpp17DefaultConstructible requirements, using a value-initialized iterator
as the source of a copy or move operation.
This guarantee is not
offered for default-initialization, although the distinction only matters for types
with trivial default constructors such as pointers or aggregates holding pointers.
— end note
]
In these cases the singular
value is overwritten the same way as any other value.
Most of the library's algorithmic templates that operate on data structures have
interfaces that use ranges.
A range is an iterator and a sentinel
that designate the beginning and end of the computation, or an iterator and a
count that designate the beginning and the number of elements to which the
computation is to be applied.228
An iterator and a sentinel denoting a range are comparable.
A range [i, s)
is empty if i == s;
otherwise, [i, s)
refers to the elements in the data structure starting with the element
pointed to by
i
and up to but not including the element, if any, pointed to by
the first iterator j such that j == s.
A counted rangei+[0, n) is empty if n ==0;
otherwise, i+[0, n) refers to
the n elements in the data structure
starting with the element pointed to by i and up to but not including
the element, if any, pointed to by
the result of n applications of ++i.
A counted range i+[0, n) is valid if and only if n ==0;
or n is positive, i is dereferenceable,
and ++i+[0, -{-}n) is valid.