Difference between revisions of "cpp/iterator/random access iterator"
m (fmt) |
Andreas Krug (Talk | contribs) m (fmt, {{c}}, and -> &&) |
||
| (7 intermediate revisions by 3 users not shown) | |||
| Line 3: | Line 3: | ||
{{ddcl|header=iterator|since=c++20|1= | {{ddcl|header=iterator|since=c++20|1= | ||
template< class I > | 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 {{ | + | 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}} | {{cpp/iterator/iter concept}} | ||
===Semantic requirements=== | ===Semantic requirements=== | ||
| − | Let {{ | + | 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=(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)}}. [[#addressof note|{{sup|[1]}}]] |
* {{c|(a + n)}} is equal to {{c|1=(a += n)}}. | * {{c|(a + n)}} is equal to {{c|1=(a += n)}}. | ||
* {{c|(a + n)}} is equal to {{c|(n + a)}}. | * {{c|(a + n)}} is equal to {{c|(n + a)}}. | ||
| Line 32: | Line 32: | ||
* If {{c|(a + (n - 1))}} is valid, then {{c|--b}} is equal to {{c|(a + (n - 1))}}. | * 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=(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)}}. | + | * {{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)}}. | * {{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}}. | * 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}}. | * {{c|1=bool(a <= b)}} is {{c|true}}. | ||
* Every required operation has constant time complexity. | * 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/equality preservation}} | ||
| Line 50: | Line 52: | ||
#include <iterator> | #include <iterator> | ||
| − | namespace cxx20 { | + | 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() | int main() | ||
{ | { | ||
| − | static constexpr auto il = { 3, 1, 4 }; | + | static constexpr auto il = {3, 1, 4}; |
| − | static_assert | + | static_assert(std::random_access_iterator<decltype(il.begin())> && |
| − | + | cxx20::distance(il.begin(), il.end()) == 3 && | |
| − | + | cxx20::distance(il.end(), il.begin()) == -3); | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
} | } | ||
}} | }} | ||
Latest revision as of 11:04, 1 October 2023
| Defined in header <iterator>
|
||
| template< class I > concept random_access_iterator = |
(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 |
[edit] 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.
[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<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
xandy, 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 <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); }
[edit] See also
| (C++20) |
specifies that a forward_iterator is a bidirectional iterator, supporting movement backwards (concept) |
| (C++20) |
specifies that a random_access_iterator is a contiguous iterator, referring to elements that are contiguous in memory (concept) |
