Difference between revisions of "cpp/iterator/random access iterator"

Revision as of 18:45, 27 June 2023

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).
• (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(a).
• (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.

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

#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())>
        and
        cxx20::distance(il.begin(), il.end()) == 3
        and
        cxx20::distance(il.end(), il.begin()) == -3
    );
}

See also