From Jason Turner

[alg.sort]

C++23 → Trunk 9.0 KB 101 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/tmpfjs1sa1y/{from.md → to.md} +88 -4
tmp/tmpfjs1sa1y/{from.md → to.md} RENAMED
@@ -24,10 +24,19 @@ template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
24
  ranges::sort(I first, S last, Comp comp = {}, Proj proj = {});
25
  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
26
  requires sortable<iterator_t<R>, Comp, Proj>
27
  constexpr borrowed_iterator_t<R>
28
  ranges::sort(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
29
  ```
30
 
31
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
32
  no parameters by those names.
33
 
@@ -47,31 +56,41 @@ projections.
47
 
48
  #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
49
 
50
  ``` cpp
51
  template<class RandomAccessIterator>
52
- void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
53
  template<class ExecutionPolicy, class RandomAccessIterator>
54
  void stable_sort(ExecutionPolicy&& exec,
55
  RandomAccessIterator first, RandomAccessIterator last);
56
 
57
  template<class RandomAccessIterator, class Compare>
58
- void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
59
  Compare comp);
60
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
61
  void stable_sort(ExecutionPolicy&& exec,
62
  RandomAccessIterator first, RandomAccessIterator last,
63
  Compare comp);
64
 
65
  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
66
  class Proj = identity>
67
  requires sortable<I, Comp, Proj>
68
- I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {});
69
  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
70
  requires sortable<iterator_t<R>, Comp, Proj>
71
- borrowed_iterator_t<R>
72
  ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
73
  ```
74
 
75
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
76
  no parameters by those names.
77
 
@@ -121,10 +140,14 @@ template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
121
  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
122
  class Proj = identity>
123
  requires sortable<I, Comp, Proj>
124
  constexpr I
125
  ranges::partial_sort(I first, I middle, S last, Comp comp = {}, Proj proj = {});
 
 
 
 
126
  ```
127
 
128
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
129
  no parameters by those names.
130
 
@@ -156,10 +179,26 @@ template<random_access_range R, class Comp = ranges::less, class Proj = identity
156
 
157
  ``` cpp
158
  return ranges::partial_sort(ranges::begin(r), middle, ranges::end(r), comp, proj);
159
  ```
160
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
161
  #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
162
 
163
  ``` cpp
164
  template<class InputIterator, class RandomAccessIterator>
165
  constexpr RandomAccessIterator
@@ -203,10 +242,29 @@ template<input_range R1, random_access_range R2, class Comp = ranges::less,
203
  indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
204
  projected<iterator_t<R2>, Proj2>>
205
  constexpr ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
206
  ranges::partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
207
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
208
  ```
209
 
210
  Let N be min(`last - first`, `result_last - result_first`). Let `comp`
211
  be `less{}`, and `proj1` and `proj2` be `identity{}` for the overloads
212
  with no parameters by those names.
@@ -303,10 +361,26 @@ template<forward_range R, class Proj = identity,
303
  ```
304
 
305
  *Effects:* Equivalent to:
306
  `return ranges::is_sorted_until(first, last, comp, proj) == last;`
307
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
308
  ``` cpp
309
  template<class ForwardIterator>
310
  constexpr ForwardIterator
311
  is_sorted_until(ForwardIterator first, ForwardIterator last);
312
  template<class ExecutionPolicy, class ForwardIterator>
@@ -329,10 +403,20 @@ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
329
  constexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {});
330
  template<forward_range R, class Proj = identity,
331
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
332
  constexpr borrowed_iterator_t<R>
333
  ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
334
  ```
335
 
336
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
337
  no parameters by those names.
338
 
 
24
  ranges::sort(I first, S last, Comp comp = {}, Proj proj = {});
25
  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
26
  requires sortable<iterator_t<R>, Comp, Proj>
27
  constexpr borrowed_iterator_t<R>
28
  ranges::sort(R&& r, Comp comp = {}, Proj proj = {});
29
+
30
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
31
+ class Comp = ranges::less, class Proj = identity>
32
+ requires sortable<I, Comp, Proj>
33
+ I ranges::sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
34
+ template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less,
35
+ class Proj = identity>
36
+ requires sortable<iterator_t<R>, Comp, Proj>
37
+ borrowed_iterator_t<R> ranges::sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
38
  ```
39
 
40
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
41
  no parameters by those names.
42
 
 
56
 
57
  #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
58
 
59
  ``` cpp
60
  template<class RandomAccessIterator>
61
+ constexpr void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
62
  template<class ExecutionPolicy, class RandomAccessIterator>
63
  void stable_sort(ExecutionPolicy&& exec,
64
  RandomAccessIterator first, RandomAccessIterator last);
65
 
66
  template<class RandomAccessIterator, class Compare>
67
+ constexpr void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
68
  Compare comp);
69
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
70
  void stable_sort(ExecutionPolicy&& exec,
71
  RandomAccessIterator first, RandomAccessIterator last,
72
  Compare comp);
73
 
74
  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
75
  class Proj = identity>
76
  requires sortable<I, Comp, Proj>
77
+ constexpr I ranges::stable_sort(I first, S last, Comp comp = {}, Proj proj = {});
78
  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
79
  requires sortable<iterator_t<R>, Comp, Proj>
80
+ constexpr borrowed_iterator_t<R>
81
  ranges::stable_sort(R&& r, Comp comp = {}, Proj proj = {});
82
+
83
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
84
+ class Comp = ranges::less, class Proj = identity>
85
+ requires sortable<I, Comp, Proj>
86
+ I ranges::stable_sort(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
87
+ template<execution-policy Ep, sized-random-access-range R, class Comp = ranges::less,
88
+ class Proj = identity>
89
+ requires sortable<iterator_t<R>, Comp, Proj>
90
+ borrowed_iterator_t<R>
91
+ ranges::stable_sort(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
92
  ```
93
 
94
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
95
  no parameters by those names.
96
 
 
140
  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
141
  class Proj = identity>
142
  requires sortable<I, Comp, Proj>
143
  constexpr I
144
  ranges::partial_sort(I first, I middle, S last, Comp comp = {}, Proj proj = {});
145
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
146
+ class Comp = ranges::less, class Proj = identity>
147
+ requires sortable<I, Comp, Proj>
148
+ I ranges::partial_sort(Ep&& exec, I first, I middle, S last, Comp comp = {}, Proj proj = {});
149
  ```
150
 
151
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
152
  no parameters by those names.
153
 
 
179
 
180
  ``` cpp
181
  return ranges::partial_sort(ranges::begin(r), middle, ranges::end(r), comp, proj);
182
  ```
183
 
184
+ ``` cpp
185
+ template<execution-policy Ep, sized-random-access-range R,
186
+ class Comp = ranges::less, class Proj = identity>
187
+ requires sortable<iterator_t<R>, Comp, Proj>
188
+ borrowed_iterator_t<R>
189
+ ranges::partial_sort(Ep&& exec, R&& r, iterator_t<R> middle, Comp comp = {},
190
+ Proj proj = {});
191
+ ```
192
+
193
+ *Effects:* Equivalent to:
194
+
195
+ ``` cpp
196
+ return ranges::partial_sort(std::forward<Ep>(exec), ranges::begin(r), middle,
197
+ ranges::end(r), comp, proj);
198
+ ```
199
+
200
  #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
201
 
202
  ``` cpp
203
  template<class InputIterator, class RandomAccessIterator>
204
  constexpr RandomAccessIterator
 
242
  indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
243
  projected<iterator_t<R2>, Proj2>>
244
  constexpr ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
245
  ranges::partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
246
  Proj1 proj1 = {}, Proj2 proj2 = {});
247
+
248
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
249
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
250
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
251
+ requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
252
+ indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
253
+ ranges::partial_sort_copy_result<I1, I2>
254
+ ranges::partial_sort_copy(Ep&& exec, I1 first, S1 last, I2 result_first, S2 result_last,
255
+ Comp comp = {}, Proj1 proj1 = {},
256
+ Proj2 proj2 = {});
257
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
258
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
259
+ requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
260
+ sortable<iterator_t<R2>, Comp, Proj2> &&
261
+ indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
262
+ projected<iterator_t<R2>, Proj2>>
263
+ ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
264
+ ranges::partial_sort_copy(Ep&& exec, R1&& r, R2&& result_r, Comp comp = {},
265
+ Proj1 proj1 = {}, Proj2 proj2 = {});
266
  ```
267
 
268
  Let N be min(`last - first`, `result_last - result_first`). Let `comp`
269
  be `less{}`, and `proj1` and `proj2` be `identity{}` for the overloads
270
  with no parameters by those names.
 
361
  ```
362
 
363
  *Effects:* Equivalent to:
364
  `return ranges::is_sorted_until(first, last, comp, proj) == last;`
365
 
366
+ ``` cpp
367
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
368
+ class Proj = identity,
369
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
370
+ bool ranges::is_sorted(Ep&& exec, I first, S last, Comp comp = {}, Proj proj = {});
371
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
372
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
373
+ bool ranges::is_sorted(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
374
+ ```
375
+
376
+ *Effects:* Equivalent to:
377
+
378
+ ``` cpp
379
+ return ranges::is_sorted_until(std::forward<Ep>(exec), first, last, comp, proj) == last;
380
+ ```
381
+
382
  ``` cpp
383
  template<class ForwardIterator>
384
  constexpr ForwardIterator
385
  is_sorted_until(ForwardIterator first, ForwardIterator last);
386
  template<class ExecutionPolicy, class ForwardIterator>
 
403
  constexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {});
404
  template<forward_range R, class Proj = identity,
405
  indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
406
  constexpr borrowed_iterator_t<R>
407
  ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {});
408
+
409
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
410
+ class Proj = identity,
411
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
412
+ I ranges::is_sorted_until(Ep&& exec, I first, S last, Comp comp = {},
413
+ Proj proj = {});
414
+ template<execution-policy Ep, sized-random-access-range R, class Proj = identity,
415
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
416
+ borrowed_iterator_t<R>
417
+ ranges::is_sorted_until(Ep&& exec, R&& r, Comp comp = {}, Proj proj = {});
418
  ```
419
 
420
  Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
421
  no parameters by those names.
422