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