[iterator.primitives] - C++17 → C++20

Files changed (1) hide show

tmp/tmp56etsb1v/{from.md → to.md} +204 -121

tmp/tmp56etsb1v/{from.md → to.md} RENAMED Viewed

@@ -1,131 +1,33 @@
 ## Iterator primitives <a id="iterator.primitives">[[iterator.primitives]]</a>
-To simplify the task of defining iterators, the library provides several
-classes and functions:
-### Iterator traits <a id="iterator.traits">[[iterator.traits]]</a>
-To implement algorithms only in terms of iterators, it is often
-necessary to determine the value and difference types that correspond to
-a particular iterator type. Accordingly, it is required that if
-`Iterator` is the type of an iterator, the types
-``` cpp
-iterator_traits<Iterator>::difference_type
-iterator_traits<Iterator>::value_type
-iterator_traits<Iterator>::iterator_category
-```
-be defined as the iterator’s difference type, value type and iterator
-category, respectively. In addition, the types
-``` cpp
-iterator_traits<Iterator>::reference
-iterator_traits<Iterator>::pointer
-```
-shall be defined as the iterator’s reference and pointer types, that is,
-for an iterator object `a`, the same type as the type of `*a` and `a->`,
-respectively. In the case of an output iterator, the types
-``` cpp
-iterator_traits<Iterator>::difference_type
-iterator_traits<Iterator>::value_type
-iterator_traits<Iterator>::reference
-iterator_traits<Iterator>::pointer
-```
-may be defined as `void`.
-If `Iterator` has valid ([[temp.deduct]]) member types
-`difference_type`, `value_type`, `pointer`, `reference`, and
-`iterator_category`, `iterator_traits<Iterator>` shall have the
-following as publicly accessible members:
-``` cpp
-using difference_type   = typename Iterator::difference_type;
-  using value_type        = typename Iterator::value_type;
-  using pointer           = typename Iterator::pointer;
-  using reference         = typename Iterator::reference;
-  using iterator_category = typename Iterator::iterator_category;
-```
-Otherwise, `iterator_traits<Iterator>` shall have no members by any of
-the above names.
-It is specialized for pointers as
-``` cpp
-namespace std {
-  template<class T> struct iterator_traits<T*> {
-    using difference_type   = ptrdiff_t;
-    using value_type        = T;
-    using pointer           = T*;
-    using reference         = T&;
-    using iterator_category = random_access_iterator_tag;
-  };
-}
-```
-and for pointers to const as
-``` cpp
-namespace std {
-  template<class T> struct iterator_traits<const T*> {
-    using difference_type   = ptrdiff_t;
-    using value_type        = T;
-    using pointer           = const T*;
-    using reference         = const T&;
-    using iterator_category = random_access_iterator_tag;
-  };
-}
-```
-[*Example 1*:
-To implement a generic `reverse` function, a C++program can do the
-following:
-``` cpp
-template <class BidirectionalIterator>
-void reverse(BidirectionalIterator first, BidirectionalIterator last) {
-  typename iterator_traits<BidirectionalIterator>::difference_type n =
-    distance(first, last);
-  --n;
-  while(n > 0) {
-    typename iterator_traits<BidirectionalIterator>::value_type
-     tmp = *first;
-    *first++ = *--last;
-    *last = tmp;
-    n -= 2;
-  }
-}
-```
-— *end example*]
 ### Standard iterator tags <a id="std.iterator.tags">[[std.iterator.tags]]</a>
 It is often desirable for a function template specialization to find out
 what is the most specific category of its iterator argument, so that the
 function can select the most efficient algorithm at compile time. To
 facilitate this, the library introduces *category tag* classes which are
 used as compile time tags for algorithm selection. They are:
-`input_iterator_tag`, `output_iterator_tag`, `forward_iterator_tag`,
-`bidirectional_iterator_tag` and `random_access_iterator_tag`. For every
-iterator of type `Iterator`,
-`iterator_traits<Iterator>::iterator_category` shall be defined to be
-the most specific category tag that describes the iterator’s behavior.
 ``` cpp
 namespace std {
-  struct input_iterator_tag { };
   struct output_iterator_tag { };
   struct forward_iterator_tag: public input_iterator_tag { };
   struct bidirectional_iterator_tag: public forward_iterator_tag { };
   struct random_access_iterator_tag: public bidirectional_iterator_tag { };
 }
 ```
 [*Example 1*:
@@ -145,11 +47,11 @@ template<class T> struct iterator_traits<BinaryTreeIterator<T>> {
 — *end example*]
 [*Example 2*:
-If `evolve()` is well defined for bidirectional iterators, but can be
 implemented more efficiently for random access iterators, then the
 implementation is as follows:
 ``` cpp
 template<class BidirectionalIterator>
@@ -185,31 +87,29 @@ iterators they use `++` to provide linear time implementations.
 ``` cpp
 template<class InputIterator, class Distance>
   constexpr void advance(InputIterator& i, Distance n);
 ```
-*Requires:* `n` shall be negative only for bidirectional and random
-access iterators.
-*Effects:* Increments (or decrements for negative `n`) iterator
-reference `i` by `n`.
 ``` cpp
 template<class InputIterator>
   constexpr typename iterator_traits<InputIterator>::difference_type
     distance(InputIterator first, InputIterator last);
 ```
-*Effects:* If `InputIterator` meets the requirements of random access
-iterator, returns `(last - first)`; otherwise, returns the number of
 increments needed to get from `first` to `last`.
-*Requires:* If `InputIterator` meets the requirements of random access
-iterator, `last` shall be reachable from `first` or `first` shall be
-reachable from `last`; otherwise, `last` shall be reachable from
-`first`.
 ``` cpp
 template<class InputIterator>
   constexpr InputIterator next(InputIterator x,
     typename iterator_traits<InputIterator>::difference_type n = 1);
 ```
@@ -222,5 +122,188 @@ template <class BidirectionalIterator>
     typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
 ```
 *Effects:* Equivalent to: `advance(x, -n); return x;`

 ## Iterator primitives <a id="iterator.primitives">[[iterator.primitives]]</a>
+To simplify the use of iterators, the library provides several classes
+and functions.
 ### Standard iterator tags <a id="std.iterator.tags">[[std.iterator.tags]]</a>
 It is often desirable for a function template specialization to find out
 what is the most specific category of its iterator argument, so that the
 function can select the most efficient algorithm at compile time. To
 facilitate this, the library introduces *category tag* classes which are
 used as compile time tags for algorithm selection. They are:
+`output_iterator_tag`, `input_iterator_tag`, `forward_iterator_tag`,
+`bidirectional_iterator_tag`, `random_access_iterator_tag`, and
+`contiguous_iterator_tag`. For every iterator of type `I`,
+`iterator_traits<I>::iterator_category` shall be defined to be a
+category tag that describes the iterator’s behavior. Additionally,
+`iterator_traits<I>::iterator_concept` may be used to indicate
+conformance to the iterator concepts [[iterator.concepts]].
 ``` cpp
 namespace std {
   struct output_iterator_tag { };
+  struct input_iterator_tag { };
   struct forward_iterator_tag: public input_iterator_tag { };
   struct bidirectional_iterator_tag: public forward_iterator_tag { };
   struct random_access_iterator_tag: public bidirectional_iterator_tag { };
+  struct contiguous_iterator_tag: public random_access_iterator_tag { };
 }
 ```
 [*Example 1*:
 — *end example*]
 [*Example 2*:
+If `evolve()` is well-defined for bidirectional iterators, but can be
 implemented more efficiently for random access iterators, then the
 implementation is as follows:
 ``` cpp
 template<class BidirectionalIterator>
 ``` cpp
 template<class InputIterator, class Distance>
   constexpr void advance(InputIterator& i, Distance n);
 ```
+*Preconditions:* `n` is negative only for bidirectional iterators.
+*Effects:* Increments `i` by `n` if `n` is non-negative, and decrements
+`i` by `-n` otherwise.
 ``` cpp
 template<class InputIterator>
   constexpr typename iterator_traits<InputIterator>::difference_type
     distance(InputIterator first, InputIterator last);
 ```
+*Preconditions:* `last` is reachable from `first`, or `InputIterator`
+meets the *Cpp17RandomAccessIterator* requirements and `first` is
+reachable from `last`.
+*Effects:* If `InputIterator` meets the *Cpp17RandomAccessIterator*
+requirements, returns `(last - first)`; otherwise, returns the number of
 increments needed to get from `first` to `last`.
 ``` cpp
 template<class InputIterator>
   constexpr InputIterator next(InputIterator x,
     typename iterator_traits<InputIterator>::difference_type n = 1);
 ```
     typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
 ```
 *Effects:* Equivalent to: `advance(x, -n); return x;`
+### Range iterator operations <a id="range.iter.ops">[[range.iter.ops]]</a>
+The library includes the function templates `ranges::advance`,
+`ranges::distance`, `ranges::next`, and `ranges::prev` to manipulate
+iterators. These operations adapt to the set of operators provided by
+each iterator category to provide the most efficient implementation
+possible for a concrete iterator type.
+[*Example 1*: `ranges::advance` uses the `+` operator to move a
+`random_access_iterator` forward `n` steps in constant time. For an
+iterator type that does not model `random_access_iterator`,
+`ranges::advance` instead performs `n` individual increments with the
+`++` operator. — *end example*]
+The function templates defined in this subclause are not found by
+argument-dependent name lookup [[basic.lookup.argdep]]. When found by
+unqualified [[basic.lookup.unqual]] name lookup for the
+*postfix-expression* in a function call [[expr.call]], they inhibit
+argument-dependent name lookup.
+[*Example 2*:
+``` cpp
+void foo() {
+    using namespace std::ranges;
+    std::vector<int> vec{1,2,3};
+    distance(begin(vec), end(vec));     // #1
+}
+```
+The function call expression at `#1` invokes `std::ranges::distance`,
+not `std::distance`, despite that (a) the iterator type returned from
+`begin(vec)` and `end(vec)` may be associated with namespace `std` and
+(b) `std::distance` is more specialized ([[temp.func.order]]) than
+`std::ranges::distance` since the former requires its first two
+parameters to have the same type.
+— *end example*]
+The number and order of deducible template parameters for the function
+templates defined in this subclause is unspecified, except where
+explicitly stated otherwise.
+#### `ranges::advance` <a id="range.iter.op.advance">[[range.iter.op.advance]]</a>
+``` cpp
+template<input_or_output_iterator I>
+  constexpr void ranges::advance(I& i, iter_difference_t<I> n);
+```
+*Preconditions:* If `I` does not model `bidirectional_iterator`, `n` is
+not negative.
+*Effects:*
+- If `I` models `random_access_iterator`, equivalent to `i += n`.
+- Otherwise, if `n` is non-negative, increments `i` by `n`.
+- Otherwise, decrements `i` by `-n`.
+``` cpp
+template<input_or_output_iterator I, sentinel_for<I> S>
+  constexpr void ranges::advance(I& i, S bound);
+```
+*Preconditions:* \[`i`, `bound`) denotes a range.
+*Effects:*
+- If `I` and `S` model `assignable_from<I&, S>`, equivalent to
+  `i = std::move(bound)`.
+- Otherwise, if `S` and `I` model `sized_sentinel_for<S, I>`, equivalent
+  to `ranges::advance(i, bound - i)`.
+- Otherwise, while `bool(i != bound)` is `true`, increments `i`.
+``` cpp
+template<input_or_output_iterator I, sentinel_for<I> S>
+  constexpr iter_difference_t<I> ranges::advance(I& i, iter_difference_t<I> n, S bound);
+```
+*Preconditions:* If `n > 0`, \[`i`, `bound`) denotes a range. If
+`n == 0`, \[`i`, `bound`) or \[`bound`, `i`) denotes a range. If
+`n < 0`, \[`bound`, `i`) denotes a range, `I` models
+`bidirectional_iterator`, and `I` and `S` model `same_as<I, S>`.
+*Effects:*
+- If `S` and `I` model `sized_sentinel_for<S, I>`:
+  - If |`n`| ≥ |`bound - i`|, equivalent to `ranges::advance(i, bound)`.
+  - Otherwise, equivalent to `ranges::advance(i, n)`.
+- Otherwise,
+  - if `n` is non-negative, while `bool(i != bound)` is `true`,
+    increments `i` but at most `n` times.
+  - Otherwise, while `bool(i != bound)` is `true`, decrements `i` but at
+    most `-n` times.
+*Returns:* `n - `M, where M is the difference between the ending and
+starting positions of `i`.
+#### `ranges::distance` <a id="range.iter.op.distance">[[range.iter.op.distance]]</a>
+``` cpp
+template<input_or_output_iterator I, sentinel_for<I> S>
+  constexpr iter_difference_t<I> ranges::distance(I first, S last);
+```
+*Preconditions:* \[`first`, `last`) denotes a range, or \[`last`,
+`first`) denotes a range and `S` and `I` model
+`same_as<S, I> && sized_sentinel_for<S, I>`.
+*Effects:* If `S` and `I` model `sized_sentinel_for<S, I>`, returns
+`(last - first)`; otherwise, returns the number of increments needed to
+get from `first` to `last`.
+``` cpp
+template<range R>
+  constexpr range_difference_t<R> ranges::distance(R&& r);
+```
+*Effects:* If `R` models `sized_range`, equivalent to:
+``` cpp
+return static_cast<range_difference_t<R>>(ranges::size(r));     // [range.prim.size]
+```
+Otherwise, equivalent to:
+``` cpp
+return ranges::distance(ranges::begin(r), ranges::end(r));      // [range.access]
+```
+#### `ranges::next` <a id="range.iter.op.next">[[range.iter.op.next]]</a>
+``` cpp
+template<input_or_output_iterator I>
+  constexpr I ranges::next(I x);
+```
+*Effects:* Equivalent to: `++x; return x;`
+``` cpp
+template<input_or_output_iterator I>
+  constexpr I ranges::next(I x, iter_difference_t<I> n);
+```
+*Effects:* Equivalent to: `ranges::advance(x, n); return x;`
+``` cpp
+template<input_or_output_iterator I, sentinel_for<I> S>
+  constexpr I ranges::next(I x, S bound);
+```
+*Effects:* Equivalent to: `ranges::advance(x, bound); return x;`
+``` cpp
+template<input_or_output_iterator I, sentinel_for<I> S>
+  constexpr I ranges::next(I x, iter_difference_t<I> n, S bound);
+```
+*Effects:* Equivalent to: `ranges::advance(x, n, bound); return x;`
+#### `ranges::prev` <a id="range.iter.op.prev">[[range.iter.op.prev]]</a>
+``` cpp
+template<bidirectional_iterator I>
+  constexpr I ranges::prev(I x);
+```
+*Effects:* Equivalent to: `-``-``x; return x;`
+``` cpp
+template<bidirectional_iterator I>
+  constexpr I ranges::prev(I x, iter_difference_t<I> n);
+```
+*Effects:* Equivalent to: `ranges::advance(x, -n); return x;`
+``` cpp
+template<bidirectional_iterator I>
+  constexpr I ranges::prev(I x, iter_difference_t<I> n, I bound);
+```
+*Effects:* Equivalent to: `ranges::advance(x, -n, bound); return x;`

Diff to HTML by rtfpessoa