31#define _RANGES_ALGO_H 1
33#if __cplusplus > 201703L
35#if __cplusplus > 202002L
43namespace std _GLIBCXX_VISIBILITY(default)
45_GLIBCXX_BEGIN_NAMESPACE_VERSION
50 template<
typename _Comp,
typename _Proj>
52 __make_comp_proj(_Comp& __comp, _Proj& __proj)
54 return [&] (
auto&& __lhs,
auto&& __rhs) ->
bool {
55 using _TL =
decltype(__lhs);
56 using _TR =
decltype(__rhs);
63 template<
typename _Pred,
typename _Proj>
65 __make_pred_proj(_Pred& __pred, _Proj& __proj)
67 return [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
76 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
77 typename _Proj =
identity,
78 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
80 operator()(_Iter __first, _Sent __last,
81 _Pred __pred, _Proj __proj = {})
const
83 for (; __first != __last; ++__first)
89 template<input_range _Range,
typename _Proj = identity,
90 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
93 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
95 return (*
this)(ranges::begin(__r), ranges::end(__r),
100 inline constexpr __all_of_fn all_of{};
104 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
105 typename _Proj =
identity,
106 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
108 operator()(_Iter __first, _Sent __last,
109 _Pred __pred, _Proj __proj = {})
const
111 for (; __first != __last; ++__first)
117 template<input_range _Range,
typename _Proj = identity,
118 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
121 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
123 return (*
this)(ranges::begin(__r), ranges::end(__r),
128 inline constexpr __any_of_fn any_of{};
132 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
133 typename _Proj =
identity,
134 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
136 operator()(_Iter __first, _Sent __last,
137 _Pred __pred, _Proj __proj = {})
const
139 for (; __first != __last; ++__first)
145 template<input_range _Range,
typename _Proj = identity,
146 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
149 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
151 return (*
this)(ranges::begin(__r), ranges::end(__r),
156 inline constexpr __none_of_fn none_of{};
158 template<
typename _Iter,
typename _Fp>
161 [[no_unique_address]] _Iter in;
162 [[no_unique_address]] _Fp fun;
164 template<
typename _Iter2,
typename _F2p>
165 requires convertible_to<const _Iter&, _Iter2>
166 && convertible_to<const _Fp&, _F2p>
168 operator in_fun_result<_Iter2, _F2p>() const &
169 {
return {in, fun}; }
171 template<
typename _Iter2,
typename _F2p>
172 requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
174 operator in_fun_result<_Iter2, _F2p>() &&
178 template<
typename _Iter,
typename _Fp>
179 using for_each_result = in_fun_result<_Iter, _Fp>;
183 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
184 typename _Proj =
identity,
185 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
186 constexpr for_each_result<_Iter, _Fun>
187 operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {})
const
189 for (; __first != __last; ++__first)
194 template<input_range _Range,
typename _Proj = identity,
195 indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
197 constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun>
198 operator()(_Range&& __r, _Fun __f, _Proj __proj = {})
const
200 return (*
this)(ranges::begin(__r), ranges::end(__r),
205 inline constexpr __for_each_fn for_each{};
207 template<
typename _Iter,
typename _Fp>
208 using for_each_n_result = in_fun_result<_Iter, _Fp>;
210 struct __for_each_n_fn
212 template<input_iterator _Iter,
typename _Proj = identity,
213 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
214 constexpr for_each_n_result<_Iter, _Fun>
215 operator()(_Iter __first, iter_difference_t<_Iter> __n,
216 _Fun __f, _Proj __proj = {})
const
218 if constexpr (random_access_iterator<_Iter>)
222 auto __last = __first + __n;
238 inline constexpr __for_each_n_fn for_each_n{};
242 struct __find_first_of_fn
244 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
245 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
246 typename _Pred = ranges::equal_to,
247 typename _Proj1 =
identity,
typename _Proj2 =
identity>
248 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
250 operator()(_Iter1 __first1, _Sent1 __last1,
251 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
252 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
254 for (; __first1 != __last1; ++__first1)
255 for (
auto __iter = __first2; __iter != __last2; ++__iter)
263 template<input_range _Range1, forward_range _Range2,
264 typename _Pred = ranges::equal_to,
265 typename _Proj1 = identity,
typename _Proj2 = identity>
266 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
267 _Pred, _Proj1, _Proj2>
268 constexpr borrowed_iterator_t<_Range1>
269 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
270 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
272 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
273 ranges::begin(__r2), ranges::end(__r2),
279 inline constexpr __find_first_of_fn find_first_of{};
283 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
284 typename _Tp,
typename _Proj =
identity>
285 requires indirect_binary_predicate<ranges::equal_to,
286 projected<_Iter, _Proj>,
288 constexpr iter_difference_t<_Iter>
289 operator()(_Iter __first, _Sent __last,
290 const _Tp& __value, _Proj __proj = {})
const
292 iter_difference_t<_Iter> __n = 0;
293 for (; __first != __last; ++__first)
299 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
300 requires indirect_binary_predicate<ranges::equal_to,
301 projected<iterator_t<_Range>, _Proj>,
303 constexpr range_difference_t<_Range>
304 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
306 return (*
this)(ranges::begin(__r), ranges::end(__r),
311 inline constexpr __count_fn count{};
315 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
316 typename _Proj =
identity,
317 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
318 constexpr iter_difference_t<_Iter>
319 operator()(_Iter __first, _Sent __last,
320 _Pred __pred, _Proj __proj = {})
const
322 iter_difference_t<_Iter> __n = 0;
323 for (; __first != __last; ++__first)
329 template<input_range _Range,
330 typename _Proj = identity,
331 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
333 constexpr range_difference_t<_Range>
334 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
336 return (*
this)(ranges::begin(__r), ranges::end(__r),
341 inline constexpr __count_if_fn count_if{};
347 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
348 typename _Pred = ranges::equal_to,
typename _Proj =
identity>
349 requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
350 constexpr subrange<_Iter>
351 operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
352 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const
355 return {__first, __first};
357 auto __value_comp = [&] <
typename _Rp> (_Rp&& __arg) ->
bool {
362 __first = ranges::find_if(
std::move(__first), __last,
365 if (__first == __last)
366 return {__first, __first};
369 auto __end = __first;
370 return {__first, ++__end};
374 if constexpr (sized_sentinel_for<_Sent, _Iter>
375 && random_access_iterator<_Iter>)
377 auto __tail_size = __last - __first;
378 auto __remainder = __count;
380 while (__remainder <= __tail_size)
382 __first += __remainder;
383 __tail_size -= __remainder;
384 auto __backtrack = __first;
387 if (--__remainder == 0)
388 return {__first - __count, __first};
390 __remainder = __count + 1 - (__first - __backtrack);
392 auto __i = __first + __tail_size;
397 __first = ranges::find_if(__first, __last, __value_comp, __proj);
398 while (__first != __last)
403 while (__i != __last && __n != 1
410 return {__first, __i};
413 __first = ranges::find_if(++__i, __last, __value_comp, __proj);
415 return {__first, __first};
419 template<forward_range _Range,
typename _Tp,
420 typename _Pred = ranges::equal_to,
typename _Proj = identity>
421 requires indirectly_comparable<iterator_t<_Range>,
const _Tp*,
423 constexpr borrowed_subrange_t<_Range>
424 operator()(_Range&& __r, range_difference_t<_Range> __count,
425 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const
427 return (*
this)(ranges::begin(__r), ranges::end(__r),
433 inline constexpr __search_n_fn search_n{};
437 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
438 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
439 typename _Pred = ranges::equal_to,
440 typename _Proj1 =
identity,
typename _Proj2 =
identity>
441 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
442 constexpr subrange<_Iter1>
443 operator()(_Iter1 __first1, _Sent1 __last1,
444 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
445 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
447 if constexpr (bidirectional_iterator<_Iter1>
448 && bidirectional_iterator<_Iter2>)
450 auto __i1 = ranges::next(__first1, __last1);
451 auto __i2 = ranges::next(__first2, __last2);
453 = ranges::search(reverse_iterator<_Iter1>{__i1},
454 reverse_iterator<_Iter1>{__first1},
455 reverse_iterator<_Iter2>{__i2},
456 reverse_iterator<_Iter2>{__first2},
459 auto __result_first = ranges::end(__rresult).base();
460 auto __result_last = ranges::begin(__rresult).base();
461 if (__result_last == __first1)
464 return {__result_first, __result_last};
468 auto __i = ranges::next(__first1, __last1);
469 if (__first2 == __last2)
472 auto __result_begin = __i;
473 auto __result_end = __i;
476 auto __new_range = ranges::search(__first1, __last1,
478 __pred, __proj1, __proj2);
479 auto __new_result_begin = ranges::begin(__new_range);
480 auto __new_result_end = ranges::end(__new_range);
481 if (__new_result_begin == __last1)
482 return {__result_begin, __result_end};
485 __result_begin = __new_result_begin;
486 __result_end = __new_result_end;
487 __first1 = __result_begin;
494 template<forward_range _Range1, forward_range _Range2,
495 typename _Pred = ranges::equal_to,
496 typename _Proj1 = identity,
typename _Proj2 = identity>
497 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
498 _Pred, _Proj1, _Proj2>
499 constexpr borrowed_subrange_t<_Range1>
500 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
501 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
503 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
504 ranges::begin(__r2), ranges::end(__r2),
510 inline constexpr __find_end_fn find_end{};
514 struct __is_permutation_fn
516 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
517 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
518 typename _Proj1 =
identity,
typename _Proj2 =
identity,
519 indirect_equivalence_relation<projected<_Iter1, _Proj1>,
520 projected<_Iter2, _Proj2>> _Pred
523 operator()(_Iter1 __first1, _Sent1 __last1,
524 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
525 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
527 constexpr bool __sized_iters
528 = (sized_sentinel_for<_Sent1, _Iter1>
529 && sized_sentinel_for<_Sent2, _Iter2>);
530 if constexpr (__sized_iters)
532 auto __d1 = ranges::distance(__first1, __last1);
533 auto __d2 = ranges::distance(__first2, __last2);
540 for (; __first1 != __last1 && __first2 != __last2;
541 ++__first1, (void)++__first2)
547 if constexpr (__sized_iters)
549 if (__first1 == __last1)
554 auto __d1 = ranges::distance(__first1, __last1);
555 auto __d2 = ranges::distance(__first2, __last2);
556 if (__d1 == 0 && __d2 == 0)
562 for (
auto __scan = __first1; __scan != __last1; ++__scan)
565 auto __comp_scan = [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
569 if (__scan != ranges::find_if(__first1, __scan,
570 __comp_scan, __proj1))
573 auto __matches = ranges::count_if(__first2, __last2,
574 __comp_scan, __proj2);
576 || ranges::count_if(__scan, __last1,
577 __comp_scan, __proj1) != __matches)
583 template<forward_range _Range1, forward_range _Range2,
584 typename _Proj1 = identity,
typename _Proj2 = identity,
585 indirect_equivalence_relation<
586 projected<iterator_t<_Range1>, _Proj1>,
587 projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
589 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
590 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
592 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
593 ranges::begin(__r2), ranges::end(__r2),
599 inline constexpr __is_permutation_fn is_permutation{};
601 template<
typename _Iter,
typename _Out>
602 using copy_if_result = in_out_result<_Iter, _Out>;
606 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
607 weakly_incrementable _Out,
typename _Proj =
identity,
608 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
609 requires indirectly_copyable<_Iter, _Out>
610 constexpr copy_if_result<_Iter, _Out>
611 operator()(_Iter __first, _Sent __last, _Out __result,
612 _Pred __pred, _Proj __proj = {})
const
614 for (; __first != __last; ++__first)
617 *__result = *__first;
623 template<input_range _Range, weakly_incrementable _Out,
624 typename _Proj = identity,
625 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
627 requires indirectly_copyable<iterator_t<_Range>, _Out>
628 constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
629 operator()(_Range&& __r, _Out __result,
630 _Pred __pred, _Proj __proj = {})
const
632 return (*
this)(ranges::begin(__r), ranges::end(__r),
638 inline constexpr __copy_if_fn copy_if{};
640 template<
typename _Iter1,
typename _Iter2>
641 using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
643 struct __swap_ranges_fn
645 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
646 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
647 requires indirectly_swappable<_Iter1, _Iter2>
648 constexpr swap_ranges_result<_Iter1, _Iter2>
649 operator()(_Iter1 __first1, _Sent1 __last1,
650 _Iter2 __first2, _Sent2 __last2)
const
652 for (; __first1 != __last1 && __first2 != __last2;
653 ++__first1, (void)++__first2)
654 ranges::iter_swap(__first1, __first2);
658 template<input_range _Range1, input_range _Range2>
659 requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
660 constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
661 borrowed_iterator_t<_Range2>>
662 operator()(_Range1&& __r1, _Range2&& __r2)
const
664 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
665 ranges::begin(__r2), ranges::end(__r2));
669 inline constexpr __swap_ranges_fn swap_ranges{};
671 template<
typename _Iter,
typename _Out>
672 using unary_transform_result = in_out_result<_Iter, _Out>;
674 template<
typename _Iter1,
typename _Iter2,
typename _Out>
675 struct in_in_out_result
677 [[no_unique_address]] _Iter1 in1;
678 [[no_unique_address]] _Iter2 in2;
679 [[no_unique_address]] _Out out;
681 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
682 requires convertible_to<const _Iter1&, _IIter1>
683 && convertible_to<const _Iter2&, _IIter2>
684 && convertible_to<const _Out&, _OOut>
686 operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
687 {
return {in1, in2, out}; }
689 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
690 requires convertible_to<_Iter1, _IIter1>
691 && convertible_to<_Iter2, _IIter2>
692 && convertible_to<_Out, _OOut>
694 operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
698 template<
typename _Iter1,
typename _Iter2,
typename _Out>
699 using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
701 struct __transform_fn
703 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
704 weakly_incrementable _Out,
705 copy_constructible _Fp,
typename _Proj =
identity>
706 requires indirectly_writable<_Out,
707 indirect_result_t<_Fp&,
708 projected<_Iter, _Proj>>>
709 constexpr unary_transform_result<_Iter, _Out>
710 operator()(_Iter __first1, _Sent __last1, _Out __result,
711 _Fp __op, _Proj __proj = {})
const
713 for (; __first1 != __last1; ++__first1, (void)++__result)
718 template<input_range _Range, weakly_incrementable _Out,
719 copy_constructible _Fp,
typename _Proj = identity>
720 requires indirectly_writable<_Out,
721 indirect_result_t<_Fp&,
722 projected<iterator_t<_Range>, _Proj>>>
723 constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
724 operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {})
const
726 return (*
this)(ranges::begin(__r), ranges::end(__r),
731 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
732 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
733 weakly_incrementable _Out, copy_constructible _Fp,
734 typename _Proj1 =
identity,
typename _Proj2 =
identity>
735 requires indirectly_writable<_Out,
736 indirect_result_t<_Fp&,
737 projected<_Iter1, _Proj1>,
738 projected<_Iter2, _Proj2>>>
739 constexpr binary_transform_result<_Iter1, _Iter2, _Out>
740 operator()(_Iter1 __first1, _Sent1 __last1,
741 _Iter2 __first2, _Sent2 __last2,
742 _Out __result, _Fp __binary_op,
743 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
745 for (; __first1 != __last1 && __first2 != __last2;
746 ++__first1, (void)++__first2, ++__result)
753 template<input_range _Range1, input_range _Range2,
754 weakly_incrementable _Out, copy_constructible _Fp,
755 typename _Proj1 = identity,
typename _Proj2 = identity>
756 requires indirectly_writable<_Out,
757 indirect_result_t<_Fp&,
758 projected<iterator_t<_Range1>, _Proj1>,
759 projected<iterator_t<_Range2>, _Proj2>>>
760 constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
761 borrowed_iterator_t<_Range2>, _Out>
762 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
763 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
765 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
766 ranges::begin(__r2), ranges::end(__r2),
772 inline constexpr __transform_fn transform{};
776 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
777 typename _Tp1,
typename _Tp2,
typename _Proj =
identity>
778 requires indirectly_writable<_Iter, const _Tp2&>
779 && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
782 operator()(_Iter __first, _Sent __last,
783 const _Tp1& __old_value,
const _Tp2& __new_value,
784 _Proj __proj = {})
const
786 for (; __first != __last; ++__first)
788 *__first = __new_value;
792 template<input_range _Range,
793 typename _Tp1,
typename _Tp2,
typename _Proj = identity>
794 requires indirectly_writable<iterator_t<_Range>,
const _Tp2&>
795 && indirect_binary_predicate<ranges::equal_to,
796 projected<iterator_t<_Range>, _Proj>,
798 constexpr borrowed_iterator_t<_Range>
799 operator()(_Range&& __r,
800 const _Tp1& __old_value,
const _Tp2& __new_value,
801 _Proj __proj = {})
const
803 return (*
this)(ranges::begin(__r), ranges::end(__r),
804 __old_value, __new_value,
std::move(__proj));
808 inline constexpr __replace_fn replace{};
810 struct __replace_if_fn
812 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
813 typename _Tp,
typename _Proj =
identity,
814 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
815 requires indirectly_writable<_Iter, const _Tp&>
817 operator()(_Iter __first, _Sent __last,
818 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
820 for (; __first != __last; ++__first)
822 *__first = __new_value;
826 template<input_range _Range,
typename _Tp,
typename _Proj = identity,
827 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
829 requires indirectly_writable<iterator_t<_Range>,
const _Tp&>
830 constexpr borrowed_iterator_t<_Range>
831 operator()(_Range&& __r,
832 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
834 return (*
this)(ranges::begin(__r), ranges::end(__r),
839 inline constexpr __replace_if_fn replace_if{};
841 template<
typename _Iter,
typename _Out>
842 using replace_copy_result = in_out_result<_Iter, _Out>;
844 struct __replace_copy_fn
846 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
847 typename _Tp1,
typename _Tp2, output_iterator<const _Tp2&> _Out,
848 typename _Proj =
identity>
849 requires indirectly_copyable<_Iter, _Out>
850 && indirect_binary_predicate<ranges::equal_to,
851 projected<_Iter, _Proj>,
const _Tp1*>
852 constexpr replace_copy_result<_Iter, _Out>
853 operator()(_Iter __first, _Sent __last, _Out __result,
854 const _Tp1& __old_value,
const _Tp2& __new_value,
855 _Proj __proj = {})
const
857 for (; __first != __last; ++__first, (void)++__result)
859 *__result = __new_value;
861 *__result = *__first;
865 template<input_range _Range,
typename _Tp1,
typename _Tp2,
866 output_iterator<const _Tp2&> _Out,
typename _Proj = identity>
867 requires indirectly_copyable<iterator_t<_Range>, _Out>
868 && indirect_binary_predicate<ranges::equal_to,
869 projected<iterator_t<_Range>, _Proj>,
871 constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
872 operator()(_Range&& __r, _Out __result,
873 const _Tp1& __old_value,
const _Tp2& __new_value,
874 _Proj __proj = {})
const
876 return (*
this)(ranges::begin(__r), ranges::end(__r),
882 inline constexpr __replace_copy_fn replace_copy{};
884 template<
typename _Iter,
typename _Out>
885 using replace_copy_if_result = in_out_result<_Iter, _Out>;
887 struct __replace_copy_if_fn
889 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
890 typename _Tp, output_iterator<const _Tp&> _Out,
891 typename _Proj =
identity,
892 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
893 requires indirectly_copyable<_Iter, _Out>
894 constexpr replace_copy_if_result<_Iter, _Out>
895 operator()(_Iter __first, _Sent __last, _Out __result,
896 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
898 for (; __first != __last; ++__first, (void)++__result)
900 *__result = __new_value;
902 *__result = *__first;
906 template<input_range _Range,
907 typename _Tp, output_iterator<const _Tp&> _Out,
908 typename _Proj = identity,
909 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
911 requires indirectly_copyable<iterator_t<_Range>, _Out>
912 constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
913 operator()(_Range&& __r, _Out __result,
914 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
916 return (*
this)(ranges::begin(__r), ranges::end(__r),
922 inline constexpr __replace_copy_if_fn replace_copy_if{};
924 struct __generate_n_fn
926 template<input_or_output_iterator _Out, copy_constructible _Fp>
927 requires invocable<_Fp&>
928 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
930 operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen)
const
932 for (; __n > 0; --__n, (void)++__first)
938 inline constexpr __generate_n_fn generate_n{};
942 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
943 copy_constructible _Fp>
944 requires invocable<_Fp&>
945 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
947 operator()(_Out __first, _Sent __last, _Fp __gen)
const
949 for (; __first != __last; ++__first)
954 template<
typename _Range, copy_constructible _Fp>
955 requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
956 constexpr borrowed_iterator_t<_Range>
957 operator()(_Range&& __r, _Fp __gen)
const
959 return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__gen));
963 inline constexpr __generate_fn generate{};
965 struct __remove_if_fn
967 template<permutable _Iter, sentinel_for<_Iter> _Sent,
968 typename _Proj =
identity,
969 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
970 constexpr subrange<_Iter>
971 operator()(_Iter __first, _Sent __last,
972 _Pred __pred, _Proj __proj = {})
const
974 __first = ranges::find_if(__first, __last, __pred, __proj);
975 if (__first == __last)
976 return {__first, __first};
978 auto __result = __first;
980 for (; __first != __last; ++__first)
987 return {__result, __first};
990 template<forward_range _Range,
typename _Proj = identity,
991 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
993 requires permutable<iterator_t<_Range>>
994 constexpr borrowed_subrange_t<_Range>
995 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
997 return (*
this)(ranges::begin(__r), ranges::end(__r),
1002 inline constexpr __remove_if_fn remove_if{};
1006 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1007 typename _Tp,
typename _Proj =
identity>
1008 requires indirect_binary_predicate<ranges::equal_to,
1009 projected<_Iter, _Proj>,
1011 constexpr subrange<_Iter>
1012 operator()(_Iter __first, _Sent __last,
1013 const _Tp& __value, _Proj __proj = {})
const
1015 auto __pred = [&] (
auto&& __arg) ->
bool {
1018 return ranges::remove_if(__first, __last,
1022 template<forward_range _Range,
typename _Tp,
typename _Proj =
identity>
1023 requires permutable<iterator_t<_Range>>
1024 && indirect_binary_predicate<ranges::equal_to,
1025 projected<iterator_t<_Range>, _Proj>,
1027 constexpr borrowed_subrange_t<_Range>
1028 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
1030 return (*
this)(ranges::begin(__r), ranges::end(__r),
1035 inline constexpr __remove_fn remove{};
1037 template<
typename _Iter,
typename _Out>
1038 using remove_copy_if_result = in_out_result<_Iter, _Out>;
1040 struct __remove_copy_if_fn
1042 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1043 weakly_incrementable _Out,
typename _Proj =
identity,
1044 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1045 requires indirectly_copyable<_Iter, _Out>
1046 constexpr remove_copy_if_result<_Iter, _Out>
1047 operator()(_Iter __first, _Sent __last, _Out __result,
1048 _Pred __pred, _Proj __proj = {})
const
1050 for (; __first != __last; ++__first)
1053 *__result = *__first;
1059 template<input_range _Range, weakly_incrementable _Out,
1060 typename _Proj = identity,
1061 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1063 requires indirectly_copyable<iterator_t<_Range>, _Out>
1064 constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1065 operator()(_Range&& __r, _Out __result,
1066 _Pred __pred, _Proj __proj = {})
const
1068 return (*
this)(ranges::begin(__r), ranges::end(__r),
1074 inline constexpr __remove_copy_if_fn remove_copy_if{};
1076 template<
typename _Iter,
typename _Out>
1077 using remove_copy_result = in_out_result<_Iter, _Out>;
1079 struct __remove_copy_fn
1081 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1082 weakly_incrementable _Out,
typename _Tp,
typename _Proj =
identity>
1083 requires indirectly_copyable<_Iter, _Out>
1084 && indirect_binary_predicate<ranges::equal_to,
1085 projected<_Iter, _Proj>,
1087 constexpr remove_copy_result<_Iter, _Out>
1088 operator()(_Iter __first, _Sent __last, _Out __result,
1089 const _Tp& __value, _Proj __proj = {})
const
1091 for (; __first != __last; ++__first)
1094 *__result = *__first;
1100 template<input_range _Range, weakly_incrementable _Out,
1101 typename _Tp,
typename _Proj = identity>
1102 requires indirectly_copyable<iterator_t<_Range>, _Out>
1103 && indirect_binary_predicate<ranges::equal_to,
1104 projected<iterator_t<_Range>, _Proj>,
1106 constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
1107 operator()(_Range&& __r, _Out __result,
1108 const _Tp& __value, _Proj __proj = {})
const
1110 return (*
this)(ranges::begin(__r), ranges::end(__r),
1115 inline constexpr __remove_copy_fn remove_copy{};
1119 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1120 typename _Proj =
identity,
1121 indirect_equivalence_relation<
1122 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1123 constexpr subrange<_Iter>
1124 operator()(_Iter __first, _Sent __last,
1125 _Comp __comp = {}, _Proj __proj = {})
const
1127 __first = ranges::adjacent_find(__first, __last, __comp, __proj);
1128 if (__first == __last)
1129 return {__first, __first};
1131 auto __dest = __first;
1133 while (++__first != __last)
1138 return {++__dest, __first};
1141 template<forward_range _Range,
typename _Proj = identity,
1142 indirect_equivalence_relation<
1143 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1144 requires permutable<iterator_t<_Range>>
1145 constexpr borrowed_subrange_t<_Range>
1146 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1148 return (*
this)(ranges::begin(__r), ranges::end(__r),
1153 inline constexpr __unique_fn unique{};
1157 template<
typename _Out,
typename _Tp>
1158 concept __can_reread_output = input_iterator<_Out>
1159 && same_as<_Tp, iter_value_t<_Out>>;
1162 template<
typename _Iter,
typename _Out>
1163 using unique_copy_result = in_out_result<_Iter, _Out>;
1165 struct __unique_copy_fn
1167 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1168 weakly_incrementable _Out,
typename _Proj =
identity,
1169 indirect_equivalence_relation<
1170 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1171 requires indirectly_copyable<_Iter, _Out>
1172 && (forward_iterator<_Iter>
1173 || __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
1174 || indirectly_copyable_storable<_Iter, _Out>)
1175 constexpr unique_copy_result<_Iter, _Out>
1176 operator()(_Iter __first, _Sent __last, _Out __result,
1177 _Comp __comp = {}, _Proj __proj = {})
const
1179 if (__first == __last)
1183 if constexpr (forward_iterator<_Iter>)
1185 auto __next = __first;
1186 *__result = *__next;
1187 while (++__next != __last)
1193 *++__result = *__first;
1197 else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
1199 *__result = *__first;
1200 while (++__first != __last)
1204 *++__result = *__first;
1209 auto __value = *__first;
1210 *__result = __value;
1211 while (++__first != __last)
1218 *++__result = __value;
1225 template<input_range _Range,
1226 weakly_incrementable _Out,
typename _Proj = identity,
1227 indirect_equivalence_relation<
1228 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1229 requires indirectly_copyable<iterator_t<_Range>, _Out>
1230 && (forward_iterator<iterator_t<_Range>>
1231 || __detail::__can_reread_output<_Out, range_value_t<_Range>>
1232 || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1233 constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1234 operator()(_Range&& __r, _Out __result,
1235 _Comp __comp = {}, _Proj __proj = {})
const
1237 return (*
this)(ranges::begin(__r), ranges::end(__r),
1243 inline constexpr __unique_copy_fn unique_copy{};
1247 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1248 requires permutable<_Iter>
1250 operator()(_Iter __first, _Sent __last)
const
1252 auto __i = ranges::next(__first, __last);
1255 if constexpr (random_access_iterator<_Iter>)
1257 if (__first != __last)
1260 while (__first < __tail)
1262 ranges::iter_swap(__first, __tail);
1272 if (__first == __tail || __first == --__tail)
1276 ranges::iter_swap(__first, __tail);
1283 template<b
idirectional_range _Range>
1284 requires permutable<iterator_t<_Range>>
1285 constexpr borrowed_iterator_t<_Range>
1286 operator()(_Range&& __r)
const
1288 return (*
this)(ranges::begin(__r), ranges::end(__r));
1292 inline constexpr __reverse_fn reverse{};
1294 template<
typename _Iter,
typename _Out>
1295 using reverse_copy_result = in_out_result<_Iter, _Out>;
1297 struct __reverse_copy_fn
1299 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1300 weakly_incrementable _Out>
1301 requires indirectly_copyable<_Iter, _Out>
1302 constexpr reverse_copy_result<_Iter, _Out>
1303 operator()(_Iter __first, _Sent __last, _Out __result)
const
1305 auto __i = ranges::next(__first, __last);
1307 while (__first != __tail)
1310 *__result = *__tail;
1316 template<b
idirectional_range _Range, weakly_incrementable _Out>
1317 requires indirectly_copyable<iterator_t<_Range>, _Out>
1318 constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1319 operator()(_Range&& __r, _Out __result)
const
1321 return (*
this)(ranges::begin(__r), ranges::end(__r),
1326 inline constexpr __reverse_copy_fn reverse_copy{};
1330 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1331 constexpr subrange<_Iter>
1332 operator()(_Iter __first, _Iter __middle, _Sent __last)
const
1334 auto __lasti = ranges::next(__first, __last);
1335 if (__first == __middle)
1336 return {__lasti, __lasti};
1337 if (__last == __middle)
1340 if constexpr (random_access_iterator<_Iter>)
1342 auto __n = __lasti - __first;
1343 auto __k = __middle - __first;
1345 if (__k == __n - __k)
1347 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1352 auto __ret = __first + (__lasti - __middle);
1356 if (__k < __n - __k)
1360 if constexpr (__is_pod(iter_value_t<_Iter>))
1364 ranges::move(__p + 1, __p + __n, __p);
1368 auto __q = __p + __k;
1369 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1371 ranges::iter_swap(__p, __q);
1378 ranges::swap(__n, __k);
1386 if constexpr (__is_pod(iter_value_t<_Iter>))
1390 ranges::move_backward(__p, __p + __n - 1, __p + __n);
1394 auto __q = __p + __n;
1396 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1400 ranges::iter_swap(__p, __q);
1405 std::swap(__n, __k);
1409 else if constexpr (bidirectional_iterator<_Iter>)
1411 auto __tail = __lasti;
1413 ranges::reverse(__first, __middle);
1414 ranges::reverse(__middle, __tail);
1416 while (__first != __middle && __middle != __tail)
1418 ranges::iter_swap(__first, --__tail);
1422 if (__first == __middle)
1424 ranges::reverse(__middle, __tail);
1429 ranges::reverse(__first, __middle);
1435 auto __first2 = __middle;
1438 ranges::iter_swap(__first, __first2);
1441 if (__first == __middle)
1442 __middle = __first2;
1443 }
while (__first2 != __last);
1445 auto __ret = __first;
1447 __first2 = __middle;
1449 while (__first2 != __last)
1451 ranges::iter_swap(__first, __first2);
1454 if (__first == __middle)
1455 __middle = __first2;
1456 else if (__first2 == __last)
1457 __first2 = __middle;
1463 template<forward_range _Range>
1464 requires permutable<iterator_t<_Range>>
1465 constexpr borrowed_subrange_t<_Range>
1466 operator()(_Range&& __r, iterator_t<_Range> __middle)
const
1468 return (*
this)(ranges::begin(__r),
std::move(__middle),
1473 inline constexpr __rotate_fn rotate{};
1475 template<
typename _Iter,
typename _Out>
1476 using rotate_copy_result = in_out_result<_Iter, _Out>;
1478 struct __rotate_copy_fn
1480 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1481 weakly_incrementable _Out>
1482 requires indirectly_copyable<_Iter, _Out>
1483 constexpr rotate_copy_result<_Iter, _Out>
1484 operator()(_Iter __first, _Iter __middle, _Sent __last,
1485 _Out __result)
const
1487 auto __copy1 = ranges::copy(__middle,
1490 auto __copy2 = ranges::copy(
std::move(__first),
1496 template<forward_range _Range, weakly_incrementable _Out>
1497 requires indirectly_copyable<iterator_t<_Range>, _Out>
1498 constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1499 operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result)
const
1501 return (*
this)(ranges::begin(__r),
std::move(__middle),
1506 inline constexpr __rotate_copy_fn rotate_copy{};
1510 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1511 weakly_incrementable _Out,
typename _Gen>
1512 requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
1513 && indirectly_copyable<_Iter, _Out>
1516 operator()(_Iter __first, _Sent __last, _Out __out,
1517 iter_difference_t<_Iter> __n, _Gen&& __g)
const
1519 if constexpr (forward_iterator<_Iter>)
1523 auto __lasti = ranges::next(__first, __last);
1524 return _GLIBCXX_STD_A::
1530 using __distrib_type
1531 = uniform_int_distribution<iter_difference_t<_Iter>>;
1532 using __param_type =
typename __distrib_type::param_type;
1533 __distrib_type __d{};
1534 iter_difference_t<_Iter> __sample_sz = 0;
1535 while (__first != __last && __sample_sz != __n)
1537 __out[__sample_sz++] = *__first;
1540 for (
auto __pop_sz = __sample_sz; __first != __last;
1541 ++__first, (void) ++__pop_sz)
1543 const auto __k = __d(__g, __param_type{0, __pop_sz});
1545 __out[__k] = *__first;
1547 return __out + __sample_sz;
1551 template<input_range _Range, weakly_incrementable _Out,
typename _Gen>
1552 requires (forward_range<_Range> || random_access_iterator<_Out>)
1553 && indirectly_copyable<iterator_t<_Range>, _Out>
1556 operator()(_Range&& __r, _Out __out,
1557 range_difference_t<_Range> __n, _Gen&& __g)
const
1559 return (*
this)(ranges::begin(__r), ranges::end(__r),
1565 inline constexpr __sample_fn sample{};
1569 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1571 requires permutable<_Iter>
1572 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1574 operator()(_Iter __first, _Sent __last, _Gen&& __g)
const
1576 auto __lasti = ranges::next(__first, __last);
1581 template<random_access_range _Range,
typename _Gen>
1582 requires permutable<iterator_t<_Range>>
1583 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1584 borrowed_iterator_t<_Range>
1585 operator()(_Range&& __r, _Gen&& __g)
const
1587 return (*
this)(ranges::begin(__r), ranges::end(__r),
1592 inline constexpr __shuffle_fn shuffle{};
1594 struct __push_heap_fn
1596 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1597 typename _Comp = ranges::less,
typename _Proj =
identity>
1598 requires sortable<_Iter, _Comp, _Proj>
1600 operator()(_Iter __first, _Sent __last,
1601 _Comp __comp = {}, _Proj __proj = {})
const
1603 auto __lasti = ranges::next(__first, __last);
1604 std::push_heap(__first, __lasti,
1605 __detail::__make_comp_proj(__comp, __proj));
1609 template<random_access_range _Range,
1610 typename _Comp = ranges::less,
typename _Proj = identity>
1611 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1612 constexpr borrowed_iterator_t<_Range>
1613 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1615 return (*
this)(ranges::begin(__r), ranges::end(__r),
1620 inline constexpr __push_heap_fn push_heap{};
1622 struct __pop_heap_fn
1624 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1625 typename _Comp = ranges::less,
typename _Proj =
identity>
1626 requires sortable<_Iter, _Comp, _Proj>
1628 operator()(_Iter __first, _Sent __last,
1629 _Comp __comp = {}, _Proj __proj = {})
const
1631 auto __lasti = ranges::next(__first, __last);
1632 std::pop_heap(__first, __lasti,
1633 __detail::__make_comp_proj(__comp, __proj));
1637 template<random_access_range _Range,
1638 typename _Comp = ranges::less,
typename _Proj = identity>
1639 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1640 constexpr borrowed_iterator_t<_Range>
1641 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1643 return (*
this)(ranges::begin(__r), ranges::end(__r),
1648 inline constexpr __pop_heap_fn pop_heap{};
1650 struct __make_heap_fn
1652 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1653 typename _Comp = ranges::less,
typename _Proj =
identity>
1654 requires sortable<_Iter, _Comp, _Proj>
1656 operator()(_Iter __first, _Sent __last,
1657 _Comp __comp = {}, _Proj __proj = {})
const
1659 auto __lasti = ranges::next(__first, __last);
1660 std::make_heap(__first, __lasti,
1661 __detail::__make_comp_proj(__comp, __proj));
1665 template<random_access_range _Range,
1666 typename _Comp = ranges::less,
typename _Proj = identity>
1667 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1668 constexpr borrowed_iterator_t<_Range>
1669 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1671 return (*
this)(ranges::begin(__r), ranges::end(__r),
1676 inline constexpr __make_heap_fn make_heap{};
1678 struct __sort_heap_fn
1680 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1681 typename _Comp = ranges::less,
typename _Proj =
identity>
1682 requires sortable<_Iter, _Comp, _Proj>
1684 operator()(_Iter __first, _Sent __last,
1685 _Comp __comp = {}, _Proj __proj = {})
const
1687 auto __lasti = ranges::next(__first, __last);
1688 std::sort_heap(__first, __lasti,
1689 __detail::__make_comp_proj(__comp, __proj));
1693 template<random_access_range _Range,
1694 typename _Comp = ranges::less,
typename _Proj = identity>
1695 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1696 constexpr borrowed_iterator_t<_Range>
1697 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1699 return (*
this)(ranges::begin(__r), ranges::end(__r),
1704 inline constexpr __sort_heap_fn sort_heap{};
1706 struct __is_heap_until_fn
1708 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1709 typename _Proj =
identity,
1710 indirect_strict_weak_order<projected<_Iter, _Proj>>
1711 _Comp = ranges::less>
1713 operator()(_Iter __first, _Sent __last,
1714 _Comp __comp = {}, _Proj __proj = {})
const
1716 iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
1717 iter_difference_t<_Iter> __parent = 0, __child = 1;
1718 for (; __child < __n; ++__child)
1722 return __first + __child;
1723 else if ((__child & 1) == 0)
1726 return __first + __n;
1729 template<random_access_range _Range,
1730 typename _Proj = identity,
1731 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1732 _Comp = ranges::less>
1733 constexpr borrowed_iterator_t<_Range>
1734 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1736 return (*
this)(ranges::begin(__r), ranges::end(__r),
1741 inline constexpr __is_heap_until_fn is_heap_until{};
1745 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1746 typename _Proj =
identity,
1747 indirect_strict_weak_order<projected<_Iter, _Proj>>
1748 _Comp = ranges::less>
1750 operator()(_Iter __first, _Sent __last,
1751 _Comp __comp = {}, _Proj __proj = {})
const
1754 == ranges::is_heap_until(__first, __last,
1759 template<random_access_range _Range,
1760 typename _Proj = identity,
1761 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1762 _Comp = ranges::less>
1764 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1766 return (*
this)(ranges::begin(__r), ranges::end(__r),
1771 inline constexpr __is_heap_fn is_heap{};
1775 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1776 typename _Comp = ranges::less,
typename _Proj =
identity>
1777 requires sortable<_Iter, _Comp, _Proj>
1779 operator()(_Iter __first, _Sent __last,
1780 _Comp __comp = {}, _Proj __proj = {})
const
1782 auto __lasti = ranges::next(__first, __last);
1783 _GLIBCXX_STD_A::sort(
std::move(__first), __lasti,
1784 __detail::__make_comp_proj(__comp, __proj));
1788 template<random_access_range _Range,
1789 typename _Comp = ranges::less,
typename _Proj = identity>
1790 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1791 constexpr borrowed_iterator_t<_Range>
1792 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1794 return (*
this)(ranges::begin(__r), ranges::end(__r),
1799 inline constexpr __sort_fn sort{};
1801 struct __stable_sort_fn
1803 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1804 typename _Comp = ranges::less,
typename _Proj =
identity>
1805 requires sortable<_Iter, _Comp, _Proj>
1807 operator()(_Iter __first, _Sent __last,
1808 _Comp __comp = {}, _Proj __proj = {})
const
1810 auto __lasti = ranges::next(__first, __last);
1811 std::stable_sort(
std::move(__first), __lasti,
1812 __detail::__make_comp_proj(__comp, __proj));
1816 template<random_access_range _Range,
1817 typename _Comp = ranges::less,
typename _Proj = identity>
1818 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1819 borrowed_iterator_t<_Range>
1820 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1822 return (*
this)(ranges::begin(__r), ranges::end(__r),
1827 inline constexpr __stable_sort_fn stable_sort{};
1829 struct __partial_sort_fn
1831 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1832 typename _Comp = ranges::less,
typename _Proj =
identity>
1833 requires sortable<_Iter, _Comp, _Proj>
1835 operator()(_Iter __first, _Iter __middle, _Sent __last,
1836 _Comp __comp = {}, _Proj __proj = {})
const
1838 if (__first == __middle)
1839 return ranges::next(__first, __last);
1841 ranges::make_heap(__first, __middle, __comp, __proj);
1842 auto __i = __middle;
1843 for (; __i != __last; ++__i)
1848 ranges::pop_heap(__first, __middle, __comp, __proj);
1849 ranges::iter_swap(__middle-1, __i);
1850 ranges::push_heap(__first, __middle, __comp, __proj);
1852 ranges::sort_heap(__first, __middle, __comp, __proj);
1857 template<random_access_range _Range,
1858 typename _Comp = ranges::less,
typename _Proj = identity>
1859 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1860 constexpr borrowed_iterator_t<_Range>
1861 operator()(_Range&& __r, iterator_t<_Range> __middle,
1862 _Comp __comp = {}, _Proj __proj = {})
const
1864 return (*
this)(ranges::begin(__r),
std::move(__middle),
1870 inline constexpr __partial_sort_fn partial_sort{};
1872 template<
typename _Iter,
typename _Out>
1873 using partial_sort_copy_result = in_out_result<_Iter, _Out>;
1875 struct __partial_sort_copy_fn
1877 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1878 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1879 typename _Comp = ranges::less,
1880 typename _Proj1 =
identity,
typename _Proj2 =
identity>
1881 requires indirectly_copyable<_Iter1, _Iter2>
1882 && sortable<_Iter2, _Comp, _Proj2>
1883 && indirect_strict_weak_order<_Comp,
1884 projected<_Iter1, _Proj1>,
1885 projected<_Iter2, _Proj2>>
1886 constexpr partial_sort_copy_result<_Iter1, _Iter2>
1887 operator()(_Iter1 __first, _Sent1 __last,
1888 _Iter2 __result_first, _Sent2 __result_last,
1890 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1892 if (__result_first == __result_last)
1895 auto __lasti = ranges::next(
std::move(__first),
1900 auto __result_real_last = __result_first;
1901 while (__first != __last && __result_real_last != __result_last)
1903 *__result_real_last = *__first;
1904 ++__result_real_last;
1908 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
1909 for (; __first != __last; ++__first)
1914 ranges::pop_heap(__result_first, __result_real_last,
1916 *(__result_real_last-1) = *__first;
1917 ranges::push_heap(__result_first, __result_real_last,
1920 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
1925 template<input_range _Range1, random_access_range _Range2,
1926 typename _Comp = ranges::less,
1927 typename _Proj1 = identity,
typename _Proj2 = identity>
1928 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
1929 && sortable<iterator_t<_Range2>, _Comp, _Proj2>
1930 && indirect_strict_weak_order<_Comp,
1931 projected<iterator_t<_Range1>, _Proj1>,
1932 projected<iterator_t<_Range2>, _Proj2>>
1933 constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
1934 borrowed_iterator_t<_Range2>>
1935 operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
1936 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1938 return (*
this)(ranges::begin(__r), ranges::end(__r),
1939 ranges::begin(__out), ranges::end(__out),
1945 inline constexpr __partial_sort_copy_fn partial_sort_copy{};
1947 struct __is_sorted_until_fn
1949 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1950 typename _Proj =
identity,
1951 indirect_strict_weak_order<projected<_Iter, _Proj>>
1952 _Comp = ranges::less>
1954 operator()(_Iter __first, _Sent __last,
1955 _Comp __comp = {}, _Proj __proj = {})
const
1957 if (__first == __last)
1960 auto __next = __first;
1961 for (++__next; __next != __last; __first = __next, (void)++__next)
1969 template<forward_range _Range,
typename _Proj = identity,
1970 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1971 _Comp = ranges::less>
1972 constexpr borrowed_iterator_t<_Range>
1973 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1975 return (*
this)(ranges::begin(__r), ranges::end(__r),
1980 inline constexpr __is_sorted_until_fn is_sorted_until{};
1982 struct __is_sorted_fn
1984 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1985 typename _Proj =
identity,
1986 indirect_strict_weak_order<projected<_Iter, _Proj>>
1987 _Comp = ranges::less>
1989 operator()(_Iter __first, _Sent __last,
1990 _Comp __comp = {}, _Proj __proj = {})
const
1992 if (__first == __last)
1995 auto __next = __first;
1996 for (++__next; __next != __last; __first = __next, (void)++__next)
2004 template<forward_range _Range,
typename _Proj = identity,
2005 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2006 _Comp = ranges::less>
2008 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2010 return (*
this)(ranges::begin(__r), ranges::end(__r),
2015 inline constexpr __is_sorted_fn is_sorted{};
2017 struct __nth_element_fn
2019 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2020 typename _Comp = ranges::less,
typename _Proj =
identity>
2021 requires sortable<_Iter, _Comp, _Proj>
2023 operator()(_Iter __first, _Iter __nth, _Sent __last,
2024 _Comp __comp = {}, _Proj __proj = {})
const
2026 auto __lasti = ranges::next(__first, __last);
2029 __detail::__make_comp_proj(__comp, __proj));
2033 template<random_access_range _Range,
2034 typename _Comp = ranges::less,
typename _Proj = identity>
2035 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2036 constexpr borrowed_iterator_t<_Range>
2037 operator()(_Range&& __r, iterator_t<_Range> __nth,
2038 _Comp __comp = {}, _Proj __proj = {})
const
2040 return (*
this)(ranges::begin(__r),
std::move(__nth),
2045 inline constexpr __nth_element_fn nth_element{};
2047 struct __lower_bound_fn
2049 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2050 typename _Tp,
typename _Proj =
identity,
2051 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2052 _Comp = ranges::less>
2054 operator()(_Iter __first, _Sent __last,
2055 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2057 auto __len = ranges::distance(__first, __last);
2061 auto __half = __len / 2;
2062 auto __middle = __first;
2063 ranges::advance(__middle, __half);
2068 __len = __len - __half - 1;
2076 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2077 indirect_strict_weak_order<
const _Tp*,
2078 projected<iterator_t<_Range>, _Proj>>
2079 _Comp = ranges::less>
2080 constexpr borrowed_iterator_t<_Range>
2081 operator()(_Range&& __r,
2082 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2084 return (*
this)(ranges::begin(__r), ranges::end(__r),
2089 inline constexpr __lower_bound_fn lower_bound{};
2091 struct __upper_bound_fn
2093 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2094 typename _Tp,
typename _Proj =
identity,
2095 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2096 _Comp = ranges::less>
2098 operator()(_Iter __first, _Sent __last,
2099 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2101 auto __len = ranges::distance(__first, __last);
2105 auto __half = __len / 2;
2106 auto __middle = __first;
2107 ranges::advance(__middle, __half);
2114 __len = __len - __half - 1;
2120 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2121 indirect_strict_weak_order<
const _Tp*,
2122 projected<iterator_t<_Range>, _Proj>>
2123 _Comp = ranges::less>
2124 constexpr borrowed_iterator_t<_Range>
2125 operator()(_Range&& __r,
2126 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2128 return (*
this)(ranges::begin(__r), ranges::end(__r),
2133 inline constexpr __upper_bound_fn upper_bound{};
2135 struct __equal_range_fn
2137 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2138 typename _Tp,
typename _Proj =
identity,
2139 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2140 _Comp = ranges::less>
2141 constexpr subrange<_Iter>
2142 operator()(_Iter __first, _Sent __last,
2143 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2145 auto __len = ranges::distance(__first, __last);
2149 auto __half = __len / 2;
2150 auto __middle = __first;
2151 ranges::advance(__middle, __half);
2158 __len = __len - __half - 1;
2167 = ranges::lower_bound(__first, __middle,
2168 __value, __comp, __proj);
2169 ranges::advance(__first, __len);
2171 = ranges::upper_bound(++__middle, __first,
2172 __value, __comp, __proj);
2173 return {__left, __right};
2176 return {__first, __first};
2179 template<forward_range _Range,
2180 typename _Tp,
typename _Proj = identity,
2181 indirect_strict_weak_order<
const _Tp*,
2182 projected<iterator_t<_Range>, _Proj>>
2183 _Comp = ranges::less>
2184 constexpr borrowed_subrange_t<_Range>
2185 operator()(_Range&& __r,
const _Tp& __value,
2186 _Comp __comp = {}, _Proj __proj = {})
const
2188 return (*
this)(ranges::begin(__r), ranges::end(__r),
2193 inline constexpr __equal_range_fn equal_range{};
2195 struct __binary_search_fn
2197 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2198 typename _Tp,
typename _Proj =
identity,
2199 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2200 _Comp = ranges::less>
2202 operator()(_Iter __first, _Sent __last,
2203 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2205 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2212 template<forward_range _Range,
2213 typename _Tp,
typename _Proj = identity,
2214 indirect_strict_weak_order<
const _Tp*,
2215 projected<iterator_t<_Range>, _Proj>>
2216 _Comp = ranges::less>
2218 operator()(_Range&& __r,
const _Tp& __value, _Comp __comp = {},
2219 _Proj __proj = {})
const
2221 return (*
this)(ranges::begin(__r), ranges::end(__r),
2226 inline constexpr __binary_search_fn binary_search{};
2228 struct __is_partitioned_fn
2230 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2231 typename _Proj =
identity,
2232 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2234 operator()(_Iter __first, _Sent __last,
2235 _Pred __pred, _Proj __proj = {})
const
2237 __first = ranges::find_if_not(
std::move(__first), __last,
2239 if (__first == __last)
2246 template<input_range _Range,
typename _Proj = identity,
2247 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2250 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2252 return (*
this)(ranges::begin(__r), ranges::end(__r),
2257 inline constexpr __is_partitioned_fn is_partitioned{};
2259 struct __partition_fn
2261 template<permutable _Iter, sentinel_for<_Iter> _Sent,
2262 typename _Proj =
identity,
2263 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2264 constexpr subrange<_Iter>
2265 operator()(_Iter __first, _Sent __last,
2266 _Pred __pred, _Proj __proj = {})
const
2268 if constexpr (bidirectional_iterator<_Iter>)
2270 auto __lasti = ranges::next(__first, __last);
2271 auto __tail = __lasti;
2275 if (__first == __tail)
2284 if (__first == __tail)
2291 ranges::iter_swap(__first, __tail);
2297 if (__first == __last)
2298 return {__first, __first};
2301 if (++__first == __last)
2302 return {__first, __first};
2304 auto __next = __first;
2305 while (++__next != __last)
2308 ranges::iter_swap(__first, __next);
2316 template<forward_range _Range,
typename _Proj = identity,
2317 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2319 requires permutable<iterator_t<_Range>>
2320 constexpr borrowed_subrange_t<_Range>
2321 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2323 return (*
this)(ranges::begin(__r), ranges::end(__r),
2328 inline constexpr __partition_fn partition{};
2331 struct __stable_partition_fn
2333 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2334 typename _Proj =
identity,
2335 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2336 requires permutable<_Iter>
2338 operator()(_Iter __first, _Sent __last,
2339 _Pred __pred, _Proj __proj = {})
const
2341 auto __lasti = ranges::next(__first, __last);
2343 = std::stable_partition(
std::move(__first), __lasti,
2344 __detail::__make_pred_proj(__pred, __proj));
2348 template<bidirectional_range _Range,
typename _Proj = identity,
2349 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2351 requires permutable<iterator_t<_Range>>
2352 borrowed_subrange_t<_Range>
2353 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2355 return (*
this)(ranges::begin(__r), ranges::end(__r),
2360 inline constexpr __stable_partition_fn stable_partition{};
2363 template<
typename _Iter,
typename _Out1,
typename _Out2>
2364 struct in_out_out_result
2366 [[no_unique_address]] _Iter in;
2367 [[no_unique_address]] _Out1 out1;
2368 [[no_unique_address]] _Out2 out2;
2370 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2371 requires convertible_to<const _Iter&, _IIter>
2372 && convertible_to<const _Out1&, _OOut1>
2373 && convertible_to<const _Out2&, _OOut2>
2375 operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
2376 {
return {in, out1, out2}; }
2378 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2379 requires convertible_to<_Iter, _IIter>
2380 && convertible_to<_Out1, _OOut1>
2381 && convertible_to<_Out2, _OOut2>
2383 operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2387 template<
typename _Iter,
typename _Out1,
typename _Out2>
2388 using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2390 struct __partition_copy_fn
2392 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2393 weakly_incrementable _Out1, weakly_incrementable _Out2,
2394 typename _Proj =
identity,
2395 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2396 requires indirectly_copyable<_Iter, _Out1>
2397 && indirectly_copyable<_Iter, _Out2>
2398 constexpr partition_copy_result<_Iter, _Out1, _Out2>
2399 operator()(_Iter __first, _Sent __last,
2400 _Out1 __out_true, _Out2 __out_false,
2401 _Pred __pred, _Proj __proj = {})
const
2403 for (; __first != __last; ++__first)
2406 *__out_true = *__first;
2411 *__out_false = *__first;
2419 template<input_range _Range, weakly_incrementable _Out1,
2420 weakly_incrementable _Out2,
2421 typename _Proj = identity,
2422 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2424 requires indirectly_copyable<iterator_t<_Range>, _Out1>
2425 && indirectly_copyable<iterator_t<_Range>, _Out2>
2426 constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2>
2427 operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false,
2428 _Pred __pred, _Proj __proj = {})
const
2430 return (*
this)(ranges::begin(__r), ranges::end(__r),
2436 inline constexpr __partition_copy_fn partition_copy{};
2438 struct __partition_point_fn
2440 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2441 typename _Proj =
identity,
2442 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2444 operator()(_Iter __first, _Sent __last,
2445 _Pred __pred, _Proj __proj = {})
const
2447 auto __len = ranges::distance(__first, __last);
2451 auto __half = __len / 2;
2452 auto __middle = __first;
2453 ranges::advance(__middle, __half);
2458 __len = __len - __half - 1;
2466 template<forward_range _Range,
typename _Proj = identity,
2467 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2469 constexpr borrowed_iterator_t<_Range>
2470 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2472 return (*
this)(ranges::begin(__r), ranges::end(__r),
2477 inline constexpr __partition_point_fn partition_point{};
2479 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2480 using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2484 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2485 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2486 weakly_incrementable _Out,
typename _Comp = ranges::less,
2487 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2488 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2489 constexpr merge_result<_Iter1, _Iter2, _Out>
2490 operator()(_Iter1 __first1, _Sent1 __last1,
2491 _Iter2 __first2, _Sent2 __last2, _Out __result,
2493 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2495 while (__first1 != __last1 && __first2 != __last2)
2501 *__result = *__first2;
2506 *__result = *__first1;
2519 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2520 typename _Comp = ranges::less,
2521 typename _Proj1 = identity,
typename _Proj2 = identity>
2522 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2523 _Comp, _Proj1, _Proj2>
2524 constexpr merge_result<borrowed_iterator_t<_Range1>,
2525 borrowed_iterator_t<_Range2>,
2527 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2529 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2531 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2532 ranges::begin(__r2), ranges::end(__r2),
2538 inline constexpr __merge_fn merge{};
2540 struct __inplace_merge_fn
2542 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2543 typename _Comp = ranges::less,
2544 typename _Proj =
identity>
2545 requires sortable<_Iter, _Comp, _Proj>
2547 operator()(_Iter __first, _Iter __middle, _Sent __last,
2548 _Comp __comp = {}, _Proj __proj = {})
const
2550 auto __lasti = ranges::next(__first, __last);
2552 __detail::__make_comp_proj(__comp, __proj));
2556 template<bidirectional_range _Range,
2557 typename _Comp = ranges::less,
typename _Proj = identity>
2558 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2559 borrowed_iterator_t<_Range>
2560 operator()(_Range&& __r, iterator_t<_Range> __middle,
2561 _Comp __comp = {}, _Proj __proj = {})
const
2563 return (*
this)(ranges::begin(__r),
std::move(__middle),
2569 inline constexpr __inplace_merge_fn inplace_merge{};
2571 struct __includes_fn
2573 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2574 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2575 typename _Proj1 =
identity,
typename _Proj2 =
identity,
2576 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2577 projected<_Iter2, _Proj2>>
2578 _Comp = ranges::less>
2580 operator()(_Iter1 __first1, _Sent1 __last1,
2581 _Iter2 __first2, _Sent2 __last2,
2583 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2585 while (__first1 != __last1 && __first2 != __last2)
2600 return __first2 == __last2;
2603 template<input_range _Range1, input_range _Range2,
2604 typename _Proj1 = identity,
typename _Proj2 = identity,
2605 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2606 projected<iterator_t<_Range2>, _Proj2>>
2607 _Comp = ranges::less>
2609 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2610 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2612 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2613 ranges::begin(__r2), ranges::end(__r2),
2619 inline constexpr __includes_fn includes{};
2621 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2622 using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2624 struct __set_union_fn
2626 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2627 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2628 weakly_incrementable _Out,
typename _Comp = ranges::less,
2629 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2630 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2631 constexpr set_union_result<_Iter1, _Iter2, _Out>
2632 operator()(_Iter1 __first1, _Sent1 __last1,
2633 _Iter2 __first2, _Sent2 __last2,
2634 _Out __result, _Comp __comp = {},
2635 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2637 while (__first1 != __last1 && __first2 != __last2)
2643 *__result = *__first1;
2650 *__result = *__first2;
2655 *__result = *__first1;
2669 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2670 typename _Comp = ranges::less,
2671 typename _Proj1 = identity,
typename _Proj2 = identity>
2672 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2673 _Comp, _Proj1, _Proj2>
2674 constexpr set_union_result<borrowed_iterator_t<_Range1>,
2675 borrowed_iterator_t<_Range2>, _Out>
2676 operator()(_Range1&& __r1, _Range2&& __r2,
2677 _Out __result, _Comp __comp = {},
2678 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2680 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2681 ranges::begin(__r2), ranges::end(__r2),
2687 inline constexpr __set_union_fn set_union{};
2689 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2690 using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2692 struct __set_intersection_fn
2694 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2695 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2696 weakly_incrementable _Out,
typename _Comp = ranges::less,
2697 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2698 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2699 constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2700 operator()(_Iter1 __first1, _Sent1 __last1,
2701 _Iter2 __first2, _Sent2 __last2, _Out __result,
2703 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2705 while (__first1 != __last1 && __first2 != __last2)
2716 *__result = *__first1;
2727 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2728 typename _Comp = ranges::less,
2729 typename _Proj1 = identity,
typename _Proj2 = identity>
2730 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2731 _Comp, _Proj1, _Proj2>
2732 constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
2733 borrowed_iterator_t<_Range2>, _Out>
2734 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2736 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2738 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2739 ranges::begin(__r2), ranges::end(__r2),
2745 inline constexpr __set_intersection_fn set_intersection{};
2747 template<
typename _Iter,
typename _Out>
2748 using set_difference_result = in_out_result<_Iter, _Out>;
2750 struct __set_difference_fn
2752 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2753 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2754 weakly_incrementable _Out,
typename _Comp = ranges::less,
2755 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2756 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2757 constexpr set_difference_result<_Iter1, _Out>
2758 operator()(_Iter1 __first1, _Sent1 __last1,
2759 _Iter2 __first2, _Sent2 __last2, _Out __result,
2761 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2763 while (__first1 != __last1 && __first2 != __last2)
2768 *__result = *__first1;
2785 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2786 typename _Comp = ranges::less,
2787 typename _Proj1 = identity,
typename _Proj2 = identity>
2788 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2789 _Comp, _Proj1, _Proj2>
2790 constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
2791 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2793 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2795 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2796 ranges::begin(__r2), ranges::end(__r2),
2802 inline constexpr __set_difference_fn set_difference{};
2804 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2805 using set_symmetric_difference_result
2806 = in_in_out_result<_Iter1, _Iter2, _Out>;
2808 struct __set_symmetric_difference_fn
2810 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2811 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2812 weakly_incrementable _Out,
typename _Comp = ranges::less,
2813 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2814 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2815 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
2816 operator()(_Iter1 __first1, _Sent1 __last1,
2817 _Iter2 __first2, _Sent2 __last2,
2818 _Out __result, _Comp __comp = {},
2819 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2821 while (__first1 != __last1 && __first2 != __last2)
2826 *__result = *__first1;
2834 *__result = *__first2;
2851 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2852 typename _Comp = ranges::less,
2853 typename _Proj1 = identity,
typename _Proj2 = identity>
2854 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2855 _Comp, _Proj1, _Proj2>
2856 constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
2857 borrowed_iterator_t<_Range2>,
2859 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2861 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2863 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2864 ranges::begin(__r2), ranges::end(__r2),
2870 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
2876 template<
typename _Tp,
typename _Proj = identity,
2877 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2878 _Comp = ranges::less>
2879 constexpr const _Tp&
2880 operator()(
const _Tp& __a,
const _Tp& __b,
2881 _Comp __comp = {}, _Proj __proj = {})
const
2891 template<input_range _Range,
typename _Proj = identity,
2892 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2893 _Comp = ranges::less>
2894 requires indirectly_copyable_storable<iterator_t<_Range>,
2895 range_value_t<_Range>*>
2896 constexpr range_value_t<_Range>
2897 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2899 auto __first = ranges::begin(__r);
2900 auto __last = ranges::end(__r);
2901 __glibcxx_assert(__first != __last);
2902 auto __result = *__first;
2903 while (++__first != __last)
2905 auto __tmp = *__first;
2914 template<copyable _Tp,
typename _Proj = identity,
2915 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2916 _Comp = ranges::less>
2918 operator()(initializer_list<_Tp> __r,
2919 _Comp __comp = {}, _Proj __proj = {})
const
2921 return (*
this)(ranges::subrange(__r),
2926 inline constexpr __max_fn max{};
2930 template<
typename _Tp,
typename _Proj = identity,
2931 indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
2933 constexpr const _Tp&
2934 operator()(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi,
2935 _Comp __comp = {}, _Proj __proj = {})
const
2950 inline constexpr __clamp_fn clamp{};
2952 template<
typename _Tp>
2953 struct min_max_result
2955 [[no_unique_address]] _Tp min;
2956 [[no_unique_address]] _Tp max;
2958 template<
typename _Tp2>
2959 requires convertible_to<const _Tp&, _Tp2>
2961 operator min_max_result<_Tp2>() const &
2962 {
return {min, max}; }
2964 template<
typename _Tp2>
2965 requires convertible_to<_Tp, _Tp2>
2967 operator min_max_result<_Tp2>() &&
2971 template<
typename _Tp>
2972 using minmax_result = min_max_result<_Tp>;
2976 template<
typename _Tp,
typename _Proj = identity,
2977 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2978 _Comp = ranges::less>
2979 constexpr minmax_result<const _Tp&>
2980 operator()(
const _Tp& __a,
const _Tp& __b,
2981 _Comp __comp = {}, _Proj __proj = {})
const
2991 template<input_range _Range,
typename _Proj = identity,
2992 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2993 _Comp = ranges::less>
2994 requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
2995 constexpr minmax_result<range_value_t<_Range>>
2996 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2998 auto __first = ranges::begin(__r);
2999 auto __last = ranges::end(__r);
3000 __glibcxx_assert(__first != __last);
3001 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3002 minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};
3003 if (++__first == __last)
3009 auto&& __val = *__first;
3010 if (__comp_proj(__val, __result.min))
3015 while (++__first != __last)
3020 range_value_t<_Range> __val1 = *__first;
3021 if (++__first == __last)
3026 if (__comp_proj(__val1, __result.min))
3028 else if (!__comp_proj(__val1, __result.max))
3032 auto&& __val2 = *__first;
3033 if (!__comp_proj(__val2, __val1))
3035 if (__comp_proj(__val1, __result.min))
3037 if (!__comp_proj(__val2, __result.max))
3042 if (__comp_proj(__val2, __result.min))
3044 if (!__comp_proj(__val1, __result.max))
3051 template<copyable _Tp,
typename _Proj = identity,
3052 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3053 _Comp = ranges::less>
3054 constexpr minmax_result<_Tp>
3055 operator()(initializer_list<_Tp> __r,
3056 _Comp __comp = {}, _Proj __proj = {})
const
3058 return (*
this)(ranges::subrange(__r),
3063 inline constexpr __minmax_fn minmax{};
3065 struct __min_element_fn
3067 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3068 typename _Proj =
identity,
3069 indirect_strict_weak_order<projected<_Iter, _Proj>>
3070 _Comp = ranges::less>
3072 operator()(_Iter __first, _Sent __last,
3073 _Comp __comp = {}, _Proj __proj = {})
const
3075 if (__first == __last)
3079 while (++__i != __last)
3089 template<forward_range _Range,
typename _Proj = identity,
3090 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3091 _Comp = ranges::less>
3092 constexpr borrowed_iterator_t<_Range>
3093 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3095 return (*
this)(ranges::begin(__r), ranges::end(__r),
3100 inline constexpr __min_element_fn min_element{};
3102 struct __max_element_fn
3104 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3105 typename _Proj =
identity,
3106 indirect_strict_weak_order<projected<_Iter, _Proj>>
3107 _Comp = ranges::less>
3109 operator()(_Iter __first, _Sent __last,
3110 _Comp __comp = {}, _Proj __proj = {})
const
3112 if (__first == __last)
3116 while (++__i != __last)
3126 template<forward_range _Range,
typename _Proj = identity,
3127 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3128 _Comp = ranges::less>
3129 constexpr borrowed_iterator_t<_Range>
3130 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3132 return (*
this)(ranges::begin(__r), ranges::end(__r),
3137 inline constexpr __max_element_fn max_element{};
3139 template<
typename _Iter>
3140 using minmax_element_result = min_max_result<_Iter>;
3142 struct __minmax_element_fn
3144 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3145 typename _Proj =
identity,
3146 indirect_strict_weak_order<projected<_Iter, _Proj>>
3147 _Comp = ranges::less>
3148 constexpr minmax_element_result<_Iter>
3149 operator()(_Iter __first, _Sent __last,
3150 _Comp __comp = {}, _Proj __proj = {})
const
3152 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3153 minmax_element_result<_Iter> __result = {__first, __first};
3154 if (__first == __last || ++__first == __last)
3160 if (__comp_proj(*__first, *__result.min))
3161 __result.min = __first;
3163 __result.max = __first;
3165 while (++__first != __last)
3170 auto __prev = __first;
3171 if (++__first == __last)
3176 if (__comp_proj(*__prev, *__result.min))
3177 __result.min = __prev;
3178 else if (!__comp_proj(*__prev, *__result.max))
3179 __result.max = __prev;
3182 if (!__comp_proj(*__first, *__prev))
3184 if (__comp_proj(*__prev, *__result.min))
3185 __result.min = __prev;
3186 if (!__comp_proj(*__first, *__result.max))
3187 __result.max = __first;
3191 if (__comp_proj(*__first, *__result.min))
3192 __result.min = __first;
3193 if (!__comp_proj(*__prev, *__result.max))
3194 __result.max = __prev;
3200 template<forward_range _Range,
typename _Proj = identity,
3201 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3202 _Comp = ranges::less>
3203 constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3204 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3206 return (*
this)(ranges::begin(__r), ranges::end(__r),
3211 inline constexpr __minmax_element_fn minmax_element{};
3213 struct __lexicographical_compare_fn
3215 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3216 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3217 typename _Proj1 =
identity,
typename _Proj2 =
identity,
3218 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3219 projected<_Iter2, _Proj2>>
3220 _Comp = ranges::less>
3222 operator()(_Iter1 __first1, _Sent1 __last1,
3223 _Iter2 __first2, _Sent2 __last2,
3225 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3227 if constexpr (__detail::__is_normal_iterator<_Iter1>
3228 && same_as<_Iter1, _Sent1>)
3229 return (*
this)(__first1.base(), __last1.base(),
3233 else if constexpr (__detail::__is_normal_iterator<_Iter2>
3234 && same_as<_Iter2, _Sent2>)
3236 __first2.base(), __last2.base(),
3241 constexpr bool __sized_iters
3242 = (sized_sentinel_for<_Sent1, _Iter1>
3243 && sized_sentinel_for<_Sent2, _Iter2>);
3244 if constexpr (__sized_iters)
3246 using _ValueType1 = iter_value_t<_Iter1>;
3247 using _ValueType2 = iter_value_t<_Iter2>;
3250 constexpr bool __use_memcmp
3251 = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3252 && __ptr_to_nonvolatile<_Iter1>
3253 && __ptr_to_nonvolatile<_Iter2>
3254 && (is_same_v<_Comp, ranges::less>
3255 || is_same_v<_Comp, ranges::greater>)
3256 && is_same_v<_Proj1, identity>
3257 && is_same_v<_Proj2, identity>);
3258 if constexpr (__use_memcmp)
3260 const auto __d1 = __last1 - __first1;
3261 const auto __d2 = __last2 - __first2;
3263 if (
const auto __len =
std::min(__d1, __d2))
3266 = std::__memcmp(__first1, __first2, __len);
3267 if constexpr (is_same_v<_Comp, ranges::less>)
3274 else if constexpr (is_same_v<_Comp, ranges::greater>)
3286 for (; __first1 != __last1 && __first2 != __last2;
3287 ++__first1, (void) ++__first2)
3298 return __first1 == __last1 && __first2 != __last2;
3302 template<input_range _Range1, input_range _Range2,
3303 typename _Proj1 = identity,
typename _Proj2 = identity,
3304 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3305 projected<iterator_t<_Range2>, _Proj2>>
3306 _Comp = ranges::less>
3308 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3309 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3311 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
3312 ranges::begin(__r2), ranges::end(__r2),
3318 template<
typename _Iter,
typename _Ref = iter_reference_t<_Iter>>
3319 static constexpr bool __ptr_to_nonvolatile
3320 = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3323 inline constexpr __lexicographical_compare_fn lexicographical_compare;
3325 template<
typename _Iter>
3326 struct in_found_result
3328 [[no_unique_address]] _Iter in;
3331 template<
typename _Iter2>
3332 requires convertible_to<const _Iter&, _Iter2>
3334 operator in_found_result<_Iter2>() const &
3335 {
return {in, found}; }
3337 template<
typename _Iter2>
3338 requires convertible_to<_Iter, _Iter2>
3340 operator in_found_result<_Iter2>() &&
3344 template<
typename _Iter>
3345 using next_permutation_result = in_found_result<_Iter>;
3347 struct __next_permutation_fn
3349 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3350 typename _Comp = ranges::less,
typename _Proj =
identity>
3351 requires sortable<_Iter, _Comp, _Proj>
3352 constexpr next_permutation_result<_Iter>
3353 operator()(_Iter __first, _Sent __last,
3354 _Comp __comp = {}, _Proj __proj = {})
const
3356 if (__first == __last)
3364 auto __lasti = ranges::next(__first, __last);
3381 ranges::iter_swap(__i, __j);
3382 ranges::reverse(__ii, __last);
3387 ranges::reverse(__first, __last);
3393 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3394 typename _Proj = identity>
3395 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3396 constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3397 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3399 return (*
this)(ranges::begin(__r), ranges::end(__r),
3404 inline constexpr __next_permutation_fn next_permutation{};
3406 template<
typename _Iter>
3407 using prev_permutation_result = in_found_result<_Iter>;
3409 struct __prev_permutation_fn
3411 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3412 typename _Comp = ranges::less,
typename _Proj =
identity>
3413 requires sortable<_Iter, _Comp, _Proj>
3414 constexpr prev_permutation_result<_Iter>
3415 operator()(_Iter __first, _Sent __last,
3416 _Comp __comp = {}, _Proj __proj = {})
const
3418 if (__first == __last)
3426 auto __lasti = ranges::next(__first, __last);
3443 ranges::iter_swap(__i, __j);
3444 ranges::reverse(__ii, __last);
3449 ranges::reverse(__first, __last);
3455 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3456 typename _Proj = identity>
3457 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3458 constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3459 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3461 return (*
this)(ranges::begin(__r), ranges::end(__r),
3466 inline constexpr __prev_permutation_fn prev_permutation{};
3468#if __glibcxx_ranges_contains >= 202207L
3469 struct __contains_fn
3471 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3472 typename _Tp,
typename _Proj =
identity>
3473 requires indirect_binary_predicate<ranges::equal_to,
3474 projected<_Iter, _Proj>,
const _Tp*>
3476 operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
const
3477 {
return ranges::find(
std::move(__first), __last, __value,
std::move(__proj)) != __last; }
3479 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
3480 requires indirect_binary_predicate<ranges::equal_to,
3481 projected<iterator_t<_Range>, _Proj>,
const _Tp*>
3483 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
3484 {
return (*
this)(ranges::begin(__r), ranges::end(__r), __value,
std::move(__proj)); }
3487 inline constexpr __contains_fn contains{};
3489 struct __contains_subrange_fn
3491 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3492 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3493 typename _Pred = ranges::equal_to,
3494 typename _Proj1 =
identity,
typename _Proj2 =
identity>
3495 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
3497 operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
3498 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3500 return __first2 == __last2
3501 || !ranges::search(__first1, __last1, __first2, __last2,
3505 template<forward_range _Range1, forward_range _Range2,
3506 typename _Pred = ranges::equal_to,
3507 typename _Proj1 = identity,
typename _Proj2 = identity>
3508 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
3509 _Pred, _Proj1, _Proj2>
3511 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
3512 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3514 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
3515 ranges::begin(__r2), ranges::end(__r2),
3520 inline constexpr __contains_subrange_fn contains_subrange{};
3524#if __glibcxx_ranges_iota >= 202202L
3526 template<
typename _Out,
typename _Tp>
3527 struct out_value_result
3529 [[no_unique_address]] _Out out;
3530 [[no_unique_address]] _Tp value;
3532 template<
typename _Out2,
typename _Tp2>
3533 requires convertible_to<const _Out&, _Out2>
3534 && convertible_to<const _Tp&, _Tp2>
3536 operator out_value_result<_Out2, _Tp2>() const &
3537 {
return {out, value}; }
3539 template<
typename _Out2,
typename _Tp2>
3540 requires convertible_to<_Out, _Out2>
3541 && convertible_to<_Tp, _Tp2>
3543 operator out_value_result<_Out2, _Tp2>() &&
3547 template<
typename _Out,
typename _Tp>
3548 using iota_result = out_value_result<_Out, _Tp>;
3552 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent, weakly_incrementable _Tp>
3553 requires indirectly_writable<_Out, const _Tp&>
3554 constexpr iota_result<_Out, _Tp>
3555 operator()(_Out __first, _Sent __last, _Tp __value)
const
3557 while (__first != __last)
3559 *__first =
static_cast<const _Tp&
>(__value);
3566 template<weakly_incrementable _Tp, output_range<const _Tp&> _Range>
3567 constexpr iota_result<borrowed_iterator_t<_Range>, _Tp>
3568 operator()(_Range&& __r, _Tp __value)
const
3569 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__value)); }
3572 inline constexpr __iota_fn iota{};
3576#if __glibcxx_ranges_find_last >= 202207L
3578 struct __find_last_fn
3580 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
typename _Proj =
identity>
3581 requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
const _Tp*>
3582 constexpr subrange<_Iter>
3583 operator()(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
const
3585 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3587 _Iter __found = ranges::find(reverse_iterator<_Iter>{__last},
3588 reverse_iterator<_Iter>{__first},
3590 if (__found == __first)
3591 return {__last, __last};
3593 return {ranges::prev(__found), __last};
3597 _Iter __found = ranges::find(__first, __last, __value, __proj);
3598 if (__found == __last)
3599 return {__found, __found};
3603 __first = ranges::find(ranges::next(__first), __last, __value, __proj);
3604 if (__first == __last)
3605 return {__found, __first};
3611 template<forward_range _Range,
typename _Tp,
typename _Proj =
identity>
3612 requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>,
const _Tp*>
3613 constexpr borrowed_subrange_t<_Range>
3614 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
3615 {
return (*
this)(ranges::begin(__r), ranges::end(__r), __value,
std::move(__proj)); }
3618 inline constexpr __find_last_fn find_last{};
3620 struct __find_last_if_fn
3622 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Proj =
identity,
3623 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3624 constexpr subrange<_Iter>
3625 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
const
3627 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3629 _Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last},
3630 reverse_iterator<_Iter>{__first},
3632 if (__found == __first)
3633 return {__last, __last};
3635 return {ranges::prev(__found), __last};
3639 _Iter __found = ranges::find_if(__first, __last, __pred, __proj);
3640 if (__found == __last)
3641 return {__found, __found};
3645 __first = ranges::find_if(ranges::next(__first), __last, __pred, __proj);
3646 if (__first == __last)
3647 return {__found, __first};
3653 template<forward_range _Range,
typename _Proj = identity,
3654 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3655 constexpr borrowed_subrange_t<_Range>
3656 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
3657 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred),
std::move(__proj)); }
3660 inline constexpr __find_last_if_fn find_last_if{};
3662 struct __find_last_if_not_fn
3664 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Proj =
identity,
3665 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
3666 constexpr subrange<_Iter>
3667 operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
const
3669 if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
3671 _Iter __found = ranges::find_if_not(reverse_iterator<_Iter>{__last},
3672 reverse_iterator<_Iter>{__first},
3674 if (__found == __first)
3675 return {__last, __last};
3677 return {ranges::prev(__found), __last};
3681 _Iter __found = ranges::find_if_not(__first, __last, __pred, __proj);
3682 if (__found == __last)
3683 return {__found, __found};
3687 __first = ranges::find_if_not(ranges::next(__first), __last, __pred, __proj);
3688 if (__first == __last)
3689 return {__found, __first};
3695 template<forward_range _Range,
typename _Proj = identity,
3696 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
3697 constexpr borrowed_subrange_t<_Range>
3698 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
3699 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__pred),
std::move(__proj)); }
3702 inline constexpr __find_last_if_not_fn find_last_if_not{};
3706#if __glibcxx_ranges_fold >= 202207L
3708 template<
typename _Iter,
typename _Tp>
3709 struct in_value_result
3711 [[no_unique_address]] _Iter in;
3712 [[no_unique_address]] _Tp value;
3714 template<
typename _Iter2,
typename _Tp2>
3715 requires convertible_to<const _Iter&, _Iter2>
3716 && convertible_to<const _Tp&, _Tp2>
3718 operator in_value_result<_Iter2, _Tp2>() const &
3719 {
return {in, value}; }
3721 template<
typename _Iter2,
typename _Tp2>
3722 requires convertible_to<_Iter, _Iter2>
3723 && convertible_to<_Tp, _Tp2>
3725 operator in_value_result<_Iter2, _Tp2>() &&
3731 template<
typename _Fp>
3737 template<
typename _Tp,
typename _Up>
3738 requires invocable<_Fp&, _Up, _Tp>
3739 invoke_result_t<_Fp&, _Up, _Tp>
3740 operator()(_Tp&&, _Up&&);
3743 template<
typename _Fp,
typename _Tp,
typename _Iter,
typename _Up>
3744 concept __indirectly_binary_left_foldable_impl = movable<_Tp> && movable<_Up>
3745 && convertible_to<_Tp, _Up>
3746 && invocable<_Fp&, _Up, iter_reference_t<_Iter>>
3747 && assignable_from<_Up&, invoke_result_t<_Fp&, _Up, iter_reference_t<_Iter>>>;
3749 template<
typename _Fp,
typename _Tp,
typename _Iter>
3750 concept __indirectly_binary_left_foldable = copy_constructible<_Fp>
3751 && indirectly_readable<_Iter>
3752 && invocable<_Fp&, _Tp, iter_reference_t<_Iter>>
3753 && convertible_to<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>,
3755 && __indirectly_binary_left_foldable_impl
3758 template <
typename _Fp,
typename _Tp,
typename _Iter>
3759 concept __indirectly_binary_right_foldable
3760 = __indirectly_binary_left_foldable<__flipped<_Fp>, _Tp, _Iter>;
3763 template<
typename _Iter,
typename _Tp>
3764 using fold_left_with_iter_result = in_value_result<_Iter, _Tp>;
3766 struct __fold_left_with_iter_fn
3768 template<
typename _Ret_iter,
3769 typename _Iter,
typename _Sent,
typename _Tp,
typename _Fp>
3770 static constexpr auto
3771 _S_impl(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
3773 using _Up = decay_t<invoke_result_t<_Fp&, _Tp, iter_reference_t<_Iter>>>;
3774 using _Ret = fold_left_with_iter_result<_Ret_iter, _Up>;
3776 if (__first == __last)
3780 for (++__first; __first != __last; ++__first)
3785 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
3786 __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3788 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3790 using _Ret_iter = _Iter;
3791 return _S_impl<_Ret_iter>(
std::move(__first), __last,
3795 template<input_range _Range,
typename _Tp,
3796 __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3798 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3800 using _Ret_iter = borrowed_iterator_t<_Range>;
3801 return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
3806 inline constexpr __fold_left_with_iter_fn fold_left_with_iter{};
3808 struct __fold_left_fn
3810 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
3811 __detail::__indirectly_binary_left_foldable<_Tp, _Iter> _Fp>
3813 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3815 return ranges::fold_left_with_iter(
std::move(__first), __last,
3819 template<input_range _Range,
typename _Tp,
3820 __detail::__indirectly_binary_left_foldable<_Tp, iterator_t<_Range>> _Fp>
3822 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3823 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__init),
std::move(__f)); }
3826 inline constexpr __fold_left_fn fold_left{};
3828 template<
typename _Iter,
typename _Tp>
3829 using fold_left_first_with_iter_result = in_value_result<_Iter, _Tp>;
3831 struct __fold_left_first_with_iter_fn
3833 template<
typename _Ret_iter,
typename _Iter,
typename _Sent,
typename _Fp>
3834 static constexpr auto
3835 _S_impl(_Iter __first, _Sent __last, _Fp __f)
3837 using _Up =
decltype(ranges::fold_left(
std::move(__first), __last,
3838 iter_value_t<_Iter>(*__first), __f));
3839 using _Ret = fold_left_first_with_iter_result<_Ret_iter, optional<_Up>>;
3841 if (__first == __last)
3842 return _Ret{
std::move(__first), optional<_Up>()};
3844 optional<_Up> __init(in_place, *__first);
3845 for (++__first; __first != __last; ++__first)
3850 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3851 __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3852 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3854 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3856 using _Ret_iter = _Iter;
3860 template<input_range _Range,
3861 __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3862 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3864 operator()(_Range&& __r, _Fp __f)
const
3866 using _Ret_iter = borrowed_iterator_t<_Range>;
3867 return _S_impl<_Ret_iter>(ranges::begin(__r), ranges::end(__r),
std::move(__f));
3871 inline constexpr __fold_left_first_with_iter_fn fold_left_first_with_iter{};
3873 struct __fold_left_first_fn
3875 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
3876 __detail::__indirectly_binary_left_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3877 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3879 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3881 return ranges::fold_left_first_with_iter(
std::move(__first), __last,
3885 template<input_range _Range,
3886 __detail::__indirectly_binary_left_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3887 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3889 operator()(_Range&& __r, _Fp __f)
const
3890 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__f)); }
3893 inline constexpr __fold_left_first_fn fold_left_first{};
3895 struct __fold_right_fn
3897 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
3898 __detail::__indirectly_binary_right_foldable<_Tp, _Iter> _Fp>
3900 operator()(_Iter __first, _Sent __last, _Tp __init, _Fp __f)
const
3902 using _Up = decay_t<invoke_result_t<_Fp&, iter_reference_t<_Iter>, _Tp>>;
3904 if (__first == __last)
3907 _Iter __tail = ranges::next(__first, __last);
3909 while (__first != __tail)
3914 template<bidirectional_range _Range,
typename _Tp,
3915 __detail::__indirectly_binary_right_foldable<_Tp, iterator_t<_Range>> _Fp>
3917 operator()(_Range&& __r, _Tp __init, _Fp __f)
const
3918 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__init),
std::move(__f)); }
3921 inline constexpr __fold_right_fn fold_right{};
3923 struct __fold_right_last_fn
3925 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3926 __detail::__indirectly_binary_right_foldable<iter_value_t<_Iter>, _Iter> _Fp>
3927 requires constructible_from<iter_value_t<_Iter>, iter_reference_t<_Iter>>
3929 operator()(_Iter __first, _Sent __last, _Fp __f)
const
3931 using _Up =
decltype(ranges::fold_right(__first, __last,
3932 iter_value_t<_Iter>(*__first), __f));
3934 if (__first == __last)
3935 return optional<_Up>();
3937 _Iter __tail = ranges::prev(ranges::next(__first,
std::move(__last)));
3938 return optional<_Up>(in_place,
3939 ranges::fold_right(
std::move(__first), __tail,
3940 iter_value_t<_Iter>(*__tail),
3944 template<bidirectional_range _Range,
3945 __detail::__indirectly_binary_right_foldable<range_value_t<_Range>, iterator_t<_Range>> _Fp>
3946 requires constructible_from<range_value_t<_Range>, range_reference_t<_Range>>
3948 operator()(_Range&& __r, _Fp __f)
const
3949 {
return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__f)); }
3952 inline constexpr __fold_right_last_fn fold_right_last{};
3956 template<
typename _ForwardIterator>
3957 constexpr _ForwardIterator
3958 shift_left(_ForwardIterator __first, _ForwardIterator __last,
3959 typename iterator_traits<_ForwardIterator>::difference_type __n)
3961 __glibcxx_assert(__n >= 0);
3965 auto __mid = ranges::next(__first, __n, __last);
3966 if (__mid == __last)
3971 template<
typename _ForwardIterator>
3972 constexpr _ForwardIterator
3973 shift_right(_ForwardIterator __first, _ForwardIterator __last,
3974 typename iterator_traits<_ForwardIterator>::difference_type __n)
3976 __glibcxx_assert(__n >= 0);
3981 =
typename iterator_traits<_ForwardIterator>::iterator_category;
3982 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
3984 auto __mid = ranges::next(__last, -__n, __first);
3985 if (__mid == __first)
3993 auto __result = ranges::next(__first, __n, __last);
3994 if (__result == __last)
3997 auto __dest_head = __first, __dest_tail = __result;
3998 while (__dest_head != __result)
4000 if (__dest_tail == __last)
4024 auto __cursor = __first;
4025 while (__cursor != __result)
4027 if (__dest_tail == __last)
4032 __dest_head =
std::move(__cursor, __result,
4038 std::iter_swap(__cursor, __dest_head);
4047_GLIBCXX_END_NAMESPACE_VERSION
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
typename decay< _Tp >::type decay_t
Alias template for decay.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.