Skip to content

Iterators

In the STL, an iterator is an object used to access and inspect elements within STL containers. Its behavior is similar to that of a pointer, but it encapsulates some validity checks and provides a uniform access pattern. 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 essentially, an iterator can be thought of as a data pointer. Iterators primarily support two operators: increment (++) and dereference (the unary * operator). Increment is used to move the iterator, while dereference can retrieve or modify 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 containers. For example, the following two for loops have the same effect:

1
2
3
4
5
6
7
8
vector<int> data(10);

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

for (vector<int>::iterator iter = data.begin(); iter != data.end(); iter++)
  cout << *iter << endl;  // Access elements using iterator
// In C++11 and later, you can simplify the above code with auto iter = data.begin()

Using auto in Competitions

Most contestants prefer using auto to replace verbose iterator declarations. According to the Supplementary Notice on Programming Language Restrictions in NOI Series Activities released in September 2021, NOI series competitions (including CSP J/S) will use C++14 for evaluation, which already supports the auto keyword.

Categories

In the STL definition, iterators are categorized into the following types based on the operations they support:

  • InputIterator: Only requires support for copying, incrementing, and dereferencing for access.
  • OutputIterator: Only requires support for copying, incrementing, and dereferencing for assignment.
  • ForwardIterator: Builds upon InputIterator by supporting multiple traversals and dereference accesses, ensuring consistent results across multiple accesses.
  • BidirectionalIterator: Builds upon ForwardIterator by supporting decrement (i.e., reverse access).
  • RandomAccessIterator: Builds upon BidirectionalIterator by supporting addition, subtraction, and comparison operations (i.e., random access).

  • ContiguousIterator: Builds upon RandomAccessIterator by requiring that for any dereferenceable iterator a + n, *(a + n) is equivalent to *(std::address_of(*a) + n) (i.e., contiguous storage, where a is a contiguous iterator and n is an integer value).

    ContiguousIterator was formally introduced in C++17.

Why is it called an InputIterator?

"Input" refers to "being able to obtain input from the iterator," while "output" refers to "being able to output to the iterator."

The agents of "input" and "output" are other parts of the program, not the iterator itself.

These iterator categories are not mutually exclusive. In fact, except for output iterators, each category in the list includes the ones that follow. For example, a bidirectional iterator can be used where a forward iterator is required. Starting from forward iterators, if these iterators also implement the functionality of output iterators (i.e., allowing write operations), they are called mutable iterators. Thus, categories such as "mutable random access iterator" can be derived.

Different STL containers support different iterator types, which should be noted when using them.

Array pointers satisfy all requirements of contiguous iterators (or random access iterators for C++14 and earlier) and can be used as contiguous iterators.

Many STL functions use iterators as parameters.

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

In C++11 and later, you can use std::next(it) to obtain the successor of forward iterator it (the iterator it remains unchanged), and std::next(it, n) to obtain the n-th successor of forward iterator it.

In C++11 and later, you can use std::prev(it) to obtain the predecessor of bidirectional iterator it (the iterator it remains unchanged), and std::prev(it, n) to obtain the n-th predecessor of bidirectional iterator it.

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

For more usage details, see Iterator library - cppreference.com.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用