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 {
362 return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
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)
570 auto&& __scan_deref = *__scan;
573 auto __comp_scan = [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
576 std::forward<_Tp>(__arg));
578 if (__scan != ranges::find_if(__first1, __scan,
579 __comp_scan, __proj1))
582 auto __matches = ranges::count_if(__first2, __last2,
583 __comp_scan, __proj2);
585 || ranges::count_if(__scan, __last1,
586 __comp_scan, __proj1) != __matches)
592 template<forward_range _Range1, forward_range _Range2,
593 typename _Proj1 = identity,
typename _Proj2 = identity,
594 indirect_equivalence_relation<
595 projected<iterator_t<_Range1>, _Proj1>,
596 projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
598 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
599 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
603 if constexpr (sized_range<_Range1>)
604 if constexpr (sized_range<_Range2>)
605 if (ranges::distance(__r1) != ranges::distance(__r2))
608 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
609 ranges::begin(__r2), ranges::end(__r2),
615 inline constexpr __is_permutation_fn is_permutation{};
617 template<
typename _Iter,
typename _Out>
618 using copy_if_result = in_out_result<_Iter, _Out>;
622 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
623 weakly_incrementable _Out,
typename _Proj =
identity,
624 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
625 requires indirectly_copyable<_Iter, _Out>
626 constexpr copy_if_result<_Iter, _Out>
627 operator()(_Iter __first, _Sent __last, _Out __result,
628 _Pred __pred, _Proj __proj = {})
const
630 for (; __first != __last; ++__first)
633 *__result = *__first;
639 template<input_range _Range, weakly_incrementable _Out,
640 typename _Proj = identity,
641 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
643 requires indirectly_copyable<iterator_t<_Range>, _Out>
644 constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
645 operator()(_Range&& __r, _Out __result,
646 _Pred __pred, _Proj __proj = {})
const
648 return (*
this)(ranges::begin(__r), ranges::end(__r),
654 inline constexpr __copy_if_fn copy_if{};
656 template<
typename _Iter1,
typename _Iter2>
657 using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
659 struct __swap_ranges_fn
661 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
662 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
663 requires indirectly_swappable<_Iter1, _Iter2>
664 constexpr swap_ranges_result<_Iter1, _Iter2>
665 operator()(_Iter1 __first1, _Sent1 __last1,
666 _Iter2 __first2, _Sent2 __last2)
const
668 for (; __first1 != __last1 && __first2 != __last2;
669 ++__first1, (void)++__first2)
670 ranges::iter_swap(__first1, __first2);
674 template<input_range _Range1, input_range _Range2>
675 requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
676 constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
677 borrowed_iterator_t<_Range2>>
678 operator()(_Range1&& __r1, _Range2&& __r2)
const
680 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
681 ranges::begin(__r2), ranges::end(__r2));
685 inline constexpr __swap_ranges_fn swap_ranges{};
687 template<
typename _Iter,
typename _Out>
688 using unary_transform_result = in_out_result<_Iter, _Out>;
690 template<
typename _Iter1,
typename _Iter2,
typename _Out>
691 struct in_in_out_result
693 [[no_unique_address]] _Iter1 in1;
694 [[no_unique_address]] _Iter2 in2;
695 [[no_unique_address]] _Out out;
697 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
698 requires convertible_to<const _Iter1&, _IIter1>
699 && convertible_to<const _Iter2&, _IIter2>
700 && convertible_to<const _Out&, _OOut>
702 operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
703 {
return {in1, in2, out}; }
705 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
706 requires convertible_to<_Iter1, _IIter1>
707 && convertible_to<_Iter2, _IIter2>
708 && convertible_to<_Out, _OOut>
710 operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
714 template<
typename _Iter1,
typename _Iter2,
typename _Out>
715 using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
717 struct __transform_fn
719 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
720 weakly_incrementable _Out,
721 copy_constructible _Fp,
typename _Proj =
identity>
722 requires indirectly_writable<_Out,
723 indirect_result_t<_Fp&,
724 projected<_Iter, _Proj>>>
725 constexpr unary_transform_result<_Iter, _Out>
726 operator()(_Iter __first1, _Sent __last1, _Out __result,
727 _Fp __op, _Proj __proj = {})
const
729 for (; __first1 != __last1; ++__first1, (void)++__result)
734 template<input_range _Range, weakly_incrementable _Out,
735 copy_constructible _Fp,
typename _Proj = identity>
736 requires indirectly_writable<_Out,
737 indirect_result_t<_Fp&,
738 projected<iterator_t<_Range>, _Proj>>>
739 constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
740 operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {})
const
742 return (*
this)(ranges::begin(__r), ranges::end(__r),
747 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
748 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
749 weakly_incrementable _Out, copy_constructible _Fp,
750 typename _Proj1 =
identity,
typename _Proj2 =
identity>
751 requires indirectly_writable<_Out,
752 indirect_result_t<_Fp&,
753 projected<_Iter1, _Proj1>,
754 projected<_Iter2, _Proj2>>>
755 constexpr binary_transform_result<_Iter1, _Iter2, _Out>
756 operator()(_Iter1 __first1, _Sent1 __last1,
757 _Iter2 __first2, _Sent2 __last2,
758 _Out __result, _Fp __binary_op,
759 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
761 for (; __first1 != __last1 && __first2 != __last2;
762 ++__first1, (void)++__first2, ++__result)
769 template<input_range _Range1, input_range _Range2,
770 weakly_incrementable _Out, copy_constructible _Fp,
771 typename _Proj1 = identity,
typename _Proj2 = identity>
772 requires indirectly_writable<_Out,
773 indirect_result_t<_Fp&,
774 projected<iterator_t<_Range1>, _Proj1>,
775 projected<iterator_t<_Range2>, _Proj2>>>
776 constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
777 borrowed_iterator_t<_Range2>, _Out>
778 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
779 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
781 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
782 ranges::begin(__r2), ranges::end(__r2),
788 inline constexpr __transform_fn transform{};
792 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
793 typename _Proj =
identity,
794 typename _Tp1 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
795 typename _Tp2 _GLIBCXX26_DEF_VAL_T(_Tp1)>
796 requires indirectly_writable<_Iter, const _Tp2&>
797 && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
800 operator()(_Iter __first, _Sent __last,
801 const _Tp1& __old_value,
const _Tp2& __new_value,
802 _Proj __proj = {})
const
804 for (; __first != __last; ++__first)
806 *__first = __new_value;
810 template<input_range _Range,
typename _Proj = identity,
812 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
813 typename _Tp2 _GLIBCXX26_DEF_VAL_T(_Tp1)>
814 requires indirectly_writable<iterator_t<_Range>,
const _Tp2&>
815 && indirect_binary_predicate<ranges::equal_to,
816 projected<iterator_t<_Range>, _Proj>,
818 constexpr borrowed_iterator_t<_Range>
819 operator()(_Range&& __r,
820 const _Tp1& __old_value,
const _Tp2& __new_value,
821 _Proj __proj = {})
const
823 return (*
this)(ranges::begin(__r), ranges::end(__r),
824 __old_value, __new_value,
std::move(__proj));
828 inline constexpr __replace_fn replace{};
830 struct __replace_if_fn
832 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
833 typename _Proj =
identity,
834 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
835 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
836 requires indirectly_writable<_Iter, const _Tp&>
838 operator()(_Iter __first, _Sent __last,
839 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
841 for (; __first != __last; ++__first)
843 *__first = __new_value;
847 template<input_range _Range,
typename _Proj = identity,
849 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
850 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
852 requires indirectly_writable<iterator_t<_Range>,
const _Tp&>
853 constexpr borrowed_iterator_t<_Range>
854 operator()(_Range&& __r,
855 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
857 return (*
this)(ranges::begin(__r), ranges::end(__r),
862 inline constexpr __replace_if_fn replace_if{};
864 template<
typename _Iter,
typename _Out>
865 using replace_copy_result = in_out_result<_Iter, _Out>;
867 struct __replace_copy_fn
869 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
870 typename _Out,
typename _Proj =
identity,
871 typename _Tp1 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
872 typename _Tp2 _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>)>
873 requires indirectly_copyable<_Iter, _Out>
874 && indirect_binary_predicate<ranges::equal_to,
875 projected<_Iter, _Proj>,
const _Tp1*>
876 && output_iterator<_Out, const _Tp2&>
877 constexpr replace_copy_result<_Iter, _Out>
878 operator()(_Iter __first, _Sent __last, _Out __result,
879 const _Tp1& __old_value,
const _Tp2& __new_value,
880 _Proj __proj = {})
const
882 for (; __first != __last; ++__first, (void)++__result)
884 *__result = __new_value;
886 *__result = *__first;
890 template<input_range _Range,
typename _Out,
891 typename _Proj = identity,
893 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
894 typename _Tp2 _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>)>
895 requires indirectly_copyable<iterator_t<_Range>, _Out>
896 && indirect_binary_predicate<ranges::equal_to,
897 projected<iterator_t<_Range>, _Proj>,
899 && output_iterator<_Out, const _Tp2&>
900 constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
901 operator()(_Range&& __r, _Out __result,
902 const _Tp1& __old_value,
const _Tp2& __new_value,
903 _Proj __proj = {})
const
905 return (*
this)(ranges::begin(__r), ranges::end(__r),
911 inline constexpr __replace_copy_fn replace_copy{};
913 template<
typename _Iter,
typename _Out>
914 using replace_copy_if_result = in_out_result<_Iter, _Out>;
916 struct __replace_copy_if_fn
918 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
920 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>),
921 typename _Proj =
identity,
922 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
923 requires indirectly_copyable<_Iter, _Out>
924 && output_iterator<_Out, const _Tp&>
925 constexpr replace_copy_if_result<_Iter, _Out>
926 operator()(_Iter __first, _Sent __last, _Out __result,
927 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
929 for (; __first != __last; ++__first, (void)++__result)
931 *__result = __new_value;
933 *__result = *__first;
937 template<input_range _Range,
939 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Out>),
940 typename _Proj = identity,
941 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
943 requires indirectly_copyable<iterator_t<_Range>, _Out>
944 && output_iterator<_Out, const _Tp&>
945 constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
946 operator()(_Range&& __r, _Out __result,
947 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
949 return (*
this)(ranges::begin(__r), ranges::end(__r),
955 inline constexpr __replace_copy_if_fn replace_copy_if{};
957 struct __generate_n_fn
959 template<input_or_output_iterator _Out, copy_constructible _Fp>
960 requires invocable<_Fp&>
961 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
963 operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen)
const
965 for (; __n > 0; --__n, (void)++__first)
971 inline constexpr __generate_n_fn generate_n{};
975 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
976 copy_constructible _Fp>
977 requires invocable<_Fp&>
978 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
980 operator()(_Out __first, _Sent __last, _Fp __gen)
const
982 for (; __first != __last; ++__first)
987 template<
typename _Range, copy_constructible _Fp>
988 requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
989 constexpr borrowed_iterator_t<_Range>
990 operator()(_Range&& __r, _Fp __gen)
const
992 return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__gen));
996 inline constexpr __generate_fn generate{};
998 struct __remove_if_fn
1000 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1001 typename _Proj =
identity,
1002 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1003 constexpr subrange<_Iter>
1004 operator()(_Iter __first, _Sent __last,
1005 _Pred __pred, _Proj __proj = {})
const
1007 __first = ranges::find_if(__first, __last, __pred, __proj);
1008 if (__first == __last)
1009 return {__first, __first};
1011 auto __result = __first;
1013 for (; __first != __last; ++__first)
1020 return {__result, __first};
1023 template<forward_range _Range,
typename _Proj = identity,
1024 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1026 requires permutable<iterator_t<_Range>>
1027 constexpr borrowed_subrange_t<_Range>
1028 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
1030 return (*
this)(ranges::begin(__r), ranges::end(__r),
1035 inline constexpr __remove_if_fn remove_if{};
1039 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1040 typename _Proj =
identity,
1041 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
1042 requires indirect_binary_predicate<ranges::equal_to,
1043 projected<_Iter, _Proj>,
1045 constexpr subrange<_Iter>
1046 operator()(_Iter __first, _Sent __last,
1047 const _Tp& __value, _Proj __proj = {})
const
1049 auto __pred = [&] (
auto&& __arg) ->
bool {
1050 return std::forward<decltype(__arg)>(__arg) == __value;
1052 return ranges::remove_if(__first, __last,
1056 template<forward_range _Range,
typename _Proj = identity,
1058 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
1059 requires permutable<iterator_t<_Range>>
1060 && indirect_binary_predicate<ranges::equal_to,
1061 projected<iterator_t<_Range>, _Proj>,
1063 constexpr borrowed_subrange_t<_Range>
1064 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
1066 return (*
this)(ranges::begin(__r), ranges::end(__r),
1071 inline constexpr __remove_fn remove{};
1073 template<
typename _Iter,
typename _Out>
1074 using remove_copy_if_result = in_out_result<_Iter, _Out>;
1076 struct __remove_copy_if_fn
1078 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1079 weakly_incrementable _Out,
typename _Proj =
identity,
1080 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1081 requires indirectly_copyable<_Iter, _Out>
1082 constexpr remove_copy_if_result<_Iter, _Out>
1083 operator()(_Iter __first, _Sent __last, _Out __result,
1084 _Pred __pred, _Proj __proj = {})
const
1086 for (; __first != __last; ++__first)
1089 *__result = *__first;
1095 template<input_range _Range, weakly_incrementable _Out,
1096 typename _Proj = identity,
1097 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1099 requires indirectly_copyable<iterator_t<_Range>, _Out>
1100 constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1101 operator()(_Range&& __r, _Out __result,
1102 _Pred __pred, _Proj __proj = {})
const
1104 return (*
this)(ranges::begin(__r), ranges::end(__r),
1110 inline constexpr __remove_copy_if_fn remove_copy_if{};
1112 template<
typename _Iter,
typename _Out>
1113 using remove_copy_result = in_out_result<_Iter, _Out>;
1115 struct __remove_copy_fn
1117 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1118 weakly_incrementable _Out,
typename _Proj =
identity,
1119 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
1120 requires indirectly_copyable<_Iter, _Out>
1121 && indirect_binary_predicate<ranges::equal_to,
1122 projected<_Iter, _Proj>,
1124 constexpr remove_copy_result<_Iter, _Out>
1125 operator()(_Iter __first, _Sent __last, _Out __result,
1126 const _Tp& __value, _Proj __proj = {})
const
1128 for (; __first != __last; ++__first)
1131 *__result = *__first;
1137 template<input_range _Range, weakly_incrementable _Out,
1138 typename _Proj = identity,
1140 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
1141 requires indirectly_copyable<iterator_t<_Range>, _Out>
1142 && indirect_binary_predicate<ranges::equal_to,
1143 projected<iterator_t<_Range>, _Proj>,
1145 constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
1146 operator()(_Range&& __r, _Out __result,
1147 const _Tp& __value, _Proj __proj = {})
const
1149 return (*
this)(ranges::begin(__r), ranges::end(__r),
1154 inline constexpr __remove_copy_fn remove_copy{};
1158 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1159 typename _Proj =
identity,
1160 indirect_equivalence_relation<
1161 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1162 constexpr subrange<_Iter>
1163 operator()(_Iter __first, _Sent __last,
1164 _Comp __comp = {}, _Proj __proj = {})
const
1166 __first = ranges::adjacent_find(__first, __last, __comp, __proj);
1167 if (__first == __last)
1168 return {__first, __first};
1170 auto __dest = __first;
1172 while (++__first != __last)
1177 return {++__dest, __first};
1180 template<forward_range _Range,
typename _Proj = identity,
1181 indirect_equivalence_relation<
1182 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1183 requires permutable<iterator_t<_Range>>
1184 constexpr borrowed_subrange_t<_Range>
1185 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1187 return (*
this)(ranges::begin(__r), ranges::end(__r),
1192 inline constexpr __unique_fn unique{};
1196 template<
typename _Out,
typename _Tp>
1197 concept __can_reread_output = input_iterator<_Out>
1198 && same_as<_Tp, iter_value_t<_Out>>;
1201 template<
typename _Iter,
typename _Out>
1202 using unique_copy_result = in_out_result<_Iter, _Out>;
1204 struct __unique_copy_fn
1206 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1207 weakly_incrementable _Out,
typename _Proj =
identity,
1208 indirect_equivalence_relation<
1209 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1210 requires indirectly_copyable<_Iter, _Out>
1211 && (forward_iterator<_Iter>
1212 || __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
1213 || indirectly_copyable_storable<_Iter, _Out>)
1214 constexpr unique_copy_result<_Iter, _Out>
1215 operator()(_Iter __first, _Sent __last, _Out __result,
1216 _Comp __comp = {}, _Proj __proj = {})
const
1218 if (__first == __last)
1222 if constexpr (forward_iterator<_Iter>)
1224 auto __next = __first;
1225 *__result = *__next;
1226 while (++__next != __last)
1232 *++__result = *__first;
1236 else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
1238 *__result = *__first;
1239 while (++__first != __last)
1243 *++__result = *__first;
1248 auto __value = *__first;
1249 *__result = __value;
1250 while (++__first != __last)
1257 *++__result = __value;
1264 template<input_range _Range,
1265 weakly_incrementable _Out,
typename _Proj = identity,
1266 indirect_equivalence_relation<
1267 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1268 requires indirectly_copyable<iterator_t<_Range>, _Out>
1269 && (forward_iterator<iterator_t<_Range>>
1270 || __detail::__can_reread_output<_Out, range_value_t<_Range>>
1271 || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1272 constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1273 operator()(_Range&& __r, _Out __result,
1274 _Comp __comp = {}, _Proj __proj = {})
const
1276 return (*
this)(ranges::begin(__r), ranges::end(__r),
1282 inline constexpr __unique_copy_fn unique_copy{};
1286 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1287 requires permutable<_Iter>
1289 operator()(_Iter __first, _Sent __last)
const
1291 auto __i = ranges::next(__first, __last);
1294 if constexpr (random_access_iterator<_Iter>)
1296 if (__first != __last)
1299 while (__first < __tail)
1301 ranges::iter_swap(__first, __tail);
1311 if (__first == __tail || __first == --__tail)
1315 ranges::iter_swap(__first, __tail);
1322 template<b
idirectional_range _Range>
1323 requires permutable<iterator_t<_Range>>
1324 constexpr borrowed_iterator_t<_Range>
1325 operator()(_Range&& __r)
const
1327 return (*
this)(ranges::begin(__r), ranges::end(__r));
1331 inline constexpr __reverse_fn reverse{};
1333 template<
typename _Iter,
typename _Out>
1334 using reverse_copy_result = in_out_result<_Iter, _Out>;
1336 struct __reverse_copy_fn
1338 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1339 weakly_incrementable _Out>
1340 requires indirectly_copyable<_Iter, _Out>
1341 constexpr reverse_copy_result<_Iter, _Out>
1342 operator()(_Iter __first, _Sent __last, _Out __result)
const
1344 auto __i = ranges::next(__first, __last);
1346 while (__first != __tail)
1349 *__result = *__tail;
1355 template<b
idirectional_range _Range, weakly_incrementable _Out>
1356 requires indirectly_copyable<iterator_t<_Range>, _Out>
1357 constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1358 operator()(_Range&& __r, _Out __result)
const
1360 return (*
this)(ranges::begin(__r), ranges::end(__r),
1365 inline constexpr __reverse_copy_fn reverse_copy{};
1369 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1370 constexpr subrange<_Iter>
1371 operator()(_Iter __first, _Iter __middle, _Sent __last)
const
1373 auto __lasti = ranges::next(__first, __last);
1374 if (__first == __middle)
1375 return {__lasti, __lasti};
1376 if (__last == __middle)
1379 if constexpr (random_access_iterator<_Iter>)
1381 auto __n = __lasti - __first;
1382 auto __k = __middle - __first;
1384 if (__k == __n - __k)
1386 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1391 auto __ret = __first + (__lasti - __middle);
1395 if (__k < __n - __k)
1399 if constexpr (__is_pod(iter_value_t<_Iter>))
1403 ranges::move(__p + 1, __p + __n, __p);
1407 auto __q = __p + __k;
1408 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1410 ranges::iter_swap(__p, __q);
1417 ranges::swap(__n, __k);
1425 if constexpr (__is_pod(iter_value_t<_Iter>))
1429 ranges::move_backward(__p, __p + __n - 1, __p + __n);
1433 auto __q = __p + __n;
1435 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1439 ranges::iter_swap(__p, __q);
1444 std::swap(__n, __k);
1448 else if constexpr (bidirectional_iterator<_Iter>)
1450 auto __tail = __lasti;
1452 ranges::reverse(__first, __middle);
1453 ranges::reverse(__middle, __tail);
1455 while (__first != __middle && __middle != __tail)
1457 ranges::iter_swap(__first, --__tail);
1461 if (__first == __middle)
1463 ranges::reverse(__middle, __tail);
1468 ranges::reverse(__first, __middle);
1474 auto __first2 = __middle;
1477 ranges::iter_swap(__first, __first2);
1480 if (__first == __middle)
1481 __middle = __first2;
1482 }
while (__first2 != __last);
1484 auto __ret = __first;
1486 __first2 = __middle;
1488 while (__first2 != __last)
1490 ranges::iter_swap(__first, __first2);
1493 if (__first == __middle)
1494 __middle = __first2;
1495 else if (__first2 == __last)
1496 __first2 = __middle;
1502 template<forward_range _Range>
1503 requires permutable<iterator_t<_Range>>
1504 constexpr borrowed_subrange_t<_Range>
1505 operator()(_Range&& __r, iterator_t<_Range> __middle)
const
1507 return (*
this)(ranges::begin(__r),
std::move(__middle),
1512 inline constexpr __rotate_fn rotate{};
1514 template<
typename _Iter,
typename _Out>
1515 using rotate_copy_result = in_out_result<_Iter, _Out>;
1517 struct __rotate_copy_fn
1519 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1520 weakly_incrementable _Out>
1521 requires indirectly_copyable<_Iter, _Out>
1522 constexpr rotate_copy_result<_Iter, _Out>
1523 operator()(_Iter __first, _Iter __middle, _Sent __last,
1524 _Out __result)
const
1526 auto __copy1 = ranges::copy(__middle,
1529 auto __copy2 = ranges::copy(
std::move(__first),
1535 template<forward_range _Range, weakly_incrementable _Out>
1536 requires indirectly_copyable<iterator_t<_Range>, _Out>
1537 constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1538 operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result)
const
1540 return (*
this)(ranges::begin(__r),
std::move(__middle),
1545 inline constexpr __rotate_copy_fn rotate_copy{};
1549 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1550 weakly_incrementable _Out,
typename _Gen>
1551 requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
1552 && indirectly_copyable<_Iter, _Out>
1553 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1555 operator()(_Iter __first, _Sent __last, _Out __out,
1556 iter_difference_t<_Iter> __n, _Gen&& __g)
const
1558 if constexpr (forward_iterator<_Iter>)
1562 auto __lasti = ranges::next(__first, __last);
1563 return _GLIBCXX_STD_A::
1565 __n, std::forward<_Gen>(__g));
1569 using __distrib_type
1570 = uniform_int_distribution<iter_difference_t<_Iter>>;
1571 using __param_type =
typename __distrib_type::param_type;
1572 __distrib_type __d{};
1573 iter_difference_t<_Iter> __sample_sz = 0;
1574 while (__first != __last && __sample_sz != __n)
1576 __out[__sample_sz++] = *__first;
1579 for (
auto __pop_sz = __sample_sz; __first != __last;
1580 ++__first, (void) ++__pop_sz)
1582 const auto __k = __d(__g, __param_type{0, __pop_sz});
1584 __out[__k] = *__first;
1586 return __out + __sample_sz;
1590 template<input_range _Range, weakly_incrementable _Out,
typename _Gen>
1591 requires (forward_range<_Range> || random_access_iterator<_Out>)
1592 && indirectly_copyable<iterator_t<_Range>, _Out>
1593 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1595 operator()(_Range&& __r, _Out __out,
1596 range_difference_t<_Range> __n, _Gen&& __g)
const
1598 return (*
this)(ranges::begin(__r), ranges::end(__r),
1600 std::forward<_Gen>(__g));
1604 inline constexpr __sample_fn sample{};
1608 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1610 requires permutable<_Iter>
1611 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1613 operator()(_Iter __first, _Sent __last, _Gen&& __g)
const
1615 auto __lasti = ranges::next(__first, __last);
1616 std::shuffle(
std::move(__first), __lasti, std::forward<_Gen>(__g));
1620 template<random_access_range _Range,
typename _Gen>
1621 requires permutable<iterator_t<_Range>>
1622 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1623 borrowed_iterator_t<_Range>
1624 operator()(_Range&& __r, _Gen&& __g)
const
1626 return (*
this)(ranges::begin(__r), ranges::end(__r),
1627 std::forward<_Gen>(__g));
1631 inline constexpr __shuffle_fn shuffle{};
1633 struct __push_heap_fn
1635 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1636 typename _Comp = ranges::less,
typename _Proj =
identity>
1637 requires sortable<_Iter, _Comp, _Proj>
1639 operator()(_Iter __first, _Sent __last,
1640 _Comp __comp = {}, _Proj __proj = {})
const
1642 auto __lasti = ranges::next(__first, __last);
1643 std::push_heap(__first, __lasti,
1644 __detail::__make_comp_proj(__comp, __proj));
1648 template<random_access_range _Range,
1649 typename _Comp = ranges::less,
typename _Proj = identity>
1650 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1651 constexpr borrowed_iterator_t<_Range>
1652 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1654 return (*
this)(ranges::begin(__r), ranges::end(__r),
1659 inline constexpr __push_heap_fn push_heap{};
1661 struct __pop_heap_fn
1663 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1664 typename _Comp = ranges::less,
typename _Proj =
identity>
1665 requires sortable<_Iter, _Comp, _Proj>
1667 operator()(_Iter __first, _Sent __last,
1668 _Comp __comp = {}, _Proj __proj = {})
const
1670 auto __lasti = ranges::next(__first, __last);
1671 std::pop_heap(__first, __lasti,
1672 __detail::__make_comp_proj(__comp, __proj));
1676 template<random_access_range _Range,
1677 typename _Comp = ranges::less,
typename _Proj = identity>
1678 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1679 constexpr borrowed_iterator_t<_Range>
1680 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1682 return (*
this)(ranges::begin(__r), ranges::end(__r),
1687 inline constexpr __pop_heap_fn pop_heap{};
1689 struct __make_heap_fn
1691 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1692 typename _Comp = ranges::less,
typename _Proj =
identity>
1693 requires sortable<_Iter, _Comp, _Proj>
1695 operator()(_Iter __first, _Sent __last,
1696 _Comp __comp = {}, _Proj __proj = {})
const
1698 auto __lasti = ranges::next(__first, __last);
1699 std::make_heap(__first, __lasti,
1700 __detail::__make_comp_proj(__comp, __proj));
1704 template<random_access_range _Range,
1705 typename _Comp = ranges::less,
typename _Proj = identity>
1706 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1707 constexpr borrowed_iterator_t<_Range>
1708 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1710 return (*
this)(ranges::begin(__r), ranges::end(__r),
1715 inline constexpr __make_heap_fn make_heap{};
1717 struct __sort_heap_fn
1719 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1720 typename _Comp = ranges::less,
typename _Proj =
identity>
1721 requires sortable<_Iter, _Comp, _Proj>
1723 operator()(_Iter __first, _Sent __last,
1724 _Comp __comp = {}, _Proj __proj = {})
const
1726 auto __lasti = ranges::next(__first, __last);
1727 std::sort_heap(__first, __lasti,
1728 __detail::__make_comp_proj(__comp, __proj));
1732 template<random_access_range _Range,
1733 typename _Comp = ranges::less,
typename _Proj = identity>
1734 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1735 constexpr borrowed_iterator_t<_Range>
1736 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1738 return (*
this)(ranges::begin(__r), ranges::end(__r),
1743 inline constexpr __sort_heap_fn sort_heap{};
1745 struct __is_heap_until_fn
1747 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1748 typename _Proj =
identity,
1749 indirect_strict_weak_order<projected<_Iter, _Proj>>
1750 _Comp = ranges::less>
1752 operator()(_Iter __first, _Sent __last,
1753 _Comp __comp = {}, _Proj __proj = {})
const
1755 iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
1756 iter_difference_t<_Iter> __parent = 0, __child = 1;
1757 for (; __child < __n; ++__child)
1761 return __first + __child;
1762 else if ((__child & 1) == 0)
1765 return __first + __n;
1768 template<random_access_range _Range,
1769 typename _Proj = identity,
1770 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1771 _Comp = ranges::less>
1772 constexpr borrowed_iterator_t<_Range>
1773 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1775 return (*
this)(ranges::begin(__r), ranges::end(__r),
1780 inline constexpr __is_heap_until_fn is_heap_until{};
1784 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1785 typename _Proj =
identity,
1786 indirect_strict_weak_order<projected<_Iter, _Proj>>
1787 _Comp = ranges::less>
1789 operator()(_Iter __first, _Sent __last,
1790 _Comp __comp = {}, _Proj __proj = {})
const
1793 == ranges::is_heap_until(__first, __last,
1798 template<random_access_range _Range,
1799 typename _Proj = identity,
1800 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1801 _Comp = ranges::less>
1803 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1805 return (*
this)(ranges::begin(__r), ranges::end(__r),
1810 inline constexpr __is_heap_fn is_heap{};
1814 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1815 typename _Comp = ranges::less,
typename _Proj =
identity>
1816 requires sortable<_Iter, _Comp, _Proj>
1818 operator()(_Iter __first, _Sent __last,
1819 _Comp __comp = {}, _Proj __proj = {})
const
1821 auto __lasti = ranges::next(__first, __last);
1822 _GLIBCXX_STD_A::sort(
std::move(__first), __lasti,
1823 __detail::__make_comp_proj(__comp, __proj));
1827 template<random_access_range _Range,
1828 typename _Comp = ranges::less,
typename _Proj = identity>
1829 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1830 constexpr borrowed_iterator_t<_Range>
1831 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1833 return (*
this)(ranges::begin(__r), ranges::end(__r),
1838 inline constexpr __sort_fn sort{};
1840 struct __stable_sort_fn
1842 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1843 typename _Comp = ranges::less,
typename _Proj =
identity>
1844 requires sortable<_Iter, _Comp, _Proj>
1845 _GLIBCXX26_CONSTEXPR
1847 operator()(_Iter __first, _Sent __last,
1848 _Comp __comp = {}, _Proj __proj = {})
const
1850 auto __lasti = ranges::next(__first, __last);
1851 std::stable_sort(
std::move(__first), __lasti,
1852 __detail::__make_comp_proj(__comp, __proj));
1856 template<random_access_range _Range,
1857 typename _Comp = ranges::less,
typename _Proj = identity>
1858 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1859 _GLIBCXX26_CONSTEXPR
1860 borrowed_iterator_t<_Range>
1861 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1863 return (*
this)(ranges::begin(__r), ranges::end(__r),
1868 inline constexpr __stable_sort_fn stable_sort{};
1870 struct __partial_sort_fn
1872 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1873 typename _Comp = ranges::less,
typename _Proj =
identity>
1874 requires sortable<_Iter, _Comp, _Proj>
1876 operator()(_Iter __first, _Iter __middle, _Sent __last,
1877 _Comp __comp = {}, _Proj __proj = {})
const
1879 if (__first == __middle)
1880 return ranges::next(__first, __last);
1882 ranges::make_heap(__first, __middle, __comp, __proj);
1883 auto __i = __middle;
1884 for (; __i != __last; ++__i)
1889 ranges::pop_heap(__first, __middle, __comp, __proj);
1890 ranges::iter_swap(__middle-1, __i);
1891 ranges::push_heap(__first, __middle, __comp, __proj);
1893 ranges::sort_heap(__first, __middle, __comp, __proj);
1898 template<random_access_range _Range,
1899 typename _Comp = ranges::less,
typename _Proj = identity>
1900 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1901 constexpr borrowed_iterator_t<_Range>
1902 operator()(_Range&& __r, iterator_t<_Range> __middle,
1903 _Comp __comp = {}, _Proj __proj = {})
const
1905 return (*
this)(ranges::begin(__r),
std::move(__middle),
1911 inline constexpr __partial_sort_fn partial_sort{};
1913 template<
typename _Iter,
typename _Out>
1914 using partial_sort_copy_result = in_out_result<_Iter, _Out>;
1916 struct __partial_sort_copy_fn
1918 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1919 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1920 typename _Comp = ranges::less,
1921 typename _Proj1 =
identity,
typename _Proj2 =
identity>
1922 requires indirectly_copyable<_Iter1, _Iter2>
1923 && sortable<_Iter2, _Comp, _Proj2>
1924 && indirect_strict_weak_order<_Comp,
1925 projected<_Iter1, _Proj1>,
1926 projected<_Iter2, _Proj2>>
1927 constexpr partial_sort_copy_result<_Iter1, _Iter2>
1928 operator()(_Iter1 __first, _Sent1 __last,
1929 _Iter2 __result_first, _Sent2 __result_last,
1931 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1933 if (__result_first == __result_last)
1936 auto __lasti = ranges::next(
std::move(__first),
1941 auto __result_real_last = __result_first;
1942 while (__first != __last && __result_real_last != __result_last)
1944 *__result_real_last = *__first;
1945 ++__result_real_last;
1949 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
1950 for (; __first != __last; ++__first)
1955 ranges::pop_heap(__result_first, __result_real_last,
1957 *(__result_real_last-1) = *__first;
1958 ranges::push_heap(__result_first, __result_real_last,
1961 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
1966 template<input_range _Range1, random_access_range _Range2,
1967 typename _Comp = ranges::less,
1968 typename _Proj1 = identity,
typename _Proj2 = identity>
1969 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
1970 && sortable<iterator_t<_Range2>, _Comp, _Proj2>
1971 && indirect_strict_weak_order<_Comp,
1972 projected<iterator_t<_Range1>, _Proj1>,
1973 projected<iterator_t<_Range2>, _Proj2>>
1974 constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
1975 borrowed_iterator_t<_Range2>>
1976 operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
1977 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1979 return (*
this)(ranges::begin(__r), ranges::end(__r),
1980 ranges::begin(__out), ranges::end(__out),
1986 inline constexpr __partial_sort_copy_fn partial_sort_copy{};
1988 struct __is_sorted_until_fn
1990 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1991 typename _Proj =
identity,
1992 indirect_strict_weak_order<projected<_Iter, _Proj>>
1993 _Comp = ranges::less>
1995 operator()(_Iter __first, _Sent __last,
1996 _Comp __comp = {}, _Proj __proj = {})
const
1998 if (__first == __last)
2001 auto __next = __first;
2002 for (++__next; __next != __last; __first = __next, (void)++__next)
2010 template<forward_range _Range,
typename _Proj = identity,
2011 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2012 _Comp = ranges::less>
2013 constexpr borrowed_iterator_t<_Range>
2014 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2016 return (*
this)(ranges::begin(__r), ranges::end(__r),
2021 inline constexpr __is_sorted_until_fn is_sorted_until{};
2023 struct __is_sorted_fn
2025 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2026 typename _Proj =
identity,
2027 indirect_strict_weak_order<projected<_Iter, _Proj>>
2028 _Comp = ranges::less>
2030 operator()(_Iter __first, _Sent __last,
2031 _Comp __comp = {}, _Proj __proj = {})
const
2033 if (__first == __last)
2036 auto __next = __first;
2037 for (++__next; __next != __last; __first = __next, (void)++__next)
2045 template<forward_range _Range,
typename _Proj = identity,
2046 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2047 _Comp = ranges::less>
2049 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2051 return (*
this)(ranges::begin(__r), ranges::end(__r),
2056 inline constexpr __is_sorted_fn is_sorted{};
2058 struct __nth_element_fn
2060 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2061 typename _Comp = ranges::less,
typename _Proj =
identity>
2062 requires sortable<_Iter, _Comp, _Proj>
2064 operator()(_Iter __first, _Iter __nth, _Sent __last,
2065 _Comp __comp = {}, _Proj __proj = {})
const
2067 auto __lasti = ranges::next(__first, __last);
2070 __detail::__make_comp_proj(__comp, __proj));
2074 template<random_access_range _Range,
2075 typename _Comp = ranges::less,
typename _Proj = identity>
2076 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2077 constexpr borrowed_iterator_t<_Range>
2078 operator()(_Range&& __r, iterator_t<_Range> __nth,
2079 _Comp __comp = {}, _Proj __proj = {})
const
2081 return (*
this)(ranges::begin(__r),
std::move(__nth),
2086 inline constexpr __nth_element_fn nth_element{};
2088 struct __lower_bound_fn
2090 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2091 typename _Proj =
identity,
2092 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
2093 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2094 _Comp = ranges::less>
2096 operator()(_Iter __first, _Sent __last,
2097 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2099 auto __len = ranges::distance(__first, __last);
2103 auto __half = __len / 2;
2104 auto __middle = __first;
2105 ranges::advance(__middle, __half);
2110 __len = __len - __half - 1;
2118 template<forward_range _Range,
2119 typename _Proj = identity,
2121 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
2122 indirect_strict_weak_order<
const _Tp*,
2123 projected<iterator_t<_Range>, _Proj>>
2124 _Comp = ranges::less>
2125 constexpr borrowed_iterator_t<_Range>
2126 operator()(_Range&& __r,
2127 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2129 return (*
this)(ranges::begin(__r), ranges::end(__r),
2134 inline constexpr __lower_bound_fn lower_bound{};
2136 struct __upper_bound_fn
2138 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2139 typename _Proj =
identity,
2140 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
2141 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2142 _Comp = ranges::less>
2144 operator()(_Iter __first, _Sent __last,
2145 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2147 auto __len = ranges::distance(__first, __last);
2151 auto __half = __len / 2;
2152 auto __middle = __first;
2153 ranges::advance(__middle, __half);
2160 __len = __len - __half - 1;
2166 template<forward_range _Range,
2167 typename _Proj = identity,
2169 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
2170 indirect_strict_weak_order<
const _Tp*,
2171 projected<iterator_t<_Range>, _Proj>>
2172 _Comp = ranges::less>
2173 constexpr borrowed_iterator_t<_Range>
2174 operator()(_Range&& __r,
2175 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2177 return (*
this)(ranges::begin(__r), ranges::end(__r),
2182 inline constexpr __upper_bound_fn upper_bound{};
2184 struct __equal_range_fn
2186 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2187 typename _Proj =
identity,
2188 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
2189 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2190 _Comp = ranges::less>
2191 constexpr subrange<_Iter>
2192 operator()(_Iter __first, _Sent __last,
2193 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2195 auto __len = ranges::distance(__first, __last);
2199 auto __half = __len / 2;
2200 auto __middle = __first;
2201 ranges::advance(__middle, __half);
2208 __len = __len - __half - 1;
2217 = ranges::lower_bound(__first, __middle,
2218 __value, __comp, __proj);
2219 ranges::advance(__first, __len);
2221 = ranges::upper_bound(++__middle, __first,
2222 __value, __comp, __proj);
2223 return {__left, __right};
2226 return {__first, __first};
2229 template<forward_range _Range,
2230 typename _Proj = identity,
2232 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
2233 indirect_strict_weak_order<
const _Tp*,
2234 projected<iterator_t<_Range>, _Proj>>
2235 _Comp = ranges::less>
2236 constexpr borrowed_subrange_t<_Range>
2237 operator()(_Range&& __r,
const _Tp& __value,
2238 _Comp __comp = {}, _Proj __proj = {})
const
2240 return (*
this)(ranges::begin(__r), ranges::end(__r),
2245 inline constexpr __equal_range_fn equal_range{};
2247 struct __binary_search_fn
2249 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2250 typename _Proj =
identity,
2251 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj),
2252 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2253 _Comp = ranges::less>
2255 operator()(_Iter __first, _Sent __last,
2256 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2258 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2265 template<forward_range _Range,
2266 typename _Proj = identity,
2268 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj),
2269 indirect_strict_weak_order<
const _Tp*,
2270 projected<iterator_t<_Range>, _Proj>>
2271 _Comp = ranges::less>
2273 operator()(_Range&& __r,
const _Tp& __value, _Comp __comp = {},
2274 _Proj __proj = {})
const
2276 return (*
this)(ranges::begin(__r), ranges::end(__r),
2281 inline constexpr __binary_search_fn binary_search{};
2283 struct __is_partitioned_fn
2285 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2286 typename _Proj =
identity,
2287 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2289 operator()(_Iter __first, _Sent __last,
2290 _Pred __pred, _Proj __proj = {})
const
2292 __first = ranges::find_if_not(
std::move(__first), __last,
2294 if (__first == __last)
2301 template<input_range _Range,
typename _Proj = identity,
2302 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2305 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2307 return (*
this)(ranges::begin(__r), ranges::end(__r),
2312 inline constexpr __is_partitioned_fn is_partitioned{};
2314 struct __partition_fn
2316 template<permutable _Iter, sentinel_for<_Iter> _Sent,
2317 typename _Proj =
identity,
2318 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2319 constexpr subrange<_Iter>
2320 operator()(_Iter __first, _Sent __last,
2321 _Pred __pred, _Proj __proj = {})
const
2323 if constexpr (bidirectional_iterator<_Iter>)
2325 auto __lasti = ranges::next(__first, __last);
2326 auto __tail = __lasti;
2330 if (__first == __tail)
2339 if (__first == __tail)
2346 ranges::iter_swap(__first, __tail);
2352 if (__first == __last)
2353 return {__first, __first};
2356 if (++__first == __last)
2357 return {__first, __first};
2359 auto __next = __first;
2360 while (++__next != __last)
2363 ranges::iter_swap(__first, __next);
2371 template<forward_range _Range,
typename _Proj = identity,
2372 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2374 requires permutable<iterator_t<_Range>>
2375 constexpr borrowed_subrange_t<_Range>
2376 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2378 return (*
this)(ranges::begin(__r), ranges::end(__r),
2383 inline constexpr __partition_fn partition{};
2386 struct __stable_partition_fn
2388 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2389 typename _Proj =
identity,
2390 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2391 requires permutable<_Iter>
2393 operator()(_Iter __first, _Sent __last,
2394 _Pred __pred, _Proj __proj = {})
const
2396 auto __lasti = ranges::next(__first, __last);
2398 = std::stable_partition(
std::move(__first), __lasti,
2399 __detail::__make_pred_proj(__pred, __proj));
2403 template<bidirectional_range _Range,
typename _Proj = identity,
2404 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2406 requires permutable<iterator_t<_Range>>
2407 borrowed_subrange_t<_Range>
2408 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2410 return (*
this)(ranges::begin(__r), ranges::end(__r),
2415 inline constexpr __stable_partition_fn stable_partition{};
2418 template<
typename _Iter,
typename _Out1,
typename _Out2>
2419 struct in_out_out_result
2421 [[no_unique_address]] _Iter in;
2422 [[no_unique_address]] _Out1 out1;
2423 [[no_unique_address]] _Out2 out2;
2425 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2426 requires convertible_to<const _Iter&, _IIter>
2427 && convertible_to<const _Out1&, _OOut1>
2428 && convertible_to<const _Out2&, _OOut2>
2430 operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
2431 {
return {in, out1, out2}; }
2433 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2434 requires convertible_to<_Iter, _IIter>
2435 && convertible_to<_Out1, _OOut1>
2436 && convertible_to<_Out2, _OOut2>
2438 operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2442 template<
typename _Iter,
typename _Out1,
typename _Out2>
2443 using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2445 struct __partition_copy_fn
2447 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2448 weakly_incrementable _Out1, weakly_incrementable _Out2,
2449 typename _Proj =
identity,
2450 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2451 requires indirectly_copyable<_Iter, _Out1>
2452 && indirectly_copyable<_Iter, _Out2>
2453 constexpr partition_copy_result<_Iter, _Out1, _Out2>
2454 operator()(_Iter __first, _Sent __last,
2455 _Out1 __out_true, _Out2 __out_false,
2456 _Pred __pred, _Proj __proj = {})
const
2458 for (; __first != __last; ++__first)
2461 *__out_true = *__first;
2466 *__out_false = *__first;
2474 template<input_range _Range, weakly_incrementable _Out1,
2475 weakly_incrementable _Out2,
2476 typename _Proj = identity,
2477 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2479 requires indirectly_copyable<iterator_t<_Range>, _Out1>
2480 && indirectly_copyable<iterator_t<_Range>, _Out2>
2481 constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2>
2482 operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false,
2483 _Pred __pred, _Proj __proj = {})
const
2485 return (*
this)(ranges::begin(__r), ranges::end(__r),
2491 inline constexpr __partition_copy_fn partition_copy{};
2493 struct __partition_point_fn
2495 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2496 typename _Proj =
identity,
2497 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2499 operator()(_Iter __first, _Sent __last,
2500 _Pred __pred, _Proj __proj = {})
const
2502 auto __len = ranges::distance(__first, __last);
2506 auto __half = __len / 2;
2507 auto __middle = __first;
2508 ranges::advance(__middle, __half);
2513 __len = __len - __half - 1;
2521 template<forward_range _Range,
typename _Proj = identity,
2522 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2524 constexpr borrowed_iterator_t<_Range>
2525 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2527 return (*
this)(ranges::begin(__r), ranges::end(__r),
2532 inline constexpr __partition_point_fn partition_point{};
2534 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2535 using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2539 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2540 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2541 weakly_incrementable _Out,
typename _Comp = ranges::less,
2542 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2543 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2544 constexpr merge_result<_Iter1, _Iter2, _Out>
2545 operator()(_Iter1 __first1, _Sent1 __last1,
2546 _Iter2 __first2, _Sent2 __last2, _Out __result,
2548 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2550 while (__first1 != __last1 && __first2 != __last2)
2556 *__result = *__first2;
2561 *__result = *__first1;
2574 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2575 typename _Comp = ranges::less,
2576 typename _Proj1 = identity,
typename _Proj2 = identity>
2577 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2578 _Comp, _Proj1, _Proj2>
2579 constexpr merge_result<borrowed_iterator_t<_Range1>,
2580 borrowed_iterator_t<_Range2>,
2582 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2584 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2586 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2587 ranges::begin(__r2), ranges::end(__r2),
2593 inline constexpr __merge_fn merge{};
2595 struct __inplace_merge_fn
2597 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2598 typename _Comp = ranges::less,
2599 typename _Proj =
identity>
2600 requires sortable<_Iter, _Comp, _Proj>
2602 operator()(_Iter __first, _Iter __middle, _Sent __last,
2603 _Comp __comp = {}, _Proj __proj = {})
const
2605 auto __lasti = ranges::next(__first, __last);
2607 __detail::__make_comp_proj(__comp, __proj));
2611 template<bidirectional_range _Range,
2612 typename _Comp = ranges::less,
typename _Proj = identity>
2613 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2614 borrowed_iterator_t<_Range>
2615 operator()(_Range&& __r, iterator_t<_Range> __middle,
2616 _Comp __comp = {}, _Proj __proj = {})
const
2618 return (*
this)(ranges::begin(__r),
std::move(__middle),
2624 inline constexpr __inplace_merge_fn inplace_merge{};
2626 struct __includes_fn
2628 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2629 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2630 typename _Proj1 =
identity,
typename _Proj2 =
identity,
2631 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2632 projected<_Iter2, _Proj2>>
2633 _Comp = ranges::less>
2635 operator()(_Iter1 __first1, _Sent1 __last1,
2636 _Iter2 __first2, _Sent2 __last2,
2638 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2640 while (__first1 != __last1 && __first2 != __last2)
2655 return __first2 == __last2;
2658 template<input_range _Range1, input_range _Range2,
2659 typename _Proj1 = identity,
typename _Proj2 = identity,
2660 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2661 projected<iterator_t<_Range2>, _Proj2>>
2662 _Comp = ranges::less>
2664 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2665 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2667 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2668 ranges::begin(__r2), ranges::end(__r2),
2674 inline constexpr __includes_fn includes{};
2676 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2677 using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2679 struct __set_union_fn
2681 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2682 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2683 weakly_incrementable _Out,
typename _Comp = ranges::less,
2684 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2685 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2686 constexpr set_union_result<_Iter1, _Iter2, _Out>
2687 operator()(_Iter1 __first1, _Sent1 __last1,
2688 _Iter2 __first2, _Sent2 __last2,
2689 _Out __result, _Comp __comp = {},
2690 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2692 while (__first1 != __last1 && __first2 != __last2)
2698 *__result = *__first1;
2705 *__result = *__first2;
2710 *__result = *__first1;
2724 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2725 typename _Comp = ranges::less,
2726 typename _Proj1 = identity,
typename _Proj2 = identity>
2727 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2728 _Comp, _Proj1, _Proj2>
2729 constexpr set_union_result<borrowed_iterator_t<_Range1>,
2730 borrowed_iterator_t<_Range2>, _Out>
2731 operator()(_Range1&& __r1, _Range2&& __r2,
2732 _Out __result, _Comp __comp = {},
2733 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2735 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2736 ranges::begin(__r2), ranges::end(__r2),
2742 inline constexpr __set_union_fn set_union{};
2744 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2745 using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2747 struct __set_intersection_fn
2749 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2750 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2751 weakly_incrementable _Out,
typename _Comp = ranges::less,
2752 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2753 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2754 constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2755 operator()(_Iter1 __first1, _Sent1 __last1,
2756 _Iter2 __first2, _Sent2 __last2, _Out __result,
2758 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2760 while (__first1 != __last1 && __first2 != __last2)
2771 *__result = *__first1;
2782 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2783 typename _Comp = ranges::less,
2784 typename _Proj1 = identity,
typename _Proj2 = identity>
2785 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2786 _Comp, _Proj1, _Proj2>
2787 constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
2788 borrowed_iterator_t<_Range2>, _Out>
2789 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2791 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2793 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2794 ranges::begin(__r2), ranges::end(__r2),
2800 inline constexpr __set_intersection_fn set_intersection{};
2802 template<
typename _Iter,
typename _Out>
2803 using set_difference_result = in_out_result<_Iter, _Out>;
2805 struct __set_difference_fn
2807 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2808 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2809 weakly_incrementable _Out,
typename _Comp = ranges::less,
2810 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2811 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2812 constexpr set_difference_result<_Iter1, _Out>
2813 operator()(_Iter1 __first1, _Sent1 __last1,
2814 _Iter2 __first2, _Sent2 __last2, _Out __result,
2816 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2818 while (__first1 != __last1 && __first2 != __last2)
2823 *__result = *__first1;
2840 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2841 typename _Comp = ranges::less,
2842 typename _Proj1 = identity,
typename _Proj2 = identity>
2843 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2844 _Comp, _Proj1, _Proj2>
2845 constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
2846 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2848 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2850 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2851 ranges::begin(__r2), ranges::end(__r2),
2857 inline constexpr __set_difference_fn set_difference{};
2859 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2860 using set_symmetric_difference_result
2861 = in_in_out_result<_Iter1, _Iter2, _Out>;
2863 struct __set_symmetric_difference_fn
2865 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2866 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2867 weakly_incrementable _Out,
typename _Comp = ranges::less,
2868 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2869 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2870 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
2871 operator()(_Iter1 __first1, _Sent1 __last1,
2872 _Iter2 __first2, _Sent2 __last2,
2873 _Out __result, _Comp __comp = {},
2874 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2876 while (__first1 != __last1 && __first2 != __last2)
2881 *__result = *__first1;
2889 *__result = *__first2;
2906 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2907 typename _Comp = ranges::less,
2908 typename _Proj1 = identity,
typename _Proj2 = identity>
2909 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2910 _Comp, _Proj1, _Proj2>
2911 constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
2912 borrowed_iterator_t<_Range2>,
2914 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2916 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2918 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2919 ranges::begin(__r2), ranges::end(__r2),
2925 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
2931 template<
typename _Tp,
typename _Proj = identity,
2932 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2933 _Comp = ranges::less>
2934 constexpr const _Tp&
2935 operator()(
const _Tp& __a,
const _Tp& __b,
2936 _Comp __comp = {}, _Proj __proj = {})
const
2946 template<input_range _Range,
typename _Proj = identity,
2947 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2948 _Comp = ranges::less>
2949 requires indirectly_copyable_storable<iterator_t<_Range>,
2950 range_value_t<_Range>*>
2951 constexpr range_value_t<_Range>
2952 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2954 auto __first = ranges::begin(__r);
2955 auto __last = ranges::end(__r);
2956 __glibcxx_assert(__first != __last);
2957 auto __result = *__first;
2958 while (++__first != __last)
2960 auto&& __tmp = *__first;
2964 __result = std::forward<decltype(__tmp)>(__tmp);
2969 template<copyable _Tp,
typename _Proj = identity,
2970 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2971 _Comp = ranges::less>
2973 operator()(initializer_list<_Tp> __r,
2974 _Comp __comp = {}, _Proj __proj = {})
const
2976 return (*
this)(ranges::subrange(__r),
2981 inline constexpr __max_fn max{};
2985 template<
typename _Tp,
typename _Proj = identity,
2986 indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
2988 constexpr const _Tp&
2989 operator()(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi,
2990 _Comp __comp = {}, _Proj __proj = {})
const
3009 inline constexpr __clamp_fn clamp{};
3011 template<
typename _Tp>
3012 struct min_max_result
3014 [[no_unique_address]] _Tp min;
3015 [[no_unique_address]] _Tp max;
3017 template<
typename _Tp2>
3018 requires convertible_to<const _Tp&, _Tp2>
3020 operator min_max_result<_Tp2>() const &
3021 {
return {min, max}; }
3023 template<
typename _Tp2>
3024 requires convertible_to<_Tp, _Tp2>
3026 operator min_max_result<_Tp2>() &&
3030 template<
typename _Tp>
3031 using minmax_result = min_max_result<_Tp>;
3035 template<
typename _Tp,
typename _Proj = identity,
3036 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3037 _Comp = ranges::less>
3038 constexpr minmax_result<const _Tp&>
3039 operator()(
const _Tp& __a,
const _Tp& __b,
3040 _Comp __comp = {}, _Proj __proj = {})
const
3050 template<input_range _Range,
typename _Proj = identity,
3051 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3052 _Comp = ranges::less>
3053 requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
3054 constexpr minmax_result<range_value_t<_Range>>
3055 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3057 auto __first = ranges::begin(__r);
3058 auto __last = ranges::end(__r);
3059 __glibcxx_assert(__first != __last);
3060 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3061 minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};
3062 if (++__first == __last)
3068 auto&& __val = *__first;
3069 if (__comp_proj(__val, __result.min))
3070 __result.min = std::forward<decltype(__val)>(__val);
3072 __result.max = std::forward<decltype(__val)>(__val);
3074 while (++__first != __last)
3079 range_value_t<_Range> __val1 = *__first;
3080 if (++__first == __last)
3085 if (__comp_proj(__val1, __result.min))
3087 else if (!__comp_proj(__val1, __result.max))
3091 auto&& __val2 = *__first;
3092 if (!__comp_proj(__val2, __val1))
3094 if (__comp_proj(__val1, __result.min))
3096 if (!__comp_proj(__val2, __result.max))
3097 __result.max = std::forward<decltype(__val2)>(__val2);
3101 if (__comp_proj(__val2, __result.min))
3102 __result.min = std::forward<decltype(__val2)>(__val2);
3103 if (!__comp_proj(__val1, __result.max))
3110 template<copyable _Tp,
typename _Proj = identity,
3111 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3112 _Comp = ranges::less>
3113 constexpr minmax_result<_Tp>
3114 operator()(initializer_list<_Tp> __r,
3115 _Comp __comp = {}, _Proj __proj = {})
const
3117 return (*
this)(ranges::subrange(__r),
3122 inline constexpr __minmax_fn minmax{};
3124 struct __min_element_fn
3126 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3127 typename _Proj =
identity,
3128 indirect_strict_weak_order<projected<_Iter, _Proj>>
3129 _Comp = ranges::less>
3131 operator()(_Iter __first, _Sent __last,
3132 _Comp __comp = {}, _Proj __proj = {})
const
3134 if (__first == __last)
3138 while (++__i != __last)
3148 template<forward_range _Range,
typename _Proj = identity,
3149 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3150 _Comp = ranges::less>
3151 constexpr borrowed_iterator_t<_Range>
3152 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3154 return (*
this)(ranges::begin(__r), ranges::end(__r),
3159 inline constexpr __min_element_fn min_element{};
3161 struct __max_element_fn
3163 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3164 typename _Proj =
identity,
3165 indirect_strict_weak_order<projected<_Iter, _Proj>>
3166 _Comp = ranges::less>
3168 operator()(_Iter __first, _Sent __last,
3169 _Comp __comp = {}, _Proj __proj = {})
const
3171 if (__first == __last)
3175 while (++__i != __last)
3185 template<forward_range _Range,
typename _Proj = identity,
3186 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3187 _Comp = ranges::less>
3188 constexpr borrowed_iterator_t<_Range>
3189 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3191 return (*
this)(ranges::begin(__r), ranges::end(__r),
3196 inline constexpr __max_element_fn max_element{};
3198 template<
typename _Iter>
3199 using minmax_element_result = min_max_result<_Iter>;
3201 struct __minmax_element_fn
3203 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3204 typename _Proj =
identity,
3205 indirect_strict_weak_order<projected<_Iter, _Proj>>
3206 _Comp = ranges::less>
3207 constexpr minmax_element_result<_Iter>
3208 operator()(_Iter __first, _Sent __last,
3209 _Comp __comp = {}, _Proj __proj = {})
const
3211 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3212 minmax_element_result<_Iter> __result = {__first, __first};
3213 if (__first == __last || ++__first == __last)
3219 if (__comp_proj(*__first, *__result.min))
3220 __result.min = __first;
3222 __result.max = __first;
3224 while (++__first != __last)
3229 auto __prev = __first;
3230 if (++__first == __last)
3235 if (__comp_proj(*__prev, *__result.min))
3236 __result.min = __prev;
3237 else if (!__comp_proj(*__prev, *__result.max))
3238 __result.max = __prev;
3241 if (!__comp_proj(*__first, *__prev))
3243 if (__comp_proj(*__prev, *__result.min))
3244 __result.min = __prev;
3245 if (!__comp_proj(*__first, *__result.max))
3246 __result.max = __first;
3250 if (__comp_proj(*__first, *__result.min))
3251 __result.min = __first;
3252 if (!__comp_proj(*__prev, *__result.max))
3253 __result.max = __prev;
3259 template<forward_range _Range,
typename _Proj = identity,
3260 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3261 _Comp = ranges::less>
3262 constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3263 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3265 return (*
this)(ranges::begin(__r), ranges::end(__r),
3270 inline constexpr __minmax_element_fn minmax_element{};
3272 struct __lexicographical_compare_fn
3274 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3275 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3276 typename _Proj1 =
identity,
typename _Proj2 =
identity,
3277 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3278 projected<_Iter2, _Proj2>>
3279 _Comp = ranges::less>
3281 operator()(_Iter1 __first1, _Sent1 __last1,
3282 _Iter2 __first2, _Sent2 __last2,
3284 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3286 if constexpr (__detail::__is_normal_iterator<_Iter1>
3287 && same_as<_Iter1, _Sent1>)
3288 return (*
this)(__first1.base(), __last1.base(),
3292 else if constexpr (__detail::__is_normal_iterator<_Iter2>
3293 && same_as<_Iter2, _Sent2>)
3295 __first2.base(), __last2.base(),
3300 constexpr bool __sized_iters
3301 = (sized_sentinel_for<_Sent1, _Iter1>
3302 && sized_sentinel_for<_Sent2, _Iter2>);
3303 if constexpr (__sized_iters)
3305 using _ValueType1 = iter_value_t<_Iter1>;
3306 using _ValueType2 = iter_value_t<_Iter2>;
3309 constexpr bool __use_memcmp
3310 = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3311 && __ptr_to_nonvolatile<_Iter1>
3312 && __ptr_to_nonvolatile<_Iter2>
3313 && (is_same_v<_Comp, ranges::less>
3314 || is_same_v<_Comp, ranges::greater>)
3315 && is_same_v<_Proj1, identity>
3316 && is_same_v<_Proj2, identity>);
3317 if constexpr (__use_memcmp)
3319 const auto __d1 = __last1 - __first1;
3320 const auto __d2 = __last2 - __first2;
3322 if (
const auto __len =
std::min(__d1, __d2))
3325 = std::__memcmp(__first1, __first2, __len);
3326 if constexpr (is_same_v<_Comp, ranges::less>)
3333 else if constexpr (is_same_v<_Comp, ranges::greater>)
3345 for (; __first1 != __last1 && __first2 != __last2;
3346 ++__first1, (void) ++__first2)
3357 return __first1 == __last1 && __first2 != __last2;
3361 template<input_range _Range1, input_range _Range2,
3362 typename _Proj1 = identity,
typename _Proj2 = identity,
3363 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3364 projected<iterator_t<_Range2>, _Proj2>>
3365 _Comp = ranges::less>
3367 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3368 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3370 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
3371 ranges::begin(__r2), ranges::end(__r2),
3377 template<
typename _Iter,
typename _Ref = iter_reference_t<_Iter>>
3378 static constexpr bool __ptr_to_nonvolatile
3379 = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3382 inline constexpr __lexicographical_compare_fn lexicographical_compare;
3384 template<
typename _Iter>
3385 struct in_found_result
3387 [[no_unique_address]] _Iter in;
3390 template<
typename _Iter2>
3391 requires convertible_to<const _Iter&, _Iter2>
3393 operator in_found_result<_Iter2>() const &
3394 {
return {in, found}; }
3396 template<
typename _Iter2>
3397 requires convertible_to<_Iter, _Iter2>
3399 operator in_found_result<_Iter2>() &&
3403 template<
typename _Iter>
3404 using next_permutation_result = in_found_result<_Iter>;
3406 struct __next_permutation_fn
3408 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3409 typename _Comp = ranges::less,
typename _Proj =
identity>
3410 requires sortable<_Iter, _Comp, _Proj>
3411 constexpr next_permutation_result<_Iter>
3412 operator()(_Iter __first, _Sent __last,
3413 _Comp __comp = {}, _Proj __proj = {})
const
3415 if (__first == __last)
3423 auto __lasti = ranges::next(__first, __last);
3440 ranges::iter_swap(__i, __j);
3441 ranges::reverse(__ii, __last);
3446 ranges::reverse(__first, __last);
3452 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3453 typename _Proj = identity>
3454 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3455 constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3456 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3458 return (*
this)(ranges::begin(__r), ranges::end(__r),
3463 inline constexpr __next_permutation_fn next_permutation{};
3465 template<
typename _Iter>
3466 using prev_permutation_result = in_found_result<_Iter>;
3468 struct __prev_permutation_fn
3470 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3471 typename _Comp = ranges::less,
typename _Proj =
identity>
3472 requires sortable<_Iter, _Comp, _Proj>
3473 constexpr prev_permutation_result<_Iter>
3474 operator()(_Iter __first, _Sent __last,
3475 _Comp __comp = {}, _Proj __proj = {})
const
3477 if (__first == __last)
3485 auto __lasti = ranges::next(__first, __last);
3502 ranges::iter_swap(__i, __j);
3503 ranges::reverse(__ii, __last);
3508 ranges::reverse(__first, __last);
3514 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3515 typename _Proj = identity>
3516 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3517 constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3518 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3520 return (*
this)(ranges::begin(__r), ranges::end(__r),
3525 inline constexpr __prev_permutation_fn prev_permutation{};
3527#if __glibcxx_ranges_contains >= 202207L
3528 struct __contains_fn
3530 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3531 typename _Proj =
identity,
3532 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
3533 requires indirect_binary_predicate<ranges::equal_to,
3534 projected<_Iter, _Proj>,
const _Tp*>
3536 operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
const
3537 {
return ranges::find(
std::move(__first), __last, __value,
std::move(__proj)) != __last; }
3539 template<input_range _Range,
3540 typename _Proj = identity,
3542 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
3543 requires indirect_binary_predicate<ranges::equal_to,
3544 projected<iterator_t<_Range>, _Proj>,
const _Tp*>
3546 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
3547 {
return (*
this)(ranges::begin(__r), ranges::end(__r), __value,
std::move(__proj)); }
3550 inline constexpr __contains_fn contains{};
3552 struct __contains_subrange_fn
3554 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3555 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3556 typename _Pred = ranges::equal_to,
3557 typename _Proj1 =
identity,
typename _Proj2 =
identity>
3558 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
3560 operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
3561 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3563 return __first2 == __last2
3564 || !ranges::search(__first1, __last1, __first2, __last2,
3568 template<forward_range _Range1, forward_range _Range2,
3569 typename _Pred = ranges::equal_to,
3570 typename _Proj1 = identity,
typename _Proj2 = identity>
3571 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
3572 _Pred, _Proj1, _Proj2>
3574 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
3575 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3577 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
3578 ranges::begin(__r2), ranges::end(__r2),
3583 inline constexpr __contains_subrange_fn contains_subrange{};
3587#if __glibcxx_ranges_find_last >= 202207L
3589 struct __find_last_fn
3591 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3592 typename _Proj =
identity,
3593 typename _Tp _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(_Iter, _Proj)>
3594 requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
const _Tp*>
3595 constexpr subrange<_Iter>
3596 operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
const
3598 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3600 _Iter __found = ranges::find(reverse_iterator<_Iter>{__last},
3601 reverse_iterator<_Iter>{__first},
3603 if (__found == __first)
3604 return {__last, __last};
3606 return {ranges::prev(__found), __last};
3610 _Iter __found = ranges::find(__first, __last, __value, __proj);
3611 if (__found == __last)
3612 return {__found, __found};
3616 __first = ranges::find(ranges::next(__first), __last, __value, __proj);
3617 if (__first == __last)
3618 return {__found, __first};
3624 template<forward_range _Range,
typename _Proj = identity,
3626 _GLIBCXX26_RANGE_ALGO_DEF_VAL_T(iterator_t<_Range>, _Proj)>
3627 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>,
const _Tp*>
3628 constexpr borrowed_subrange_t<_Range>
3629 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
3630 {
return (*
this)(ranges::begin(__r), ranges::end(__r), __value,
std::move(__proj)); }
3633 inline constexpr __find_last_fn find_last{};
3635 struct __find_last_if_fn
3637 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Proj =
identity,
3638 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3639 constexpr subrange<_Iter>
3640 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
const
3642 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3644 _Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last},
3645 reverse_iterator<_Iter>{__first},
3647 if (__found == __first)
3648 return {__last, __last};
3650 return {ranges::prev(__found), __last};
3654 _Iter __found = ranges::find_if(__first, __last, __pred, __proj);
3655 if (__found == __last)
3656 return {__found, __found};
3660 __first = ranges::find_if(ranges::next(__first), __last, __pred, __proj);
3661 if (__first == __last)
3662 return {__found, __first};
3668 template<forward_range _Range,
typename _Proj = identity,
3669 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3670 constexpr borrowed_subrange_t<_Range>
3671 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
3672 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred),
std::move(__proj)); }
3675 inline constexpr __find_last_if_fn find_last_if{};
3677 struct __find_last_if_not_fn
3679 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Proj =
identity,
3680 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3681 constexpr subrange<_Iter>
3682 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
const
3684 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3686 _Iter __found = ranges::find_if_not(reverse_iterator<_Iter>{__last},
3687 reverse_iterator<_Iter>{__first},
3689 if (__found == __first)
3690 return {__last, __last};
3692 return {ranges::prev(__found), __last};
3696 _Iter __found = ranges::find_if_not(__first, __last, __pred, __proj);
3697 if (__found == __last)
3698 return {__found, __found};
3702 __first = ranges::find_if_not(ranges::next(__first), __last, __pred, __proj);
3703 if (__first == __last)
3704 return {__found, __first};
3710 template<forward_range _Range,
typename _Proj = identity,
3711 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3712 constexpr borrowed_subrange_t<_Range>
3713 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
3714 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred),
std::move(__proj)); }
3717 inline constexpr __find_last_if_not_fn find_last_if_not{};
3721#if __glibcxx_ranges_fold >= 202207L
3723 template<
typename _Iter,
typename _Tp>
3724 struct in_value_result
3726 [[no_unique_address]] _Iter in;
3727 [[no_unique_address]] _Tp value;
3729 template<
typename _Iter2,
typename _Tp2>
3730 requires convertible_to<const _Iter&, _Iter2>
3731 && convertible_to<const _Tp&, _Tp2>
3733 operator in_value_result<_Iter2, _Tp2>() const &
3734 {
return {in, value}; }
3736 template<
typename _Iter2,
typename _Tp2>
3737 requires convertible_to<_Iter, _Iter2>
3738 && convertible_to<_Tp, _Tp2>
3740 operator in_value_result<_Iter2, _Tp2>() &&
3746 template<
typename _Fp>
3752 template<
typename _Tp,
typename _Up>
3753 requires invocable<_Fp&, _Up, _Tp>
3754 invoke_result_t<_Fp&, _Up, _Tp>
3755 operator()(_Tp&&, _Up&&);
3758 template<
typename _Fp,
typename _Tp,
typename _Iter,
typename _Up>
3759 concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up>
3760 && convertible_to<_Tp, _Up>
3761 && invocable<_Fp&, _Up, iter_reference_t<_Iter>>
3762 && assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>;
3764 template<
typename _Fp,
typename _Tp,
typename _Iter>
3765 concept __indirectly_binary_left_foldable = copy_constructible<_Fp>
3766 && indirectly_readable<_Iter>
3767 && invocable<_Fp&, _Tp, iter_reference_t<_Iter>>
3768 && convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>,
3769 decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>
3770 && __indirectly_binary_left_foldable_impl
3771 <_Fp, _Tp, _Iter, decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>;
3773 template <
typename _Fp,
typename _Tp,
typename _Iter>
3774 concept __indirectly_binary_right_foldable
3775 = __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>;
3778 template<
typename _Iter,
typename _Tp>
3779 using fold_left_with_iter_result = in_value_result<_Iter, _Tp>;
3781 struct __fold_left_with_iter_fn
3783 template<
typename _Ret_iter,
3784 typename _Iter,
typename _Sent,
typename _Tp,
typename _Fp>
3785 static constexpr auto
3786 _S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
3788 using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>;
3789 using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>;
3791 if (__first == __last)
3795 for (++__first; __first != __last; ++__first)
3800 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3801 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>),
3802 __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3804 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3806 using _Ret_iter = _Iter;
3807 return _S_impl<_Ret_iter>(
std::move(__first), __last,
3811 template<input_range _Range,
3812 typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>),
3813 __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3815 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3817 using _Ret_iter = borrowed_iterator_t<_Range>;
3818 return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
3823 inline constexpr __fold_left_with_iter_fn fold_left_with_iter{};
3825 struct __fold_left_fn
3827 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3828 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>),
3829 __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3831 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3833 return ranges::fold_left_with_iter(
std::move(__first), __last,
3837 template<input_range _Range,
3838 typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>),
3839 __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3841 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3842 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__init),
std::move(__f)); }
3845 inline constexpr __fold_left_fn fold_left{};
3847 template<
typename _Iter,
typename _Tp>
3848 using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>;
3850 struct __fold_left_first_with_iter_fn
3852 template<
typename _Ret_iter,
typename _Iter,
typename _Sent,
typename _Fp>
3853 static constexpr auto
3854 _S_impl(_Iter __first, _Sent __last, _Fp __f)
3856 using _Up =
decltype(ranges::fold_left(
std::move(__first), __last,
3857 iter_value_t<_Iter>(*__first), __f));
3858 using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>;
3860 if (__first == __last)
3861 return _Ret{
std::move(__first), optional<_Up>()};
3863 optional<_Up> __init(in_place, *__first);
3864 for (++__first; __first != __last; ++__first)
3869 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3870 __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3871 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3873 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3875 using _Ret_iter = _Iter;
3879 template<input_range _Range,
3880 __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3881 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3883 operator()(_Range&& __r, _Fp __f)
const
3885 using _Ret_iter = borrowed_iterator_t<_Range>;
3886 return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
std::move(__f));
3890 inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{};
3892 struct __fold_left_first_fn
3894 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3895 __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3896 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3898 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3900 return ranges::fold_left_first_with_iter(
std::move(__first), __last,
3904 template<input_range _Range,
3905 __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3906 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3908 operator()(_Range&& __r, _Fp __f)
const
3909 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__f)); }
3912 inline constexpr __fold_left_first_fn fold_left_first{};
3914 struct __fold_right_fn
3916 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3917 typename _Tp _GLIBCXX26_DEF_VAL_T(iter_value_t<_Iter>),
3918 __detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp>
3920 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3922 using _Up = decay_t<invoke_result_t<_Fp&, iter_reference_t<_Iter>, _Tp>>;
3924 if (__first == __last)
3927 _Iter __tail = ranges::next(__first, __last);
3929 while (__first != __tail)
3934 template<bidirectional_range _Range,
3935 typename _Tp _GLIBCXX26_DEF_VAL_T(range_value_t<_Range>),
3936 __detail::__indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Fp>
3938 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3939 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__init),
std::move(__f)); }
3942 inline constexpr __fold_right_fn fold_right{};
3944 struct __fold_right_last_fn
3946 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3947 __detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3948 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3950 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3952 using _Up =
decltype(ranges::fold_right(__first, __last,
3953 iter_value_t<_Iter>(*__first), __f));
3955 if (__first == __last)
3956 return optional<_Up>();
3958 _Iter __tail = ranges::prev(ranges::next(__first,
std::move(__last)));
3959 return optional<_Up>(in_place,
3960 ranges::fold_right(
std::move(__first), __tail,
3961 iter_value_t<_Iter>(*__tail),
3965 template<bidirectional_range _Range,
3966 __detail::__indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3967 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3969 operator()(_Range&& __r, _Fp __f)
const
3970 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__f)); }
3973 inline constexpr __fold_right_last_fn fold_right_last{};
3977 template<
typename _ForwardIterator>
3978 constexpr _ForwardIterator
3979 shift_left(_ForwardIterator __first, _ForwardIterator __last,
3980 typename iterator_traits<_ForwardIterator>::difference_type __n)
3982 __glibcxx_assert(__n >= 0);
3986 auto __mid = ranges::next(__first, __n, __last);
3987 if (__mid == __last)
3992 template<
typename _ForwardIterator>
3993 constexpr _ForwardIterator
3994 shift_right(_ForwardIterator __first, _ForwardIterator __last,
3995 typename iterator_traits<_ForwardIterator>::difference_type __n)
3997 __glibcxx_assert(__n >= 0);
4002 =
typename iterator_traits<_ForwardIterator>::iterator_category;
4003 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
4005 auto __mid = ranges::next(__last, -__n, __first);
4006 if (__mid == __first)
4014 auto __result = ranges::next(__first, __n, __last);
4015 if (__result == __last)
4018 auto __dest_head = __first, __dest_tail = __result;
4019 while (__dest_head != __result)
4021 if (__dest_tail == __last)
4045 auto __cursor = __first;
4046 while (__cursor != __result)
4048 if (__dest_tail == __last)
4053 __dest_head =
std::move(__cursor, __result,
4059 std::iter_swap(__cursor, __dest_head);
4068_GLIBCXX_END_NAMESPACE_VERSION
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.