1 // Core algorithmic facilities -*- C++ -*-
2
3 // Copyright (C) 2020 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /** @file bits/ranges_algo.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{algorithm}
28 */
29
30 #ifndef _RANGES_ALGO_H
31 #define _RANGES_ALGO_H 1
32
33 #if __cplusplus > 201703L
34
35 #include <bits/ranges_algobase.h>
36 #include <bits/uniform_int_dist.h> // concept uniform_random_bit_generator
37
38 #if __cpp_lib_concepts
_GLIBCXX_VISIBILITY(default)39 namespace std _GLIBCXX_VISIBILITY(default)
40 {
41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
42 namespace ranges
43 {
44 namespace __detail
45 {
46 template<typename _Comp, typename _Proj>
47 constexpr auto
48 __make_comp_proj(_Comp& __comp, _Proj& __proj)
49 {
50 return [&] (auto&& __lhs, auto&& __rhs) -> bool {
51 using _TL = decltype(__lhs);
52 using _TR = decltype(__rhs);
53 return std::__invoke(__comp,
54 std::__invoke(__proj, std::forward<_TL>(__lhs)),
55 std::__invoke(__proj, std::forward<_TR>(__rhs)));
56 };
57 }
58
59 template<typename _Pred, typename _Proj>
60 constexpr auto
61 __make_pred_proj(_Pred& __pred, _Proj& __proj)
62 {
63 return [&] <typename _Tp> (_Tp&& __arg) -> bool {
64 return std::__invoke(__pred,
65 std::__invoke(__proj, std::forward<_Tp>(__arg)));
66 };
67 }
68 } // namespace __detail
69
70 struct __all_of_fn
71 {
72 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
73 typename _Proj = identity,
74 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
75 constexpr bool
76 operator()(_Iter __first, _Sent __last,
77 _Pred __pred, _Proj __proj = {}) const
78 {
79 for (; __first != __last; ++__first)
80 if (!(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
81 return false;
82 return true;
83 }
84
85 template<input_range _Range, typename _Proj = identity,
86 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
87 _Pred>
88 constexpr bool
89 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
90 {
91 return (*this)(ranges::begin(__r), ranges::end(__r),
92 std::move(__pred), std::move(__proj));
93 }
94 };
95
96 inline constexpr __all_of_fn all_of{};
97
98 struct __any_of_fn
99 {
100 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
101 typename _Proj = identity,
102 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
103 constexpr bool
104 operator()(_Iter __first, _Sent __last,
105 _Pred __pred, _Proj __proj = {}) const
106 {
107 for (; __first != __last; ++__first)
108 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
109 return true;
110 return false;
111 }
112
113 template<input_range _Range, typename _Proj = identity,
114 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
115 _Pred>
116 constexpr bool
117 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
118 {
119 return (*this)(ranges::begin(__r), ranges::end(__r),
120 std::move(__pred), std::move(__proj));
121 }
122 };
123
124 inline constexpr __any_of_fn any_of{};
125
126 struct __none_of_fn
127 {
128 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
129 typename _Proj = identity,
130 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
131 constexpr bool
132 operator()(_Iter __first, _Sent __last,
133 _Pred __pred, _Proj __proj = {}) const
134 {
135 for (; __first != __last; ++__first)
136 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
137 return false;
138 return true;
139 }
140
141 template<input_range _Range, typename _Proj = identity,
142 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
143 _Pred>
144 constexpr bool
145 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
146 {
147 return (*this)(ranges::begin(__r), ranges::end(__r),
148 std::move(__pred), std::move(__proj));
149 }
150 };
151
152 inline constexpr __none_of_fn none_of{};
153
154 template<typename _Iter, typename _Fp>
155 struct in_fun_result
156 {
157 [[no_unique_address]] _Iter in;
158 [[no_unique_address]] _Fp fun;
159
160 template<typename _Iter2, typename _F2p>
161 requires convertible_to<const _Iter&, _Iter2>
162 && convertible_to<const _Fp&, _F2p>
163 constexpr
164 operator in_fun_result<_Iter2, _F2p>() const &
165 { return {in, fun}; }
166
167 template<typename _Iter2, typename _F2p>
168 requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
169 constexpr
170 operator in_fun_result<_Iter2, _F2p>() &&
171 { return {std::move(in), std::move(fun)}; }
172 };
173
174 template<typename _Iter, typename _Fp>
175 using for_each_result = in_fun_result<_Iter, _Fp>;
176
177 struct __for_each_fn
178 {
179 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
180 typename _Proj = identity,
181 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
182 constexpr for_each_result<_Iter, _Fun>
183 operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {}) const
184 {
185 for (; __first != __last; ++__first)
186 std::__invoke(__f, std::__invoke(__proj, *__first));
187 return { std::move(__first), std::move(__f) };
188 }
189
190 template<input_range _Range, typename _Proj = identity,
191 indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
192 _Fun>
193 constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun>
194 operator()(_Range&& __r, _Fun __f, _Proj __proj = {}) const
195 {
196 return (*this)(ranges::begin(__r), ranges::end(__r),
197 std::move(__f), std::move(__proj));
198 }
199 };
200
201 inline constexpr __for_each_fn for_each{};
202
203 template<typename _Iter, typename _Fp>
204 using for_each_n_result = in_fun_result<_Iter, _Fp>;
205
206 struct __for_each_n_fn
207 {
208 template<input_iterator _Iter, typename _Proj = identity,
209 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
210 constexpr for_each_n_result<_Iter, _Fun>
211 operator()(_Iter __first, iter_difference_t<_Iter> __n,
212 _Fun __f, _Proj __proj = {}) const
213 {
214 if constexpr (random_access_iterator<_Iter>)
215 {
216 if (__n <= 0)
217 return {std::move(__first), std::move(__f)};
218 auto __last = __first + __n;
219 return ranges::for_each(std::move(__first), std::move(__last),
220 std::move(__f), std::move(__proj));
221 }
222 else
223 {
224 while (__n-- > 0)
225 {
226 std::__invoke(__f, std::__invoke(__proj, *__first));
227 ++__first;
228 }
229 return {std::move(__first), std::move(__f)};
230 }
231 }
232 };
233
234 inline constexpr __for_each_n_fn for_each_n{};
235
236 struct __find_fn
237 {
238 template<input_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
239 typename _Proj = identity>
240 requires indirect_binary_predicate<ranges::equal_to,
241 projected<_Iter, _Proj>, const _Tp*>
242 constexpr _Iter
243 operator()(_Iter __first, _Sent __last,
244 const _Tp& __value, _Proj __proj = {}) const
245 {
246 while (__first != __last
247 && !(std::__invoke(__proj, *__first) == __value))
248 ++__first;
249 return __first;
250 }
251
252 template<input_range _Range, typename _Tp, typename _Proj = identity>
253 requires indirect_binary_predicate<ranges::equal_to,
254 projected<iterator_t<_Range>, _Proj>,
255 const _Tp*>
256 constexpr borrowed_iterator_t<_Range>
257 operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
258 {
259 return (*this)(ranges::begin(__r), ranges::end(__r),
260 __value, std::move(__proj));
261 }
262 };
263
264 inline constexpr __find_fn find{};
265
266 struct __find_if_fn
267 {
268 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
269 typename _Proj = identity,
270 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
271 constexpr _Iter
272 operator()(_Iter __first, _Sent __last,
273 _Pred __pred, _Proj __proj = {}) const
274 {
275 while (__first != __last
276 && !(bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
277 ++__first;
278 return __first;
279 }
280
281 template<input_range _Range, typename _Proj = identity,
282 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
283 _Pred>
284 constexpr borrowed_iterator_t<_Range>
285 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
286 {
287 return (*this)(ranges::begin(__r), ranges::end(__r),
288 std::move(__pred), std::move(__proj));
289 }
290 };
291
292 inline constexpr __find_if_fn find_if{};
293
294 struct __find_if_not_fn
295 {
296 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
297 typename _Proj = identity,
298 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
299 constexpr _Iter
300 operator()(_Iter __first, _Sent __last,
301 _Pred __pred, _Proj __proj = {}) const
302 {
303 while (__first != __last
304 && (bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
305 ++__first;
306 return __first;
307 }
308
309 template<input_range _Range, typename _Proj = identity,
310 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
311 _Pred>
312 constexpr borrowed_iterator_t<_Range>
313 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
314 {
315 return (*this)(ranges::begin(__r), ranges::end(__r),
316 std::move(__pred), std::move(__proj));
317 }
318 };
319
320 inline constexpr __find_if_not_fn find_if_not{};
321
322 struct __find_first_of_fn
323 {
324 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
325 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
326 typename _Pred = ranges::equal_to,
327 typename _Proj1 = identity, typename _Proj2 = identity>
328 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
329 constexpr _Iter1
330 operator()(_Iter1 __first1, _Sent1 __last1,
331 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
332 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
333 {
334 for (; __first1 != __last1; ++__first1)
335 for (auto __iter = __first2; __iter != __last2; ++__iter)
336 if (std::__invoke(__pred,
337 std::__invoke(__proj1, *__first1),
338 std::__invoke(__proj2, *__iter)))
339 return __first1;
340 return __first1;
341 }
342
343 template<input_range _Range1, forward_range _Range2,
344 typename _Pred = ranges::equal_to,
345 typename _Proj1 = identity, typename _Proj2 = identity>
346 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
347 _Pred, _Proj1, _Proj2>
348 constexpr borrowed_iterator_t<_Range1>
349 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
350 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
351 {
352 return (*this)(ranges::begin(__r1), ranges::end(__r1),
353 ranges::begin(__r2), ranges::end(__r2),
354 std::move(__pred),
355 std::move(__proj1), std::move(__proj2));
356 }
357 };
358
359 inline constexpr __find_first_of_fn find_first_of{};
360
361 struct __count_fn
362 {
363 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
364 typename _Tp, typename _Proj = identity>
365 requires indirect_binary_predicate<ranges::equal_to,
366 projected<_Iter, _Proj>,
367 const _Tp*>
368 constexpr iter_difference_t<_Iter>
369 operator()(_Iter __first, _Sent __last,
370 const _Tp& __value, _Proj __proj = {}) const
371 {
372 iter_difference_t<_Iter> __n = 0;
373 for (; __first != __last; ++__first)
374 if (std::__invoke(__proj, *__first) == __value)
375 ++__n;
376 return __n;
377 }
378
379 template<input_range _Range, typename _Tp, typename _Proj = identity>
380 requires indirect_binary_predicate<ranges::equal_to,
381 projected<iterator_t<_Range>, _Proj>,
382 const _Tp*>
383 constexpr range_difference_t<_Range>
384 operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
385 {
386 return (*this)(ranges::begin(__r), ranges::end(__r),
387 __value, std::move(__proj));
388 }
389 };
390
391 inline constexpr __count_fn count{};
392
393 struct __count_if_fn
394 {
395 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
396 typename _Proj = identity,
397 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
398 constexpr iter_difference_t<_Iter>
399 operator()(_Iter __first, _Sent __last,
400 _Pred __pred, _Proj __proj = {}) const
401 {
402 iter_difference_t<_Iter> __n = 0;
403 for (; __first != __last; ++__first)
404 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
405 ++__n;
406 return __n;
407 }
408
409 template<input_range _Range,
410 typename _Proj = identity,
411 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
412 _Pred>
413 constexpr range_difference_t<_Range>
414 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
415 {
416 return (*this)(ranges::begin(__r), ranges::end(__r),
417 std::move(__pred), std::move(__proj));
418 }
419 };
420
421 inline constexpr __count_if_fn count_if{};
422
423 template<typename _Iter1, typename _Iter2>
424 struct in_in_result
425 {
426 [[no_unique_address]] _Iter1 in1;
427 [[no_unique_address]] _Iter2 in2;
428
429 template<typename _IIter1, typename _IIter2>
430 requires convertible_to<const _Iter1&, _IIter1>
431 && convertible_to<const _Iter2&, _IIter2>
432 constexpr
433 operator in_in_result<_IIter1, _IIter2>() const &
434 { return {in1, in2}; }
435
436 template<typename _IIter1, typename _IIter2>
437 requires convertible_to<_Iter1, _IIter1>
438 && convertible_to<_Iter2, _IIter2>
439 constexpr
440 operator in_in_result<_IIter1, _IIter2>() &&
441 { return {std::move(in1), std::move(in2)}; }
442 };
443
444 template<typename _Iter1, typename _Iter2>
445 using mismatch_result = in_in_result<_Iter1, _Iter2>;
446
447 struct __mismatch_fn
448 {
449 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
450 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
451 typename _Pred = ranges::equal_to,
452 typename _Proj1 = identity, typename _Proj2 = identity>
453 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
454 constexpr mismatch_result<_Iter1, _Iter2>
455 operator()(_Iter1 __first1, _Sent1 __last1,
456 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
457 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
458 {
459 while (__first1 != __last1 && __first2 != __last2
460 && (bool)std::__invoke(__pred,
461 std::__invoke(__proj1, *__first1),
462 std::__invoke(__proj2, *__first2)))
463 {
464 ++__first1;
465 ++__first2;
466 }
467 return { std::move(__first1), std::move(__first2) };
468 }
469
470 template<input_range _Range1, input_range _Range2,
471 typename _Pred = ranges::equal_to,
472 typename _Proj1 = identity, typename _Proj2 = identity>
473 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
474 _Pred, _Proj1, _Proj2>
475 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
476 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
477 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
478 {
479 return (*this)(ranges::begin(__r1), ranges::end(__r1),
480 ranges::begin(__r2), ranges::end(__r2),
481 std::move(__pred),
482 std::move(__proj1), std::move(__proj2));
483 }
484 };
485
486 inline constexpr __mismatch_fn mismatch{};
487
488 struct __search_fn
489 {
490 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
491 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
492 typename _Pred = ranges::equal_to,
493 typename _Proj1 = identity, typename _Proj2 = identity>
494 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
495 constexpr subrange<_Iter1>
496 operator()(_Iter1 __first1, _Sent1 __last1,
497 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
498 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
499 {
500 if (__first1 == __last1 || __first2 == __last2)
501 return {__first1, __first1};
502
503 for (;;)
504 {
505 for (;;)
506 {
507 if (__first1 == __last1)
508 return {__first1, __first1};
509 if (std::__invoke(__pred,
510 std::__invoke(__proj1, *__first1),
511 std::__invoke(__proj2, *__first2)))
512 break;
513 ++__first1;
514 }
515 auto __cur1 = __first1;
516 auto __cur2 = __first2;
517 for (;;)
518 {
519 if (++__cur2 == __last2)
520 return {__first1, ++__cur1};
521 if (++__cur1 == __last1)
522 return {__cur1, __cur1};
523 if (!(bool)std::__invoke(__pred,
524 std::__invoke(__proj1, *__cur1),
525 std::__invoke(__proj2, *__cur2)))
526 {
527 ++__first1;
528 break;
529 }
530 }
531 }
532 }
533
534 template<forward_range _Range1, forward_range _Range2,
535 typename _Pred = ranges::equal_to,
536 typename _Proj1 = identity, typename _Proj2 = identity>
537 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
538 _Pred, _Proj1, _Proj2>
539 constexpr borrowed_subrange_t<_Range1>
540 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
541 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
542 {
543 return (*this)(ranges::begin(__r1), ranges::end(__r1),
544 ranges::begin(__r2), ranges::end(__r2),
545 std::move(__pred),
546 std::move(__proj1), std::move(__proj2));
547 }
548 };
549
550 inline constexpr __search_fn search{};
551
552 struct __search_n_fn
553 {
554 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Tp,
555 typename _Pred = ranges::equal_to, typename _Proj = identity>
556 requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
557 constexpr subrange<_Iter>
558 operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
559 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
560 {
561 if (__count <= 0)
562 return {__first, __first};
563
564 auto __value_comp = [&] <typename _Rp> (_Rp&& __arg) -> bool {
565 return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
566 };
567 if (__count == 1)
568 {
569 __first = ranges::find_if(std::move(__first), __last,
570 std::move(__value_comp),
571 std::move(__proj));
572 if (__first == __last)
573 return {__first, __first};
574 else
575 {
576 auto __end = __first;
577 return {__first, ++__end};
578 }
579 }
580
581 if constexpr (sized_sentinel_for<_Sent, _Iter>
582 && random_access_iterator<_Iter>)
583 {
584 auto __tail_size = __last - __first;
585 auto __remainder = __count;
586
587 while (__remainder <= __tail_size)
588 {
589 __first += __remainder;
590 __tail_size -= __remainder;
591 auto __backtrack = __first;
592 while (__value_comp(std::__invoke(__proj, *--__backtrack)))
593 {
594 if (--__remainder == 0)
595 return {__first - __count, __first};
596 }
597 __remainder = __count + 1 - (__first - __backtrack);
598 }
599 auto __i = __first + __tail_size;
600 return {__i, __i};
601 }
602 else
603 {
604 __first = ranges::find_if(__first, __last, __value_comp, __proj);
605 while (__first != __last)
606 {
607 auto __n = __count;
608 auto __i = __first;
609 ++__i;
610 while (__i != __last && __n != 1
611 && __value_comp(std::__invoke(__proj, *__i)))
612 {
613 ++__i;
614 --__n;
615 }
616 if (__n == 1)
617 return {__first, __i};
618 if (__i == __last)
619 return {__i, __i};
620 __first = ranges::find_if(++__i, __last, __value_comp, __proj);
621 }
622 return {__first, __first};
623 }
624 }
625
626 template<forward_range _Range, typename _Tp,
627 typename _Pred = ranges::equal_to, typename _Proj = identity>
628 requires indirectly_comparable<iterator_t<_Range>, const _Tp*,
629 _Pred, _Proj>
630 constexpr borrowed_subrange_t<_Range>
631 operator()(_Range&& __r, range_difference_t<_Range> __count,
632 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {}) const
633 {
634 return (*this)(ranges::begin(__r), ranges::end(__r),
635 std::move(__count), __value,
636 std::move(__pred), std::move(__proj));
637 }
638 };
639
640 inline constexpr __search_n_fn search_n{};
641
642 struct __find_end_fn
643 {
644 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
645 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
646 typename _Pred = ranges::equal_to,
647 typename _Proj1 = identity, typename _Proj2 = identity>
648 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
649 constexpr subrange<_Iter1>
650 operator()(_Iter1 __first1, _Sent1 __last1,
651 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
652 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
653 {
654 if constexpr (bidirectional_iterator<_Iter1>
655 && bidirectional_iterator<_Iter2>)
656 {
657 auto __i1 = ranges::next(__first1, __last1);
658 auto __i2 = ranges::next(__first2, __last2);
659 auto __rresult
660 = ranges::search(reverse_iterator<_Iter1>{__i1},
661 reverse_iterator<_Iter1>{__first1},
662 reverse_iterator<_Iter2>{__i2},
663 reverse_iterator<_Iter2>{__first2},
664 std::move(__pred),
665 std::move(__proj1), std::move(__proj2));
666 auto __result_first = ranges::end(__rresult).base();
667 auto __result_last = ranges::begin(__rresult).base();
668 if (__result_last == __first1)
669 return {__i1, __i1};
670 else
671 return {__result_first, __result_last};
672 }
673 else
674 {
675 auto __i = ranges::next(__first1, __last1);
676 if (__first2 == __last2)
677 return {__i, __i};
678
679 auto __result_begin = __i;
680 auto __result_end = __i;
681 for (;;)
682 {
683 auto __new_range = ranges::search(__first1, __last1,
684 __first2, __last2,
685 __pred, __proj1, __proj2);
686 auto __new_result_begin = ranges::begin(__new_range);
687 auto __new_result_end = ranges::end(__new_range);
688 if (__new_result_begin == __last1)
689 return {__result_begin, __result_end};
690 else
691 {
692 __result_begin = __new_result_begin;
693 __result_end = __new_result_end;
694 __first1 = __result_begin;
695 ++__first1;
696 }
697 }
698 }
699 }
700
701 template<forward_range _Range1, forward_range _Range2,
702 typename _Pred = ranges::equal_to,
703 typename _Proj1 = identity, typename _Proj2 = identity>
704 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
705 _Pred, _Proj1, _Proj2>
706 constexpr borrowed_subrange_t<_Range1>
707 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
708 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
709 {
710 return (*this)(ranges::begin(__r1), ranges::end(__r1),
711 ranges::begin(__r2), ranges::end(__r2),
712 std::move(__pred),
713 std::move(__proj1), std::move(__proj2));
714 }
715 };
716
717 inline constexpr __find_end_fn find_end{};
718
719 struct __adjacent_find_fn
720 {
721 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
722 typename _Proj = identity,
723 indirect_binary_predicate<projected<_Iter, _Proj>,
724 projected<_Iter, _Proj>> _Pred
725 = ranges::equal_to>
726 constexpr _Iter
727 operator()(_Iter __first, _Sent __last,
728 _Pred __pred = {}, _Proj __proj = {}) const
729 {
730 if (__first == __last)
731 return __first;
732 auto __next = __first;
733 for (; ++__next != __last; __first = __next)
734 {
735 if (std::__invoke(__pred,
736 std::__invoke(__proj, *__first),
737 std::__invoke(__proj, *__next)))
738 return __first;
739 }
740 return __next;
741 }
742
743 template<forward_range _Range, typename _Proj = identity,
744 indirect_binary_predicate<
745 projected<iterator_t<_Range>, _Proj>,
746 projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
747 constexpr borrowed_iterator_t<_Range>
748 operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {}) const
749 {
750 return (*this)(ranges::begin(__r), ranges::end(__r),
751 std::move(__pred), std::move(__proj));
752 }
753 };
754
755 inline constexpr __adjacent_find_fn adjacent_find{};
756
757 struct __is_permutation_fn
758 {
759 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
760 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
761 typename _Proj1 = identity, typename _Proj2 = identity,
762 indirect_equivalence_relation<projected<_Iter1, _Proj1>,
763 projected<_Iter2, _Proj2>> _Pred
764 = ranges::equal_to>
765 constexpr bool
766 operator()(_Iter1 __first1, _Sent1 __last1,
767 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
768 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
769 {
770 constexpr bool __sized_iters
771 = (sized_sentinel_for<_Sent1, _Iter1>
772 && sized_sentinel_for<_Sent2, _Iter2>);
773 if constexpr (__sized_iters)
774 {
775 auto __d1 = ranges::distance(__first1, __last1);
776 auto __d2 = ranges::distance(__first2, __last2);
777 if (__d1 != __d2)
778 return false;
779 }
780
781 // Efficiently compare identical prefixes: O(N) if sequences
782 // have the same elements in the same order.
783 for (; __first1 != __last1 && __first2 != __last2;
784 ++__first1, (void)++__first2)
785 if (!(bool)std::__invoke(__pred,
786 std::__invoke(__proj1, *__first1),
787 std::__invoke(__proj2, *__first2)))
788 break;
789
790 if constexpr (__sized_iters)
791 {
792 if (__first1 == __last1)
793 return true;
794 }
795 else
796 {
797 auto __d1 = ranges::distance(__first1, __last1);
798 auto __d2 = ranges::distance(__first2, __last2);
799 if (__d1 == 0 && __d2 == 0)
800 return true;
801 if (__d1 != __d2)
802 return false;
803 }
804
805 for (auto __scan = __first1; __scan != __last1; ++__scan)
806 {
807 auto&& __proj_scan = std::__invoke(__proj1, *__scan);
808 auto __comp_scan = [&] <typename _Tp> (_Tp&& __arg) -> bool {
809 return std::__invoke(__pred, __proj_scan,
810 std::forward<_Tp>(__arg));
811 };
812 if (__scan != ranges::find_if(__first1, __scan,
813 __comp_scan, __proj1))
814 continue; // We've seen this one before.
815
816 auto __matches = ranges::count_if(__first2, __last2,
817 __comp_scan, __proj2);
818 if (__matches == 0
819 || ranges::count_if(__scan, __last1,
820 __comp_scan, __proj1) != __matches)
821 return false;
822 }
823 return true;
824 }
825
826 template<forward_range _Range1, forward_range _Range2,
827 typename _Proj1 = identity, typename _Proj2 = identity,
828 indirect_equivalence_relation<
829 projected<iterator_t<_Range1>, _Proj1>,
830 projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
831 constexpr bool
832 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
833 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
834 {
835 return (*this)(ranges::begin(__r1), ranges::end(__r1),
836 ranges::begin(__r2), ranges::end(__r2),
837 std::move(__pred),
838 std::move(__proj1), std::move(__proj2));
839 }
840 };
841
842 inline constexpr __is_permutation_fn is_permutation{};
843
844 template<typename _Iter, typename _Out>
845 using copy_if_result = in_out_result<_Iter, _Out>;
846
847 struct __copy_if_fn
848 {
849 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
850 weakly_incrementable _Out, typename _Proj = identity,
851 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
852 requires indirectly_copyable<_Iter, _Out>
853 constexpr copy_if_result<_Iter, _Out>
854 operator()(_Iter __first, _Sent __last, _Out __result,
855 _Pred __pred, _Proj __proj = {}) const
856 {
857 for (; __first != __last; ++__first)
858 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
859 {
860 *__result = *__first;
861 ++__result;
862 }
863 return {std::move(__first), std::move(__result)};
864 }
865
866 template<input_range _Range, weakly_incrementable _Out,
867 typename _Proj = identity,
868 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
869 _Pred>
870 requires indirectly_copyable<iterator_t<_Range>, _Out>
871 constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
872 operator()(_Range&& __r, _Out __result,
873 _Pred __pred, _Proj __proj = {}) const
874 {
875 return (*this)(ranges::begin(__r), ranges::end(__r),
876 std::move(__result),
877 std::move(__pred), std::move(__proj));
878 }
879 };
880
881 inline constexpr __copy_if_fn copy_if{};
882
883 template<typename _Iter1, typename _Iter2>
884 using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
885
886 struct __swap_ranges_fn
887 {
888 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
889 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
890 requires indirectly_swappable<_Iter1, _Iter2>
891 constexpr swap_ranges_result<_Iter1, _Iter2>
892 operator()(_Iter1 __first1, _Sent1 __last1,
893 _Iter2 __first2, _Sent2 __last2) const
894 {
895 for (; __first1 != __last1 && __first2 != __last2;
896 ++__first1, (void)++__first2)
897 ranges::iter_swap(__first1, __first2);
898 return {std::move(__first1), std::move(__first2)};
899 }
900
901 template<input_range _Range1, input_range _Range2>
902 requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
903 constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
904 borrowed_iterator_t<_Range2>>
905 operator()(_Range1&& __r1, _Range2&& __r2) const
906 {
907 return (*this)(ranges::begin(__r1), ranges::end(__r1),
908 ranges::begin(__r2), ranges::end(__r2));
909 }
910 };
911
912 inline constexpr __swap_ranges_fn swap_ranges{};
913
914 template<typename _Iter, typename _Out>
915 using unary_transform_result = in_out_result<_Iter, _Out>;
916
917 template<typename _Iter1, typename _Iter2, typename _Out>
918 struct in_in_out_result
919 {
920 [[no_unique_address]] _Iter1 in1;
921 [[no_unique_address]] _Iter2 in2;
922 [[no_unique_address]] _Out out;
923
924 template<typename _IIter1, typename _IIter2, typename _OOut>
925 requires convertible_to<const _Iter1&, _IIter1>
926 && convertible_to<const _Iter2&, _IIter2>
927 && convertible_to<const _Out&, _OOut>
928 constexpr
929 operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
930 { return {in1, in2, out}; }
931
932 template<typename _IIter1, typename _IIter2, typename _OOut>
933 requires convertible_to<_Iter1, _IIter1>
934 && convertible_to<_Iter2, _IIter2>
935 && convertible_to<_Out, _OOut>
936 constexpr
937 operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
938 { return {std::move(in1), std::move(in2), std::move(out)}; }
939 };
940
941 template<typename _Iter1, typename _Iter2, typename _Out>
942 using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
943
944 struct __transform_fn
945 {
946 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
947 weakly_incrementable _Out,
948 copy_constructible _Fp, typename _Proj = identity>
949 requires indirectly_writable<_Out,
950 indirect_result_t<_Fp&,
951 projected<_Iter, _Proj>>>
952 constexpr unary_transform_result<_Iter, _Out>
953 operator()(_Iter __first1, _Sent __last1, _Out __result,
954 _Fp __op, _Proj __proj = {}) const
955 {
956 for (; __first1 != __last1; ++__first1, (void)++__result)
957 *__result = std::__invoke(__op, std::__invoke(__proj, *__first1));
958 return {std::move(__first1), std::move(__result)};
959 }
960
961 template<input_range _Range, weakly_incrementable _Out,
962 copy_constructible _Fp, typename _Proj = identity>
963 requires indirectly_writable<_Out,
964 indirect_result_t<_Fp&,
965 projected<iterator_t<_Range>, _Proj>>>
966 constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
967 operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {}) const
968 {
969 return (*this)(ranges::begin(__r), ranges::end(__r),
970 std::move(__result),
971 std::move(__op), std::move(__proj));
972 }
973
974 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
975 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
976 weakly_incrementable _Out, copy_constructible _Fp,
977 typename _Proj1 = identity, typename _Proj2 = identity>
978 requires indirectly_writable<_Out,
979 indirect_result_t<_Fp&,
980 projected<_Iter1, _Proj1>,
981 projected<_Iter2, _Proj2>>>
982 constexpr binary_transform_result<_Iter1, _Iter2, _Out>
983 operator()(_Iter1 __first1, _Sent1 __last1,
984 _Iter2 __first2, _Sent2 __last2,
985 _Out __result, _Fp __binary_op,
986 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
987 {
988 for (; __first1 != __last1 && __first2 != __last2;
989 ++__first1, (void)++__first2, ++__result)
990 *__result = std::__invoke(__binary_op,
991 std::__invoke(__proj1, *__first1),
992 std::__invoke(__proj2, *__first2));
993 return {std::move(__first1), std::move(__first2), std::move(__result)};
994 }
995
996 template<input_range _Range1, input_range _Range2,
997 weakly_incrementable _Out, copy_constructible _Fp,
998 typename _Proj1 = identity, typename _Proj2 = identity>
999 requires indirectly_writable<_Out,
1000 indirect_result_t<_Fp&,
1001 projected<iterator_t<_Range1>, _Proj1>,
1002 projected<iterator_t<_Range2>, _Proj2>>>
1003 constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
1004 borrowed_iterator_t<_Range2>, _Out>
1005 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
1006 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
1007 {
1008 return (*this)(ranges::begin(__r1), ranges::end(__r1),
1009 ranges::begin(__r2), ranges::end(__r2),
1010 std::move(__result), std::move(__binary_op),
1011 std::move(__proj1), std::move(__proj2));
1012 }
1013 };
1014
1015 inline constexpr __transform_fn transform{};
1016
1017 struct __replace_fn
1018 {
1019 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1020 typename _Tp1, typename _Tp2, typename _Proj = identity>
1021 requires indirectly_writable<_Iter, const _Tp2&>
1022 && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
1023 const _Tp1*>
1024 constexpr _Iter
1025 operator()(_Iter __first, _Sent __last,
1026 const _Tp1& __old_value, const _Tp2& __new_value,
1027 _Proj __proj = {}) const
1028 {
1029 for (; __first != __last; ++__first)
1030 if (std::__invoke(__proj, *__first) == __old_value)
1031 *__first = __new_value;
1032 return __first;
1033 }
1034
1035 template<input_range _Range,
1036 typename _Tp1, typename _Tp2, typename _Proj = identity>
1037 requires indirectly_writable<iterator_t<_Range>, const _Tp2&>
1038 && indirect_binary_predicate<ranges::equal_to,
1039 projected<iterator_t<_Range>, _Proj>,
1040 const _Tp1*>
1041 constexpr borrowed_iterator_t<_Range>
1042 operator()(_Range&& __r,
1043 const _Tp1& __old_value, const _Tp2& __new_value,
1044 _Proj __proj = {}) const
1045 {
1046 return (*this)(ranges::begin(__r), ranges::end(__r),
1047 __old_value, __new_value, std::move(__proj));
1048 }
1049 };
1050
1051 inline constexpr __replace_fn replace{};
1052
1053 struct __replace_if_fn
1054 {
1055 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1056 typename _Tp, typename _Proj = identity,
1057 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1058 requires indirectly_writable<_Iter, const _Tp&>
1059 constexpr _Iter
1060 operator()(_Iter __first, _Sent __last,
1061 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
1062 {
1063 for (; __first != __last; ++__first)
1064 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
1065 *__first = __new_value;
1066 return std::move(__first);
1067 }
1068
1069 template<input_range _Range, typename _Tp, typename _Proj = identity,
1070 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1071 _Pred>
1072 requires indirectly_writable<iterator_t<_Range>, const _Tp&>
1073 constexpr borrowed_iterator_t<_Range>
1074 operator()(_Range&& __r,
1075 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
1076 {
1077 return (*this)(ranges::begin(__r), ranges::end(__r),
1078 std::move(__pred), __new_value, std::move(__proj));
1079 }
1080 };
1081
1082 inline constexpr __replace_if_fn replace_if{};
1083
1084 template<typename _Iter, typename _Out>
1085 using replace_copy_result = in_out_result<_Iter, _Out>;
1086
1087 struct __replace_copy_fn
1088 {
1089 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1090 typename _Tp1, typename _Tp2, output_iterator<const _Tp2&> _Out,
1091 typename _Proj = identity>
1092 requires indirectly_copyable<_Iter, _Out>
1093 && indirect_binary_predicate<ranges::equal_to,
1094 projected<_Iter, _Proj>, const _Tp1*>
1095 constexpr replace_copy_result<_Iter, _Out>
1096 operator()(_Iter __first, _Sent __last, _Out __result,
1097 const _Tp1& __old_value, const _Tp2& __new_value,
1098 _Proj __proj = {}) const
1099 {
1100 for (; __first != __last; ++__first, (void)++__result)
1101 if (std::__invoke(__proj, *__first) == __old_value)
1102 *__result = __new_value;
1103 else
1104 *__result = *__first;
1105 return {std::move(__first), std::move(__result)};
1106 }
1107
1108 template<input_range _Range, typename _Tp1, typename _Tp2,
1109 output_iterator<const _Tp2&> _Out, typename _Proj = identity>
1110 requires indirectly_copyable<iterator_t<_Range>, _Out>
1111 && indirect_binary_predicate<ranges::equal_to,
1112 projected<iterator_t<_Range>, _Proj>,
1113 const _Tp1*>
1114 constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
1115 operator()(_Range&& __r, _Out __result,
1116 const _Tp1& __old_value, const _Tp2& __new_value,
1117 _Proj __proj = {}) const
1118 {
1119 return (*this)(ranges::begin(__r), ranges::end(__r),
1120 std::move(__result), __old_value,
1121 __new_value, std::move(__proj));
1122 }
1123 };
1124
1125 inline constexpr __replace_copy_fn replace_copy{};
1126
1127 template<typename _Iter, typename _Out>
1128 using replace_copy_if_result = in_out_result<_Iter, _Out>;
1129
1130 struct __replace_copy_if_fn
1131 {
1132 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1133 typename _Tp, output_iterator<const _Tp&> _Out,
1134 typename _Proj = identity,
1135 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1136 requires indirectly_copyable<_Iter, _Out>
1137 constexpr replace_copy_if_result<_Iter, _Out>
1138 operator()(_Iter __first, _Sent __last, _Out __result,
1139 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
1140 {
1141 for (; __first != __last; ++__first, (void)++__result)
1142 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
1143 *__result = __new_value;
1144 else
1145 *__result = *__first;
1146 return {std::move(__first), std::move(__result)};
1147 }
1148
1149 template<input_range _Range,
1150 typename _Tp, output_iterator<const _Tp&> _Out,
1151 typename _Proj = identity,
1152 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1153 _Pred>
1154 requires indirectly_copyable<iterator_t<_Range>, _Out>
1155 constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1156 operator()(_Range&& __r, _Out __result,
1157 _Pred __pred, const _Tp& __new_value, _Proj __proj = {}) const
1158 {
1159 return (*this)(ranges::begin(__r), ranges::end(__r),
1160 std::move(__result), std::move(__pred),
1161 __new_value, std::move(__proj));
1162 }
1163 };
1164
1165 inline constexpr __replace_copy_if_fn replace_copy_if{};
1166
1167 struct __generate_n_fn
1168 {
1169 template<input_or_output_iterator _Out, copy_constructible _Fp>
1170 requires invocable<_Fp&>
1171 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
1172 constexpr _Out
1173 operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen) const
1174 {
1175 for (; __n > 0; --__n, (void)++__first)
1176 *__first = std::__invoke(__gen);
1177 return __first;
1178 }
1179 };
1180
1181 inline constexpr __generate_n_fn generate_n{};
1182
1183 struct __generate_fn
1184 {
1185 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
1186 copy_constructible _Fp>
1187 requires invocable<_Fp&>
1188 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
1189 constexpr _Out
1190 operator()(_Out __first, _Sent __last, _Fp __gen) const
1191 {
1192 for (; __first != __last; ++__first)
1193 *__first = std::__invoke(__gen);
1194 return __first;
1195 }
1196
1197 template<typename _Range, copy_constructible _Fp>
1198 requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
1199 constexpr borrowed_iterator_t<_Range>
1200 operator()(_Range&& __r, _Fp __gen) const
1201 {
1202 return (*this)(ranges::begin(__r), ranges::end(__r), std::move(__gen));
1203 }
1204 };
1205
1206 inline constexpr __generate_fn generate{};
1207
1208 struct __remove_if_fn
1209 {
1210 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1211 typename _Proj = identity,
1212 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1213 constexpr subrange<_Iter>
1214 operator()(_Iter __first, _Sent __last,
1215 _Pred __pred, _Proj __proj = {}) const
1216 {
1217 __first = ranges::find_if(__first, __last, __pred, __proj);
1218 if (__first == __last)
1219 return {__first, __first};
1220
1221 auto __result = __first;
1222 ++__first;
1223 for (; __first != __last; ++__first)
1224 if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
1225 {
1226 *__result = std::move(*__first);
1227 ++__result;
1228 }
1229
1230 return {__result, __first};
1231 }
1232
1233 template<forward_range _Range, typename _Proj = identity,
1234 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1235 _Pred>
1236 requires permutable<iterator_t<_Range>>
1237 constexpr borrowed_subrange_t<_Range>
1238 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
1239 {
1240 return (*this)(ranges::begin(__r), ranges::end(__r),
1241 std::move(__pred), std::move(__proj));
1242 }
1243 };
1244
1245 inline constexpr __remove_if_fn remove_if{};
1246
1247 struct __remove_fn
1248 {
1249 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1250 typename _Tp, typename _Proj = identity>
1251 requires indirect_binary_predicate<ranges::equal_to,
1252 projected<_Iter, _Proj>,
1253 const _Tp*>
1254 constexpr subrange<_Iter>
1255 operator()(_Iter __first, _Sent __last,
1256 const _Tp& __value, _Proj __proj = {}) const
1257 {
1258 auto __pred = [&] (auto&& __arg) -> bool {
1259 return std::forward<decltype(__arg)>(__arg) == __value;
1260 };
1261 return ranges::remove_if(__first, __last,
1262 std::move(__pred), std::move(__proj));
1263 }
1264
1265 template<forward_range _Range, typename _Tp, typename _Proj = identity>
1266 requires permutable<iterator_t<_Range>>
1267 && indirect_binary_predicate<ranges::equal_to,
1268 projected<iterator_t<_Range>, _Proj>,
1269 const _Tp*>
1270 constexpr borrowed_subrange_t<_Range>
1271 operator()(_Range&& __r, const _Tp& __value, _Proj __proj = {}) const
1272 {
1273 return (*this)(ranges::begin(__r), ranges::end(__r),
1274 __value, std::move(__proj));
1275 }
1276 };
1277
1278 inline constexpr __remove_fn remove{};
1279
1280 template<typename _Iter, typename _Out>
1281 using remove_copy_if_result = in_out_result<_Iter, _Out>;
1282
1283 struct __remove_copy_if_fn
1284 {
1285 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1286 weakly_incrementable _Out, typename _Proj = identity,
1287 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1288 requires indirectly_copyable<_Iter, _Out>
1289 constexpr remove_copy_if_result<_Iter, _Out>
1290 operator()(_Iter __first, _Sent __last, _Out __result,
1291 _Pred __pred, _Proj __proj = {}) const
1292 {
1293 for (; __first != __last; ++__first)
1294 if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
1295 {
1296 *__result = *__first;
1297 ++__result;
1298 }
1299 return {std::move(__first), std::move(__result)};
1300 }
1301
1302 template<input_range _Range, weakly_incrementable _Out,
1303 typename _Proj = identity,
1304 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1305 _Pred>
1306 requires indirectly_copyable<iterator_t<_Range>, _Out>
1307 constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1308 operator()(_Range&& __r, _Out __result,
1309 _Pred __pred, _Proj __proj = {}) const
1310 {
1311 return (*this)(ranges::begin(__r), ranges::end(__r),
1312 std::move(__result),
1313 std::move(__pred), std::move(__proj));
1314 }
1315 };
1316
1317 inline constexpr __remove_copy_if_fn remove_copy_if{};
1318
1319 template<typename _Iter, typename _Out>
1320 using remove_copy_result = in_out_result<_Iter, _Out>;
1321
1322 struct __remove_copy_fn
1323 {
1324 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1325 weakly_incrementable _Out, typename _Tp, typename _Proj = identity>
1326 requires indirectly_copyable<_Iter, _Out>
1327 && indirect_binary_predicate<ranges::equal_to,
1328 projected<_Iter, _Proj>,
1329 const _Tp*>
1330 constexpr remove_copy_result<_Iter, _Out>
1331 operator()(_Iter __first, _Sent __last, _Out __result,
1332 const _Tp& __value, _Proj __proj = {}) const
1333 {
1334 for (; __first != __last; ++__first)
1335 if (!(std::__invoke(__proj, *__first) == __value))
1336 {
1337 *__result = *__first;
1338 ++__result;
1339 }
1340 return {std::move(__first), std::move(__result)};
1341 }
1342
1343 template<input_range _Range, weakly_incrementable _Out,
1344 typename _Tp, typename _Proj = identity>
1345 requires indirectly_copyable<iterator_t<_Range>, _Out>
1346 && indirect_binary_predicate<ranges::equal_to,
1347 projected<iterator_t<_Range>, _Proj>,
1348 const _Tp*>
1349 constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
1350 operator()(_Range&& __r, _Out __result,
1351 const _Tp& __value, _Proj __proj = {}) const
1352 {
1353 return (*this)(ranges::begin(__r), ranges::end(__r),
1354 std::move(__result), __value, std::move(__proj));
1355 }
1356 };
1357
1358 inline constexpr __remove_copy_fn remove_copy{};
1359
1360 struct __unique_fn
1361 {
1362 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1363 typename _Proj = identity,
1364 indirect_equivalence_relation<
1365 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1366 constexpr subrange<_Iter>
1367 operator()(_Iter __first, _Sent __last,
1368 _Comp __comp = {}, _Proj __proj = {}) const
1369 {
1370 __first = ranges::adjacent_find(__first, __last, __comp, __proj);
1371 if (__first == __last)
1372 return {__first, __first};
1373
1374 auto __dest = __first;
1375 ++__first;
1376 while (++__first != __last)
1377 if (!std::__invoke(__comp,
1378 std::__invoke(__proj, *__dest),
1379 std::__invoke(__proj, *__first)))
1380 *++__dest = std::move(*__first);
1381 return {++__dest, __first};
1382 }
1383
1384 template<forward_range _Range, typename _Proj = identity,
1385 indirect_equivalence_relation<
1386 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1387 requires permutable<iterator_t<_Range>>
1388 constexpr borrowed_subrange_t<_Range>
1389 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1390 {
1391 return (*this)(ranges::begin(__r), ranges::end(__r),
1392 std::move(__comp), std::move(__proj));
1393 }
1394 };
1395
1396 inline constexpr __unique_fn unique{};
1397
1398 namespace __detail
1399 {
1400 template<typename _Out, typename _Tp>
1401 concept __can_reread_output = input_iterator<_Out>
1402 && same_as<_Tp, iter_value_t<_Out>>;
1403 }
1404
1405 template<typename _Iter, typename _Out>
1406 using unique_copy_result = in_out_result<_Iter, _Out>;
1407
1408 struct __unique_copy_fn
1409 {
1410 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1411 weakly_incrementable _Out, typename _Proj = identity,
1412 indirect_equivalence_relation<
1413 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1414 requires indirectly_copyable<_Iter, _Out>
1415 && (forward_iterator<_Iter>
1416 || __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
1417 || indirectly_copyable_storable<_Iter, _Out>)
1418 constexpr unique_copy_result<_Iter, _Out>
1419 operator()(_Iter __first, _Sent __last, _Out __result,
1420 _Comp __comp = {}, _Proj __proj = {}) const
1421 {
1422 if (__first == __last)
1423 return {std::move(__first), std::move(__result)};
1424
1425 // TODO: perform a closer comparison with reference implementations
1426 if constexpr (forward_iterator<_Iter>)
1427 {
1428 auto __next = __first;
1429 *__result = *__next;
1430 while (++__next != __last)
1431 if (!std::__invoke(__comp,
1432 std::__invoke(__proj, *__first),
1433 std::__invoke(__proj, *__next)))
1434 {
1435 __first = __next;
1436 *++__result = *__first;
1437 }
1438 return {__next, std::move(++__result)};
1439 }
1440 else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
1441 {
1442 *__result = *__first;
1443 while (++__first != __last)
1444 if (!std::__invoke(__comp,
1445 std::__invoke(__proj, *__result),
1446 std::__invoke(__proj, *__first)))
1447 *++__result = *__first;
1448 return {std::move(__first), std::move(++__result)};
1449 }
1450 else // indirectly_copyable_storable<_Iter, _Out>
1451 {
1452 auto __value = *__first;
1453 *__result = __value;
1454 while (++__first != __last)
1455 {
1456 if (!(bool)std::__invoke(__comp,
1457 std::__invoke(__proj, *__first),
1458 std::__invoke(__proj, __value)))
1459 {
1460 __value = *__first;
1461 *++__result = __value;
1462 }
1463 }
1464 return {std::move(__first), std::move(++__result)};
1465 }
1466 }
1467
1468 template<input_range _Range,
1469 weakly_incrementable _Out, typename _Proj = identity,
1470 indirect_equivalence_relation<
1471 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1472 requires indirectly_copyable<iterator_t<_Range>, _Out>
1473 && (forward_iterator<iterator_t<_Range>>
1474 || __detail::__can_reread_output<_Out, range_value_t<_Range>>
1475 || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1476 constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1477 operator()(_Range&& __r, _Out __result,
1478 _Comp __comp = {}, _Proj __proj = {}) const
1479 {
1480 return (*this)(ranges::begin(__r), ranges::end(__r),
1481 std::move(__result),
1482 std::move(__comp), std::move(__proj));
1483 }
1484 };
1485
1486 inline constexpr __unique_copy_fn unique_copy{};
1487
1488 struct __reverse_fn
1489 {
1490 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1491 requires permutable<_Iter>
1492 constexpr _Iter
1493 operator()(_Iter __first, _Sent __last) const
1494 {
1495 auto __i = ranges::next(__first, __last);
1496 auto __tail = __i;
1497
1498 if constexpr (random_access_iterator<_Iter>)
1499 {
1500 if (__first != __last)
1501 {
1502 --__tail;
1503 while (__first < __tail)
1504 {
1505 ranges::iter_swap(__first, __tail);
1506 ++__first;
1507 --__tail;
1508 }
1509 }
1510 return __i;
1511 }
1512 else
1513 {
1514 for (;;)
1515 if (__first == __tail || __first == --__tail)
1516 break;
1517 else
1518 {
1519 ranges::iter_swap(__first, __tail);
1520 ++__first;
1521 }
1522 return __i;
1523 }
1524 }
1525
1526 template<bidirectional_range _Range>
1527 requires permutable<iterator_t<_Range>>
1528 constexpr borrowed_iterator_t<_Range>
1529 operator()(_Range&& __r) const
1530 {
1531 return (*this)(ranges::begin(__r), ranges::end(__r));
1532 }
1533 };
1534
1535 inline constexpr __reverse_fn reverse{};
1536
1537 template<typename _Iter, typename _Out>
1538 using reverse_copy_result = in_out_result<_Iter, _Out>;
1539
1540 struct __reverse_copy_fn
1541 {
1542 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1543 weakly_incrementable _Out>
1544 requires indirectly_copyable<_Iter, _Out>
1545 constexpr reverse_copy_result<_Iter, _Out>
1546 operator()(_Iter __first, _Sent __last, _Out __result) const
1547 {
1548 auto __i = ranges::next(__first, __last);
1549 auto __tail = __i;
1550 while (__first != __tail)
1551 {
1552 --__tail;
1553 *__result = *__tail;
1554 ++__result;
1555 }
1556 return {__i, std::move(__result)};
1557 }
1558
1559 template<bidirectional_range _Range, weakly_incrementable _Out>
1560 requires indirectly_copyable<iterator_t<_Range>, _Out>
1561 constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1562 operator()(_Range&& __r, _Out __result) const
1563 {
1564 return (*this)(ranges::begin(__r), ranges::end(__r),
1565 std::move(__result));
1566 }
1567 };
1568
1569 inline constexpr __reverse_copy_fn reverse_copy{};
1570
1571 struct __rotate_fn
1572 {
1573 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1574 constexpr subrange<_Iter>
1575 operator()(_Iter __first, _Iter __middle, _Sent __last) const
1576 {
1577 auto __lasti = ranges::next(__first, __last);
1578 if (__first == __middle)
1579 return {__lasti, __lasti};
1580 if (__last == __middle)
1581 return {std::move(__first), std::move(__lasti)};
1582
1583 if constexpr (random_access_iterator<_Iter>)
1584 {
1585 auto __n = __lasti - __first;
1586 auto __k = __middle - __first;
1587
1588 if (__k == __n - __k)
1589 {
1590 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1591 return {std::move(__middle), std::move(__lasti)};
1592 }
1593
1594 auto __p = __first;
1595 auto __ret = __first + (__lasti - __middle);
1596
1597 for (;;)
1598 {
1599 if (__k < __n - __k)
1600 {
1601 // TODO: is_pod is deprecated, but this condition is
1602 // consistent with the STL implementation.
1603 if constexpr (__is_pod(iter_value_t<_Iter>))
1604 if (__k == 1)
1605 {
1606 auto __t = std::move(*__p);
1607 ranges::move(__p + 1, __p + __n, __p);
1608 *(__p + __n - 1) = std::move(__t);
1609 return {std::move(__ret), std::move(__lasti)};
1610 }
1611 auto __q = __p + __k;
1612 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1613 {
1614 ranges::iter_swap(__p, __q);
1615 ++__p;
1616 ++__q;
1617 }
1618 __n %= __k;
1619 if (__n == 0)
1620 return {std::move(__ret), std::move(__lasti)};
1621 ranges::swap(__n, __k);
1622 __k = __n - __k;
1623 }
1624 else
1625 {
1626 __k = __n - __k;
1627 // TODO: is_pod is deprecated, but this condition is
1628 // consistent with the STL implementation.
1629 if constexpr (__is_pod(iter_value_t<_Iter>))
1630 if (__k == 1)
1631 {
1632 auto __t = std::move(*(__p + __n - 1));
1633 ranges::move_backward(__p, __p + __n - 1, __p + __n);
1634 *__p = std::move(__t);
1635 return {std::move(__ret), std::move(__lasti)};
1636 }
1637 auto __q = __p + __n;
1638 __p = __q - __k;
1639 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1640 {
1641 --__p;
1642 --__q;
1643 ranges::iter_swap(__p, __q);
1644 }
1645 __n %= __k;
1646 if (__n == 0)
1647 return {std::move(__ret), std::move(__lasti)};
1648 std::swap(__n, __k);
1649 }
1650 }
1651 }
1652 else if constexpr (bidirectional_iterator<_Iter>)
1653 {
1654 auto __tail = __lasti;
1655
1656 ranges::reverse(__first, __middle);
1657 ranges::reverse(__middle, __tail);
1658
1659 while (__first != __middle && __middle != __tail)
1660 {
1661 ranges::iter_swap(__first, --__tail);
1662 ++__first;
1663 }
1664
1665 if (__first == __middle)
1666 {
1667 ranges::reverse(__middle, __tail);
1668 return {std::move(__tail), std::move(__lasti)};
1669 }
1670 else
1671 {
1672 ranges::reverse(__first, __middle);
1673 return {std::move(__first), std::move(__lasti)};
1674 }
1675 }
1676 else
1677 {
1678 auto __first2 = __middle;
1679 do
1680 {
1681 ranges::iter_swap(__first, __first2);
1682 ++__first;
1683 ++__first2;
1684 if (__first == __middle)
1685 __middle = __first2;
1686 } while (__first2 != __last);
1687
1688 auto __ret = __first;
1689
1690 __first2 = __middle;
1691
1692 while (__first2 != __last)
1693 {
1694 ranges::iter_swap(__first, __first2);
1695 ++__first;
1696 ++__first2;
1697 if (__first == __middle)
1698 __middle = __first2;
1699 else if (__first2 == __last)
1700 __first2 = __middle;
1701 }
1702 return {std::move(__ret), std::move(__lasti)};
1703 }
1704 }
1705
1706 template<forward_range _Range>
1707 requires permutable<iterator_t<_Range>>
1708 constexpr borrowed_subrange_t<_Range>
1709 operator()(_Range&& __r, iterator_t<_Range> __middle) const
1710 {
1711 return (*this)(ranges::begin(__r), std::move(__middle),
1712 ranges::end(__r));
1713 }
1714 };
1715
1716 inline constexpr __rotate_fn rotate{};
1717
1718 template<typename _Iter, typename _Out>
1719 using rotate_copy_result = in_out_result<_Iter, _Out>;
1720
1721 struct __rotate_copy_fn
1722 {
1723 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1724 weakly_incrementable _Out>
1725 requires indirectly_copyable<_Iter, _Out>
1726 constexpr rotate_copy_result<_Iter, _Out>
1727 operator()(_Iter __first, _Iter __middle, _Sent __last,
1728 _Out __result) const
1729 {
1730 auto __copy1 = ranges::copy(__middle,
1731 std::move(__last),
1732 std::move(__result));
1733 auto __copy2 = ranges::copy(std::move(__first),
1734 std::move(__middle),
1735 std::move(__copy1.out));
1736 return { std::move(__copy1.in), std::move(__copy2.out) };
1737 }
1738
1739 template<forward_range _Range, weakly_incrementable _Out>
1740 requires indirectly_copyable<iterator_t<_Range>, _Out>
1741 constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1742 operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result) const
1743 {
1744 return (*this)(ranges::begin(__r), std::move(__middle),
1745 ranges::end(__r), std::move(__result));
1746 }
1747 };
1748
1749 inline constexpr __rotate_copy_fn rotate_copy{};
1750
1751 struct __sample_fn
1752 {
1753 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1754 weakly_incrementable _Out, typename _Gen>
1755 requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
1756 && indirectly_copyable<_Iter, _Out>
1757 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1758 _Out
1759 operator()(_Iter __first, _Sent __last, _Out __out,
1760 iter_difference_t<_Iter> __n, _Gen&& __g) const
1761 {
1762 if constexpr (forward_iterator<_Iter>)
1763 {
1764 // FIXME: Forwarding to std::sample here requires computing __lasti
1765 // which may take linear time.
1766 auto __lasti = ranges::next(__first, __last);
1767 return std::sample(std::move(__first), std::move(__lasti),
1768 std::move(__out), __n, std::forward<_Gen>(__g));
1769 }
1770 else
1771 {
1772 using __distrib_type
1773 = uniform_int_distribution<iter_difference_t<_Iter>>;
1774 using __param_type = typename __distrib_type::param_type;
1775 __distrib_type __d{};
1776 iter_difference_t<_Iter> __sample_sz = 0;
1777 while (__first != __last && __sample_sz != __n)
1778 {
1779 __out[__sample_sz++] = *__first;
1780 ++__first;
1781 }
1782 for (auto __pop_sz = __sample_sz; __first != __last;
1783 ++__first, (void) ++__pop_sz)
1784 {
1785 const auto __k = __d(__g, __param_type{0, __pop_sz});
1786 if (__k < __n)
1787 __out[__k] = *__first;
1788 }
1789 return __out + __sample_sz;
1790 }
1791 }
1792
1793 template<input_range _Range, weakly_incrementable _Out, typename _Gen>
1794 requires (forward_range<_Range> || random_access_iterator<_Out>)
1795 && indirectly_copyable<iterator_t<_Range>, _Out>
1796 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1797 _Out
1798 operator()(_Range&& __r, _Out __out,
1799 range_difference_t<_Range> __n, _Gen&& __g) const
1800 {
1801 return (*this)(ranges::begin(__r), ranges::end(__r),
1802 std::move(__out), __n,
1803 std::forward<_Gen>(__g));
1804 }
1805 };
1806
1807 inline constexpr __sample_fn sample{};
1808
1809 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
1810 struct __shuffle_fn
1811 {
1812 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1813 typename _Gen>
1814 requires permutable<_Iter>
1815 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1816 _Iter
1817 operator()(_Iter __first, _Sent __last, _Gen&& __g) const
1818 {
1819 auto __lasti = ranges::next(__first, __last);
1820 std::shuffle(std::move(__first), __lasti, std::forward<_Gen>(__g));
1821 return __lasti;
1822 }
1823
1824 template<random_access_range _Range, typename _Gen>
1825 requires permutable<iterator_t<_Range>>
1826 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1827 borrowed_iterator_t<_Range>
1828 operator()(_Range&& __r, _Gen&& __g) const
1829 {
1830 return (*this)(ranges::begin(__r), ranges::end(__r),
1831 std::forward<_Gen>(__g));
1832 }
1833 };
1834
1835 inline constexpr __shuffle_fn shuffle{};
1836 #endif
1837
1838 struct __push_heap_fn
1839 {
1840 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1841 typename _Comp = ranges::less, typename _Proj = identity>
1842 requires sortable<_Iter, _Comp, _Proj>
1843 constexpr _Iter
1844 operator()(_Iter __first, _Sent __last,
1845 _Comp __comp = {}, _Proj __proj = {}) const
1846 {
1847 auto __lasti = ranges::next(__first, __last);
1848 std::push_heap(__first, __lasti,
1849 __detail::__make_comp_proj(__comp, __proj));
1850 return __lasti;
1851 }
1852
1853 template<random_access_range _Range,
1854 typename _Comp = ranges::less, typename _Proj = identity>
1855 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1856 constexpr borrowed_iterator_t<_Range>
1857 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1858 {
1859 return (*this)(ranges::begin(__r), ranges::end(__r),
1860 std::move(__comp), std::move(__proj));
1861 }
1862 };
1863
1864 inline constexpr __push_heap_fn push_heap{};
1865
1866 struct __pop_heap_fn
1867 {
1868 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1869 typename _Comp = ranges::less, typename _Proj = identity>
1870 requires sortable<_Iter, _Comp, _Proj>
1871 constexpr _Iter
1872 operator()(_Iter __first, _Sent __last,
1873 _Comp __comp = {}, _Proj __proj = {}) const
1874 {
1875 auto __lasti = ranges::next(__first, __last);
1876 std::pop_heap(__first, __lasti,
1877 __detail::__make_comp_proj(__comp, __proj));
1878 return __lasti;
1879 }
1880
1881 template<random_access_range _Range,
1882 typename _Comp = ranges::less, typename _Proj = identity>
1883 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1884 constexpr borrowed_iterator_t<_Range>
1885 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1886 {
1887 return (*this)(ranges::begin(__r), ranges::end(__r),
1888 std::move(__comp), std::move(__proj));
1889 }
1890 };
1891
1892 inline constexpr __pop_heap_fn pop_heap{};
1893
1894 struct __make_heap_fn
1895 {
1896 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1897 typename _Comp = ranges::less, typename _Proj = identity>
1898 requires sortable<_Iter, _Comp, _Proj>
1899 constexpr _Iter
1900 operator()(_Iter __first, _Sent __last,
1901 _Comp __comp = {}, _Proj __proj = {}) const
1902 {
1903 auto __lasti = ranges::next(__first, __last);
1904 std::make_heap(__first, __lasti,
1905 __detail::__make_comp_proj(__comp, __proj));
1906 return __lasti;
1907 }
1908
1909 template<random_access_range _Range,
1910 typename _Comp = ranges::less, typename _Proj = identity>
1911 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1912 constexpr borrowed_iterator_t<_Range>
1913 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1914 {
1915 return (*this)(ranges::begin(__r), ranges::end(__r),
1916 std::move(__comp), std::move(__proj));
1917 }
1918 };
1919
1920 inline constexpr __make_heap_fn make_heap{};
1921
1922 struct __sort_heap_fn
1923 {
1924 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1925 typename _Comp = ranges::less, typename _Proj = identity>
1926 requires sortable<_Iter, _Comp, _Proj>
1927 constexpr _Iter
1928 operator()(_Iter __first, _Sent __last,
1929 _Comp __comp = {}, _Proj __proj = {}) const
1930 {
1931 auto __lasti = ranges::next(__first, __last);
1932 std::sort_heap(__first, __lasti,
1933 __detail::__make_comp_proj(__comp, __proj));
1934 return __lasti;
1935 }
1936
1937 template<random_access_range _Range,
1938 typename _Comp = ranges::less, typename _Proj = identity>
1939 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1940 constexpr borrowed_iterator_t<_Range>
1941 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1942 {
1943 return (*this)(ranges::begin(__r), ranges::end(__r),
1944 std::move(__comp), std::move(__proj));
1945 }
1946 };
1947
1948 inline constexpr __sort_heap_fn sort_heap{};
1949
1950 struct __is_heap_until_fn
1951 {
1952 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1953 typename _Proj = identity,
1954 indirect_strict_weak_order<projected<_Iter, _Proj>>
1955 _Comp = ranges::less>
1956 constexpr _Iter
1957 operator()(_Iter __first, _Sent __last,
1958 _Comp __comp = {}, _Proj __proj = {}) const
1959 {
1960 iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
1961 iter_difference_t<_Iter> __parent = 0, __child = 1;
1962 for (; __child < __n; ++__child)
1963 if (std::__invoke(__comp,
1964 std::__invoke(__proj, *(__first + __parent)),
1965 std::__invoke(__proj, *(__first + __child))))
1966 return __first + __child;
1967 else if ((__child & 1) == 0)
1968 ++__parent;
1969
1970 return __first + __n;
1971 }
1972
1973 template<random_access_range _Range,
1974 typename _Proj = identity,
1975 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1976 _Comp = ranges::less>
1977 constexpr borrowed_iterator_t<_Range>
1978 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
1979 {
1980 return (*this)(ranges::begin(__r), ranges::end(__r),
1981 std::move(__comp), std::move(__proj));
1982 }
1983 };
1984
1985 inline constexpr __is_heap_until_fn is_heap_until{};
1986
1987 struct __is_heap_fn
1988 {
1989 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1990 typename _Proj = identity,
1991 indirect_strict_weak_order<projected<_Iter, _Proj>>
1992 _Comp = ranges::less>
1993 constexpr bool
1994 operator()(_Iter __first, _Sent __last,
1995 _Comp __comp = {}, _Proj __proj = {}) const
1996 {
1997 return (__last
1998 == ranges::is_heap_until(__first, __last,
1999 std::move(__comp),
2000 std::move(__proj)));
2001 }
2002
2003 template<random_access_range _Range,
2004 typename _Proj = identity,
2005 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2006 _Comp = ranges::less>
2007 constexpr bool
2008 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2009 {
2010 return (*this)(ranges::begin(__r), ranges::end(__r),
2011 std::move(__comp), std::move(__proj));
2012 }
2013 };
2014
2015 inline constexpr __is_heap_fn is_heap{};
2016
2017 struct __sort_fn
2018 {
2019 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2020 typename _Comp = ranges::less, typename _Proj = identity>
2021 requires sortable<_Iter, _Comp, _Proj>
2022 constexpr _Iter
2023 operator()(_Iter __first, _Sent __last,
2024 _Comp __comp = {}, _Proj __proj = {}) const
2025 {
2026 auto __lasti = ranges::next(__first, __last);
2027 std::sort(std::move(__first), __lasti,
2028 __detail::__make_comp_proj(__comp, __proj));
2029 return __lasti;
2030 }
2031
2032 template<random_access_range _Range,
2033 typename _Comp = ranges::less, typename _Proj = identity>
2034 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2035 constexpr borrowed_iterator_t<_Range>
2036 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2037 {
2038 return (*this)(ranges::begin(__r), ranges::end(__r),
2039 std::move(__comp), std::move(__proj));
2040 }
2041 };
2042
2043 inline constexpr __sort_fn sort{};
2044
2045 struct __stable_sort_fn
2046 {
2047 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2048 typename _Comp = ranges::less, typename _Proj = identity>
2049 requires sortable<_Iter, _Comp, _Proj>
2050 _Iter
2051 operator()(_Iter __first, _Sent __last,
2052 _Comp __comp = {}, _Proj __proj = {}) const
2053 {
2054 auto __lasti = ranges::next(__first, __last);
2055 std::stable_sort(std::move(__first), __lasti,
2056 __detail::__make_comp_proj(__comp, __proj));
2057 return __lasti;
2058 }
2059
2060 template<random_access_range _Range,
2061 typename _Comp = ranges::less, typename _Proj = identity>
2062 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2063 borrowed_iterator_t<_Range>
2064 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2065 {
2066 return (*this)(ranges::begin(__r), ranges::end(__r),
2067 std::move(__comp), std::move(__proj));
2068 }
2069 };
2070
2071 inline constexpr __stable_sort_fn stable_sort{};
2072
2073 struct __partial_sort_fn
2074 {
2075 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2076 typename _Comp = ranges::less, typename _Proj = identity>
2077 requires sortable<_Iter, _Comp, _Proj>
2078 constexpr _Iter
2079 operator()(_Iter __first, _Iter __middle, _Sent __last,
2080 _Comp __comp = {}, _Proj __proj = {}) const
2081 {
2082 if (__first == __middle)
2083 return ranges::next(__first, __last);
2084
2085 ranges::make_heap(__first, __middle, __comp, __proj);
2086 auto __i = __middle;
2087 for (; __i != __last; ++__i)
2088 if (std::__invoke(__comp,
2089 std::__invoke(__proj, *__i),
2090 std::__invoke(__proj, *__first)))
2091 {
2092 ranges::pop_heap(__first, __middle, __comp, __proj);
2093 ranges::iter_swap(__middle-1, __i);
2094 ranges::push_heap(__first, __middle, __comp, __proj);
2095 }
2096 ranges::sort_heap(__first, __middle, __comp, __proj);
2097
2098 return __i;
2099 }
2100
2101 template<random_access_range _Range,
2102 typename _Comp = ranges::less, typename _Proj = identity>
2103 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2104 constexpr borrowed_iterator_t<_Range>
2105 operator()(_Range&& __r, iterator_t<_Range> __middle,
2106 _Comp __comp = {}, _Proj __proj = {}) const
2107 {
2108 return (*this)(ranges::begin(__r), std::move(__middle),
2109 ranges::end(__r),
2110 std::move(__comp), std::move(__proj));
2111 }
2112 };
2113
2114 inline constexpr __partial_sort_fn partial_sort{};
2115
2116 template<typename _Iter, typename _Out>
2117 using partial_sort_copy_result = in_out_result<_Iter, _Out>;
2118
2119 struct __partial_sort_copy_fn
2120 {
2121 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2122 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2123 typename _Comp = ranges::less,
2124 typename _Proj1 = identity, typename _Proj2 = identity>
2125 requires indirectly_copyable<_Iter1, _Iter2>
2126 && sortable<_Iter2, _Comp, _Proj2>
2127 && indirect_strict_weak_order<_Comp,
2128 projected<_Iter1, _Proj1>,
2129 projected<_Iter2, _Proj2>>
2130 constexpr partial_sort_copy_result<_Iter1, _Iter2>
2131 operator()(_Iter1 __first, _Sent1 __last,
2132 _Iter2 __result_first, _Sent2 __result_last,
2133 _Comp __comp = {},
2134 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2135 {
2136 if (__result_first == __result_last)
2137 {
2138 // TODO: Eliminating the variable __lasti triggers an ICE.
2139 auto __lasti = ranges::next(std::move(__first),
2140 std::move(__last));
2141 return {std::move(__lasti), std::move(__result_first)};
2142 }
2143
2144 auto __result_real_last = __result_first;
2145 while (__first != __last && __result_real_last != __result_last)
2146 {
2147 *__result_real_last = *__first;
2148 ++__result_real_last;
2149 ++__first;
2150 }
2151
2152 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
2153 for (; __first != __last; ++__first)
2154 if (std::__invoke(__comp,
2155 std::__invoke(__proj1, *__first),
2156 std::__invoke(__proj2, *__result_first)))
2157 {
2158 ranges::pop_heap(__result_first, __result_real_last,
2159 __comp, __proj2);
2160 *(__result_real_last-1) = *__first;
2161 ranges::push_heap(__result_first, __result_real_last,
2162 __comp, __proj2);
2163 }
2164 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
2165
2166 return {std::move(__first), std::move(__result_real_last)};
2167 }
2168
2169 template<input_range _Range1, random_access_range _Range2,
2170 typename _Comp = ranges::less,
2171 typename _Proj1 = identity, typename _Proj2 = identity>
2172 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
2173 && sortable<iterator_t<_Range2>, _Comp, _Proj2>
2174 && indirect_strict_weak_order<_Comp,
2175 projected<iterator_t<_Range1>, _Proj1>,
2176 projected<iterator_t<_Range2>, _Proj2>>
2177 constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
2178 borrowed_iterator_t<_Range2>>
2179 operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
2180 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2181 {
2182 return (*this)(ranges::begin(__r), ranges::end(__r),
2183 ranges::begin(__out), ranges::end(__out),
2184 std::move(__comp),
2185 std::move(__proj1), std::move(__proj2));
2186 }
2187 };
2188
2189 inline constexpr __partial_sort_copy_fn partial_sort_copy{};
2190
2191 struct __is_sorted_until_fn
2192 {
2193 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2194 typename _Proj = identity,
2195 indirect_strict_weak_order<projected<_Iter, _Proj>>
2196 _Comp = ranges::less>
2197 constexpr _Iter
2198 operator()(_Iter __first, _Sent __last,
2199 _Comp __comp = {}, _Proj __proj = {}) const
2200 {
2201 if (__first == __last)
2202 return __first;
2203
2204 auto __next = __first;
2205 for (++__next; __next != __last; __first = __next, (void)++__next)
2206 if (std::__invoke(__comp,
2207 std::__invoke(__proj, *__next),
2208 std::__invoke(__proj, *__first)))
2209 return __next;
2210 return __next;
2211 }
2212
2213 template<forward_range _Range, typename _Proj = identity,
2214 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2215 _Comp = ranges::less>
2216 constexpr borrowed_iterator_t<_Range>
2217 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2218 {
2219 return (*this)(ranges::begin(__r), ranges::end(__r),
2220 std::move(__comp), std::move(__proj));
2221 }
2222 };
2223
2224 inline constexpr __is_sorted_until_fn is_sorted_until{};
2225
2226 struct __is_sorted_fn
2227 {
2228 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2229 typename _Proj = identity,
2230 indirect_strict_weak_order<projected<_Iter, _Proj>>
2231 _Comp = ranges::less>
2232 constexpr bool
2233 operator()(_Iter __first, _Sent __last,
2234 _Comp __comp = {}, _Proj __proj = {}) const
2235 {
2236 if (__first == __last)
2237 return true;
2238
2239 auto __next = __first;
2240 for (++__next; __next != __last; __first = __next, (void)++__next)
2241 if (std::__invoke(__comp,
2242 std::__invoke(__proj, *__next),
2243 std::__invoke(__proj, *__first)))
2244 return false;
2245 return true;
2246 }
2247
2248 template<forward_range _Range, typename _Proj = identity,
2249 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2250 _Comp = ranges::less>
2251 constexpr bool
2252 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
2253 {
2254 return (*this)(ranges::begin(__r), ranges::end(__r),
2255 std::move(__comp), std::move(__proj));
2256 }
2257 };
2258
2259 inline constexpr __is_sorted_fn is_sorted{};
2260
2261 struct __nth_element_fn
2262 {
2263 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2264 typename _Comp = ranges::less, typename _Proj = identity>
2265 requires sortable<_Iter, _Comp, _Proj>
2266 constexpr _Iter
2267 operator()(_Iter __first, _Iter __nth, _Sent __last,
2268 _Comp __comp = {}, _Proj __proj = {}) const
2269 {
2270 auto __lasti = ranges::next(__first, __last);
2271 std::nth_element(std::move(__first), std::move(__nth), __lasti,
2272 __detail::__make_comp_proj(__comp, __proj));
2273 return __lasti;
2274 }
2275
2276 template<random_access_range _Range,
2277 typename _Comp = ranges::less, typename _Proj = identity>
2278 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2279 constexpr borrowed_iterator_t<_Range>
2280 operator()(_Range&& __r, iterator_t<_Range> __nth,
2281 _Comp __comp = {}, _Proj __proj = {}) const
2282 {
2283 return (*this)(ranges::begin(__r), std::move(__nth),
2284 ranges::end(__r), std::move(__comp), std::move(__proj));
2285 }
2286 };
2287
2288 inline constexpr __nth_element_fn nth_element{};
2289
2290 struct __lower_bound_fn
2291 {
2292 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2293 typename _Tp, typename _Proj = identity,
2294 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2295 _Comp = ranges::less>
2296 constexpr _Iter
2297 operator()(_Iter __first, _Sent __last,
2298 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2299 {
2300 auto __len = ranges::distance(__first, __last);
2301
2302 while (__len > 0)
2303 {
2304 auto __half = __len / 2;
2305 auto __middle = __first;
2306 ranges::advance(__middle, __half);
2307 if (std::__invoke(__comp, std::__invoke(__proj, *__middle), __value))
2308 {
2309 __first = __middle;
2310 ++__first;
2311 __len = __len - __half - 1;
2312 }
2313 else
2314 __len = __half;
2315 }
2316 return __first;
2317 }
2318
2319 template<forward_range _Range, typename _Tp, typename _Proj = identity,
2320 indirect_strict_weak_order<const _Tp*,
2321 projected<iterator_t<_Range>, _Proj>>
2322 _Comp = ranges::less>
2323 constexpr borrowed_iterator_t<_Range>
2324 operator()(_Range&& __r,
2325 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2326 {
2327 return (*this)(ranges::begin(__r), ranges::end(__r),
2328 __value, std::move(__comp), std::move(__proj));
2329 }
2330 };
2331
2332 inline constexpr __lower_bound_fn lower_bound{};
2333
2334 struct __upper_bound_fn
2335 {
2336 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2337 typename _Tp, typename _Proj = identity,
2338 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2339 _Comp = ranges::less>
2340 constexpr _Iter
2341 operator()(_Iter __first, _Sent __last,
2342 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2343 {
2344 auto __len = ranges::distance(__first, __last);
2345
2346 while (__len > 0)
2347 {
2348 auto __half = __len / 2;
2349 auto __middle = __first;
2350 ranges::advance(__middle, __half);
2351 if (std::__invoke(__comp, __value, std::__invoke(__proj, *__middle)))
2352 __len = __half;
2353 else
2354 {
2355 __first = __middle;
2356 ++__first;
2357 __len = __len - __half - 1;
2358 }
2359 }
2360 return __first;
2361 }
2362
2363 template<forward_range _Range, typename _Tp, typename _Proj = identity,
2364 indirect_strict_weak_order<const _Tp*,
2365 projected<iterator_t<_Range>, _Proj>>
2366 _Comp = ranges::less>
2367 constexpr borrowed_iterator_t<_Range>
2368 operator()(_Range&& __r,
2369 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2370 {
2371 return (*this)(ranges::begin(__r), ranges::end(__r),
2372 __value, std::move(__comp), std::move(__proj));
2373 }
2374 };
2375
2376 inline constexpr __upper_bound_fn upper_bound{};
2377
2378 struct __equal_range_fn
2379 {
2380 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2381 typename _Tp, typename _Proj = identity,
2382 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2383 _Comp = ranges::less>
2384 constexpr subrange<_Iter>
2385 operator()(_Iter __first, _Sent __last,
2386 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2387 {
2388 auto __len = ranges::distance(__first, __last);
2389
2390 while (__len > 0)
2391 {
2392 auto __half = __len / 2;
2393 auto __middle = __first;
2394 ranges::advance(__middle, __half);
2395 if (std::__invoke(__comp,
2396 std::__invoke(__proj, *__middle),
2397 __value))
2398 {
2399 __first = __middle;
2400 ++__first;
2401 __len = __len - __half - 1;
2402 }
2403 else if (std::__invoke(__comp,
2404 __value,
2405 std::__invoke(__proj, *__middle)))
2406 __len = __half;
2407 else
2408 {
2409 auto __left
2410 = ranges::lower_bound(__first, __middle,
2411 __value, __comp, __proj);
2412 ranges::advance(__first, __len);
2413 auto __right
2414 = ranges::upper_bound(++__middle, __first,
2415 __value, __comp, __proj);
2416 return {__left, __right};
2417 }
2418 }
2419 return {__first, __first};
2420 }
2421
2422 template<forward_range _Range,
2423 typename _Tp, typename _Proj = identity,
2424 indirect_strict_weak_order<const _Tp*,
2425 projected<iterator_t<_Range>, _Proj>>
2426 _Comp = ranges::less>
2427 constexpr borrowed_subrange_t<_Range>
2428 operator()(_Range&& __r, const _Tp& __value,
2429 _Comp __comp = {}, _Proj __proj = {}) const
2430 {
2431 return (*this)(ranges::begin(__r), ranges::end(__r),
2432 __value, std::move(__comp), std::move(__proj));
2433 }
2434 };
2435
2436 inline constexpr __equal_range_fn equal_range{};
2437
2438 struct __binary_search_fn
2439 {
2440 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2441 typename _Tp, typename _Proj = identity,
2442 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2443 _Comp = ranges::less>
2444 constexpr bool
2445 operator()(_Iter __first, _Sent __last,
2446 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const
2447 {
2448 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2449 if (__i == __last)
2450 return false;
2451 return !(bool)std::__invoke(__comp, __value,
2452 std::__invoke(__proj, *__i));
2453 }
2454
2455 template<forward_range _Range,
2456 typename _Tp, typename _Proj = identity,
2457 indirect_strict_weak_order<const _Tp*,
2458 projected<iterator_t<_Range>, _Proj>>
2459 _Comp = ranges::less>
2460 constexpr bool
2461 operator()(_Range&& __r, const _Tp& __value, _Comp __comp = {},
2462 _Proj __proj = {}) const
2463 {
2464 return (*this)(ranges::begin(__r), ranges::end(__r),
2465 __value, std::move(__comp), std::move(__proj));
2466 }
2467 };
2468
2469 inline constexpr __binary_search_fn binary_search{};
2470
2471 struct __is_partitioned_fn
2472 {
2473 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2474 typename _Proj = identity,
2475 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2476 constexpr bool
2477 operator()(_Iter __first, _Sent __last,
2478 _Pred __pred, _Proj __proj = {}) const
2479 {
2480 __first = ranges::find_if_not(std::move(__first), __last,
2481 __pred, __proj);
2482 if (__first == __last)
2483 return true;
2484 ++__first;
2485 return ranges::none_of(std::move(__first), std::move(__last),
2486 std::move(__pred), std::move(__proj));
2487 }
2488
2489 template<input_range _Range, typename _Proj = identity,
2490 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2491 _Pred>
2492 constexpr bool
2493 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2494 {
2495 return (*this)(ranges::begin(__r), ranges::end(__r),
2496 std::move(__pred), std::move(__proj));
2497 }
2498 };
2499
2500 inline constexpr __is_partitioned_fn is_partitioned{};
2501
2502 struct __partition_fn
2503 {
2504 template<permutable _Iter, sentinel_for<_Iter> _Sent,
2505 typename _Proj = identity,
2506 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2507 constexpr subrange<_Iter>
2508 operator()(_Iter __first, _Sent __last,
2509 _Pred __pred, _Proj __proj = {}) const
2510 {
2511 if constexpr (bidirectional_iterator<_Iter>)
2512 {
2513 auto __lasti = ranges::next(__first, __last);
2514 auto __tail = __lasti;
2515 for (;;)
2516 {
2517 for (;;)
2518 if (__first == __tail)
2519 return {std::move(__first), std::move(__lasti)};
2520 else if (std::__invoke(__pred,
2521 std::__invoke(__proj, *__first)))
2522 ++__first;
2523 else
2524 break;
2525 --__tail;
2526 for (;;)
2527 if (__first == __tail)
2528 return {std::move(__first), std::move(__lasti)};
2529 else if (!(bool)std::__invoke(__pred,
2530 std::__invoke(__proj, *__tail)))
2531 --__tail;
2532 else
2533 break;
2534 ranges::iter_swap(__first, __tail);
2535 ++__first;
2536 }
2537 }
2538 else
2539 {
2540 if (__first == __last)
2541 return {__first, __first};
2542
2543 while (std::__invoke(__pred, std::__invoke(__proj, *__first)))
2544 if (++__first == __last)
2545 return {__first, __first};
2546
2547 auto __next = __first;
2548 while (++__next != __last)
2549 if (std::__invoke(__pred, std::__invoke(__proj, *__next)))
2550 {
2551 ranges::iter_swap(__first, __next);
2552 ++__first;
2553 }
2554
2555 return {std::move(__first), std::move(__next)};
2556 }
2557 }
2558
2559 template<forward_range _Range, typename _Proj = identity,
2560 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2561 _Pred>
2562 requires permutable<iterator_t<_Range>>
2563 constexpr borrowed_subrange_t<_Range>
2564 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2565 {
2566 return (*this)(ranges::begin(__r), ranges::end(__r),
2567 std::move(__pred), std::move(__proj));
2568 }
2569 };
2570
2571 inline constexpr __partition_fn partition{};
2572
2573 struct __stable_partition_fn
2574 {
2575 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2576 typename _Proj = identity,
2577 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2578 requires permutable<_Iter>
2579 subrange<_Iter>
2580 operator()(_Iter __first, _Sent __last,
2581 _Pred __pred, _Proj __proj = {}) const
2582 {
2583 auto __lasti = ranges::next(__first, __last);
2584 auto __middle
2585 = std::stable_partition(std::move(__first), __lasti,
2586 __detail::__make_pred_proj(__pred, __proj));
2587 return {std::move(__middle), std::move(__lasti)};
2588 }
2589
2590 template<bidirectional_range _Range, typename _Proj = identity,
2591 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2592 _Pred>
2593 requires permutable<iterator_t<_Range>>
2594 borrowed_subrange_t<_Range>
2595 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2596 {
2597 return (*this)(ranges::begin(__r), ranges::end(__r),
2598 std::move(__pred), std::move(__proj));
2599 }
2600 };
2601
2602 inline constexpr __stable_partition_fn stable_partition{};
2603
2604 template<typename _Iter, typename _Out1, typename _Out2>
2605 struct in_out_out_result
2606 {
2607 [[no_unique_address]] _Iter in;
2608 [[no_unique_address]] _Out1 out1;
2609 [[no_unique_address]] _Out2 out2;
2610
2611 template<typename _IIter, typename _OOut1, typename _OOut2>
2612 requires convertible_to<const _Iter&, _IIter>
2613 && convertible_to<const _Out1&, _OOut1>
2614 && convertible_to<const _Out2&, _OOut2>
2615 constexpr
2616 operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
2617 { return {in, out1, out2}; }
2618
2619 template<typename _IIter, typename _OOut1, typename _OOut2>
2620 requires convertible_to<_Iter, _IIter>
2621 && convertible_to<_Out1, _OOut1>
2622 && convertible_to<_Out2, _OOut2>
2623 constexpr
2624 operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2625 { return {std::move(in), std::move(out1), std::move(out2)}; }
2626 };
2627
2628 template<typename _Iter, typename _Out1, typename _Out2>
2629 using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2630
2631 struct __partition_copy_fn
2632 {
2633 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2634 weakly_incrementable _Out1, weakly_incrementable _Out2,
2635 typename _Proj = identity,
2636 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2637 requires indirectly_copyable<_Iter, _Out1>
2638 && indirectly_copyable<_Iter, _Out2>
2639 constexpr partition_copy_result<_Iter, _Out1, _Out2>
2640 operator()(_Iter __first, _Sent __last,
2641 _Out1 __out_true, _Out2 __out_false,
2642 _Pred __pred, _Proj __proj = {}) const
2643 {
2644 for (; __first != __last; ++__first)
2645 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
2646 {
2647 *__out_true = *__first;
2648 ++__out_true;
2649 }
2650 else
2651 {
2652 *__out_false = *__first;
2653 ++__out_false;
2654 }
2655
2656 return {std::move(__first),
2657 std::move(__out_true), std::move(__out_false)};
2658 }
2659
2660 template<input_range _Range, weakly_incrementable _Out1,
2661 weakly_incrementable _Out2,
2662 typename _Proj = identity,
2663 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2664 _Pred>
2665 requires indirectly_copyable<iterator_t<_Range>, _Out1>
2666 && indirectly_copyable<iterator_t<_Range>, _Out2>
2667 constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2>
2668 operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false,
2669 _Pred __pred, _Proj __proj = {}) const
2670 {
2671 return (*this)(ranges::begin(__r), ranges::end(__r),
2672 std::move(__out_true), std::move(__out_false),
2673 std::move(__pred), std::move(__proj));
2674 }
2675 };
2676
2677 inline constexpr __partition_copy_fn partition_copy{};
2678
2679 struct __partition_point_fn
2680 {
2681 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2682 typename _Proj = identity,
2683 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2684 constexpr _Iter
2685 operator()(_Iter __first, _Sent __last,
2686 _Pred __pred, _Proj __proj = {}) const
2687 {
2688 auto __len = ranges::distance(__first, __last);
2689
2690 while (__len > 0)
2691 {
2692 auto __half = __len / 2;
2693 auto __middle = __first;
2694 ranges::advance(__middle, __half);
2695 if (std::__invoke(__pred, std::__invoke(__proj, *__middle)))
2696 {
2697 __first = __middle;
2698 ++__first;
2699 __len = __len - __half - 1;
2700 }
2701 else
2702 __len = __half;
2703 }
2704 return __first;
2705 }
2706
2707 template<forward_range _Range, typename _Proj = identity,
2708 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2709 _Pred>
2710 constexpr borrowed_iterator_t<_Range>
2711 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {}) const
2712 {
2713 return (*this)(ranges::begin(__r), ranges::end(__r),
2714 std::move(__pred), std::move(__proj));
2715 }
2716 };
2717
2718 inline constexpr __partition_point_fn partition_point{};
2719
2720 template<typename _Iter1, typename _Iter2, typename _Out>
2721 using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2722
2723 struct __merge_fn
2724 {
2725 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2726 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2727 weakly_incrementable _Out, typename _Comp = ranges::less,
2728 typename _Proj1 = identity, typename _Proj2 = identity>
2729 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2730 constexpr merge_result<_Iter1, _Iter2, _Out>
2731 operator()(_Iter1 __first1, _Sent1 __last1,
2732 _Iter2 __first2, _Sent2 __last2, _Out __result,
2733 _Comp __comp = {},
2734 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2735 {
2736 while (__first1 != __last1 && __first2 != __last2)
2737 {
2738 if (std::__invoke(__comp,
2739 std::__invoke(__proj2, *__first2),
2740 std::__invoke(__proj1, *__first1)))
2741 {
2742 *__result = *__first2;
2743 ++__first2;
2744 }
2745 else
2746 {
2747 *__result = *__first1;
2748 ++__first1;
2749 }
2750 ++__result;
2751 }
2752 auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
2753 std::move(__result));
2754 auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
2755 std::move(__copy1.out));
2756 return { std::move(__copy1.in), std::move(__copy2.in),
2757 std::move(__copy2.out) };
2758 }
2759
2760 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2761 typename _Comp = ranges::less,
2762 typename _Proj1 = identity, typename _Proj2 = identity>
2763 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2764 _Comp, _Proj1, _Proj2>
2765 constexpr merge_result<borrowed_iterator_t<_Range1>,
2766 borrowed_iterator_t<_Range2>,
2767 _Out>
2768 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2769 _Comp __comp = {},
2770 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2771 {
2772 return (*this)(ranges::begin(__r1), ranges::end(__r1),
2773 ranges::begin(__r2), ranges::end(__r2),
2774 std::move(__result), std::move(__comp),
2775 std::move(__proj1), std::move(__proj2));
2776 }
2777 };
2778
2779 inline constexpr __merge_fn merge{};
2780
2781 struct __inplace_merge_fn
2782 {
2783 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2784 typename _Comp = ranges::less,
2785 typename _Proj = identity>
2786 requires sortable<_Iter, _Comp, _Proj>
2787 _Iter
2788 operator()(_Iter __first, _Iter __middle, _Sent __last,
2789 _Comp __comp = {}, _Proj __proj = {}) const
2790 {
2791 auto __lasti = ranges::next(__first, __last);
2792 std::inplace_merge(std::move(__first), std::move(__middle), __lasti,
2793 __detail::__make_comp_proj(__comp, __proj));
2794 return __lasti;
2795 }
2796
2797 template<bidirectional_range _Range,
2798 typename _Comp = ranges::less, typename _Proj = identity>
2799 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2800 borrowed_iterator_t<_Range>
2801 operator()(_Range&& __r, iterator_t<_Range> __middle,
2802 _Comp __comp = {}, _Proj __proj = {}) const
2803 {
2804 return (*this)(ranges::begin(__r), std::move(__middle),
2805 ranges::end(__r),
2806 std::move(__comp), std::move(__proj));
2807 }
2808 };
2809
2810 inline constexpr __inplace_merge_fn inplace_merge{};
2811
2812 struct __includes_fn
2813 {
2814 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2815 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2816 typename _Proj1 = identity, typename _Proj2 = identity,
2817 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2818 projected<_Iter2, _Proj2>>
2819 _Comp = ranges::less>
2820 constexpr bool
2821 operator()(_Iter1 __first1, _Sent1 __last1,
2822 _Iter2 __first2, _Sent2 __last2,
2823 _Comp __comp = {},
2824 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2825 {
2826 while (__first1 != __last1 && __first2 != __last2)
2827 if (std::__invoke(__comp,
2828 std::__invoke(__proj2, *__first2),
2829 std::__invoke(__proj1, *__first1)))
2830 return false;
2831 else if (std::__invoke(__comp,
2832 std::__invoke(__proj1, *__first1),
2833 std::__invoke(__proj2, *__first2)))
2834 ++__first1;
2835 else
2836 {
2837 ++__first1;
2838 ++__first2;
2839 }
2840
2841 return __first2 == __last2;
2842 }
2843
2844 template<input_range _Range1, input_range _Range2,
2845 typename _Proj1 = identity, typename _Proj2 = identity,
2846 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2847 projected<iterator_t<_Range2>, _Proj2>>
2848 _Comp = ranges::less>
2849 constexpr bool
2850 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2851 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2852 {
2853 return (*this)(ranges::begin(__r1), ranges::end(__r1),
2854 ranges::begin(__r2), ranges::end(__r2),
2855 std::move(__comp),
2856 std::move(__proj1), std::move(__proj2));
2857 }
2858 };
2859
2860 inline constexpr __includes_fn includes{};
2861
2862 template<typename _Iter1, typename _Iter2, typename _Out>
2863 using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2864
2865 struct __set_union_fn
2866 {
2867 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2868 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2869 weakly_incrementable _Out, typename _Comp = ranges::less,
2870 typename _Proj1 = identity, typename _Proj2 = identity>
2871 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2872 constexpr set_union_result<_Iter1, _Iter2, _Out>
2873 operator()(_Iter1 __first1, _Sent1 __last1,
2874 _Iter2 __first2, _Sent2 __last2,
2875 _Out __result, _Comp __comp = {},
2876 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2877 {
2878 while (__first1 != __last1 && __first2 != __last2)
2879 {
2880 if (std::__invoke(__comp,
2881 std::__invoke(__proj1, *__first1),
2882 std::__invoke(__proj2, *__first2)))
2883 {
2884 *__result = *__first1;
2885 ++__first1;
2886 }
2887 else if (std::__invoke(__comp,
2888 std::__invoke(__proj2, *__first2),
2889 std::__invoke(__proj1, *__first1)))
2890 {
2891 *__result = *__first2;
2892 ++__first2;
2893 }
2894 else
2895 {
2896 *__result = *__first1;
2897 ++__first1;
2898 ++__first2;
2899 }
2900 ++__result;
2901 }
2902 auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
2903 std::move(__result));
2904 auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
2905 std::move(__copy1.out));
2906 return {std::move(__copy1.in), std::move(__copy2.in),
2907 std::move(__copy2.out)};
2908 }
2909
2910 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2911 typename _Comp = ranges::less,
2912 typename _Proj1 = identity, typename _Proj2 = identity>
2913 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2914 _Comp, _Proj1, _Proj2>
2915 constexpr set_union_result<borrowed_iterator_t<_Range1>,
2916 borrowed_iterator_t<_Range2>, _Out>
2917 operator()(_Range1&& __r1, _Range2&& __r2,
2918 _Out __result, _Comp __comp = {},
2919 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2920 {
2921 return (*this)(ranges::begin(__r1), ranges::end(__r1),
2922 ranges::begin(__r2), ranges::end(__r2),
2923 std::move(__result), std::move(__comp),
2924 std::move(__proj1), std::move(__proj2));
2925 }
2926 };
2927
2928 inline constexpr __set_union_fn set_union{};
2929
2930 template<typename _Iter1, typename _Iter2, typename _Out>
2931 using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2932
2933 struct __set_intersection_fn
2934 {
2935 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2936 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2937 weakly_incrementable _Out, typename _Comp = ranges::less,
2938 typename _Proj1 = identity, typename _Proj2 = identity>
2939 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2940 constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2941 operator()(_Iter1 __first1, _Sent1 __last1,
2942 _Iter2 __first2, _Sent2 __last2, _Out __result,
2943 _Comp __comp = {},
2944 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2945 {
2946 while (__first1 != __last1 && __first2 != __last2)
2947 if (std::__invoke(__comp,
2948 std::__invoke(__proj1, *__first1),
2949 std::__invoke(__proj2, *__first2)))
2950 ++__first1;
2951 else if (std::__invoke(__comp,
2952 std::__invoke(__proj2, *__first2),
2953 std::__invoke(__proj1, *__first1)))
2954 ++__first2;
2955 else
2956 {
2957 *__result = *__first1;
2958 ++__first1;
2959 ++__first2;
2960 ++__result;
2961 }
2962 // TODO: Eliminating these variables triggers an ICE.
2963 auto __last1i = ranges::next(std::move(__first1), std::move(__last1));
2964 auto __last2i = ranges::next(std::move(__first2), std::move(__last2));
2965 return {std::move(__last1i), std::move(__last2i), std::move(__result)};
2966 }
2967
2968 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2969 typename _Comp = ranges::less,
2970 typename _Proj1 = identity, typename _Proj2 = identity>
2971 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2972 _Comp, _Proj1, _Proj2>
2973 constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
2974 borrowed_iterator_t<_Range2>, _Out>
2975 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2976 _Comp __comp = {},
2977 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
2978 {
2979 return (*this)(ranges::begin(__r1), ranges::end(__r1),
2980 ranges::begin(__r2), ranges::end(__r2),
2981 std::move(__result), std::move(__comp),
2982 std::move(__proj1), std::move(__proj2));
2983 }
2984 };
2985
2986 inline constexpr __set_intersection_fn set_intersection{};
2987
2988 template<typename _Iter, typename _Out>
2989 using set_difference_result = in_out_result<_Iter, _Out>;
2990
2991 struct __set_difference_fn
2992 {
2993 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2994 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2995 weakly_incrementable _Out, typename _Comp = ranges::less,
2996 typename _Proj1 = identity, typename _Proj2 = identity>
2997 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2998 constexpr set_difference_result<_Iter1, _Out>
2999 operator()(_Iter1 __first1, _Sent1 __last1,
3000 _Iter2 __first2, _Sent2 __last2, _Out __result,
3001 _Comp __comp = {},
3002 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3003 {
3004 while (__first1 != __last1 && __first2 != __last2)
3005 if (std::__invoke(__comp,
3006 std::__invoke(__proj1, *__first1),
3007 std::__invoke(__proj2, *__first2)))
3008 {
3009 *__result = *__first1;
3010 ++__first1;
3011 ++__result;
3012 }
3013 else if (std::__invoke(__comp,
3014 std::__invoke(__proj2, *__first2),
3015 std::__invoke(__proj1, *__first1)))
3016 ++__first2;
3017 else
3018 {
3019 ++__first1;
3020 ++__first2;
3021 }
3022 return ranges::copy(std::move(__first1), std::move(__last1),
3023 std::move(__result));
3024 }
3025
3026 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3027 typename _Comp = ranges::less,
3028 typename _Proj1 = identity, typename _Proj2 = identity>
3029 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3030 _Comp, _Proj1, _Proj2>
3031 constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
3032 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
3033 _Comp __comp = {},
3034 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3035 {
3036 return (*this)(ranges::begin(__r1), ranges::end(__r1),
3037 ranges::begin(__r2), ranges::end(__r2),
3038 std::move(__result), std::move(__comp),
3039 std::move(__proj1), std::move(__proj2));
3040 }
3041 };
3042
3043 inline constexpr __set_difference_fn set_difference{};
3044
3045 template<typename _Iter1, typename _Iter2, typename _Out>
3046 using set_symmetric_difference_result
3047 = in_in_out_result<_Iter1, _Iter2, _Out>;
3048
3049 struct __set_symmetric_difference_fn
3050 {
3051 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3052 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3053 weakly_incrementable _Out, typename _Comp = ranges::less,
3054 typename _Proj1 = identity, typename _Proj2 = identity>
3055 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
3056 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
3057 operator()(_Iter1 __first1, _Sent1 __last1,
3058 _Iter2 __first2, _Sent2 __last2,
3059 _Out __result, _Comp __comp = {},
3060 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3061 {
3062 while (__first1 != __last1 && __first2 != __last2)
3063 if (std::__invoke(__comp,
3064 std::__invoke(__proj1, *__first1),
3065 std::__invoke(__proj2, *__first2)))
3066 {
3067 *__result = *__first1;
3068 ++__first1;
3069 ++__result;
3070 }
3071 else if (std::__invoke(__comp,
3072 std::__invoke(__proj2, *__first2),
3073 std::__invoke(__proj1, *__first1)))
3074 {
3075 *__result = *__first2;
3076 ++__first2;
3077 ++__result;
3078 }
3079 else
3080 {
3081 ++__first1;
3082 ++__first2;
3083 }
3084 auto __copy1 = ranges::copy(std::move(__first1), std::move(__last1),
3085 std::move(__result));
3086 auto __copy2 = ranges::copy(std::move(__first2), std::move(__last2),
3087 std::move(__copy1.out));
3088 return {std::move(__copy1.in), std::move(__copy2.in),
3089 std::move(__copy2.out)};
3090 }
3091
3092 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3093 typename _Comp = ranges::less,
3094 typename _Proj1 = identity, typename _Proj2 = identity>
3095 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3096 _Comp, _Proj1, _Proj2>
3097 constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
3098 borrowed_iterator_t<_Range2>,
3099 _Out>
3100 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
3101 _Comp __comp = {},
3102 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3103 {
3104 return (*this)(ranges::begin(__r1), ranges::end(__r1),
3105 ranges::begin(__r2), ranges::end(__r2),
3106 std::move(__result), std::move(__comp),
3107 std::move(__proj1), std::move(__proj2));
3108 }
3109 };
3110
3111 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
3112
3113 struct __min_fn
3114 {
3115 template<typename _Tp, typename _Proj = identity,
3116 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3117 _Comp = ranges::less>
3118 constexpr const _Tp&
3119 operator()(const _Tp& __a, const _Tp& __b,
3120 _Comp __comp = {}, _Proj __proj = {}) const
3121 {
3122 if (std::__invoke(__comp,
3123 std::__invoke(__proj, __b),
3124 std::__invoke(__proj, __a)))
3125 return __b;
3126 else
3127 return __a;
3128 }
3129
3130 template<input_range _Range, typename _Proj = identity,
3131 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3132 _Comp = ranges::less>
3133 requires indirectly_copyable_storable<iterator_t<_Range>,
3134 range_value_t<_Range>*>
3135 constexpr range_value_t<_Range>
3136 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3137 {
3138 auto __first = ranges::begin(__r);
3139 auto __last = ranges::end(__r);
3140 __glibcxx_assert(__first != __last);
3141 auto __result = *__first;
3142 while (++__first != __last)
3143 {
3144 auto __tmp = *__first;
3145 if (std::__invoke(__comp,
3146 std::__invoke(__proj, __tmp),
3147 std::__invoke(__proj, __result)))
3148 __result = std::move(__tmp);
3149 }
3150 return __result;
3151 }
3152
3153 template<copyable _Tp, typename _Proj = identity,
3154 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3155 _Comp = ranges::less>
3156 constexpr _Tp
3157 operator()(initializer_list<_Tp> __r,
3158 _Comp __comp = {}, _Proj __proj = {}) const
3159 {
3160 return (*this)(ranges::subrange(__r),
3161 std::move(__comp), std::move(__proj));
3162 }
3163 };
3164
3165 inline constexpr __min_fn min{};
3166
3167 struct __max_fn
3168 {
3169 template<typename _Tp, typename _Proj = identity,
3170 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3171 _Comp = ranges::less>
3172 constexpr const _Tp&
3173 operator()(const _Tp& __a, const _Tp& __b,
3174 _Comp __comp = {}, _Proj __proj = {}) const
3175 {
3176 if (std::__invoke(__comp,
3177 std::__invoke(__proj, __a),
3178 std::__invoke(__proj, __b)))
3179 return __b;
3180 else
3181 return __a;
3182 }
3183
3184 template<input_range _Range, typename _Proj = identity,
3185 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3186 _Comp = ranges::less>
3187 requires indirectly_copyable_storable<iterator_t<_Range>,
3188 range_value_t<_Range>*>
3189 constexpr range_value_t<_Range>
3190 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3191 {
3192 auto __first = ranges::begin(__r);
3193 auto __last = ranges::end(__r);
3194 __glibcxx_assert(__first != __last);
3195 auto __result = *__first;
3196 while (++__first != __last)
3197 {
3198 auto __tmp = *__first;
3199 if (std::__invoke(__comp,
3200 std::__invoke(__proj, __result),
3201 std::__invoke(__proj, __tmp)))
3202 __result = std::move(__tmp);
3203 }
3204 return __result;
3205 }
3206
3207 template<copyable _Tp, typename _Proj = identity,
3208 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3209 _Comp = ranges::less>
3210 constexpr _Tp
3211 operator()(initializer_list<_Tp> __r,
3212 _Comp __comp = {}, _Proj __proj = {}) const
3213 {
3214 return (*this)(ranges::subrange(__r),
3215 std::move(__comp), std::move(__proj));
3216 }
3217 };
3218
3219 inline constexpr __max_fn max{};
3220
3221 struct __clamp_fn
3222 {
3223 template<typename _Tp, typename _Proj = identity,
3224 indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
3225 = ranges::less>
3226 constexpr const _Tp&
3227 operator()(const _Tp& __val, const _Tp& __lo, const _Tp& __hi,
3228 _Comp __comp = {}, _Proj __proj = {}) const
3229 {
3230 __glibcxx_assert(!(std::__invoke(__comp,
3231 std::__invoke(__proj, __hi),
3232 std::__invoke(__proj, __lo))));
3233 auto&& __proj_val = std::__invoke(__proj, __val);
3234 if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo)))
3235 return __lo;
3236 else if (std::__invoke(__comp, std::__invoke(__proj, __hi), __proj_val))
3237 return __hi;
3238 else
3239 return __val;
3240 }
3241 };
3242
3243 inline constexpr __clamp_fn clamp{};
3244
3245 template<typename _Tp>
3246 struct min_max_result
3247 {
3248 [[no_unique_address]] _Tp min;
3249 [[no_unique_address]] _Tp max;
3250
3251 template<typename _Tp2>
3252 requires convertible_to<const _Tp&, _Tp2>
3253 constexpr
3254 operator min_max_result<_Tp2>() const &
3255 { return {min, max}; }
3256
3257 template<typename _Tp2>
3258 requires convertible_to<_Tp, _Tp2>
3259 constexpr
3260 operator min_max_result<_Tp2>() &&
3261 { return {std::move(min), std::move(max)}; }
3262 };
3263
3264 template<typename _Tp>
3265 using minmax_result = min_max_result<_Tp>;
3266
3267 struct __minmax_fn
3268 {
3269 template<typename _Tp, typename _Proj = identity,
3270 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3271 _Comp = ranges::less>
3272 constexpr minmax_result<const _Tp&>
3273 operator()(const _Tp& __a, const _Tp& __b,
3274 _Comp __comp = {}, _Proj __proj = {}) const
3275 {
3276 if (std::__invoke(__comp,
3277 std::__invoke(__proj, __b),
3278 std::__invoke(__proj, __a)))
3279 return {__b, __a};
3280 else
3281 return {__a, __b};
3282 }
3283
3284 template<input_range _Range, typename _Proj = identity,
3285 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3286 _Comp = ranges::less>
3287 requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
3288 constexpr minmax_result<range_value_t<_Range>>
3289 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3290 {
3291 auto __first = ranges::begin(__r);
3292 auto __last = ranges::end(__r);
3293 __glibcxx_assert(__first != __last);
3294 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3295 minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
3296 if (++__first == __last)
3297 return __result;
3298 else
3299 {
3300 // At this point __result.min == __result.max, so a single
3301 // comparison with the next element suffices.
3302 auto&& __val = *__first;
3303 if (__comp_proj(__val, __result.min))
3304 __result.min = std::forward<decltype(__val)>(__val);
3305 else
3306 __result.max = std::forward<decltype(__val)>(__val);
3307 }
3308 while (++__first != __last)
3309 {
3310 // Now process two elements at a time so that we perform at most
3311 // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2
3312 // iterations of this loop performs three comparisons).
3313 range_value_t<_Range> __val1 = *__first;
3314 if (++__first == __last)
3315 {
3316 // N is odd; in this final iteration, we perform at most two
3317 // comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons,
3318 // which is not more than 3*N/2, as required.
3319 if (__comp_proj(__val1, __result.min))
3320 __result.min = std::move(__val1);
3321 else if (!__comp_proj(__val1, __result.max))
3322 __result.max = std::move(__val1);
3323 break;
3324 }
3325 auto&& __val2 = *__first;
3326 if (!__comp_proj(__val2, __val1))
3327 {
3328 if (__comp_proj(__val1, __result.min))
3329 __result.min = std::move(__val1);
3330 if (!__comp_proj(__val2, __result.max))
3331 __result.max = std::forward<decltype(__val2)>(__val2);
3332 }
3333 else
3334 {
3335 if (__comp_proj(__val2, __result.min))
3336 __result.min = std::forward<decltype(__val2)>(__val2);
3337 if (!__comp_proj(__val1, __result.max))
3338 __result.max = std::move(__val1);
3339 }
3340 }
3341 return __result;
3342 }
3343
3344 template<copyable _Tp, typename _Proj = identity,
3345 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3346 _Comp = ranges::less>
3347 constexpr minmax_result<_Tp>
3348 operator()(initializer_list<_Tp> __r,
3349 _Comp __comp = {}, _Proj __proj = {}) const
3350 {
3351 return (*this)(ranges::subrange(__r),
3352 std::move(__comp), std::move(__proj));
3353 }
3354 };
3355
3356 inline constexpr __minmax_fn minmax{};
3357
3358 struct __min_element_fn
3359 {
3360 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3361 typename _Proj = identity,
3362 indirect_strict_weak_order<projected<_Iter, _Proj>>
3363 _Comp = ranges::less>
3364 constexpr _Iter
3365 operator()(_Iter __first, _Sent __last,
3366 _Comp __comp = {}, _Proj __proj = {}) const
3367 {
3368 if (__first == __last)
3369 return __first;
3370
3371 auto __i = __first;
3372 while (++__i != __last)
3373 {
3374 if (std::__invoke(__comp,
3375 std::__invoke(__proj, *__i),
3376 std::__invoke(__proj, *__first)))
3377 __first = __i;
3378 }
3379 return __first;
3380 }
3381
3382 template<forward_range _Range, typename _Proj = identity,
3383 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3384 _Comp = ranges::less>
3385 constexpr borrowed_iterator_t<_Range>
3386 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3387 {
3388 return (*this)(ranges::begin(__r), ranges::end(__r),
3389 std::move(__comp), std::move(__proj));
3390 }
3391 };
3392
3393 inline constexpr __min_element_fn min_element{};
3394
3395 struct __max_element_fn
3396 {
3397 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3398 typename _Proj = identity,
3399 indirect_strict_weak_order<projected<_Iter, _Proj>>
3400 _Comp = ranges::less>
3401 constexpr _Iter
3402 operator()(_Iter __first, _Sent __last,
3403 _Comp __comp = {}, _Proj __proj = {}) const
3404 {
3405 if (__first == __last)
3406 return __first;
3407
3408 auto __i = __first;
3409 while (++__i != __last)
3410 {
3411 if (std::__invoke(__comp,
3412 std::__invoke(__proj, *__first),
3413 std::__invoke(__proj, *__i)))
3414 __first = __i;
3415 }
3416 return __first;
3417 }
3418
3419 template<forward_range _Range, typename _Proj = identity,
3420 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3421 _Comp = ranges::less>
3422 constexpr borrowed_iterator_t<_Range>
3423 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3424 {
3425 return (*this)(ranges::begin(__r), ranges::end(__r),
3426 std::move(__comp), std::move(__proj));
3427 }
3428 };
3429
3430 inline constexpr __max_element_fn max_element{};
3431
3432 template<typename _Iter>
3433 using minmax_element_result = min_max_result<_Iter>;
3434
3435 struct __minmax_element_fn
3436 {
3437 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3438 typename _Proj = identity,
3439 indirect_strict_weak_order<projected<_Iter, _Proj>>
3440 _Comp = ranges::less>
3441 constexpr minmax_element_result<_Iter>
3442 operator()(_Iter __first, _Sent __last,
3443 _Comp __comp = {}, _Proj __proj = {}) const
3444 {
3445 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3446 minmax_element_result<_Iter> __result = {__first, __first};
3447 if (__first == __last || ++__first == __last)
3448 return __result;
3449 else
3450 {
3451 // At this point __result.min == __result.max, so a single
3452 // comparison with the next element suffices.
3453 if (__comp_proj(*__first, *__result.min))
3454 __result.min = __first;
3455 else
3456 __result.max = __first;
3457 }
3458 while (++__first != __last)
3459 {
3460 // Now process two elements at a time so that we perform at most
3461 // 1 + 3*(N-2)/2 comparisons in total (each of the (N-2)/2
3462 // iterations of this loop performs three comparisons).
3463 auto __prev = __first;
3464 if (++__first == __last)
3465 {
3466 // N is odd; in this final iteration, we perform at most two
3467 // comparisons, for a total of 1 + 3*(N-3)/2 + 2 comparisons,
3468 // which is not more than 3*N/2, as required.
3469 if (__comp_proj(*__prev, *__result.min))
3470 __result.min = __prev;
3471 else if (!__comp_proj(*__prev, *__result.max))
3472 __result.max = __prev;
3473 break;
3474 }
3475 if (!__comp_proj(*__first, *__prev))
3476 {
3477 if (__comp_proj(*__prev, *__result.min))
3478 __result.min = __prev;
3479 if (!__comp_proj(*__first, *__result.max))
3480 __result.max = __first;
3481 }
3482 else
3483 {
3484 if (__comp_proj(*__first, *__result.min))
3485 __result.min = __first;
3486 if (!__comp_proj(*__prev, *__result.max))
3487 __result.max = __prev;
3488 }
3489 }
3490 return __result;
3491 }
3492
3493 template<forward_range _Range, typename _Proj = identity,
3494 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3495 _Comp = ranges::less>
3496 constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3497 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3498 {
3499 return (*this)(ranges::begin(__r), ranges::end(__r),
3500 std::move(__comp), std::move(__proj));
3501 }
3502 };
3503
3504 inline constexpr __minmax_element_fn minmax_element{};
3505
3506 struct __lexicographical_compare_fn
3507 {
3508 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3509 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3510 typename _Proj1 = identity, typename _Proj2 = identity,
3511 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3512 projected<_Iter2, _Proj2>>
3513 _Comp = ranges::less>
3514 constexpr bool
3515 operator()(_Iter1 __first1, _Sent1 __last1,
3516 _Iter2 __first2, _Sent2 __last2,
3517 _Comp __comp = {},
3518 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3519 {
3520 if constexpr (__detail::__is_normal_iterator<_Iter1>
3521 && same_as<_Iter1, _Sent1>)
3522 return (*this)(__first1.base(), __last1.base(),
3523 std::move(__first2), std::move(__last2),
3524 std::move(__comp),
3525 std::move(__proj1), std::move(__proj2));
3526 else if constexpr (__detail::__is_normal_iterator<_Iter2>
3527 && same_as<_Iter2, _Sent2>)
3528 return (*this)(std::move(__first1), std::move(__last1),
3529 __first2.base(), __last2.base(),
3530 std::move(__comp),
3531 std::move(__proj1), std::move(__proj2));
3532 else
3533 {
3534 constexpr bool __sized_iters
3535 = (sized_sentinel_for<_Sent1, _Iter1>
3536 && sized_sentinel_for<_Sent2, _Iter2>);
3537 if constexpr (__sized_iters)
3538 {
3539 using _ValueType1 = iter_value_t<_Iter1>;
3540 using _ValueType2 = iter_value_t<_Iter2>;
3541 // This condition is consistent with the one in
3542 // __lexicographical_compare_aux in <bits/stl_algobase.h>.
3543 constexpr bool __use_memcmp
3544 = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3545 && __ptr_to_nonvolatile<_Iter1>
3546 && __ptr_to_nonvolatile<_Iter2>
3547 && (is_same_v<_Comp, ranges::less>
3548 || is_same_v<_Comp, ranges::greater>)
3549 && is_same_v<_Proj1, identity>
3550 && is_same_v<_Proj2, identity>);
3551 if constexpr (__use_memcmp)
3552 {
3553 const auto __d1 = __last1 - __first1;
3554 const auto __d2 = __last2 - __first2;
3555
3556 if (const auto __len = std::min(__d1, __d2))
3557 {
3558 const auto __c
3559 = std::__memcmp(__first1, __first2, __len);
3560 if constexpr (is_same_v<_Comp, ranges::less>)
3561 {
3562 if (__c < 0)
3563 return true;
3564 if (__c > 0)
3565 return false;
3566 }
3567 else if constexpr (is_same_v<_Comp, ranges::greater>)
3568 {
3569 if (__c > 0)
3570 return true;
3571 if (__c < 0)
3572 return false;
3573 }
3574 }
3575 return __d1 < __d2;
3576 }
3577 }
3578
3579 for (; __first1 != __last1 && __first2 != __last2;
3580 ++__first1, (void) ++__first2)
3581 {
3582 if (std::__invoke(__comp,
3583 std::__invoke(__proj1, *__first1),
3584 std::__invoke(__proj2, *__first2)))
3585 return true;
3586 if (std::__invoke(__comp,
3587 std::__invoke(__proj2, *__first2),
3588 std::__invoke(__proj1, *__first1)))
3589 return false;
3590 }
3591 return __first1 == __last1 && __first2 != __last2;
3592 }
3593 }
3594
3595 template<input_range _Range1, input_range _Range2,
3596 typename _Proj1 = identity, typename _Proj2 = identity,
3597 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3598 projected<iterator_t<_Range2>, _Proj2>>
3599 _Comp = ranges::less>
3600 constexpr bool
3601 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3602 _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const
3603 {
3604 return (*this)(ranges::begin(__r1), ranges::end(__r1),
3605 ranges::begin(__r2), ranges::end(__r2),
3606 std::move(__comp),
3607 std::move(__proj1), std::move(__proj2));
3608 }
3609
3610 private:
3611 template<typename _Iter, typename _Ref = iter_reference_t<_Iter>>
3612 static constexpr bool __ptr_to_nonvolatile
3613 = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3614 };
3615
3616 inline constexpr __lexicographical_compare_fn lexicographical_compare;
3617
3618 template<typename _Iter>
3619 struct in_found_result
3620 {
3621 [[no_unique_address]] _Iter in;
3622 bool found;
3623
3624 template<typename _Iter2>
3625 requires convertible_to<const _Iter&, _Iter2>
3626 constexpr
3627 operator in_found_result<_Iter2>() const &
3628 { return {in, found}; }
3629
3630 template<typename _Iter2>
3631 requires convertible_to<_Iter, _Iter2>
3632 constexpr
3633 operator in_found_result<_Iter2>() &&
3634 { return {std::move(in), found}; }
3635 };
3636
3637 template<typename _Iter>
3638 using next_permutation_result = in_found_result<_Iter>;
3639
3640 struct __next_permutation_fn
3641 {
3642 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3643 typename _Comp = ranges::less, typename _Proj = identity>
3644 requires sortable<_Iter, _Comp, _Proj>
3645 constexpr next_permutation_result<_Iter>
3646 operator()(_Iter __first, _Sent __last,
3647 _Comp __comp = {}, _Proj __proj = {}) const
3648 {
3649 if (__first == __last)
3650 return {std::move(__first), false};
3651
3652 auto __i = __first;
3653 ++__i;
3654 if (__i == __last)
3655 return {std::move(__i), false};
3656
3657 auto __lasti = ranges::next(__first, __last);
3658 __i = __lasti;
3659 --__i;
3660
3661 for (;;)
3662 {
3663 auto __ii = __i;
3664 --__i;
3665 if (std::__invoke(__comp,
3666 std::__invoke(__proj, *__i),
3667 std::__invoke(__proj, *__ii)))
3668 {
3669 auto __j = __lasti;
3670 while (!(bool)std::__invoke(__comp,
3671 std::__invoke(__proj, *__i),
3672 std::__invoke(__proj, *--__j)))
3673 ;
3674 ranges::iter_swap(__i, __j);
3675 ranges::reverse(__ii, __last);
3676 return {std::move(__lasti), true};
3677 }
3678 if (__i == __first)
3679 {
3680 ranges::reverse(__first, __last);
3681 return {std::move(__lasti), false};
3682 }
3683 }
3684 }
3685
3686 template<bidirectional_range _Range, typename _Comp = ranges::less,
3687 typename _Proj = identity>
3688 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3689 constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3690 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3691 {
3692 return (*this)(ranges::begin(__r), ranges::end(__r),
3693 std::move(__comp), std::move(__proj));
3694 }
3695 };
3696
3697 inline constexpr __next_permutation_fn next_permutation{};
3698
3699 template<typename _Iter>
3700 using prev_permutation_result = in_found_result<_Iter>;
3701
3702 struct __prev_permutation_fn
3703 {
3704 template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3705 typename _Comp = ranges::less, typename _Proj = identity>
3706 requires sortable<_Iter, _Comp, _Proj>
3707 constexpr prev_permutation_result<_Iter>
3708 operator()(_Iter __first, _Sent __last,
3709 _Comp __comp = {}, _Proj __proj = {}) const
3710 {
3711 if (__first == __last)
3712 return {std::move(__first), false};
3713
3714 auto __i = __first;
3715 ++__i;
3716 if (__i == __last)
3717 return {std::move(__i), false};
3718
3719 auto __lasti = ranges::next(__first, __last);
3720 __i = __lasti;
3721 --__i;
3722
3723 for (;;)
3724 {
3725 auto __ii = __i;
3726 --__i;
3727 if (std::__invoke(__comp,
3728 std::__invoke(__proj, *__ii),
3729 std::__invoke(__proj, *__i)))
3730 {
3731 auto __j = __lasti;
3732 while (!(bool)std::__invoke(__comp,
3733 std::__invoke(__proj, *--__j),
3734 std::__invoke(__proj, *__i)))
3735 ;
3736 ranges::iter_swap(__i, __j);
3737 ranges::reverse(__ii, __last);
3738 return {std::move(__lasti), true};
3739 }
3740 if (__i == __first)
3741 {
3742 ranges::reverse(__first, __last);
3743 return {std::move(__lasti), false};
3744 }
3745 }
3746 }
3747
3748 template<bidirectional_range _Range, typename _Comp = ranges::less,
3749 typename _Proj = identity>
3750 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3751 constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3752 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const
3753 {
3754 return (*this)(ranges::begin(__r), ranges::end(__r),
3755 std::move(__comp), std::move(__proj));
3756 }
3757 };
3758
3759 inline constexpr __prev_permutation_fn prev_permutation{};
3760
3761 } // namespace ranges
3762
3763 #define __cpp_lib_shift 201806L
3764 template<typename _ForwardIterator>
3765 constexpr _ForwardIterator
3766 shift_left(_ForwardIterator __first, _ForwardIterator __last,
3767 typename iterator_traits<_ForwardIterator>::difference_type __n)
3768 {
3769 __glibcxx_assert(__n >= 0);
3770 if (__n == 0)
3771 return __last;
3772
3773 auto __mid = ranges::next(__first, __n, __last);
3774 if (__mid == __last)
3775 return __first;
3776 return std::move(std::move(__mid), std::move(__last), std::move(__first));
3777 }
3778
3779 template<typename _ForwardIterator>
3780 constexpr _ForwardIterator
3781 shift_right(_ForwardIterator __first, _ForwardIterator __last,
3782 typename iterator_traits<_ForwardIterator>::difference_type __n)
3783 {
3784 __glibcxx_assert(__n >= 0);
3785 if (__n == 0)
3786 return __first;
3787
3788 using _Cat
3789 = typename iterator_traits<_ForwardIterator>::iterator_category;
3790 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
3791 {
3792 auto __mid = ranges::next(__last, -__n, __first);
3793 if (__mid == __first)
3794 return __last;
3795
3796 return std::move_backward(std::move(__first), std::move(__mid),
3797 std::move(__last));
3798 }
3799 else
3800 {
3801 auto __result = ranges::next(__first, __n, __last);
3802 if (__result == __last)
3803 return __last;
3804
3805 auto __dest_head = __first, __dest_tail = __result;
3806 while (__dest_head != __result)
3807 {
3808 if (__dest_tail == __last)
3809 {
3810 // If we get here, then we must have
3811 // 2*n >= distance(__first, __last)
3812 // i.e. we are shifting out at least half of the range. In
3813 // this case we can safely perform the shift with a single
3814 // move.
3815 std::move(std::move(__first), std::move(__dest_head), __result);
3816 return __result;
3817 }
3818 ++__dest_head;
3819 ++__dest_tail;
3820 }
3821
3822 for (;;)
3823 {
3824 // At the start of each iteration of this outer loop, the range
3825 // [__first, __result) contains those elements that after shifting
3826 // the whole range right by __n, should end up in
3827 // [__dest_head, __dest_tail) in order.
3828
3829 // The below inner loop swaps the elements of [__first, __result)
3830 // and [__dest_head, __dest_tail), while simultaneously shifting
3831 // the latter range by __n.
3832 auto __cursor = __first;
3833 while (__cursor != __result)
3834 {
3835 if (__dest_tail == __last)
3836 {
3837 // At this point the ranges [__first, result) and
3838 // [__dest_head, dest_tail) are disjoint, so we can safely
3839 // move the remaining elements.
3840 __dest_head = std::move(__cursor, __result,
3841 std::move(__dest_head));
3842 std::move(std::move(__first), std::move(__cursor),
3843 std::move(__dest_head));
3844 return __result;
3845 }
3846 std::iter_swap(__cursor, __dest_head);
3847 ++__dest_head;
3848 ++__dest_tail;
3849 ++__cursor;
3850 }
3851 }
3852 }
3853 }
3854
3855 _GLIBCXX_END_NAMESPACE_VERSION
3856 } // namespace std
3857 #endif // concepts
3858 #endif // C++20
3859 #endif // _RANGES_ALGO_H
3860