Iterators
Fundamental to the use of the container classes and the associated algorithms provided by the standard library is the concept of an iterator. Abstractly, an iterator is simply a pointer-like object used to cycle through all the elements stored in a container. Because different algorithms need to traverse containers in a variety of fashions, there are different forms of iterator. Each container class in the standard library can generate an iterator with functionality appropriate to the storage technique used in implementing the container. It is the category of iterators required as arguments that chiefly distinguishes which algorithms in the standard library can be used with which container classes.
Range
Just as pointers can be used in a variety of ways in traditional programming, iterators are also used for a number of different purposes. An iterator can be used to denote a specific value, just as a pointer can be used to reference a specific memory location. On the other hand, a pair of iterators can be used to describe a range of values, just as two pointers can be used to describe a contiguous region of memory. In the case of iterators, however, the values being described are not necessarily physically in sequence, but are rather logically in sequence, because they are derived from the same container, and the second follows the first in the order in which the elements are maintained by the container.
Conventional pointers can sometimes be null, meaning they point at nothing. Iterators, as well, can fail to denote any specific value. Just as it is a logical error to dereference a null pointer, it is an error to dereference an iterator that is not denoting a value.
When two pointers that describe a region in memory are used in a C++ program, it is conventional that the ending pointer is not considered to be part of the region. For example, an array named x of length ten is sometimes described as extending from x to x+10, even though the element at x+10 is not part of the array. Instead, the pointer value x+10 is the past-the-end value - the element that is the next value after the end of the range being described. Iterators are used similarly to describe a range. The second value is not considered to be part of the range being denoted. Instead, the second value is a past-the-end element, describing the next value in sequence after the final value of the range. Sometimes, as with pointers to memory, this will be an actual value in the container. Other times it may be a special value, specifically constructed for the purpose. In either case, it is not proper to dereference an iterator that is being used to specify the end of a range.
Just as with conventional pointers, the fundamental operation used to modify an iterator is the increment operator (operator ++). When the increment operator is applied to an iterator that denotes the final value in a sequence, it will be changed to the "past the end" value. An iterator j is said to be reachable from an iterator i if, after a finite sequence of applications of the expression ++i, the iterator i becomes equal to j.
Iterator Ranges
Ranges can be used to describe the entire contents of a container, by constructing an iterator to the initial element and a special "ending" iterator. Ranges can also be used to describe subsequences within a single container, by employing two iterators to specific values. Whenever two iterators are used to describe a range it is assumed, but not verified, that the second iterator is reachable from the first. Errors can occur if this expectation is not satisfied.
In the remainder of this section we will describe the different forms of iterators used by the standard library, as well as various other iterator-related functions.