Iterators

In the STL, an iterator is an object used to access and inspect elements in an STL container. Its behavior is similar to that of a pointer, but it encapsulates some validity checks and provides a uniform access format. Similar concepts exist in many other high-level languages, such as Python's __iter__ function and C#'s IEnumerator.

Basic Usage

Iterators may sound obscure, but an iterator itself can actually be regarded as a data pointer. An iterator mainly supports two operators: increment (++) and dereference (the unary * operator). Increment moves the iterator, while dereference obtains or modifies the element it points to.

The type of an iterator pointing to an element in an STL container container is generally container::iterator.

Iterators can be used to traverse a container. For example, the following two for loops have the same effect:

vector<int> data(10);

for (int i = 0; i < data.size(); i++)
  cout << data[i] << endl;  // Access elements by index

for (vector<int>::iterator iter = data.begin(); iter != data.end(); iter++)
  cout << *iter << endl;  // Access elements with an iterator
// After C++11, auto iter = data.begin() can be used to simplify the code above

Classification

In the STL definition, iterators are divided into the following categories according to the operations they support:

• InputIterator: only required to support copying, increment, and dereference access.

• OutputIterator: only required to support copying, increment, and dereference assignment.

• ForwardIterator: on top of InputIterator, supports multiple traversals and iterator dereference access, and guarantees that repeated accesses produce consistent results.

• BidirectionalIterator: on top of ForwardIterator, supports decrement (that is, reverse access).

• RandomAccessIterator: on top of BidirectionalIterator, supports addition, subtraction, and comparison (that is, random access).

• ContiguousIterator: on top of RandomAccessIterator, requires that for a dereferenceable iterator a + n, *(a + n) be equivalent to *(std::address_of(*a) + n) (that is, contiguous storage, where a is a contiguous iterator and n is an integer value).

  ContiguousIterator was formally introduced in C++17.

These iterator categories are not mutually exclusive. In fact, except for OutputIterator, each iterator earlier in the list contains the iterators later in the list. For example, a BidirectionalIterator can also be used wherever a ForwardIterator is required. Starting with ForwardIterator, if these iterators also implement the functionality of OutputIterator (that is, allow writing), they are called mutable iterators. Thus, categories such as "mutable random-access iterator" can be derived.

Different STL containers support different iterator types, so care is needed when using them.

A pointer to an array satisfies all requirements of a contiguous iterator (or a random-access iterator for C++14 and earlier) and can be used as a contiguous iterator.

Related Functions

Many STL functions use iterators as parameters.

You can use std::advance(it, n) to move iterator it backward by n steps; if n is negative, it moves forward accordingly. In this case, the iterator must satisfy the requirements of a bidirectional iterator; otherwise, the behavior is undefined.

After C++11, std::next(it) can be used to obtain the successor of the forward iterator it (the iterator it itself remains unchanged), and std::next(it, n) can be used to obtain the successor of the forward iterator it with number n.

After C++11, std::prev(it) can be used to obtain the predecessor of the bidirectional iterator it (the iterator it itself remains unchanged), and std::prev(it, n) can be used to obtain the predecessor of the bidirectional iterator it with number n.

STL containers generally support access starting from one or both ends, as well as support for the const qualifier. For example, a container's begin() function obtains an iterator pointing to its first element, rbegin() obtains a reverse iterator pointing to its last element, cbegin() obtains a const iterator pointing to its first element, and end() obtains an iterator pointing to the end of the container (the "end" is not the last element; it can be regarded as the successor of the last element. The predecessor of the "end" is the last element in the container, while the end itself does not point to any element).

See Iterator library - cppreference.com for more usage.