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)
564 auto&& __scan_deref = *__scan;
567 auto __comp_scan = [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
572 if (__scan != ranges::find_if(__first1, __scan,
573 __comp_scan, __proj1))
576 auto __matches = ranges::count_if(__first2, __last2,
577 __comp_scan, __proj2);
579 || ranges::count_if(__scan, __last1,
580 __comp_scan, __proj1) != __matches)
586 template<forward_range _Range1, forward_range _Range2,
587 typename _Proj1 = identity,
typename _Proj2 = identity,
588 indirect_equivalence_relation<
589 projected<iterator_t<_Range1>, _Proj1>,
590 projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
592 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
593 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
597 if constexpr (sized_range<_Range1>)
598 if constexpr (sized_range<_Range2>)
599 if (ranges::distance(__r1) != ranges::distance(__r2))
602 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
603 ranges::begin(__r2), ranges::end(__r2),
609 inline constexpr __is_permutation_fn is_permutation{};
611 template<
typename _Iter,
typename _Out>
612 using copy_if_result = in_out_result<_Iter, _Out>;
616 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
617 weakly_incrementable _Out,
typename _Proj =
identity,
618 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
619 requires indirectly_copyable<_Iter, _Out>
620 constexpr copy_if_result<_Iter, _Out>
621 operator()(_Iter __first, _Sent __last, _Out __result,
622 _Pred __pred, _Proj __proj = {})
const
624 for (; __first != __last; ++__first)
627 *__result = *__first;
633 template<input_range _Range, weakly_incrementable _Out,
634 typename _Proj = identity,
635 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
637 requires indirectly_copyable<iterator_t<_Range>, _Out>
638 constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
639 operator()(_Range&& __r, _Out __result,
640 _Pred __pred, _Proj __proj = {})
const
642 return (*
this)(ranges::begin(__r), ranges::end(__r),
648 inline constexpr __copy_if_fn copy_if{};
650 template<
typename _Iter1,
typename _Iter2>
651 using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
653 struct __swap_ranges_fn
655 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
656 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
657 requires indirectly_swappable<_Iter1, _Iter2>
658 constexpr swap_ranges_result<_Iter1, _Iter2>
659 operator()(_Iter1 __first1, _Sent1 __last1,
660 _Iter2 __first2, _Sent2 __last2)
const
662 for (; __first1 != __last1 && __first2 != __last2;
663 ++__first1, (void)++__first2)
664 ranges::iter_swap(__first1, __first2);
668 template<input_range _Range1, input_range _Range2>
669 requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
670 constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
671 borrowed_iterator_t<_Range2>>
672 operator()(_Range1&& __r1, _Range2&& __r2)
const
674 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
675 ranges::begin(__r2), ranges::end(__r2));
679 inline constexpr __swap_ranges_fn swap_ranges{};
681 template<
typename _Iter,
typename _Out>
682 using unary_transform_result = in_out_result<_Iter, _Out>;
684 template<
typename _Iter1,
typename _Iter2,
typename _Out>
685 struct in_in_out_result
687 [[no_unique_address]] _Iter1 in1;
688 [[no_unique_address]] _Iter2 in2;
689 [[no_unique_address]] _Out out;
691 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
692 requires convertible_to<const _Iter1&, _IIter1>
693 && convertible_to<const _Iter2&, _IIter2>
694 && convertible_to<const _Out&, _OOut>
696 operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
697 {
return {in1, in2, out}; }
699 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
700 requires convertible_to<_Iter1, _IIter1>
701 && convertible_to<_Iter2, _IIter2>
702 && convertible_to<_Out, _OOut>
704 operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
708 template<
typename _Iter1,
typename _Iter2,
typename _Out>
709 using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
711 struct __transform_fn
713 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
714 weakly_incrementable _Out,
715 copy_constructible _Fp,
typename _Proj =
identity>
716 requires indirectly_writable<_Out,
717 indirect_result_t<_Fp&,
718 projected<_Iter, _Proj>>>
719 constexpr unary_transform_result<_Iter, _Out>
720 operator()(_Iter __first1, _Sent __last1, _Out __result,
721 _Fp __op, _Proj __proj = {})
const
723 for (; __first1 != __last1; ++__first1, (void)++__result)
728 template<input_range _Range, weakly_incrementable _Out,
729 copy_constructible _Fp,
typename _Proj = identity>
730 requires indirectly_writable<_Out,
731 indirect_result_t<_Fp&,
732 projected<iterator_t<_Range>, _Proj>>>
733 constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
734 operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {})
const
736 return (*
this)(ranges::begin(__r), ranges::end(__r),
741 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
742 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
743 weakly_incrementable _Out, copy_constructible _Fp,
744 typename _Proj1 =
identity,
typename _Proj2 =
identity>
745 requires indirectly_writable<_Out,
746 indirect_result_t<_Fp&,
747 projected<_Iter1, _Proj1>,
748 projected<_Iter2, _Proj2>>>
749 constexpr binary_transform_result<_Iter1, _Iter2, _Out>
750 operator()(_Iter1 __first1, _Sent1 __last1,
751 _Iter2 __first2, _Sent2 __last2,
752 _Out __result, _Fp __binary_op,
753 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
755 for (; __first1 != __last1 && __first2 != __last2;
756 ++__first1, (void)++__first2, ++__result)
763 template<input_range _Range1, input_range _Range2,
764 weakly_incrementable _Out, copy_constructible _Fp,
765 typename _Proj1 = identity,
typename _Proj2 = identity>
766 requires indirectly_writable<_Out,
767 indirect_result_t<_Fp&,
768 projected<iterator_t<_Range1>, _Proj1>,
769 projected<iterator_t<_Range2>, _Proj2>>>
770 constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
771 borrowed_iterator_t<_Range2>, _Out>
772 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
773 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
775 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
776 ranges::begin(__r2), ranges::end(__r2),
782 inline constexpr __transform_fn transform{};
786 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
787 typename _Tp1,
typename _Tp2,
typename _Proj =
identity>
788 requires indirectly_writable<_Iter, const _Tp2&>
789 && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
792 operator()(_Iter __first, _Sent __last,
793 const _Tp1& __old_value,
const _Tp2& __new_value,
794 _Proj __proj = {})
const
796 for (; __first != __last; ++__first)
798 *__first = __new_value;
802 template<input_range _Range,
803 typename _Tp1,
typename _Tp2,
typename _Proj = identity>
804 requires indirectly_writable<iterator_t<_Range>,
const _Tp2&>
805 && indirect_binary_predicate<ranges::equal_to,
806 projected<iterator_t<_Range>, _Proj>,
808 constexpr borrowed_iterator_t<_Range>
809 operator()(_Range&& __r,
810 const _Tp1& __old_value,
const _Tp2& __new_value,
811 _Proj __proj = {})
const
813 return (*
this)(ranges::begin(__r), ranges::end(__r),
814 __old_value, __new_value,
std::move(__proj));
818 inline constexpr __replace_fn replace{};
820 struct __replace_if_fn
822 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
823 typename _Tp,
typename _Proj =
identity,
824 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
825 requires indirectly_writable<_Iter, const _Tp&>
827 operator()(_Iter __first, _Sent __last,
828 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
830 for (; __first != __last; ++__first)
832 *__first = __new_value;
836 template<input_range _Range,
typename _Tp,
typename _Proj = identity,
837 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
839 requires indirectly_writable<iterator_t<_Range>,
const _Tp&>
840 constexpr borrowed_iterator_t<_Range>
841 operator()(_Range&& __r,
842 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
844 return (*
this)(ranges::begin(__r), ranges::end(__r),
849 inline constexpr __replace_if_fn replace_if{};
851 template<
typename _Iter,
typename _Out>
852 using replace_copy_result = in_out_result<_Iter, _Out>;
854 struct __replace_copy_fn
856 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
857 typename _Tp1,
typename _Tp2, output_iterator<const _Tp2&> _Out,
858 typename _Proj =
identity>
859 requires indirectly_copyable<_Iter, _Out>
860 && indirect_binary_predicate<ranges::equal_to,
861 projected<_Iter, _Proj>,
const _Tp1*>
862 constexpr replace_copy_result<_Iter, _Out>
863 operator()(_Iter __first, _Sent __last, _Out __result,
864 const _Tp1& __old_value,
const _Tp2& __new_value,
865 _Proj __proj = {})
const
867 for (; __first != __last; ++__first, (void)++__result)
869 *__result = __new_value;
871 *__result = *__first;
875 template<input_range _Range,
typename _Tp1,
typename _Tp2,
876 output_iterator<const _Tp2&> _Out,
typename _Proj = identity>
877 requires indirectly_copyable<iterator_t<_Range>, _Out>
878 && indirect_binary_predicate<ranges::equal_to,
879 projected<iterator_t<_Range>, _Proj>,
881 constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
882 operator()(_Range&& __r, _Out __result,
883 const _Tp1& __old_value,
const _Tp2& __new_value,
884 _Proj __proj = {})
const
886 return (*
this)(ranges::begin(__r), ranges::end(__r),
892 inline constexpr __replace_copy_fn replace_copy{};
894 template<
typename _Iter,
typename _Out>
895 using replace_copy_if_result = in_out_result<_Iter, _Out>;
897 struct __replace_copy_if_fn
899 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
900 typename _Tp, output_iterator<const _Tp&> _Out,
901 typename _Proj =
identity,
902 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
903 requires indirectly_copyable<_Iter, _Out>
904 constexpr replace_copy_if_result<_Iter, _Out>
905 operator()(_Iter __first, _Sent __last, _Out __result,
906 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
908 for (; __first != __last; ++__first, (void)++__result)
910 *__result = __new_value;
912 *__result = *__first;
916 template<input_range _Range,
917 typename _Tp, output_iterator<const _Tp&> _Out,
918 typename _Proj = identity,
919 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
921 requires indirectly_copyable<iterator_t<_Range>, _Out>
922 constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
923 operator()(_Range&& __r, _Out __result,
924 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
926 return (*
this)(ranges::begin(__r), ranges::end(__r),
932 inline constexpr __replace_copy_if_fn replace_copy_if{};
934 struct __generate_n_fn
936 template<input_or_output_iterator _Out, copy_constructible _Fp>
937 requires invocable<_Fp&>
938 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
940 operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen)
const
942 for (; __n > 0; --__n, (void)++__first)
948 inline constexpr __generate_n_fn generate_n{};
952 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
953 copy_constructible _Fp>
954 requires invocable<_Fp&>
955 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
957 operator()(_Out __first, _Sent __last, _Fp __gen)
const
959 for (; __first != __last; ++__first)
964 template<
typename _Range, copy_constructible _Fp>
965 requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
966 constexpr borrowed_iterator_t<_Range>
967 operator()(_Range&& __r, _Fp __gen)
const
969 return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__gen));
973 inline constexpr __generate_fn generate{};
975 struct __remove_if_fn
977 template<permutable _Iter, sentinel_for<_Iter> _Sent,
978 typename _Proj =
identity,
979 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
980 constexpr subrange<_Iter>
981 operator()(_Iter __first, _Sent __last,
982 _Pred __pred, _Proj __proj = {})
const
984 __first = ranges::find_if(__first, __last, __pred, __proj);
985 if (__first == __last)
986 return {__first, __first};
988 auto __result = __first;
990 for (; __first != __last; ++__first)
997 return {__result, __first};
1000 template<forward_range _Range,
typename _Proj = identity,
1001 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1003 requires permutable<iterator_t<_Range>>
1004 constexpr borrowed_subrange_t<_Range>
1005 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
1007 return (*
this)(ranges::begin(__r), ranges::end(__r),
1012 inline constexpr __remove_if_fn remove_if{};
1016 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1017 typename _Tp,
typename _Proj =
identity>
1018 requires indirect_binary_predicate<ranges::equal_to,
1019 projected<_Iter, _Proj>,
1021 constexpr subrange<_Iter>
1022 operator()(_Iter __first, _Sent __last,
1023 const _Tp& __value, _Proj __proj = {})
const
1025 auto __pred = [&] (
auto&& __arg) ->
bool {
1028 return ranges::remove_if(__first, __last,
1032 template<forward_range _Range,
typename _Tp,
typename _Proj =
identity>
1033 requires permutable<iterator_t<_Range>>
1034 && indirect_binary_predicate<ranges::equal_to,
1035 projected<iterator_t<_Range>, _Proj>,
1037 constexpr borrowed_subrange_t<_Range>
1038 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
1040 return (*
this)(ranges::begin(__r), ranges::end(__r),
1045 inline constexpr __remove_fn remove{};
1047 template<
typename _Iter,
typename _Out>
1048 using remove_copy_if_result = in_out_result<_Iter, _Out>;
1050 struct __remove_copy_if_fn
1052 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1053 weakly_incrementable _Out,
typename _Proj =
identity,
1054 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1055 requires indirectly_copyable<_Iter, _Out>
1056 constexpr remove_copy_if_result<_Iter, _Out>
1057 operator()(_Iter __first, _Sent __last, _Out __result,
1058 _Pred __pred, _Proj __proj = {})
const
1060 for (; __first != __last; ++__first)
1063 *__result = *__first;
1069 template<input_range _Range, weakly_incrementable _Out,
1070 typename _Proj = identity,
1071 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1073 requires indirectly_copyable<iterator_t<_Range>, _Out>
1074 constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1075 operator()(_Range&& __r, _Out __result,
1076 _Pred __pred, _Proj __proj = {})
const
1078 return (*
this)(ranges::begin(__r), ranges::end(__r),
1084 inline constexpr __remove_copy_if_fn remove_copy_if{};
1086 template<
typename _Iter,
typename _Out>
1087 using remove_copy_result = in_out_result<_Iter, _Out>;
1089 struct __remove_copy_fn
1091 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1092 weakly_incrementable _Out,
typename _Tp,
typename _Proj =
identity>
1093 requires indirectly_copyable<_Iter, _Out>
1094 && indirect_binary_predicate<ranges::equal_to,
1095 projected<_Iter, _Proj>,
1097 constexpr remove_copy_result<_Iter, _Out>
1098 operator()(_Iter __first, _Sent __last, _Out __result,
1099 const _Tp& __value, _Proj __proj = {})
const
1101 for (; __first != __last; ++__first)
1104 *__result = *__first;
1110 template<input_range _Range, weakly_incrementable _Out,
1111 typename _Tp,
typename _Proj = identity>
1112 requires indirectly_copyable<iterator_t<_Range>, _Out>
1113 && indirect_binary_predicate<ranges::equal_to,
1114 projected<iterator_t<_Range>, _Proj>,
1116 constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
1117 operator()(_Range&& __r, _Out __result,
1118 const _Tp& __value, _Proj __proj = {})
const
1120 return (*
this)(ranges::begin(__r), ranges::end(__r),
1125 inline constexpr __remove_copy_fn remove_copy{};
1129 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1130 typename _Proj =
identity,
1131 indirect_equivalence_relation<
1132 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1133 constexpr subrange<_Iter>
1134 operator()(_Iter __first, _Sent __last,
1135 _Comp __comp = {}, _Proj __proj = {})
const
1137 __first = ranges::adjacent_find(__first, __last, __comp, __proj);
1138 if (__first == __last)
1139 return {__first, __first};
1141 auto __dest = __first;
1143 while (++__first != __last)
1148 return {++__dest, __first};
1151 template<forward_range _Range,
typename _Proj = identity,
1152 indirect_equivalence_relation<
1153 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1154 requires permutable<iterator_t<_Range>>
1155 constexpr borrowed_subrange_t<_Range>
1156 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1158 return (*
this)(ranges::begin(__r), ranges::end(__r),
1163 inline constexpr __unique_fn unique{};
1167 template<
typename _Out,
typename _Tp>
1168 concept __can_reread_output = input_iterator<_Out>
1169 && same_as<_Tp, iter_value_t<_Out>>;
1172 template<
typename _Iter,
typename _Out>
1173 using unique_copy_result = in_out_result<_Iter, _Out>;
1175 struct __unique_copy_fn
1177 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1178 weakly_incrementable _Out,
typename _Proj =
identity,
1179 indirect_equivalence_relation<
1180 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1181 requires indirectly_copyable<_Iter, _Out>
1182 && (forward_iterator<_Iter>
1183 || __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
1184 || indirectly_copyable_storable<_Iter, _Out>)
1185 constexpr unique_copy_result<_Iter, _Out>
1186 operator()(_Iter __first, _Sent __last, _Out __result,
1187 _Comp __comp = {}, _Proj __proj = {})
const
1189 if (__first == __last)
1193 if constexpr (forward_iterator<_Iter>)
1195 auto __next = __first;
1196 *__result = *__next;
1197 while (++__next != __last)
1203 *++__result = *__first;
1207 else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
1209 *__result = *__first;
1210 while (++__first != __last)
1214 *++__result = *__first;
1219 auto __value = *__first;
1220 *__result = __value;
1221 while (++__first != __last)
1228 *++__result = __value;
1235 template<input_range _Range,
1236 weakly_incrementable _Out,
typename _Proj = identity,
1237 indirect_equivalence_relation<
1238 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1239 requires indirectly_copyable<iterator_t<_Range>, _Out>
1240 && (forward_iterator<iterator_t<_Range>>
1241 || __detail::__can_reread_output<_Out, range_value_t<_Range>>
1242 || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1243 constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1244 operator()(_Range&& __r, _Out __result,
1245 _Comp __comp = {}, _Proj __proj = {})
const
1247 return (*
this)(ranges::begin(__r), ranges::end(__r),
1253 inline constexpr __unique_copy_fn unique_copy{};
1257 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1258 requires permutable<_Iter>
1260 operator()(_Iter __first, _Sent __last)
const
1262 auto __i = ranges::next(__first, __last);
1265 if constexpr (random_access_iterator<_Iter>)
1267 if (__first != __last)
1270 while (__first < __tail)
1272 ranges::iter_swap(__first, __tail);
1282 if (__first == __tail || __first == --__tail)
1286 ranges::iter_swap(__first, __tail);
1293 template<b
idirectional_range _Range>
1294 requires permutable<iterator_t<_Range>>
1295 constexpr borrowed_iterator_t<_Range>
1296 operator()(_Range&& __r)
const
1298 return (*
this)(ranges::begin(__r), ranges::end(__r));
1302 inline constexpr __reverse_fn reverse{};
1304 template<
typename _Iter,
typename _Out>
1305 using reverse_copy_result = in_out_result<_Iter, _Out>;
1307 struct __reverse_copy_fn
1309 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1310 weakly_incrementable _Out>
1311 requires indirectly_copyable<_Iter, _Out>
1312 constexpr reverse_copy_result<_Iter, _Out>
1313 operator()(_Iter __first, _Sent __last, _Out __result)
const
1315 auto __i = ranges::next(__first, __last);
1317 while (__first != __tail)
1320 *__result = *__tail;
1326 template<b
idirectional_range _Range, weakly_incrementable _Out>
1327 requires indirectly_copyable<iterator_t<_Range>, _Out>
1328 constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1329 operator()(_Range&& __r, _Out __result)
const
1331 return (*
this)(ranges::begin(__r), ranges::end(__r),
1336 inline constexpr __reverse_copy_fn reverse_copy{};
1340 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1341 constexpr subrange<_Iter>
1342 operator()(_Iter __first, _Iter __middle, _Sent __last)
const
1344 auto __lasti = ranges::next(__first, __last);
1345 if (__first == __middle)
1346 return {__lasti, __lasti};
1347 if (__last == __middle)
1350 if constexpr (random_access_iterator<_Iter>)
1352 auto __n = __lasti - __first;
1353 auto __k = __middle - __first;
1355 if (__k == __n - __k)
1357 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1362 auto __ret = __first + (__lasti - __middle);
1366 if (__k < __n - __k)
1370 if constexpr (__is_pod(iter_value_t<_Iter>))
1374 ranges::move(__p + 1, __p + __n, __p);
1378 auto __q = __p + __k;
1379 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1381 ranges::iter_swap(__p, __q);
1388 ranges::swap(__n, __k);
1396 if constexpr (__is_pod(iter_value_t<_Iter>))
1400 ranges::move_backward(__p, __p + __n - 1, __p + __n);
1404 auto __q = __p + __n;
1406 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1410 ranges::iter_swap(__p, __q);
1415 std::swap(__n, __k);
1419 else if constexpr (bidirectional_iterator<_Iter>)
1421 auto __tail = __lasti;
1423 ranges::reverse(__first, __middle);
1424 ranges::reverse(__middle, __tail);
1426 while (__first != __middle && __middle != __tail)
1428 ranges::iter_swap(__first, --__tail);
1432 if (__first == __middle)
1434 ranges::reverse(__middle, __tail);
1439 ranges::reverse(__first, __middle);
1445 auto __first2 = __middle;
1448 ranges::iter_swap(__first, __first2);
1451 if (__first == __middle)
1452 __middle = __first2;
1453 }
while (__first2 != __last);
1455 auto __ret = __first;
1457 __first2 = __middle;
1459 while (__first2 != __last)
1461 ranges::iter_swap(__first, __first2);
1464 if (__first == __middle)
1465 __middle = __first2;
1466 else if (__first2 == __last)
1467 __first2 = __middle;
1473 template<forward_range _Range>
1474 requires permutable<iterator_t<_Range>>
1475 constexpr borrowed_subrange_t<_Range>
1476 operator()(_Range&& __r, iterator_t<_Range> __middle)
const
1478 return (*
this)(ranges::begin(__r),
std::move(__middle),
1483 inline constexpr __rotate_fn rotate{};
1485 template<
typename _Iter,
typename _Out>
1486 using rotate_copy_result = in_out_result<_Iter, _Out>;
1488 struct __rotate_copy_fn
1490 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1491 weakly_incrementable _Out>
1492 requires indirectly_copyable<_Iter, _Out>
1493 constexpr rotate_copy_result<_Iter, _Out>
1494 operator()(_Iter __first, _Iter __middle, _Sent __last,
1495 _Out __result)
const
1497 auto __copy1 = ranges::copy(__middle,
1500 auto __copy2 = ranges::copy(
std::move(__first),
1506 template<forward_range _Range, weakly_incrementable _Out>
1507 requires indirectly_copyable<iterator_t<_Range>, _Out>
1508 constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1509 operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result)
const
1511 return (*
this)(ranges::begin(__r),
std::move(__middle),
1516 inline constexpr __rotate_copy_fn rotate_copy{};
1520 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1521 weakly_incrementable _Out,
typename _Gen>
1522 requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
1523 && indirectly_copyable<_Iter, _Out>
1524 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1526 operator()(_Iter __first, _Sent __last, _Out __out,
1527 iter_difference_t<_Iter> __n, _Gen&& __g)
const
1529 if constexpr (forward_iterator<_Iter>)
1533 auto __lasti = ranges::next(__first, __last);
1534 return _GLIBCXX_STD_A::
1540 using __distrib_type
1541 = uniform_int_distribution<iter_difference_t<_Iter>>;
1542 using __param_type =
typename __distrib_type::param_type;
1543 __distrib_type __d{};
1544 iter_difference_t<_Iter> __sample_sz = 0;
1545 while (__first != __last && __sample_sz != __n)
1547 __out[__sample_sz++] = *__first;
1550 for (
auto __pop_sz = __sample_sz; __first != __last;
1551 ++__first, (void) ++__pop_sz)
1553 const auto __k = __d(__g, __param_type{0, __pop_sz});
1555 __out[__k] = *__first;
1557 return __out + __sample_sz;
1561 template<input_range _Range, weakly_incrementable _Out,
typename _Gen>
1562 requires (forward_range<_Range> || random_access_iterator<_Out>)
1563 && indirectly_copyable<iterator_t<_Range>, _Out>
1564 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1566 operator()(_Range&& __r, _Out __out,
1567 range_difference_t<_Range> __n, _Gen&& __g)
const
1569 return (*
this)(ranges::begin(__r), ranges::end(__r),
1575 inline constexpr __sample_fn sample{};
1579 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1581 requires permutable<_Iter>
1582 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1584 operator()(_Iter __first, _Sent __last, _Gen&& __g)
const
1586 auto __lasti = ranges::next(__first, __last);
1591 template<random_access_range _Range,
typename _Gen>
1592 requires permutable<iterator_t<_Range>>
1593 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1594 borrowed_iterator_t<_Range>
1595 operator()(_Range&& __r, _Gen&& __g)
const
1597 return (*
this)(ranges::begin(__r), ranges::end(__r),
1602 inline constexpr __shuffle_fn shuffle{};
1604 struct __push_heap_fn
1606 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1607 typename _Comp = ranges::less,
typename _Proj =
identity>
1608 requires sortable<_Iter, _Comp, _Proj>
1610 operator()(_Iter __first, _Sent __last,
1611 _Comp __comp = {}, _Proj __proj = {})
const
1613 auto __lasti = ranges::next(__first, __last);
1614 std::push_heap(__first, __lasti,
1615 __detail::__make_comp_proj(__comp, __proj));
1619 template<random_access_range _Range,
1620 typename _Comp = ranges::less,
typename _Proj = identity>
1621 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1622 constexpr borrowed_iterator_t<_Range>
1623 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1625 return (*
this)(ranges::begin(__r), ranges::end(__r),
1630 inline constexpr __push_heap_fn push_heap{};
1632 struct __pop_heap_fn
1634 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1635 typename _Comp = ranges::less,
typename _Proj =
identity>
1636 requires sortable<_Iter, _Comp, _Proj>
1638 operator()(_Iter __first, _Sent __last,
1639 _Comp __comp = {}, _Proj __proj = {})
const
1641 auto __lasti = ranges::next(__first, __last);
1642 std::pop_heap(__first, __lasti,
1643 __detail::__make_comp_proj(__comp, __proj));
1647 template<random_access_range _Range,
1648 typename _Comp = ranges::less,
typename _Proj = identity>
1649 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1650 constexpr borrowed_iterator_t<_Range>
1651 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1653 return (*
this)(ranges::begin(__r), ranges::end(__r),
1658 inline constexpr __pop_heap_fn pop_heap{};
1660 struct __make_heap_fn
1662 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1663 typename _Comp = ranges::less,
typename _Proj =
identity>
1664 requires sortable<_Iter, _Comp, _Proj>
1666 operator()(_Iter __first, _Sent __last,
1667 _Comp __comp = {}, _Proj __proj = {})
const
1669 auto __lasti = ranges::next(__first, __last);
1670 std::make_heap(__first, __lasti,
1671 __detail::__make_comp_proj(__comp, __proj));
1675 template<random_access_range _Range,
1676 typename _Comp = ranges::less,
typename _Proj = identity>
1677 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1678 constexpr borrowed_iterator_t<_Range>
1679 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1681 return (*
this)(ranges::begin(__r), ranges::end(__r),
1686 inline constexpr __make_heap_fn make_heap{};
1688 struct __sort_heap_fn
1690 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1691 typename _Comp = ranges::less,
typename _Proj =
identity>
1692 requires sortable<_Iter, _Comp, _Proj>
1694 operator()(_Iter __first, _Sent __last,
1695 _Comp __comp = {}, _Proj __proj = {})
const
1697 auto __lasti = ranges::next(__first, __last);
1698 std::sort_heap(__first, __lasti,
1699 __detail::__make_comp_proj(__comp, __proj));
1703 template<random_access_range _Range,
1704 typename _Comp = ranges::less,
typename _Proj = identity>
1705 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1706 constexpr borrowed_iterator_t<_Range>
1707 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1709 return (*
this)(ranges::begin(__r), ranges::end(__r),
1714 inline constexpr __sort_heap_fn sort_heap{};
1716 struct __is_heap_until_fn
1718 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1719 typename _Proj =
identity,
1720 indirect_strict_weak_order<projected<_Iter, _Proj>>
1721 _Comp = ranges::less>
1723 operator()(_Iter __first, _Sent __last,
1724 _Comp __comp = {}, _Proj __proj = {})
const
1726 iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
1727 iter_difference_t<_Iter> __parent = 0, __child = 1;
1728 for (; __child < __n; ++__child)
1732 return __first + __child;
1733 else if ((__child & 1) == 0)
1736 return __first + __n;
1739 template<random_access_range _Range,
1740 typename _Proj = identity,
1741 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1742 _Comp = ranges::less>
1743 constexpr borrowed_iterator_t<_Range>
1744 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1746 return (*
this)(ranges::begin(__r), ranges::end(__r),
1751 inline constexpr __is_heap_until_fn is_heap_until{};
1755 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1756 typename _Proj =
identity,
1757 indirect_strict_weak_order<projected<_Iter, _Proj>>
1758 _Comp = ranges::less>
1760 operator()(_Iter __first, _Sent __last,
1761 _Comp __comp = {}, _Proj __proj = {})
const
1764 == ranges::is_heap_until(__first, __last,
1769 template<random_access_range _Range,
1770 typename _Proj = identity,
1771 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1772 _Comp = ranges::less>
1774 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1776 return (*
this)(ranges::begin(__r), ranges::end(__r),
1781 inline constexpr __is_heap_fn is_heap{};
1785 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1786 typename _Comp = ranges::less,
typename _Proj =
identity>
1787 requires sortable<_Iter, _Comp, _Proj>
1789 operator()(_Iter __first, _Sent __last,
1790 _Comp __comp = {}, _Proj __proj = {})
const
1792 auto __lasti = ranges::next(__first, __last);
1793 _GLIBCXX_STD_A::sort(
std::move(__first), __lasti,
1794 __detail::__make_comp_proj(__comp, __proj));
1798 template<random_access_range _Range,
1799 typename _Comp = ranges::less,
typename _Proj = identity>
1800 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1801 constexpr borrowed_iterator_t<_Range>
1802 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1804 return (*
this)(ranges::begin(__r), ranges::end(__r),
1809 inline constexpr __sort_fn sort{};
1811 struct __stable_sort_fn
1813 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1814 typename _Comp = ranges::less,
typename _Proj =
identity>
1815 requires sortable<_Iter, _Comp, _Proj>
1817 operator()(_Iter __first, _Sent __last,
1818 _Comp __comp = {}, _Proj __proj = {})
const
1820 auto __lasti = ranges::next(__first, __last);
1821 std::stable_sort(
std::move(__first), __lasti,
1822 __detail::__make_comp_proj(__comp, __proj));
1826 template<random_access_range _Range,
1827 typename _Comp = ranges::less,
typename _Proj = identity>
1828 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1829 borrowed_iterator_t<_Range>
1830 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1832 return (*
this)(ranges::begin(__r), ranges::end(__r),
1837 inline constexpr __stable_sort_fn stable_sort{};
1839 struct __partial_sort_fn
1841 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1842 typename _Comp = ranges::less,
typename _Proj =
identity>
1843 requires sortable<_Iter, _Comp, _Proj>
1845 operator()(_Iter __first, _Iter __middle, _Sent __last,
1846 _Comp __comp = {}, _Proj __proj = {})
const
1848 if (__first == __middle)
1849 return ranges::next(__first, __last);
1851 ranges::make_heap(__first, __middle, __comp, __proj);
1852 auto __i = __middle;
1853 for (; __i != __last; ++__i)
1858 ranges::pop_heap(__first, __middle, __comp, __proj);
1859 ranges::iter_swap(__middle-1, __i);
1860 ranges::push_heap(__first, __middle, __comp, __proj);
1862 ranges::sort_heap(__first, __middle, __comp, __proj);
1867 template<random_access_range _Range,
1868 typename _Comp = ranges::less,
typename _Proj = identity>
1869 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1870 constexpr borrowed_iterator_t<_Range>
1871 operator()(_Range&& __r, iterator_t<_Range> __middle,
1872 _Comp __comp = {}, _Proj __proj = {})
const
1874 return (*
this)(ranges::begin(__r),
std::move(__middle),
1880 inline constexpr __partial_sort_fn partial_sort{};
1882 template<
typename _Iter,
typename _Out>
1883 using partial_sort_copy_result = in_out_result<_Iter, _Out>;
1885 struct __partial_sort_copy_fn
1887 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1888 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1889 typename _Comp = ranges::less,
1890 typename _Proj1 =
identity,
typename _Proj2 =
identity>
1891 requires indirectly_copyable<_Iter1, _Iter2>
1892 && sortable<_Iter2, _Comp, _Proj2>
1893 && indirect_strict_weak_order<_Comp,
1894 projected<_Iter1, _Proj1>,
1895 projected<_Iter2, _Proj2>>
1896 constexpr partial_sort_copy_result<_Iter1, _Iter2>
1897 operator()(_Iter1 __first, _Sent1 __last,
1898 _Iter2 __result_first, _Sent2 __result_last,
1900 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1902 if (__result_first == __result_last)
1905 auto __lasti = ranges::next(
std::move(__first),
1910 auto __result_real_last = __result_first;
1911 while (__first != __last && __result_real_last != __result_last)
1913 *__result_real_last = *__first;
1914 ++__result_real_last;
1918 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
1919 for (; __first != __last; ++__first)
1924 ranges::pop_heap(__result_first, __result_real_last,
1926 *(__result_real_last-1) = *__first;
1927 ranges::push_heap(__result_first, __result_real_last,
1930 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
1935 template<input_range _Range1, random_access_range _Range2,
1936 typename _Comp = ranges::less,
1937 typename _Proj1 = identity,
typename _Proj2 = identity>
1938 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
1939 && sortable<iterator_t<_Range2>, _Comp, _Proj2>
1940 && indirect_strict_weak_order<_Comp,
1941 projected<iterator_t<_Range1>, _Proj1>,
1942 projected<iterator_t<_Range2>, _Proj2>>
1943 constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
1944 borrowed_iterator_t<_Range2>>
1945 operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
1946 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1948 return (*
this)(ranges::begin(__r), ranges::end(__r),
1949 ranges::begin(__out), ranges::end(__out),
1955 inline constexpr __partial_sort_copy_fn partial_sort_copy{};
1957 struct __is_sorted_until_fn
1959 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1960 typename _Proj =
identity,
1961 indirect_strict_weak_order<projected<_Iter, _Proj>>
1962 _Comp = ranges::less>
1964 operator()(_Iter __first, _Sent __last,
1965 _Comp __comp = {}, _Proj __proj = {})
const
1967 if (__first == __last)
1970 auto __next = __first;
1971 for (++__next; __next != __last; __first = __next, (void)++__next)
1979 template<forward_range _Range,
typename _Proj = identity,
1980 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1981 _Comp = ranges::less>
1982 constexpr borrowed_iterator_t<_Range>
1983 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1985 return (*
this)(ranges::begin(__r), ranges::end(__r),
1990 inline constexpr __is_sorted_until_fn is_sorted_until{};
1992 struct __is_sorted_fn
1994 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1995 typename _Proj =
identity,
1996 indirect_strict_weak_order<projected<_Iter, _Proj>>
1997 _Comp = ranges::less>
1999 operator()(_Iter __first, _Sent __last,
2000 _Comp __comp = {}, _Proj __proj = {})
const
2002 if (__first == __last)
2005 auto __next = __first;
2006 for (++__next; __next != __last; __first = __next, (void)++__next)
2014 template<forward_range _Range,
typename _Proj = identity,
2015 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2016 _Comp = ranges::less>
2018 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2020 return (*
this)(ranges::begin(__r), ranges::end(__r),
2025 inline constexpr __is_sorted_fn is_sorted{};
2027 struct __nth_element_fn
2029 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2030 typename _Comp = ranges::less,
typename _Proj =
identity>
2031 requires sortable<_Iter, _Comp, _Proj>
2033 operator()(_Iter __first, _Iter __nth, _Sent __last,
2034 _Comp __comp = {}, _Proj __proj = {})
const
2036 auto __lasti = ranges::next(__first, __last);
2039 __detail::__make_comp_proj(__comp, __proj));
2043 template<random_access_range _Range,
2044 typename _Comp = ranges::less,
typename _Proj = identity>
2045 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2046 constexpr borrowed_iterator_t<_Range>
2047 operator()(_Range&& __r, iterator_t<_Range> __nth,
2048 _Comp __comp = {}, _Proj __proj = {})
const
2050 return (*
this)(ranges::begin(__r),
std::move(__nth),
2055 inline constexpr __nth_element_fn nth_element{};
2057 struct __lower_bound_fn
2059 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2060 typename _Tp,
typename _Proj =
identity,
2061 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2062 _Comp = ranges::less>
2064 operator()(_Iter __first, _Sent __last,
2065 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2067 auto __len = ranges::distance(__first, __last);
2071 auto __half = __len / 2;
2072 auto __middle = __first;
2073 ranges::advance(__middle, __half);
2078 __len = __len - __half - 1;
2086 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2087 indirect_strict_weak_order<
const _Tp*,
2088 projected<iterator_t<_Range>, _Proj>>
2089 _Comp = ranges::less>
2090 constexpr borrowed_iterator_t<_Range>
2091 operator()(_Range&& __r,
2092 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2094 return (*
this)(ranges::begin(__r), ranges::end(__r),
2099 inline constexpr __lower_bound_fn lower_bound{};
2101 struct __upper_bound_fn
2103 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2104 typename _Tp,
typename _Proj =
identity,
2105 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2106 _Comp = ranges::less>
2108 operator()(_Iter __first, _Sent __last,
2109 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2111 auto __len = ranges::distance(__first, __last);
2115 auto __half = __len / 2;
2116 auto __middle = __first;
2117 ranges::advance(__middle, __half);
2124 __len = __len - __half - 1;
2130 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2131 indirect_strict_weak_order<
const _Tp*,
2132 projected<iterator_t<_Range>, _Proj>>
2133 _Comp = ranges::less>
2134 constexpr borrowed_iterator_t<_Range>
2135 operator()(_Range&& __r,
2136 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2138 return (*
this)(ranges::begin(__r), ranges::end(__r),
2143 inline constexpr __upper_bound_fn upper_bound{};
2145 struct __equal_range_fn
2147 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2148 typename _Tp,
typename _Proj =
identity,
2149 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2150 _Comp = ranges::less>
2151 constexpr subrange<_Iter>
2152 operator()(_Iter __first, _Sent __last,
2153 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2155 auto __len = ranges::distance(__first, __last);
2159 auto __half = __len / 2;
2160 auto __middle = __first;
2161 ranges::advance(__middle, __half);
2168 __len = __len - __half - 1;
2177 = ranges::lower_bound(__first, __middle,
2178 __value, __comp, __proj);
2179 ranges::advance(__first, __len);
2181 = ranges::upper_bound(++__middle, __first,
2182 __value, __comp, __proj);
2183 return {__left, __right};
2186 return {__first, __first};
2189 template<forward_range _Range,
2190 typename _Tp,
typename _Proj = identity,
2191 indirect_strict_weak_order<
const _Tp*,
2192 projected<iterator_t<_Range>, _Proj>>
2193 _Comp = ranges::less>
2194 constexpr borrowed_subrange_t<_Range>
2195 operator()(_Range&& __r,
const _Tp& __value,
2196 _Comp __comp = {}, _Proj __proj = {})
const
2198 return (*
this)(ranges::begin(__r), ranges::end(__r),
2203 inline constexpr __equal_range_fn equal_range{};
2205 struct __binary_search_fn
2207 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2208 typename _Tp,
typename _Proj =
identity,
2209 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2210 _Comp = ranges::less>
2212 operator()(_Iter __first, _Sent __last,
2213 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2215 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2222 template<forward_range _Range,
2223 typename _Tp,
typename _Proj = identity,
2224 indirect_strict_weak_order<
const _Tp*,
2225 projected<iterator_t<_Range>, _Proj>>
2226 _Comp = ranges::less>
2228 operator()(_Range&& __r,
const _Tp& __value, _Comp __comp = {},
2229 _Proj __proj = {})
const
2231 return (*
this)(ranges::begin(__r), ranges::end(__r),
2236 inline constexpr __binary_search_fn binary_search{};
2238 struct __is_partitioned_fn
2240 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2241 typename _Proj =
identity,
2242 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2244 operator()(_Iter __first, _Sent __last,
2245 _Pred __pred, _Proj __proj = {})
const
2247 __first = ranges::find_if_not(
std::move(__first), __last,
2249 if (__first == __last)
2256 template<input_range _Range,
typename _Proj = identity,
2257 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2260 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2262 return (*
this)(ranges::begin(__r), ranges::end(__r),
2267 inline constexpr __is_partitioned_fn is_partitioned{};
2269 struct __partition_fn
2271 template<permutable _Iter, sentinel_for<_Iter> _Sent,
2272 typename _Proj =
identity,
2273 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2274 constexpr subrange<_Iter>
2275 operator()(_Iter __first, _Sent __last,
2276 _Pred __pred, _Proj __proj = {})
const
2278 if constexpr (bidirectional_iterator<_Iter>)
2280 auto __lasti = ranges::next(__first, __last);
2281 auto __tail = __lasti;
2285 if (__first == __tail)
2294 if (__first == __tail)
2301 ranges::iter_swap(__first, __tail);
2307 if (__first == __last)
2308 return {__first, __first};
2311 if (++__first == __last)
2312 return {__first, __first};
2314 auto __next = __first;
2315 while (++__next != __last)
2318 ranges::iter_swap(__first, __next);
2326 template<forward_range _Range,
typename _Proj = identity,
2327 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2329 requires permutable<iterator_t<_Range>>
2330 constexpr borrowed_subrange_t<_Range>
2331 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2333 return (*
this)(ranges::begin(__r), ranges::end(__r),
2338 inline constexpr __partition_fn partition{};
2341 struct __stable_partition_fn
2343 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2344 typename _Proj =
identity,
2345 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2346 requires permutable<_Iter>
2348 operator()(_Iter __first, _Sent __last,
2349 _Pred __pred, _Proj __proj = {})
const
2351 auto __lasti = ranges::next(__first, __last);
2353 = std::stable_partition(
std::move(__first), __lasti,
2354 __detail::__make_pred_proj(__pred, __proj));
2358 template<bidirectional_range _Range,
typename _Proj = identity,
2359 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2361 requires permutable<iterator_t<_Range>>
2362 borrowed_subrange_t<_Range>
2363 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2365 return (*
this)(ranges::begin(__r), ranges::end(__r),
2370 inline constexpr __stable_partition_fn stable_partition{};
2373 template<
typename _Iter,
typename _Out1,
typename _Out2>
2374 struct in_out_out_result
2376 [[no_unique_address]] _Iter in;
2377 [[no_unique_address]] _Out1 out1;
2378 [[no_unique_address]] _Out2 out2;
2380 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2381 requires convertible_to<const _Iter&, _IIter>
2382 && convertible_to<const _Out1&, _OOut1>
2383 && convertible_to<const _Out2&, _OOut2>
2385 operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
2386 {
return {in, out1, out2}; }
2388 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2389 requires convertible_to<_Iter, _IIter>
2390 && convertible_to<_Out1, _OOut1>
2391 && convertible_to<_Out2, _OOut2>
2393 operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2397 template<
typename _Iter,
typename _Out1,
typename _Out2>
2398 using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2400 struct __partition_copy_fn
2402 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2403 weakly_incrementable _Out1, weakly_incrementable _Out2,
2404 typename _Proj =
identity,
2405 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2406 requires indirectly_copyable<_Iter, _Out1>
2407 && indirectly_copyable<_Iter, _Out2>
2408 constexpr partition_copy_result<_Iter, _Out1, _Out2>
2409 operator()(_Iter __first, _Sent __last,
2410 _Out1 __out_true, _Out2 __out_false,
2411 _Pred __pred, _Proj __proj = {})
const
2413 for (; __first != __last; ++__first)
2416 *__out_true = *__first;
2421 *__out_false = *__first;
2429 template<input_range _Range, weakly_incrementable _Out1,
2430 weakly_incrementable _Out2,
2431 typename _Proj = identity,
2432 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2434 requires indirectly_copyable<iterator_t<_Range>, _Out1>
2435 && indirectly_copyable<iterator_t<_Range>, _Out2>
2436 constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2>
2437 operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false,
2438 _Pred __pred, _Proj __proj = {})
const
2440 return (*
this)(ranges::begin(__r), ranges::end(__r),
2446 inline constexpr __partition_copy_fn partition_copy{};
2448 struct __partition_point_fn
2450 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2451 typename _Proj =
identity,
2452 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2454 operator()(_Iter __first, _Sent __last,
2455 _Pred __pred, _Proj __proj = {})
const
2457 auto __len = ranges::distance(__first, __last);
2461 auto __half = __len / 2;
2462 auto __middle = __first;
2463 ranges::advance(__middle, __half);
2468 __len = __len - __half - 1;
2476 template<forward_range _Range,
typename _Proj = identity,
2477 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2479 constexpr borrowed_iterator_t<_Range>
2480 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2482 return (*
this)(ranges::begin(__r), ranges::end(__r),
2487 inline constexpr __partition_point_fn partition_point{};
2489 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2490 using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2494 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2495 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2496 weakly_incrementable _Out,
typename _Comp = ranges::less,
2497 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2498 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2499 constexpr merge_result<_Iter1, _Iter2, _Out>
2500 operator()(_Iter1 __first1, _Sent1 __last1,
2501 _Iter2 __first2, _Sent2 __last2, _Out __result,
2503 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2505 while (__first1 != __last1 && __first2 != __last2)
2511 *__result = *__first2;
2516 *__result = *__first1;
2529 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2530 typename _Comp = ranges::less,
2531 typename _Proj1 = identity,
typename _Proj2 = identity>
2532 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2533 _Comp, _Proj1, _Proj2>
2534 constexpr merge_result<borrowed_iterator_t<_Range1>,
2535 borrowed_iterator_t<_Range2>,
2537 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2539 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2541 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2542 ranges::begin(__r2), ranges::end(__r2),
2548 inline constexpr __merge_fn merge{};
2550 struct __inplace_merge_fn
2552 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2553 typename _Comp = ranges::less,
2554 typename _Proj =
identity>
2555 requires sortable<_Iter, _Comp, _Proj>
2557 operator()(_Iter __first, _Iter __middle, _Sent __last,
2558 _Comp __comp = {}, _Proj __proj = {})
const
2560 auto __lasti = ranges::next(__first, __last);
2562 __detail::__make_comp_proj(__comp, __proj));
2566 template<bidirectional_range _Range,
2567 typename _Comp = ranges::less,
typename _Proj = identity>
2568 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2569 borrowed_iterator_t<_Range>
2570 operator()(_Range&& __r, iterator_t<_Range> __middle,
2571 _Comp __comp = {}, _Proj __proj = {})
const
2573 return (*
this)(ranges::begin(__r),
std::move(__middle),
2579 inline constexpr __inplace_merge_fn inplace_merge{};
2581 struct __includes_fn
2583 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2584 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2585 typename _Proj1 =
identity,
typename _Proj2 =
identity,
2586 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2587 projected<_Iter2, _Proj2>>
2588 _Comp = ranges::less>
2590 operator()(_Iter1 __first1, _Sent1 __last1,
2591 _Iter2 __first2, _Sent2 __last2,
2593 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2595 while (__first1 != __last1 && __first2 != __last2)
2610 return __first2 == __last2;
2613 template<input_range _Range1, input_range _Range2,
2614 typename _Proj1 = identity,
typename _Proj2 = identity,
2615 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2616 projected<iterator_t<_Range2>, _Proj2>>
2617 _Comp = ranges::less>
2619 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2620 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2622 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2623 ranges::begin(__r2), ranges::end(__r2),
2629 inline constexpr __includes_fn includes{};
2631 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2632 using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2634 struct __set_union_fn
2636 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2637 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2638 weakly_incrementable _Out,
typename _Comp = ranges::less,
2639 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2640 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2641 constexpr set_union_result<_Iter1, _Iter2, _Out>
2642 operator()(_Iter1 __first1, _Sent1 __last1,
2643 _Iter2 __first2, _Sent2 __last2,
2644 _Out __result, _Comp __comp = {},
2645 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2647 while (__first1 != __last1 && __first2 != __last2)
2653 *__result = *__first1;
2660 *__result = *__first2;
2665 *__result = *__first1;
2679 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2680 typename _Comp = ranges::less,
2681 typename _Proj1 = identity,
typename _Proj2 = identity>
2682 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2683 _Comp, _Proj1, _Proj2>
2684 constexpr set_union_result<borrowed_iterator_t<_Range1>,
2685 borrowed_iterator_t<_Range2>, _Out>
2686 operator()(_Range1&& __r1, _Range2&& __r2,
2687 _Out __result, _Comp __comp = {},
2688 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2690 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2691 ranges::begin(__r2), ranges::end(__r2),
2697 inline constexpr __set_union_fn set_union{};
2699 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2700 using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2702 struct __set_intersection_fn
2704 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2705 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2706 weakly_incrementable _Out,
typename _Comp = ranges::less,
2707 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2708 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2709 constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2710 operator()(_Iter1 __first1, _Sent1 __last1,
2711 _Iter2 __first2, _Sent2 __last2, _Out __result,
2713 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2715 while (__first1 != __last1 && __first2 != __last2)
2726 *__result = *__first1;
2737 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2738 typename _Comp = ranges::less,
2739 typename _Proj1 = identity,
typename _Proj2 = identity>
2740 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2741 _Comp, _Proj1, _Proj2>
2742 constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
2743 borrowed_iterator_t<_Range2>, _Out>
2744 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2746 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2748 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2749 ranges::begin(__r2), ranges::end(__r2),
2755 inline constexpr __set_intersection_fn set_intersection{};
2757 template<
typename _Iter,
typename _Out>
2758 using set_difference_result = in_out_result<_Iter, _Out>;
2760 struct __set_difference_fn
2762 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2763 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2764 weakly_incrementable _Out,
typename _Comp = ranges::less,
2765 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2766 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2767 constexpr set_difference_result<_Iter1, _Out>
2768 operator()(_Iter1 __first1, _Sent1 __last1,
2769 _Iter2 __first2, _Sent2 __last2, _Out __result,
2771 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2773 while (__first1 != __last1 && __first2 != __last2)
2778 *__result = *__first1;
2795 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2796 typename _Comp = ranges::less,
2797 typename _Proj1 = identity,
typename _Proj2 = identity>
2798 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2799 _Comp, _Proj1, _Proj2>
2800 constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
2801 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2803 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2805 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2806 ranges::begin(__r2), ranges::end(__r2),
2812 inline constexpr __set_difference_fn set_difference{};
2814 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2815 using set_symmetric_difference_result
2816 = in_in_out_result<_Iter1, _Iter2, _Out>;
2818 struct __set_symmetric_difference_fn
2820 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2821 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2822 weakly_incrementable _Out,
typename _Comp = ranges::less,
2823 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2824 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2825 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
2826 operator()(_Iter1 __first1, _Sent1 __last1,
2827 _Iter2 __first2, _Sent2 __last2,
2828 _Out __result, _Comp __comp = {},
2829 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2831 while (__first1 != __last1 && __first2 != __last2)
2836 *__result = *__first1;
2844 *__result = *__first2;
2861 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2862 typename _Comp = ranges::less,
2863 typename _Proj1 = identity,
typename _Proj2 = identity>
2864 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2865 _Comp, _Proj1, _Proj2>
2866 constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
2867 borrowed_iterator_t<_Range2>,
2869 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2871 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2873 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2874 ranges::begin(__r2), ranges::end(__r2),
2880 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
2886 template<
typename _Tp,
typename _Proj = identity,
2887 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2888 _Comp = ranges::less>
2889 constexpr const _Tp&
2890 operator()(
const _Tp& __a,
const _Tp& __b,
2891 _Comp __comp = {}, _Proj __proj = {})
const
2901 template<input_range _Range,
typename _Proj = identity,
2902 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2903 _Comp = ranges::less>
2904 requires indirectly_copyable_storable<iterator_t<_Range>,
2905 range_value_t<_Range>*>
2906 constexpr range_value_t<_Range>
2907 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2909 auto __first = ranges::begin(__r);
2910 auto __last = ranges::end(__r);
2911 __glibcxx_assert(__first != __last);
2912 auto __result = *__first;
2913 while (++__first != __last)
2915 auto&& __tmp = *__first;
2924 template<copyable _Tp,
typename _Proj = identity,
2925 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2926 _Comp = ranges::less>
2928 operator()(initializer_list<_Tp> __r,
2929 _Comp __comp = {}, _Proj __proj = {})
const
2931 return (*
this)(ranges::subrange(__r),
2936 inline constexpr __max_fn max{};
2940 template<
typename _Tp,
typename _Proj = identity,
2941 indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
2943 constexpr const _Tp&
2944 operator()(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi,
2945 _Comp __comp = {}, _Proj __proj = {})
const
2964 inline constexpr __clamp_fn clamp{};
2966 template<
typename _Tp>
2967 struct min_max_result
2969 [[no_unique_address]] _Tp min;
2970 [[no_unique_address]] _Tp max;
2972 template<
typename _Tp2>
2973 requires convertible_to<const _Tp&, _Tp2>
2975 operator min_max_result<_Tp2>() const &
2976 {
return {min, max}; }
2978 template<
typename _Tp2>
2979 requires convertible_to<_Tp, _Tp2>
2981 operator min_max_result<_Tp2>() &&
2985 template<
typename _Tp>
2986 using minmax_result = min_max_result<_Tp>;
2990 template<
typename _Tp,
typename _Proj = identity,
2991 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2992 _Comp = ranges::less>
2993 constexpr minmax_result<const _Tp&>
2994 operator()(
const _Tp& __a,
const _Tp& __b,
2995 _Comp __comp = {}, _Proj __proj = {})
const
3005 template<input_range _Range,
typename _Proj = identity,
3006 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3007 _Comp = ranges::less>
3008 requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
3009 constexpr minmax_result<range_value_t<_Range>>
3010 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3012 auto __first = ranges::begin(__r);
3013 auto __last = ranges::end(__r);
3014 __glibcxx_assert(__first != __last);
3015 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3016 minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};
3017 if (++__first == __last)
3023 auto&& __val = *__first;
3024 if (__comp_proj(__val, __result.min))
3029 while (++__first != __last)
3034 range_value_t<_Range> __val1 = *__first;
3035 if (++__first == __last)
3040 if (__comp_proj(__val1, __result.min))
3042 else if (!__comp_proj(__val1, __result.max))
3046 auto&& __val2 = *__first;
3047 if (!__comp_proj(__val2, __val1))
3049 if (__comp_proj(__val1, __result.min))
3051 if (!__comp_proj(__val2, __result.max))
3056 if (__comp_proj(__val2, __result.min))
3058 if (!__comp_proj(__val1, __result.max))
3065 template<copyable _Tp,
typename _Proj = identity,
3066 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3067 _Comp = ranges::less>
3068 constexpr minmax_result<_Tp>
3069 operator()(initializer_list<_Tp> __r,
3070 _Comp __comp = {}, _Proj __proj = {})
const
3072 return (*
this)(ranges::subrange(__r),
3077 inline constexpr __minmax_fn minmax{};
3079 struct __min_element_fn
3081 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3082 typename _Proj =
identity,
3083 indirect_strict_weak_order<projected<_Iter, _Proj>>
3084 _Comp = ranges::less>
3086 operator()(_Iter __first, _Sent __last,
3087 _Comp __comp = {}, _Proj __proj = {})
const
3089 if (__first == __last)
3093 while (++__i != __last)
3103 template<forward_range _Range,
typename _Proj = identity,
3104 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3105 _Comp = ranges::less>
3106 constexpr borrowed_iterator_t<_Range>
3107 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3109 return (*
this)(ranges::begin(__r), ranges::end(__r),
3114 inline constexpr __min_element_fn min_element{};
3116 struct __max_element_fn
3118 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3119 typename _Proj =
identity,
3120 indirect_strict_weak_order<projected<_Iter, _Proj>>
3121 _Comp = ranges::less>
3123 operator()(_Iter __first, _Sent __last,
3124 _Comp __comp = {}, _Proj __proj = {})
const
3126 if (__first == __last)
3130 while (++__i != __last)
3140 template<forward_range _Range,
typename _Proj = identity,
3141 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3142 _Comp = ranges::less>
3143 constexpr borrowed_iterator_t<_Range>
3144 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3146 return (*
this)(ranges::begin(__r), ranges::end(__r),
3151 inline constexpr __max_element_fn max_element{};
3153 template<
typename _Iter>
3154 using minmax_element_result = min_max_result<_Iter>;
3156 struct __minmax_element_fn
3158 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3159 typename _Proj =
identity,
3160 indirect_strict_weak_order<projected<_Iter, _Proj>>
3161 _Comp = ranges::less>
3162 constexpr minmax_element_result<_Iter>
3163 operator()(_Iter __first, _Sent __last,
3164 _Comp __comp = {}, _Proj __proj = {})
const
3166 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3167 minmax_element_result<_Iter> __result = {__first, __first};
3168 if (__first == __last || ++__first == __last)
3174 if (__comp_proj(*__first, *__result.min))
3175 __result.min = __first;
3177 __result.max = __first;
3179 while (++__first != __last)
3184 auto __prev = __first;
3185 if (++__first == __last)
3190 if (__comp_proj(*__prev, *__result.min))
3191 __result.min = __prev;
3192 else if (!__comp_proj(*__prev, *__result.max))
3193 __result.max = __prev;
3196 if (!__comp_proj(*__first, *__prev))
3198 if (__comp_proj(*__prev, *__result.min))
3199 __result.min = __prev;
3200 if (!__comp_proj(*__first, *__result.max))
3201 __result.max = __first;
3205 if (__comp_proj(*__first, *__result.min))
3206 __result.min = __first;
3207 if (!__comp_proj(*__prev, *__result.max))
3208 __result.max = __prev;
3214 template<forward_range _Range,
typename _Proj = identity,
3215 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3216 _Comp = ranges::less>
3217 constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3218 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3220 return (*
this)(ranges::begin(__r), ranges::end(__r),
3225 inline constexpr __minmax_element_fn minmax_element{};
3227 struct __lexicographical_compare_fn
3229 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3230 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3231 typename _Proj1 =
identity,
typename _Proj2 =
identity,
3232 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3233 projected<_Iter2, _Proj2>>
3234 _Comp = ranges::less>
3236 operator()(_Iter1 __first1, _Sent1 __last1,
3237 _Iter2 __first2, _Sent2 __last2,
3239 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3241 if constexpr (__detail::__is_normal_iterator<_Iter1>
3242 && same_as<_Iter1, _Sent1>)
3243 return (*
this)(__first1.base(), __last1.base(),
3247 else if constexpr (__detail::__is_normal_iterator<_Iter2>
3248 && same_as<_Iter2, _Sent2>)
3250 __first2.base(), __last2.base(),
3255 constexpr bool __sized_iters
3256 = (sized_sentinel_for<_Sent1, _Iter1>
3257 && sized_sentinel_for<_Sent2, _Iter2>);
3258 if constexpr (__sized_iters)
3260 using _ValueType1 = iter_value_t<_Iter1>;
3261 using _ValueType2 = iter_value_t<_Iter2>;
3264 constexpr bool __use_memcmp
3265 = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3266 && __ptr_to_nonvolatile<_Iter1>
3267 && __ptr_to_nonvolatile<_Iter2>
3268 && (is_same_v<_Comp, ranges::less>
3269 || is_same_v<_Comp, ranges::greater>)
3270 && is_same_v<_Proj1, identity>
3271 && is_same_v<_Proj2, identity>);
3272 if constexpr (__use_memcmp)
3274 const auto __d1 = __last1 - __first1;
3275 const auto __d2 = __last2 - __first2;
3277 if (
const auto __len =
std::min(__d1, __d2))
3280 = std::__memcmp(__first1, __first2, __len);
3281 if constexpr (is_same_v<_Comp, ranges::less>)
3288 else if constexpr (is_same_v<_Comp, ranges::greater>)
3300 for (; __first1 != __last1 && __first2 != __last2;
3301 ++__first1, (void) ++__first2)
3312 return __first1 == __last1 && __first2 != __last2;
3316 template<input_range _Range1, input_range _Range2,
3317 typename _Proj1 = identity,
typename _Proj2 = identity,
3318 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3319 projected<iterator_t<_Range2>, _Proj2>>
3320 _Comp = ranges::less>
3322 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3323 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3325 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
3326 ranges::begin(__r2), ranges::end(__r2),
3332 template<
typename _Iter,
typename _Ref = iter_reference_t<_Iter>>
3333 static constexpr bool __ptr_to_nonvolatile
3334 = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3337 inline constexpr __lexicographical_compare_fn lexicographical_compare;
3339 template<
typename _Iter>
3340 struct in_found_result
3342 [[no_unique_address]] _Iter in;
3345 template<
typename _Iter2>
3346 requires convertible_to<const _Iter&, _Iter2>
3348 operator in_found_result<_Iter2>() const &
3349 {
return {in, found}; }
3351 template<
typename _Iter2>
3352 requires convertible_to<_Iter, _Iter2>
3354 operator in_found_result<_Iter2>() &&
3358 template<
typename _Iter>
3359 using next_permutation_result = in_found_result<_Iter>;
3361 struct __next_permutation_fn
3363 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3364 typename _Comp = ranges::less,
typename _Proj =
identity>
3365 requires sortable<_Iter, _Comp, _Proj>
3366 constexpr next_permutation_result<_Iter>
3367 operator()(_Iter __first, _Sent __last,
3368 _Comp __comp = {}, _Proj __proj = {})
const
3370 if (__first == __last)
3378 auto __lasti = ranges::next(__first, __last);
3395 ranges::iter_swap(__i, __j);
3396 ranges::reverse(__ii, __last);
3401 ranges::reverse(__first, __last);
3407 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3408 typename _Proj = identity>
3409 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3410 constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3411 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3413 return (*
this)(ranges::begin(__r), ranges::end(__r),
3418 inline constexpr __next_permutation_fn next_permutation{};
3420 template<
typename _Iter>
3421 using prev_permutation_result = in_found_result<_Iter>;
3423 struct __prev_permutation_fn
3425 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3426 typename _Comp = ranges::less,
typename _Proj =
identity>
3427 requires sortable<_Iter, _Comp, _Proj>
3428 constexpr prev_permutation_result<_Iter>
3429 operator()(_Iter __first, _Sent __last,
3430 _Comp __comp = {}, _Proj __proj = {})
const
3432 if (__first == __last)
3440 auto __lasti = ranges::next(__first, __last);
3457 ranges::iter_swap(__i, __j);
3458 ranges::reverse(__ii, __last);
3463 ranges::reverse(__first, __last);
3469 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3470 typename _Proj = identity>
3471 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3472 constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3473 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3475 return (*
this)(ranges::begin(__r), ranges::end(__r),
3480 inline constexpr __prev_permutation_fn prev_permutation{};
3482#if __glibcxx_ranges_contains >= 202207L
3483 struct __contains_fn
3485 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3486 typename _Tp,
typename _Proj =
identity>
3487 requires indirect_binary_predicate<ranges::equal_to,
3488 projected<_Iter, _Proj>,
const _Tp*>
3490 operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
const
3491 {
return ranges::find(
std::move(__first), __last, __value,
std::move(__proj)) != __last; }
3493 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
3494 requires indirect_binary_predicate<ranges::equal_to,
3495 projected<iterator_t<_Range>, _Proj>,
const _Tp*>
3497 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
3498 {
return (*
this)(ranges::begin(__r), ranges::end(__r), __value,
std::move(__proj)); }
3501 inline constexpr __contains_fn contains{};
3503 struct __contains_subrange_fn
3505 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3506 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3507 typename _Pred = ranges::equal_to,
3508 typename _Proj1 =
identity,
typename _Proj2 =
identity>
3509 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
3511 operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
3512 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3514 return __first2 == __last2
3515 || !ranges::search(__first1, __last1, __first2, __last2,
3519 template<forward_range _Range1, forward_range _Range2,
3520 typename _Pred = ranges::equal_to,
3521 typename _Proj1 = identity,
typename _Proj2 = identity>
3522 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
3523 _Pred, _Proj1, _Proj2>
3525 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
3526 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3528 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
3529 ranges::begin(__r2), ranges::end(__r2),
3534 inline constexpr __contains_subrange_fn contains_subrange{};
3538#if __glibcxx_ranges_find_last >= 202207L
3540 struct __find_last_fn
3542 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
typename _Proj =
identity>
3543 requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
const _Tp*>
3544 constexpr subrange<_Iter>
3545 operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
const
3547 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3549 _Iter __found = ranges::find(reverse_iterator<_Iter>{__last},
3550 reverse_iterator<_Iter>{__first},
3552 if (__found == __first)
3553 return {__last, __last};
3555 return {ranges::prev(__found), __last};
3559 _Iter __found = ranges::find(__first, __last, __value, __proj);
3560 if (__found == __last)
3561 return {__found, __found};
3565 __first = ranges::find(ranges::next(__first), __last, __value, __proj);
3566 if (__first == __last)
3567 return {__found, __first};
3573 template<forward_range _Range,
typename _Tp,
typename _Proj =
identity>
3574 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>,
const _Tp*>
3575 constexpr borrowed_subrange_t<_Range>
3576 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
3577 {
return (*
this)(ranges::begin(__r), ranges::end(__r), __value,
std::move(__proj)); }
3580 inline constexpr __find_last_fn find_last{};
3582 struct __find_last_if_fn
3584 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Proj =
identity,
3585 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3586 constexpr subrange<_Iter>
3587 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
const
3589 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3591 _Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last},
3592 reverse_iterator<_Iter>{__first},
3594 if (__found == __first)
3595 return {__last, __last};
3597 return {ranges::prev(__found), __last};
3601 _Iter __found = ranges::find_if(__first, __last, __pred, __proj);
3602 if (__found == __last)
3603 return {__found, __found};
3607 __first = ranges::find_if(ranges::next(__first), __last, __pred, __proj);
3608 if (__first == __last)
3609 return {__found, __first};
3615 template<forward_range _Range,
typename _Proj = identity,
3616 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3617 constexpr borrowed_subrange_t<_Range>
3618 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
3619 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred),
std::move(__proj)); }
3622 inline constexpr __find_last_if_fn find_last_if{};
3624 struct __find_last_if_not_fn
3626 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Proj =
identity,
3627 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3628 constexpr subrange<_Iter>
3629 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
const
3631 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3633 _Iter __found = ranges::find_if_not(reverse_iterator<_Iter>{__last},
3634 reverse_iterator<_Iter>{__first},
3636 if (__found == __first)
3637 return {__last, __last};
3639 return {ranges::prev(__found), __last};
3643 _Iter __found = ranges::find_if_not(__first, __last, __pred, __proj);
3644 if (__found == __last)
3645 return {__found, __found};
3649 __first = ranges::find_if_not(ranges::next(__first), __last, __pred, __proj);
3650 if (__first == __last)
3651 return {__found, __first};
3657 template<forward_range _Range,
typename _Proj = identity,
3658 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3659 constexpr borrowed_subrange_t<_Range>
3660 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
3661 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred),
std::move(__proj)); }
3664 inline constexpr __find_last_if_not_fn find_last_if_not{};
3668#if __glibcxx_ranges_fold >= 202207L
3670 template<
typename _Iter,
typename _Tp>
3671 struct in_value_result
3673 [[no_unique_address]] _Iter in;
3674 [[no_unique_address]] _Tp value;
3676 template<
typename _Iter2,
typename _Tp2>
3677 requires convertible_to<const _Iter&, _Iter2>
3678 && convertible_to<const _Tp&, _Tp2>
3680 operator in_value_result<_Iter2, _Tp2>() const &
3681 {
return {in, value}; }
3683 template<
typename _Iter2,
typename _Tp2>
3684 requires convertible_to<_Iter, _Iter2>
3685 && convertible_to<_Tp, _Tp2>
3687 operator in_value_result<_Iter2, _Tp2>() &&
3693 template<
typename _Fp>
3699 template<
typename _Tp,
typename _Up>
3700 requires invocable<_Fp&, _Up, _Tp>
3701 invoke_result_t<_Fp&, _Up, _Tp>
3702 operator()(_Tp&&, _Up&&);
3705 template<
typename _Fp,
typename _Tp,
typename _Iter,
typename _Up>
3706 concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up>
3707 && convertible_to<_Tp, _Up>
3708 && invocable<_Fp&, _Up, iter_reference_t<_Iter>>
3709 && assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>;
3711 template<
typename _Fp,
typename _Tp,
typename _Iter>
3712 concept __indirectly_binary_left_foldable = copy_constructible<_Fp>
3713 && indirectly_readable<_Iter>
3714 && invocable<_Fp&, _Tp, iter_reference_t<_Iter>>
3715 && convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>,
3716 decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>
3717 && __indirectly_binary_left_foldable_impl
3718 <_Fp, _Tp, _Iter, decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>>;
3720 template <
typename _Fp,
typename _Tp,
typename _Iter>
3721 concept __indirectly_binary_right_foldable
3722 = __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>;
3725 template<
typename _Iter,
typename _Tp>
3726 using fold_left_with_iter_result = in_value_result<_Iter, _Tp>;
3728 struct __fold_left_with_iter_fn
3730 template<
typename _Ret_iter,
3731 typename _Iter,
typename _Sent,
typename _Tp,
typename _Fp>
3732 static constexpr auto
3733 _S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
3735 using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>;
3736 using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>;
3738 if (__first == __last)
3742 for (++__first; __first != __last; ++__first)
3747 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
3748 __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3750 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3752 using _Ret_iter = _Iter;
3753 return _S_impl<_Ret_iter>(
std::move(__first), __last,
3757 template<input_range _Range,
typename _Tp,
3758 __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3760 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3762 using _Ret_iter = borrowed_iterator_t<_Range>;
3763 return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
3768 inline constexpr __fold_left_with_iter_fn fold_left_with_iter{};
3770 struct __fold_left_fn
3772 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
3773 __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3775 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3777 return ranges::fold_left_with_iter(
std::move(__first), __last,
3781 template<input_range _Range,
typename _Tp,
3782 __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3784 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3785 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__init),
std::move(__f)); }
3788 inline constexpr __fold_left_fn fold_left{};
3790 template<
typename _Iter,
typename _Tp>
3791 using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>;
3793 struct __fold_left_first_with_iter_fn
3795 template<
typename _Ret_iter,
typename _Iter,
typename _Sent,
typename _Fp>
3796 static constexpr auto
3797 _S_impl(_Iter __first, _Sent __last, _Fp __f)
3799 using _Up =
decltype(ranges::fold_left(
std::move(__first), __last,
3800 iter_value_t<_Iter>(*__first), __f));
3801 using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>;
3803 if (__first == __last)
3804 return _Ret{
std::move(__first), optional<_Up>()};
3806 optional<_Up> __init(in_place, *__first);
3807 for (++__first; __first != __last; ++__first)
3812 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3813 __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3814 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3816 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3818 using _Ret_iter = _Iter;
3822 template<input_range _Range,
3823 __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3824 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3826 operator()(_Range&& __r, _Fp __f)
const
3828 using _Ret_iter = borrowed_iterator_t<_Range>;
3829 return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
std::move(__f));
3833 inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{};
3835 struct __fold_left_first_fn
3837 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3838 __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3839 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3841 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3843 return ranges::fold_left_first_with_iter(
std::move(__first), __last,
3847 template<input_range _Range,
3848 __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3849 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3851 operator()(_Range&& __r, _Fp __f)
const
3852 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__f)); }
3855 inline constexpr __fold_left_first_fn fold_left_first{};
3857 struct __fold_right_fn
3859 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
3860 __detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp>
3862 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3864 using _Up = decay_t<invoke_result_t<_Fp&, iter_reference_t<_Iter>, _Tp>>;
3866 if (__first == __last)
3869 _Iter __tail = ranges::next(__first, __last);
3871 while (__first != __tail)
3876 template<bidirectional_range _Range,
typename _Tp,
3877 __detail::__indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Fp>
3879 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3880 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__init),
std::move(__f)); }
3883 inline constexpr __fold_right_fn fold_right{};
3885 struct __fold_right_last_fn
3887 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3888 __detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3889 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3891 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3893 using _Up =
decltype(ranges::fold_right(__first, __last,
3894 iter_value_t<_Iter>(*__first), __f));
3896 if (__first == __last)
3897 return optional<_Up>();
3899 _Iter __tail = ranges::prev(ranges::next(__first,
std::move(__last)));
3900 return optional<_Up>(in_place,
3901 ranges::fold_right(
std::move(__first), __tail,
3902 iter_value_t<_Iter>(*__tail),
3906 template<bidirectional_range _Range,
3907 __detail::__indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3908 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3910 operator()(_Range&& __r, _Fp __f)
const
3911 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__f)); }
3914 inline constexpr __fold_right_last_fn fold_right_last{};
3918 template<
typename _ForwardIterator>
3919 constexpr _ForwardIterator
3920 shift_left(_ForwardIterator __first, _ForwardIterator __last,
3921 typename iterator_traits<_ForwardIterator>::difference_type __n)
3923 __glibcxx_assert(__n >= 0);
3927 auto __mid = ranges::next(__first, __n, __last);
3928 if (__mid == __last)
3933 template<
typename _ForwardIterator>
3934 constexpr _ForwardIterator
3935 shift_right(_ForwardIterator __first, _ForwardIterator __last,
3936 typename iterator_traits<_ForwardIterator>::difference_type __n)
3938 __glibcxx_assert(__n >= 0);
3943 =
typename iterator_traits<_ForwardIterator>::iterator_category;
3944 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
3946 auto __mid = ranges::next(__last, -__n, __first);
3947 if (__mid == __first)
3955 auto __result = ranges::next(__first, __n, __last);
3956 if (__result == __last)
3959 auto __dest_head = __first, __dest_tail = __result;
3960 while (__dest_head != __result)
3962 if (__dest_tail == __last)
3986 auto __cursor = __first;
3987 while (__cursor != __result)
3989 if (__dest_tail == __last)
3994 __dest_head =
std::move(__cursor, __result,
4000 std::iter_swap(__cursor, __dest_head);
4009_GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.