Namespaces
Variants
Views
Actions

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

From cppreference.com
< cpp‎ | iterator
m (→‎Semantic requirements)
(Type mistake)
Line 23: Line 23:
  
 
===Semantic requirements===
 
===Semantic requirements===
−
Let {{tt|a}} and {{tt|b}} be valid iterators of type {{tt|I}} such that {{tt|b}} is reachable from {{tt|a}}, and let {{tt|n}} be a value of type {{c|std::iter_reference_t<I>}} equal to {{c|b - a}}. {{tt|random_access_iterator&lt;I>}} is modeled only if all the concepts it subsumes are modeled and:
+
Let {{tt|a}} and {{tt|b}} be valid iterators of type {{tt|I}} such that {{tt|b}} is reachable from {{tt|a}}, and let {{tt|n}} be a value of type {{c|std::iter_difference_t<I>}} equal to {{c|b - a}}. {{tt|random_access_iterator&lt;I>}} is modeled only if all the concepts it subsumes are modeled and:
 
* {{c|1=(a += n)}} is equal to {{c|b}}.
 
* {{c|1=(a += n)}} is equal to {{c|b}}.
 
* {{c|1=std::addressof(a += n)}} is equal to {{c|std::addressof(a)}}.
 
* {{c|1=std::addressof(a += n)}} is equal to {{c|std::addressof(a)}}.

Revision as of 01:24, 31 July 2020

 
C++
 
Iterator library
Iterator concepts
(C++20)
(C++20)
random_access_iterator
(C++20)
(C++20)


Iterator primitives
Algorithm concepts and utilities
Indirect callable concepts
Common algorithm requirements
(C++20)
(C++20)
(C++20)
Utilities
(C++20)
Iterator adaptors
Range access
(C++11)(C++14)
(C++14)(C++14)  
(C++11)(C++14)
(C++14)(C++14)  
(C++17)(C++20)
(C++17)
(C++17)
 
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.

Contents

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

See also

(C++20)
 specifies that a forward_iterator is a bidirectional iterator, supporting movement backwards
(concept) [edit]
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/iterator/random_access_iterator&oldid=121446"