[alg.modifying.operations] - C++20 → C++23

Files changed (1) hide show

tmp/tmpq15mlcox/{from.md → to.md} +70 -41

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

@@ -65,14 +65,14 @@ template<input_iterator I, weakly_incrementable O>
 ```
 Let N be max(0, `n`).
 *Mandates:* The type `Size` is convertible to an integral
-type ([[conv.integral]], [[class.conv]]).
 *Effects:* For each non-negative integer i < N, performs
-`*(result + i) = *(first + i)`.
 *Returns:*
 - `result + `N for the overloads in namespace `std`.
 - `{first + `N`, result + `N`}` for the overload in namespace `ranges`.
@@ -111,11 +111,11 @@ and N be the number of iterators `i` in the range \[`first`, `last`) for
 which the condition E holds.
 *Preconditions:* The ranges \[`first`, `last`) and \[`result`,
 `result + (last - first)`) do not overlap.
-[*Note 1*: For the overload with an `ExecutionPolicy`, there may be a
 performance cost if `iterator_traits<ForwardIterator1>::value_type` is
 not *Cpp17MoveConstructible*
 ([[cpp17.moveconstructible]]). — *end note*]
 *Effects:* Copies all of the elements referred to by the iterator `i` in
@@ -152,11 +152,13 @@ Let N be `last - first`.
 *Preconditions:* `result` is not in the range (`first`, `last`).
 *Effects:* Copies elements in the range \[`first`, `last`) into the
 range \[`result - `N, `result`) starting from `last - 1` and proceeding
-to `first`. [^2] For each positive integer n ≤ N, performs
 `*(result - `n`) = *(last - `n`)`.
 *Returns:*
 - `result - `N for the overload in namespace `std`.
@@ -249,12 +251,13 @@ Let N be `last - first`.
 *Preconditions:* `result` is not in the range (`first`, `last`).
 *Effects:* Moves elements in the range \[`first`, `last`) into the range
 \[`result - `N, `result`) starting from `last - 1` and proceeding to
-`first`. [^3] For each positive integer n ≤ N, performs
-`*(result - `n`) = `E.
 *Returns:*
 - `result - `N for the overload in namespace `std`.
 - `{last, result - `N`}` for the overloads in namespace `ranges`.
@@ -572,11 +575,10 @@ template<class OutputIterator, class Size, class T>
   constexpr OutputIterator fill_n(OutputIterator first, Size n, const T& value);
 template<class ExecutionPolicy, class ForwardIterator, class Size, class T>
   ForwardIterator fill_n(ExecutionPolicy&& exec,
                          ForwardIterator first, Size n, const T& value);
 template<class T, output_iterator<const T&> O, sentinel_for<O> S>
   constexpr O ranges::fill(O first, S last, const T& value);
 template<class T, output_range<const T&> R>
   constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value);
 template<class T, output_iterator<const T&> O>
@@ -586,12 +588,12 @@ template<class T, output_iterator<const T&> O>
 Let N be max(0, `n`) for the `fill_n` algorithms, and `last - first` for
 the `fill` algorithms.
 *Mandates:* The expression `value` is
 writable [[iterator.requirements.general]] to the output iterator. The
-type `Size` is convertible to an integral type ([[conv.integral]],
-[[class.conv]]).
 *Effects:* Assigns `value` through all the iterators in the range
 \[`first`, `first + `N).
 *Returns:* `first + `N.
@@ -628,11 +630,11 @@ template<input_or_output_iterator O, copy_constructible F>
 Let N be max(0, `n`) for the `generate_n` algorithms, and `last - first`
 for the `generate` algorithms.
 *Mandates:* `Size` is convertible to an integral
-type ([[conv.integral]], [[class.conv]]).
 *Effects:* Assigns the result of successive evaluations of `gen()`
 through each iterator in the range \[`first`, `first + `N).
 *Returns:* `first + `N.
@@ -693,15 +695,15 @@ the range \[`first`, `last`) for which E holds.
 *Returns:* Let j be the end of the resulting range. Returns:
 - j for the overloads in namespace `std`.
 - `{`j`, last}` for the overloads in namespace `ranges`.
-*Remarks:* Stable [[algorithm.stable]].
 *Complexity:* Exactly `last - first` applications of the corresponding
 predicate and any projection.
 [*Note 1*: Each element in the range \[`ret`, `last`), where `ret` is
 the returned value, has a valid but unspecified state, because the
 algorithms can eliminate elements by moving from elements that were
 originally in that range. — *end note*]
@@ -765,14 +767,14 @@ Let N be the number of elements in \[`first`, `last`) for which E is
 `result`.
 *Preconditions:* The ranges \[`first`, `last`) and \[`result`,
 `result + (last - first)`) do not overlap.
-[*Note 2*: For the overloads with an `ExecutionPolicy`, there may be a
-performance cost if `iterator_traits<ForwardIterator1>::value_type` does
-not meet the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]])
-requirements. — *end note*]
 *Effects:* Copies all the elements referred to by the iterator `i` in
 the range \[`first`, `last`) for which E is `false`.
 *Returns:*
@@ -817,11 +819,11 @@ and let E be
 - `bool(pred(*(i - 1), *i))` for the overloads in namespace `std`;
 - `bool(invoke(comp, invoke(proj, *(i - 1)), invoke(proj, *i)))` for the
   overloads in namespace `ranges`.
-*Preconditions:* For the overloads in namepace `std`, `pred` is an
 equivalence relation and the type of `*first` meets the
 *Cpp17MoveAssignable* requirements ([[cpp17.moveassignable]]).
 *Effects:* For a nonempty range, eliminates all but the first element
 from every consecutive group of equivalent elements referred to by the
@@ -892,19 +894,19 @@ parameter `pred`, and let E be
 - The ranges \[`first`, `last`) and \[`result`, `result+(last-first)`)
   do not overlap.
 - For the overloads in namespace `std`:
   - The comparison function is an equivalence relation.
   - For the overloads with no `ExecutionPolicy`, let `T` be the value
-    type of `InputIterator`. If `InputIterator` meets the
- *Cpp17ForwardIterator* requirements, then there are no additional
-    requirements for `T`. Otherwise, if `OutputIterator` meets the
-    *Cpp17ForwardIterator* requirements and its value type is the same
-    as `T`, then `T` meets the *Cpp17CopyAssignable*
     ([[cpp17.copyassignable]]) requirements. Otherwise, `T` meets both
     the *Cpp17CopyConstructible* ([[cpp17.copyconstructible]]) and
     *Cpp17CopyAssignable* requirements. \[*Note 1*: For the overloads
-    with an `ExecutionPolicy`, there may be a performance cost if the
     value type of `ForwardIterator1` does not meet both the
     *Cpp17CopyConstructible* and *Cpp17CopyAssignable*
     requirements. — *end note*]
 *Effects:* Copies only the first element from every consecutive group of
@@ -1076,11 +1078,11 @@ template<forward_range R, weakly_incrementable O>
 ```
 *Effects:* Equivalent to:
 ``` cpp
-return ranges::rotate_copy(ranges::begin(r), middle, ranges::end(r), result);
 ```
 ### Sample <a id="alg.random.sample">[[alg.random.sample]]</a>
 ``` cpp
@@ -1113,11 +1115,11 @@ overload in namespace `std`:
   requirements [[input.iterators]].
 - `SampleIterator` meets the *Cpp17OutputIterator*
   requirements [[output.iterators]].
 - `SampleIterator` meets the *Cpp17RandomAccessIterator*
   requirements [[random.access.iterators]] unless `PopulationIterator`
- meets the *Cpp17ForwardIterator* requirements [[forward.iterators]].
 - `remove_reference_t<UniformRandomBitGenerator>` meets the requirements
   of a uniform random bit generator type [[rand.req.urng]].
 *Effects:* Copies min(`last - first`,  `n`) elements (the *sample*) from
 \[`first`, `last`) (the *population*) to `out` such that each possible
@@ -1131,13 +1133,13 @@ sampling* and *reservoir sampling*. — *end note*]
 *Complexity:* 𝑂(`last - first`).
 *Remarks:*
 - For the overload in namespace `std`, stable if and only if
-  `PopulationIterator` meets the *Cpp17ForwardIterator* requirements.
- For the first overload in namespace `ranges`, stable if and only if
-  `I` models `forward_iterator`.
 - To the extent that the implementation of this function makes use of
   random numbers, the object `g` serves as the implementation’s source
   of randomness.
 ### Shuffle <a id="alg.random.shuffle">[[alg.random.shuffle]]</a>
@@ -1186,23 +1188,34 @@ template<class ForwardIterator>
                typename iterator_traits<ForwardIterator>::difference_type n);
 template<class ExecutionPolicy, class ForwardIterator>
   ForwardIterator
     shift_left(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
                typename iterator_traits<ForwardIterator>::difference_type n);
 ```
-*Preconditions:* `n >= 0` is `true`. The type of `*first` meets the
-*Cpp17MoveAssignable* requirements.
 *Effects:* If `n == 0` or `n >= last - first`, does nothing. Otherwise,
 moves the element from position `first + n + i` into position
-`first + i` for each non-negative integer `i < (last - first) - n`. In
-the first overload case, does so in order starting from `i = 0` and
-proceeding to `i = (last - first) - n - 1`.
-*Returns:* `first + (last - first - n)` if `n < last - first`, otherwise
-`first`.
 *Complexity:* At most `(last - first) - n` assignments.
 ``` cpp
 template<class ForwardIterator>
@@ -1211,23 +1224,39 @@ template<class ForwardIterator>
                 typename iterator_traits<ForwardIterator>::difference_type n);
 template<class ExecutionPolicy, class ForwardIterator>
   ForwardIterator
     shift_right(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
                 typename iterator_traits<ForwardIterator>::difference_type n);
 ```
-*Preconditions:* `n >= 0` is `true`. The type of `*first` meets the
-*Cpp17MoveAssignable* requirements. `ForwardIterator` meets the
 *Cpp17BidirectionalIterator* requirements [[bidirectional.iterators]] or
 the *Cpp17ValueSwappable* requirements.
 *Effects:* If `n == 0` or `n >= last - first`, does nothing. Otherwise,
 moves the element from position `first + i` into position
 `first + n + i` for each non-negative integer `i < (last - first) - n`.
-In the first overload case, if `ForwardIterator` meets the
-*Cpp17BidirectionalIterator* requirements, does so in order starting
-from `i = (last - first) - n - 1` and proceeding to `i = 0`.
-*Returns:* `first + n` if `n < last - first`, otherwise `last`.
 *Complexity:* At most `(last - first) - n` assignments or swaps.

 ```
 Let N be max(0, `n`).
 *Mandates:* The type `Size` is convertible to an integral
+type [[conv.integral]], [[class.conv]].
 *Effects:* For each non-negative integer i < N, performs
+`*(result + `i`) = *(first + `i`)`.
 *Returns:*
 - `result + `N for the overloads in namespace `std`.
 - `{first + `N`, result + `N`}` for the overload in namespace `ranges`.
 which the condition E holds.
 *Preconditions:* The ranges \[`first`, `last`) and \[`result`,
 `result + (last - first)`) do not overlap.
+[*Note 1*: For the overload with an `ExecutionPolicy`, there might be a
 performance cost if `iterator_traits<ForwardIterator1>::value_type` is
 not *Cpp17MoveConstructible*
 ([[cpp17.moveconstructible]]). — *end note*]
 *Effects:* Copies all of the elements referred to by the iterator `i` in
 *Preconditions:* `result` is not in the range (`first`, `last`).
 *Effects:* Copies elements in the range \[`first`, `last`) into the
 range \[`result - `N, `result`) starting from `last - 1` and proceeding
+to `first`.[^2]
+For each positive integer n ≤ N, performs
 `*(result - `n`) = *(last - `n`)`.
 *Returns:*
 - `result - `N for the overload in namespace `std`.
 *Preconditions:* `result` is not in the range (`first`, `last`).
 *Effects:* Moves elements in the range \[`first`, `last`) into the range
 \[`result - `N, `result`) starting from `last - 1` and proceeding to
+`first`.[^3]
+For each positive integer n ≤ N, performs `*(result - `n`) = `E.
 *Returns:*
 - `result - `N for the overload in namespace `std`.
 - `{last, result - `N`}` for the overloads in namespace `ranges`.
   constexpr OutputIterator fill_n(OutputIterator first, Size n, const T& value);
 template<class ExecutionPolicy, class ForwardIterator, class Size, class T>
   ForwardIterator fill_n(ExecutionPolicy&& exec,
                          ForwardIterator first, Size n, const T& value);
 template<class T, output_iterator<const T&> O, sentinel_for<O> S>
   constexpr O ranges::fill(O first, S last, const T& value);
 template<class T, output_range<const T&> R>
   constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value);
 template<class T, output_iterator<const T&> O>
 Let N be max(0, `n`) for the `fill_n` algorithms, and `last - first` for
 the `fill` algorithms.
 *Mandates:* The expression `value` is
 writable [[iterator.requirements.general]] to the output iterator. The
+type `Size` is convertible to an integral
+type [[conv.integral]], [[class.conv]].
 *Effects:* Assigns `value` through all the iterators in the range
 \[`first`, `first + `N).
 *Returns:* `first + `N.
 Let N be max(0, `n`) for the `generate_n` algorithms, and `last - first`
 for the `generate` algorithms.
 *Mandates:* `Size` is convertible to an integral
+type [[conv.integral]], [[class.conv]].
 *Effects:* Assigns the result of successive evaluations of `gen()`
 through each iterator in the range \[`first`, `first + `N).
 *Returns:* `first + `N.
 *Returns:* Let j be the end of the resulting range. Returns:
 - j for the overloads in namespace `std`.
 - `{`j`, last}` for the overloads in namespace `ranges`.
 *Complexity:* Exactly `last - first` applications of the corresponding
 predicate and any projection.
+*Remarks:* Stable [[algorithm.stable]].
 [*Note 1*: Each element in the range \[`ret`, `last`), where `ret` is
 the returned value, has a valid but unspecified state, because the
 algorithms can eliminate elements by moving from elements that were
 originally in that range. — *end note*]
 `result`.
 *Preconditions:* The ranges \[`first`, `last`) and \[`result`,
 `result + (last - first)`) do not overlap.
+[*Note 2*: For the overloads with an `ExecutionPolicy`, there might be
+a performance cost if `iterator_traits<ForwardIterator1>::value_type`
+does not meet the *Cpp17MoveConstructible*
+([[cpp17.moveconstructible]]) requirements. — *end note*]
 *Effects:* Copies all the elements referred to by the iterator `i` in
 the range \[`first`, `last`) for which E is `false`.
 *Returns:*
 - `bool(pred(*(i - 1), *i))` for the overloads in namespace `std`;
 - `bool(invoke(comp, invoke(proj, *(i - 1)), invoke(proj, *i)))` for the
   overloads in namespace `ranges`.
+*Preconditions:* For the overloads in namespace `std`, `pred` is an
 equivalence relation and the type of `*first` meets the
 *Cpp17MoveAssignable* requirements ([[cpp17.moveassignable]]).
 *Effects:* For a nonempty range, eliminates all but the first element
 from every consecutive group of equivalent elements referred to by the
 - The ranges \[`first`, `last`) and \[`result`, `result+(last-first)`)
   do not overlap.
 - For the overloads in namespace `std`:
   - The comparison function is an equivalence relation.
   - For the overloads with no `ExecutionPolicy`, let `T` be the value
+    type of `InputIterator`. If `InputIterator` models
+ `forward_iterator` [[iterator.concept.forward]], then there are no
+ additional requirements for `T`. Otherwise, if `OutputIterator`
+ meets the *Cpp17ForwardIterator* requirements and its value type is
+ the same as `T`, then `T` meets the *Cpp17CopyAssignable*
     ([[cpp17.copyassignable]]) requirements. Otherwise, `T` meets both
     the *Cpp17CopyConstructible* ([[cpp17.copyconstructible]]) and
     *Cpp17CopyAssignable* requirements. \[*Note 1*: For the overloads
+    with an `ExecutionPolicy`, there might be a performance cost if the
     value type of `ForwardIterator1` does not meet both the
     *Cpp17CopyConstructible* and *Cpp17CopyAssignable*
     requirements. — *end note*]
 *Effects:* Copies only the first element from every consecutive group of
 ```
 *Effects:* Equivalent to:
 ``` cpp
+return ranges::rotate_copy(ranges::begin(r), middle, ranges::end(r), std::move(result));
 ```
 ### Sample <a id="alg.random.sample">[[alg.random.sample]]</a>
 ``` cpp
   requirements [[input.iterators]].
 - `SampleIterator` meets the *Cpp17OutputIterator*
   requirements [[output.iterators]].
 - `SampleIterator` meets the *Cpp17RandomAccessIterator*
   requirements [[random.access.iterators]] unless `PopulationIterator`
+ models `forward_iterator` [[iterator.concept.forward]].
 - `remove_reference_t<UniformRandomBitGenerator>` meets the requirements
   of a uniform random bit generator type [[rand.req.urng]].
 *Effects:* Copies min(`last - first`,  `n`) elements (the *sample*) from
 \[`first`, `last`) (the *population*) to `out` such that each possible
 *Complexity:* 𝑂(`last - first`).
 *Remarks:*
 - For the overload in namespace `std`, stable if and only if
+  `PopulationIterator` models `forward_iterator`. For the first overload
+  in namespace `ranges`, stable if and only if `I` models
+  `forward_iterator`.
 - To the extent that the implementation of this function makes use of
   random numbers, the object `g` serves as the implementation’s source
   of randomness.
 ### Shuffle <a id="alg.random.shuffle">[[alg.random.shuffle]]</a>
                typename iterator_traits<ForwardIterator>::difference_type n);
 template<class ExecutionPolicy, class ForwardIterator>
   ForwardIterator
     shift_left(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
                typename iterator_traits<ForwardIterator>::difference_type n);
+template<permutable I, sentinel_for<I> S>
+  constexpr subrange<I> ranges::shift_left(I first, S last, iter_difference_t<I> n);
+template<forward_range R>
+  requires permutable<iterator_t<R>>
+  constexpr borrowed_subrange_t<R> ranges::shift_left(R&& r, range_difference_t<R> n)
 ```
+*Preconditions:* `n >= 0` is `true`. For the overloads in namespace
+`std`, the type of `*first` meets the *Cpp17MoveAssignable*
+requirements.
 *Effects:* If `n == 0` or `n >= last - first`, does nothing. Otherwise,
 moves the element from position `first + n + i` into position
+`first + i` for each non-negative integer `i < (last - first) - n`. For
+the overloads without an `ExecutionPolicy` template parameter, does so
+in order starting from `i = 0` and proceeding to
+`i = (last - first) - n - 1`.
+*Returns:* Let *NEW_LAST* be `first + (last - first - n)` if
+`n < last - first`, otherwise `first`.
+- *NEW_LAST* for the overloads in namespace `std`.
+- `{first, `*`NEW_LAST`*`}` for the overloads in namespace `ranges`.
 *Complexity:* At most `(last - first) - n` assignments.
 ``` cpp
 template<class ForwardIterator>
                 typename iterator_traits<ForwardIterator>::difference_type n);
 template<class ExecutionPolicy, class ForwardIterator>
   ForwardIterator
     shift_right(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last,
                 typename iterator_traits<ForwardIterator>::difference_type n);
+template<permutable I, sentinel_for<I> S>
+  constexpr subrange<I> ranges::shift_right(I first, S last, iter_difference_t<I> n);
+template<forward_range R>
+  requires permutable<iterator_t<R>>
+  constexpr borrowed_subrange_t<R> ranges::shift_right(R&& r, range_difference_t<R> n);
 ```
+*Preconditions:* `n >= 0` is `true`. For the overloads in namespace
+`std`, the type of `*first` meets the *Cpp17MoveAssignable*
+requirements, and `ForwardIterator` meets the
 *Cpp17BidirectionalIterator* requirements [[bidirectional.iterators]] or
 the *Cpp17ValueSwappable* requirements.
 *Effects:* If `n == 0` or `n >= last - first`, does nothing. Otherwise,
 moves the element from position `first + i` into position
 `first + n + i` for each non-negative integer `i < (last - first) - n`.
+Does so in order starting from `i = (last - first) - n - 1` and
+proceeding to `i = 0` if:
+- for the overload in namespace `std` without an `ExecutionPolicy`
+  template parameter, `ForwardIterator` meets the
+  *Cpp17BidirectionalIterator* requirements,
+- for the overloads in namespace `ranges`, `I` models
+  `bidirectional_iterator`.
+*Returns:* Let *NEW_FIRST* be `first + n` if `n < last - first`,
+otherwise `last`.
+- *NEW_FIRST* for the overloads in namespace `std`.
+- `{`*`NEW_FIRST`*`, last}` for the overloads in namespace `ranges`.
 *Complexity:* At most `(last - first) - n` assignments or swaps.

Diff to HTML by rtfpessoa