30 #ifndef _RANGES_ALGO_H 31 #define _RANGES_ALGO_H 1 33 #if __cplusplus > 201703L 39 #if __cpp_lib_concepts 40 namespace std _GLIBCXX_VISIBILITY(default)
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
47 template<
typename _Comp,
typename _Proj>
49 __make_comp_proj(_Comp& __comp, _Proj& __proj)
51 return [&] (
auto&& __lhs,
auto&& __rhs) ->
bool {
52 using _TL = decltype(__lhs);
53 using _TR = decltype(__rhs);
60 template<
typename _Pred,
typename _Proj>
62 __make_pred_proj(_Pred& __pred, _Proj& __proj)
64 return [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
73 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
74 typename _Proj =
identity,
75 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
77 operator()(_Iter __first, _Sent __last,
78 _Pred __pred, _Proj __proj = {})
const 80 for (; __first != __last; ++__first)
86 template<input_range _Range,
typename _Proj = identity,
87 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
90 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 97 inline constexpr __all_of_fn all_of{};
101 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
102 typename _Proj =
identity,
103 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
105 operator()(_Iter __first, _Sent __last,
106 _Pred __pred, _Proj __proj = {})
const 108 for (; __first != __last; ++__first)
114 template<input_range _Range,
typename _Proj = identity,
115 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
118 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 125 inline constexpr __any_of_fn any_of{};
129 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
130 typename _Proj =
identity,
131 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
133 operator()(_Iter __first, _Sent __last,
134 _Pred __pred, _Proj __proj = {})
const 136 for (; __first != __last; ++__first)
142 template<input_range _Range,
typename _Proj = identity,
143 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
146 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 153 inline constexpr __none_of_fn none_of{};
155 template<
typename _Iter,
typename _Fp>
158 [[no_unique_address]] _Iter in;
159 [[no_unique_address]] _Fp fun;
161 template<
typename _Iter2,
typename _F2p>
162 requires convertible_to<const _Iter&, _Iter2>
163 && convertible_to<const _Fp&, _F2p>
165 operator in_fun_result<_Iter2, _F2p>()
const &
166 {
return {in, fun}; }
168 template<
typename _Iter2,
typename _F2p>
169 requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
171 operator in_fun_result<_Iter2, _F2p>() &&
175 template<
typename _Iter,
typename _Fp>
176 using for_each_result = in_fun_result<_Iter, _Fp>;
180 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
181 typename _Proj =
identity,
182 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
183 constexpr for_each_result<_Iter, _Fun>
184 operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {})
const 186 for (; __first != __last; ++__first)
191 template<input_range _Range,
typename _Proj = identity,
192 indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
194 constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun>
195 operator()(_Range&& __r, _Fun __f, _Proj __proj = {})
const 202 inline constexpr __for_each_fn for_each{};
204 template<
typename _Iter,
typename _Fp>
205 using for_each_n_result = in_fun_result<_Iter, _Fp>;
207 struct __for_each_n_fn
209 template<input_iterator _Iter,
typename _Proj = identity,
210 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
211 constexpr for_each_n_result<_Iter, _Fun>
212 operator()(_Iter __first, iter_difference_t<_Iter> __n,
213 _Fun __f, _Proj __proj = {})
const 215 if constexpr (random_access_iterator<_Iter>)
219 auto __last = __first + __n;
235 inline constexpr __for_each_n_fn
for_each_n{};
239 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
240 typename _Proj =
identity>
241 requires indirect_binary_predicate<ranges::equal_to,
242 projected<_Iter, _Proj>,
const _Tp*>
244 operator()(_Iter __first, _Sent __last,
245 const _Tp& __value, _Proj __proj = {})
const 247 while (__first != __last
253 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
254 requires indirect_binary_predicate<ranges::equal_to,
255 projected<iterator_t<_Range>, _Proj>,
257 constexpr borrowed_iterator_t<_Range>
258 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const 265 inline constexpr __find_fn find{};
269 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
270 typename _Proj =
identity,
271 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
273 operator()(_Iter __first, _Sent __last,
274 _Pred __pred, _Proj __proj = {})
const 276 while (__first != __last
282 template<input_range _Range,
typename _Proj = identity,
283 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
285 constexpr borrowed_iterator_t<_Range>
286 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 293 inline constexpr __find_if_fn find_if{};
295 struct __find_if_not_fn
297 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
298 typename _Proj =
identity,
299 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
301 operator()(_Iter __first, _Sent __last,
302 _Pred __pred, _Proj __proj = {})
const 304 while (__first != __last
310 template<input_range _Range,
typename _Proj = identity,
311 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
313 constexpr borrowed_iterator_t<_Range>
314 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 321 inline constexpr __find_if_not_fn find_if_not{};
323 struct __find_first_of_fn
325 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
326 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
327 typename _Pred = ranges::equal_to,
328 typename _Proj1 =
identity,
typename _Proj2 =
identity>
329 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
331 operator()(_Iter1 __first1, _Sent1 __last1,
332 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
333 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 335 for (; __first1 != __last1; ++__first1)
336 for (
auto __iter = __first2; __iter != __last2; ++__iter)
344 template<input_range _Range1, forward_range _Range2,
345 typename _Pred = ranges::equal_to,
346 typename _Proj1 = identity,
typename _Proj2 = identity>
347 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
348 _Pred, _Proj1, _Proj2>
349 constexpr borrowed_iterator_t<_Range1>
350 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
351 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 360 inline constexpr __find_first_of_fn find_first_of{};
364 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
365 typename _Tp,
typename _Proj =
identity>
366 requires indirect_binary_predicate<ranges::equal_to,
367 projected<_Iter, _Proj>,
369 constexpr iter_difference_t<_Iter>
370 operator()(_Iter __first, _Sent __last,
371 const _Tp& __value, _Proj __proj = {})
const 373 iter_difference_t<_Iter> __n = 0;
374 for (; __first != __last; ++__first)
380 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
381 requires indirect_binary_predicate<ranges::equal_to,
382 projected<iterator_t<_Range>, _Proj>,
384 constexpr range_difference_t<_Range>
385 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const 392 inline constexpr __count_fn count{};
396 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
397 typename _Proj =
identity,
398 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
399 constexpr iter_difference_t<_Iter>
400 operator()(_Iter __first, _Sent __last,
401 _Pred __pred, _Proj __proj = {})
const 403 iter_difference_t<_Iter> __n = 0;
404 for (; __first != __last; ++__first)
410 template<input_range _Range,
411 typename _Proj = identity,
412 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
414 constexpr range_difference_t<_Range>
415 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 422 inline constexpr __count_if_fn count_if{};
424 template<
typename _Iter1,
typename _Iter2>
427 [[no_unique_address]] _Iter1 in1;
428 [[no_unique_address]] _Iter2 in2;
430 template<
typename _IIter1,
typename _IIter2>
431 requires convertible_to<const _Iter1&, _IIter1>
432 && convertible_to<const _Iter2&, _IIter2>
434 operator in_in_result<_IIter1, _IIter2>()
const &
435 {
return {in1, in2}; }
437 template<
typename _IIter1,
typename _IIter2>
438 requires convertible_to<_Iter1, _IIter1>
439 && convertible_to<_Iter2, _IIter2>
441 operator in_in_result<_IIter1, _IIter2>() &&
445 template<
typename _Iter1,
typename _Iter2>
446 using mismatch_result = in_in_result<_Iter1, _Iter2>;
450 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
451 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
452 typename _Pred = ranges::equal_to,
453 typename _Proj1 =
identity,
typename _Proj2 =
identity>
454 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
455 constexpr mismatch_result<_Iter1, _Iter2>
456 operator()(_Iter1 __first1, _Sent1 __last1,
457 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
458 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 460 while (__first1 != __last1 && __first2 != __last2
471 template<input_range _Range1, input_range _Range2,
472 typename _Pred = ranges::equal_to,
473 typename _Proj1 = identity,
typename _Proj2 = identity>
474 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
475 _Pred, _Proj1, _Proj2>
476 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
477 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
478 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 487 inline constexpr __mismatch_fn mismatch{};
491 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
492 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
493 typename _Pred = ranges::equal_to,
494 typename _Proj1 =
identity,
typename _Proj2 =
identity>
495 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
496 constexpr subrange<_Iter1>
497 operator()(_Iter1 __first1, _Sent1 __last1,
498 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
499 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 501 if (__first1 == __last1 || __first2 == __last2)
502 return {__first1, __first1};
508 if (__first1 == __last1)
509 return {__first1, __first1};
516 auto __cur1 = __first1;
517 auto __cur2 = __first2;
520 if (++__cur2 == __last2)
521 return {__first1, ++__cur1};
522 if (++__cur1 == __last1)
523 return {__cur1, __cur1};
535 template<forward_range _Range1, forward_range _Range2,
536 typename _Pred = ranges::equal_to,
537 typename _Proj1 = identity,
typename _Proj2 = identity>
538 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
539 _Pred, _Proj1, _Proj2>
540 constexpr borrowed_subrange_t<_Range1>
541 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
542 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 551 inline constexpr __search_fn search{};
555 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
556 typename _Pred = ranges::equal_to,
typename _Proj =
identity>
557 requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
558 constexpr subrange<_Iter>
559 operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
560 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const 563 return {__first, __first};
565 auto __value_comp = [&] <
typename _Rp> (_Rp&& __arg) {
566 return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
570 __first = ranges::find_if(
std::move(__first), __last,
573 if (__first == __last)
574 return {__first, __first};
577 auto __end = __first;
578 return {__first, ++__end};
582 if constexpr (sized_sentinel_for<_Sent, _Iter>
583 && random_access_iterator<_Iter>)
585 auto __tail_size = __last - __first;
586 auto __remainder = __count;
588 while (__remainder <= __tail_size)
590 __first += __remainder;
591 __tail_size -= __remainder;
592 auto __backtrack = __first;
595 if (--__remainder == 0)
596 return {__first - __count, __first};
598 __remainder = __count + 1 - (__first - __backtrack);
600 auto __i = __first + __tail_size;
605 __first = ranges::find_if(__first, __last, __value_comp, __proj);
606 while (__first != __last)
611 while (__i != __last && __n != 1
618 return {__first, __i};
621 __first = ranges::find_if(++__i, __last, __value_comp, __proj);
623 return {__first, __first};
627 template<forward_range _Range,
typename _Tp,
628 typename _Pred = ranges::equal_to,
typename _Proj = identity>
629 requires indirectly_comparable<iterator_t<_Range>,
const _Tp*,
631 constexpr borrowed_subrange_t<_Range>
632 operator()(_Range&& __r, range_difference_t<_Range> __count,
633 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const 641 inline constexpr __search_n_fn search_n{};
645 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
646 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
647 typename _Pred = ranges::equal_to,
648 typename _Proj1 =
identity,
typename _Proj2 =
identity>
649 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
650 constexpr subrange<_Iter1>
651 operator()(_Iter1 __first1, _Sent1 __last1,
652 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
653 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 655 if constexpr (bidirectional_iterator<_Iter1>
656 && bidirectional_iterator<_Iter2>)
658 auto __i1 = ranges::next(__first1, __last1);
659 auto __i2 = ranges::next(__first2, __last2);
661 = ranges::search(reverse_iterator<_Iter1>{__i1},
662 reverse_iterator<_Iter1>{__first1},
663 reverse_iterator<_Iter2>{__i2},
664 reverse_iterator<_Iter2>{__first2},
667 auto __result_first =
ranges::end(__rresult).base();
669 if (__result_last == __first1)
672 return {__result_first, __result_last};
676 auto __i = ranges::next(__first1, __last1);
677 if (__first2 == __last2)
680 auto __result_begin = __i;
681 auto __result_end = __i;
684 auto __new_range = ranges::search(__first1, __last1,
686 __pred, __proj1, __proj2);
689 if (__new_result_begin == __last1)
690 return {__result_begin, __result_end};
693 __result_begin = __new_result_begin;
694 __result_end = __new_result_end;
695 __first1 = __result_begin;
702 template<forward_range _Range1, forward_range _Range2,
703 typename _Pred = ranges::equal_to,
704 typename _Proj1 = identity,
typename _Proj2 = identity>
705 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
706 _Pred, _Proj1, _Proj2>
707 constexpr borrowed_subrange_t<_Range1>
708 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
709 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 718 inline constexpr __find_end_fn find_end{};
720 struct __adjacent_find_fn
722 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
723 typename _Proj =
identity,
724 indirect_binary_predicate<projected<_Iter, _Proj>,
725 projected<_Iter, _Proj>> _Pred
728 operator()(_Iter __first, _Sent __last,
729 _Pred __pred = {}, _Proj __proj = {})
const 731 if (__first == __last)
733 auto __next = __first;
734 for (; ++__next != __last; __first = __next)
744 template<forward_range _Range,
typename _Proj = identity,
745 indirect_binary_predicate<
746 projected<iterator_t<_Range>, _Proj>,
747 projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
748 constexpr borrowed_iterator_t<_Range>
749 operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {})
const 756 inline constexpr __adjacent_find_fn adjacent_find{};
758 struct __is_permutation_fn
760 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
761 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
762 typename _Proj1 =
identity,
typename _Proj2 =
identity,
763 indirect_equivalence_relation<projected<_Iter1, _Proj1>,
764 projected<_Iter2, _Proj2>> _Pred
767 operator()(_Iter1 __first1, _Sent1 __last1,
768 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
769 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 771 constexpr
bool __sized_iters
772 = (sized_sentinel_for<_Sent1, _Iter1>
773 && sized_sentinel_for<_Sent2, _Iter2>);
774 if constexpr (__sized_iters)
776 auto __d1 = ranges::distance(__first1, __last1);
777 auto __d2 = ranges::distance(__first2, __last2);
784 for (; __first1 != __last1 && __first2 != __last2;
785 ++__first1, (void)++__first2)
791 if constexpr (__sized_iters)
793 if (__first1 == __last1)
798 auto __d1 = ranges::distance(__first1, __last1);
799 auto __d2 = ranges::distance(__first2, __last2);
800 if (__d1 == 0 && __d2 == 0)
806 for (
auto __scan = __first1; __scan != __last1; ++__scan)
809 auto __comp_scan = [&] <
typename _Tp> (_Tp&& __arg) {
811 std::forward<_Tp>(__arg));
813 if (__scan != ranges::find_if(__first1, __scan,
814 __comp_scan, __proj1))
817 auto __matches = ranges::count_if(__first2, __last2,
818 __comp_scan, __proj2);
820 || ranges::count_if(__scan, __last1,
821 __comp_scan, __proj1) != __matches)
827 template<forward_range _Range1, forward_range _Range2,
828 typename _Proj1 = identity,
typename _Proj2 = identity,
829 indirect_equivalence_relation<
830 projected<iterator_t<_Range1>, _Proj1>,
831 projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
833 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
834 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 843 inline constexpr __is_permutation_fn is_permutation{};
845 template<
typename _Iter,
typename _Out>
846 using copy_if_result = in_out_result<_Iter, _Out>;
850 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
851 weakly_incrementable _Out,
typename _Proj =
identity,
852 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
853 requires indirectly_copyable<_Iter, _Out>
854 constexpr copy_if_result<_Iter, _Out>
855 operator()(_Iter __first, _Sent __last, _Out __result,
856 _Pred __pred, _Proj __proj = {})
const 858 for (; __first != __last; ++__first)
861 *__result = *__first;
867 template<input_range _Range, weakly_incrementable _Out,
868 typename _Proj = identity,
869 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
871 requires indirectly_copyable<iterator_t<_Range>, _Out>
872 constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
873 operator()(_Range&& __r, _Out __result,
874 _Pred __pred, _Proj __proj = {})
const 882 inline constexpr __copy_if_fn copy_if{};
884 template<
typename _Iter1,
typename _Iter2>
885 using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
887 struct __swap_ranges_fn
889 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
890 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
891 requires indirectly_swappable<_Iter1, _Iter2>
892 constexpr swap_ranges_result<_Iter1, _Iter2>
893 operator()(_Iter1 __first1, _Sent1 __last1,
894 _Iter2 __first2, _Sent2 __last2)
const 896 for (; __first1 != __last1 && __first2 != __last2;
897 ++__first1, (void)++__first2)
898 ranges::iter_swap(__first1, __first2);
902 template<input_range _Range1, input_range _Range2>
903 requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
904 constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
905 borrowed_iterator_t<_Range2>>
906 operator()(_Range1&& __r1, _Range2&& __r2)
const 913 inline constexpr __swap_ranges_fn swap_ranges{};
915 template<
typename _Iter,
typename _Out>
916 using unary_transform_result = in_out_result<_Iter, _Out>;
918 template<
typename _Iter1,
typename _Iter2,
typename _Out>
919 struct in_in_out_result
921 [[no_unique_address]] _Iter1 in1;
922 [[no_unique_address]] _Iter2 in2;
923 [[no_unique_address]] _Out out;
925 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
926 requires convertible_to<const _Iter1&, _IIter1>
927 && convertible_to<const _Iter2&, _IIter2>
928 && convertible_to<const _Out&, _OOut>
930 operator in_in_out_result<_IIter1, _IIter2, _OOut>()
const &
931 {
return {in1, in2, out}; }
933 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
934 requires convertible_to<_Iter1, _IIter1>
935 && convertible_to<_Iter2, _IIter2>
936 && convertible_to<_Out, _OOut>
938 operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
942 template<
typename _Iter1,
typename _Iter2,
typename _Out>
943 using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
945 struct __transform_fn
947 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
948 weakly_incrementable _Out,
949 copy_constructible _Fp,
typename _Proj =
identity>
950 requires indirectly_writable<_Out,
951 indirect_result_t<_Fp&,
952 projected<_Iter, _Proj>>>
953 constexpr unary_transform_result<_Iter, _Out>
954 operator()(_Iter __first1, _Sent __last1, _Out __result,
955 _Fp __op, _Proj __proj = {})
const 957 for (; __first1 != __last1; ++__first1, (void)++__result)
962 template<input_range _Range, weakly_incrementable _Out,
963 copy_constructible _Fp,
typename _Proj = identity>
964 requires indirectly_writable<_Out,
965 indirect_result_t<_Fp&,
966 projected<iterator_t<_Range>, _Proj>>>
967 constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
968 operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {})
const 975 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
976 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
977 weakly_incrementable _Out, copy_constructible _Fp,
978 typename _Proj1 =
identity,
typename _Proj2 =
identity>
979 requires indirectly_writable<_Out,
980 indirect_result_t<_Fp&,
981 projected<_Iter1, _Proj1>,
982 projected<_Iter2, _Proj2>>>
983 constexpr binary_transform_result<_Iter1, _Iter2, _Out>
984 operator()(_Iter1 __first1, _Sent1 __last1,
985 _Iter2 __first2, _Sent2 __last2,
986 _Out __result, _Fp __binary_op,
987 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 989 for (; __first1 != __last1 && __first2 != __last2;
990 ++__first1, (void)++__first2, ++__result)
997 template<input_range _Range1, input_range _Range2,
998 weakly_incrementable _Out, copy_constructible _Fp,
999 typename _Proj1 = identity,
typename _Proj2 = identity>
1000 requires indirectly_writable<_Out,
1001 indirect_result_t<_Fp&,
1002 projected<iterator_t<_Range1>, _Proj1>,
1003 projected<iterator_t<_Range2>, _Proj2>>>
1004 constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
1005 borrowed_iterator_t<_Range2>, _Out>
1006 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
1007 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 1016 inline constexpr __transform_fn transform{};
1020 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1021 typename _Tp1,
typename _Tp2,
typename _Proj =
identity>
1022 requires indirectly_writable<_Iter, const _Tp2&>
1023 && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
1026 operator()(_Iter __first, _Sent __last,
1027 const _Tp1& __old_value,
const _Tp2& __new_value,
1028 _Proj __proj = {})
const 1030 for (; __first != __last; ++__first)
1032 *__first = __new_value;
1036 template<input_range _Range,
1037 typename _Tp1,
typename _Tp2,
typename _Proj = identity>
1038 requires indirectly_writable<iterator_t<_Range>,
const _Tp2&>
1039 && indirect_binary_predicate<ranges::equal_to,
1040 projected<iterator_t<_Range>, _Proj>,
1042 constexpr borrowed_iterator_t<_Range>
1043 operator()(_Range&& __r,
1044 const _Tp1& __old_value,
const _Tp2& __new_value,
1045 _Proj __proj = {})
const 1048 __old_value, __new_value,
std::move(__proj));
1052 inline constexpr __replace_fn replace{};
1054 struct __replace_if_fn
1056 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1057 typename _Tp,
typename _Proj =
identity,
1058 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1059 requires indirectly_writable<_Iter, const _Tp&>
1061 operator()(_Iter __first, _Sent __last,
1062 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const 1064 for (; __first != __last; ++__first)
1066 *__first = __new_value;
1070 template<input_range _Range,
typename _Tp,
typename _Proj = identity,
1071 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1073 requires indirectly_writable<iterator_t<_Range>,
const _Tp&>
1074 constexpr borrowed_iterator_t<_Range>
1075 operator()(_Range&& __r,
1076 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const 1083 inline constexpr __replace_if_fn replace_if{};
1085 template<
typename _Iter,
typename _Out>
1086 using replace_copy_result = in_out_result<_Iter, _Out>;
1088 struct __replace_copy_fn
1090 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1091 typename _Tp1,
typename _Tp2, output_iterator<const _Tp2&> _Out,
1092 typename _Proj =
identity>
1093 requires indirectly_copyable<_Iter, _Out>
1094 && indirect_binary_predicate<ranges::equal_to,
1095 projected<_Iter, _Proj>,
const _Tp1*>
1096 constexpr replace_copy_result<_Iter, _Out>
1097 operator()(_Iter __first, _Sent __last, _Out __result,
1098 const _Tp1& __old_value,
const _Tp2& __new_value,
1099 _Proj __proj = {})
const 1101 for (; __first != __last; ++__first, (void)++__result)
1103 *__result = __new_value;
1105 *__result = *__first;
1109 template<input_range _Range,
typename _Tp1,
typename _Tp2,
1110 output_iterator<const _Tp2&> _Out,
typename _Proj = identity>
1111 requires indirectly_copyable<iterator_t<_Range>, _Out>
1112 && indirect_binary_predicate<ranges::equal_to,
1113 projected<iterator_t<_Range>, _Proj>,
1115 constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
1116 operator()(_Range&& __r, _Out __result,
1117 const _Tp1& __old_value,
const _Tp2& __new_value,
1118 _Proj __proj = {})
const 1126 inline constexpr __replace_copy_fn replace_copy{};
1128 template<
typename _Iter,
typename _Out>
1129 using replace_copy_if_result = in_out_result<_Iter, _Out>;
1131 struct __replace_copy_if_fn
1133 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1134 typename _Tp, output_iterator<const _Tp&> _Out,
1135 typename _Proj =
identity,
1136 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1137 requires indirectly_copyable<_Iter, _Out>
1138 constexpr replace_copy_if_result<_Iter, _Out>
1139 operator()(_Iter __first, _Sent __last, _Out __result,
1140 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const 1142 for (; __first != __last; ++__first, (void)++__result)
1144 *__result = __new_value;
1146 *__result = *__first;
1150 template<input_range _Range,
1151 typename _Tp, output_iterator<const _Tp&> _Out,
1152 typename _Proj = identity,
1153 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1155 requires indirectly_copyable<iterator_t<_Range>, _Out>
1156 constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1157 operator()(_Range&& __r, _Out __result,
1158 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const 1166 inline constexpr __replace_copy_if_fn replace_copy_if{};
1168 struct __generate_n_fn
1170 template<input_or_output_iterator _Out, copy_constructible _Fp>
1171 requires invocable<_Fp&>
1172 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
1174 operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen)
const 1176 for (; __n > 0; --__n, (void)++__first)
1182 inline constexpr __generate_n_fn generate_n{};
1184 struct __generate_fn
1186 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
1187 copy_constructible _Fp>
1188 requires invocable<_Fp&>
1189 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
1191 operator()(_Out __first, _Sent __last, _Fp __gen)
const 1193 for (; __first != __last; ++__first)
1198 template<
typename _Range, copy_constructible _Fp>
1199 requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
1200 constexpr borrowed_iterator_t<_Range>
1201 operator()(_Range&& __r, _Fp __gen)
const 1207 inline constexpr __generate_fn generate{};
1209 struct __remove_if_fn
1211 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1212 typename _Proj =
identity,
1213 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1214 constexpr subrange<_Iter>
1215 operator()(_Iter __first, _Sent __last,
1216 _Pred __pred, _Proj __proj = {})
const 1218 __first = ranges::find_if(__first, __last, __pred, __proj);
1219 if (__first == __last)
1220 return {__first, __first};
1222 auto __result = __first;
1224 for (; __first != __last; ++__first)
1231 return {__result, __first};
1234 template<forward_range _Range,
typename _Proj = identity,
1235 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1237 requires permutable<iterator_t<_Range>>
1238 constexpr borrowed_subrange_t<_Range>
1239 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 1246 inline constexpr __remove_if_fn remove_if{};
1250 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1251 typename _Tp,
typename _Proj =
identity>
1252 requires indirect_binary_predicate<ranges::equal_to,
1253 projected<_Iter, _Proj>,
1255 constexpr subrange<_Iter>
1256 operator()(_Iter __first, _Sent __last,
1257 const _Tp& __value, _Proj __proj = {})
const 1259 auto __pred = [&] (
auto&& __arg) {
1260 return std::forward<decltype(__arg)>(__arg) == __value;
1262 return ranges::remove_if(__first, __last,
1266 template<forward_range _Range,
typename _Tp,
typename _Proj =
identity>
1267 requires permutable<iterator_t<_Range>>
1268 && indirect_binary_predicate<ranges::equal_to,
1269 projected<iterator_t<_Range>, _Proj>,
1271 constexpr borrowed_subrange_t<_Range>
1272 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const 1279 inline constexpr __remove_fn
remove{};
1281 template<
typename _Iter,
typename _Out>
1282 using remove_copy_if_result = in_out_result<_Iter, _Out>;
1284 struct __remove_copy_if_fn
1286 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1287 weakly_incrementable _Out,
typename _Proj =
identity,
1288 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1289 requires indirectly_copyable<_Iter, _Out>
1290 constexpr remove_copy_if_result<_Iter, _Out>
1291 operator()(_Iter __first, _Sent __last, _Out __result,
1292 _Pred __pred, _Proj __proj = {})
const 1294 for (; __first != __last; ++__first)
1297 *__result = *__first;
1303 template<input_range _Range, weakly_incrementable _Out,
1304 typename _Proj = identity,
1305 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1307 requires indirectly_copyable<iterator_t<_Range>, _Out>
1308 constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1309 operator()(_Range&& __r, _Out __result,
1310 _Pred __pred, _Proj __proj = {})
const 1318 inline constexpr __remove_copy_if_fn remove_copy_if{};
1320 template<
typename _Iter,
typename _Out>
1321 using remove_copy_result = in_out_result<_Iter, _Out>;
1323 struct __remove_copy_fn
1325 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1326 weakly_incrementable _Out,
typename _Tp,
typename _Proj =
identity>
1327 requires indirectly_copyable<_Iter, _Out>
1328 && indirect_binary_predicate<ranges::equal_to,
1329 projected<_Iter, _Proj>,
1331 constexpr remove_copy_result<_Iter, _Out>
1332 operator()(_Iter __first, _Sent __last, _Out __result,
1333 const _Tp& __value, _Proj __proj = {})
const 1335 for (; __first != __last; ++__first)
1338 *__result = *__first;
1344 template<input_range _Range, weakly_incrementable _Out,
1345 typename _Tp,
typename _Proj = identity>
1346 requires indirectly_copyable<iterator_t<_Range>, _Out>
1347 && indirect_binary_predicate<ranges::equal_to,
1348 projected<iterator_t<_Range>, _Proj>,
1350 constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
1351 operator()(_Range&& __r, _Out __result,
1352 const _Tp& __value, _Proj __proj = {})
const 1359 inline constexpr __remove_copy_fn remove_copy{};
1363 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1364 typename _Proj =
identity,
1365 indirect_equivalence_relation<
1366 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1367 constexpr subrange<_Iter>
1368 operator()(_Iter __first, _Sent __last,
1369 _Comp __comp = {}, _Proj __proj = {})
const 1371 __first = ranges::adjacent_find(__first, __last, __comp, __proj);
1372 if (__first == __last)
1373 return {__first, __first};
1375 auto __dest = __first;
1377 while (++__first != __last)
1382 return {++__dest, __first};
1385 template<forward_range _Range,
typename _Proj = identity,
1386 indirect_equivalence_relation<
1387 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1388 requires permutable<iterator_t<_Range>>
1389 constexpr borrowed_subrange_t<_Range>
1390 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 1397 inline constexpr __unique_fn unique{};
1401 template<
typename _Out,
typename _Tp>
1402 concept __can_reread_output = input_iterator<_Out>
1403 && same_as<_Tp, iter_value_t<_Out>>;
1406 template<
typename _Iter,
typename _Out>
1407 using unique_copy_result = in_out_result<_Iter, _Out>;
1409 struct __unique_copy_fn
1411 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1412 weakly_incrementable _Out,
typename _Proj =
identity,
1413 indirect_equivalence_relation<
1414 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1415 requires indirectly_copyable<_Iter, _Out>
1416 && (forward_iterator<_Iter>
1417 || __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
1418 || indirectly_copyable_storable<_Iter, _Out>)
1419 constexpr unique_copy_result<_Iter, _Out>
1420 operator()(_Iter __first, _Sent __last, _Out __result,
1421 _Comp __comp = {}, _Proj __proj = {})
const 1423 if (__first == __last)
1427 if constexpr (forward_iterator<_Iter>)
1429 auto __next = __first;
1430 *__result = *__next;
1431 while (++__next != __last)
1437 *++__result = *__first;
1441 else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
1443 *__result = *__first;
1444 while (++__first != __last)
1448 *++__result = *__first;
1453 auto __value = *__first;
1454 *__result = __value;
1455 while (++__first != __last)
1462 *++__result = __value;
1469 template<input_range _Range,
1470 weakly_incrementable _Out,
typename _Proj = identity,
1471 indirect_equivalence_relation<
1472 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1473 requires indirectly_copyable<iterator_t<_Range>, _Out>
1474 && (forward_iterator<iterator_t<_Range>>
1475 || __detail::__can_reread_output<_Out, range_value_t<_Range>>
1476 || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1477 constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1478 operator()(_Range&& __r, _Out __result,
1479 _Comp __comp = {}, _Proj __proj = {})
const 1487 inline constexpr __unique_copy_fn unique_copy{};
1491 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1492 requires permutable<_Iter>
1494 operator()(_Iter __first, _Sent __last)
const 1496 auto __i = ranges::next(__first, __last);
1499 if constexpr (random_access_iterator<_Iter>)
1501 if (__first != __last)
1504 while (__first < __tail)
1506 ranges::iter_swap(__first, __tail);
1516 if (__first == __tail || __first == --__tail)
1520 ranges::iter_swap(__first, __tail);
1527 template<b
idirectional_range _Range>
1528 requires permutable<iterator_t<_Range>>
1529 constexpr borrowed_iterator_t<_Range>
1530 operator()(_Range&& __r)
const 1536 inline constexpr __reverse_fn reverse{};
1538 template<
typename _Iter,
typename _Out>
1539 using reverse_copy_result = in_out_result<_Iter, _Out>;
1541 struct __reverse_copy_fn
1543 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1544 weakly_incrementable _Out>
1545 requires indirectly_copyable<_Iter, _Out>
1546 constexpr reverse_copy_result<_Iter, _Out>
1547 operator()(_Iter __first, _Sent __last, _Out __result)
const 1549 auto __i = ranges::next(__first, __last);
1551 while (__first != __tail)
1554 *__result = *__tail;
1557 return {__i, __result};
1560 template<b
idirectional_range _Range, weakly_incrementable _Out>
1561 requires indirectly_copyable<iterator_t<_Range>, _Out>
1562 constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1563 operator()(_Range&& __r, _Out __result)
const 1570 inline constexpr __reverse_copy_fn reverse_copy{};
1574 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1575 constexpr subrange<_Iter>
1576 operator()(_Iter __first, _Iter __middle, _Sent __last)
const 1578 auto __lasti = ranges::next(__first, __last);
1579 if (__first == __middle)
1580 return {__lasti, __lasti};
1581 if (__last == __middle)
1584 if constexpr (random_access_iterator<_Iter>)
1586 auto __n = __lasti - __first;
1587 auto __k = __middle - __first;
1589 if (__k == __n - __k)
1591 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1596 auto __ret = __first + (__lasti - __middle);
1600 if (__k < __n - __k)
1604 if constexpr (__is_pod(iter_value_t<_Iter>))
1612 auto __q = __p + __k;
1613 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1615 ranges::iter_swap(__p, __q);
1622 ranges::swap(__n, __k);
1630 if constexpr (__is_pod(iter_value_t<_Iter>))
1638 auto __q = __p + __n;
1640 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1644 ranges::iter_swap(__p, __q);
1649 std::swap(__n, __k);
1653 else if constexpr (bidirectional_iterator<_Iter>)
1655 auto __tail = __lasti;
1657 ranges::reverse(__first, __middle);
1658 ranges::reverse(__middle, __tail);
1660 while (__first != __middle && __middle != __tail)
1662 ranges::iter_swap(__first, --__tail);
1666 if (__first == __middle)
1668 ranges::reverse(__middle, __tail);
1673 ranges::reverse(__first, __middle);
1679 auto __first2 = __middle;
1682 ranges::iter_swap(__first, __first2);
1685 if (__first == __middle)
1686 __middle = __first2;
1687 }
while (__first2 != __last);
1689 auto __ret = __first;
1691 __first2 = __middle;
1693 while (__first2 != __last)
1695 ranges::iter_swap(__first, __first2);
1698 if (__first == __middle)
1699 __middle = __first2;
1700 else if (__first2 == __last)
1701 __first2 = __middle;
1707 template<forward_range _Range>
1708 requires permutable<iterator_t<_Range>>
1709 constexpr borrowed_subrange_t<_Range>
1710 operator()(_Range&& __r, iterator_t<_Range> __middle)
const 1717 inline constexpr __rotate_fn rotate{};
1719 template<
typename _Iter,
typename _Out>
1720 using rotate_copy_result = in_out_result<_Iter, _Out>;
1722 struct __rotate_copy_fn
1724 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1725 weakly_incrementable _Out>
1726 requires indirectly_copyable<_Iter, _Out>
1727 constexpr rotate_copy_result<_Iter, _Out>
1728 operator()(_Iter __first, _Iter __middle, _Sent __last,
1729 _Out __result)
const 1731 auto __copy1 = ranges::copy(__middle,
1734 auto __copy2 = ranges::copy(
std::move(__first),
1740 template<forward_range _Range, weakly_incrementable _Out>
1741 requires indirectly_copyable<iterator_t<_Range>, _Out>
1742 constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1743 operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result)
const 1750 inline constexpr __rotate_copy_fn rotate_copy{};
1754 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1755 weakly_incrementable _Out,
typename _Gen>
1756 requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
1757 && indirectly_copyable<_Iter, _Out>
1758 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1760 operator()(_Iter __first, _Sent __last, _Out __out,
1761 iter_difference_t<_Iter> __n, _Gen&& __g)
const 1763 if constexpr (forward_iterator<_Iter>)
1767 auto __lasti = ranges::next(__first, __last);
1770 __n, std::forward<_Gen>(__g));
1774 using __distrib_type
1775 = uniform_int_distribution<iter_difference_t<_Iter>>;
1776 using __param_type =
typename __distrib_type::param_type;
1777 __distrib_type __d{};
1778 iter_difference_t<_Iter> __sample_sz = 0;
1779 while (__first != __last && __sample_sz != __n)
1781 __out[__sample_sz++] = *__first;
1784 for (
auto __pop_sz = __sample_sz; __first != __last;
1785 ++__first, (void) ++__pop_sz)
1787 const auto __k = __d(__g, __param_type{0, __pop_sz});
1789 __out[__k] = *__first;
1791 return __out + __sample_sz;
1795 template<input_range _Range, weakly_incrementable _Out,
typename _Gen>
1796 requires (forward_range<_Range> || random_access_iterator<_Out>)
1797 && indirectly_copyable<iterator_t<_Range>, _Out>
1798 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1800 operator()(_Range&& __r, _Out __out,
1801 range_difference_t<_Range> __n, _Gen&& __g)
const 1805 std::forward<_Gen>(__g));
1809 inline constexpr __sample_fn
sample{};
1811 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 1814 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1816 requires permutable<_Iter>
1817 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1819 operator()(_Iter __first, _Sent __last, _Gen&& __g)
const 1821 auto __lasti = ranges::next(__first, __last);
1826 template<random_access_range _Range,
typename _Gen>
1827 requires permutable<iterator_t<_Range>>
1828 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1829 borrowed_iterator_t<_Range>
1830 operator()(_Range&& __r, _Gen&& __g)
const 1833 std::forward<_Gen>(__g));
1837 inline constexpr __shuffle_fn shuffle{};
1840 struct __push_heap_fn
1842 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1843 typename _Comp = ranges::less,
typename _Proj =
identity>
1844 requires sortable<_Iter, _Comp, _Proj>
1846 operator()(_Iter __first, _Sent __last,
1847 _Comp __comp = {}, _Proj __proj = {})
const 1849 auto __lasti = ranges::next(__first, __last);
1851 __detail::__make_comp_proj(__comp, __proj));
1855 template<random_access_range _Range,
1856 typename _Comp = ranges::less,
typename _Proj = identity>
1857 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1858 constexpr borrowed_iterator_t<_Range>
1859 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 1866 inline constexpr __push_heap_fn push_heap{};
1868 struct __pop_heap_fn
1870 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1871 typename _Comp = ranges::less,
typename _Proj =
identity>
1872 requires sortable<_Iter, _Comp, _Proj>
1874 operator()(_Iter __first, _Sent __last,
1875 _Comp __comp = {}, _Proj __proj = {})
const 1877 auto __lasti = ranges::next(__first, __last);
1879 __detail::__make_comp_proj(__comp, __proj));
1883 template<random_access_range _Range,
1884 typename _Comp = ranges::less,
typename _Proj = identity>
1885 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1886 constexpr borrowed_iterator_t<_Range>
1887 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 1894 inline constexpr __pop_heap_fn pop_heap{};
1896 struct __make_heap_fn
1898 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1899 typename _Comp = ranges::less,
typename _Proj =
identity>
1900 requires sortable<_Iter, _Comp, _Proj>
1902 operator()(_Iter __first, _Sent __last,
1903 _Comp __comp = {}, _Proj __proj = {})
const 1905 auto __lasti = ranges::next(__first, __last);
1907 __detail::__make_comp_proj(__comp, __proj));
1911 template<random_access_range _Range,
1912 typename _Comp = ranges::less,
typename _Proj = identity>
1913 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1914 constexpr borrowed_iterator_t<_Range>
1915 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 1922 inline constexpr __make_heap_fn make_heap{};
1924 struct __sort_heap_fn
1926 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1927 typename _Comp = ranges::less,
typename _Proj =
identity>
1928 requires sortable<_Iter, _Comp, _Proj>
1930 operator()(_Iter __first, _Sent __last,
1931 _Comp __comp = {}, _Proj __proj = {})
const 1933 auto __lasti = ranges::next(__first, __last);
1935 __detail::__make_comp_proj(__comp, __proj));
1939 template<random_access_range _Range,
1940 typename _Comp = ranges::less,
typename _Proj = identity>
1941 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1942 constexpr borrowed_iterator_t<_Range>
1943 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 1950 inline constexpr __sort_heap_fn sort_heap{};
1952 struct __is_heap_until_fn
1954 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1955 typename _Proj =
identity,
1956 indirect_strict_weak_order<projected<_Iter, _Proj>>
1957 _Comp = ranges::less>
1959 operator()(_Iter __first, _Sent __last,
1960 _Comp __comp = {}, _Proj __proj = {})
const 1962 iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
1963 iter_difference_t<_Iter> __parent = 0, __child = 1;
1964 for (; __child < __n; ++__child)
1968 return __first + __child;
1969 else if ((__child & 1) == 0)
1972 return __first + __n;
1975 template<random_access_range _Range,
1976 typename _Proj = identity,
1977 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1978 _Comp = ranges::less>
1979 constexpr borrowed_iterator_t<_Range>
1980 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 1987 inline constexpr __is_heap_until_fn is_heap_until{};
1991 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1992 typename _Proj =
identity,
1993 indirect_strict_weak_order<projected<_Iter, _Proj>>
1994 _Comp = ranges::less>
1996 operator()(_Iter __first, _Sent __last,
1997 _Comp __comp = {}, _Proj __proj = {})
const 2000 == ranges::is_heap_until(__first, __last,
2005 template<random_access_range _Range,
2006 typename _Proj = identity,
2007 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2008 _Comp = ranges::less>
2010 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 2017 inline constexpr __is_heap_fn is_heap{};
2021 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2022 typename _Comp = ranges::less,
typename _Proj =
identity>
2023 requires sortable<_Iter, _Comp, _Proj>
2025 operator()(_Iter __first, _Sent __last,
2026 _Comp __comp = {}, _Proj __proj = {})
const 2028 auto __lasti = ranges::next(__first, __last);
2029 _GLIBCXX_STD_A::sort(
std::move(__first), __lasti,
2030 __detail::__make_comp_proj(__comp, __proj));
2034 template<random_access_range _Range,
2035 typename _Comp = ranges::less,
typename _Proj = identity>
2036 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2037 constexpr borrowed_iterator_t<_Range>
2038 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 2045 inline constexpr __sort_fn sort{};
2047 struct __stable_sort_fn
2049 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2050 typename _Comp = ranges::less,
typename _Proj =
identity>
2051 requires sortable<_Iter, _Comp, _Proj>
2053 operator()(_Iter __first, _Sent __last,
2054 _Comp __comp = {}, _Proj __proj = {})
const 2056 auto __lasti = ranges::next(__first, __last);
2058 __detail::__make_comp_proj(__comp, __proj));
2062 template<random_access_range _Range,
2063 typename _Comp = ranges::less,
typename _Proj = identity>
2064 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2065 borrowed_iterator_t<_Range>
2066 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 2073 inline constexpr __stable_sort_fn stable_sort{};
2075 struct __partial_sort_fn
2077 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2078 typename _Comp = ranges::less,
typename _Proj =
identity>
2079 requires sortable<_Iter, _Comp, _Proj>
2081 operator()(_Iter __first, _Iter __middle, _Sent __last,
2082 _Comp __comp = {}, _Proj __proj = {})
const 2084 if (__first == __middle)
2085 return ranges::next(__first, __last);
2087 ranges::make_heap(__first, __middle, __comp, __proj);
2088 auto __i = __middle;
2089 for (; __i != __last; ++__i)
2094 ranges::pop_heap(__first, __middle, __comp, __proj);
2095 ranges::iter_swap(__middle-1, __i);
2096 ranges::push_heap(__first, __middle, __comp, __proj);
2098 ranges::sort_heap(__first, __middle, __comp, __proj);
2103 template<random_access_range _Range,
2104 typename _Comp = ranges::less,
typename _Proj = identity>
2105 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2106 constexpr borrowed_iterator_t<_Range>
2107 operator()(_Range&& __r, iterator_t<_Range> __middle,
2108 _Comp __comp = {}, _Proj __proj = {})
const 2116 inline constexpr __partial_sort_fn partial_sort{};
2118 template<
typename _Iter,
typename _Out>
2119 using partial_sort_copy_result = in_out_result<_Iter, _Out>;
2121 struct __partial_sort_copy_fn
2123 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2124 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2125 typename _Comp = ranges::less,
2126 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2127 requires indirectly_copyable<_Iter1, _Iter2>
2128 && sortable<_Iter2, _Comp, _Proj2>
2129 && indirect_strict_weak_order<_Comp,
2130 projected<_Iter1, _Proj1>,
2131 projected<_Iter2, _Proj2>>
2132 constexpr partial_sort_copy_result<_Iter1, _Iter2>
2133 operator()(_Iter1 __first, _Sent1 __last,
2134 _Iter2 __result_first, _Sent2 __result_last,
2136 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 2138 if (__result_first == __result_last)
2141 auto __lasti = ranges::next(
std::move(__first),
2146 auto __result_real_last = __result_first;
2147 while (__first != __last && __result_real_last != __result_last)
2149 *__result_real_last = *__first;
2150 ++__result_real_last;
2154 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
2155 for (; __first != __last; ++__first)
2160 ranges::pop_heap(__result_first, __result_real_last,
2162 *(__result_real_last-1) = *__first;
2163 ranges::push_heap(__result_first, __result_real_last,
2166 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
2171 template<input_range _Range1, random_access_range _Range2,
2172 typename _Comp = ranges::less,
2173 typename _Proj1 = identity,
typename _Proj2 = identity>
2174 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
2175 && sortable<iterator_t<_Range2>, _Comp, _Proj2>
2176 && indirect_strict_weak_order<_Comp,
2177 projected<iterator_t<_Range1>, _Proj1>,
2178 projected<iterator_t<_Range2>, _Proj2>>
2179 constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
2180 borrowed_iterator_t<_Range2>>
2181 operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
2182 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 2191 inline constexpr __partial_sort_copy_fn partial_sort_copy{};
2193 struct __is_sorted_until_fn
2195 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2196 typename _Proj =
identity,
2197 indirect_strict_weak_order<projected<_Iter, _Proj>>
2198 _Comp = ranges::less>
2200 operator()(_Iter __first, _Sent __last,
2201 _Comp __comp = {}, _Proj __proj = {})
const 2203 if (__first == __last)
2206 auto __next = __first;
2207 for (++__next; __next != __last; __first = __next, (void)++__next)
2215 template<forward_range _Range,
typename _Proj = identity,
2216 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2217 _Comp = ranges::less>
2218 constexpr borrowed_iterator_t<_Range>
2219 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 2226 inline constexpr __is_sorted_until_fn is_sorted_until{};
2228 struct __is_sorted_fn
2230 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2231 typename _Proj =
identity,
2232 indirect_strict_weak_order<projected<_Iter, _Proj>>
2233 _Comp = ranges::less>
2235 operator()(_Iter __first, _Sent __last,
2236 _Comp __comp = {}, _Proj __proj = {})
const 2238 if (__first == __last)
2241 auto __next = __first;
2242 for (++__next; __next != __last; __first = __next, (void)++__next)
2250 template<forward_range _Range,
typename _Proj = identity,
2251 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2252 _Comp = ranges::less>
2254 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 2261 inline constexpr __is_sorted_fn is_sorted{};
2263 struct __nth_element_fn
2265 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2266 typename _Comp = ranges::less,
typename _Proj =
identity>
2267 requires sortable<_Iter, _Comp, _Proj>
2269 operator()(_Iter __first, _Iter __nth, _Sent __last,
2270 _Comp __comp = {}, _Proj __proj = {})
const 2272 auto __lasti = ranges::next(__first, __last);
2275 __detail::__make_comp_proj(__comp, __proj));
2279 template<random_access_range _Range,
2280 typename _Comp = ranges::less,
typename _Proj = identity>
2281 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2282 constexpr borrowed_iterator_t<_Range>
2283 operator()(_Range&& __r, iterator_t<_Range> __nth,
2284 _Comp __comp = {}, _Proj __proj = {})
const 2291 inline constexpr __nth_element_fn nth_element{};
2293 struct __lower_bound_fn
2295 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2296 typename _Tp,
typename _Proj =
identity,
2297 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2298 _Comp = ranges::less>
2300 operator()(_Iter __first, _Sent __last,
2301 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const 2303 auto __len = ranges::distance(__first, __last);
2307 auto __half = __len / 2;
2308 auto __middle = __first;
2309 ranges::advance(__middle, __half);
2314 __len = __len - __half - 1;
2322 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2323 indirect_strict_weak_order<
const _Tp*,
2324 projected<iterator_t<_Range>, _Proj>>
2325 _Comp = ranges::less>
2326 constexpr borrowed_iterator_t<_Range>
2327 operator()(_Range&& __r,
2328 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const 2335 inline constexpr __lower_bound_fn lower_bound{};
2337 struct __upper_bound_fn
2339 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2340 typename _Tp,
typename _Proj =
identity,
2341 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2342 _Comp = ranges::less>
2344 operator()(_Iter __first, _Sent __last,
2345 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const 2347 auto __len = ranges::distance(__first, __last);
2351 auto __half = __len / 2;
2352 auto __middle = __first;
2353 ranges::advance(__middle, __half);
2360 __len = __len - __half - 1;
2366 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2367 indirect_strict_weak_order<
const _Tp*,
2368 projected<iterator_t<_Range>, _Proj>>
2369 _Comp = ranges::less>
2370 constexpr borrowed_iterator_t<_Range>
2371 operator()(_Range&& __r,
2372 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const 2379 inline constexpr __upper_bound_fn upper_bound{};
2381 struct __equal_range_fn
2383 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2384 typename _Tp,
typename _Proj =
identity,
2385 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2386 _Comp = ranges::less>
2387 constexpr subrange<_Iter>
2388 operator()(_Iter __first, _Sent __last,
2389 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const 2391 auto __len = ranges::distance(__first, __last);
2395 auto __half = __len / 2;
2396 auto __middle = __first;
2397 ranges::advance(__middle, __half);
2404 __len = __len - __half - 1;
2413 = ranges::lower_bound(__first, __middle,
2414 __value, __comp, __proj);
2415 ranges::advance(__first, __len);
2417 = ranges::upper_bound(++__middle, __first,
2418 __value, __comp, __proj);
2419 return {__left, __right};
2422 return {__first, __first};
2425 template<forward_range _Range,
2426 typename _Tp,
typename _Proj = identity,
2427 indirect_strict_weak_order<
const _Tp*,
2428 projected<iterator_t<_Range>, _Proj>>
2429 _Comp = ranges::less>
2430 constexpr borrowed_subrange_t<_Range>
2431 operator()(_Range&& __r,
const _Tp& __value,
2432 _Comp __comp = {}, _Proj __proj = {})
const 2439 inline constexpr __equal_range_fn equal_range{};
2441 struct __binary_search_fn
2443 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2444 typename _Tp,
typename _Proj =
identity,
2445 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2446 _Comp = ranges::less>
2448 operator()(_Iter __first, _Sent __last,
2449 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const 2451 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2458 template<forward_range _Range,
2459 typename _Tp,
typename _Proj = identity,
2460 indirect_strict_weak_order<
const _Tp*,
2461 projected<iterator_t<_Range>, _Proj>>
2462 _Comp = ranges::less>
2464 operator()(_Range&& __r,
const _Tp& __value, _Comp __comp = {},
2465 _Proj __proj = {})
const 2472 inline constexpr __binary_search_fn binary_search{};
2474 struct __is_partitioned_fn
2476 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2477 typename _Proj =
identity,
2478 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2480 operator()(_Iter __first, _Sent __last,
2481 _Pred __pred, _Proj __proj = {})
const 2483 __first = ranges::find_if_not(
std::move(__first), __last,
2485 if (__first == __last)
2492 template<input_range _Range,
typename _Proj = identity,
2493 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2496 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 2503 inline constexpr __is_partitioned_fn is_partitioned{};
2505 struct __partition_fn
2507 template<permutable _Iter, sentinel_for<_Iter> _Sent,
2508 typename _Proj =
identity,
2509 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2510 constexpr subrange<_Iter>
2511 operator()(_Iter __first, _Sent __last,
2512 _Pred __pred, _Proj __proj = {})
const 2514 if constexpr (bidirectional_iterator<_Iter>)
2516 auto __lasti = ranges::next(__first, __last);
2517 auto __tail = __lasti;
2521 if (__first == __tail)
2530 if (__first == __tail)
2537 ranges::iter_swap(__first, __tail);
2543 if (__first == __last)
2547 if (++__first == __last)
2550 auto __next = __first;
2551 while (++__next != __last)
2554 ranges::iter_swap(__first, __next);
2562 template<forward_range _Range,
typename _Proj = identity,
2563 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2565 requires permutable<iterator_t<_Range>>
2566 constexpr borrowed_subrange_t<_Range>
2567 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 2574 inline constexpr __partition_fn partition{};
2576 struct __stable_partition_fn
2578 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2579 typename _Proj =
identity,
2580 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2581 requires permutable<_Iter>
2583 operator()(_Iter __first, _Sent __last,
2584 _Pred __pred, _Proj __proj = {})
const 2586 auto __lasti = ranges::next(__first, __last);
2589 __detail::__make_pred_proj(__pred, __proj));
2593 template<bidirectional_range _Range,
typename _Proj = identity,
2594 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2596 requires permutable<iterator_t<_Range>>
2597 borrowed_subrange_t<_Range>
2598 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 2605 inline constexpr __stable_partition_fn stable_partition{};
2607 template<
typename _Iter,
typename _Out1,
typename _Out2>
2608 struct in_out_out_result
2610 [[no_unique_address]] _Iter in;
2611 [[no_unique_address]] _Out1 out1;
2612 [[no_unique_address]] _Out2 out2;
2614 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2615 requires convertible_to<const _Iter&, _IIter>
2616 && convertible_to<const _Out1&, _OOut1>
2617 && convertible_to<const _Out2&, _OOut2>
2619 operator in_out_out_result<_IIter, _OOut1, _OOut2>()
const &
2620 {
return {in, out1, out2}; }
2622 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2623 requires convertible_to<_Iter, _IIter>
2624 && convertible_to<_Out1, _OOut1>
2625 && convertible_to<_Out2, _OOut2>
2627 operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2631 template<
typename _Iter,
typename _Out1,
typename _Out2>
2632 using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2634 struct __partition_copy_fn
2636 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2637 weakly_incrementable _Out1, weakly_incrementable _O2,
2638 typename _Proj =
identity,
2639 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2640 requires indirectly_copyable<_Iter, _Out1>
2641 && indirectly_copyable<_Iter, _O2>
2642 constexpr partition_copy_result<_Iter, _Out1, _O2>
2643 operator()(_Iter __first, _Sent __last,
2644 _Out1 __out_true, _O2 __out_false,
2645 _Pred __pred, _Proj __proj = {})
const 2647 for (; __first != __last; ++__first)
2650 *__out_true = *__first;
2655 *__out_false = *__first;
2663 template<input_range _Range, weakly_incrementable _Out1,
2664 weakly_incrementable _O2,
2665 typename _Proj = identity,
2666 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2668 requires indirectly_copyable<iterator_t<_Range>, _Out1>
2669 && indirectly_copyable<iterator_t<_Range>, _O2>
2670 constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _O2>
2671 operator()(_Range&& __r, _Out1 out_true, _O2 out_false,
2672 _Pred __pred, _Proj __proj = {})
const 2680 inline constexpr __partition_copy_fn partition_copy{};
2682 struct __partition_point_fn
2684 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2685 typename _Proj =
identity,
2686 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2688 operator()(_Iter __first, _Sent __last,
2689 _Pred __pred, _Proj __proj = {})
const 2691 auto __len = ranges::distance(__first, __last);
2695 auto __half = __len / 2;
2696 auto __middle = __first;
2697 ranges::advance(__middle, __half);
2702 __len = __len - __half - 1;
2710 template<forward_range _Range,
typename _Proj = identity,
2711 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2713 constexpr borrowed_iterator_t<_Range>
2714 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const 2721 inline constexpr __partition_point_fn partition_point{};
2723 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2724 using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2728 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2729 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2730 weakly_incrementable _Out,
typename _Comp = ranges::less,
2731 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2732 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2733 constexpr merge_result<_Iter1, _Iter2, _Out>
2734 operator()(_Iter1 __first1, _Sent1 __last1,
2735 _Iter2 __first2, _Sent2 __last2, _Out __result,
2737 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 2739 while (__first1 != __last1 && __first2 != __last2)
2745 *__result = *__first2;
2750 *__result = *__first1;
2763 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2764 typename _Comp = ranges::less,
2765 typename _Proj1 = identity,
typename _Proj2 = identity>
2766 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2767 _Comp, _Proj1, _Proj2>
2768 constexpr merge_result<borrowed_iterator_t<_Range1>,
2769 borrowed_iterator_t<_Range2>,
2771 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2773 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 2782 inline constexpr __merge_fn merge{};
2784 struct __inplace_merge_fn
2786 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2787 typename _Comp = ranges::less,
2788 typename _Proj =
identity>
2789 requires sortable<_Iter, _Comp, _Proj>
2791 operator()(_Iter __first, _Iter __middle, _Sent __last,
2792 _Comp __comp = {}, _Proj __proj = {})
const 2794 auto __lasti = ranges::next(__first, __last);
2796 __detail::__make_comp_proj(__comp, __proj));
2800 template<bidirectional_range _Range,
2801 typename _Comp = ranges::less,
typename _Proj = identity>
2802 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2803 borrowed_iterator_t<_Range>
2804 operator()(_Range&& __r, iterator_t<_Range> __middle,
2805 _Comp __comp = {}, _Proj __proj = {})
const 2813 inline constexpr __inplace_merge_fn inplace_merge{};
2815 struct __includes_fn
2817 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2818 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2819 typename _Proj1 =
identity,
typename _Proj2 =
identity,
2820 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2821 projected<_Iter2, _Proj2>>
2822 _Comp = ranges::less>
2824 operator()(_Iter1 __first1, _Sent1 __last1,
2825 _Iter2 __first2, _Sent2 __last2,
2827 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 2829 while (__first1 != __last1 && __first2 != __last2)
2844 return __first2 == __last2;
2847 template<input_range _Range1, input_range _Range2,
2848 typename _Proj1 = identity,
typename _Proj2 = identity,
2849 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2850 projected<iterator_t<_Range2>, _Proj2>>
2851 _Comp = ranges::less>
2853 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2854 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 2863 inline constexpr __includes_fn includes{};
2865 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2866 using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2868 struct __set_union_fn
2870 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2871 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2872 weakly_incrementable _Out,
typename _Comp = ranges::less,
2873 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2874 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2875 constexpr set_union_result<_Iter1, _Iter2, _Out>
2876 operator()(_Iter1 __first1, _Sent1 __last1,
2877 _Iter2 __first2, _Sent2 __last2,
2878 _Out __result, _Comp __comp = {},
2879 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 2881 while (__first1 != __last1 && __first2 != __last2)
2887 *__result = *__first1;
2894 *__result = *__first2;
2899 *__result = *__first1;
2913 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2914 typename _Comp = ranges::less,
2915 typename _Proj1 = identity,
typename _Proj2 = identity>
2916 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2917 _Comp, _Proj1, _Proj2>
2918 constexpr set_union_result<borrowed_iterator_t<_Range1>,
2919 borrowed_iterator_t<_Range2>, _Out>
2920 operator()(_Range1&& __r1, _Range2&& __r2,
2921 _Out __result, _Comp __comp = {},
2922 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 2931 inline constexpr __set_union_fn set_union{};
2933 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2934 using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2936 struct __set_intersection_fn
2938 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2939 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2940 weakly_incrementable _Out,
typename _Comp = ranges::less,
2941 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2942 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2943 constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2944 operator()(_Iter1 __first1, _Sent1 __last1,
2945 _Iter2 __first2, _Sent2 __last2, _Out __result,
2947 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 2949 while (__first1 != __last1 && __first2 != __last2)
2960 *__result = *__first1;
2971 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2972 typename _Comp = ranges::less,
2973 typename _Proj1 = identity,
typename _Proj2 = identity>
2974 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2975 _Comp, _Proj1, _Proj2>
2976 constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
2977 borrowed_iterator_t<_Range2>, _Out>
2978 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2980 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 2989 inline constexpr __set_intersection_fn set_intersection{};
2991 template<
typename _Iter,
typename _Out>
2992 using set_difference_result = in_out_result<_Iter, _Out>;
2994 struct __set_difference_fn
2996 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2997 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2998 weakly_incrementable _Out,
typename _Comp = ranges::less,
2999 typename _Proj1 =
identity,
typename _Proj2 =
identity>
3000 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
3001 constexpr set_difference_result<_Iter1, _Out>
3002 operator()(_Iter1 __first1, _Sent1 __last1,
3003 _Iter2 __first2, _Sent2 __last2, _Out __result,
3005 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 3007 while (__first1 != __last1 && __first2 != __last2)
3012 *__result = *__first1;
3029 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3030 typename _Comp = ranges::less,
3031 typename _Proj1 = identity,
typename _Proj2 = identity>
3032 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3033 _Comp, _Proj1, _Proj2>
3034 constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
3035 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
3037 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 3046 inline constexpr __set_difference_fn set_difference{};
3048 template<
typename _Iter1,
typename _Iter2,
typename _Out>
3049 using set_symmetric_difference_result
3050 = in_in_out_result<_Iter1, _Iter2, _Out>;
3052 struct __set_symmetric_difference_fn
3054 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3055 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3056 weakly_incrementable _Out,
typename _Comp = ranges::less,
3057 typename _Proj1 =
identity,
typename _Proj2 =
identity>
3058 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
3059 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
3060 operator()(_Iter1 __first1, _Sent1 __last1,
3061 _Iter2 __first2, _Sent2 __last2,
3062 _Out __result, _Comp __comp = {},
3063 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 3065 while (__first1 != __last1 && __first2 != __last2)
3070 *__result = *__first1;
3078 *__result = *__first2;
3095 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3096 typename _Comp = ranges::less,
3097 typename _Proj1 = identity,
typename _Proj2 = identity>
3098 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3099 _Comp, _Proj1, _Proj2>
3100 constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
3101 borrowed_iterator_t<_Range2>,
3103 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
3105 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 3114 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
3118 template<
typename _Tp,
typename _Proj = identity,
3119 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3120 _Comp = ranges::less>
3121 constexpr
const _Tp&
3122 operator()(
const _Tp& __a,
const _Tp& __b,
3123 _Comp __comp = {}, _Proj __proj = {})
const 3133 template<input_range _Range,
typename _Proj = identity,
3134 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3135 _Comp = ranges::less>
3136 requires indirectly_copyable_storable<iterator_t<_Range>,
3137 range_value_t<_Range>*>
3138 constexpr range_value_t<_Range>
3139 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 3143 __glibcxx_assert(__first != __last);
3144 auto __result = *__first;
3145 while (++__first != __last)
3147 auto __tmp = *__first;
3156 template<copyable _Tp,
typename _Proj = identity,
3157 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3158 _Comp = ranges::less>
3160 operator()(initializer_list<_Tp> __r,
3161 _Comp __comp = {}, _Proj __proj = {})
const 3163 return (*
this)(ranges::subrange(__r),
3168 inline constexpr __min_fn
min{};
3172 template<
typename _Tp,
typename _Proj = identity,
3173 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3174 _Comp = ranges::less>
3175 constexpr
const _Tp&
3176 operator()(
const _Tp& __a,
const _Tp& __b,
3177 _Comp __comp = {}, _Proj __proj = {})
const 3187 template<input_range _Range,
typename _Proj = identity,
3188 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3189 _Comp = ranges::less>
3190 requires indirectly_copyable_storable<iterator_t<_Range>,
3191 range_value_t<_Range>*>
3192 constexpr range_value_t<_Range>
3193 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 3197 __glibcxx_assert(__first != __last);
3198 auto __result = *__first;
3199 while (++__first != __last)
3201 auto __tmp = *__first;
3210 template<copyable _Tp,
typename _Proj = identity,
3211 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3212 _Comp = ranges::less>
3214 operator()(initializer_list<_Tp> __r,
3215 _Comp __comp = {}, _Proj __proj = {})
const 3217 return (*
this)(ranges::subrange(__r),
3222 inline constexpr __max_fn
max{};
3226 template<
typename _Tp,
typename _Proj = identity,
3227 indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
3229 constexpr
const _Tp&
3230 operator()(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi,
3231 _Comp __comp = {}, _Proj __proj = {})
const 3246 inline constexpr __clamp_fn
clamp{};
3248 template<
typename _Tp>
3249 struct min_max_result
3251 [[no_unique_address]] _Tp
min;
3252 [[no_unique_address]] _Tp
max;
3254 template<
typename _Tp2>
3255 requires convertible_to<const _Tp&, _Tp2>
3257 operator min_max_result<_Tp2>()
const &
3260 template<
typename _Tp2>
3261 requires convertible_to<_Tp, _Tp2>
3263 operator min_max_result<_Tp2>() &&
3267 template<
typename _Tp>
3268 using minmax_result = min_max_result<_Tp>;
3272 template<
typename _Tp,
typename _Proj = identity,
3273 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3274 _Comp = ranges::less>
3275 constexpr minmax_result<const _Tp&>
3276 operator()(
const _Tp& __a,
const _Tp& __b,
3277 _Comp __comp = {}, _Proj __proj = {})
const 3287 template<input_range _Range,
typename _Proj = identity,
3288 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3289 _Comp = ranges::less>
3290 requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
3291 constexpr minmax_result<range_value_t<_Range>>
3292 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 3296 __glibcxx_assert(__first != __last);
3297 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3298 minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
3299 if (++__first == __last)
3305 auto&& __val = *__first;
3306 if (__comp_proj(__val, __result.min))
3307 __result.min = std::forward<decltype(__val)>(__val);
3309 __result.max = std::forward<decltype(__val)>(__val);
3311 while (++__first != __last)
3316 range_value_t<_Range> __val1 = *__first;
3317 if (++__first == __last)
3322 if (__comp_proj(__val1, __result.min))
3324 else if (!__comp_proj(__val1, __result.max))
3328 auto&& __val2 = *__first;
3329 if (!__comp_proj(__val2, __val1))
3331 if (__comp_proj(__val1, __result.min))
3333 if (!__comp_proj(__val2, __result.max))
3338 if (__comp_proj(__val2, __result.min))
3340 if (!__comp_proj(__val1, __result.max))
3347 template<copyable _Tp,
typename _Proj = identity,
3348 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3349 _Comp = ranges::less>
3350 constexpr minmax_result<_Tp>
3351 operator()(initializer_list<_Tp> __r,
3352 _Comp __comp = {}, _Proj __proj = {})
const 3354 return (*
this)(ranges::subrange(__r),
3359 inline constexpr __minmax_fn
minmax{};
3361 struct __min_element_fn
3363 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3364 typename _Proj =
identity,
3365 indirect_strict_weak_order<projected<_Iter, _Proj>>
3366 _Comp = ranges::less>
3368 operator()(_Iter __first, _Sent __last,
3369 _Comp __comp = {}, _Proj __proj = {})
const 3371 if (__first == __last)
3375 while (++__i != __last)
3385 template<forward_range _Range,
typename _Proj = identity,
3386 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3387 _Comp = ranges::less>
3388 constexpr borrowed_iterator_t<_Range>
3389 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 3396 inline constexpr __min_element_fn min_element{};
3398 struct __max_element_fn
3400 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3401 typename _Proj =
identity,
3402 indirect_strict_weak_order<projected<_Iter, _Proj>>
3403 _Comp = ranges::less>
3405 operator()(_Iter __first, _Sent __last,
3406 _Comp __comp = {}, _Proj __proj = {})
const 3408 if (__first == __last)
3412 while (++__i != __last)
3422 template<forward_range _Range,
typename _Proj = identity,
3423 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3424 _Comp = ranges::less>
3425 constexpr borrowed_iterator_t<_Range>
3426 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 3433 inline constexpr __max_element_fn max_element{};
3435 template<
typename _Iter>
3436 using minmax_element_result = min_max_result<_Iter>;
3438 struct __minmax_element_fn
3440 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3441 typename _Proj =
identity,
3442 indirect_strict_weak_order<projected<_Iter, _Proj>>
3443 _Comp = ranges::less>
3444 constexpr minmax_element_result<_Iter>
3445 operator()(_Iter __first, _Sent __last,
3446 _Comp __comp = {}, _Proj __proj = {})
const 3448 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3449 minmax_element_result<_Iter> __result = {__first, __first};
3450 if (__first == __last || ++__first == __last)
3456 if (__comp_proj(*__first, *__result.min))
3457 __result.min = __first;
3459 __result.max = __first;
3461 while (++__first != __last)
3466 auto __prev = __first;
3467 if (++__first == __last)
3472 if (__comp_proj(*__prev, *__result.min))
3473 __result.min = __prev;
3474 else if (!__comp_proj(*__prev, *__result.max))
3475 __result.max = __prev;
3478 if (!__comp_proj(*__first, *__prev))
3480 if (__comp_proj(*__prev, *__result.min))
3481 __result.min = __prev;
3482 if (!__comp_proj(*__first, *__result.max))
3483 __result.max = __first;
3487 if (__comp_proj(*__first, *__result.min))
3488 __result.min = __first;
3489 if (!__comp_proj(*__prev, *__result.max))
3490 __result.max = __prev;
3496 template<forward_range _Range,
typename _Proj = identity,
3497 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3498 _Comp = ranges::less>
3499 constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3500 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 3507 inline constexpr __minmax_element_fn minmax_element{};
3509 struct __lexicographical_compare_fn
3511 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3512 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3513 typename _Proj1 =
identity,
typename _Proj2 =
identity,
3514 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3515 projected<_Iter2, _Proj2>>
3516 _Comp = ranges::less>
3518 operator()(_Iter1 __first1, _Sent1 __last1,
3519 _Iter2 __first2, _Sent2 __last2,
3521 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 3523 if constexpr (__detail::__is_normal_iterator<_Iter1>
3524 && same_as<_Iter1, _Sent1>)
3525 return (*
this)(__first1.base(), __last1.base(),
3529 else if constexpr (__detail::__is_normal_iterator<_Iter2>
3530 && same_as<_Iter2, _Sent2>)
3532 __first2.base(), __last2.base(),
3537 constexpr
bool __sized_iters
3538 = (sized_sentinel_for<_Sent1, _Iter1>
3539 && sized_sentinel_for<_Sent2, _Iter2>);
3540 if constexpr (__sized_iters)
3542 using _ValueType1 = iter_value_t<_Iter1>;
3543 using _ValueType2 = iter_value_t<_Iter2>;
3546 constexpr
bool __use_memcmp
3547 = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3548 && __ptr_to_nonvolatile<_Iter1>
3549 && __ptr_to_nonvolatile<_Iter2>
3550 && (is_same_v<_Comp, ranges::less>
3551 || is_same_v<_Comp, ranges::greater>)
3552 && is_same_v<_Proj1, identity>
3553 && is_same_v<_Proj2, identity>);
3554 if constexpr (__use_memcmp)
3556 const auto __d1 = __last1 - __first1;
3557 const auto __d2 = __last2 - __first2;
3559 if (
const auto __len =
std::min(__d1, __d2))
3562 = std::__memcmp(__first1, __first2, __len);
3563 if constexpr (is_same_v<_Comp, ranges::less>)
3570 else if constexpr (is_same_v<_Comp, ranges::greater>)
3582 for (; __first1 != __last1 && __first2 != __last2;
3583 ++__first1, (void) ++__first2)
3594 return __first1 == __last1 && __first2 != __last2;
3598 template<input_range _Range1, input_range _Range2,
3599 typename _Proj1 = identity,
typename _Proj2 = identity,
3600 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3601 projected<iterator_t<_Range2>, _Proj2>>
3602 _Comp = ranges::less>
3604 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3605 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const 3614 template<
typename _Iter,
typename _Ref = iter_reference_t<_Iter>>
3615 static constexpr
bool __ptr_to_nonvolatile
3616 = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3619 inline constexpr __lexicographical_compare_fn lexicographical_compare;
3621 template<
typename _Iter>
3622 struct in_found_result
3624 [[no_unique_address]] _Iter in;
3627 template<
typename _Iter2>
3628 requires convertible_to<const _Iter&, _Iter2>
3630 operator in_found_result<_Iter2>()
const &
3631 {
return {in, found}; }
3633 template<
typename _Iter2>
3634 requires convertible_to<_Iter, _Iter2>
3636 operator in_found_result<_Iter2>() &&
3640 template<
typename _Iter>
3641 using next_permutation_result = in_found_result<_Iter>;
3643 struct __next_permutation_fn
3645 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3646 typename _Comp = ranges::less,
typename _Proj =
identity>
3647 requires sortable<_Iter, _Comp, _Proj>
3648 constexpr next_permutation_result<_Iter>
3649 operator()(_Iter __first, _Sent __last,
3650 _Comp __comp = {}, _Proj __proj = {})
const 3652 if (__first == __last)
3660 auto __lasti = ranges::next(__first, __last);
3677 ranges::iter_swap(__i, __j);
3678 ranges::reverse(__ii, __last);
3683 ranges::reverse(__first, __last);
3689 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3690 typename _Proj = identity>
3691 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3692 constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3693 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 3700 inline constexpr __next_permutation_fn next_permutation{};
3702 template<
typename _Iter>
3703 using prev_permutation_result = in_found_result<_Iter>;
3705 struct __prev_permutation_fn
3707 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3708 typename _Comp = ranges::less,
typename _Proj =
identity>
3709 requires sortable<_Iter, _Comp, _Proj>
3710 constexpr prev_permutation_result<_Iter>
3711 operator()(_Iter __first, _Sent __last,
3712 _Comp __comp = {}, _Proj __proj = {})
const 3714 if (__first == __last)
3722 auto __lasti = ranges::next(__first, __last);
3739 ranges::iter_swap(__i, __j);
3740 ranges::reverse(__ii, __last);
3745 ranges::reverse(__first, __last);
3751 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3752 typename _Proj = identity>
3753 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3754 constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3755 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const 3762 inline constexpr __prev_permutation_fn prev_permutation{};
3766 #define __cpp_lib_shift 201806L 3767 template<
typename _ForwardIterator>
3768 constexpr _ForwardIterator
3769 shift_left(_ForwardIterator __first, _ForwardIterator __last,
3770 typename iterator_traits<_ForwardIterator>::difference_type __n)
3772 __glibcxx_assert(__n >= 0);
3776 auto __mid = ranges::next(__first, __n, __last);
3777 if (__mid == __last)
3782 template<
typename _ForwardIterator>
3783 constexpr _ForwardIterator
3784 shift_right(_ForwardIterator __first, _ForwardIterator __last,
3785 typename iterator_traits<_ForwardIterator>::difference_type __n)
3787 __glibcxx_assert(__n >= 0);
3792 =
typename iterator_traits<_ForwardIterator>::iterator_category;
3793 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
3795 auto __mid = ranges::next(__last, -__n, __first);
3796 if (__mid == __first)
3804 auto __result = ranges::next(__first, __n, __last);
3805 if (__result == __last)
3808 auto __dest_head = __first, __dest_tail = __result;
3809 while (__dest_head != __result)
3811 if (__dest_tail == __last)
3835 auto __cursor = __first;
3836 while (__cursor != __result)
3838 if (__dest_tail == __last)
3843 __dest_head =
std::move(__cursor, __result,
3858 _GLIBCXX_END_NAMESPACE_VERSION
3862 #endif // _RANGES_ALGO_H _Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
constexpr void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
constexpr _InputIterator for_each_n(_InputIterator __first, _Size __n, _Function __f)
Apply a function to every element of a sequence.
_SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomBitGenerator &&__g)
Take a random sample from a population.
_ForwardIterator stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
Move elements for which a predicate is true to the beginning of a sequence, preserving relative order...
void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort the elements of a sequence using a predicate for comparison, preserving the relative order of eq...
void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator &&__g)
Shuffle the elements of a sequence using a uniform random number generator.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Push an element onto a heap using comparison functor.
constexpr pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
void inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp)
Merges two sorted ranges in place.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
constexpr void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Pop an element off a heap using comparison functor.
ISO C++ entities toplevel namespace is std.
constexpr const _Tp & clamp(const _Tp &, const _Tp &, const _Tp &)
Returns the value clamped between lo and hi.
constexpr void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Construct a heap over a range using comparison functor.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort a heap using comparison functor.