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