# Iterator categories and concepts

> C++ has two iterator taxonomies, the legacy named requirements from C++98 and the C++20 iterator concepts, and an iterator can sit at different levels in each. Knowing which one an algorithm consults explains why proxy iterators are random-access in one world and input-only in the other.

- **Source:** C++ Atlas (https://cppatlas.com/topics/iterator-categories-and-concepts)
- **Track:** Iterators, algorithms and ranges
- **Estimated reading time:** 14 minutes
- **ISO C++ clauses:** [iterator.requirements] (https://eel.is/c++draft/iterator.requirements), [iterator.concepts] (https://eel.is/c++draft/iterator.concepts), [iterator.cpp17] (https://eel.is/c++draft/iterator.cpp17), [iterator.traits] (https://eel.is/c++draft/iterator.traits), [iterator.assoc.types] (https://eel.is/c++draft/iterator.assoc.types), [iterator.operations] (https://eel.is/c++draft/iterator.operations)
- **cppreference links:** [Iterator library](https://en.cppreference.com/w/cpp/iterator), [std::iterator_traits](https://en.cppreference.com/w/cpp/iterator/iterator_traits), [std::forward_iterator](https://en.cppreference.com/w/cpp/iterator/forward_iterator), [LegacyForwardIterator](https://en.cppreference.com/w/cpp/named_req/ForwardIterator), [std::iter_value_t and related aliases](https://en.cppreference.com/w/cpp/iterator/iter_t), [std::distance](https://en.cppreference.com/w/cpp/iterator/distance)
- **Prerequisites:** pointers-arrays-and-pointer-arithmetic, concepts-and-constraints

## The one idea

An iterator category is a promise about which operations an iterator supports and what they cost. C++ has made that promise twice. The legacy **named requirements**, spelled *Cpp17InputIterator* through *Cpp17RandomAccessIterator* in the standard, date from C++98 and are checked by nobody: an iterator announces its level through a nested `iterator_category` tag, and algorithms trust the tag. The C++20 **iterator concepts**, `std::input_iterator` through `std::contiguous_iterator`, are real language concepts that the compiler checks, announced through a nested `iterator_concept` tag.

The two ladders look the same, but the rungs are defined differently. The single biggest difference is that the legacy forward iterator must return a real reference from `operator*`, and the C++20 one need not.

> **Mental model.** Every iterator has two report cards. `iterator_category` is graded under the C++98 rules, `iterator_concept` under the C++20 rules, and `std::` algorithms that predate ranges usually read the first while `std::ranges::` algorithms read the second.

## The legacy ladder

Each level adds operations and guarantees to the one below it.

```text
input        *it (read), ++it, it == j          single pass
  forward    + default-constructible, multi-pass, *it is T& or const T&
    bidirectional  + --it
      random access  + it + n, it - j, it[n], <  (all O(1))
        contiguous   + elements adjacent in memory (C++17 requirement, C++20 tag)
output       *it = v, ++it                      single pass, write only
```

The **multi-pass guarantee** is what separates input from forward. For forward iterators, `a == b` implies `++a == ++b`, and incrementing a copy does not change what the original refers to. An `std::istream_iterator` breaks this: copying it does not copy the stream, so once any copy advances, the characters it consumed are gone for everyone. That is why an algorithm like `std::search` that must revisit elements requires forward iterators, while `std::find` accepts input iterators.

The forward requirements also demand that `reference` be `T&` or `const T&`, where `T` is the value type. That clause, written for C++98, is the one proxy iterators cannot meet. Output iterators sit off to the side: they promise only that `*it = value` followed by `++it` works, and their `value_type` is usually `void`.

## The C++20 concepts

C++20 rebuilt the hierarchy on top of smaller concepts: `std::indirectly_readable`, `std::weakly_incrementable`, `std::incrementable`, and `std::sentinel_for`. The result differs from the legacy rules in ways that are deliberate.

- `std::input_iterator` does not require `==` between iterators, because the end of an input range is usually a sentinel of a different type. It does not require copyability, and postfix `++` may return `void`. A move-only generator iterator is a valid C++20 input iterator.
- `std::forward_iterator` adds `std::incrementable`, which brings in `std::regular` (copyable, default-initializable, equality comparable) and the multi-pass guarantee. It says nothing about `reference` being a language reference.
- `std::contiguous_iterator` does require `iter_reference_t<I>` to be an lvalue reference, and `std::to_address` to work, since contiguity is about real memory.

```cpp
#include <cstddef>
#include <iterator>

struct Gen {                       // move-only, no operator==
  using difference_type = std::ptrdiff_t;
  using value_type = int;
  int n = 0;
  Gen() = default;
  Gen(Gen&&) = default;
  Gen& operator=(Gen&&) = default;
  int operator*() const { return n; }
  Gen& operator++() { ++n; return *this; }
  void operator++(int) { ++n; }
};

static_assert(std::input_iterator<Gen>);     // OK in C++20
static_assert(!std::forward_iterator<Gen>);  // not copyable, so not multi-pass
```

Which tag does a concept consult? The standard defines an exposition-only alias, `ITER_CONCEPT(I)`. It uses `iterator_concept` if present, falls back to `iterator_category`, and, if `iterator_traits<I>` is the unspecialized primary template and neither member exists, assumes `random_access_iterator_tag` and lets the syntactic checks decide. Pointers are handled by the specialization `iterator_traits<T*>`, which reports `random_access_iterator_tag` as the category and `contiguous_iterator_tag` as the concept.

> **Standardese.** [iterator.concept.forward] lists the multi-pass guarantee as a semantic requirement of `std::forward_iterator`, and its only requirement on dereference is the `indirectly_readable` one inherited from input. The `T&` rule lives solely in [forward.iterators], the Cpp17ForwardIterator requirements.

## Why proxy iterators are two categories at once

`std::vector<bool>::iterator` dereferences to a proxy object, not a `bool&`. Under the C++98 rules it therefore fails the forward requirements and is, strictly, only an input iterator. Implementations nevertheless tag it `random_access_iterator_tag`, a long-standing white lie that legacy algorithms happen to tolerate. Under C++20 rules there is no lie: the iterator genuinely models `std::random_access_iterator`.

Range adaptors face the same issue honestly. A `views::transform` whose function returns by value produces elements as prvalues. Its iterator sets `iterator_concept` from the underlying range, so it can be random-access, but it sets `iterator_category` to `input_iterator_tag`, because claiming forward under C++98 rules would be false.

```cpp
#include <iterator>
#include <ranges>
#include <type_traits>
#include <vector>

std::vector<int> v{1, 2, 3};
auto t = v | std::views::transform([](int x) { return x * 2; });
using TI = std::ranges::iterator_t<decltype(t)>;

static_assert(std::random_access_iterator<TI>);    // C++20 report card
static_assert(std::is_same_v<std::iterator_traits<TI>::iterator_category,
                             std::input_iterator_tag>);  // C++98 report card
```

If the function returns a reference instead, the category is copied from the underlying iterator, except that contiguous is downgraded to random access. The same logic explains why `std::ranges::iota_view` iterators report an input category: `*it` returns an integer by value.

> **Pitfall.** Pass a transform iterator to a pre-ranges algorithm and the algorithm may treat it as single-pass. In C++20 it does not even meet the forward requirements that `std::max_element` or `std::search` state. C++23 adopted P2408, which lets algorithms that do not write through an iterator accept one that models the C++20 concept, but an implementation that dispatches on `iterator_category` may still choose the slow, step-by-step path.

## Associated types and `iterator_traits`

`std::iterator_traits<I>` exposes five legacy members: `difference_type`, `value_type`, `reference`, `pointer`, and `iterator_category`. Since C++20, if the iterator does not define them all, the primary template tries to compute them from the iterator's operations, and leaves the traits empty if it cannot recognise even an output iterator.

C++20 also added standalone aliases that are what generic code should use now:

| Alias | Meaning |
| --- | --- |
| `std::iter_value_t<I>` | the value type, with cv-qualifiers removed |
| `std::iter_reference_t<I>` | `decltype(*it)` |
| `std::iter_difference_t<I>` | the signed distance type |
| `std::iter_rvalue_reference_t<I>` | the type of `std::ranges::iter_move(it)` |
| `std::iter_common_reference_t<I>` | common reference of reference and `value_type&` |

The value type of `const int*` is `int`, not `const int`, while its reference type is `const int&`. For `std::vector<bool>::iterator`, the value type is `bool` and the reference type is the proxy class, which is exactly the split that the common reference machinery exists to bridge.

```cpp
#include <iterator>
#include <type_traits>

static_assert(std::is_same_v<std::iter_value_t<const int*>, int>);
static_assert(std::is_same_v<std::iter_reference_t<const int*>, const int&>);
static_assert(std::is_same_v<std::iter_rvalue_reference_t<int*>, int&&>);
```

These aliases read `std::indirectly_readable_traits` and `std::incrementable_traits` unless you have specialized `iterator_traits`, in which case your specialization wins.

## `advance`, `distance`, `next` and their costs

The generic iterator operations hide the category but not its cost. [iterator.operations] specifies `std::advance(it, n)` and `std::distance(first, last)` as constant time for random-access iterators and linear otherwise. `std::next` and `std::prev` are built on `advance`. Several preconditions are easy to forget:

- `std::advance` with a negative `n` requires a bidirectional iterator; for anything weaker it is undefined behavior.
- `std::distance(first, last)` requires `last` to be reachable from `first`, or, for random-access iterators, `first` reachable from `last`.
- `std::list::size()` is constant time, but `std::distance` over a list still walks every node, because a list iterator is bidirectional.

The `std::ranges` versions are concept-driven and know about sentinels. `std::ranges::distance(it, s)` is constant time whenever `s` models `std::sized_sentinel_for` its iterator, and `std::ranges::advance(it, n, bound)` stops at a bound instead of running off the end.

The legacy versions are where the two taxonomies collide in practice. With a C++20 iterator that reports a random-access concept but an input category, libc++ 21's `std::distance` increments one step at a time, while libstdc++ in GCC 16 recognises the concept and subtracts. Both are conforming. Calling `std::ranges::distance` makes the constant-time result portable.

## Output iterators

An output iterator is the write-only twin of an input iterator. `std::back_insert_iterator`, `std::ostream_iterator`, and `std::insert_iterator` are typical: `*it` returns the iterator itself, assignment through it calls `push_back` or writes to a stream, and `++it` does nothing. Their `value_type` and `reference` are `void`, so `std::iter_value_t` is not usable on them, though since C++20 `difference_type` is `std::ptrdiff_t`, so they satisfy `std::weakly_incrementable`.

The C++20 concept is `std::output_iterator<I, T>`. It takes the written type as a second parameter, because an iterator may accept some types and not others. Every mutable forward iterator is also an output iterator for its value type, but output iterators themselves guarantee only a single pass.

## What to remember

- Two taxonomies: legacy named requirements graded by `iterator_category`, and C++20 concepts graded by `iterator_concept` through `ITER_CONCEPT`.
- Multi-pass, the guarantee that copies advance independently, is what forward adds to input.
- Legacy forward requires `*it` to yield `T&` or `const T&`; `std::forward_iterator` does not, so proxy iterators can model C++20 random access.
- `views::transform` returning by value reports an input category but a random-access concept; `vector<bool>` iterators are tagged random access by convention.
- C++20 input iterators may be move-only and need not support `==`.
- `int*` reports `contiguous_iterator_tag` through `iterator_concept`, not `iterator_category`.
- Prefer `std::iter_value_t` and friends to `iterator_traits`; the value type has cv-qualifiers removed.
- `std::distance` is linear below random access, even for `std::list`; `std::ranges::distance` uses sized sentinels.

## Concept Map Outline

- **Iterator categories and concepts:** Two taxonomies: legacy named requirements tagged by iterator_category, C++20 concepts tagged by iterator_concept.
  - **Legacy ladder:** Input, forward, bidirectional, random access, contiguous; output on the side.
    - **Multi-pass:** Forward adds it: copies advance independently and a == b implies ++a == ++b.
    - **True reference rule:** Cpp17ForwardIterator requires *it to be T& or const T&, which proxies cannot meet.
    - **Tag is trusted:** Nothing checks iterator_category; vector<bool> iterators claim random access anyway.
  - **C++20 concepts:** Checked by the compiler and built from indirectly_readable, incrementable and sentinel_for.
    - **Weaker input:** input_iterator may be move-only, lack ==, and have a void postfix ++.
    - **Forward without T&:** forward_iterator needs regular and multi-pass, but any reference type.
    - **Contiguous needs lvalue:** contiguous_iterator requires an lvalue reference and working std::to_address.
    - **ITER_CONCEPT:** Reads iterator_concept, then iterator_category, else random access for primary traits.
  - **Proxy iterators:** An iterator can be random access by concept and input by category.
    - **views::transform:** By-value result: concept follows the base range, category is input_iterator_tag.
    - **vector<bool>:** Models random_access_iterator but never contiguous_iterator; reference is a proxy.
    - **Pointers:** iterator_traits<T*> reports random access category and contiguous concept.
  - **Associated types:** Prefer the C++20 aliases over iterator_traits members.
    - **iter_value_t:** cv-qualifiers removed: iter_value_t<const int*> is int.
    - **iter_reference_t:** Exactly decltype(*it), such as const int& for const int*.
    - **iter_rvalue_reference_t:** Type of ranges::iter_move(it); int&& for int*.
    - **Traits specialization wins:** A user specialization of iterator_traits overrides the computed traits.
  - **Operations and cost:** advance, distance, next and prev hide the category but not the cost.
    - **Linear below random:** std::distance on a list walks every node, even though size() is O(1).
    - **Negative advance:** Undefined behavior unless the iterator is at least bidirectional.
    - **ranges::distance:** Constant time whenever the sentinel models sized_sentinel_for.
  - **Output iterators:** Write-only and single pass, such as back_insert_iterator and ostream_iterator.
    - **void value_type:** iter_value_t is unusable, but difference_type is ptrdiff_t since C++20.
    - **output_iterator<I, T>:** Takes the written type as a parameter because acceptance depends on it.

## Standardese Quiz Questions

### Question 1 [warmup] ([iterator.concept.contiguous], [deque.overview], [vector.overview])

In C++23, which of these `static_assert`s fails?

```cpp
#include <deque>
#include <forward_list>
#include <iterator>
#include <list>
#include <vector>

static_assert(std::contiguous_iterator<std::vector<int>::iterator>);   // A
static_assert(std::contiguous_iterator<std::deque<int>::iterator>);    // B
static_assert(std::bidirectional_iterator<std::list<int>::iterator>);  // C
static_assert(std::forward_iterator<std::forward_list<int>::iterator>); // D
```

A. A: `vector` iterators are only random-access
B. B
C. C: `list` iterators are only forward
D. None of them fails

**Answer (B):** B

**Why:** A false `static_assert` makes the program ill-formed, so line B fails to compile. A `deque` supports constant-time indexing, so its iterators are random-access, but its elements live in separately allocated blocks and are not adjacent in memory, so it is not contiguous. `vector` iterators model `std::contiguous_iterator`, the C++20 concept for elements adjacent in memory. `list` is doubly linked and bidirectional, and `forward_list` is forward.

### Question 2 [warmup] ([readable.traits], [iterator.assoc.types])

What is `std::iter_value_t<const int*>`?

A. `const int`
B. `const int&`
C. `int`
D. `int&`

**Answer (C):** `int`

**Why:** The value type is the type of an object you could copy the element into, so cv-qualification is removed: `std::indirectly_readable_traits<const int*>` gives `int`. The reference type, `std::iter_reference_t<const int*>`, is `const int&`, which is the type that keeps the constness. Confusing the two is the usual mistake.

### Question 3 [warmup] ([iterator.operations], [list.overview])

For a `std::list<int>` with *n* elements, what does the standard specify as the complexity of `std::distance(l.begin(), l.end())`?

A. Constant, because `std::list::size()` is constant since C++11
B. Linear in *n*
C. Logarithmic in *n*
D. Unspecified

**Answer (B):** Linear in *n*

**Why:** `std::distance` is constant time only for random-access iterators, and it is linear otherwise. A list iterator is bidirectional, so `distance` must increment from `begin` to `end`. `std::list` does store its size, which makes `l.size()` constant time, but `distance` only sees two iterators and cannot reach the container.

### Question 4 [tricky] ([range.transform.iterator], [iterator.concept.random.access], [forward.iterators])

In C++23, which pair of results is correct for `TI`?

```cpp
#include <iterator>
#include <ranges>
#include <vector>

std::vector<int> v{1, 2, 3};
auto t = v | std::views::transform([](int x) { return x * 2; });
using TI = std::ranges::iterator_t<decltype(t)>;

constexpr bool ra = std::random_access_iterator<TI>;
using Cat = std::iterator_traits<TI>::iterator_category;
```

A. `ra` is `true`; `Cat` is `std::random_access_iterator_tag`
B. `ra` is `false`; `Cat` is `std::input_iterator_tag`
C. `ra` is `true`; `Cat` is `std::input_iterator_tag`
D. `ra` is `false`; `Cat` is `std::random_access_iterator_tag`

**Answer (C):** `ra` is `true`; `Cat` is `std::input_iterator_tag`

**Why:** The transform iterator takes its `iterator_concept` from the underlying `vector` iterator, so it models `std::random_access_iterator`: the C++20 concepts do not require `*it` to return a reference. Its `iterator_category` is computed separately under the legacy rules, and because the lambda returns `int` by value, `*it` is a prvalue and cannot meet the Cpp17ForwardIterator reference requirement. The category is therefore `std::input_iterator_tag`. Assuming both reports agree is the trap.

### Question 5 [tricky] ([iterator.concept.input], [iterator.concept.winc], [iterator.concepts.general])

In C++23, does `Gen` model `std::input_iterator`?

```cpp
#include <cstddef>
#include <iterator>

struct Gen {
  using difference_type = std::ptrdiff_t;
  using value_type = int;
  int n = 0;
  Gen() = default;
  Gen(Gen&&) = default;
  Gen& operator=(Gen&&) = default;
  int operator*() const { return n; }
  Gen& operator++() { ++n; return *this; }
  void operator++(int) { ++n; }
};

constexpr bool b = std::input_iterator<Gen>;
```

A. No: an input iterator must be copyable
B. No: an input iterator must support `==`
C. No: postfix `++` must return the iterator
D. Yes

**Answer (D):** Yes

**Why:** C++20 deliberately weakened the input-iterator requirements. `std::input_iterator` needs `std::weakly_incrementable` (movable, a signed `difference_type`, pre- and postfix `++` with postfix allowed to return anything), `std::indirectly_readable`, and an iterator concept derived from `input_iterator_tag`, which here comes from the `random_access_iterator_tag` fallback for the primary `iterator_traits` template. Copyability and `==` belong to the legacy Cpp17InputIterator requirements, which is where all three tempting answers come from.

### Question 6 [tricky] ([vector.bool], [iterator.concept.random.access], [iterator.concept.contiguous])

In C++23, which statement about `std::vector<bool>::iterator` is guaranteed?

A. It models `std::random_access_iterator` but not `std::contiguous_iterator`
B. It models `std::contiguous_iterator`, because `vector` storage is contiguous
C. It models only `std::input_iterator`, because `*it` is a proxy
D. It does not model `std::input_iterator`, because the proxy is not `bool&`

**Answer (A):** It models `std::random_access_iterator` but not `std::contiguous_iterator`

**Why:** The C++20 concepts accept proxy references: `std::indirectly_readable` only needs a common reference between the proxy and `bool&`, which exists, and nothing above it demands a language reference. So the iterator is random-access. It cannot be contiguous, because `std::contiguous_iterator` requires `iter_reference_t` to be an lvalue reference and the elements are bits, not addressable `bool` objects. The input-only answer is the verdict of the legacy Cpp17ForwardIterator rules, not the concepts.

### Question 7 [standardese] ([forward.iterators], [iterator.concept.forward])

Which of these is required by the Cpp17ForwardIterator requirements but **not** by the `std::forward_iterator` concept?

A. The multi-pass guarantee
B. Default construction
C. That `reference` is `T&` or `const T&`, where `T` is the value type
D. Equality comparison between two iterators of the same type

**Answer (C):** That `reference` is `T&` or `const T&`, where `T` is the value type

**Why:** [forward.iterators] requires the legacy `reference` type to be a language reference to the value type, which is what proxy iterators cannot satisfy. `std::forward_iterator` refines `std::input_iterator` with `std::incrementable` and `std::sentinel_for<I, I>`, which bring in default construction, equality comparison and copyability, and [iterator.concept.forward] states the multi-pass guarantee as a semantic requirement. So the other three are required by both.

### Question 8 [standardese] ([iterator.traits], [iterator.concepts.general], [iterator.concept.contiguous])

How does `std::contiguous_iterator<int*>` learn that a pointer is contiguous?

A. `std::iterator_traits<int*>::iterator_category` is `std::contiguous_iterator_tag`
B. `std::iterator_traits<int*>::iterator_concept` is `std::contiguous_iterator_tag`
C. The `ITER_CONCEPT` fallback assumes `std::contiguous_iterator_tag` for pointers
D. The concept special-cases pointer types with `std::is_pointer_v`

**Answer (B):** `std::iterator_traits<int*>::iterator_concept` is `std::contiguous_iterator_tag`

**Why:** The specialization `iterator_traits<T*>` defines `iterator_concept` as `contiguous_iterator_tag` while keeping `iterator_category` as `random_access_iterator_tag`, so old code that switches on the category is unaffected. `ITER_CONCEPT` reads `iterator_concept` first. The fallback for a missing tag is `random_access_iterator_tag`, and it applies only when `iterator_traits` is the primary template, which is not the case for pointers.
