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