From Jason Turner

[alg.sort]

C++17 → C++20 17.0 KB 259 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpxbg5wlj2/{from.md → to.md} +192 -61
tmp/tmpxbg5wlj2/{from.md → to.md} RENAMED
@@ -2,33 +2,50 @@
2
 
3
  #### `sort` <a id="sort">[[sort]]</a>
4
 
5
  ``` cpp
6
  template<class RandomAccessIterator>
7
- void sort(RandomAccessIterator first, RandomAccessIterator last);
8
  template<class ExecutionPolicy, class RandomAccessIterator>
9
  void sort(ExecutionPolicy&& exec,
10
  RandomAccessIterator first, RandomAccessIterator last);
11
 
12
  template<class RandomAccessIterator, class Compare>
13
- void sort(RandomAccessIterator first, RandomAccessIterator last,
14
  Compare comp);
15
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
16
  void sort(ExecutionPolicy&& exec,
17
  RandomAccessIterator first, RandomAccessIterator last,
18
  Compare comp);
 
 
 
 
 
 
 
 
 
 
19
  ```
20
 
21
- *Requires:* `RandomAccessIterator` shall satisfy the requirements of
22
- `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
23
- shall satisfy the requirements of `MoveConstructible`
24
- (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
25
- (Table  [[tab:moveassignable]]).
26
 
27
- *Effects:* Sorts the elements in the range \[`first`, `last`).
 
 
 
 
28
 
29
- *Complexity:* 𝑂(N log N) comparisons, where N = `last - first`.
 
 
 
 
 
 
30
 
31
  #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
32
 
33
  ``` cpp
34
  template<class RandomAccessIterator>
@@ -42,70 +59,112 @@ template<class RandomAccessIterator, class Compare>
42
  Compare comp);
43
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
44
  void stable_sort(ExecutionPolicy&& exec,
45
  RandomAccessIterator first, RandomAccessIterator last,
46
  Compare comp);
 
 
 
 
 
 
 
 
 
47
  ```
48
 
49
- *Requires:* `RandomAccessIterator` shall satisfy the requirements of
50
- `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
51
- shall satisfy the requirements of `MoveConstructible`
52
- (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
53
- (Table  [[tab:moveassignable]]).
54
 
55
- *Effects:* Sorts the elements in the range \[`first`, `last`).
 
 
 
 
56
 
57
- *Complexity:* At most N log²(N) comparisons, where N = `last - first`,
58
- but only N log N comparisons if there is enough extra memory.
59
 
60
- *Remarks:* Stable ([[algorithm.stable]]).
 
 
 
 
 
 
 
61
 
62
  #### `partial_sort` <a id="partial.sort">[[partial.sort]]</a>
63
 
64
  ``` cpp
65
  template<class RandomAccessIterator>
66
- void partial_sort(RandomAccessIterator first,
67
  RandomAccessIterator middle,
68
  RandomAccessIterator last);
69
  template<class ExecutionPolicy, class RandomAccessIterator>
70
  void partial_sort(ExecutionPolicy&& exec,
71
  RandomAccessIterator first,
72
  RandomAccessIterator middle,
73
  RandomAccessIterator last);
74
 
75
  template<class RandomAccessIterator, class Compare>
76
- void partial_sort(RandomAccessIterator first,
77
  RandomAccessIterator middle,
78
  RandomAccessIterator last,
79
  Compare comp);
80
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
81
  void partial_sort(ExecutionPolicy&& exec,
82
  RandomAccessIterator first,
83
  RandomAccessIterator middle,
84
  RandomAccessIterator last,
85
  Compare comp);
 
 
 
 
 
 
86
  ```
87
 
88
- *Requires:* `RandomAccessIterator` shall satisfy the requirements of
89
- `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
90
- shall satisfy the requirements of `MoveConstructible`
91
- (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
92
- (Table  [[tab:moveassignable]]).
93
 
94
- *Effects:* Places the first `middle - first` sorted elements from the
95
- range \[`first`, `last`) into the range \[`first`, `middle`). The rest
96
- of the elements in the range \[`middle`, `last`) are placed in an
97
- unspecified order.
 
 
 
 
 
 
 
 
 
98
 
99
  *Complexity:* Approximately `(last - first) * log(middle - first)`
100
- comparisons.
 
 
 
 
 
 
 
 
 
 
 
 
 
101
 
102
  #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
103
 
104
  ``` cpp
105
  template<class InputIterator, class RandomAccessIterator>
106
- RandomAccessIterator
107
  partial_sort_copy(InputIterator first, InputIterator last,
108
  RandomAccessIterator result_first,
109
  RandomAccessIterator result_last);
110
  template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
111
  RandomAccessIterator
@@ -114,11 +173,11 @@ template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterato
114
  RandomAccessIterator result_first,
115
  RandomAccessIterator result_last);
116
 
117
  template<class InputIterator, class RandomAccessIterator,
118
  class Compare>
119
- RandomAccessIterator
120
  partial_sort_copy(InputIterator first, InputIterator last,
121
  RandomAccessIterator result_first,
122
  RandomAccessIterator result_last,
123
  Compare comp);
124
  template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
@@ -127,86 +186,158 @@ template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterato
127
  partial_sort_copy(ExecutionPolicy&& exec,
128
  ForwardIterator first, ForwardIterator last,
129
  RandomAccessIterator result_first,
130
  RandomAccessIterator result_last,
131
  Compare comp);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
132
  ```
133
 
134
- *Requires:* `RandomAccessIterator` shall satisfy the requirements of
135
- `ValueSwappable` ([[swappable.requirements]]). The type of
136
- `*result_first` shall satisfy the requirements of `MoveConstructible`
137
- (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
138
- (Table  [[tab:moveassignable]]).
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
139
 
140
- *Effects:* Places the first
141
- `min(last - first, result_last - result_first)` sorted elements into the
142
- range \[`result_first`,
143
- `result_first + min(last - first, result_last - result_first)`).
144
 
145
- *Returns:* The smaller of: `result_last` or
146
- `result_first + (last - first)`.
147
 
148
- *Complexity:* Approximately
149
- `(last - first) * log(min(last - first, result_last - result_first))`
150
- comparisons.
151
 
152
  #### `is_sorted` <a id="is.sorted">[[is.sorted]]</a>
153
 
154
  ``` cpp
155
  template<class ForwardIterator>
156
- bool is_sorted(ForwardIterator first, ForwardIterator last);
157
  ```
158
 
159
- *Returns:* `is_sorted_until(first, last) == last`
160
 
161
  ``` cpp
162
  template<class ExecutionPolicy, class ForwardIterator>
163
  bool is_sorted(ExecutionPolicy&& exec,
164
  ForwardIterator first, ForwardIterator last);
165
  ```
166
 
167
- *Returns:*
168
- `is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last) == last`
 
 
 
169
 
170
  ``` cpp
171
  template<class ForwardIterator, class Compare>
172
- bool is_sorted(ForwardIterator first, ForwardIterator last,
173
  Compare comp);
174
  ```
175
 
176
- *Returns:* `is_sorted_until(first, last, comp) == last`
 
177
 
178
  ``` cpp
179
  template<class ExecutionPolicy, class ForwardIterator, class Compare>
180
  bool is_sorted(ExecutionPolicy&& exec,
181
  ForwardIterator first, ForwardIterator last,
182
  Compare comp);
183
  ```
184
 
185
- *Returns:*
186
 
187
  ``` cpp
188
- is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last
189
  ```
190
 
 
 
 
 
 
 
 
 
 
 
 
 
191
  ``` cpp
192
  template<class ForwardIterator>
193
- ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
 
194
  template<class ExecutionPolicy, class ForwardIterator>
195
- ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
 
196
  ForwardIterator first, ForwardIterator last);
197
 
198
  template<class ForwardIterator, class Compare>
199
- ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
 
200
  Compare comp);
201
  template<class ExecutionPolicy, class ForwardIterator, class Compare>
202
- ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
 
203
  ForwardIterator first, ForwardIterator last,
204
  Compare comp);
 
 
 
 
 
 
 
 
205
  ```
206
 
207
- *Returns:* If `(last - first) < 2`, returns `last`. Otherwise, returns
208
- the last iterator `i` in \[`first`, `last`\] for which the range
209
- \[`first`, `i`) is sorted.
 
 
210
 
211
  *Complexity:* Linear.
212
 
 
2
 
3
  #### `sort` <a id="sort">[[sort]]</a>
4
 
5
  ``` cpp
6
  template<class RandomAccessIterator>
7
+ constexpr void sort(RandomAccessIterator first, RandomAccessIterator last);
8
  template<class ExecutionPolicy, class RandomAccessIterator>
9
  void sort(ExecutionPolicy&& exec,
10
  RandomAccessIterator first, RandomAccessIterator last);
11
 
12
  template<class RandomAccessIterator, class Compare>
13
+ constexpr void sort(RandomAccessIterator first, RandomAccessIterator last,
14
  Compare comp);
15
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
16
  void sort(ExecutionPolicy&& exec,
17
  RandomAccessIterator first, RandomAccessIterator last,
18
  Compare comp);
19
+
20
+ template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
21
+ class Proj = identity>
22
+ requires sortable<I, Comp, Proj>
23
+ constexpr I
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
 
34
+ *Preconditions:* For the overloads in namespace `std`,
35
+ `RandomAccessIterator` meets the *Cpp17ValueSwappable*
36
+ requirements [[swappable.requirements]] and the type of `*first` meets
37
+ the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
38
+ *Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
39
 
40
+ *Effects:* Sorts the elements in the range \[`first`, `last`) with
41
+ respect to `comp` and `proj`.
42
+
43
+ *Returns:* `last` for the overloads in namespace `ranges`.
44
+
45
+ *Complexity:* Let N be `last - first`. 𝑂(N log N) comparisons and
46
+ projections.
47
 
48
  #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
49
 
50
  ``` cpp
51
  template<class RandomAccessIterator>
 
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
 
78
+ *Preconditions:* For the overloads in namespace `std`,
79
+ `RandomAccessIterator` meets the *Cpp17ValueSwappable*
80
+ requirements [[swappable.requirements]] and the type of `*first` meets
81
+ the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
82
+ *Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
83
 
84
+ *Effects:* Sorts the elements in the range \[`first`, `last`) with
85
+ respect to `comp` and `proj`.
86
 
87
+ *Returns:* `last` for the overloads in namespace `ranges`.
88
+
89
+ *Complexity:* Let N be `last - first`. If enough extra memory is
90
+ available, N log(N) comparisons. Otherwise, at most N log²(N)
91
+ comparisons. In either case, twice as many projections as the number of
92
+ comparisons.
93
+
94
+ *Remarks:* Stable [[algorithm.stable]].
95
 
96
  #### `partial_sort` <a id="partial.sort">[[partial.sort]]</a>
97
 
98
  ``` cpp
99
  template<class RandomAccessIterator>
100
+ constexpr void partial_sort(RandomAccessIterator first,
101
  RandomAccessIterator middle,
102
  RandomAccessIterator last);
103
  template<class ExecutionPolicy, class RandomAccessIterator>
104
  void partial_sort(ExecutionPolicy&& exec,
105
  RandomAccessIterator first,
106
  RandomAccessIterator middle,
107
  RandomAccessIterator last);
108
 
109
  template<class RandomAccessIterator, class Compare>
110
+ constexpr void partial_sort(RandomAccessIterator first,
111
  RandomAccessIterator middle,
112
  RandomAccessIterator last,
113
  Compare comp);
114
  template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
115
  void partial_sort(ExecutionPolicy&& exec,
116
  RandomAccessIterator first,
117
  RandomAccessIterator middle,
118
  RandomAccessIterator last,
119
  Compare comp);
120
+
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
 
131
+ *Preconditions:* \[`first`, `middle`) and \[`middle`, `last`) are valid
132
+ ranges. For the overloads in namespace `std`, `RandomAccessIterator`
133
+ meets the *Cpp17ValueSwappable* requirements [[swappable.requirements]]
134
+ and the type of `*first` meets the *Cpp17MoveConstructible*
135
+ ([[cpp17.moveconstructible]]) and *Cpp17MoveAssignable*
136
+ ([[cpp17.moveassignable]]) requirements.
137
+
138
+ *Effects:* Places the first `middle - first` elements from the range
139
+ \[`first`, `last`) as sorted with respect to `comp` and `proj` into the
140
+ range \[`first`, `middle`). The rest of the elements in the range
141
+ \[`middle`, `last`) are placed in an unspecified order.
142
+
143
+ *Returns:* `last` for the overload in namespace `ranges`.
144
 
145
  *Complexity:* Approximately `(last - first) * log(middle - first)`
146
+ comparisons, and twice as many projections.
147
+
148
+ ``` cpp
149
+ template<random_access_range R, class Comp = ranges::less, class Proj = identity>
150
+ requires sortable<iterator_t<R>, Comp, Proj>
151
+ constexpr borrowed_iterator_t<R>
152
+ ranges::partial_sort(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});
153
+ ```
154
+
155
+ *Effects:* Equivalent to:
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
166
  partial_sort_copy(InputIterator first, InputIterator last,
167
  RandomAccessIterator result_first,
168
  RandomAccessIterator result_last);
169
  template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
170
  RandomAccessIterator
 
173
  RandomAccessIterator result_first,
174
  RandomAccessIterator result_last);
175
 
176
  template<class InputIterator, class RandomAccessIterator,
177
  class Compare>
178
+ constexpr RandomAccessIterator
179
  partial_sort_copy(InputIterator first, InputIterator last,
180
  RandomAccessIterator result_first,
181
  RandomAccessIterator result_last,
182
  Compare comp);
183
  template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
 
186
  partial_sort_copy(ExecutionPolicy&& exec,
187
  ForwardIterator first, ForwardIterator last,
188
  RandomAccessIterator result_first,
189
  RandomAccessIterator result_last,
190
  Compare comp);
191
+
192
+ template<input_iterator I1, sentinel_for<I1> S1, random_access_iterator I2, sentinel_for<I2> S2,
193
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
194
+ requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
195
+ indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
196
+ constexpr ranges::partial_sort_copy_result<I1, I2>
197
+ ranges::partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
198
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
199
+ template<input_range R1, random_access_range R2, class Comp = ranges::less,
200
+ class Proj1 = identity, class Proj2 = identity>
201
+ requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
202
+ sortable<iterator_t<R2>, Comp, Proj2> &&
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.
213
+
214
+ *Mandates:* For the overloads in namespace `std`, the expression
215
+ `*first` is writable [[iterator.requirements.general]] to
216
+ `result_first`.
217
+
218
+ *Preconditions:* For the overloads in namespace `std`,
219
+ `RandomAccessIterator` meets the *Cpp17ValueSwappable*
220
+ requirements [[swappable.requirements]], the type of `*result_first`
221
+ meets the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
222
+ *Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
223
+
224
+ *Preconditions:* For iterators `a1` and `b1` in \[`first`, `last`), and
225
+ iterators `x2` and `y2` in \[`result_first`, `result_last`), after
226
+ evaluating the assignment `*y2 = *b1`, let E be the value of
227
+
228
+ ``` cpp
229
+ bool(invoke(comp, invoke(proj1, *a1), invoke(proj2, *y2))).
230
+ ```
231
+
232
+ Then, after evaluating the assignment `*x2 = *a1`, E is equal to
233
+
234
+ ``` cpp
235
+ bool(invoke(comp, invoke(proj2, *x2), invoke(proj2, *y2))).
236
+ ```
237
+
238
+ [*Note 1*: Writing a value from the input range into the output range
239
+ does not affect how it is ordered by `comp` and `proj1` or
240
+ `proj2`. — *end note*]
241
+
242
+ *Effects:* Places the first N elements as sorted with respect to `comp`
243
+ and `proj2` into the range \[`result_first`, `result_first + `N).
244
 
245
+ *Returns:*
 
 
 
246
 
247
+ - `result_first + `N for the overloads in namespace `std`.
248
+ - `{last, result_first + `N`}` for the overloads in namespace `ranges`.
249
 
250
+ *Complexity:* Approximately `(last - first) * log `N comparisons, and
251
+ twice as many projections.
 
252
 
253
  #### `is_sorted` <a id="is.sorted">[[is.sorted]]</a>
254
 
255
  ``` cpp
256
  template<class ForwardIterator>
257
+ constexpr bool is_sorted(ForwardIterator first, ForwardIterator last);
258
  ```
259
 
260
+ *Effects:* Equivalent to: `return is_sorted_until(first, last) == last;`
261
 
262
  ``` cpp
263
  template<class ExecutionPolicy, class ForwardIterator>
264
  bool is_sorted(ExecutionPolicy&& exec,
265
  ForwardIterator first, ForwardIterator last);
266
  ```
267
 
268
+ *Effects:* Equivalent to:
269
+
270
+ ``` cpp
271
+ return is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last) == last;
272
+ ```
273
 
274
  ``` cpp
275
  template<class ForwardIterator, class Compare>
276
+ constexpr bool is_sorted(ForwardIterator first, ForwardIterator last,
277
  Compare comp);
278
  ```
279
 
280
+ *Effects:* Equivalent to:
281
+ `return is_sorted_until(first, last, comp) == last;`
282
 
283
  ``` cpp
284
  template<class ExecutionPolicy, class ForwardIterator, class Compare>
285
  bool is_sorted(ExecutionPolicy&& exec,
286
  ForwardIterator first, ForwardIterator last,
287
  Compare comp);
288
  ```
289
 
290
+ *Effects:* Equivalent to:
291
 
292
  ``` cpp
293
+ return is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last;
294
  ```
295
 
296
+ ``` cpp
297
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
298
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
299
+ constexpr bool ranges::is_sorted(I first, S last, Comp comp = {}, Proj proj = {});
300
+ template<forward_range R, class Proj = identity,
301
+ indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
302
+ constexpr bool ranges::is_sorted(R&& r, Comp comp = {}, Proj proj = {});
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>
313
+ ForwardIterator
314
+ is_sorted_until(ExecutionPolicy&& exec,
315
  ForwardIterator first, ForwardIterator last);
316
 
317
  template<class ForwardIterator, class Compare>
318
+ constexpr ForwardIterator
319
+ is_sorted_until(ForwardIterator first, ForwardIterator last,
320
  Compare comp);
321
  template<class ExecutionPolicy, class ForwardIterator, class Compare>
322
+ ForwardIterator
323
+ is_sorted_until(ExecutionPolicy&& exec,
324
  ForwardIterator first, ForwardIterator last,
325
  Compare comp);
326
+
327
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
328
+ indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
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
+
339
+ *Returns:* The last iterator `i` in \[`first`, `last`\] for which the
340
+ range \[`first`, `i`) is sorted with respect to `comp` and `proj`.
341
 
342
  *Complexity:* Linear.
343