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 _Tp,
typename _Proj =
identity>
285 requires indirect_binary_predicate<ranges::equal_to,
286 projected<_Iter, _Proj>,
288 constexpr iter_difference_t<_Iter>
289 operator()(_Iter __first, _Sent __last,
290 const _Tp& __value, _Proj __proj = {})
const
292 iter_difference_t<_Iter> __n = 0;
293 for (; __first != __last; ++__first)
299 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
300 requires indirect_binary_predicate<ranges::equal_to,
301 projected<iterator_t<_Range>, _Proj>,
303 constexpr range_difference_t<_Range>
304 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
306 return (*
this)(ranges::begin(__r), ranges::end(__r),
311 inline constexpr __count_fn count{};
315 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
316 typename _Proj =
identity,
317 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
318 constexpr iter_difference_t<_Iter>
319 operator()(_Iter __first, _Sent __last,
320 _Pred __pred, _Proj __proj = {})
const
322 iter_difference_t<_Iter> __n = 0;
323 for (; __first != __last; ++__first)
329 template<input_range _Range,
330 typename _Proj = identity,
331 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
333 constexpr range_difference_t<_Range>
334 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
336 return (*
this)(ranges::begin(__r), ranges::end(__r),
341 inline constexpr __count_if_fn count_if{};
347 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
348 typename _Pred = ranges::equal_to,
typename _Proj =
identity>
349 requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
350 constexpr subrange<_Iter>
351 operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
352 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const
355 return {__first, __first};
357 auto __value_comp = [&] <
typename _Rp> (_Rp&& __arg) ->
bool {
362 __first = ranges::find_if(
std::move(__first), __last,
365 if (__first == __last)
366 return {__first, __first};
369 auto __end = __first;
370 return {__first, ++__end};
374 if constexpr (sized_sentinel_for<_Sent, _Iter>
375 && random_access_iterator<_Iter>)
377 auto __tail_size = __last - __first;
378 auto __remainder = __count;
380 while (__remainder <= __tail_size)
382 __first += __remainder;
383 __tail_size -= __remainder;
384 auto __backtrack = __first;
387 if (--__remainder == 0)
388 return {__first - __count, __first};
390 __remainder = __count + 1 - (__first - __backtrack);
392 auto __i = __first + __tail_size;
397 __first = ranges::find_if(__first, __last, __value_comp, __proj);
398 while (__first != __last)
403 while (__i != __last && __n != 1
410 return {__first, __i};
413 __first = ranges::find_if(++__i, __last, __value_comp, __proj);
415 return {__first, __first};
419 template<forward_range _Range,
typename _Tp,
420 typename _Pred = ranges::equal_to,
typename _Proj = identity>
421 requires indirectly_comparable<iterator_t<_Range>,
const _Tp*,
423 constexpr borrowed_subrange_t<_Range>
424 operator()(_Range&& __r, range_difference_t<_Range> __count,
425 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const
427 return (*
this)(ranges::begin(__r), ranges::end(__r),
433 inline constexpr __search_n_fn search_n{};
437 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
438 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
439 typename _Pred = ranges::equal_to,
440 typename _Proj1 =
identity,
typename _Proj2 =
identity>
441 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
442 constexpr subrange<_Iter1>
443 operator()(_Iter1 __first1, _Sent1 __last1,
444 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
445 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
447 if constexpr (bidirectional_iterator<_Iter1>
448 && bidirectional_iterator<_Iter2>)
450 auto __i1 = ranges::next(__first1, __last1);
451 auto __i2 = ranges::next(__first2, __last2);
453 = ranges::search(reverse_iterator<_Iter1>{__i1},
454 reverse_iterator<_Iter1>{__first1},
455 reverse_iterator<_Iter2>{__i2},
456 reverse_iterator<_Iter2>{__first2},
459 auto __result_first = ranges::end(__rresult).base();
460 auto __result_last = ranges::begin(__rresult).base();
461 if (__result_last == __first1)
464 return {__result_first, __result_last};
468 auto __i = ranges::next(__first1, __last1);
469 if (__first2 == __last2)
472 auto __result_begin = __i;
473 auto __result_end = __i;
476 auto __new_range = ranges::search(__first1, __last1,
478 __pred, __proj1, __proj2);
479 auto __new_result_begin = ranges::begin(__new_range);
480 auto __new_result_end = ranges::end(__new_range);
481 if (__new_result_begin == __last1)
482 return {__result_begin, __result_end};
485 __result_begin = __new_result_begin;
486 __result_end = __new_result_end;
487 __first1 = __result_begin;
494 template<forward_range _Range1, forward_range _Range2,
495 typename _Pred = ranges::equal_to,
496 typename _Proj1 = identity,
typename _Proj2 = identity>
497 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
498 _Pred, _Proj1, _Proj2>
499 constexpr borrowed_subrange_t<_Range1>
500 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
501 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
503 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
504 ranges::begin(__r2), ranges::end(__r2),
510 inline constexpr __find_end_fn find_end{};
514 struct __is_permutation_fn
516 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
517 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
518 typename _Proj1 =
identity,
typename _Proj2 =
identity,
519 indirect_equivalence_relation<projected<_Iter1, _Proj1>,
520 projected<_Iter2, _Proj2>> _Pred
523 operator()(_Iter1 __first1, _Sent1 __last1,
524 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
525 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
527 constexpr bool __sized_iters
528 = (sized_sentinel_for<_Sent1, _Iter1>
529 && sized_sentinel_for<_Sent2, _Iter2>);
530 if constexpr (__sized_iters)
532 auto __d1 = ranges::distance(__first1, __last1);
533 auto __d2 = ranges::distance(__first2, __last2);
540 for (; __first1 != __last1 && __first2 != __last2;
541 ++__first1, (void)++__first2)
547 if constexpr (__sized_iters)
549 if (__first1 == __last1)
554 auto __d1 = ranges::distance(__first1, __last1);
555 auto __d2 = ranges::distance(__first2, __last2);
556 if (__d1 == 0 && __d2 == 0)
562 for (
auto __scan = __first1; __scan != __last1; ++__scan)
565 auto __comp_scan = [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
569 if (__scan != ranges::find_if(__first1, __scan,
570 __comp_scan, __proj1))
573 auto __matches = ranges::count_if(__first2, __last2,
574 __comp_scan, __proj2);
576 || ranges::count_if(__scan, __last1,
577 __comp_scan, __proj1) != __matches)
583 template<forward_range _Range1, forward_range _Range2,
584 typename _Proj1 = identity,
typename _Proj2 = identity,
585 indirect_equivalence_relation<
586 projected<iterator_t<_Range1>, _Proj1>,
587 projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
589 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
590 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
594 if constexpr (sized_range<_Range1>)
595 if constexpr (sized_range<_Range2>)
596 if (ranges::distance(__r1) != ranges::distance(__r2))
599 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
600 ranges::begin(__r2), ranges::end(__r2),
606 inline constexpr __is_permutation_fn is_permutation{};
608 template<
typename _Iter,
typename _Out>
609 using copy_if_result = in_out_result<_Iter, _Out>;
613 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
614 weakly_incrementable _Out,
typename _Proj =
identity,
615 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
616 requires indirectly_copyable<_Iter, _Out>
617 constexpr copy_if_result<_Iter, _Out>
618 operator()(_Iter __first, _Sent __last, _Out __result,
619 _Pred __pred, _Proj __proj = {})
const
621 for (; __first != __last; ++__first)
624 *__result = *__first;
630 template<input_range _Range, weakly_incrementable _Out,
631 typename _Proj = identity,
632 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
634 requires indirectly_copyable<iterator_t<_Range>, _Out>
635 constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
636 operator()(_Range&& __r, _Out __result,
637 _Pred __pred, _Proj __proj = {})
const
639 return (*
this)(ranges::begin(__r), ranges::end(__r),
645 inline constexpr __copy_if_fn copy_if{};
647 template<
typename _Iter1,
typename _Iter2>
648 using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
650 struct __swap_ranges_fn
652 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
653 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
654 requires indirectly_swappable<_Iter1, _Iter2>
655 constexpr swap_ranges_result<_Iter1, _Iter2>
656 operator()(_Iter1 __first1, _Sent1 __last1,
657 _Iter2 __first2, _Sent2 __last2)
const
659 for (; __first1 != __last1 && __first2 != __last2;
660 ++__first1, (void)++__first2)
661 ranges::iter_swap(__first1, __first2);
665 template<input_range _Range1, input_range _Range2>
666 requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
667 constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
668 borrowed_iterator_t<_Range2>>
669 operator()(_Range1&& __r1, _Range2&& __r2)
const
671 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
672 ranges::begin(__r2), ranges::end(__r2));
676 inline constexpr __swap_ranges_fn swap_ranges{};
678 template<
typename _Iter,
typename _Out>
679 using unary_transform_result = in_out_result<_Iter, _Out>;
681 template<
typename _Iter1,
typename _Iter2,
typename _Out>
682 struct in_in_out_result
684 [[no_unique_address]] _Iter1 in1;
685 [[no_unique_address]] _Iter2 in2;
686 [[no_unique_address]] _Out out;
688 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
689 requires convertible_to<const _Iter1&, _IIter1>
690 && convertible_to<const _Iter2&, _IIter2>
691 && convertible_to<const _Out&, _OOut>
693 operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
694 {
return {in1, in2, out}; }
696 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
697 requires convertible_to<_Iter1, _IIter1>
698 && convertible_to<_Iter2, _IIter2>
699 && convertible_to<_Out, _OOut>
701 operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
705 template<
typename _Iter1,
typename _Iter2,
typename _Out>
706 using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
708 struct __transform_fn
710 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
711 weakly_incrementable _Out,
712 copy_constructible _Fp,
typename _Proj =
identity>
713 requires indirectly_writable<_Out,
714 indirect_result_t<_Fp&,
715 projected<_Iter, _Proj>>>
716 constexpr unary_transform_result<_Iter, _Out>
717 operator()(_Iter __first1, _Sent __last1, _Out __result,
718 _Fp __op, _Proj __proj = {})
const
720 for (; __first1 != __last1; ++__first1, (void)++__result)
725 template<input_range _Range, weakly_incrementable _Out,
726 copy_constructible _Fp,
typename _Proj = identity>
727 requires indirectly_writable<_Out,
728 indirect_result_t<_Fp&,
729 projected<iterator_t<_Range>, _Proj>>>
730 constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
731 operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {})
const
733 return (*
this)(ranges::begin(__r), ranges::end(__r),
738 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
739 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
740 weakly_incrementable _Out, copy_constructible _Fp,
741 typename _Proj1 =
identity,
typename _Proj2 =
identity>
742 requires indirectly_writable<_Out,
743 indirect_result_t<_Fp&,
744 projected<_Iter1, _Proj1>,
745 projected<_Iter2, _Proj2>>>
746 constexpr binary_transform_result<_Iter1, _Iter2, _Out>
747 operator()(_Iter1 __first1, _Sent1 __last1,
748 _Iter2 __first2, _Sent2 __last2,
749 _Out __result, _Fp __binary_op,
750 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
752 for (; __first1 != __last1 && __first2 != __last2;
753 ++__first1, (void)++__first2, ++__result)
760 template<input_range _Range1, input_range _Range2,
761 weakly_incrementable _Out, copy_constructible _Fp,
762 typename _Proj1 = identity,
typename _Proj2 = identity>
763 requires indirectly_writable<_Out,
764 indirect_result_t<_Fp&,
765 projected<iterator_t<_Range1>, _Proj1>,
766 projected<iterator_t<_Range2>, _Proj2>>>
767 constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
768 borrowed_iterator_t<_Range2>, _Out>
769 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
770 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
772 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
773 ranges::begin(__r2), ranges::end(__r2),
779 inline constexpr __transform_fn transform{};
783 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
784 typename _Tp1,
typename _Tp2,
typename _Proj =
identity>
785 requires indirectly_writable<_Iter, const _Tp2&>
786 && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
789 operator()(_Iter __first, _Sent __last,
790 const _Tp1& __old_value,
const _Tp2& __new_value,
791 _Proj __proj = {})
const
793 for (; __first != __last; ++__first)
795 *__first = __new_value;
799 template<input_range _Range,
800 typename _Tp1,
typename _Tp2,
typename _Proj = identity>
801 requires indirectly_writable<iterator_t<_Range>,
const _Tp2&>
802 && indirect_binary_predicate<ranges::equal_to,
803 projected<iterator_t<_Range>, _Proj>,
805 constexpr borrowed_iterator_t<_Range>
806 operator()(_Range&& __r,
807 const _Tp1& __old_value,
const _Tp2& __new_value,
808 _Proj __proj = {})
const
810 return (*
this)(ranges::begin(__r), ranges::end(__r),
811 __old_value, __new_value,
std::move(__proj));
815 inline constexpr __replace_fn replace{};
817 struct __replace_if_fn
819 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
820 typename _Tp,
typename _Proj =
identity,
821 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
822 requires indirectly_writable<_Iter, const _Tp&>
824 operator()(_Iter __first, _Sent __last,
825 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
827 for (; __first != __last; ++__first)
829 *__first = __new_value;
833 template<input_range _Range,
typename _Tp,
typename _Proj = identity,
834 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
836 requires indirectly_writable<iterator_t<_Range>,
const _Tp&>
837 constexpr borrowed_iterator_t<_Range>
838 operator()(_Range&& __r,
839 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
841 return (*
this)(ranges::begin(__r), ranges::end(__r),
846 inline constexpr __replace_if_fn replace_if{};
848 template<
typename _Iter,
typename _Out>
849 using replace_copy_result = in_out_result<_Iter, _Out>;
851 struct __replace_copy_fn
853 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
854 typename _Tp1,
typename _Tp2, output_iterator<const _Tp2&> _Out,
855 typename _Proj =
identity>
856 requires indirectly_copyable<_Iter, _Out>
857 && indirect_binary_predicate<ranges::equal_to,
858 projected<_Iter, _Proj>,
const _Tp1*>
859 constexpr replace_copy_result<_Iter, _Out>
860 operator()(_Iter __first, _Sent __last, _Out __result,
861 const _Tp1& __old_value,
const _Tp2& __new_value,
862 _Proj __proj = {})
const
864 for (; __first != __last; ++__first, (void)++__result)
866 *__result = __new_value;
868 *__result = *__first;
872 template<input_range _Range,
typename _Tp1,
typename _Tp2,
873 output_iterator<const _Tp2&> _Out,
typename _Proj = identity>
874 requires indirectly_copyable<iterator_t<_Range>, _Out>
875 && indirect_binary_predicate<ranges::equal_to,
876 projected<iterator_t<_Range>, _Proj>,
878 constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
879 operator()(_Range&& __r, _Out __result,
880 const _Tp1& __old_value,
const _Tp2& __new_value,
881 _Proj __proj = {})
const
883 return (*
this)(ranges::begin(__r), ranges::end(__r),
889 inline constexpr __replace_copy_fn replace_copy{};
891 template<
typename _Iter,
typename _Out>
892 using replace_copy_if_result = in_out_result<_Iter, _Out>;
894 struct __replace_copy_if_fn
896 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
897 typename _Tp, output_iterator<const _Tp&> _Out,
898 typename _Proj =
identity,
899 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
900 requires indirectly_copyable<_Iter, _Out>
901 constexpr replace_copy_if_result<_Iter, _Out>
902 operator()(_Iter __first, _Sent __last, _Out __result,
903 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
905 for (; __first != __last; ++__first, (void)++__result)
907 *__result = __new_value;
909 *__result = *__first;
913 template<input_range _Range,
914 typename _Tp, output_iterator<const _Tp&> _Out,
915 typename _Proj = identity,
916 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
918 requires indirectly_copyable<iterator_t<_Range>, _Out>
919 constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
920 operator()(_Range&& __r, _Out __result,
921 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
923 return (*
this)(ranges::begin(__r), ranges::end(__r),
929 inline constexpr __replace_copy_if_fn replace_copy_if{};
931 struct __generate_n_fn
933 template<input_or_output_iterator _Out, copy_constructible _Fp>
934 requires invocable<_Fp&>
935 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
937 operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen)
const
939 for (; __n > 0; --__n, (void)++__first)
945 inline constexpr __generate_n_fn generate_n{};
949 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
950 copy_constructible _Fp>
951 requires invocable<_Fp&>
952 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
954 operator()(_Out __first, _Sent __last, _Fp __gen)
const
956 for (; __first != __last; ++__first)
961 template<
typename _Range, copy_constructible _Fp>
962 requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
963 constexpr borrowed_iterator_t<_Range>
964 operator()(_Range&& __r, _Fp __gen)
const
966 return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__gen));
970 inline constexpr __generate_fn generate{};
972 struct __remove_if_fn
974 template<permutable _Iter, sentinel_for<_Iter> _Sent,
975 typename _Proj =
identity,
976 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
977 constexpr subrange<_Iter>
978 operator()(_Iter __first, _Sent __last,
979 _Pred __pred, _Proj __proj = {})
const
981 __first = ranges::find_if(__first, __last, __pred, __proj);
982 if (__first == __last)
983 return {__first, __first};
985 auto __result = __first;
987 for (; __first != __last; ++__first)
994 return {__result, __first};
997 template<forward_range _Range,
typename _Proj = identity,
998 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1000 requires permutable<iterator_t<_Range>>
1001 constexpr borrowed_subrange_t<_Range>
1002 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
1004 return (*
this)(ranges::begin(__r), ranges::end(__r),
1009 inline constexpr __remove_if_fn remove_if{};
1013 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1014 typename _Tp,
typename _Proj =
identity>
1015 requires indirect_binary_predicate<ranges::equal_to,
1016 projected<_Iter, _Proj>,
1018 constexpr subrange<_Iter>
1019 operator()(_Iter __first, _Sent __last,
1020 const _Tp& __value, _Proj __proj = {})
const
1022 auto __pred = [&] (
auto&& __arg) ->
bool {
1025 return ranges::remove_if(__first, __last,
1029 template<forward_range _Range,
typename _Tp,
typename _Proj =
identity>
1030 requires permutable<iterator_t<_Range>>
1031 && indirect_binary_predicate<ranges::equal_to,
1032 projected<iterator_t<_Range>, _Proj>,
1034 constexpr borrowed_subrange_t<_Range>
1035 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
1037 return (*
this)(ranges::begin(__r), ranges::end(__r),
1042 inline constexpr __remove_fn remove{};
1044 template<
typename _Iter,
typename _Out>
1045 using remove_copy_if_result = in_out_result<_Iter, _Out>;
1047 struct __remove_copy_if_fn
1049 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1050 weakly_incrementable _Out,
typename _Proj =
identity,
1051 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1052 requires indirectly_copyable<_Iter, _Out>
1053 constexpr remove_copy_if_result<_Iter, _Out>
1054 operator()(_Iter __first, _Sent __last, _Out __result,
1055 _Pred __pred, _Proj __proj = {})
const
1057 for (; __first != __last; ++__first)
1060 *__result = *__first;
1066 template<input_range _Range, weakly_incrementable _Out,
1067 typename _Proj = identity,
1068 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1070 requires indirectly_copyable<iterator_t<_Range>, _Out>
1071 constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1072 operator()(_Range&& __r, _Out __result,
1073 _Pred __pred, _Proj __proj = {})
const
1075 return (*
this)(ranges::begin(__r), ranges::end(__r),
1081 inline constexpr __remove_copy_if_fn remove_copy_if{};
1083 template<
typename _Iter,
typename _Out>
1084 using remove_copy_result = in_out_result<_Iter, _Out>;
1086 struct __remove_copy_fn
1088 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1089 weakly_incrementable _Out,
typename _Tp,
typename _Proj =
identity>
1090 requires indirectly_copyable<_Iter, _Out>
1091 && indirect_binary_predicate<ranges::equal_to,
1092 projected<_Iter, _Proj>,
1094 constexpr remove_copy_result<_Iter, _Out>
1095 operator()(_Iter __first, _Sent __last, _Out __result,
1096 const _Tp& __value, _Proj __proj = {})
const
1098 for (; __first != __last; ++__first)
1101 *__result = *__first;
1107 template<input_range _Range, weakly_incrementable _Out,
1108 typename _Tp,
typename _Proj = identity>
1109 requires indirectly_copyable<iterator_t<_Range>, _Out>
1110 && indirect_binary_predicate<ranges::equal_to,
1111 projected<iterator_t<_Range>, _Proj>,
1113 constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
1114 operator()(_Range&& __r, _Out __result,
1115 const _Tp& __value, _Proj __proj = {})
const
1117 return (*
this)(ranges::begin(__r), ranges::end(__r),
1122 inline constexpr __remove_copy_fn remove_copy{};
1126 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1127 typename _Proj =
identity,
1128 indirect_equivalence_relation<
1129 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1130 constexpr subrange<_Iter>
1131 operator()(_Iter __first, _Sent __last,
1132 _Comp __comp = {}, _Proj __proj = {})
const
1134 __first = ranges::adjacent_find(__first, __last, __comp, __proj);
1135 if (__first == __last)
1136 return {__first, __first};
1138 auto __dest = __first;
1140 while (++__first != __last)
1145 return {++__dest, __first};
1148 template<forward_range _Range,
typename _Proj = identity,
1149 indirect_equivalence_relation<
1150 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1151 requires permutable<iterator_t<_Range>>
1152 constexpr borrowed_subrange_t<_Range>
1153 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1155 return (*
this)(ranges::begin(__r), ranges::end(__r),
1160 inline constexpr __unique_fn unique{};
1164 template<
typename _Out,
typename _Tp>
1165 concept __can_reread_output = input_iterator<_Out>
1166 && same_as<_Tp, iter_value_t<_Out>>;
1169 template<
typename _Iter,
typename _Out>
1170 using unique_copy_result = in_out_result<_Iter, _Out>;
1172 struct __unique_copy_fn
1174 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1175 weakly_incrementable _Out,
typename _Proj =
identity,
1176 indirect_equivalence_relation<
1177 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1178 requires indirectly_copyable<_Iter, _Out>
1179 && (forward_iterator<_Iter>
1180 || __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
1181 || indirectly_copyable_storable<_Iter, _Out>)
1182 constexpr unique_copy_result<_Iter, _Out>
1183 operator()(_Iter __first, _Sent __last, _Out __result,
1184 _Comp __comp = {}, _Proj __proj = {})
const
1186 if (__first == __last)
1190 if constexpr (forward_iterator<_Iter>)
1192 auto __next = __first;
1193 *__result = *__next;
1194 while (++__next != __last)
1200 *++__result = *__first;
1204 else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
1206 *__result = *__first;
1207 while (++__first != __last)
1211 *++__result = *__first;
1216 auto __value = *__first;
1217 *__result = __value;
1218 while (++__first != __last)
1225 *++__result = __value;
1232 template<input_range _Range,
1233 weakly_incrementable _Out,
typename _Proj = identity,
1234 indirect_equivalence_relation<
1235 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1236 requires indirectly_copyable<iterator_t<_Range>, _Out>
1237 && (forward_iterator<iterator_t<_Range>>
1238 || __detail::__can_reread_output<_Out, range_value_t<_Range>>
1239 || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1240 constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1241 operator()(_Range&& __r, _Out __result,
1242 _Comp __comp = {}, _Proj __proj = {})
const
1244 return (*
this)(ranges::begin(__r), ranges::end(__r),
1250 inline constexpr __unique_copy_fn unique_copy{};
1254 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1255 requires permutable<_Iter>
1257 operator()(_Iter __first, _Sent __last)
const
1259 auto __i = ranges::next(__first, __last);
1262 if constexpr (random_access_iterator<_Iter>)
1264 if (__first != __last)
1267 while (__first < __tail)
1269 ranges::iter_swap(__first, __tail);
1279 if (__first == __tail || __first == --__tail)
1283 ranges::iter_swap(__first, __tail);
1290 template<b
idirectional_range _Range>
1291 requires permutable<iterator_t<_Range>>
1292 constexpr borrowed_iterator_t<_Range>
1293 operator()(_Range&& __r)
const
1295 return (*
this)(ranges::begin(__r), ranges::end(__r));
1299 inline constexpr __reverse_fn reverse{};
1301 template<
typename _Iter,
typename _Out>
1302 using reverse_copy_result = in_out_result<_Iter, _Out>;
1304 struct __reverse_copy_fn
1306 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1307 weakly_incrementable _Out>
1308 requires indirectly_copyable<_Iter, _Out>
1309 constexpr reverse_copy_result<_Iter, _Out>
1310 operator()(_Iter __first, _Sent __last, _Out __result)
const
1312 auto __i = ranges::next(__first, __last);
1314 while (__first != __tail)
1317 *__result = *__tail;
1323 template<b
idirectional_range _Range, weakly_incrementable _Out>
1324 requires indirectly_copyable<iterator_t<_Range>, _Out>
1325 constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1326 operator()(_Range&& __r, _Out __result)
const
1328 return (*
this)(ranges::begin(__r), ranges::end(__r),
1333 inline constexpr __reverse_copy_fn reverse_copy{};
1337 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1338 constexpr subrange<_Iter>
1339 operator()(_Iter __first, _Iter __middle, _Sent __last)
const
1341 auto __lasti = ranges::next(__first, __last);
1342 if (__first == __middle)
1343 return {__lasti, __lasti};
1344 if (__last == __middle)
1347 if constexpr (random_access_iterator<_Iter>)
1349 auto __n = __lasti - __first;
1350 auto __k = __middle - __first;
1352 if (__k == __n - __k)
1354 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1359 auto __ret = __first + (__lasti - __middle);
1363 if (__k < __n - __k)
1367 if constexpr (__is_pod(iter_value_t<_Iter>))
1371 ranges::move(__p + 1, __p + __n, __p);
1375 auto __q = __p + __k;
1376 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1378 ranges::iter_swap(__p, __q);
1385 ranges::swap(__n, __k);
1393 if constexpr (__is_pod(iter_value_t<_Iter>))
1397 ranges::move_backward(__p, __p + __n - 1, __p + __n);
1401 auto __q = __p + __n;
1403 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1407 ranges::iter_swap(__p, __q);
1412 std::swap(__n, __k);
1416 else if constexpr (bidirectional_iterator<_Iter>)
1418 auto __tail = __lasti;
1420 ranges::reverse(__first, __middle);
1421 ranges::reverse(__middle, __tail);
1423 while (__first != __middle && __middle != __tail)
1425 ranges::iter_swap(__first, --__tail);
1429 if (__first == __middle)
1431 ranges::reverse(__middle, __tail);
1436 ranges::reverse(__first, __middle);
1442 auto __first2 = __middle;
1445 ranges::iter_swap(__first, __first2);
1448 if (__first == __middle)
1449 __middle = __first2;
1450 }
while (__first2 != __last);
1452 auto __ret = __first;
1454 __first2 = __middle;
1456 while (__first2 != __last)
1458 ranges::iter_swap(__first, __first2);
1461 if (__first == __middle)
1462 __middle = __first2;
1463 else if (__first2 == __last)
1464 __first2 = __middle;
1470 template<forward_range _Range>
1471 requires permutable<iterator_t<_Range>>
1472 constexpr borrowed_subrange_t<_Range>
1473 operator()(_Range&& __r, iterator_t<_Range> __middle)
const
1475 return (*
this)(ranges::begin(__r),
std::move(__middle),
1480 inline constexpr __rotate_fn rotate{};
1482 template<
typename _Iter,
typename _Out>
1483 using rotate_copy_result = in_out_result<_Iter, _Out>;
1485 struct __rotate_copy_fn
1487 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1488 weakly_incrementable _Out>
1489 requires indirectly_copyable<_Iter, _Out>
1490 constexpr rotate_copy_result<_Iter, _Out>
1491 operator()(_Iter __first, _Iter __middle, _Sent __last,
1492 _Out __result)
const
1494 auto __copy1 = ranges::copy(__middle,
1497 auto __copy2 = ranges::copy(
std::move(__first),
1503 template<forward_range _Range, weakly_incrementable _Out>
1504 requires indirectly_copyable<iterator_t<_Range>, _Out>
1505 constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1506 operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result)
const
1508 return (*
this)(ranges::begin(__r),
std::move(__middle),
1513 inline constexpr __rotate_copy_fn rotate_copy{};
1517 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1518 weakly_incrementable _Out,
typename _Gen>
1519 requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
1520 && indirectly_copyable<_Iter, _Out>
1521 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1523 operator()(_Iter __first, _Sent __last, _Out __out,
1524 iter_difference_t<_Iter> __n, _Gen&& __g)
const
1526 if constexpr (forward_iterator<_Iter>)
1530 auto __lasti = ranges::next(__first, __last);
1531 return _GLIBCXX_STD_A::
1537 using __distrib_type
1538 = uniform_int_distribution<iter_difference_t<_Iter>>;
1539 using __param_type =
typename __distrib_type::param_type;
1540 __distrib_type __d{};
1541 iter_difference_t<_Iter> __sample_sz = 0;
1542 while (__first != __last && __sample_sz != __n)
1544 __out[__sample_sz++] = *__first;
1547 for (
auto __pop_sz = __sample_sz; __first != __last;
1548 ++__first, (void) ++__pop_sz)
1550 const auto __k = __d(__g, __param_type{0, __pop_sz});
1552 __out[__k] = *__first;
1554 return __out + __sample_sz;
1558 template<input_range _Range, weakly_incrementable _Out,
typename _Gen>
1559 requires (forward_range<_Range> || random_access_iterator<_Out>)
1560 && indirectly_copyable<iterator_t<_Range>, _Out>
1561 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1563 operator()(_Range&& __r, _Out __out,
1564 range_difference_t<_Range> __n, _Gen&& __g)
const
1566 return (*
this)(ranges::begin(__r), ranges::end(__r),
1572 inline constexpr __sample_fn sample{};
1576 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1578 requires permutable<_Iter>
1579 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1581 operator()(_Iter __first, _Sent __last, _Gen&& __g)
const
1583 auto __lasti = ranges::next(__first, __last);
1588 template<random_access_range _Range,
typename _Gen>
1589 requires permutable<iterator_t<_Range>>
1590 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1591 borrowed_iterator_t<_Range>
1592 operator()(_Range&& __r, _Gen&& __g)
const
1594 return (*
this)(ranges::begin(__r), ranges::end(__r),
1599 inline constexpr __shuffle_fn shuffle{};
1601 struct __push_heap_fn
1603 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1604 typename _Comp = ranges::less,
typename _Proj =
identity>
1605 requires sortable<_Iter, _Comp, _Proj>
1607 operator()(_Iter __first, _Sent __last,
1608 _Comp __comp = {}, _Proj __proj = {})
const
1610 auto __lasti = ranges::next(__first, __last);
1611 std::push_heap(__first, __lasti,
1612 __detail::__make_comp_proj(__comp, __proj));
1616 template<random_access_range _Range,
1617 typename _Comp = ranges::less,
typename _Proj = identity>
1618 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1619 constexpr borrowed_iterator_t<_Range>
1620 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1622 return (*
this)(ranges::begin(__r), ranges::end(__r),
1627 inline constexpr __push_heap_fn push_heap{};
1629 struct __pop_heap_fn
1631 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1632 typename _Comp = ranges::less,
typename _Proj =
identity>
1633 requires sortable<_Iter, _Comp, _Proj>
1635 operator()(_Iter __first, _Sent __last,
1636 _Comp __comp = {}, _Proj __proj = {})
const
1638 auto __lasti = ranges::next(__first, __last);
1639 std::pop_heap(__first, __lasti,
1640 __detail::__make_comp_proj(__comp, __proj));
1644 template<random_access_range _Range,
1645 typename _Comp = ranges::less,
typename _Proj = identity>
1646 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1647 constexpr borrowed_iterator_t<_Range>
1648 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1650 return (*
this)(ranges::begin(__r), ranges::end(__r),
1655 inline constexpr __pop_heap_fn pop_heap{};
1657 struct __make_heap_fn
1659 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1660 typename _Comp = ranges::less,
typename _Proj =
identity>
1661 requires sortable<_Iter, _Comp, _Proj>
1663 operator()(_Iter __first, _Sent __last,
1664 _Comp __comp = {}, _Proj __proj = {})
const
1666 auto __lasti = ranges::next(__first, __last);
1667 std::make_heap(__first, __lasti,
1668 __detail::__make_comp_proj(__comp, __proj));
1672 template<random_access_range _Range,
1673 typename _Comp = ranges::less,
typename _Proj = identity>
1674 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1675 constexpr borrowed_iterator_t<_Range>
1676 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1678 return (*
this)(ranges::begin(__r), ranges::end(__r),
1683 inline constexpr __make_heap_fn make_heap{};
1685 struct __sort_heap_fn
1687 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1688 typename _Comp = ranges::less,
typename _Proj =
identity>
1689 requires sortable<_Iter, _Comp, _Proj>
1691 operator()(_Iter __first, _Sent __last,
1692 _Comp __comp = {}, _Proj __proj = {})
const
1694 auto __lasti = ranges::next(__first, __last);
1695 std::sort_heap(__first, __lasti,
1696 __detail::__make_comp_proj(__comp, __proj));
1700 template<random_access_range _Range,
1701 typename _Comp = ranges::less,
typename _Proj = identity>
1702 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1703 constexpr borrowed_iterator_t<_Range>
1704 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1706 return (*
this)(ranges::begin(__r), ranges::end(__r),
1711 inline constexpr __sort_heap_fn sort_heap{};
1713 struct __is_heap_until_fn
1715 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1716 typename _Proj =
identity,
1717 indirect_strict_weak_order<projected<_Iter, _Proj>>
1718 _Comp = ranges::less>
1720 operator()(_Iter __first, _Sent __last,
1721 _Comp __comp = {}, _Proj __proj = {})
const
1723 iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
1724 iter_difference_t<_Iter> __parent = 0, __child = 1;
1725 for (; __child < __n; ++__child)
1729 return __first + __child;
1730 else if ((__child & 1) == 0)
1733 return __first + __n;
1736 template<random_access_range _Range,
1737 typename _Proj = identity,
1738 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1739 _Comp = ranges::less>
1740 constexpr borrowed_iterator_t<_Range>
1741 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1743 return (*
this)(ranges::begin(__r), ranges::end(__r),
1748 inline constexpr __is_heap_until_fn is_heap_until{};
1752 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1753 typename _Proj =
identity,
1754 indirect_strict_weak_order<projected<_Iter, _Proj>>
1755 _Comp = ranges::less>
1757 operator()(_Iter __first, _Sent __last,
1758 _Comp __comp = {}, _Proj __proj = {})
const
1761 == ranges::is_heap_until(__first, __last,
1766 template<random_access_range _Range,
1767 typename _Proj = identity,
1768 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1769 _Comp = ranges::less>
1771 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1773 return (*
this)(ranges::begin(__r), ranges::end(__r),
1778 inline constexpr __is_heap_fn is_heap{};
1782 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1783 typename _Comp = ranges::less,
typename _Proj =
identity>
1784 requires sortable<_Iter, _Comp, _Proj>
1786 operator()(_Iter __first, _Sent __last,
1787 _Comp __comp = {}, _Proj __proj = {})
const
1789 auto __lasti = ranges::next(__first, __last);
1790 _GLIBCXX_STD_A::sort(
std::move(__first), __lasti,
1791 __detail::__make_comp_proj(__comp, __proj));
1795 template<random_access_range _Range,
1796 typename _Comp = ranges::less,
typename _Proj = identity>
1797 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1798 constexpr borrowed_iterator_t<_Range>
1799 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1801 return (*
this)(ranges::begin(__r), ranges::end(__r),
1806 inline constexpr __sort_fn sort{};
1808 struct __stable_sort_fn
1810 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1811 typename _Comp = ranges::less,
typename _Proj =
identity>
1812 requires sortable<_Iter, _Comp, _Proj>
1814 operator()(_Iter __first, _Sent __last,
1815 _Comp __comp = {}, _Proj __proj = {})
const
1817 auto __lasti = ranges::next(__first, __last);
1818 std::stable_sort(
std::move(__first), __lasti,
1819 __detail::__make_comp_proj(__comp, __proj));
1823 template<random_access_range _Range,
1824 typename _Comp = ranges::less,
typename _Proj = identity>
1825 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1826 borrowed_iterator_t<_Range>
1827 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1829 return (*
this)(ranges::begin(__r), ranges::end(__r),
1834 inline constexpr __stable_sort_fn stable_sort{};
1836 struct __partial_sort_fn
1838 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1839 typename _Comp = ranges::less,
typename _Proj =
identity>
1840 requires sortable<_Iter, _Comp, _Proj>
1842 operator()(_Iter __first, _Iter __middle, _Sent __last,
1843 _Comp __comp = {}, _Proj __proj = {})
const
1845 if (__first == __middle)
1846 return ranges::next(__first, __last);
1848 ranges::make_heap(__first, __middle, __comp, __proj);
1849 auto __i = __middle;
1850 for (; __i != __last; ++__i)
1855 ranges::pop_heap(__first, __middle, __comp, __proj);
1856 ranges::iter_swap(__middle-1, __i);
1857 ranges::push_heap(__first, __middle, __comp, __proj);
1859 ranges::sort_heap(__first, __middle, __comp, __proj);
1864 template<random_access_range _Range,
1865 typename _Comp = ranges::less,
typename _Proj = identity>
1866 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1867 constexpr borrowed_iterator_t<_Range>
1868 operator()(_Range&& __r, iterator_t<_Range> __middle,
1869 _Comp __comp = {}, _Proj __proj = {})
const
1871 return (*
this)(ranges::begin(__r),
std::move(__middle),
1877 inline constexpr __partial_sort_fn partial_sort{};
1879 template<
typename _Iter,
typename _Out>
1880 using partial_sort_copy_result = in_out_result<_Iter, _Out>;
1882 struct __partial_sort_copy_fn
1884 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1885 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1886 typename _Comp = ranges::less,
1887 typename _Proj1 =
identity,
typename _Proj2 =
identity>
1888 requires indirectly_copyable<_Iter1, _Iter2>
1889 && sortable<_Iter2, _Comp, _Proj2>
1890 && indirect_strict_weak_order<_Comp,
1891 projected<_Iter1, _Proj1>,
1892 projected<_Iter2, _Proj2>>
1893 constexpr partial_sort_copy_result<_Iter1, _Iter2>
1894 operator()(_Iter1 __first, _Sent1 __last,
1895 _Iter2 __result_first, _Sent2 __result_last,
1897 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1899 if (__result_first == __result_last)
1902 auto __lasti = ranges::next(
std::move(__first),
1907 auto __result_real_last = __result_first;
1908 while (__first != __last && __result_real_last != __result_last)
1910 *__result_real_last = *__first;
1911 ++__result_real_last;
1915 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
1916 for (; __first != __last; ++__first)
1921 ranges::pop_heap(__result_first, __result_real_last,
1923 *(__result_real_last-1) = *__first;
1924 ranges::push_heap(__result_first, __result_real_last,
1927 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
1932 template<input_range _Range1, random_access_range _Range2,
1933 typename _Comp = ranges::less,
1934 typename _Proj1 = identity,
typename _Proj2 = identity>
1935 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
1936 && sortable<iterator_t<_Range2>, _Comp, _Proj2>
1937 && indirect_strict_weak_order<_Comp,
1938 projected<iterator_t<_Range1>, _Proj1>,
1939 projected<iterator_t<_Range2>, _Proj2>>
1940 constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
1941 borrowed_iterator_t<_Range2>>
1942 operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
1943 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1945 return (*
this)(ranges::begin(__r), ranges::end(__r),
1946 ranges::begin(__out), ranges::end(__out),
1952 inline constexpr __partial_sort_copy_fn partial_sort_copy{};
1954 struct __is_sorted_until_fn
1956 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1957 typename _Proj =
identity,
1958 indirect_strict_weak_order<projected<_Iter, _Proj>>
1959 _Comp = ranges::less>
1961 operator()(_Iter __first, _Sent __last,
1962 _Comp __comp = {}, _Proj __proj = {})
const
1964 if (__first == __last)
1967 auto __next = __first;
1968 for (++__next; __next != __last; __first = __next, (void)++__next)
1976 template<forward_range _Range,
typename _Proj = identity,
1977 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1978 _Comp = ranges::less>
1979 constexpr borrowed_iterator_t<_Range>
1980 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1982 return (*
this)(ranges::begin(__r), ranges::end(__r),
1987 inline constexpr __is_sorted_until_fn is_sorted_until{};
1989 struct __is_sorted_fn
1991 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1992 typename _Proj =
identity,
1993 indirect_strict_weak_order<projected<_Iter, _Proj>>
1994 _Comp = ranges::less>
1996 operator()(_Iter __first, _Sent __last,
1997 _Comp __comp = {}, _Proj __proj = {})
const
1999 if (__first == __last)
2002 auto __next = __first;
2003 for (++__next; __next != __last; __first = __next, (void)++__next)
2011 template<forward_range _Range,
typename _Proj = identity,
2012 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2013 _Comp = ranges::less>
2015 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2017 return (*
this)(ranges::begin(__r), ranges::end(__r),
2022 inline constexpr __is_sorted_fn is_sorted{};
2024 struct __nth_element_fn
2026 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2027 typename _Comp = ranges::less,
typename _Proj =
identity>
2028 requires sortable<_Iter, _Comp, _Proj>
2030 operator()(_Iter __first, _Iter __nth, _Sent __last,
2031 _Comp __comp = {}, _Proj __proj = {})
const
2033 auto __lasti = ranges::next(__first, __last);
2036 __detail::__make_comp_proj(__comp, __proj));
2040 template<random_access_range _Range,
2041 typename _Comp = ranges::less,
typename _Proj = identity>
2042 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2043 constexpr borrowed_iterator_t<_Range>
2044 operator()(_Range&& __r, iterator_t<_Range> __nth,
2045 _Comp __comp = {}, _Proj __proj = {})
const
2047 return (*
this)(ranges::begin(__r),
std::move(__nth),
2052 inline constexpr __nth_element_fn nth_element{};
2054 struct __lower_bound_fn
2056 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2057 typename _Tp,
typename _Proj =
identity,
2058 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2059 _Comp = ranges::less>
2061 operator()(_Iter __first, _Sent __last,
2062 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2064 auto __len = ranges::distance(__first, __last);
2068 auto __half = __len / 2;
2069 auto __middle = __first;
2070 ranges::advance(__middle, __half);
2075 __len = __len - __half - 1;
2083 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2084 indirect_strict_weak_order<
const _Tp*,
2085 projected<iterator_t<_Range>, _Proj>>
2086 _Comp = ranges::less>
2087 constexpr borrowed_iterator_t<_Range>
2088 operator()(_Range&& __r,
2089 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2091 return (*
this)(ranges::begin(__r), ranges::end(__r),
2096 inline constexpr __lower_bound_fn lower_bound{};
2098 struct __upper_bound_fn
2100 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2101 typename _Tp,
typename _Proj =
identity,
2102 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2103 _Comp = ranges::less>
2105 operator()(_Iter __first, _Sent __last,
2106 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2108 auto __len = ranges::distance(__first, __last);
2112 auto __half = __len / 2;
2113 auto __middle = __first;
2114 ranges::advance(__middle, __half);
2121 __len = __len - __half - 1;
2127 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2128 indirect_strict_weak_order<
const _Tp*,
2129 projected<iterator_t<_Range>, _Proj>>
2130 _Comp = ranges::less>
2131 constexpr borrowed_iterator_t<_Range>
2132 operator()(_Range&& __r,
2133 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2135 return (*
this)(ranges::begin(__r), ranges::end(__r),
2140 inline constexpr __upper_bound_fn upper_bound{};
2142 struct __equal_range_fn
2144 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2145 typename _Tp,
typename _Proj =
identity,
2146 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2147 _Comp = ranges::less>
2148 constexpr subrange<_Iter>
2149 operator()(_Iter __first, _Sent __last,
2150 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2152 auto __len = ranges::distance(__first, __last);
2156 auto __half = __len / 2;
2157 auto __middle = __first;
2158 ranges::advance(__middle, __half);
2165 __len = __len - __half - 1;
2174 = ranges::lower_bound(__first, __middle,
2175 __value, __comp, __proj);
2176 ranges::advance(__first, __len);
2178 = ranges::upper_bound(++__middle, __first,
2179 __value, __comp, __proj);
2180 return {__left, __right};
2183 return {__first, __first};
2186 template<forward_range _Range,
2187 typename _Tp,
typename _Proj = identity,
2188 indirect_strict_weak_order<
const _Tp*,
2189 projected<iterator_t<_Range>, _Proj>>
2190 _Comp = ranges::less>
2191 constexpr borrowed_subrange_t<_Range>
2192 operator()(_Range&& __r,
const _Tp& __value,
2193 _Comp __comp = {}, _Proj __proj = {})
const
2195 return (*
this)(ranges::begin(__r), ranges::end(__r),
2200 inline constexpr __equal_range_fn equal_range{};
2202 struct __binary_search_fn
2204 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2205 typename _Tp,
typename _Proj =
identity,
2206 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2207 _Comp = ranges::less>
2209 operator()(_Iter __first, _Sent __last,
2210 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2212 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2219 template<forward_range _Range,
2220 typename _Tp,
typename _Proj = identity,
2221 indirect_strict_weak_order<
const _Tp*,
2222 projected<iterator_t<_Range>, _Proj>>
2223 _Comp = ranges::less>
2225 operator()(_Range&& __r,
const _Tp& __value, _Comp __comp = {},
2226 _Proj __proj = {})
const
2228 return (*
this)(ranges::begin(__r), ranges::end(__r),
2233 inline constexpr __binary_search_fn binary_search{};
2235 struct __is_partitioned_fn
2237 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2238 typename _Proj =
identity,
2239 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2241 operator()(_Iter __first, _Sent __last,
2242 _Pred __pred, _Proj __proj = {})
const
2244 __first = ranges::find_if_not(
std::move(__first), __last,
2246 if (__first == __last)
2253 template<input_range _Range,
typename _Proj = identity,
2254 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2257 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2259 return (*
this)(ranges::begin(__r), ranges::end(__r),
2264 inline constexpr __is_partitioned_fn is_partitioned{};
2266 struct __partition_fn
2268 template<permutable _Iter, sentinel_for<_Iter> _Sent,
2269 typename _Proj =
identity,
2270 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2271 constexpr subrange<_Iter>
2272 operator()(_Iter __first, _Sent __last,
2273 _Pred __pred, _Proj __proj = {})
const
2275 if constexpr (bidirectional_iterator<_Iter>)
2277 auto __lasti = ranges::next(__first, __last);
2278 auto __tail = __lasti;
2282 if (__first == __tail)
2291 if (__first == __tail)
2298 ranges::iter_swap(__first, __tail);
2304 if (__first == __last)
2305 return {__first, __first};
2308 if (++__first == __last)
2309 return {__first, __first};
2311 auto __next = __first;
2312 while (++__next != __last)
2315 ranges::iter_swap(__first, __next);
2323 template<forward_range _Range,
typename _Proj = identity,
2324 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2326 requires permutable<iterator_t<_Range>>
2327 constexpr borrowed_subrange_t<_Range>
2328 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2330 return (*
this)(ranges::begin(__r), ranges::end(__r),
2335 inline constexpr __partition_fn partition{};
2338 struct __stable_partition_fn
2340 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2341 typename _Proj =
identity,
2342 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2343 requires permutable<_Iter>
2345 operator()(_Iter __first, _Sent __last,
2346 _Pred __pred, _Proj __proj = {})
const
2348 auto __lasti = ranges::next(__first, __last);
2350 = std::stable_partition(
std::move(__first), __lasti,
2351 __detail::__make_pred_proj(__pred, __proj));
2355 template<bidirectional_range _Range,
typename _Proj = identity,
2356 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2358 requires permutable<iterator_t<_Range>>
2359 borrowed_subrange_t<_Range>
2360 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2362 return (*
this)(ranges::begin(__r), ranges::end(__r),
2367 inline constexpr __stable_partition_fn stable_partition{};
2370 template<
typename _Iter,
typename _Out1,
typename _Out2>
2371 struct in_out_out_result
2373 [[no_unique_address]] _Iter in;
2374 [[no_unique_address]] _Out1 out1;
2375 [[no_unique_address]] _Out2 out2;
2377 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2378 requires convertible_to<const _Iter&, _IIter>
2379 && convertible_to<const _Out1&, _OOut1>
2380 && convertible_to<const _Out2&, _OOut2>
2382 operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
2383 {
return {in, out1, out2}; }
2385 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2386 requires convertible_to<_Iter, _IIter>
2387 && convertible_to<_Out1, _OOut1>
2388 && convertible_to<_Out2, _OOut2>
2390 operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2394 template<
typename _Iter,
typename _Out1,
typename _Out2>
2395 using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2397 struct __partition_copy_fn
2399 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2400 weakly_incrementable _Out1, weakly_incrementable _Out2,
2401 typename _Proj =
identity,
2402 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2403 requires indirectly_copyable<_Iter, _Out1>
2404 && indirectly_copyable<_Iter, _Out2>
2405 constexpr partition_copy_result<_Iter, _Out1, _Out2>
2406 operator()(_Iter __first, _Sent __last,
2407 _Out1 __out_true, _Out2 __out_false,
2408 _Pred __pred, _Proj __proj = {})
const
2410 for (; __first != __last; ++__first)
2413 *__out_true = *__first;
2418 *__out_false = *__first;
2426 template<input_range _Range, weakly_incrementable _Out1,
2427 weakly_incrementable _Out2,
2428 typename _Proj = identity,
2429 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2431 requires indirectly_copyable<iterator_t<_Range>, _Out1>
2432 && indirectly_copyable<iterator_t<_Range>, _Out2>
2433 constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2>
2434 operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false,
2435 _Pred __pred, _Proj __proj = {})
const
2437 return (*
this)(ranges::begin(__r), ranges::end(__r),
2443 inline constexpr __partition_copy_fn partition_copy{};
2445 struct __partition_point_fn
2447 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2448 typename _Proj =
identity,
2449 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2451 operator()(_Iter __first, _Sent __last,
2452 _Pred __pred, _Proj __proj = {})
const
2454 auto __len = ranges::distance(__first, __last);
2458 auto __half = __len / 2;
2459 auto __middle = __first;
2460 ranges::advance(__middle, __half);
2465 __len = __len - __half - 1;
2473 template<forward_range _Range,
typename _Proj = identity,
2474 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2476 constexpr borrowed_iterator_t<_Range>
2477 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2479 return (*
this)(ranges::begin(__r), ranges::end(__r),
2484 inline constexpr __partition_point_fn partition_point{};
2486 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2487 using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2491 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2492 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2493 weakly_incrementable _Out,
typename _Comp = ranges::less,
2494 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2495 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2496 constexpr merge_result<_Iter1, _Iter2, _Out>
2497 operator()(_Iter1 __first1, _Sent1 __last1,
2498 _Iter2 __first2, _Sent2 __last2, _Out __result,
2500 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2502 while (__first1 != __last1 && __first2 != __last2)
2508 *__result = *__first2;
2513 *__result = *__first1;
2526 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2527 typename _Comp = ranges::less,
2528 typename _Proj1 = identity,
typename _Proj2 = identity>
2529 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2530 _Comp, _Proj1, _Proj2>
2531 constexpr merge_result<borrowed_iterator_t<_Range1>,
2532 borrowed_iterator_t<_Range2>,
2534 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2536 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2538 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2539 ranges::begin(__r2), ranges::end(__r2),
2545 inline constexpr __merge_fn merge{};
2547 struct __inplace_merge_fn
2549 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2550 typename _Comp = ranges::less,
2551 typename _Proj =
identity>
2552 requires sortable<_Iter, _Comp, _Proj>
2554 operator()(_Iter __first, _Iter __middle, _Sent __last,
2555 _Comp __comp = {}, _Proj __proj = {})
const
2557 auto __lasti = ranges::next(__first, __last);
2559 __detail::__make_comp_proj(__comp, __proj));
2563 template<bidirectional_range _Range,
2564 typename _Comp = ranges::less,
typename _Proj = identity>
2565 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2566 borrowed_iterator_t<_Range>
2567 operator()(_Range&& __r, iterator_t<_Range> __middle,
2568 _Comp __comp = {}, _Proj __proj = {})
const
2570 return (*
this)(ranges::begin(__r),
std::move(__middle),
2576 inline constexpr __inplace_merge_fn inplace_merge{};
2578 struct __includes_fn
2580 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2581 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2582 typename _Proj1 =
identity,
typename _Proj2 =
identity,
2583 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2584 projected<_Iter2, _Proj2>>
2585 _Comp = ranges::less>
2587 operator()(_Iter1 __first1, _Sent1 __last1,
2588 _Iter2 __first2, _Sent2 __last2,
2590 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2592 while (__first1 != __last1 && __first2 != __last2)
2607 return __first2 == __last2;
2610 template<input_range _Range1, input_range _Range2,
2611 typename _Proj1 = identity,
typename _Proj2 = identity,
2612 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2613 projected<iterator_t<_Range2>, _Proj2>>
2614 _Comp = ranges::less>
2616 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2617 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2619 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2620 ranges::begin(__r2), ranges::end(__r2),
2626 inline constexpr __includes_fn includes{};
2628 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2629 using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2631 struct __set_union_fn
2633 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2634 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2635 weakly_incrementable _Out,
typename _Comp = ranges::less,
2636 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2637 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2638 constexpr set_union_result<_Iter1, _Iter2, _Out>
2639 operator()(_Iter1 __first1, _Sent1 __last1,
2640 _Iter2 __first2, _Sent2 __last2,
2641 _Out __result, _Comp __comp = {},
2642 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2644 while (__first1 != __last1 && __first2 != __last2)
2650 *__result = *__first1;
2657 *__result = *__first2;
2662 *__result = *__first1;
2676 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2677 typename _Comp = ranges::less,
2678 typename _Proj1 = identity,
typename _Proj2 = identity>
2679 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2680 _Comp, _Proj1, _Proj2>
2681 constexpr set_union_result<borrowed_iterator_t<_Range1>,
2682 borrowed_iterator_t<_Range2>, _Out>
2683 operator()(_Range1&& __r1, _Range2&& __r2,
2684 _Out __result, _Comp __comp = {},
2685 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2687 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2688 ranges::begin(__r2), ranges::end(__r2),
2694 inline constexpr __set_union_fn set_union{};
2696 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2697 using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2699 struct __set_intersection_fn
2701 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2702 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2703 weakly_incrementable _Out,
typename _Comp = ranges::less,
2704 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2705 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2706 constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2707 operator()(_Iter1 __first1, _Sent1 __last1,
2708 _Iter2 __first2, _Sent2 __last2, _Out __result,
2710 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2712 while (__first1 != __last1 && __first2 != __last2)
2723 *__result = *__first1;
2734 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2735 typename _Comp = ranges::less,
2736 typename _Proj1 = identity,
typename _Proj2 = identity>
2737 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2738 _Comp, _Proj1, _Proj2>
2739 constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
2740 borrowed_iterator_t<_Range2>, _Out>
2741 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2743 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2745 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2746 ranges::begin(__r2), ranges::end(__r2),
2752 inline constexpr __set_intersection_fn set_intersection{};
2754 template<
typename _Iter,
typename _Out>
2755 using set_difference_result = in_out_result<_Iter, _Out>;
2757 struct __set_difference_fn
2759 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2760 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2761 weakly_incrementable _Out,
typename _Comp = ranges::less,
2762 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2763 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2764 constexpr set_difference_result<_Iter1, _Out>
2765 operator()(_Iter1 __first1, _Sent1 __last1,
2766 _Iter2 __first2, _Sent2 __last2, _Out __result,
2768 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2770 while (__first1 != __last1 && __first2 != __last2)
2775 *__result = *__first1;
2792 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2793 typename _Comp = ranges::less,
2794 typename _Proj1 = identity,
typename _Proj2 = identity>
2795 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2796 _Comp, _Proj1, _Proj2>
2797 constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
2798 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2800 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2802 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2803 ranges::begin(__r2), ranges::end(__r2),
2809 inline constexpr __set_difference_fn set_difference{};
2811 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2812 using set_symmetric_difference_result
2813 = in_in_out_result<_Iter1, _Iter2, _Out>;
2815 struct __set_symmetric_difference_fn
2817 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2818 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2819 weakly_incrementable _Out,
typename _Comp = ranges::less,
2820 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2821 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2822 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
2823 operator()(_Iter1 __first1, _Sent1 __last1,
2824 _Iter2 __first2, _Sent2 __last2,
2825 _Out __result, _Comp __comp = {},
2826 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2828 while (__first1 != __last1 && __first2 != __last2)
2833 *__result = *__first1;
2841 *__result = *__first2;
2858 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2859 typename _Comp = ranges::less,
2860 typename _Proj1 = identity,
typename _Proj2 = identity>
2861 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2862 _Comp, _Proj1, _Proj2>
2863 constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
2864 borrowed_iterator_t<_Range2>,
2866 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2868 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2870 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2871 ranges::begin(__r2), ranges::end(__r2),
2877 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
2883 template<
typename _Tp,
typename _Proj = identity,
2884 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2885 _Comp = ranges::less>
2886 constexpr const _Tp&
2887 operator()(
const _Tp& __a,
const _Tp& __b,
2888 _Comp __comp = {}, _Proj __proj = {})
const
2898 template<input_range _Range,
typename _Proj = identity,
2899 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2900 _Comp = ranges::less>
2901 requires indirectly_copyable_storable<iterator_t<_Range>,
2902 range_value_t<_Range>*>
2903 constexpr range_value_t<_Range>
2904 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2906 auto __first = ranges::begin(__r);
2907 auto __last = ranges::end(__r);
2908 __glibcxx_assert(__first != __last);
2909 auto __result = *__first;
2910 while (++__first != __last)
2912 auto&& __tmp = *__first;
2921 template<copyable _Tp,
typename _Proj = identity,
2922 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2923 _Comp = ranges::less>
2925 operator()(initializer_list<_Tp> __r,
2926 _Comp __comp = {}, _Proj __proj = {})
const
2928 return (*
this)(ranges::subrange(__r),
2933 inline constexpr __max_fn max{};
2937 template<
typename _Tp,
typename _Proj = identity,
2938 indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
2940 constexpr const _Tp&
2941 operator()(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi,
2942 _Comp __comp = {}, _Proj __proj = {})
const
2961 inline constexpr __clamp_fn clamp{};
2963 template<
typename _Tp>
2964 struct min_max_result
2966 [[no_unique_address]] _Tp min;
2967 [[no_unique_address]] _Tp max;
2969 template<
typename _Tp2>
2970 requires convertible_to<const _Tp&, _Tp2>
2972 operator min_max_result<_Tp2>() const &
2973 {
return {min, max}; }
2975 template<
typename _Tp2>
2976 requires convertible_to<_Tp, _Tp2>
2978 operator min_max_result<_Tp2>() &&
2982 template<
typename _Tp>
2983 using minmax_result = min_max_result<_Tp>;
2987 template<
typename _Tp,
typename _Proj = identity,
2988 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2989 _Comp = ranges::less>
2990 constexpr minmax_result<const _Tp&>
2991 operator()(
const _Tp& __a,
const _Tp& __b,
2992 _Comp __comp = {}, _Proj __proj = {})
const
3002 template<input_range _Range,
typename _Proj = identity,
3003 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3004 _Comp = ranges::less>
3005 requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
3006 constexpr minmax_result<range_value_t<_Range>>
3007 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3009 auto __first = ranges::begin(__r);
3010 auto __last = ranges::end(__r);
3011 __glibcxx_assert(__first != __last);
3012 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3013 minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};
3014 if (++__first == __last)
3020 auto&& __val = *__first;
3021 if (__comp_proj(__val, __result.min))
3026 while (++__first != __last)
3031 range_value_t<_Range> __val1 = *__first;
3032 if (++__first == __last)
3037 if (__comp_proj(__val1, __result.min))
3039 else if (!__comp_proj(__val1, __result.max))
3043 auto&& __val2 = *__first;
3044 if (!__comp_proj(__val2, __val1))
3046 if (__comp_proj(__val1, __result.min))
3048 if (!__comp_proj(__val2, __result.max))
3053 if (__comp_proj(__val2, __result.min))
3055 if (!__comp_proj(__val1, __result.max))
3062 template<copyable _Tp,
typename _Proj = identity,
3063 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3064 _Comp = ranges::less>
3065 constexpr minmax_result<_Tp>
3066 operator()(initializer_list<_Tp> __r,
3067 _Comp __comp = {}, _Proj __proj = {})
const
3069 return (*
this)(ranges::subrange(__r),
3074 inline constexpr __minmax_fn minmax{};
3076 struct __min_element_fn
3078 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3079 typename _Proj =
identity,
3080 indirect_strict_weak_order<projected<_Iter, _Proj>>
3081 _Comp = ranges::less>
3083 operator()(_Iter __first, _Sent __last,
3084 _Comp __comp = {}, _Proj __proj = {})
const
3086 if (__first == __last)
3090 while (++__i != __last)
3100 template<forward_range _Range,
typename _Proj = identity,
3101 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3102 _Comp = ranges::less>
3103 constexpr borrowed_iterator_t<_Range>
3104 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3106 return (*
this)(ranges::begin(__r), ranges::end(__r),
3111 inline constexpr __min_element_fn min_element{};
3113 struct __max_element_fn
3115 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3116 typename _Proj =
identity,
3117 indirect_strict_weak_order<projected<_Iter, _Proj>>
3118 _Comp = ranges::less>
3120 operator()(_Iter __first, _Sent __last,
3121 _Comp __comp = {}, _Proj __proj = {})
const
3123 if (__first == __last)
3127 while (++__i != __last)
3137 template<forward_range _Range,
typename _Proj = identity,
3138 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3139 _Comp = ranges::less>
3140 constexpr borrowed_iterator_t<_Range>
3141 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3143 return (*
this)(ranges::begin(__r), ranges::end(__r),
3148 inline constexpr __max_element_fn max_element{};
3150 template<
typename _Iter>
3151 using minmax_element_result = min_max_result<_Iter>;
3153 struct __minmax_element_fn
3155 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3156 typename _Proj =
identity,
3157 indirect_strict_weak_order<projected<_Iter, _Proj>>
3158 _Comp = ranges::less>
3159 constexpr minmax_element_result<_Iter>
3160 operator()(_Iter __first, _Sent __last,
3161 _Comp __comp = {}, _Proj __proj = {})
const
3163 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3164 minmax_element_result<_Iter> __result = {__first, __first};
3165 if (__first == __last || ++__first == __last)
3171 if (__comp_proj(*__first, *__result.min))
3172 __result.min = __first;
3174 __result.max = __first;
3176 while (++__first != __last)
3181 auto __prev = __first;
3182 if (++__first == __last)
3187 if (__comp_proj(*__prev, *__result.min))
3188 __result.min = __prev;
3189 else if (!__comp_proj(*__prev, *__result.max))
3190 __result.max = __prev;
3193 if (!__comp_proj(*__first, *__prev))
3195 if (__comp_proj(*__prev, *__result.min))
3196 __result.min = __prev;
3197 if (!__comp_proj(*__first, *__result.max))
3198 __result.max = __first;
3202 if (__comp_proj(*__first, *__result.min))
3203 __result.min = __first;
3204 if (!__comp_proj(*__prev, *__result.max))
3205 __result.max = __prev;
3211 template<forward_range _Range,
typename _Proj = identity,
3212 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3213 _Comp = ranges::less>
3214 constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3215 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3217 return (*
this)(ranges::begin(__r), ranges::end(__r),
3222 inline constexpr __minmax_element_fn minmax_element{};
3224 struct __lexicographical_compare_fn
3226 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3227 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3228 typename _Proj1 =
identity,
typename _Proj2 =
identity,
3229 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3230 projected<_Iter2, _Proj2>>
3231 _Comp = ranges::less>
3233 operator()(_Iter1 __first1, _Sent1 __last1,
3234 _Iter2 __first2, _Sent2 __last2,
3236 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3238 if constexpr (__detail::__is_normal_iterator<_Iter1>
3239 && same_as<_Iter1, _Sent1>)
3240 return (*
this)(__first1.base(), __last1.base(),
3244 else if constexpr (__detail::__is_normal_iterator<_Iter2>
3245 && same_as<_Iter2, _Sent2>)
3247 __first2.base(), __last2.base(),
3252 constexpr bool __sized_iters
3253 = (sized_sentinel_for<_Sent1, _Iter1>
3254 && sized_sentinel_for<_Sent2, _Iter2>);
3255 if constexpr (__sized_iters)
3257 using _ValueType1 = iter_value_t<_Iter1>;
3258 using _ValueType2 = iter_value_t<_Iter2>;
3261 constexpr bool __use_memcmp
3262 = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3263 && __ptr_to_nonvolatile<_Iter1>
3264 && __ptr_to_nonvolatile<_Iter2>
3265 && (is_same_v<_Comp, ranges::less>
3266 || is_same_v<_Comp, ranges::greater>)
3267 && is_same_v<_Proj1, identity>
3268 && is_same_v<_Proj2, identity>);
3269 if constexpr (__use_memcmp)
3271 const auto __d1 = __last1 - __first1;
3272 const auto __d2 = __last2 - __first2;
3274 if (
const auto __len =
std::min(__d1, __d2))
3277 = std::__memcmp(__first1, __first2, __len);
3278 if constexpr (is_same_v<_Comp, ranges::less>)
3285 else if constexpr (is_same_v<_Comp, ranges::greater>)
3297 for (; __first1 != __last1 && __first2 != __last2;
3298 ++__first1, (void) ++__first2)
3309 return __first1 == __last1 && __first2 != __last2;
3313 template<input_range _Range1, input_range _Range2,
3314 typename _Proj1 = identity,
typename _Proj2 = identity,
3315 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3316 projected<iterator_t<_Range2>, _Proj2>>
3317 _Comp = ranges::less>
3319 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3320 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3322 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
3323 ranges::begin(__r2), ranges::end(__r2),
3329 template<
typename _Iter,
typename _Ref = iter_reference_t<_Iter>>
3330 static constexpr bool __ptr_to_nonvolatile
3331 = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3334 inline constexpr __lexicographical_compare_fn lexicographical_compare;
3336 template<
typename _Iter>
3337 struct in_found_result
3339 [[no_unique_address]] _Iter in;
3342 template<
typename _Iter2>
3343 requires convertible_to<const _Iter&, _Iter2>
3345 operator in_found_result<_Iter2>() const &
3346 {
return {in, found}; }
3348 template<
typename _Iter2>
3349 requires convertible_to<_Iter, _Iter2>
3351 operator in_found_result<_Iter2>() &&
3355 template<
typename _Iter>
3356 using next_permutation_result = in_found_result<_Iter>;
3358 struct __next_permutation_fn
3360 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3361 typename _Comp = ranges::less,
typename _Proj =
identity>
3362 requires sortable<_Iter, _Comp, _Proj>
3363 constexpr next_permutation_result<_Iter>
3364 operator()(_Iter __first, _Sent __last,
3365 _Comp __comp = {}, _Proj __proj = {})
const
3367 if (__first == __last)
3375 auto __lasti = ranges::next(__first, __last);
3392 ranges::iter_swap(__i, __j);
3393 ranges::reverse(__ii, __last);
3398 ranges::reverse(__first, __last);
3404 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3405 typename _Proj = identity>
3406 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3407 constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3408 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3410 return (*
this)(ranges::begin(__r), ranges::end(__r),
3415 inline constexpr __next_permutation_fn next_permutation{};
3417 template<
typename _Iter>
3418 using prev_permutation_result = in_found_result<_Iter>;
3420 struct __prev_permutation_fn
3422 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3423 typename _Comp = ranges::less,
typename _Proj =
identity>
3424 requires sortable<_Iter, _Comp, _Proj>
3425 constexpr prev_permutation_result<_Iter>
3426 operator()(_Iter __first, _Sent __last,
3427 _Comp __comp = {}, _Proj __proj = {})
const
3429 if (__first == __last)
3437 auto __lasti = ranges::next(__first, __last);
3454 ranges::iter_swap(__i, __j);
3455 ranges::reverse(__ii, __last);
3460 ranges::reverse(__first, __last);
3466 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3467 typename _Proj = identity>
3468 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3469 constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3470 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3472 return (*
this)(ranges::begin(__r), ranges::end(__r),
3477 inline constexpr __prev_permutation_fn prev_permutation{};
3479#if __glibcxx_ranges_contains >= 202207L
3480 struct __contains_fn
3482 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3483 typename _Tp,
typename _Proj =
identity>
3484 requires indirect_binary_predicate<ranges::equal_to,
3485 projected<_Iter, _Proj>,
const _Tp*>
3487 operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
const
3488 {
return ranges::find(
std::move(__first), __last, __value,
std::move(__proj)) != __last; }
3490 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
3491 requires indirect_binary_predicate<ranges::equal_to,
3492 projected<iterator_t<_Range>, _Proj>,
const _Tp*>
3494 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
3495 {
return (*
this)(ranges::begin(__r), ranges::end(__r), __value,
std::move(__proj)); }
3498 inline constexpr __contains_fn contains{};
3500 struct __contains_subrange_fn
3502 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3503 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3504 typename _Pred = ranges::equal_to,
3505 typename _Proj1 =
identity,
typename _Proj2 =
identity>
3506 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
3508 operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
3509 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3511 return __first2 == __last2
3512 || !ranges::search(__first1, __last1, __first2, __last2,
3516 template<forward_range _Range1, forward_range _Range2,
3517 typename _Pred = ranges::equal_to,
3518 typename _Proj1 = identity,
typename _Proj2 = identity>
3519 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
3520 _Pred, _Proj1, _Proj2>
3522 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
3523 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3525 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
3526 ranges::begin(__r2), ranges::end(__r2),
3531 inline constexpr __contains_subrange_fn contains_subrange{};
3535#if __glibcxx_ranges_iota >= 202202L
3537 template<
typename _Out,
typename _Tp>
3538 struct out_value_result
3540 [[no_unique_address]] _Out out;
3541 [[no_unique_address]] _Tp value;
3543 template<
typename _Out2,
typename _Tp2>
3544 requires convertible_to<const _Out&, _Out2>
3545 && convertible_to<const _Tp&, _Tp2>
3547 operator out_value_result<_Out2, _Tp2>() const &
3548 {
return {out, value}; }
3550 template<
typename _Out2,
typename _Tp2>
3551 requires convertible_to<_Out, _Out2>
3552 && convertible_to<_Tp, _Tp2>
3554 operator out_value_result<_Out2, _Tp2>() &&
3558 template<
typename _Out,
typename _Tp>
3559 using iota_result = out_value_result<_Out, _Tp>;
3563 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp>
3564 requires indirectly_writable<_Out, const _Tp&>
3565 constexpr iota_result<_Out, _Tp>
3566 operator()(_Out __first, _Sent __last, _Tp __value)
const
3568 while (__first != __last)
3570 *__first =
static_cast<const _Tp&
>(__value);
3577 template<weakly_incrementable _Tp, output_range<const _Tp&> _Range>
3578 constexpr iota_result<borrowed_iterator_t<_Range>, _Tp>
3579 operator()(_Range&& __r, _Tp __value)
const
3580 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__value)); }
3583 inline constexpr __iota_fn
iota{};
3587#if __glibcxx_ranges_find_last >= 202207L
3589 struct __find_last_fn
3591 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
typename _Proj =
identity>
3592 requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
const _Tp*>
3593 constexpr subrange<_Iter>
3594 operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
const
3596 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3598 _Iter __found = ranges::find(reverse_iterator<_Iter>{__last},
3599 reverse_iterator<_Iter>{__first},
3601 if (__found == __first)
3602 return {__last, __last};
3604 return {ranges::prev(__found), __last};
3608 _Iter __found = ranges::find(__first, __last, __value, __proj);
3609 if (__found == __last)
3610 return {__found, __found};
3614 __first = ranges::find(ranges::next(__first), __last, __value, __proj);
3615 if (__first == __last)
3616 return {__found, __first};
3622 template<forward_range _Range,
typename _Tp,
typename _Proj =
identity>
3623 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>,
const _Tp*>
3624 constexpr borrowed_subrange_t<_Range>
3625 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
3626 {
return (*
this)(ranges::begin(__r), ranges::end(__r), __value,
std::move(__proj)); }
3629 inline constexpr __find_last_fn find_last{};
3631 struct __find_last_if_fn
3633 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Proj =
identity,
3634 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3635 constexpr subrange<_Iter>
3636 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
const
3638 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3640 _Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last},
3641 reverse_iterator<_Iter>{__first},
3643 if (__found == __first)
3644 return {__last, __last};
3646 return {ranges::prev(__found), __last};
3650 _Iter __found = ranges::find_if(__first, __last, __pred, __proj);
3651 if (__found == __last)
3652 return {__found, __found};
3656 __first = ranges::find_if(ranges::next(__first), __last, __pred, __proj);
3657 if (__first == __last)
3658 return {__found, __first};
3664 template<forward_range _Range,
typename _Proj = identity,
3665 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3666 constexpr borrowed_subrange_t<_Range>
3667 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
3668 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred),
std::move(__proj)); }
3671 inline constexpr __find_last_if_fn find_last_if{};
3673 struct __find_last_if_not_fn
3675 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Proj =
identity,
3676 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3677 constexpr subrange<_Iter>
3678 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
const
3680 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3682 _Iter __found = ranges::find_if_not(reverse_iterator<_Iter>{__last},
3683 reverse_iterator<_Iter>{__first},
3685 if (__found == __first)
3686 return {__last, __last};
3688 return {ranges::prev(__found), __last};
3692 _Iter __found = ranges::find_if_not(__first, __last, __pred, __proj);
3693 if (__found == __last)
3694 return {__found, __found};
3698 __first = ranges::find_if_not(ranges::next(__first), __last, __pred, __proj);
3699 if (__first == __last)
3700 return {__found, __first};
3706 template<forward_range _Range,
typename _Proj = identity,
3707 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3708 constexpr borrowed_subrange_t<_Range>
3709 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
3710 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred),
std::move(__proj)); }
3713 inline constexpr __find_last_if_not_fn find_last_if_not{};
3717#if __glibcxx_ranges_fold >= 202207L
3719 template<
typename _Iter,
typename _Tp>
3720 struct in_value_result
3722 [[no_unique_address]] _Iter in;
3723 [[no_unique_address]] _Tp value;
3725 template<
typename _Iter2,
typename _Tp2>
3726 requires convertible_to<const _Iter&, _Iter2>
3727 && convertible_to<const _Tp&, _Tp2>
3729 operator in_value_result<_Iter2, _Tp2>() const &
3730 {
return {in, value}; }
3732 template<
typename _Iter2,
typename _Tp2>
3733 requires convertible_to<_Iter, _Iter2>
3734 && convertible_to<_Tp, _Tp2>
3736 operator in_value_result<_Iter2, _Tp2>() &&
3742 template<
typename _Fp>
3748 template<
typename _Tp,
typename _Up>
3749 requires invocable<_Fp&, _Up, _Tp>
3750 invoke_result_t<_Fp&, _Up, _Tp>
3751 operator()(_Tp&&, _Up&&);
3754 template<
typename _Fp,
typename _Tp,
typename _Iter,
typename _Up>
3755 concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up>
3756 && convertible_to<_Tp, _Up>
3757 && invocable<_Fp&, _Up, iter_reference_t<_Iter>>
3758 && assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>;
3760 template<
typename _Fp,
typename _Tp,
typename _Iter>
3761 concept __indirectly_binary_left_foldable = copy_constructible<_Fp>
3762 && indirectly_readable<_Iter>
3763 && invocable<_Fp&, _Tp, iter_reference_t<_Iter>>
3764 && convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>,
3765 decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>
3766 && __indirectly_binary_left_foldable_impl
3767 <_Fp, _Tp, _Iter, decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>;
3769 template <
typename _Fp,
typename _Tp,
typename _Iter>
3770 concept __indirectly_binary_right_foldable
3771 = __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>;
3774 template<
typename _Iter,
typename _Tp>
3775 using fold_left_with_iter_result = in_value_result<_Iter, _Tp>;
3777 struct __fold_left_with_iter_fn
3779 template<
typename _Ret_iter,
3780 typename _Iter,
typename _Sent,
typename _Tp,
typename _Fp>
3781 static constexpr auto
3782 _S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
3784 using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>;
3785 using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>;
3787 if (__first == __last)
3791 for (++__first; __first != __last; ++__first)
3796 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
3797 __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3799 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3801 using _Ret_iter = _Iter;
3802 return _S_impl<_Ret_iter>(
std::move(__first), __last,
3806 template<input_range _Range,
typename _Tp,
3807 __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3809 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3811 using _Ret_iter = borrowed_iterator_t<_Range>;
3812 return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
3817 inline constexpr __fold_left_with_iter_fn fold_left_with_iter{};
3819 struct __fold_left_fn
3821 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
3822 __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3824 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3826 return ranges::fold_left_with_iter(
std::move(__first), __last,
3830 template<input_range _Range,
typename _Tp,
3831 __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3833 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3834 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__init),
std::move(__f)); }
3837 inline constexpr __fold_left_fn fold_left{};
3839 template<
typename _Iter,
typename _Tp>
3840 using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>;
3842 struct __fold_left_first_with_iter_fn
3844 template<
typename _Ret_iter,
typename _Iter,
typename _Sent,
typename _Fp>
3845 static constexpr auto
3846 _S_impl(_Iter __first, _Sent __last, _Fp __f)
3848 using _Up =
decltype(ranges::fold_left(
std::move(__first), __last,
3849 iter_value_t<_Iter>(*__first), __f));
3850 using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>;
3852 if (__first == __last)
3853 return _Ret{
std::move(__first), optional<_Up>()};
3855 optional<_Up> __init(in_place, *__first);
3856 for (++__first; __first != __last; ++__first)
3861 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3862 __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3863 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3865 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3867 using _Ret_iter = _Iter;
3871 template<input_range _Range,
3872 __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3873 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3875 operator()(_Range&& __r, _Fp __f)
const
3877 using _Ret_iter = borrowed_iterator_t<_Range>;
3878 return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
std::move(__f));
3882 inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{};
3884 struct __fold_left_first_fn
3886 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3887 __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3888 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3890 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3892 return ranges::fold_left_first_with_iter(
std::move(__first), __last,
3896 template<input_range _Range,
3897 __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3898 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3900 operator()(_Range&& __r, _Fp __f)
const
3901 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__f)); }
3904 inline constexpr __fold_left_first_fn fold_left_first{};
3906 struct __fold_right_fn
3908 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
3909 __detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp>
3911 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3913 using _Up = decay_t<invoke_result_t<_Fp&, iter_reference_t<_Iter>, _Tp>>;
3915 if (__first == __last)
3918 _Iter __tail = ranges::next(__first, __last);
3920 while (__first != __tail)
3925 template<bidirectional_range _Range,
typename _Tp,
3926 __detail::__indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Fp>
3928 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3929 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__init),
std::move(__f)); }
3932 inline constexpr __fold_right_fn fold_right{};
3934 struct __fold_right_last_fn
3936 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3937 __detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3938 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3940 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3942 using _Up =
decltype(ranges::fold_right(__first, __last,
3943 iter_value_t<_Iter>(*__first), __f));
3945 if (__first == __last)
3946 return optional<_Up>();
3948 _Iter __tail = ranges::prev(ranges::next(__first,
std::move(__last)));
3949 return optional<_Up>(in_place,
3950 ranges::fold_right(
std::move(__first), __tail,
3951 iter_value_t<_Iter>(*__tail),
3955 template<bidirectional_range _Range,
3956 __detail::__indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3957 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3959 operator()(_Range&& __r, _Fp __f)
const
3960 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__f)); }
3963 inline constexpr __fold_right_last_fn fold_right_last{};
3967 template<
typename _ForwardIterator>
3968 constexpr _ForwardIterator
3969 shift_left(_ForwardIterator __first, _ForwardIterator __last,
3970 typename iterator_traits<_ForwardIterator>::difference_type __n)
3972 __glibcxx_assert(__n >= 0);
3976 auto __mid = ranges::next(__first, __n, __last);
3977 if (__mid == __last)
3982 template<
typename _ForwardIterator>
3983 constexpr _ForwardIterator
3984 shift_right(_ForwardIterator __first, _ForwardIterator __last,
3985 typename iterator_traits<_ForwardIterator>::difference_type __n)
3987 __glibcxx_assert(__n >= 0);
3992 =
typename iterator_traits<_ForwardIterator>::iterator_category;
3993 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
3995 auto __mid = ranges::next(__last, -__n, __first);
3996 if (__mid == __first)
4004 auto __result = ranges::next(__first, __n, __last);
4005 if (__result == __last)
4008 auto __dest_head = __first, __dest_tail = __result;
4009 while (__dest_head != __result)
4011 if (__dest_tail == __last)
4035 auto __cursor = __first;
4036 while (__cursor != __result)
4038 if (__dest_tail == __last)
4043 __dest_head =
std::move(__cursor, __result,
4049 std::iter_swap(__cursor, __dest_head);
4058_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.
constexpr void iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value)
Create a range of sequentially increasing values.
ISO C++ entities toplevel namespace is std.