# std::random_access_iterator

> C++ Atlas: `cppatlas.com/w/cpp/iterator/random_access_iterator` | Source: https://en.cppreference.com/w/cpp/iterator/random_access_iterator | Domain: Iterator | Standards: C++20

The concept random_access_iterator refines bidirectional_iterator by adding support for constant time advancement with the +=, +, -=, and - operators, constant time computation of distance with -, and array notation with subscripting [].

## Official Specification Summary (cppreference)

```cpp
// Defined in header <iterator>

template< class I >
    concept random_access_iterator =
        std::bidirectional_iterator<I> &&
        std::derived_from</*ITER_CONCEPT*/<I>, std::random_access_iterator_tag> &&
        std::totally_ordered<I> &&
        std::sized_sentinel_for<I, I> &&
        requires(I i, const I j, const std::iter_difference_t<I> n) {
            { i += n } -> std::same_as<I&>;
            { j +  n } -> std::same_as<I>;
            { n +  j } -> std::same_as<I>;
            { i -= n } -> std::same_as<I&>;
            { j -  n } -> std::same_as<I>;
            {  j[n]  } -> std::same_as<std::iter_reference_t<I>>;
        }; // (since C++20)
```

The concept `random_access_iterator` refines `bidirectional_iterator` by adding support for constant time advancement with the `+=`, `+`, `-=`, and `-` operators, constant time computation of distance with `-`, and array notation with subscripting `[]`.

### Iterator concept determination

Definition of this concept is specified via an exposition-only alias template `/*ITER_CONCEPT*/`.

In order to determine `/*ITER_CONCEPT*/<I>`, let `ITER_TRAITS<I>` denote `I` if the specialization `std::iterator_traits<I>` is generated from the primary template, or `std::iterator_traits<I>` otherwise:

- If `ITER_TRAITS<I>::iterator_concept` is valid and names a type, `/*ITER_CONCEPT*/<I>` denotes the type.
- Otherwise, if `ITER_TRAITS<I>::iterator_category` is valid and names a type, `/*ITER_CONCEPT*/<I>` denotes the type.
- Otherwise, if `std::iterator_traits<I>` is generated from the primary template, `/*ITER_CONCEPT*/<I>` denotes `std::random_access_iterator_tag`.
- Otherwise, `/*ITER_CONCEPT*/<I>` does not denote a type and results in a substitution failure.

### Semantic requirements

Let `a` and `b` be valid iterators of type `I` such that `b` is reachable from `a`, and let `n` be a value of type `std::iter_difference_t<I>` equal to `b - a`. `std::random_access_iterator<I>` is modeled only if all the concepts it subsumes are modeled and:

- `(a += n)` is equal to `b`.
- `std::addressof(a += n)` is equal to `std::addressof(a)`. [1]
- `(a + n)` is equal to `(a += n)`.
- `(a + n)` is equal to `(n + a)`.
- For any two positive integers `x` and `y`, if `a + (x + y)` is valid, then `a + (x + y)` is equal to `(a + x) + y`.
- `a + 0` is equal to `a`.
- If `(a + (n - 1))` is valid, then `--b` is equal to `(a + (n - 1))`.
- `(b += -n)` and `(b -= n)` are both equal to `a`.
- `std::addressof(b -= n)` is equal to `std::addressof(b)`. [1]
- `(b - n)` is equal to `(b -= n)`.
- If `b` is dereferenceable, then `a[n]` is valid and is equal to `*b`.
- `bool(a <= b)` is `true`.
- Every required operation has constant time complexity.

Note that `std::addressof` returns the address of the iterator object, not the address of the object the iterator points to. I.e. `operator+=` and `operator-=` must return a reference to `*this`.

### Equality preservation

Expressions declared in `requires` expressions of the standard library concepts are required to be equality-preserving (except where stated otherwise).

### Implicit expression variations

A `requires` expression that uses an expression that is non-modifying for some constant lvalue operand also requires implicit expression variations.

### Notes

Unlike the *LegacyRandomAccessIterator* requirements, the `random_access_iterator` concept does not require dereference to return an lvalue.

### Example

Demonstrates a possible implementation of `std::distance` via C++20 concepts.

```cpp
#include <iterator>

namespace cxx20
{
    template<std::input_or_output_iterator Iter>
    constexpr std::iter_difference_t<Iter> distance(Iter first, Iter last)
    {
        if constexpr(std::random_access_iterator<Iter>)
            return last - first;
        else
        {
            std::iter_difference_t<Iter> result{};
            for (; first != last; ++first)
                ++result;
            return result;
        }
    }
}

int main()
{
    static constexpr auto il = {3, 1, 4};

    static_assert(std::random_access_iterator<decltype(il.begin())> &&
                  cxx20::distance(il.begin(), il.end()) == 3 &&
                  cxx20::distance(il.end(), il.begin()) == -3);
}
```

### See also

- [`bidirectional_iterator`](https://en.cppreference.com/w/cpp/iterator/bidirectional_iterator) (C++20): specifies that a `forward_iterator` is a bidirectional iterator, supporting movement backwards (concept)
- [`contiguous_iterator`](https://en.cppreference.com/w/cpp/iterator/contiguous_iterator) (C++20): specifies that a `random_access_iterator` is a contiguous iterator, referring to elements that are contiguous in memory (concept)

---
Attribution: content from https://en.cppreference.com/w/cpp/iterator/random_access_iterator (cppreference.com), licensed under CC-BY-SA 3.0 and GFDL. Modified: converted to markdown, study notes added. Offline snapshot of 9 February 2025.