From Jason Turner

[alg.set.operations]

C++23 → Trunk 15.5 KB 195 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/tmpkrewst5s/{from.md → to.md} +159 -29
tmp/tmpkrewst5s/{from.md → to.md} RENAMED
@@ -40,10 +40,24 @@ template<input_range R1, input_range R2, class Proj1 = identity,
40
  class Proj2 = identity,
41
  indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
42
  projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
43
  constexpr bool ranges::includes(R1&& r1, R2&& r2, Comp comp = {},
44
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
45
  ```
46
 
47
  Let `comp` be `less{}`, `proj1` be `identity{}`, and `proj2` be
48
  `identity{}`, for the overloads with no parameters by those names.
49
 
@@ -101,29 +115,58 @@ template<input_range R1, input_range R2, weakly_incrementable O,
101
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
102
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
103
  constexpr ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
104
  ranges::set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
105
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
106
  ```
107
 
108
- Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
109
- overloads with no parameters by those names.
 
 
 
 
 
 
 
110
 
111
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
112
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
113
  respectively. The resulting range does not overlap with either of the
114
  original ranges.
115
 
116
- *Effects:* Constructs a sorted union of the elements from the two
117
- ranges; that is, the set of elements that are present in one or both of
118
- the ranges.
119
 
120
- *Returns:* Let `result_last` be the end of the constructed range.
121
- Returns
122
 
123
  - `result_last` for the overloads in namespace `std`.
124
- - `{last1, last2, result_last}` for the overloads in namespace `ranges`.
 
 
 
 
 
125
 
126
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
127
  comparisons and applications of each projection.
128
 
129
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
@@ -175,29 +218,58 @@ template<input_range R1, input_range R2, weakly_incrementable O,
175
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
176
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
177
  constexpr ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
178
  ranges::set_intersection(R1&& r1, R2&& r2, O result,
179
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
180
  ```
181
 
182
- Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
183
- overloads with no parameters by those names.
 
 
 
 
 
 
 
184
 
185
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
186
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
187
  respectively. The resulting range does not overlap with either of the
188
  original ranges.
189
 
190
- *Effects:* Constructs a sorted intersection of the elements from the two
191
  ranges; that is, the set of elements that are present in both of the
192
  ranges.
193
 
194
- *Returns:* Let `result_last` be the end of the constructed range.
195
- Returns
196
 
197
  - `result_last` for the overloads in namespace `std`.
198
- - `{last1, last2, result_last}` for the overloads in namespace `ranges`.
 
 
 
 
 
199
 
200
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
201
  comparisons and applications of each projection.
202
 
203
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
@@ -247,29 +319,56 @@ template<input_range R1, input_range R2, weakly_incrementable O,
247
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
248
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
249
  constexpr ranges::set_difference_result<borrowed_iterator_t<R1>, O>
250
  ranges::set_difference(R1&& r1, R2&& r2, O result,
251
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
252
  ```
253
 
254
- Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
255
- overloads with no parameters by those names.
 
 
 
 
 
 
 
256
 
257
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
258
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
259
  respectively. The resulting range does not overlap with either of the
260
  original ranges.
261
 
262
- *Effects:* Copies the elements of the range \[`first1`, `last1`) which
263
- are not present in the range \[`first2`, `last2`) to the range beginning
264
- at `result`. The elements in the constructed range are sorted.
265
 
266
- *Returns:* Let `result_last` be the end of the constructed range.
267
- Returns
268
 
269
  - `result_last` for the overloads in namespace `std`.
270
- - `{last1, result_last}` for the overloads in namespace `ranges`.
 
 
 
 
271
 
272
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
273
  comparisons and applications of each projection.
274
 
275
  *Remarks:* If \[`first1`, `last1`) contains m elements that are
@@ -321,31 +420,62 @@ template<input_range R1, input_range R2, weakly_incrementable O,
321
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
322
  constexpr ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>,
323
  borrowed_iterator_t<R2>, O>
324
  ranges::set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
325
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
326
  ```
327
 
328
- Let `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
329
- overloads with no parameters by those names.
 
 
 
 
 
 
 
 
 
330
 
331
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
332
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
333
  respectively. The resulting range does not overlap with either of the
334
  original ranges.
335
 
336
  *Effects:* Copies the elements of the range \[`first1`, `last1`) that
337
  are not present in the range \[`first2`, `last2`), and the elements of
338
  the range \[`first2`, `last2`) that are not present in the range
339
- \[`first1`, `last1`) to the range beginning at `result`. The elements in
340
- the constructed range are sorted.
341
 
342
- *Returns:* Let `result_last` be the end of the constructed range.
343
- Returns
344
 
345
  - `result_last` for the overloads in namespace `std`.
346
- - `{last1, last2, result_last}` for the overloads in namespace `ranges`.
 
 
 
 
 
347
 
348
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
349
  comparisons and applications of each projection.
350
 
351
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
 
40
  class Proj2 = identity,
41
  indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
42
  projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
43
  constexpr bool ranges::includes(R1&& r1, R2&& r2, Comp comp = {},
44
  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
+ class Proj1 = identity, class Proj2 = identity,
49
+ indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp =
50
+ ranges::less>
51
+ bool ranges::includes(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
52
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
53
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
54
+ class Proj1 = identity, class Proj2 = identity,
55
+ indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
56
+ projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
57
+ bool ranges::includes(Ep&& exec, R1&& r1, R2&& r2,
58
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
59
  ```
60
 
61
  Let `comp` be `less{}`, `proj1` be `identity{}`, and `proj2` be
62
  `identity{}`, for the overloads with no parameters by those names.
63
 
 
115
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
116
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
117
  constexpr ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
118
  ranges::set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
119
  Proj1 proj1 = {}, Proj2 proj2 = {});
120
+
121
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
122
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
123
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
124
+ class Proj1 = identity, class Proj2 = identity>
125
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
126
+ ranges::set_union_result<I1, I2, O>
127
+ ranges::set_union(Ep&& exec, I1 first1, S1 last1,
128
+ I2 first2, S2 last2, O result, OutS result_last,
129
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
130
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
131
+ sized-random-access-range OutR, class Comp = ranges::less,
132
+ class Proj1 = identity, class Proj2 = identity>
133
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
134
+ ranges::set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>,
135
+ borrowed_iterator_t<OutR>>
136
+ ranges::set_union(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {},
137
+ Proj1 proj1 = {}, Proj2 proj2 = {});
138
  ```
139
 
140
+ Let:
141
+
142
+ - `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
143
+ overloads with no parameters by those names;
144
+ - M be `last1 - first1` plus the number of elements in \[`first2`,
145
+ `last2`) that are not present in \[`first1`, `last1`);
146
+ - `result_last` be `result + `M for the overloads with no parameter
147
+ `result_last` or `result_r`;
148
+ - N be min(M, `result_last - result`).
149
 
150
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
151
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
152
  respectively. The resulting range does not overlap with either of the
153
  original ranges.
154
 
155
+ *Effects:* Constructs a sorted union of N elements from the two ranges;
156
+ that is, the set of elements that are present in one or both of the
157
+ ranges.
158
 
159
+ *Returns:*
 
160
 
161
  - `result_last` for the overloads in namespace `std`.
162
+ - `{last1, last2, result + `N`}` for the overloads in namespace
163
+ `ranges`, if N is equal to M.
164
+ - Otherwise, `{j1, j2, result_last}` for the overloads in namespace
165
+ `ranges`, where the iterators `j1` and `j2` point to positions past
166
+ the last copied or skipped elements in \[`first1`, `last1`) and
167
+ \[`first2`, `last2`), respectively.
168
 
169
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
170
  comparisons and applications of each projection.
171
 
172
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
 
218
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
219
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
220
  constexpr ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
221
  ranges::set_intersection(R1&& r1, R2&& r2, O result,
222
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
223
+
224
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
225
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
226
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
227
+ class Proj1 = identity, class Proj2 = identity>
228
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
229
+ ranges::set_intersection_result<I1, I2, O>
230
+ ranges::set_intersection(Ep&& exec, I1 first1, S1 last1,
231
+ I2 first2, S2 last2, O result, OutS result_last,
232
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
233
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
234
+ sized-random-access-range OutR, class Comp = ranges::less,
235
+ class Proj1 = identity, class Proj2 = identity>
236
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
237
+ ranges::set_intersection_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>,
238
+ borrowed_iterator_t<OutR>>
239
+ ranges::set_intersection(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {},
240
+ Proj1 proj1 = {}, Proj2 proj2 = {});
241
  ```
242
 
243
+ Let:
244
+
245
+ - `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
246
+ overloads with no parameters by those names;
247
+ - M be the number of elements in \[`first1`, `last1`) that are present
248
+ in \[`first2`, `last2`);
249
+ - `result_last` be `result + `M for the overloads with no parameter
250
+ `result_last` or `result_r`;
251
+ - N be min(M, `result_last - result`).
252
 
253
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
254
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
255
  respectively. The resulting range does not overlap with either of the
256
  original ranges.
257
 
258
+ *Effects:* Constructs a sorted intersection of N elements from the two
259
  ranges; that is, the set of elements that are present in both of the
260
  ranges.
261
 
262
+ *Returns:*
 
263
 
264
  - `result_last` for the overloads in namespace `std`.
265
+ - `{last1, last2, result + `N`}` for the overloads in namespace
266
+ `ranges`, if N is equal to M.
267
+ - Otherwise, `{j1, j2, result_last}` for the overloads in namespace
268
+ `ranges`, where the iterators `j1` and `j2` point to positions past
269
+ the last copied or skipped elements in \[`first1`, `last1`) and
270
+ \[`first2`, `last2`), respectively.
271
 
272
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
273
  comparisons and applications of each projection.
274
 
275
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains
 
319
  class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
320
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
321
  constexpr ranges::set_difference_result<borrowed_iterator_t<R1>, O>
322
  ranges::set_difference(R1&& r1, R2&& r2, O result,
323
  Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
324
+
325
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
326
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
327
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
328
+ class Proj1 = identity, class Proj2 = identity>
329
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
330
+ ranges::set_difference_result<I1, O>
331
+ ranges::set_difference(Ep&& exec, I1 first1, S1 last1,
332
+ I2 first2, S2 last2, O result, OutS result_last,
333
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
334
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
335
+ sized-random-access-range OutR, class Comp = ranges::less,
336
+ class Proj1 = identity, class Proj2 = identity>
337
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
338
+ ranges::set_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<OutR>>
339
+ ranges::set_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r, Comp comp = {},
340
+ Proj1 proj1 = {}, Proj2 proj2 = {});
341
  ```
342
 
343
+ Let:
344
+
345
+ - `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
346
+ overloads with no parameters by those names;
347
+ - M be the number of elements in \[`first1`, `last1`) that are not
348
+ present in \[`first2`, `last2`);
349
+ - `result_last` be `result + `M for the overloads with no parameter
350
+ `result_last` or `result_r`;
351
+ - N be min(M, `result_last - result`).
352
 
353
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
354
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
355
  respectively. The resulting range does not overlap with either of the
356
  original ranges.
357
 
358
+ *Effects:* Copies N elements of the range \[`first1`, `last1`) which are
359
+ not present in the range \[`first2`, `last2`) to the range \[`result`,
360
+ `result + `N). The elements in the constructed range are sorted.
361
 
362
+ *Returns:*
 
363
 
364
  - `result_last` for the overloads in namespace `std`.
365
+ - `{last1, result + `N`}` for the overloads in namespace `ranges`, if N
366
+ is equal to M.
367
+ - Otherwise, `{j1, result_last}` for the overloads in namespace
368
+ `ranges`, where the iterator `j1` points to the position past the last
369
+ copied or skipped element in \[`first1`, `last1`).
370
 
371
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
372
  comparisons and applications of each projection.
373
 
374
  *Remarks:* If \[`first1`, `last1`) contains m elements that are
 
420
  requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
421
  constexpr ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>,
422
  borrowed_iterator_t<R2>, O>
423
  ranges::set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
424
  Proj1 proj1 = {}, Proj2 proj2 = {});
425
+
426
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
427
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
428
+ random_access_iterator O, sized_sentinel_for<O> OutS, class Comp = ranges::less,
429
+ class Proj1 = identity, class Proj2 = identity>
430
+ requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
431
+ ranges::set_symmetric_difference_result<I1, I2, O>
432
+ ranges::set_symmetric_difference(Ep&& exec, I1 first1, S1 last1,
433
+ I2 first2, S2 last2, O result, OutS result_last,
434
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
435
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
436
+ sized-random-access-range OutR, class Comp = ranges::less,
437
+ class Proj1 = identity, class Proj2 = identity>
438
+ requires mergeable<iterator_t<R1>, iterator_t<R2>, iterator_t<OutR>, Comp, Proj1, Proj2>
439
+ ranges::set_symmetric_difference_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>,
440
+ borrowed_iterator_t<OutR>>
441
+ ranges::set_symmetric_difference(Ep&& exec, R1&& r1, R2&& r2, OutR&& result_r,
442
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
443
  ```
444
 
445
+ Let:
446
+
447
+ - `comp` be `less{}`, and `proj1` and `proj2` be `identity{}` for the
448
+ overloads with no parameters by those names;
449
+ - K be the number of elements in \[`first1`, `last1`) that are not
450
+ present in \[`first2`, `last2`).
451
+ - M be the number of elements in \[`first2`, `last2`) that are not
452
+ present in \[`first1`, `last1`).
453
+ - `result_last` be `result + `M` + `K for the overloads with no
454
+ parameter `result_last` or `result_r`;
455
+ - N be min(K + M, `result_last - result`).
456
 
457
  *Preconditions:* The ranges \[`first1`, `last1`) and \[`first2`,
458
  `last2`) are sorted with respect to `comp` and `proj1` or `proj2`,
459
  respectively. The resulting range does not overlap with either of the
460
  original ranges.
461
 
462
  *Effects:* Copies the elements of the range \[`first1`, `last1`) that
463
  are not present in the range \[`first2`, `last2`), and the elements of
464
  the range \[`first2`, `last2`) that are not present in the range
465
+ \[`first1`, `last1`) to the range \[`result`, `result + `N). The
466
+ elements in the constructed range are sorted.
467
 
468
+ *Returns:*
 
469
 
470
  - `result_last` for the overloads in namespace `std`.
471
+ - `{last1, last2, result + `N`}` for the overloads in namespace
472
+ `ranges`, if N is equal to M + K.
473
+ - Otherwise, `{j1, j2, result_last}` for the overloads in namespace
474
+ `ranges`, where the iterators `j1` and `j2` point to positions past
475
+ the last copied or skipped elements in \[`first1`, `last1`) and
476
+ \[`first2`, `last2`), respectively.
477
 
478
  *Complexity:* At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
479
  comparisons and applications of each projection.
480
 
481
  *Remarks:* Stable [[algorithm.stable]]. If \[`first1`, `last1`) contains