31#define _RANGES_ALGO_H 1
33#if __cplusplus > 201703L
35#if __cplusplus > 202002L
43namespace std _GLIBCXX_VISIBILITY(default)
45_GLIBCXX_BEGIN_NAMESPACE_VERSION
50 template<
typename _Comp,
typename _Proj>
52 __make_comp_proj(_Comp& __comp, _Proj& __proj)
54 return [&] (
auto&& __lhs,
auto&& __rhs) ->
bool {
55 using _TL =
decltype(__lhs);
56 using _TR =
decltype(__rhs);
63 template<
typename _Pred,
typename _Proj>
65 __make_pred_proj(_Pred& __pred, _Proj& __proj)
67 return [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
76 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
77 typename _Proj =
identity,
78 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
80 operator()(_Iter __first, _Sent __last,
81 _Pred __pred, _Proj __proj = {})
const
83 for (; __first != __last; ++__first)
89 template<input_range _Range,
typename _Proj = identity,
90 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
93 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
95 return (*
this)(ranges::begin(__r), ranges::end(__r),
100 inline constexpr __all_of_fn all_of{};
104 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
105 typename _Proj =
identity,
106 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
108 operator()(_Iter __first, _Sent __last,
109 _Pred __pred, _Proj __proj = {})
const
111 for (; __first != __last; ++__first)
117 template<input_range _Range,
typename _Proj = identity,
118 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
121 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
123 return (*
this)(ranges::begin(__r), ranges::end(__r),
128 inline constexpr __any_of_fn any_of{};
132 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
133 typename _Proj =
identity,
134 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
136 operator()(_Iter __first, _Sent __last,
137 _Pred __pred, _Proj __proj = {})
const
139 for (; __first != __last; ++__first)
145 template<input_range _Range,
typename _Proj = identity,
146 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
149 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
151 return (*
this)(ranges::begin(__r), ranges::end(__r),
156 inline constexpr __none_of_fn none_of{};
158 template<
typename _Iter,
typename _Fp>
161 [[no_unique_address]] _Iter in;
162 [[no_unique_address]] _Fp fun;
164 template<
typename _Iter2,
typename _F2p>
165 requires convertible_to<const _Iter&, _Iter2>
166 && convertible_to<const _Fp&, _F2p>
168 operator in_fun_result<_Iter2, _F2p>() const &
169 {
return {in, fun}; }
171 template<
typename _Iter2,
typename _F2p>
172 requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
174 operator in_fun_result<_Iter2, _F2p>() &&
178 template<
typename _Iter,
typename _Fp>
179 using for_each_result = in_fun_result<_Iter, _Fp>;
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
189 for (; __first != __last; ++__first)
194 template<input_range _Range,
typename _Proj = identity,
195 indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
197 constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun>
198 operator()(_Range&& __r, _Fun __f, _Proj __proj = {})
const
200 return (*
this)(ranges::begin(__r), ranges::end(__r),
205 inline constexpr __for_each_fn for_each{};
207 template<
typename _Iter,
typename _Fp>
208 using for_each_n_result = in_fun_result<_Iter, _Fp>;
210 struct __for_each_n_fn
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
218 if constexpr (random_access_iterator<_Iter>)
222 auto __last = __first + __n;
238 inline constexpr __for_each_n_fn for_each_n{};
242 struct __find_first_of_fn
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>
250 operator()(_Iter1 __first1, _Sent1 __last1,
251 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
252 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
254 for (; __first1 != __last1; ++__first1)
255 for (
auto __iter = __first2; __iter != __last2; ++__iter)
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
272 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
273 ranges::begin(__r2), ranges::end(__r2),
279 inline constexpr __find_first_of_fn find_first_of{};
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>,
289 constexpr iter_difference_t<_Iter>
290 operator()(_Iter __first, _Sent __last,
291 const _Tp& __value, _Proj __proj = {})
const
293 iter_difference_t<_Iter> __n = 0;
294 for (; __first != __last; ++__first)
300 template<input_range _Range,
typename _Proj = identity,
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>,
306 constexpr range_difference_t<_Range>
307 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
309 return (*
this)(ranges::begin(__r), ranges::end(__r),
314 inline constexpr __count_fn count{};
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
325 iter_difference_t<_Iter> __n = 0;
326 for (; __first != __last; ++__first)
332 template<input_range _Range,
333 typename _Proj = identity,
334 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
336 constexpr range_difference_t<_Range>
337 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
339 return (*
this)(ranges::begin(__r), ranges::end(__r),
344 inline constexpr __count_if_fn count_if{};
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
359 return {__first, __first};
361 auto __value_comp = [&] <
typename _Rp> (_Rp&& __arg) ->
bool {
366 __first = ranges::find_if(
std::move(__first), __last,
369 if (__first == __last)
370 return {__first, __first};
373 auto __end = __first;
374 return {__first, ++__end};
378 if constexpr (sized_sentinel_for<_Sent, _Iter>
379 && random_access_iterator<_Iter>)
381 auto __tail_size = __last - __first;
382 auto __remainder = __count;
384 while (__remainder <= __tail_size)
386 __first += __remainder;
387 __tail_size -= __remainder;
388 auto __backtrack = __first;
391 if (--__remainder == 0)
392 return {__first - __count, __first};
394 __remainder = __count + 1 - (__first - __backtrack);
396 auto __i = __first + __tail_size;
401 __first = ranges::find_if(__first, __last, __value_comp, __proj);
402 while (__first != __last)
407 while (__i != __last && __n != 1
414 return {__first, __i};
417 __first = ranges::find_if(++__i, __last, __value_comp, __proj);
419 return {__first, __first};
423 template<forward_range _Range,
424 typename _Pred = ranges::equal_to,
typename _Proj = identity,
426 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
427 requires indirectly_comparable<iterator_t<_Range>,
const _Tp*,
429 constexpr borrowed_subrange_t<_Range>
430 operator()(_Range&& __r, range_difference_t<_Range> __count,
431 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const
433 return (*
this)(ranges::begin(__r), ranges::end(__r),
439 inline constexpr __search_n_fn search_n{};
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
453 if constexpr (bidirectional_iterator<_Iter1>
454 && bidirectional_iterator<_Iter2>)
456 auto __i1 = ranges::next(__first1, __last1);
457 auto __i2 = ranges::next(__first2, __last2);
459 = ranges::search(reverse_iterator<_Iter1>{__i1},
460 reverse_iterator<_Iter1>{__first1},
461 reverse_iterator<_Iter2>{__i2},
462 reverse_iterator<_Iter2>{__first2},
465 auto __result_first = ranges::end(__rresult).base();
466 auto __result_last = ranges::begin(__rresult).base();
467 if (__result_last == __first1)
470 return {__result_first, __result_last};
474 auto __i = ranges::next(__first1, __last1);
475 if (__first2 == __last2)
478 auto __result_begin = __i;
479 auto __result_end = __i;
482 auto __new_range = ranges::search(__first1, __last1,
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};
491 __result_begin = __new_result_begin;
492 __result_end = __new_result_end;
493 __first1 = __result_begin;
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
509 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
510 ranges::begin(__r2), ranges::end(__r2),
516 inline constexpr __find_end_fn find_end{};
520 struct __is_permutation_fn
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
529 operator()(_Iter1 __first1, _Sent1 __last1,
530 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
531 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
533 constexpr bool __sized_iters
534 = (sized_sentinel_for<_Sent1, _Iter1>
535 && sized_sentinel_for<_Sent2, _Iter2>);
536 if constexpr (__sized_iters)
538 auto __d1 = ranges::distance(__first1, __last1);
539 auto __d2 = ranges::distance(__first2, __last2);
546 for (; __first1 != __last1 && __first2 != __last2;
547 ++__first1, (void)++__first2)
553 if constexpr (__sized_iters)
555 if (__first1 == __last1)
560 auto __d1 = ranges::distance(__first1, __last1);
561 auto __d2 = ranges::distance(__first2, __last2);
562 if (__d1 == 0 && __d2 == 0)
568 for (
auto __scan = __first1; __scan != __last1; ++__scan)
571 auto __comp_scan = [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
575 if (__scan != ranges::find_if(__first1, __scan,
576 __comp_scan, __proj1))
579 auto __matches = ranges::count_if(__first2, __last2,
580 __comp_scan, __proj2);
582 || ranges::count_if(__scan, __last1,
583 __comp_scan, __proj1) != __matches)
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>
595 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
596 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
600 if constexpr (sized_range<_Range1>)
601 if constexpr (sized_range<_Range2>)
602 if (ranges::distance(__r1) != ranges::distance(__r2))
605 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
606 ranges::begin(__r2), ranges::end(__r2),
612 inline constexpr __is_permutation_fn is_permutation{};
614 template<
typename _Iter,
typename _Out>
615 using copy_if_result = in_out_result<_Iter, _Out>;
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
627 for (; __first != __last; ++__first)
630 *__result = *__first;
636 template<input_range _Range, weakly_incrementable _Out,
637 typename _Proj = identity,
638 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
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
645 return (*
this)(ranges::begin(__r), ranges::end(__r),
651 inline constexpr __copy_if_fn copy_if{};
653 template<
typename _Iter1,
typename _Iter2>
654 using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
656 struct __swap_ranges_fn
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
665 for (; __first1 != __last1 && __first2 != __last2;
666 ++__first1, (void)++__first2)
667 ranges::iter_swap(__first1, __first2);
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
677 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
678 ranges::begin(__r2), ranges::end(__r2));
682 inline constexpr __swap_ranges_fn swap_ranges{};
684 template<
typename _Iter,
typename _Out>
685 using unary_transform_result = in_out_result<_Iter, _Out>;
687 template<
typename _Iter1,
typename _Iter2,
typename _Out>
688 struct in_in_out_result
690 [[no_unique_address]] _Iter1 in1;
691 [[no_unique_address]] _Iter2 in2;
692 [[no_unique_address]] _Out out;
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>
699 operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
700 {
return {in1, in2, out}; }
702 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
703 requires convertible_to<_Iter1, _IIter1>
704 && convertible_to<_Iter2, _IIter2>
705 && convertible_to<_Out, _OOut>
707 operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
711 template<
typename _Iter1,
typename _Iter2,
typename _Out>
712 using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
714 struct __transform_fn
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
726 for (; __first1 != __last1; ++__first1, (void)++__result)
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
739 return (*
this)(ranges::begin(__r), ranges::end(__r),
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
758 for (; __first1 != __last1 && __first2 != __last2;
759 ++__first1, (void)++__first2, ++__result)
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
778 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
779 ranges::begin(__r2), ranges::end(__r2),
785 inline constexpr __transform_fn transform{};
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>,
797 operator()(_Iter __first, _Sent __last,
798 const _Tp1& __old_value,
const _Tp2& __new_value,
799 _Proj __proj = {})
const
801 for (; __first != __last; ++__first)
803 *__first = __new_value;
807 template<input_range _Range,
typename _Proj = identity,
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>,
815 constexpr borrowed_iterator_t<_Range>
816 operator()(_Range&& __r,
817 const _Tp1& __old_value,
const _Tp2& __new_value,
818 _Proj __proj = {})
const
820 return (*
this)(ranges::begin(__r), ranges::end(__r),
821 __old_value, __new_value,
std::move(__proj));
825 inline constexpr __replace_fn replace{};
827 struct __replace_if_fn
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&>
835 operator()(_Iter __first, _Sent __last,
836 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
838 for (; __first != __last; ++__first)
840 *__first = __new_value;
844 template<input_range _Range,
typename _Proj = identity,
846 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
847 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
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
854 return (*
this)(ranges::begin(__r), ranges::end(__r),
859 inline constexpr __replace_if_fn replace_if{};
861 template<
typename _Iter,
typename _Out>
862 using replace_copy_result = in_out_result<_Iter, _Out>;
864 struct __replace_copy_fn
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
879 for (; __first != __last; ++__first, (void)++__result)
881 *__result = __new_value;
883 *__result = *__first;
887 template<input_range _Range,
typename _Out,
888 typename _Proj = identity,
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>,
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
902 return (*
this)(ranges::begin(__r), ranges::end(__r),
908 inline constexpr __replace_copy_fn replace_copy{};
910 template<
typename _Iter,
typename _Out>
911 using replace_copy_if_result = in_out_result<_Iter, _Out>;
913 struct __replace_copy_if_fn
915 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
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
926 for (; __first != __last; ++__first, (void)++__result)
928 *__result = __new_value;
930 *__result = *__first;
934 template<input_range _Range,
936 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>),
937 typename _Proj = identity,
938 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
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
946 return (*
this)(ranges::begin(__r), ranges::end(__r),
952 inline constexpr __replace_copy_if_fn replace_copy_if{};
954 struct __generate_n_fn
956 template<input_or_output_iterator _Out, copy_constructible _Fp>
957 requires invocable<_Fp&>
958 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
960 operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen)
const
962 for (; __n > 0; --__n, (void)++__first)
968 inline constexpr __generate_n_fn generate_n{};
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&>>
977 operator()(_Out __first, _Sent __last, _Fp __gen)
const
979 for (; __first != __last; ++__first)
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
989 return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__gen));
993 inline constexpr __generate_fn generate{};
995 struct __remove_if_fn
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
1004 __first = ranges::find_if(__first, __last, __pred, __proj);
1005 if (__first == __last)
1006 return {__first, __first};
1008 auto __result = __first;
1010 for (; __first != __last; ++__first)
1017 return {__result, __first};
1020 template<forward_range _Range,
typename _Proj = identity,
1021 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1023 requires permutable<iterator_t<_Range>>
1024 constexpr borrowed_subrange_t<_Range>
1025 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
1027 return (*
this)(ranges::begin(__r), ranges::end(__r),
1032 inline constexpr __remove_if_fn remove_if{};
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>,
1042 constexpr subrange<_Iter>
1043 operator()(_Iter __first, _Sent __last,
1044 const _Tp& __value, _Proj __proj = {})
const
1046 auto __pred = [&] (
auto&& __arg) ->
bool {
1049 return ranges::remove_if(__first, __last,
1053 template<forward_range _Range,
typename _Proj = identity,
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>,
1060 constexpr borrowed_subrange_t<_Range>
1061 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
1063 return (*
this)(ranges::begin(__r), ranges::end(__r),
1068 inline constexpr __remove_fn remove{};
1070 template<
typename _Iter,
typename _Out>
1071 using remove_copy_if_result = in_out_result<_Iter, _Out>;
1073 struct __remove_copy_if_fn
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
1083 for (; __first != __last; ++__first)
1086 *__result = *__first;
1092 template<input_range _Range, weakly_incrementable _Out,
1093 typename _Proj = identity,
1094 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
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
1101 return (*
this)(ranges::begin(__r), ranges::end(__r),
1107 inline constexpr __remove_copy_if_fn remove_copy_if{};
1109 template<
typename _Iter,
typename _Out>
1110 using remove_copy_result = in_out_result<_Iter, _Out>;
1112 struct __remove_copy_fn
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>,
1121 constexpr remove_copy_result<_Iter, _Out>
1122 operator()(_Iter __first, _Sent __last, _Out __result,
1123 const _Tp& __value, _Proj __proj = {})
const
1125 for (; __first != __last; ++__first)
1128 *__result = *__first;
1134 template<input_range _Range, weakly_incrementable _Out,
1135 typename _Proj = identity,
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>,
1142 constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
1143 operator()(_Range&& __r, _Out __result,
1144 const _Tp& __value, _Proj __proj = {})
const
1146 return (*
this)(ranges::begin(__r), ranges::end(__r),
1151 inline constexpr __remove_copy_fn remove_copy{};
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
1163 __first = ranges::adjacent_find(__first, __last, __comp, __proj);
1164 if (__first == __last)
1165 return {__first, __first};
1167 auto __dest = __first;
1169 while (++__first != __last)
1174 return {++__dest, __first};
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
1184 return (*
this)(ranges::begin(__r), ranges::end(__r),
1189 inline constexpr __unique_fn unique{};
1193 template<
typename _Out,
typename _Tp>
1194 concept __can_reread_output = input_iterator<_Out>
1195 && same_as<_Tp, iter_value_t<_Out>>;
1198 template<
typename _Iter,
typename _Out>
1199 using unique_copy_result = in_out_result<_Iter, _Out>;
1201 struct __unique_copy_fn
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
1215 if (__first == __last)
1219 if constexpr (forward_iterator<_Iter>)
1221 auto __next = __first;
1222 *__result = *__next;
1223 while (++__next != __last)
1229 *++__result = *__first;
1233 else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
1235 *__result = *__first;
1236 while (++__first != __last)
1240 *++__result = *__first;
1245 auto __value = *__first;
1246 *__result = __value;
1247 while (++__first != __last)
1254 *++__result = __value;
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
1273 return (*
this)(ranges::begin(__r), ranges::end(__r),
1279 inline constexpr __unique_copy_fn unique_copy{};
1283 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1284 requires permutable<_Iter>
1286 operator()(_Iter __first, _Sent __last)
const
1288 auto __i = ranges::next(__first, __last);
1291 if constexpr (random_access_iterator<_Iter>)
1293 if (__first != __last)
1296 while (__first < __tail)
1298 ranges::iter_swap(__first, __tail);
1308 if (__first == __tail || __first == --__tail)
1312 ranges::iter_swap(__first, __tail);
1319 template<b
idirectional_range _Range>
1320 requires permutable<iterator_t<_Range>>
1321 constexpr borrowed_iterator_t<_Range>
1322 operator()(_Range&& __r)
const
1324 return (*
this)(ranges::begin(__r), ranges::end(__r));
1328 inline constexpr __reverse_fn reverse{};
1330 template<
typename _Iter,
typename _Out>
1331 using reverse_copy_result = in_out_result<_Iter, _Out>;
1333 struct __reverse_copy_fn
1335 template<b
idirectional_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
1341 auto __i = ranges::next(__first, __last);
1343 while (__first != __tail)
1346 *__result = *__tail;
1352 template<b
idirectional_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
1357 return (*
this)(ranges::begin(__r), ranges::end(__r),
1362 inline constexpr __reverse_copy_fn reverse_copy{};
1366 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1367 constexpr subrange<_Iter>
1368 operator()(_Iter __first, _Iter __middle, _Sent __last)
const
1370 auto __lasti = ranges::next(__first, __last);
1371 if (__first == __middle)
1372 return {__lasti, __lasti};
1373 if (__last == __middle)
1376 if constexpr (random_access_iterator<_Iter>)
1378 auto __n = __lasti - __first;
1379 auto __k = __middle - __first;
1381 if (__k == __n - __k)
1383 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1388 auto __ret = __first + (__lasti - __middle);
1392 if (__k < __n - __k)
1396 if constexpr (__is_pod(iter_value_t<_Iter>))
1400 ranges::move(__p + 1, __p + __n, __p);
1404 auto __q = __p + __k;
1405 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1407 ranges::iter_swap(__p, __q);
1414 ranges::swap(__n, __k);
1422 if constexpr (__is_pod(iter_value_t<_Iter>))
1426 ranges::move_backward(__p, __p + __n - 1, __p + __n);
1430 auto __q = __p + __n;
1432 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1436 ranges::iter_swap(__p, __q);
1441 std::swap(__n, __k);
1445 else if constexpr (bidirectional_iterator<_Iter>)
1447 auto __tail = __lasti;
1449 ranges::reverse(__first, __middle);
1450 ranges::reverse(__middle, __tail);
1452 while (__first != __middle && __middle != __tail)
1454 ranges::iter_swap(__first, --__tail);
1458 if (__first == __middle)
1460 ranges::reverse(__middle, __tail);
1465 ranges::reverse(__first, __middle);
1471 auto __first2 = __middle;
1474 ranges::iter_swap(__first, __first2);
1477 if (__first == __middle)
1478 __middle = __first2;
1479 }
while (__first2 != __last);
1481 auto __ret = __first;
1483 __first2 = __middle;
1485 while (__first2 != __last)
1487 ranges::iter_swap(__first, __first2);
1490 if (__first == __middle)
1491 __middle = __first2;
1492 else if (__first2 == __last)
1493 __first2 = __middle;
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
1504 return (*
this)(ranges::begin(__r),
std::move(__middle),
1509 inline constexpr __rotate_fn rotate{};
1511 template<
typename _Iter,
typename _Out>
1512 using rotate_copy_result = in_out_result<_Iter, _Out>;
1514 struct __rotate_copy_fn
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
1523 auto __copy1 = ranges::copy(__middle,
1526 auto __copy2 = ranges::copy(
std::move(__first),
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
1537 return (*
this)(ranges::begin(__r),
std::move(__middle),
1542 inline constexpr __rotate_copy_fn rotate_copy{};
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>
1552 operator()(_Iter __first, _Sent __last, _Out __out,
1553 iter_difference_t<_Iter> __n, _Gen&& __g)
const
1555 if constexpr (forward_iterator<_Iter>)
1559 auto __lasti = ranges::next(__first, __last);
1560 return _GLIBCXX_STD_A::
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)
1573 __out[__sample_sz++] = *__first;
1576 for (
auto __pop_sz = __sample_sz; __first != __last;
1577 ++__first, (void) ++__pop_sz)
1579 const auto __k = __d(__g, __param_type{0, __pop_sz});
1581 __out[__k] = *__first;
1583 return __out + __sample_sz;
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>
1592 operator()(_Range&& __r, _Out __out,
1593 range_difference_t<_Range> __n, _Gen&& __g)
const
1595 return (*
this)(ranges::begin(__r), ranges::end(__r),
1601 inline constexpr __sample_fn sample{};
1605 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1607 requires permutable<_Iter>
1608 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1610 operator()(_Iter __first, _Sent __last, _Gen&& __g)
const
1612 auto __lasti = ranges::next(__first, __last);
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
1623 return (*
this)(ranges::begin(__r), ranges::end(__r),
1628 inline constexpr __shuffle_fn shuffle{};
1630 struct __push_heap_fn
1632 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1633 typename _Comp = ranges::less,
typename _Proj =
identity>
1634 requires sortable<_Iter, _Comp, _Proj>
1636 operator()(_Iter __first, _Sent __last,
1637 _Comp __comp = {}, _Proj __proj = {})
const
1639 auto __lasti = ranges::next(__first, __last);
1640 std::push_heap(__first, __lasti,
1641 __detail::__make_comp_proj(__comp, __proj));
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
1651 return (*
this)(ranges::begin(__r), ranges::end(__r),
1656 inline constexpr __push_heap_fn push_heap{};
1658 struct __pop_heap_fn
1660 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1661 typename _Comp = ranges::less,
typename _Proj =
identity>
1662 requires sortable<_Iter, _Comp, _Proj>
1664 operator()(_Iter __first, _Sent __last,
1665 _Comp __comp = {}, _Proj __proj = {})
const
1667 auto __lasti = ranges::next(__first, __last);
1668 std::pop_heap(__first, __lasti,
1669 __detail::__make_comp_proj(__comp, __proj));
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
1679 return (*
this)(ranges::begin(__r), ranges::end(__r),
1684 inline constexpr __pop_heap_fn pop_heap{};
1686 struct __make_heap_fn
1688 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1689 typename _Comp = ranges::less,
typename _Proj =
identity>
1690 requires sortable<_Iter, _Comp, _Proj>
1692 operator()(_Iter __first, _Sent __last,
1693 _Comp __comp = {}, _Proj __proj = {})
const
1695 auto __lasti = ranges::next(__first, __last);
1696 std::make_heap(__first, __lasti,
1697 __detail::__make_comp_proj(__comp, __proj));
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
1707 return (*
this)(ranges::begin(__r), ranges::end(__r),
1712 inline constexpr __make_heap_fn make_heap{};
1714 struct __sort_heap_fn
1716 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1717 typename _Comp = ranges::less,
typename _Proj =
identity>
1718 requires sortable<_Iter, _Comp, _Proj>
1720 operator()(_Iter __first, _Sent __last,
1721 _Comp __comp = {}, _Proj __proj = {})
const
1723 auto __lasti = ranges::next(__first, __last);
1724 std::sort_heap(__first, __lasti,
1725 __detail::__make_comp_proj(__comp, __proj));
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
1735 return (*
this)(ranges::begin(__r), ranges::end(__r),
1740 inline constexpr __sort_heap_fn sort_heap{};
1742 struct __is_heap_until_fn
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>
1749 operator()(_Iter __first, _Sent __last,
1750 _Comp __comp = {}, _Proj __proj = {})
const
1752 iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
1753 iter_difference_t<_Iter> __parent = 0, __child = 1;
1754 for (; __child < __n; ++__child)
1758 return __first + __child;
1759 else if ((__child & 1) == 0)
1762 return __first + __n;
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
1772 return (*
this)(ranges::begin(__r), ranges::end(__r),
1777 inline constexpr __is_heap_until_fn is_heap_until{};
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>
1786 operator()(_Iter __first, _Sent __last,
1787 _Comp __comp = {}, _Proj __proj = {})
const
1790 == ranges::is_heap_until(__first, __last,
1795 template<random_access_range _Range,
1796 typename _Proj = identity,
1797 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1798 _Comp = ranges::less>
1800 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1802 return (*
this)(ranges::begin(__r), ranges::end(__r),
1807 inline constexpr __is_heap_fn is_heap{};
1811 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1812 typename _Comp = ranges::less,
typename _Proj =
identity>
1813 requires sortable<_Iter, _Comp, _Proj>
1815 operator()(_Iter __first, _Sent __last,
1816 _Comp __comp = {}, _Proj __proj = {})
const
1818 auto __lasti = ranges::next(__first, __last);
1819 _GLIBCXX_STD_A::sort(
std::move(__first), __lasti,
1820 __detail::__make_comp_proj(__comp, __proj));
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
1830 return (*
this)(ranges::begin(__r), ranges::end(__r),
1835 inline constexpr __sort_fn sort{};
1837 struct __stable_sort_fn
1839 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1840 typename _Comp = ranges::less,
typename _Proj =
identity>
1841 requires sortable<_Iter, _Comp, _Proj>
1843 operator()(_Iter __first, _Sent __last,
1844 _Comp __comp = {}, _Proj __proj = {})
const
1846 auto __lasti = ranges::next(__first, __last);
1847 std::stable_sort(
std::move(__first), __lasti,
1848 __detail::__make_comp_proj(__comp, __proj));
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
1858 return (*
this)(ranges::begin(__r), ranges::end(__r),
1863 inline constexpr __stable_sort_fn stable_sort{};
1865 struct __partial_sort_fn
1867 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1868 typename _Comp = ranges::less,
typename _Proj =
identity>
1869 requires sortable<_Iter, _Comp, _Proj>
1871 operator()(_Iter __first, _Iter __middle, _Sent __last,
1872 _Comp __comp = {}, _Proj __proj = {})
const
1874 if (__first == __middle)
1875 return ranges::next(__first, __last);
1877 ranges::make_heap(__first, __middle, __comp, __proj);
1878 auto __i = __middle;
1879 for (; __i != __last; ++__i)
1884 ranges::pop_heap(__first, __middle, __comp, __proj);
1885 ranges::iter_swap(__middle-1, __i);
1886 ranges::push_heap(__first, __middle, __comp, __proj);
1888 ranges::sort_heap(__first, __middle, __comp, __proj);
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
1900 return (*
this)(ranges::begin(__r),
std::move(__middle),
1906 inline constexpr __partial_sort_fn partial_sort{};
1908 template<
typename _Iter,
typename _Out>
1909 using partial_sort_copy_result = in_out_result<_Iter, _Out>;
1911 struct __partial_sort_copy_fn
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,
1926 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1928 if (__result_first == __result_last)
1931 auto __lasti = ranges::next(
std::move(__first),
1936 auto __result_real_last = __result_first;
1937 while (__first != __last && __result_real_last != __result_last)
1939 *__result_real_last = *__first;
1940 ++__result_real_last;
1944 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
1945 for (; __first != __last; ++__first)
1950 ranges::pop_heap(__result_first, __result_real_last,
1952 *(__result_real_last-1) = *__first;
1953 ranges::push_heap(__result_first, __result_real_last,
1956 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
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
1974 return (*
this)(ranges::begin(__r), ranges::end(__r),
1975 ranges::begin(__out), ranges::end(__out),
1981 inline constexpr __partial_sort_copy_fn partial_sort_copy{};
1983 struct __is_sorted_until_fn
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>
1990 operator()(_Iter __first, _Sent __last,
1991 _Comp __comp = {}, _Proj __proj = {})
const
1993 if (__first == __last)
1996 auto __next = __first;
1997 for (++__next; __next != __last; __first = __next, (void)++__next)
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
2011 return (*
this)(ranges::begin(__r), ranges::end(__r),
2016 inline constexpr __is_sorted_until_fn is_sorted_until{};
2018 struct __is_sorted_fn
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>
2025 operator()(_Iter __first, _Sent __last,
2026 _Comp __comp = {}, _Proj __proj = {})
const
2028 if (__first == __last)
2031 auto __next = __first;
2032 for (++__next; __next != __last; __first = __next, (void)++__next)
2040 template<forward_range _Range,
typename _Proj = identity,
2041 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2042 _Comp = ranges::less>
2044 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2046 return (*
this)(ranges::begin(__r), ranges::end(__r),
2051 inline constexpr __is_sorted_fn is_sorted{};
2053 struct __nth_element_fn
2055 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2056 typename _Comp = ranges::less,
typename _Proj =
identity>
2057 requires sortable<_Iter, _Comp, _Proj>
2059 operator()(_Iter __first, _Iter __nth, _Sent __last,
2060 _Comp __comp = {}, _Proj __proj = {})
const
2062 auto __lasti = ranges::next(__first, __last);
2065 __detail::__make_comp_proj(__comp, __proj));
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
2076 return (*
this)(ranges::begin(__r),
std::move(__nth),
2081 inline constexpr __nth_element_fn nth_element{};
2083 struct __lower_bound_fn
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>
2091 operator()(_Iter __first, _Sent __last,
2092 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2094 auto __len = ranges::distance(__first, __last);
2098 auto __half = __len / 2;
2099 auto __middle = __first;
2100 ranges::advance(__middle, __half);
2105 __len = __len - __half - 1;
2113 template<forward_range _Range,
2114 typename _Proj = identity,
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
2124 return (*
this)(ranges::begin(__r), ranges::end(__r),
2129 inline constexpr __lower_bound_fn lower_bound{};
2131 struct __upper_bound_fn
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>
2139 operator()(_Iter __first, _Sent __last,
2140 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2142 auto __len = ranges::distance(__first, __last);
2146 auto __half = __len / 2;
2147 auto __middle = __first;
2148 ranges::advance(__middle, __half);
2155 __len = __len - __half - 1;
2161 template<forward_range _Range,
2162 typename _Proj = identity,
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
2172 return (*
this)(ranges::begin(__r), ranges::end(__r),
2177 inline constexpr __upper_bound_fn upper_bound{};
2179 struct __equal_range_fn
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
2190 auto __len = ranges::distance(__first, __last);
2194 auto __half = __len / 2;
2195 auto __middle = __first;
2196 ranges::advance(__middle, __half);
2203 __len = __len - __half - 1;
2212 = ranges::lower_bound(__first, __middle,
2213 __value, __comp, __proj);
2214 ranges::advance(__first, __len);
2216 = ranges::upper_bound(++__middle, __first,
2217 __value, __comp, __proj);
2218 return {__left, __right};
2221 return {__first, __first};
2224 template<forward_range _Range,
2225 typename _Proj = identity,
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
2235 return (*
this)(ranges::begin(__r), ranges::end(__r),
2240 inline constexpr __equal_range_fn equal_range{};
2242 struct __binary_search_fn
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>
2250 operator()(_Iter __first, _Sent __last,
2251 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2253 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2260 template<forward_range _Range,
2261 typename _Proj = identity,
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>
2268 operator()(_Range&& __r,
const _Tp& __value, _Comp __comp = {},
2269 _Proj __proj = {})
const
2271 return (*
this)(ranges::begin(__r), ranges::end(__r),
2276 inline constexpr __binary_search_fn binary_search{};
2278 struct __is_partitioned_fn
2280 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2281 typename _Proj =
identity,
2282 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2284 operator()(_Iter __first, _Sent __last,
2285 _Pred __pred, _Proj __proj = {})
const
2287 __first = ranges::find_if_not(
std::move(__first), __last,
2289 if (__first == __last)
2296 template<input_range _Range,
typename _Proj = identity,
2297 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2300 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2302 return (*
this)(ranges::begin(__r), ranges::end(__r),
2307 inline constexpr __is_partitioned_fn is_partitioned{};
2309 struct __partition_fn
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
2318 if constexpr (bidirectional_iterator<_Iter>)
2320 auto __lasti = ranges::next(__first, __last);
2321 auto __tail = __lasti;
2325 if (__first == __tail)
2334 if (__first == __tail)
2341 ranges::iter_swap(__first, __tail);
2347 if (__first == __last)
2348 return {__first, __first};
2351 if (++__first == __last)
2352 return {__first, __first};
2354 auto __next = __first;
2355 while (++__next != __last)
2358 ranges::iter_swap(__first, __next);
2366 template<forward_range _Range,
typename _Proj = identity,
2367 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2369 requires permutable<iterator_t<_Range>>
2370 constexpr borrowed_subrange_t<_Range>
2371 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2373 return (*
this)(ranges::begin(__r), ranges::end(__r),
2378 inline constexpr __partition_fn partition{};
2381 struct __stable_partition_fn
2383 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2384 typename _Proj =
identity,
2385 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2386 requires permutable<_Iter>
2388 operator()(_Iter __first, _Sent __last,
2389 _Pred __pred, _Proj __proj = {})
const
2391 auto __lasti = ranges::next(__first, __last);
2393 = std::stable_partition(
std::move(__first), __lasti,
2394 __detail::__make_pred_proj(__pred, __proj));
2398 template<bidirectional_range _Range,
typename _Proj = identity,
2399 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2401 requires permutable<iterator_t<_Range>>
2402 borrowed_subrange_t<_Range>
2403 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2405 return (*
this)(ranges::begin(__r), ranges::end(__r),
2410 inline constexpr __stable_partition_fn stable_partition{};
2413 template<
typename _Iter,
typename _Out1,
typename _Out2>
2414 struct in_out_out_result
2416 [[no_unique_address]] _Iter in;
2417 [[no_unique_address]] _Out1 out1;
2418 [[no_unique_address]] _Out2 out2;
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>
2425 operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
2426 {
return {in, out1, out2}; }
2428 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2429 requires convertible_to<_Iter, _IIter>
2430 && convertible_to<_Out1, _OOut1>
2431 && convertible_to<_Out2, _OOut2>
2433 operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2437 template<
typename _Iter,
typename _Out1,
typename _Out2>
2438 using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2440 struct __partition_copy_fn
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
2453 for (; __first != __last; ++__first)
2456 *__out_true = *__first;
2461 *__out_false = *__first;
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>>
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
2480 return (*
this)(ranges::begin(__r), ranges::end(__r),
2486 inline constexpr __partition_copy_fn partition_copy{};
2488 struct __partition_point_fn
2490 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2491 typename _Proj =
identity,
2492 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2494 operator()(_Iter __first, _Sent __last,
2495 _Pred __pred, _Proj __proj = {})
const
2497 auto __len = ranges::distance(__first, __last);
2501 auto __half = __len / 2;
2502 auto __middle = __first;
2503 ranges::advance(__middle, __half);
2508 __len = __len - __half - 1;
2516 template<forward_range _Range,
typename _Proj = identity,
2517 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2519 constexpr borrowed_iterator_t<_Range>
2520 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2522 return (*
this)(ranges::begin(__r), ranges::end(__r),
2527 inline constexpr __partition_point_fn partition_point{};
2529 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2530 using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
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,
2543 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2545 while (__first1 != __last1 && __first2 != __last2)
2551 *__result = *__first2;
2556 *__result = *__first1;
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>,
2577 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2579 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2581 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2582 ranges::begin(__r2), ranges::end(__r2),
2588 inline constexpr __merge_fn merge{};
2590 struct __inplace_merge_fn
2592 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2593 typename _Comp = ranges::less,
2594 typename _Proj =
identity>
2595 requires sortable<_Iter, _Comp, _Proj>
2597 operator()(_Iter __first, _Iter __middle, _Sent __last,
2598 _Comp __comp = {}, _Proj __proj = {})
const
2600 auto __lasti = ranges::next(__first, __last);
2602 __detail::__make_comp_proj(__comp, __proj));
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
2613 return (*
this)(ranges::begin(__r),
std::move(__middle),
2619 inline constexpr __inplace_merge_fn inplace_merge{};
2621 struct __includes_fn
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>
2630 operator()(_Iter1 __first1, _Sent1 __last1,
2631 _Iter2 __first2, _Sent2 __last2,
2633 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2635 while (__first1 != __last1 && __first2 != __last2)
2650 return __first2 == __last2;
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>
2659 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2660 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2662 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2663 ranges::begin(__r2), ranges::end(__r2),
2669 inline constexpr __includes_fn includes{};
2671 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2672 using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2674 struct __set_union_fn
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
2687 while (__first1 != __last1 && __first2 != __last2)
2693 *__result = *__first1;
2700 *__result = *__first2;
2705 *__result = *__first1;
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
2730 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2731 ranges::begin(__r2), ranges::end(__r2),
2737 inline constexpr __set_union_fn set_union{};
2739 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2740 using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2742 struct __set_intersection_fn
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,
2753 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2755 while (__first1 != __last1 && __first2 != __last2)
2766 *__result = *__first1;
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,
2786 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2788 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2789 ranges::begin(__r2), ranges::end(__r2),
2795 inline constexpr __set_intersection_fn set_intersection{};
2797 template<
typename _Iter,
typename _Out>
2798 using set_difference_result = in_out_result<_Iter, _Out>;
2800 struct __set_difference_fn
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,
2811 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2813 while (__first1 != __last1 && __first2 != __last2)
2818 *__result = *__first1;
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,
2843 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2845 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2846 ranges::begin(__r2), ranges::end(__r2),
2852 inline constexpr __set_difference_fn set_difference{};
2854 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2855 using set_symmetric_difference_result
2856 = in_in_out_result<_Iter1, _Iter2, _Out>;
2858 struct __set_symmetric_difference_fn
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
2871 while (__first1 != __last1 && __first2 != __last2)
2876 *__result = *__first1;
2884 *__result = *__first2;
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>,
2909 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2911 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2913 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2914 ranges::begin(__r2), ranges::end(__r2),
2920 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
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
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
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)
2955 auto&& __tmp = *__first;
2964 template<copyable _Tp,
typename _Proj = identity,
2965 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2966 _Comp = ranges::less>
2968 operator()(initializer_list<_Tp> __r,
2969 _Comp __comp = {}, _Proj __proj = {})
const
2971 return (*
this)(ranges::subrange(__r),
2976 inline constexpr __max_fn max{};
2980 template<
typename _Tp,
typename _Proj = identity,
2981 indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
2983 constexpr const _Tp&
2984 operator()(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi,
2985 _Comp __comp = {}, _Proj __proj = {})
const
3000 inline constexpr __clamp_fn clamp{};
3002 template<
typename _Tp>
3003 struct min_max_result
3005 [[no_unique_address]] _Tp min;
3006 [[no_unique_address]] _Tp max;
3008 template<
typename _Tp2>
3009 requires convertible_to<const _Tp&, _Tp2>
3011 operator min_max_result<_Tp2>() const &
3012 {
return {min, max}; }
3014 template<
typename _Tp2>
3015 requires convertible_to<_Tp, _Tp2>
3017 operator min_max_result<_Tp2>() &&
3021 template<
typename _Tp>
3022 using minmax_result = min_max_result<_Tp>;
3026 template<
typename _Tp,
typename _Proj = identity,
3027 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3028 _Comp = ranges::less>
3029 constexpr minmax_result<const _Tp&>
3030 operator()(
const _Tp& __a,
const _Tp& __b,
3031 _Comp __comp = {}, _Proj __proj = {})
const
3041 template<input_range _Range,
typename _Proj = identity,
3042 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3043 _Comp = ranges::less>
3044 requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
3045 constexpr minmax_result<range_value_t<_Range>>
3046 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3048 auto __first = ranges::begin(__r);
3049 auto __last = ranges::end(__r);
3050 __glibcxx_assert(__first != __last);
3051 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3052 minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};
3053 if (++__first == __last)
3059 auto&& __val = *__first;
3060 if (__comp_proj(__val, __result.min))
3065 while (++__first != __last)
3070 range_value_t<_Range> __val1 = *__first;
3071 if (++__first == __last)
3076 if (__comp_proj(__val1, __result.min))
3078 else if (!__comp_proj(__val1, __result.max))
3082 auto&& __val2 = *__first;
3083 if (!__comp_proj(__val2, __val1))
3085 if (__comp_proj(__val1, __result.min))
3087 if (!__comp_proj(__val2, __result.max))
3092 if (__comp_proj(__val2, __result.min))
3094 if (!__comp_proj(__val1, __result.max))
3101 template<copyable _Tp,
typename _Proj = identity,
3102 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3103 _Comp = ranges::less>
3104 constexpr minmax_result<_Tp>
3105 operator()(initializer_list<_Tp> __r,
3106 _Comp __comp = {}, _Proj __proj = {})
const
3108 return (*
this)(ranges::subrange(__r),
3113 inline constexpr __minmax_fn minmax{};
3115 struct __min_element_fn
3117 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3118 typename _Proj =
identity,
3119 indirect_strict_weak_order<projected<_Iter, _Proj>>
3120 _Comp = ranges::less>
3122 operator()(_Iter __first, _Sent __last,
3123 _Comp __comp = {}, _Proj __proj = {})
const
3125 if (__first == __last)
3129 while (++__i != __last)
3139 template<forward_range _Range,
typename _Proj = identity,
3140 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3141 _Comp = ranges::less>
3142 constexpr borrowed_iterator_t<_Range>
3143 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3145 return (*
this)(ranges::begin(__r), ranges::end(__r),
3150 inline constexpr __min_element_fn min_element{};
3152 struct __max_element_fn
3154 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3155 typename _Proj =
identity,
3156 indirect_strict_weak_order<projected<_Iter, _Proj>>
3157 _Comp = ranges::less>
3159 operator()(_Iter __first, _Sent __last,
3160 _Comp __comp = {}, _Proj __proj = {})
const
3162 if (__first == __last)
3166 while (++__i != __last)
3176 template<forward_range _Range,
typename _Proj = identity,
3177 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3178 _Comp = ranges::less>
3179 constexpr borrowed_iterator_t<_Range>
3180 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3182 return (*
this)(ranges::begin(__r), ranges::end(__r),
3187 inline constexpr __max_element_fn max_element{};
3189 template<
typename _Iter>
3190 using minmax_element_result = min_max_result<_Iter>;
3192 struct __minmax_element_fn
3194 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3195 typename _Proj =
identity,
3196 indirect_strict_weak_order<projected<_Iter, _Proj>>
3197 _Comp = ranges::less>
3198 constexpr minmax_element_result<_Iter>
3199 operator()(_Iter __first, _Sent __last,
3200 _Comp __comp = {}, _Proj __proj = {})
const
3202 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3203 minmax_element_result<_Iter> __result = {__first, __first};
3204 if (__first == __last || ++__first == __last)
3210 if (__comp_proj(*__first, *__result.min))
3211 __result.min = __first;
3213 __result.max = __first;
3215 while (++__first != __last)
3220 auto __prev = __first;
3221 if (++__first == __last)
3226 if (__comp_proj(*__prev, *__result.min))
3227 __result.min = __prev;
3228 else if (!__comp_proj(*__prev, *__result.max))
3229 __result.max = __prev;
3232 if (!__comp_proj(*__first, *__prev))
3234 if (__comp_proj(*__prev, *__result.min))
3235 __result.min = __prev;
3236 if (!__comp_proj(*__first, *__result.max))
3237 __result.max = __first;
3241 if (__comp_proj(*__first, *__result.min))
3242 __result.min = __first;
3243 if (!__comp_proj(*__prev, *__result.max))
3244 __result.max = __prev;
3250 template<forward_range _Range,
typename _Proj = identity,
3251 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3252 _Comp = ranges::less>
3253 constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3254 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3256 return (*
this)(ranges::begin(__r), ranges::end(__r),
3261 inline constexpr __minmax_element_fn minmax_element{};
3263 struct __lexicographical_compare_fn
3265 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3266 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3267 typename _Proj1 =
identity,
typename _Proj2 =
identity,
3268 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3269 projected<_Iter2, _Proj2>>
3270 _Comp = ranges::less>
3272 operator()(_Iter1 __first1, _Sent1 __last1,
3273 _Iter2 __first2, _Sent2 __last2,
3275 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3277 if constexpr (__detail::__is_normal_iterator<_Iter1>
3278 && same_as<_Iter1, _Sent1>)
3279 return (*
this)(__first1.base(), __last1.base(),
3283 else if constexpr (__detail::__is_normal_iterator<_Iter2>
3284 && same_as<_Iter2, _Sent2>)
3286 __first2.base(), __last2.base(),
3291 constexpr bool __sized_iters
3292 = (sized_sentinel_for<_Sent1, _Iter1>
3293 && sized_sentinel_for<_Sent2, _Iter2>);
3294 if constexpr (__sized_iters)
3296 using _ValueType1 = iter_value_t<_Iter1>;
3297 using _ValueType2 = iter_value_t<_Iter2>;
3300 constexpr bool __use_memcmp
3301 = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3302 && __ptr_to_nonvolatile<_Iter1>
3303 && __ptr_to_nonvolatile<_Iter2>
3304 && (is_same_v<_Comp, ranges::less>
3305 || is_same_v<_Comp, ranges::greater>)
3306 && is_same_v<_Proj1, identity>
3307 && is_same_v<_Proj2, identity>);
3308 if constexpr (__use_memcmp)
3310 const auto __d1 = __last1 - __first1;
3311 const auto __d2 = __last2 - __first2;
3313 if (
const auto __len =
std::min(__d1, __d2))
3316 = std::__memcmp(__first1, __first2, __len);
3317 if constexpr (is_same_v<_Comp, ranges::less>)
3324 else if constexpr (is_same_v<_Comp, ranges::greater>)
3336 for (; __first1 != __last1 && __first2 != __last2;
3337 ++__first1, (void) ++__first2)
3348 return __first1 == __last1 && __first2 != __last2;
3352 template<input_range _Range1, input_range _Range2,
3353 typename _Proj1 = identity,
typename _Proj2 = identity,
3354 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3355 projected<iterator_t<_Range2>, _Proj2>>
3356 _Comp = ranges::less>
3358 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3359 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3361 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
3362 ranges::begin(__r2), ranges::end(__r2),
3368 template<
typename _Iter,
typename _Ref = iter_reference_t<_Iter>>
3369 static constexpr bool __ptr_to_nonvolatile
3370 = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3373 inline constexpr __lexicographical_compare_fn lexicographical_compare;
3375 template<
typename _Iter>
3376 struct in_found_result
3378 [[no_unique_address]] _Iter in;
3381 template<
typename _Iter2>
3382 requires convertible_to<const _Iter&, _Iter2>
3384 operator in_found_result<_Iter2>() const &
3385 {
return {in, found}; }
3387 template<
typename _Iter2>
3388 requires convertible_to<_Iter, _Iter2>
3390 operator in_found_result<_Iter2>() &&
3394 template<
typename _Iter>
3395 using next_permutation_result = in_found_result<_Iter>;
3397 struct __next_permutation_fn
3399 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3400 typename _Comp = ranges::less,
typename _Proj =
identity>
3401 requires sortable<_Iter, _Comp, _Proj>
3402 constexpr next_permutation_result<_Iter>
3403 operator()(_Iter __first, _Sent __last,
3404 _Comp __comp = {}, _Proj __proj = {})
const
3406 if (__first == __last)
3414 auto __lasti = ranges::next(__first, __last);
3431 ranges::iter_swap(__i, __j);
3432 ranges::reverse(__ii, __last);
3437 ranges::reverse(__first, __last);
3443 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3444 typename _Proj = identity>
3445 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3446 constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3447 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3449 return (*
this)(ranges::begin(__r), ranges::end(__r),
3454 inline constexpr __next_permutation_fn next_permutation{};
3456 template<
typename _Iter>
3457 using prev_permutation_result = in_found_result<_Iter>;
3459 struct __prev_permutation_fn
3461 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3462 typename _Comp = ranges::less,
typename _Proj =
identity>
3463 requires sortable<_Iter, _Comp, _Proj>
3464 constexpr prev_permutation_result<_Iter>
3465 operator()(_Iter __first, _Sent __last,
3466 _Comp __comp = {}, _Proj __proj = {})
const
3468 if (__first == __last)
3476 auto __lasti = ranges::next(__first, __last);
3493 ranges::iter_swap(__i, __j);
3494 ranges::reverse(__ii, __last);
3499 ranges::reverse(__first, __last);
3505 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3506 typename _Proj = identity>
3507 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3508 constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3509 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3511 return (*
this)(ranges::begin(__r), ranges::end(__r),
3516 inline constexpr __prev_permutation_fn prev_permutation{};
3518#if __glibcxx_ranges_contains >= 202207L
3519 struct __contains_fn
3521 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3522 typename _Proj =
identity,
3523 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
3524 requires indirect_binary_predicate<ranges::equal_to,
3525 projected<_Iter, _Proj>,
const _Tp*>
3527 operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
const
3528 {
return ranges::find(
std::move(__first), __last, __value,
std::move(__proj)) != __last; }
3530 template<input_range _Range,
3531 typename _Proj = identity,
3533 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
3534 requires indirect_binary_predicate<ranges::equal_to,
3535 projected<iterator_t<_Range>, _Proj>,
const _Tp*>
3537 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
3538 {
return (*
this)(ranges::begin(__r), ranges::end(__r), __value,
std::move(__proj)); }
3541 inline constexpr __contains_fn contains{};
3543 struct __contains_subrange_fn
3545 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3546 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3547 typename _Pred = ranges::equal_to,
3548 typename _Proj1 =
identity,
typename _Proj2 =
identity>
3549 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
3551 operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
3552 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3554 return __first2 == __last2
3555 || !ranges::search(__first1, __last1, __first2, __last2,
3559 template<forward_range _Range1, forward_range _Range2,
3560 typename _Pred = ranges::equal_to,
3561 typename _Proj1 = identity,
typename _Proj2 = identity>
3562 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
3563 _Pred, _Proj1, _Proj2>
3565 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
3566 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3568 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
3569 ranges::begin(__r2), ranges::end(__r2),
3574 inline constexpr __contains_subrange_fn contains_subrange{};
3578#if __glibcxx_ranges_find_last >= 202207L
3580 struct __find_last_fn
3582 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3583 typename _Proj =
identity,
3584 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
3585 requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
const _Tp*>
3586 constexpr subrange<_Iter>
3587 operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
const
3589 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3591 _Iter __found = ranges::find(reverse_iterator<_Iter>{__last},
3592 reverse_iterator<_Iter>{__first},
3594 if (__found == __first)
3595 return {__last, __last};
3597 return {ranges::prev(__found), __last};
3601 _Iter __found = ranges::find(__first, __last, __value, __proj);
3602 if (__found == __last)
3603 return {__found, __found};
3607 __first = ranges::find(ranges::next(__first), __last, __value, __proj);
3608 if (__first == __last)
3609 return {__found, __first};
3615 template<forward_range _Range,
typename _Proj = identity,
3617 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
3618 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>,
const _Tp*>
3619 constexpr borrowed_subrange_t<_Range>
3620 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
3621 {
return (*
this)(ranges::begin(__r), ranges::end(__r), __value,
std::move(__proj)); }
3624 inline constexpr __find_last_fn find_last{};
3626 struct __find_last_if_fn
3628 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Proj =
identity,
3629 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3630 constexpr subrange<_Iter>
3631 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
const
3633 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3635 _Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last},
3636 reverse_iterator<_Iter>{__first},
3638 if (__found == __first)
3639 return {__last, __last};
3641 return {ranges::prev(__found), __last};
3645 _Iter __found = ranges::find_if(__first, __last, __pred, __proj);
3646 if (__found == __last)
3647 return {__found, __found};
3651 __first = ranges::find_if(ranges::next(__first), __last, __pred, __proj);
3652 if (__first == __last)
3653 return {__found, __first};
3659 template<forward_range _Range,
typename _Proj = identity,
3660 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3661 constexpr borrowed_subrange_t<_Range>
3662 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
3663 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred),
std::move(__proj)); }
3666 inline constexpr __find_last_if_fn find_last_if{};
3668 struct __find_last_if_not_fn
3670 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Proj =
identity,
3671 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3672 constexpr subrange<_Iter>
3673 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
const
3675 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3677 _Iter __found = ranges::find_if_not(reverse_iterator<_Iter>{__last},
3678 reverse_iterator<_Iter>{__first},
3680 if (__found == __first)
3681 return {__last, __last};
3683 return {ranges::prev(__found), __last};
3687 _Iter __found = ranges::find_if_not(__first, __last, __pred, __proj);
3688 if (__found == __last)
3689 return {__found, __found};
3693 __first = ranges::find_if_not(ranges::next(__first), __last, __pred, __proj);
3694 if (__first == __last)
3695 return {__found, __first};
3701 template<forward_range _Range,
typename _Proj = identity,
3702 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3703 constexpr borrowed_subrange_t<_Range>
3704 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
3705 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred),
std::move(__proj)); }
3708 inline constexpr __find_last_if_not_fn find_last_if_not{};
3712#if __glibcxx_ranges_fold >= 202207L
3714 template<
typename _Iter,
typename _Tp>
3715 struct in_value_result
3717 [[no_unique_address]] _Iter in;
3718 [[no_unique_address]] _Tp value;
3720 template<
typename _Iter2,
typename _Tp2>
3721 requires convertible_to<const _Iter&, _Iter2>
3722 && convertible_to<const _Tp&, _Tp2>
3724 operator in_value_result<_Iter2, _Tp2>() const &
3725 {
return {in, value}; }
3727 template<
typename _Iter2,
typename _Tp2>
3728 requires convertible_to<_Iter, _Iter2>
3729 && convertible_to<_Tp, _Tp2>
3731 operator in_value_result<_Iter2, _Tp2>() &&
3737 template<
typename _Fp>
3743 template<
typename _Tp,
typename _Up>
3744 requires invocable<_Fp&, _Up, _Tp>
3745 invoke_result_t<_Fp&, _Up, _Tp>
3746 operator()(_Tp&&, _Up&&);
3749 template<
typename _Fp,
typename _Tp,
typename _Iter,
typename _Up>
3750 concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up>
3751 && convertible_to<_Tp, _Up>
3752 && invocable<_Fp&, _Up, iter_reference_t<_Iter>>
3753 && assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>;
3755 template<
typename _Fp,
typename _Tp,
typename _Iter>
3756 concept __indirectly_binary_left_foldable = copy_constructible<_Fp>
3757 && indirectly_readable<_Iter>
3758 && invocable<_Fp&, _Tp, iter_reference_t<_Iter>>
3759 && convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>,
3761 && __indirectly_binary_left_foldable_impl
3764 template <
typename _Fp,
typename _Tp,
typename _Iter>
3765 concept __indirectly_binary_right_foldable
3766 = __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>;
3769 template<
typename _Iter,
typename _Tp>
3770 using fold_left_with_iter_result = in_value_result<_Iter, _Tp>;
3772 struct __fold_left_with_iter_fn
3774 template<
typename _Ret_iter,
3775 typename _Iter,
typename _Sent,
typename _Tp,
typename _Fp>
3776 static constexpr auto
3777 _S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
3779 using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>;
3780 using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>;
3782 if (__first == __last)
3786 for (++__first; __first != __last; ++__first)
3791 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3792 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>),
3793 __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3795 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3797 using _Ret_iter = _Iter;
3798 return _S_impl<_Ret_iter>(
std::move(__first), __last,
3802 template<input_range _Range,
3803 typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>),
3804 __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3806 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3808 using _Ret_iter = borrowed_iterator_t<_Range>;
3809 return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
3814 inline constexpr __fold_left_with_iter_fn fold_left_with_iter{};
3816 struct __fold_left_fn
3818 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3819 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>),
3820 __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3822 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3824 return ranges::fold_left_with_iter(
std::move(__first), __last,
3828 template<input_range _Range,
3829 typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>),
3830 __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3832 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3833 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__init),
std::move(__f)); }
3836 inline constexpr __fold_left_fn fold_left{};
3838 template<
typename _Iter,
typename _Tp>
3839 using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>;
3841 struct __fold_left_first_with_iter_fn
3843 template<
typename _Ret_iter,
typename _Iter,
typename _Sent,
typename _Fp>
3844 static constexpr auto
3845 _S_impl(_Iter __first, _Sent __last, _Fp __f)
3847 using _Up =
decltype(ranges::fold_left(
std::move(__first), __last,
3848 iter_value_t<_Iter>(*__first), __f));
3849 using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>;
3851 if (__first == __last)
3852 return _Ret{
std::move(__first), optional<_Up>()};
3854 optional<_Up> __init(in_place, *__first);
3855 for (++__first; __first != __last; ++__first)
3860 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3861 __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3862 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3864 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3866 using _Ret_iter = _Iter;
3870 template<input_range _Range,
3871 __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3872 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3874 operator()(_Range&& __r, _Fp __f)
const
3876 using _Ret_iter = borrowed_iterator_t<_Range>;
3877 return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
std::move(__f));
3881 inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{};
3883 struct __fold_left_first_fn
3885 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3886 __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3887 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3889 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3891 return ranges::fold_left_first_with_iter(
std::move(__first), __last,
3895 template<input_range _Range,
3896 __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3897 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3899 operator()(_Range&& __r, _Fp __f)
const
3900 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__f)); }
3903 inline constexpr __fold_left_first_fn fold_left_first{};
3905 struct __fold_right_fn
3907 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3908 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>),
3909 __detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp>
3911 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3913 using _Up = decay_t<invoke_result_t<_Fp&, iter_reference_t<_Iter>, _Tp>>;
3915 if (__first == __last)
3918 _Iter __tail = ranges::next(__first, __last);
3920 while (__first != __tail)
3925 template<bidirectional_range _Range,
3926 typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>),
3927 __detail::__indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Fp>
3929 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3930 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__init),
std::move(__f)); }
3933 inline constexpr __fold_right_fn fold_right{};
3935 struct __fold_right_last_fn
3937 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3938 __detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3939 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3941 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3943 using _Up =
decltype(ranges::fold_right(__first, __last,
3944 iter_value_t<_Iter>(*__first), __f));
3946 if (__first == __last)
3947 return optional<_Up>();
3949 _Iter __tail = ranges::prev(ranges::next(__first,
std::move(__last)));
3950 return optional<_Up>(in_place,
3951 ranges::fold_right(
std::move(__first), __tail,
3952 iter_value_t<_Iter>(*__tail),
3956 template<bidirectional_range _Range,
3957 __detail::__indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3958 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3960 operator()(_Range&& __r, _Fp __f)
const
3961 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__f)); }
3964 inline constexpr __fold_right_last_fn fold_right_last{};
3968 template<
typename _ForwardIterator>
3969 constexpr _ForwardIterator
3970 shift_left(_ForwardIterator __first, _ForwardIterator __last,
3973 __glibcxx_assert(__n >= 0);
3977 auto __mid = ranges::next(__first, __n, __last);
3978 if (__mid == __last)
3983 template<
typename _ForwardIterator>
3984 constexpr _ForwardIterator
3985 shift_right(_ForwardIterator __first, _ForwardIterator __last,
3988 __glibcxx_assert(__n >= 0);
3994 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
3996 auto __mid = ranges::next(__last, -__n, __first);
3997 if (__mid == __first)
4005 auto __result = ranges::next(__first, __n, __last);
4006 if (__result == __last)
4009 auto __dest_head = __first, __dest_tail = __result;
4010 while (__dest_head != __result)
4012 if (__dest_tail == __last)
4036 auto __cursor = __first;
4037 while (__cursor != __result)
4039 if (__dest_tail == __last)
4044 __dest_head =
std::move(__cursor, __result,
4050 std::iter_swap(__cursor, __dest_head);
4059_GLIBCXX_END_NAMESPACE_VERSION
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
typename decay< _Tp >::type decay_t
Alias template for decay.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.
Traits class for iterators.