std::random_access_iterator - cppreference.com (original) (raw)

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 **[]**.

1 Iterator concept determination
2 Semantic requirements
3 Equality preservation
4 Implicit expression variations
5 Notes
6 Example
7 See also

[edit] Iterator concept determination

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

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

If ITER_TRAITS::iterator_concept is valid and names a type, /*ITER_CONCEPT*/ denotes the type.
Otherwise, if ITER_TRAITS::iterator_category is valid and names a type, /*ITER_CONCEPT*/ denotes the type.
Otherwise, if std::iterator_traits is generated from the primary template, /*ITER_CONCEPT*/ denotes std::random_access_iterator_tag.
(That is, std::derived_from</*ITER_CONCEPT*/, std::random_access_iterator_tag> is assumed to be true.)
Otherwise, /*ITER_CONCEPT*/ does not denote a type and results in a substitution failure.

[edit] 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 equal to b - a. std::random_access_iterator 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.

[edit] Equality preservation

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

[edit] Implicit expression variations

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

[edit] Notes

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

[edit] Example

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

#include namespace cxx20 { template<std::input_or_output_iterator Iter> constexpr std::iter_difference_t distance(Iter first, Iter last) { if constexpr(std::random_access_iterator) return last - first; else { std::iter_difference_t 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); }