[alg.merge] - C++17 → C++20

Files changed (1) hide show

tmp/tmp43ohu_jl/{from.md → to.md} +75 -31

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

@@ -1,11 +1,11 @@
 ### Merge <a id="alg.merge">[[alg.merge]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
-  OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator>
@@ -15,43 +15,67 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
           ForwardIterator2 first2, ForwardIterator2 last2,
           ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
-  OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     merge(ExecutionPolicy&& exec,
           ForwardIterator1 first1, ForwardIterator1 last1,
           ForwardIterator2 first2, ForwardIterator2 last2,
           ForwardIterator result, Compare comp);
 ```
-*Requires:* The ranges \[`first1`, `last1`) and \[`first2`, `last2`)
-shall be sorted with respect to `operator<` or `comp`. The resulting
-range shall not overlap with either of the original ranges.
-*Effects:*  Copies all the elements of the two ranges \[`first1`,
 `last1`) and \[`first2`, `last2`) into the range \[`result`,
-`result_last`), where `result_last` is
-`result + (last1 - first1) + (last2 - first2)`, such that the resulting
-range satisfies `is_sorted(result, result_last)` or
-`is_sorted(result, result_last, comp)`, respectively.
-*Returns:* `result + (last1 - first1) + (last2 - first2)`.
-*Complexity:* Let N = `(last1 - first1) + (last2 - first2)`:
-- For the overloads with no `ExecutionPolicy`, at most N - 1
-  comparisons.
 - For the overloads with an `ExecutionPolicy`, 𝑂(N) comparisons.
-*Remarks:* Stable ([[algorithm.stable]]).
 ``` cpp
 template<class BidirectionalIterator>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
@@ -69,32 +93,52 @@ template<class BidirectionalIterator, class Compare>
 template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
   void inplace_merge(ExecutionPolicy&& exec,
                      BidirectionalIterator first,
                      BidirectionalIterator middle,
                      BidirectionalIterator last, Compare comp);
 ```
-*Requires:* The ranges \[`first`, `middle`) and \[`middle`, `last`)
-shall be sorted with respect to `operator<` or `comp`.
-`BidirectionalIterator` shall satisfy the requirements of
-`ValueSwappable` ([[swappable.requirements]]). The type of `*first`
-shall satisfy the requirements of `MoveConstructible`
-(Table  [[tab:moveconstructible]]) and of `MoveAssignable`
-(Table  [[tab:moveassignable]]).
 *Effects:* Merges two sorted consecutive ranges \[`first`, `middle`) and
 \[`middle`, `last`), putting the result of the merge into the range
-\[`first`, `last`). The resulting range will be in non-decreasing order;
-that is, for every iterator `i` in \[`first`, `last`) other than
-`first`, the condition `*i < *(i - 1)` or, respectively,
-`comp(*i, *(i - 1))` will be `false`.
 *Complexity:* Let N = `last - first`:
-- For the overloads with no `ExecutionPolicy`, if enough additional
   memory is available, exactly N - 1 comparisons.
-- For the overloads with no `ExecutionPolicy` if no additional memory is
-  available, 𝑂(N log N) comparisons.
-- For the overloads with an `ExecutionPolicy`, 𝑂(N log N) comparisons.
-*Remarks:* Stable ([[algorithm.stable]]).

 ### Merge <a id="alg.merge">[[alg.merge]]</a>
 ``` cpp
 template<class InputIterator1, class InputIterator2,
          class OutputIterator>
+ constexpr OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator>
           ForwardIterator2 first2, ForwardIterator2 last2,
           ForwardIterator result);
 template<class InputIterator1, class InputIterator2,
          class OutputIterator, class Compare>
+ constexpr OutputIterator
     merge(InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result, Compare comp);
 template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
          class ForwardIterator, class Compare>
   ForwardIterator
     merge(ExecutionPolicy&& exec,
           ForwardIterator1 first1, ForwardIterator1 last1,
           ForwardIterator2 first2, ForwardIterator2 last2,
           ForwardIterator result, Compare comp);
+template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+         weakly_incrementable O, class Comp = ranges::less, class Proj1 = identity,
+         class Proj2 = identity>
+  requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
+  constexpr ranges::merge_result<I1, I2, O>
+    ranges::merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
+                  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
+template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ranges::less,
+         class Proj1 = identity, class Proj2 = identity>
+  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
+  constexpr ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
+    ranges::merge(R1&& r1, R2&& r2, O result,
+                  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
 ```
+Let N be `(last1 - first1) + (last2 - first2)`. Let `comp` be `less{}`,
+`proj1` be `identity{}`, and `proj2` be `identity{}`, for the overloads
+with no parameters by those names.
+*Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
+`last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
+respectively. The resulting range does not overlap with either of the
+original ranges.
+*Effects:* Copies all the elements of the two ranges \[`first1`,
 `last1`) and \[`first2`, `last2`) into the range \[`result`,
+`result_last`), where `result_last` is `result + `N. If an element `a`
+precedes `b` in an input range, `a` is copied into the output range
+before `b`. If `e1` is an element of \[`first1`, `last1`) and `e2` of
+\[`first2`, `last2`), `e2` is copied into the output range before `e1`
+if and only if
+`bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))` is `true`.
+*Returns:*
+- `result_last` for the overloads in namespace `std`.
+- `{last1, last2, result_last}` for the overloads in namespace `ranges`.
+*Complexity:*
+- For the overloads with no `ExecutionPolicy`, at most N - 1 comparisons
+  and applications of each projection.
 - For the overloads with an `ExecutionPolicy`, 𝑂(N) comparisons.
+*Remarks:* Stable [[algorithm.stable]].
 ``` cpp
 template<class BidirectionalIterator>
   void inplace_merge(BidirectionalIterator first,
                      BidirectionalIterator middle,
 template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
   void inplace_merge(ExecutionPolicy&& exec,
                      BidirectionalIterator first,
                      BidirectionalIterator middle,
                      BidirectionalIterator last, Compare comp);
+template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+         class Proj = identity>
+  requires sortable<I, Comp, Proj>
+  I ranges::inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});
 ```
+Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
+no parameters by those names.
+*Preconditions:* \[`first`, `middle`) and \[`middle`, `last`) are valid
+ranges sorted with respect to `comp` and `proj`. For the overloads in
+namespace `std`, `BidirectionalIterator` meets the *Cpp17ValueSwappable*
+requirements [[swappable.requirements]] and the type of `*first` meets
+the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
+*Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
 *Effects:* Merges two sorted consecutive ranges \[`first`, `middle`) and
 \[`middle`, `last`), putting the result of the merge into the range
+\[`first`, `last`). The resulting range is sorted with respect to `comp`
+and `proj`.
+*Returns:* `last` for the overload in namespace `ranges`.
 *Complexity:* Let N = `last - first`:
+- For the overloads with no `ExecutionPolicy`, and if enough additional
   memory is available, exactly N - 1 comparisons.
+- Otherwise, 𝑂(N log N) comparisons.
+In either case, twice as many projections as comparisons.
+*Remarks:* Stable [[algorithm.stable]].
+``` cpp
+template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
+  requires sortable<iterator_t<R>, Comp, Proj>
+  borrowed_iterator_t<R>
+    ranges::inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
+```
+*Effects:* Equivalent to:
+``` cpp
+return ranges::inplace_merge(ranges::begin(r), middle, ranges::end(r), comp, proj);
+```

Diff to HTML by rtfpessoa