From Jason Turner

[alg.merge]

C++23 → Trunk 7.9 KB 98 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpki80906x/{from.md → to.md} +72 -21
tmp/tmpki80906x/{from.md → to.md} RENAMED
@@ -40,56 +40,87 @@ template<input_range R1, input_range R2, weakly_incrementable O, class Comp = ra
40
  class Proj1 = identity, class Proj2 = identity>
41
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
42
  constexpr ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
43
  ranges::merge(R1&& r1, R2&& r2, O result,
44
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
45
  ```
46
 
47
- Let N be `(last1 - first1) + (last2 - first2)`. Let `comp` be `less{}`,
48
- `proj1` be `identity{}`, and `proj2` be `identity{}`, for the overloads
49
- with no parameters by those names.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
50
 
51
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
52
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
53
  respectively. The resulting range does not overlap with either of the
54
  original ranges.
55
 
56
- *Effects:* Copies all the elements of the two ranges \[`first1`,
57
- `last1`) and \[`first2`, `last2`) into the range \[`result`,
58
- `result_last`), where `result_last` is `result + `N. If an element `a`
59
- precedes `b` in an input range, `a` is copied into the output range
60
- before `b`. If `e1` is an element of \[`first1`, `last1`) and `e2` of
61
- \[`first2`, `last2`), `e2` is copied into the output range before `e1`
62
- if and only if
63
- `bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))` is `true`.
64
 
65
  *Returns:*
66
 
67
- - `result_last` for the overloads in namespace `std`.
68
- - `{last1, last2, result_last}` for the overloads in namespace `ranges`.
 
69
 
70
  *Complexity:*
71
 
72
- - For the overloads with no `ExecutionPolicy`, at most N - 1 comparisons
73
  and applications of each projection.
74
- - For the overloads with an `ExecutionPolicy`, 𝑂(N) comparisons.
 
75
 
76
  *Remarks:* Stable [[algorithm.stable]].
77
 
78
  ``` cpp
79
  template<class BidirectionalIterator>
80
- void inplace_merge(BidirectionalIterator first,
81
  BidirectionalIterator middle,
82
  BidirectionalIterator last);
83
  template<class ExecutionPolicy, class BidirectionalIterator>
84
  void inplace_merge(ExecutionPolicy&& exec,
85
  BidirectionalIterator first,
86
  BidirectionalIterator middle,
87
  BidirectionalIterator last);
88
 
89
  template<class BidirectionalIterator, class Compare>
90
- void inplace_merge(BidirectionalIterator first,
91
  BidirectionalIterator middle,
92
  BidirectionalIterator last, Compare comp);
93
  template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
94
  void inplace_merge(ExecutionPolicy&& exec,
95
  BidirectionalIterator first,
@@ -97,11 +128,15 @@ template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
97
  BidirectionalIterator last, Compare comp);
98
 
99
  template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
100
  class Proj = identity>
101
  requires sortable<I, Comp, Proj>
102
- I ranges::inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});
 
 
 
 
103
  ```
104
 
105
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
106
  no parameters by those names.
107
 
@@ -119,26 +154,42 @@ and `proj`.
119
 
120
  *Returns:* `last` for the overload in namespace `ranges`.
121
 
122
  *Complexity:* Let N = `last - first`:
123
 
124
- - For the overloads with no `ExecutionPolicy`, and if enough additional
125
- memory is available, exactly N - 1 comparisons.
126
  - Otherwise, 𝑂(N log N) comparisons.
127
 
128
  In either case, twice as many projections as comparisons.
129
 
130
  *Remarks:* Stable [[algorithm.stable]].
131
 
132
  ``` cpp
133
  template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
134
  requires sortable<iterator_t<R>, Comp, Proj>
135
- borrowed_iterator_t<R>
136
  ranges::inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
137
  ```
138
 
139
  *Effects:* Equivalent to:
140
 
141
  ``` cpp
142
  return ranges::inplace_merge(ranges::begin(r), middle, ranges::end(r), comp, proj);
143
  ```
144
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
40
  class Proj1 = identity, class Proj2 = identity>
41
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
42
  constexpr ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
43
  ranges::merge(R1&& r1, R2&& r2, O result,
44
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
45
+
46
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
47
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
48
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
49
+ class Proj1 = identity, class Proj2 = identity>
50
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
51
+ ranges::merge_result<I1, I2, O>
52
+ ranges::merge(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2, O result, OutS result_last,
53
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
54
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
55
+ sized-random-access-range OutR, class Comp = ranges::less,
56
+ class Proj1 = identity, class Proj2 = identity>
57
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
58
+ ranges::merge_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, borrowed_iterator_t<OutR>>
59
+ ranges::merge(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
60
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
61
  ```
62
 
63
+ Let:
64
+
65
+ - N be:
66
+ - `(last1 - first1) + (last2 - first2)` for the overloads with no
67
+ parameter `result_last` or `result_r`;
68
+ - min(`(last1 - first1) + (last2 - first2)`, `result_last - result`)
69
+ for the overloads with parameters `result_last` or `result_r`;
70
+ - `comp` be `less{}`, `proj1` be `identity{}`, and `proj2` be
71
+ `identity{}`, for the overloads with no parameters by those names;
72
+ - E(`e1`, `e1`) be
73
+ `bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))`;
74
+ - K be the smallest integer in \[`0`, `last1 - first1`) such that for
75
+ the element `e1` in the position `first1 + `K there are at least N - K
76
+ elements `e2` in \[`first2`, `last2`) for which E(`e1`, `e1`) holds,
77
+ and be equal to `last1 - first1` if no such integer exists.
78
+ \[*Note 1*: `first1 + `K points to the position past the last element
79
+ to be copied. — *end note*]
80
 
81
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
82
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
83
  respectively. The resulting range does not overlap with either of the
84
  original ranges.
85
 
86
+ *Effects:* Copies the first K elements of the range \[`first1`, `last1`)
87
+ and the first N - K elements of the range \[`first2`, `last2`) into the
88
+ range \[`result`, `result + `N). If an element `a` precedes `b` in an
89
+ input range, `a` is copied into the output range before `b`. If `e1` is
90
+ an element of \[`first1`, `last1`) and `e2` of \[`first2`, `last2`),
91
+ `e2` is copied into the output range before `e1` if and only if
92
+ E(`e1`, `e1`) is `true`.
 
93
 
94
  *Returns:*
95
 
96
+ - `result + `N for the overloads in namespace `std`.
97
+ - `{first1 + `K`, first2 + `N` - `K`, result + `N`}` for the overloads
98
+ in namespace `ranges`.
99
 
100
  *Complexity:*
101
 
102
+ - For the non-parallel algorithm overloads, at most N - 1 comparisons
103
  and applications of each projection.
104
+ - For the parallel algorithm overloads, 𝑂(N) comparisons and
105
+ applications of each projection.
106
 
107
  *Remarks:* Stable [[algorithm.stable]].
108
 
109
  ``` cpp
110
  template<class BidirectionalIterator>
111
+ constexpr void inplace_merge(BidirectionalIterator first,
112
  BidirectionalIterator middle,
113
  BidirectionalIterator last);
114
  template<class ExecutionPolicy, class BidirectionalIterator>
115
  void inplace_merge(ExecutionPolicy&& exec,
116
  BidirectionalIterator first,
117
  BidirectionalIterator middle,
118
  BidirectionalIterator last);
119
 
120
  template<class BidirectionalIterator, class Compare>
121
+ constexpr void inplace_merge(BidirectionalIterator first,
122
  BidirectionalIterator middle,
123
  BidirectionalIterator last, Compare comp);
124
  template<class ExecutionPolicy, class BidirectionalIterator, class Compare>
125
  void inplace_merge(ExecutionPolicy&& exec,
126
  BidirectionalIterator first,
 
128
  BidirectionalIterator last, Compare comp);
129
 
130
  template<bidirectional_iterator I, sentinel_for<I> S, class Comp = ranges::less,
131
  class Proj = identity>
132
  requires sortable<I, Comp, Proj>
133
+ constexpr I ranges::inplace_merge(I first, I middle, S last, Comp comp = {}, Proj proj = {});
134
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
135
+ class Comp = ranges::less, class Proj = identity>
136
+ requires sortable<I, Comp, Proj>
137
+ I ranges::inplace_merge(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {});
138
  ```
139
 
140
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
141
  no parameters by those names.
142
 
 
154
 
155
  *Returns:* `last` for the overload in namespace `ranges`.
156
 
157
  *Complexity:* Let N = `last - first`:
158
 
159
+ - For the non-parallel algorithm overloads, and if enough additional
160
+ memory is available, at most N - 1 comparisons.
161
  - Otherwise, 𝑂(N log N) comparisons.
162
 
163
  In either case, twice as many projections as comparisons.
164
 
165
  *Remarks:* Stable [[algorithm.stable]].
166
 
167
  ``` cpp
168
  template<bidirectional_range R, class Comp = ranges::less, class Proj = identity>
169
  requires sortable<iterator_t<R>, Comp, Proj>
170
+ constexpr borrowed_iterator_t<R>
171
  ranges::inplace_merge(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
172
  ```
173
 
174
  *Effects:* Equivalent to:
175
 
176
  ``` cpp
177
  return ranges::inplace_merge(ranges::begin(r), middle, ranges::end(r), comp, proj);
178
  ```
179
 
180
+ ``` cpp
181
+ template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less,
182
+ class Proj = identity>
183
+ requires sortable<iterator_t<R>, Comp, Proj>
184
+ borrowed_iterator_t<R>
185
+ ranges::inplace_merge(Ep&& exec, R&& r, iterator_t<R> middle, Comp comp = {},
186
+ Proj proj = {});
187
+ ```
188
+
189
+ *Effects:* Equivalent to:
190
+
191
+ ``` cpp
192
+ return ranges::inplace_merge(std::forward<Ep>(exec), ranges::begin(r), middle,
193
+ ranges::end(r), comp, proj);
194
+ ```
195
+