From Jason Turner

[alg.partitions]

C++23 → Trunk 11.2 KB 118 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/tmpj9ot3zz5/{from.md → to.md} +90 -21
tmp/tmpj9ot3zz5/{from.md → to.md} RENAMED
@@ -11,10 +11,17 @@ template<input_iterator I, sentinel_for<I> S, class Proj = identity,
11
  indirect_unary_predicate<projected<I, Proj>> Pred>
12
  constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});
13
  template<input_range R, class Proj = identity,
14
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
15
  constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
16
  ```
17
 
18
  Let `proj` be `identity{}` for the overloads with no parameter named
19
  `proj`.
20
 
@@ -29,22 +36,29 @@ are partitioned with respect to the expression
29
  template<class ForwardIterator, class Predicate>
30
  constexpr ForwardIterator
31
  partition(ForwardIterator first, ForwardIterator last, Predicate pred);
32
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
33
  ForwardIterator
34
- partition(ExecutionPolicy&& exec,
35
- ForwardIterator first, ForwardIterator last, Predicate pred);
36
 
37
  template<permutable I, sentinel_for<I> S, class Proj = identity,
38
  indirect_unary_predicate<projected<I, Proj>> Pred>
39
  constexpr subrange<I>
40
  ranges::partition(I first, S last, Pred pred, Proj proj = {});
41
  template<forward_range R, class Proj = identity,
42
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
43
  requires permutable<iterator_t<R>>
44
  constexpr borrowed_subrange_t<R>
45
  ranges::partition(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
46
  ```
47
 
48
  Let `proj` be `identity{}` for the overloads with no parameter named
49
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
50
 
@@ -61,35 +75,47 @@ iterator `j` in \[`first`, `i`) and `false` for every iterator `j` in
61
  - `i` for the overloads in namespace `std`.
62
  - `{i, last}` for the overloads in namespace `ranges`.
63
 
64
  *Complexity:* Let N = `last - first`:
65
 
66
- - For the overload with no `ExecutionPolicy`, exactly N applications of
67
  the predicate and projection. At most N / 2 swaps if the type of
68
  `first` meets the *Cpp17BidirectionalIterator* requirements for the
69
  overloads in namespace `std` or models `bidirectional_iterator` for
70
  the overloads in namespace `ranges`, and at most N swaps otherwise.
71
- - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
72
  applications of the predicate.
73
 
74
  ``` cpp
75
  template<class BidirectionalIterator, class Predicate>
76
  BidirectionalIterator
77
- stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
 
78
  template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
79
  BidirectionalIterator
80
  stable_partition(ExecutionPolicy&& exec,
81
  BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
82
 
83
  template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
84
  indirect_unary_predicate<projected<I, Proj>> Pred>
85
  requires permutable<I>
86
- subrange<I> ranges::stable_partition(I first, S last, Pred pred, Proj proj = {});
87
  template<bidirectional_range R, class Proj = identity,
88
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
89
  requires permutable<iterator_t<R>>
90
- borrowed_subrange_t<R> ranges::stable_partition(R&& r, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
91
  ```
92
 
93
  Let `proj` be `identity{}` for the overloads with no parameter named
94
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
95
 
@@ -110,14 +136,14 @@ range \[`i`, `last`), E(`*j`) is `false`. Returns:
110
  - `i` for the overloads in namespace `std`.
111
  - `{i, last}` for the overloads in namespace `ranges`.
112
 
113
  *Complexity:* Let N = `last - first`:
114
 
115
- - For the overloads with no `ExecutionPolicy`, at most N log₂ N swaps,
116
- but only 𝑂(N) swaps if there is enough extra memory. Exactly N
117
  applications of the predicate and projection.
118
- - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
119
  applications of the predicate.
120
 
121
  ``` cpp
122
  template<class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate>
123
  constexpr pair<OutputIterator1, OutputIterator2>
@@ -141,37 +167,80 @@ template<input_range R, weakly_incrementable O1, weakly_incrementable O2,
141
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
142
  requires indirectly_copyable<iterator_t<R>, O1> &&
143
  indirectly_copyable<iterator_t<R>, O2>
144
  constexpr ranges::partition_copy_result<borrowed_iterator_t<R>, O1, O2>
145
  ranges::partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
146
  ```
147
 
148
  Let `proj` be `identity{}` for the overloads with no parameter named
149
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
150
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
151
  *Mandates:* For the overloads in namespace `std`, the expression
152
  `*first` is writable [[iterator.requirements.general]] to `out_true` and
153
  `out_false`.
154
 
155
  *Preconditions:* The input range and output ranges do not overlap.
156
 
157
- [*Note 1*: For the overload with an `ExecutionPolicy`, there might be a
158
- performance cost if `first`’s value type does not meet the
159
- *Cpp17CopyConstructible* requirements. — *end note*]
 
 
160
 
161
- *Effects:* For each iterator `i` in \[`first`, `last`), copies `*i` to
162
- the output range beginning with `out_true` if E(`*i`) is `true`, or to
163
- the output range beginning with `out_false` otherwise.
164
 
165
- *Returns:* Let `o1` be the end of the output range beginning at
166
- `out_true`, and `o2` the end of the output range beginning at
167
- `out_false`. Returns
 
168
 
169
  - `{o1, o2}` for the overloads in namespace `std`.
170
- - `{last, o1, o2}` for the overloads in namespace `ranges`.
171
 
172
- *Complexity:* Exactly `last - first` applications of `pred` and `proj`.
173
 
174
  ``` cpp
175
  template<class ForwardIterator, class Predicate>
176
  constexpr ForwardIterator
177
  partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
 
11
  indirect_unary_predicate<projected<I, Proj>> Pred>
12
  constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});
13
  template<input_range R, class Proj = identity,
14
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
15
  constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});
16
+
17
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
18
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
19
+ bool ranges::is_partitioned(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
20
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
21
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
22
+ bool ranges::is_partitioned(Ep&& exec, R&& r, Pred pred, Proj proj = {});
23
  ```
24
 
25
  Let `proj` be `identity{}` for the overloads with no parameter named
26
  `proj`.
27
 
 
36
  template<class ForwardIterator, class Predicate>
37
  constexpr ForwardIterator
38
  partition(ForwardIterator first, ForwardIterator last, Predicate pred);
39
  template<class ExecutionPolicy, class ForwardIterator, class Predicate>
40
  ForwardIterator
41
+ partition(ExecutionPolicy&& exec, ForwardIterator first, ForwardIterator last, Predicate pred);
 
42
 
43
  template<permutable I, sentinel_for<I> S, class Proj = identity,
44
  indirect_unary_predicate<projected<I, Proj>> Pred>
45
  constexpr subrange<I>
46
  ranges::partition(I first, S last, Pred pred, Proj proj = {});
47
  template<forward_range R, class Proj = identity,
48
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
49
  requires permutable<iterator_t<R>>
50
  constexpr borrowed_subrange_t<R>
51
  ranges::partition(R&& r, Pred pred, Proj proj = {});
52
+
53
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
54
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
55
+ subrange<I> ranges::partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
56
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
57
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
58
+ requires permutable<iterator_t<R>>
59
+ borrowed_subrange_t<R> ranges::partition(Ep&& exec, R&& r, Pred pred, Proj proj = {});
60
  ```
61
 
62
  Let `proj` be `identity{}` for the overloads with no parameter named
63
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
64
 
 
75
  - `i` for the overloads in namespace `std`.
76
  - `{i, last}` for the overloads in namespace `ranges`.
77
 
78
  *Complexity:* Let N = `last - first`:
79
 
80
+ - For the non-parallel algorithm overloads, exactly N applications of
81
  the predicate and projection. At most N / 2 swaps if the type of
82
  `first` meets the *Cpp17BidirectionalIterator* requirements for the
83
  overloads in namespace `std` or models `bidirectional_iterator` for
84
  the overloads in namespace `ranges`, and at most N swaps otherwise.
85
+ - For the parallel algorithm overloads, 𝑂(N log N) swaps and 𝑂(N)
86
  applications of the predicate.
87
 
88
  ``` cpp
89
  template<class BidirectionalIterator, class Predicate>
90
  BidirectionalIterator
91
+ constexpr stable_partition(BidirectionalIterator first, BidirectionalIterator last,
92
+ Predicate pred);
93
  template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
94
  BidirectionalIterator
95
  stable_partition(ExecutionPolicy&& exec,
96
  BidirectionalIterator first, BidirectionalIterator last, Predicate pred);
97
 
98
  template<bidirectional_iterator I, sentinel_for<I> S, class Proj = identity,
99
  indirect_unary_predicate<projected<I, Proj>> Pred>
100
  requires permutable<I>
101
+ constexpr subrange<I> ranges::stable_partition(I first, S last, Pred pred, Proj proj = {});
102
  template<bidirectional_range R, class Proj = identity,
103
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
104
  requires permutable<iterator_t<R>>
105
+ constexpr borrowed_subrange_t<R> ranges::stable_partition(R&& r, Pred pred, Proj proj = {});
106
+
107
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
108
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
109
+ requires permutable<I>
110
+ subrange<I>
111
+ ranges::stable_partition(Ep&& exec, I first, S last, Pred pred, Proj proj = {});
112
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
113
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
114
+ requires permutable<iterator_t<R>>
115
+ borrowed_subrange_t<R>
116
+ ranges::stable_partition(Ep&& exec, R&& r, Pred pred, Proj proj = {});
117
  ```
118
 
119
  Let `proj` be `identity{}` for the overloads with no parameter named
120
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
121
 
 
136
  - `i` for the overloads in namespace `std`.
137
  - `{i, last}` for the overloads in namespace `ranges`.
138
 
139
  *Complexity:* Let N = `last - first`:
140
 
141
+ - For the non-parallel algorithm overloads, at most N log₂ N swaps, but
142
+ only 𝑂(N) swaps if there is enough extra memory. Exactly N
143
  applications of the predicate and projection.
144
+ - For the parallel algorithm overloads, 𝑂(N log N) swaps and 𝑂(N)
145
  applications of the predicate.
146
 
147
  ``` cpp
148
  template<class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate>
149
  constexpr pair<OutputIterator1, OutputIterator2>
 
167
  indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
168
  requires indirectly_copyable<iterator_t<R>, O1> &&
169
  indirectly_copyable<iterator_t<R>, O2>
170
  constexpr ranges::partition_copy_result<borrowed_iterator_t<R>, O1, O2>
171
  ranges::partition_copy(R&& r, O1 out_true, O2 out_false, Pred pred, Proj proj = {});
172
+
173
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
174
+ random_access_iterator O1, sized_sentinel_for<O1> OutS1,
175
+ random_access_iterator O2, sized_sentinel_for<O2> OutS2,
176
+ class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
177
+ requires indirectly_copyable<I, O1> && indirectly_copyable<I, O2>
178
+ ranges::partition_copy_result<I, O1, O2>
179
+ ranges::partition_copy(Ep&& exec, I first, S last, O1 out_true, OutS1 last_true,
180
+ O2 out_false, OutS2 last_false, Pred pred, Proj proj = {});
181
+ template<execution-policy Ep, sized-random-access-range R,
182
+ sized-random-access-range OutR1, sized-random-access-range OutR2,
183
+ class Proj = identity,
184
+ indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
185
+ requires indirectly_copyable<iterator_t<R>, iterator_t<OutR1>> &&
186
+ indirectly_copyable<iterator_t<R>, iterator_t<OutR2>>
187
+ ranges::partition_copy_result<borrowed_iterator_t<R>, borrowed_iterator_t<OutR1>,
188
+ borrowed_iterator_t<OutR2>>
189
+ ranges::partition_copy(Ep&& exec, R&& r, OutR1&& out_true_r, OutR2&& out_false_r,
190
+ Pred pred, Proj proj = {});
191
  ```
192
 
193
  Let `proj` be `identity{}` for the overloads with no parameter named
194
  `proj` and let E(x) be `bool(invoke(pred, invoke(proj, `x`)))`.
195
 
196
+ For the overloads with no parameters `last_true`, `last_false`,
197
+ `out_true_r`, or `out_false_r`, let
198
+
199
+ - M be the number of iterators `i` in \[`first`, `last`) for which
200
+ E(`*i`) is `true`, and K be `last - first - `M;
201
+ - `last_true` be `out_true + `M, and `last_false` be `out_false + `K.
202
+
203
+ For the overloads with parameters `last_true`, `last_false`,
204
+ `out_true_r`, or `out_false_r`, let M be `last_true - out_true` and K be
205
+ `last_false - out_false`.
206
+
207
+ Let:
208
+
209
+ - `i1` be the iterator in \[`first`, `last`) for which E(`*i1`) is
210
+ `true` and there are exactly M iterators `j` in \[`first`, `i1`) for
211
+ which E(`*j`) is `true`, or `last` if no such iterator exists;
212
+ - `i2` be the iterator in \[`first`, `last`) for which E(`*i2`) is
213
+ `false` and there are exactly K iterators `j` in \[`first`, `i2`) for
214
+ which E(`*j`) is `false`, or `last` if no such iterator exists;
215
+ - N be min(`i1 - first`, `i2 - first`).
216
+
217
  *Mandates:* For the overloads in namespace `std`, the expression
218
  `*first` is writable [[iterator.requirements.general]] to `out_true` and
219
  `out_false`.
220
 
221
  *Preconditions:* The input range and output ranges do not overlap.
222
 
223
+ [*Note 1*: For the parallel algorithm overload in namespace `std`,
224
+ there can be a performance cost if `first`’s value type does not meet
225
+ the *Cpp17CopyConstructible* requirements. For the parallel algorithm
226
+ overloads in namespace `ranges`, there can be a performance cost if
227
+ `first`’s value type does not model `copy_constructible`. — *end note*]
228
 
229
+ *Effects:* For each iterator `i` in \[`first`, `first + `N), copies `*i`
230
+ to the output range \[`out_true`, `last_true`) if E(`*i`) is `true`, or
231
+ to the output range \[`out_false`, `last_false`) otherwise.
232
 
233
+ *Returns:* Let `o1` be the iterator past the last copied element in the
234
+ output range \[`out_true`, `last_true`), and `o2` be the iterator past
235
+ the last copied element in the output range \[`out_false`,
236
+ `last_false`). Returns:
237
 
238
  - `{o1, o2}` for the overloads in namespace `std`.
239
+ - `{first + `N`, o1, o2}` for the overloads in namespace `ranges`.
240
 
241
+ *Complexity:* At most `last - first` applications of `pred` and `proj`.
242
 
243
  ``` cpp
244
  template<class ForwardIterator, class Predicate>
245
  constexpr ForwardIterator
246
  partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);