View source for cpp/iterator/random access iterator

{{cpp/title|random_access_iterator}}
{{cpp/iterator/navbar}}
{{ddcl|header=iterator|since=c++20|1=
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>>;
        };
}}

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

{{cpp/iterator/iter concept}}

===Semantic requirements===
Let {{c|a}} and {{c|b}} be valid iterators of type {{tt|I}} such that {{c|b}} is reachable from {{c|a}}, and let {{c|n}} be a value of type {{c|std::iter_difference_t<I>}} equal to {{c|b - a}}. {{co|std::random_access_iterator<I>}} is modeled only if all the concepts it subsumes are modeled and:
* {{c|1=(a += n)}} is equal to {{c|b}}.
* {{c|1=std::addressof(a += n)}} is equal to {{c|std::addressof(a)}}. [[#addressof note|{{sup|[1]}}]]
* {{c|(a + n)}} is equal to {{c|1=(a += n)}}.
* {{c|(a + n)}} is equal to {{c|(n + a)}}.
* For any two positive integers {{tt|x}} and {{tt|y}}, if {{c|a + (x + y)}} is valid, then {{c|a + (x + y)}} is equal to {{c|(a + x) + y}}.
* {{c|a + 0}} is equal to {{c|a}}.
* If {{c|(a + (n - 1))}} is valid, then {{c|--b}} is equal to {{c|(a + (n - 1))}}.
* {{c|1=(b += -n)}} and {{c|1=(b -= n)}} are both equal to {{c|a}}.
* {{c|1=std::addressof(b -= n)}} is equal to {{c|std::addressof(b)}}. [[#addressof note|{{sup|[1]}}]]
* {{c|(b - n)}} is equal to {{c|1=(b -= n)}}.
* If {{c|b}} is dereferenceable, then {{c|a[n]}} is valid and is equal to {{c|*b}}.
* {{c|1=bool(a <= b)}} is {{c|true}}.
* Every required operation has constant time complexity.
{{anchor|addressof note}}
{{petty|Note that {{lc|std::addressof}} returns the address of the iterator object, not the address of the object the iterator points to. I.e. {{tt|1=operator+=}} and {{tt|1=operator-=}} must return a reference to {{c|*this}}.}}

{{cpp/concepts/equality preservation}}
{{cpp/concepts/implicit expression variations}}

===Notes===
Unlike the {{named req|RandomAccessIterator}} requirements, the {{tt|random_access_iterator}} concept does not require dereference to return an lvalue.

===Example===
{{example
|Demonstrates a possible implementation of {{lc|std::distance}} via C++20 concepts.
|code=
#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===
{{dsc begin}}
{{dsc inc|cpp/iterator/dsc bidirectional_iterator}}
{{dsc inc|cpp/iterator/dsc contiguous_iterator}}
{{dsc end}}

{{langlinks|de|es|ja|ru|zh}}