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{};
1399 template<
typename _Iter,
typename _Out>
1400 using unique_copy_result = in_out_result<_Iter, _Out>;
1402 struct __unique_copy_fn
1404 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1405 weakly_incrementable _Out,
typename _Proj =
identity,
1406 indirect_equivalence_relation<
1407 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1408 requires indirectly_copyable<_Iter, _Out>
1409 && (forward_iterator<_Iter>
1410 || (input_iterator<_Out>
1411 && same_as<iter_value_t<_Iter>, iter_value_t<_Out>>)
1412 || indirectly_copyable_storable<_Iter, _Out>)
1413 constexpr unique_copy_result<_Iter, _Out>
1414 operator()(_Iter __first, _Sent __last, _Out __result,
1415 _Comp __comp = {}, _Proj __proj = {})
const
1417 if (__first == __last)
1421 if constexpr (forward_iterator<_Iter>)
1423 auto __next = __first;
1424 *__result = *__next;
1425 while (++__next != __last)
1431 *++__result = *__first;
1435 else if constexpr (input_iterator<_Out>
1436 && same_as<iter_value_t<_Iter>, iter_value_t<_Out>>)
1438 *__result = *__first;
1439 while (++__first != __last)
1443 *++__result = *__first;
1448 auto __value = *__first;
1449 *__result = __value;
1450 while (++__first != __last)
1457 *++__result = __value;
1464 template<input_range _Range,
1465 weakly_incrementable _Out,
typename _Proj = identity,
1466 indirect_equivalence_relation<
1467 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1468 requires indirectly_copyable<iterator_t<_Range>, _Out>
1469 && (forward_iterator<iterator_t<_Range>>
1470 || (input_iterator<_Out>
1471 && same_as<range_value_t<_Range>, iter_value_t<_Out>>)
1472 || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1473 constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1474 operator()(_Range&& __r, _Out __result,
1475 _Comp __comp = {}, _Proj __proj = {})
const
1483 inline constexpr __unique_copy_fn unique_copy{};
1487 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1488 requires permutable<_Iter>
1490 operator()(_Iter __first, _Sent __last)
const
1492 auto __i = ranges::next(__first, __last);
1495 if constexpr (random_access_iterator<_Iter>)
1497 if (__first != __last)
1500 while (__first < __tail)
1502 ranges::iter_swap(__first, __tail);
1512 if (__first == __tail || __first == --__tail)
1516 ranges::iter_swap(__first, __tail);
1523 template<b
idirectional_range _Range>
1524 requires permutable<iterator_t<_Range>>
1525 constexpr borrowed_iterator_t<_Range>
1526 operator()(_Range&& __r)
const
1532 inline constexpr __reverse_fn reverse{};
1534 template<
typename _Iter,
typename _Out>
1535 using reverse_copy_result = in_out_result<_Iter, _Out>;
1537 struct __reverse_copy_fn
1539 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1540 weakly_incrementable _Out>
1541 requires indirectly_copyable<_Iter, _Out>
1542 constexpr reverse_copy_result<_Iter, _Out>
1543 operator()(_Iter __first, _Sent __last, _Out __result)
const
1545 auto __i = ranges::next(__first, __last);
1547 while (__first != __tail)
1550 *__result = *__tail;
1553 return {__i, __result};
1556 template<b
idirectional_range _Range, weakly_incrementable _Out>
1557 requires indirectly_copyable<iterator_t<_Range>, _Out>
1558 constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1559 operator()(_Range&& __r, _Out __result)
const
1566 inline constexpr __reverse_copy_fn reverse_copy{};
1570 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1571 constexpr subrange<_Iter>
1572 operator()(_Iter __first, _Iter __middle, _Sent __last)
const
1574 auto __lasti = ranges::next(__first, __last);
1575 if (__first == __middle)
1576 return {__lasti, __lasti};
1577 if (__last == __middle)
1580 if constexpr (random_access_iterator<_Iter>)
1582 auto __n = __lasti - __first;
1583 auto __k = __middle - __first;
1585 if (__k == __n - __k)
1587 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1592 auto __ret = __first + (__lasti - __middle);
1596 if (__k < __n - __k)
1600 if constexpr (__is_pod(iter_value_t<_Iter>))
1608 auto __q = __p + __k;
1609 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1611 ranges::iter_swap(__p, __q);
1626 if constexpr (__is_pod(iter_value_t<_Iter>))
1634 auto __q = __p + __n;
1636 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1640 ranges::iter_swap(__p, __q);
1649 else if constexpr (bidirectional_iterator<_Iter>)
1651 auto __tail = __lasti;
1653 ranges::reverse(__first, __middle);
1654 ranges::reverse(__middle, __tail);
1656 while (__first != __middle && __middle != __tail)
1658 ranges::iter_swap(__first, --__tail);
1662 if (__first == __middle)
1664 ranges::reverse(__middle, __tail);
1669 ranges::reverse(__first, __middle);
1675 auto __first2 = __middle;
1678 ranges::iter_swap(__first, __first2);
1681 if (__first == __middle)
1682 __middle = __first2;
1683 }
while (__first2 != __last);
1685 auto __ret = __first;
1687 __first2 = __middle;
1689 while (__first2 != __last)
1691 ranges::iter_swap(__first, __first2);
1694 if (__first == __middle)
1695 __middle = __first2;
1696 else if (__first2 == __last)
1697 __first2 = __middle;
1703 template<forward_range _Range>
1704 requires permutable<iterator_t<_Range>>
1705 constexpr borrowed_subrange_t<_Range>
1706 operator()(_Range&& __r, iterator_t<_Range> __middle)
const
1713 inline constexpr __rotate_fn rotate{};
1715 template<
typename _Iter,
typename _Out>
1716 using rotate_copy_result = in_out_result<_Iter, _Out>;
1718 struct __rotate_copy_fn
1720 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1721 weakly_incrementable _Out>
1722 requires indirectly_copyable<_Iter, _Out>
1723 constexpr rotate_copy_result<_Iter, _Out>
1724 operator()(_Iter __first, _Iter __middle, _Sent __last,
1725 _Out __result)
const
1727 auto __copy1 = ranges::copy(__middle,
1730 auto __copy2 = ranges::copy(
std::move(__first),
1736 template<forward_range _Range, weakly_incrementable _Out>
1737 requires indirectly_copyable<iterator_t<_Range>, _Out>
1738 constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1739 operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result)
const
1746 inline constexpr __rotate_copy_fn rotate_copy{};
1750 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1751 weakly_incrementable _Out,
typename _Gen>
1752 requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
1753 && indirectly_copyable<_Iter, _Out>
1754 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1756 operator()(_Iter __first, _Sent __last, _Out __out,
1757 iter_difference_t<_Iter> __n, _Gen&& __g)
const
1759 if constexpr (forward_iterator<_Iter>)
1763 auto __lasti = ranges::next(__first, __last);
1766 __n, std::forward<_Gen>(__g));
1770 using __distrib_type
1771 = uniform_int_distribution<iter_difference_t<_Iter>>;
1772 using __param_type =
typename __distrib_type::param_type;
1773 __distrib_type __d{};
1774 iter_difference_t<_Iter> __sample_sz = 0;
1775 while (__first != __last && __sample_sz != __n)
1777 __out[__sample_sz++] = *__first;
1780 for (
auto __pop_sz = __sample_sz; __first != __last;
1781 ++__first, (void) ++__pop_sz)
1783 const auto __k = __d(__g, __param_type{0, __pop_sz});
1785 __out[__k] = *__first;
1787 return __out + __sample_sz;
1791 template<input_range _Range, weakly_incrementable _Out,
typename _Gen>
1792 requires (forward_range<_Range> || random_access_iterator<_Out>)
1793 && indirectly_copyable<iterator_t<_Range>, _Out>
1794 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1796 operator()(_Range&& __r, _Out __out,
1797 range_difference_t<_Range> __n, _Gen&& __g)
const
1801 std::forward<_Gen>(__g));
1805 inline constexpr __sample_fn
sample{};
1807 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
1810 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1812 requires permutable<_Iter>
1813 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1815 operator()(_Iter __first, _Sent __last, _Gen&& __g)
const
1817 auto __lasti = ranges::next(__first, __last);
1818 std::shuffle(
std::move(__first), __lasti, std::forward<_Gen>(__g));
1822 template<random_access_range _Range,
typename _Gen>
1823 requires permutable<iterator_t<_Range>>
1824 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1825 borrowed_iterator_t<_Range>
1826 operator()(_Range&& __r, _Gen&& __g)
const
1829 std::forward<_Gen>(__g));
1833 inline constexpr __shuffle_fn shuffle{};
1836 struct __push_heap_fn
1838 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1839 typename _Comp = ranges::less,
typename _Proj =
identity>
1840 requires sortable<_Iter, _Comp, _Proj>
1842 operator()(_Iter __first, _Sent __last,
1843 _Comp __comp = {}, _Proj __proj = {})
const
1845 auto __lasti = ranges::next(__first, __last);
1846 std::push_heap(__first, __lasti,
1847 __detail::__make_comp_proj(__comp, __proj));
1851 template<random_access_range _Range,
1852 typename _Comp = ranges::less,
typename _Proj = identity>
1853 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1854 constexpr borrowed_iterator_t<_Range>
1855 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1862 inline constexpr __push_heap_fn push_heap{};
1864 struct __pop_heap_fn
1866 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1867 typename _Comp = ranges::less,
typename _Proj =
identity>
1868 requires sortable<_Iter, _Comp, _Proj>
1870 operator()(_Iter __first, _Sent __last,
1871 _Comp __comp = {}, _Proj __proj = {})
const
1873 auto __lasti = ranges::next(__first, __last);
1874 std::pop_heap(__first, __lasti,
1875 __detail::__make_comp_proj(__comp, __proj));
1879 template<random_access_range _Range,
1880 typename _Comp = ranges::less,
typename _Proj = identity>
1881 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1882 constexpr borrowed_iterator_t<_Range>
1883 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1890 inline constexpr __pop_heap_fn pop_heap{};
1892 struct __make_heap_fn
1894 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1895 typename _Comp = ranges::less,
typename _Proj =
identity>
1896 requires sortable<_Iter, _Comp, _Proj>
1898 operator()(_Iter __first, _Sent __last,
1899 _Comp __comp = {}, _Proj __proj = {})
const
1901 auto __lasti = ranges::next(__first, __last);
1902 std::make_heap(__first, __lasti,
1903 __detail::__make_comp_proj(__comp, __proj));
1907 template<random_access_range _Range,
1908 typename _Comp = ranges::less,
typename _Proj = identity>
1909 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1910 constexpr borrowed_iterator_t<_Range>
1911 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1918 inline constexpr __make_heap_fn make_heap{};
1920 struct __sort_heap_fn
1922 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1923 typename _Comp = ranges::less,
typename _Proj =
identity>
1924 requires sortable<_Iter, _Comp, _Proj>
1926 operator()(_Iter __first, _Sent __last,
1927 _Comp __comp = {}, _Proj __proj = {})
const
1929 auto __lasti = ranges::next(__first, __last);
1930 std::sort_heap(__first, __lasti,
1931 __detail::__make_comp_proj(__comp, __proj));
1935 template<random_access_range _Range,
1936 typename _Comp = ranges::less,
typename _Proj = identity>
1937 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1938 constexpr borrowed_iterator_t<_Range>
1939 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1946 inline constexpr __sort_heap_fn sort_heap{};
1948 struct __is_heap_until_fn
1950 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1951 typename _Proj =
identity,
1952 indirect_strict_weak_order<projected<_Iter, _Proj>>
1953 _Comp = ranges::less>
1955 operator()(_Iter __first, _Sent __last,
1956 _Comp __comp = {}, _Proj __proj = {})
const
1958 iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
1959 iter_difference_t<_Iter> __parent = 0, __child = 1;
1960 for (; __child < __n; ++__child)
1964 return __first + __child;
1965 else if ((__child & 1) == 0)
1968 return __first + __n;
1971 template<random_access_range _Range,
1972 typename _Proj = identity,
1973 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1974 _Comp = ranges::less>
1975 constexpr borrowed_iterator_t<_Range>
1976 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1983 inline constexpr __is_heap_until_fn is_heap_until{};
1987 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1988 typename _Proj =
identity,
1989 indirect_strict_weak_order<projected<_Iter, _Proj>>
1990 _Comp = ranges::less>
1992 operator()(_Iter __first, _Sent __last,
1993 _Comp __comp = {}, _Proj __proj = {})
const
1996 == ranges::is_heap_until(__first, __last,
2001 template<random_access_range _Range,
2002 typename _Proj = identity,
2003 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2004 _Comp = ranges::less>
2006 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2013 inline constexpr __is_heap_fn is_heap{};
2017 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2018 typename _Comp = ranges::less,
typename _Proj =
identity>
2019 requires sortable<_Iter, _Comp, _Proj>
2021 operator()(_Iter __first, _Sent __last,
2022 _Comp __comp = {}, _Proj __proj = {})
const
2024 auto __lasti = ranges::next(__first, __last);
2025 _GLIBCXX_STD_A::sort(
std::move(__first), __lasti,
2026 __detail::__make_comp_proj(__comp, __proj));
2030 template<random_access_range _Range,
2031 typename _Comp = ranges::less,
typename _Proj = identity>
2032 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2033 constexpr borrowed_iterator_t<_Range>
2034 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2041 inline constexpr __sort_fn sort{};
2043 struct __stable_sort_fn
2045 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2046 typename _Comp = ranges::less,
typename _Proj =
identity>
2047 requires sortable<_Iter, _Comp, _Proj>
2049 operator()(_Iter __first, _Sent __last,
2050 _Comp __comp = {}, _Proj __proj = {})
const
2052 auto __lasti = ranges::next(__first, __last);
2053 std::stable_sort(
std::move(__first), __lasti,
2054 __detail::__make_comp_proj(__comp, __proj));
2058 template<random_access_range _Range,
2059 typename _Comp = ranges::less,
typename _Proj = identity>
2060 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2061 borrowed_iterator_t<_Range>
2062 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2069 inline constexpr __stable_sort_fn stable_sort{};
2071 struct __partial_sort_fn
2073 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2074 typename _Comp = ranges::less,
typename _Proj =
identity>
2075 requires sortable<_Iter, _Comp, _Proj>
2077 operator()(_Iter __first, _Iter __middle, _Sent __last,
2078 _Comp __comp = {}, _Proj __proj = {})
const
2080 if (__first == __middle)
2081 return ranges::next(__first, __last);
2083 ranges::make_heap(__first, __middle, __comp, __proj);
2084 auto __i = __middle;
2085 for (; __i != __last; ++__i)
2090 ranges::pop_heap(__first, __middle, __comp, __proj);
2091 ranges::iter_swap(__middle-1, __i);
2092 ranges::push_heap(__first, __middle, __comp, __proj);
2094 ranges::sort_heap(__first, __middle, __comp, __proj);
2099 template<random_access_range _Range,
2100 typename _Comp = ranges::less,
typename _Proj = identity>
2101 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2102 constexpr borrowed_iterator_t<_Range>
2103 operator()(_Range&& __r, iterator_t<_Range> __middle,
2104 _Comp __comp = {}, _Proj __proj = {})
const
2112 inline constexpr __partial_sort_fn partial_sort{};
2114 template<
typename _Iter,
typename _Out>
2115 using partial_sort_copy_result = in_out_result<_Iter, _Out>;
2117 struct __partial_sort_copy_fn
2119 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2120 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2121 typename _Comp = ranges::less,
2122 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2123 requires indirectly_copyable<_Iter1, _Iter2>
2124 && sortable<_Iter2, _Comp, _Proj2>
2125 && indirect_strict_weak_order<_Comp,
2126 projected<_Iter1, _Proj1>,
2127 projected<_Iter2, _Proj2>>
2128 constexpr partial_sort_copy_result<_Iter1, _Iter2>
2129 operator()(_Iter1 __first, _Sent1 __last,
2130 _Iter2 __result_first, _Sent2 __result_last,
2132 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2134 if (__result_first == __result_last)
2137 auto __lasti = ranges::next(
std::move(__first),
2142 auto __result_real_last = __result_first;
2143 while (__first != __last && __result_real_last != __result_last)
2145 *__result_real_last = *__first;
2146 ++__result_real_last;
2150 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
2151 for (; __first != __last; ++__first)
2156 ranges::pop_heap(__result_first, __result_real_last,
2158 *(__result_real_last-1) = *__first;
2159 ranges::push_heap(__result_first, __result_real_last,
2162 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
2167 template<input_range _Range1, random_access_range _Range2,
2168 typename _Comp = ranges::less,
2169 typename _Proj1 = identity,
typename _Proj2 = identity>
2170 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
2171 && sortable<iterator_t<_Range2>, _Comp, _Proj2>
2172 && indirect_strict_weak_order<_Comp,
2173 projected<iterator_t<_Range1>, _Proj1>,
2174 projected<iterator_t<_Range2>, _Proj2>>
2175 constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
2176 borrowed_iterator_t<_Range2>>
2177 operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
2178 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2187 inline constexpr __partial_sort_copy_fn partial_sort_copy{};
2189 struct __is_sorted_until_fn
2191 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2192 typename _Proj =
identity,
2193 indirect_strict_weak_order<projected<_Iter, _Proj>>
2194 _Comp = ranges::less>
2196 operator()(_Iter __first, _Sent __last,
2197 _Comp __comp = {}, _Proj __proj = {})
const
2199 if (__first == __last)
2202 auto __next = __first;
2203 for (++__next; __next != __last; __first = __next, (void)++__next)
2211 template<forward_range _Range,
typename _Proj = identity,
2212 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2213 _Comp = ranges::less>
2214 constexpr borrowed_iterator_t<_Range>
2215 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2222 inline constexpr __is_sorted_until_fn is_sorted_until{};
2224 struct __is_sorted_fn
2226 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2227 typename _Proj =
identity,
2228 indirect_strict_weak_order<projected<_Iter, _Proj>>
2229 _Comp = ranges::less>
2231 operator()(_Iter __first, _Sent __last,
2232 _Comp __comp = {}, _Proj __proj = {})
const
2234 if (__first == __last)
2237 auto __next = __first;
2238 for (++__next; __next != __last; __first = __next, (void)++__next)
2246 template<forward_range _Range,
typename _Proj = identity,
2247 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2248 _Comp = ranges::less>
2250 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2257 inline constexpr __is_sorted_fn is_sorted{};
2259 struct __nth_element_fn
2261 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2262 typename _Comp = ranges::less,
typename _Proj =
identity>
2263 requires sortable<_Iter, _Comp, _Proj>
2265 operator()(_Iter __first, _Iter __nth, _Sent __last,
2266 _Comp __comp = {}, _Proj __proj = {})
const
2268 auto __lasti = ranges::next(__first, __last);
2271 __detail::__make_comp_proj(__comp, __proj));
2275 template<random_access_range _Range,
2276 typename _Comp = ranges::less,
typename _Proj = identity>
2277 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2278 constexpr borrowed_iterator_t<_Range>
2279 operator()(_Range&& __r, iterator_t<_Range> __nth,
2280 _Comp __comp = {}, _Proj __proj = {})
const
2287 inline constexpr __nth_element_fn nth_element{};
2289 struct __lower_bound_fn
2291 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2292 typename _Tp,
typename _Proj =
identity,
2293 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2294 _Comp = ranges::less>
2296 operator()(_Iter __first, _Sent __last,
2297 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2299 auto __len = ranges::distance(__first, __last);
2303 auto __half = __len / 2;
2304 auto __middle = __first;
2305 ranges::advance(__middle, __half);
2310 __len = __len - __half - 1;
2318 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2319 indirect_strict_weak_order<
const _Tp*,
2320 projected<iterator_t<_Range>, _Proj>>
2321 _Comp = ranges::less>
2322 constexpr borrowed_iterator_t<_Range>
2323 operator()(_Range&& __r,
2324 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2331 inline constexpr __lower_bound_fn lower_bound{};
2333 struct __upper_bound_fn
2335 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2336 typename _Tp,
typename _Proj =
identity,
2337 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2338 _Comp = ranges::less>
2340 operator()(_Iter __first, _Sent __last,
2341 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2343 auto __len = ranges::distance(__first, __last);
2347 auto __half = __len / 2;
2348 auto __middle = __first;
2349 ranges::advance(__middle, __half);
2356 __len = __len - __half - 1;
2362 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2363 indirect_strict_weak_order<
const _Tp*,
2364 projected<iterator_t<_Range>, _Proj>>
2365 _Comp = ranges::less>
2366 constexpr borrowed_iterator_t<_Range>
2367 operator()(_Range&& __r,
2368 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2375 inline constexpr __upper_bound_fn upper_bound{};
2377 struct __equal_range_fn
2379 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2380 typename _Tp,
typename _Proj =
identity,
2381 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2382 _Comp = ranges::less>
2383 constexpr subrange<_Iter>
2384 operator()(_Iter __first, _Sent __last,
2385 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2387 auto __len = ranges::distance(__first, __last);
2391 auto __half = __len / 2;
2392 auto __middle = __first;
2393 ranges::advance(__middle, __half);
2400 __len = __len - __half - 1;
2409 = ranges::lower_bound(__first, __middle,
2410 __value, __comp, __proj);
2411 ranges::advance(__first, __len);
2413 = ranges::upper_bound(++__middle, __first,
2414 __value, __comp, __proj);
2415 return {__left, __right};
2418 return {__first, __first};
2421 template<forward_range _Range,
2422 typename _Tp,
typename _Proj = identity,
2423 indirect_strict_weak_order<
const _Tp*,
2424 projected<iterator_t<_Range>, _Proj>>
2425 _Comp = ranges::less>
2426 constexpr borrowed_subrange_t<_Range>
2427 operator()(_Range&& __r,
const _Tp& __value,
2428 _Comp __comp = {}, _Proj __proj = {})
const
2435 inline constexpr __equal_range_fn equal_range{};
2437 struct __binary_search_fn
2439 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2440 typename _Tp,
typename _Proj =
identity,
2441 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2442 _Comp = ranges::less>
2444 operator()(_Iter __first, _Sent __last,
2445 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2447 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2454 template<forward_range _Range,
2455 typename _Tp,
typename _Proj = identity,
2456 indirect_strict_weak_order<
const _Tp*,
2457 projected<iterator_t<_Range>, _Proj>>
2458 _Comp = ranges::less>
2460 operator()(_Range&& __r,
const _Tp& __value, _Comp __comp = {},
2461 _Proj __proj = {})
const
2468 inline constexpr __binary_search_fn binary_search{};
2470 struct __is_partitioned_fn
2472 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2473 typename _Proj =
identity,
2474 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2476 operator()(_Iter __first, _Sent __last,
2477 _Pred __pred, _Proj __proj = {})
const
2479 __first = ranges::find_if_not(
std::move(__first), __last,
2481 if (__first == __last)
2488 template<input_range _Range,
typename _Proj = identity,
2489 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2492 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2499 inline constexpr __is_partitioned_fn is_partitioned{};
2501 struct __partition_fn
2503 template<permutable _Iter, sentinel_for<_Iter> _Sent,
2504 typename _Proj =
identity,
2505 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2506 constexpr subrange<_Iter>
2507 operator()(_Iter __first, _Sent __last,
2508 _Pred __pred, _Proj __proj = {})
const
2510 if constexpr (bidirectional_iterator<_Iter>)
2512 auto __lasti = ranges::next(__first, __last);
2513 auto __tail = __lasti;
2517 if (__first == __tail)
2526 if (__first == __tail)
2533 ranges::iter_swap(__first, __tail);
2539 if (__first == __last)
2543 if (++__first == __last)
2546 auto __next = __first;
2547 while (++__next != __last)
2550 ranges::iter_swap(__first, __next);
2558 template<forward_range _Range,
typename _Proj = identity,
2559 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2561 requires permutable<iterator_t<_Range>>
2562 constexpr borrowed_subrange_t<_Range>
2563 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2570 inline constexpr __partition_fn partition{};
2572 struct __stable_partition_fn
2574 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2575 typename _Proj =
identity,
2576 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2577 requires permutable<_Iter>
2579 operator()(_Iter __first, _Sent __last,
2580 _Pred __pred, _Proj __proj = {})
const
2582 auto __lasti = ranges::next(__first, __last);
2584 = std::stable_partition(
std::move(__first), __lasti,
2585 __detail::__make_pred_proj(__pred, __proj));
2589 template<bidirectional_range _Range,
typename _Proj = identity,
2590 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2592 requires permutable<iterator_t<_Range>>
2593 borrowed_subrange_t<_Range>
2594 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2601 inline constexpr __stable_partition_fn stable_partition{};
2603 template<
typename _Iter,
typename _Out1,
typename _Out2>
2604 struct in_out_out_result
2606 [[no_unique_address]] _Iter in;
2607 [[no_unique_address]] _Out1 out1;
2608 [[no_unique_address]] _Out2 out2;
2610 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2611 requires convertible_to<const _Iter&, _IIter>
2612 && convertible_to<const _Out1&, _OOut1>
2613 && convertible_to<const _Out2&, _OOut2>
2615 operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
2616 {
return {in, out1, out2}; }
2618 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2619 requires convertible_to<_Iter, _IIter>
2620 && convertible_to<_Out1, _OOut1>
2621 && convertible_to<_Out2, _OOut2>
2623 operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2627 template<
typename _Iter,
typename _Out1,
typename _Out2>
2628 using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2630 struct __partition_copy_fn
2632 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2633 weakly_incrementable _Out1, weakly_incrementable _O2,
2634 typename _Proj =
identity,
2635 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2636 requires indirectly_copyable<_Iter, _Out1>
2637 && indirectly_copyable<_Iter, _O2>
2638 constexpr partition_copy_result<_Iter, _Out1, _O2>
2639 operator()(_Iter __first, _Sent __last,
2640 _Out1 __out_true, _O2 __out_false,
2641 _Pred __pred, _Proj __proj = {})
const
2643 for (; __first != __last; ++__first)
2646 *__out_true = *__first;
2651 *__out_false = *__first;
2659 template<input_range _Range, weakly_incrementable _Out1,
2660 weakly_incrementable _O2,
2661 typename _Proj = identity,
2662 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2664 requires indirectly_copyable<iterator_t<_Range>, _Out1>
2665 && indirectly_copyable<iterator_t<_Range>, _O2>
2666 constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _O2>
2667 operator()(_Range&& __r, _Out1 out_true, _O2 out_false,
2668 _Pred __pred, _Proj __proj = {})
const
2676 inline constexpr __partition_copy_fn partition_copy{};
2678 struct __partition_point_fn
2680 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2681 typename _Proj =
identity,
2682 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2684 operator()(_Iter __first, _Sent __last,
2685 _Pred __pred, _Proj __proj = {})
const
2687 auto __len = ranges::distance(__first, __last);
2691 auto __half = __len / 2;
2692 auto __middle = __first;
2693 ranges::advance(__middle, __half);
2698 __len = __len - __half - 1;
2706 template<forward_range _Range,
typename _Proj = identity,
2707 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2709 constexpr borrowed_iterator_t<_Range>
2710 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2717 inline constexpr __partition_point_fn partition_point{};
2719 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2720 using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2724 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2725 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2726 weakly_incrementable _Out,
typename _Comp = ranges::less,
2727 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2728 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2729 constexpr merge_result<_Iter1, _Iter2, _Out>
2730 operator()(_Iter1 __first1, _Sent1 __last1,
2731 _Iter2 __first2, _Sent2 __last2, _Out __result,
2733 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2735 while (__first1 != __last1 && __first2 != __last2)
2741 *__result = *__first2;
2746 *__result = *__first1;
2759 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2760 typename _Comp = ranges::less,
2761 typename _Proj1 = identity,
typename _Proj2 = identity>
2762 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2763 _Comp, _Proj1, _Proj2>
2764 constexpr merge_result<borrowed_iterator_t<_Range1>,
2765 borrowed_iterator_t<_Range2>,
2767 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2769 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2778 inline constexpr __merge_fn merge{};
2780 struct __inplace_merge_fn
2782 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2783 typename _Comp = ranges::less,
2784 typename _Proj =
identity>
2785 requires sortable<_Iter, _Comp, _Proj>
2787 operator()(_Iter __first, _Iter __middle, _Sent __last,
2788 _Comp __comp = {}, _Proj __proj = {})
const
2790 auto __lasti = ranges::next(__first, __last);
2792 __detail::__make_comp_proj(__comp, __proj));
2796 template<bidirectional_range _Range,
2797 typename _Comp = ranges::less,
typename _Proj = identity>
2798 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2799 borrowed_iterator_t<_Range>
2800 operator()(_Range&& __r, iterator_t<_Range> __middle,
2801 _Comp __comp = {}, _Proj __proj = {})
const
2809 inline constexpr __inplace_merge_fn inplace_merge{};
2811 struct __includes_fn
2813 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2814 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2815 typename _Proj1 =
identity,
typename _Proj2 =
identity,
2816 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2817 projected<_Iter2, _Proj2>>
2818 _Comp = ranges::less>
2820 operator()(_Iter1 __first1, _Sent1 __last1,
2821 _Iter2 __first2, _Sent2 __last2,
2823 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2825 while (__first1 != __last1 && __first2 != __last2)
2840 return __first2 == __last2;
2843 template<input_range _Range1, input_range _Range2,
2844 typename _Proj1 = identity,
typename _Proj2 = identity,
2845 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2846 projected<iterator_t<_Range2>, _Proj2>>
2847 _Comp = ranges::less>
2849 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2850 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2859 inline constexpr __includes_fn includes{};
2861 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2862 using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2864 struct __set_union_fn
2866 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2867 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2868 weakly_incrementable _Out,
typename _Comp = ranges::less,
2869 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2870 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2871 constexpr set_union_result<_Iter1, _Iter2, _Out>
2872 operator()(_Iter1 __first1, _Sent1 __last1,
2873 _Iter2 __first2, _Sent2 __last2,
2874 _Out __result, _Comp __comp = {},
2875 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2877 while (__first1 != __last1 && __first2 != __last2)
2883 *__result = *__first1;
2890 *__result = *__first2;
2895 *__result = *__first1;
2909 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2910 typename _Comp = ranges::less,
2911 typename _Proj1 = identity,
typename _Proj2 = identity>
2912 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2913 _Comp, _Proj1, _Proj2>
2914 constexpr set_union_result<borrowed_iterator_t<_Range1>,
2915 borrowed_iterator_t<_Range2>, _Out>
2916 operator()(_Range1&& __r1, _Range2&& __r2,
2917 _Out __result, _Comp __comp = {},
2918 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2927 inline constexpr __set_union_fn set_union{};
2929 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2930 using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2932 struct __set_intersection_fn
2934 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2935 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2936 weakly_incrementable _Out,
typename _Comp = ranges::less,
2937 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2938 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2939 constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2940 operator()(_Iter1 __first1, _Sent1 __last1,
2941 _Iter2 __first2, _Sent2 __last2, _Out __result,
2943 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2945 while (__first1 != __last1 && __first2 != __last2)
2956 *__result = *__first1;
2967 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2968 typename _Comp = ranges::less,
2969 typename _Proj1 = identity,
typename _Proj2 = identity>
2970 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2971 _Comp, _Proj1, _Proj2>
2972 constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
2973 borrowed_iterator_t<_Range2>, _Out>
2974 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2976 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2985 inline constexpr __set_intersection_fn set_intersection{};
2987 template<
typename _Iter,
typename _Out>
2988 using set_difference_result = in_out_result<_Iter, _Out>;
2990 struct __set_difference_fn
2992 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2993 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2994 weakly_incrementable _Out,
typename _Comp = ranges::less,
2995 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2996 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2997 constexpr set_difference_result<_Iter1, _Out>
2998 operator()(_Iter1 __first1, _Sent1 __last1,
2999 _Iter2 __first2, _Sent2 __last2, _Out __result,
3001 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3003 while (__first1 != __last1 && __first2 != __last2)
3008 *__result = *__first1;
3025 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3026 typename _Comp = ranges::less,
3027 typename _Proj1 = identity,
typename _Proj2 = identity>
3028 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3029 _Comp, _Proj1, _Proj2>
3030 constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
3031 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
3033 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3042 inline constexpr __set_difference_fn set_difference{};
3044 template<
typename _Iter1,
typename _Iter2,
typename _Out>
3045 using set_symmetric_difference_result
3046 = in_in_out_result<_Iter1, _Iter2, _Out>;
3048 struct __set_symmetric_difference_fn
3050 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3051 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3052 weakly_incrementable _Out,
typename _Comp = ranges::less,
3053 typename _Proj1 =
identity,
typename _Proj2 =
identity>
3054 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
3055 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
3056 operator()(_Iter1 __first1, _Sent1 __last1,
3057 _Iter2 __first2, _Sent2 __last2,
3058 _Out __result, _Comp __comp = {},
3059 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3061 while (__first1 != __last1 && __first2 != __last2)
3066 *__result = *__first1;
3074 *__result = *__first2;
3091 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3092 typename _Comp = ranges::less,
3093 typename _Proj1 = identity,
typename _Proj2 = identity>
3094 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3095 _Comp, _Proj1, _Proj2>
3096 constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
3097 borrowed_iterator_t<_Range2>,
3099 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
3101 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3110 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
3114 template<
typename _Tp,
typename _Proj = identity,
3115 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3116 _Comp = ranges::less>
3117 constexpr
const _Tp&
3118 operator()(
const _Tp& __a,
const _Tp& __b,
3119 _Comp __comp = {}, _Proj __proj = {})
const
3129 template<input_range _Range,
typename _Proj = identity,
3130 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3131 _Comp = ranges::less>
3132 requires indirectly_copyable_storable<iterator_t<_Range>,
3133 range_value_t<_Range>*>
3134 constexpr range_value_t<_Range>
3135 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3139 __glibcxx_assert(__first != __last);
3140 auto __result = *__first;
3141 while (++__first != __last)
3143 auto __tmp = *__first;
3152 template<copyable _Tp,
typename _Proj = identity,
3153 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3154 _Comp = ranges::less>
3156 operator()(initializer_list<_Tp> __r,
3157 _Comp __comp = {}, _Proj __proj = {})
const
3159 return (*
this)(ranges::subrange(__r),
3164 inline constexpr __min_fn
min{};
3168 template<
typename _Tp,
typename _Proj = identity,
3169 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3170 _Comp = ranges::less>
3171 constexpr
const _Tp&
3172 operator()(
const _Tp& __a,
const _Tp& __b,
3173 _Comp __comp = {}, _Proj __proj = {})
const
3183 template<input_range _Range,
typename _Proj = identity,
3184 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3185 _Comp = ranges::less>
3186 requires indirectly_copyable_storable<iterator_t<_Range>,
3187 range_value_t<_Range>*>
3188 constexpr range_value_t<_Range>
3189 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3193 __glibcxx_assert(__first != __last);
3194 auto __result = *__first;
3195 while (++__first != __last)
3197 auto __tmp = *__first;
3206 template<copyable _Tp,
typename _Proj = identity,
3207 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3208 _Comp = ranges::less>
3210 operator()(initializer_list<_Tp> __r,
3211 _Comp __comp = {}, _Proj __proj = {})
const
3213 return (*
this)(ranges::subrange(__r),
3218 inline constexpr __max_fn
max{};
3222 template<
typename _Tp,
typename _Proj = identity,
3223 indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
3225 constexpr
const _Tp&
3226 operator()(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi,
3227 _Comp __comp = {}, _Proj __proj = {})
const
3242 inline constexpr __clamp_fn
clamp{};
3244 template<
typename _Tp>
3245 struct min_max_result
3247 [[no_unique_address]] _Tp
min;
3248 [[no_unique_address]] _Tp
max;
3250 template<
typename _Tp2>
3251 requires convertible_to<const _Tp&, _Tp2>
3253 operator min_max_result<_Tp2>() const &
3256 template<
typename _Tp2>
3257 requires convertible_to<_Tp, _Tp2>
3259 operator min_max_result<_Tp2>() &&
3263 template<
typename _Tp>
3264 using minmax_result = min_max_result<_Tp>;
3268 template<
typename _Tp,
typename _Proj = identity,
3269 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3270 _Comp = ranges::less>
3271 constexpr minmax_result<const _Tp&>
3272 operator()(
const _Tp& __a,
const _Tp& __b,
3273 _Comp __comp = {}, _Proj __proj = {})
const
3283 template<input_range _Range,
typename _Proj = identity,
3284 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3285 _Comp = ranges::less>
3286 requires indirectly_copyable_storable<iterator_t<_Range>,
3287 range_value_t<_Range>*>
3288 constexpr minmax_result<range_value_t<_Range>>
3289 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3293 __glibcxx_assert(__first != __last);
3294 minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
3295 while (++__first != __last)
3297 auto __tmp = *__first;
3310 template<copyable _Tp,
typename _Proj = identity,
3311 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3312 _Comp = ranges::less>
3313 constexpr minmax_result<_Tp>
3314 operator()(initializer_list<_Tp> __r,
3315 _Comp __comp = {}, _Proj __proj = {})
const
3317 return (*
this)(ranges::subrange(__r),
3322 inline constexpr __minmax_fn
minmax{};
3324 struct __min_element_fn
3326 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3327 typename _Proj =
identity,
3328 indirect_strict_weak_order<projected<_Iter, _Proj>>
3329 _Comp = ranges::less>
3331 operator()(_Iter __first, _Sent __last,
3332 _Comp __comp = {}, _Proj __proj = {})
const
3334 if (__first == __last)
3338 while (++__i != __last)
3348 template<forward_range _Range,
typename _Proj = identity,
3349 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3350 _Comp = ranges::less>
3351 constexpr borrowed_iterator_t<_Range>
3352 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3359 inline constexpr __min_element_fn min_element{};
3361 struct __max_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 __max_element_fn max_element{};
3398 template<
typename _Iter>
3399 using minmax_element_result = min_max_result<_Iter>;
3401 struct __minmax_element_fn
3403 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3404 typename _Proj =
identity,
3405 indirect_strict_weak_order<projected<_Iter, _Proj>>
3406 _Comp = ranges::less>
3407 constexpr minmax_element_result<_Iter>
3408 operator()(_Iter __first, _Sent __last,
3409 _Comp __comp = {}, _Proj __proj = {})
const
3411 if (__first == __last)
3412 return {__first, __first};
3414 minmax_element_result<_Iter> __result = {__first, __first};
3416 while (++__i != __last)
3430 template<forward_range _Range,
typename _Proj = identity,
3431 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3432 _Comp = ranges::less>
3433 constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3434 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3441 inline constexpr __minmax_element_fn minmax_element{};
3443 struct __lexicographical_compare_fn
3445 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3446 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3447 typename _Proj1 =
identity,
typename _Proj2 =
identity,
3448 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3449 projected<_Iter2, _Proj2>>
3450 _Comp = ranges::less>
3452 operator()(_Iter1 __first1, _Sent1 __last1,
3453 _Iter2 __first2, _Sent2 __last2,
3455 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3457 if constexpr (__detail::__is_normal_iterator<_Iter1>
3458 && same_as<_Iter1, _Sent1>)
3459 return (*
this)(__first1.base(), __last1.base(),
3463 else if constexpr (__detail::__is_normal_iterator<_Iter2>
3464 && same_as<_Iter2, _Sent2>)
3466 __first2.base(), __last2.base(),
3471 constexpr
bool __sized_iters
3472 = (sized_sentinel_for<_Sent1, _Iter1>
3473 && sized_sentinel_for<_Sent2, _Iter2>);
3474 if constexpr (__sized_iters)
3476 using _ValueType1 = iter_value_t<_Iter1>;
3477 using _ValueType2 = iter_value_t<_Iter2>;
3480 constexpr
bool __use_memcmp
3481 = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3482 && __ptr_to_nonvolatile<_Iter1>
3483 && __ptr_to_nonvolatile<_Iter2>
3484 && (is_same_v<_Comp, ranges::less>
3485 || is_same_v<_Comp, ranges::greater>)
3486 && is_same_v<_Proj1, identity>
3487 && is_same_v<_Proj2, identity>);
3488 if constexpr (__use_memcmp)
3490 const auto __d1 = __last1 - __first1;
3491 const auto __d2 = __last2 - __first2;
3493 if (
const auto __len =
std::min(__d1, __d2))
3496 = std::__memcmp(__first1, __first2, __len);
3497 if constexpr (is_same_v<_Comp, ranges::less>)
3504 else if constexpr (is_same_v<_Comp, ranges::greater>)
3516 for (; __first1 != __last1 && __first2 != __last2;
3517 ++__first1, (void) ++__first2)
3528 return __first1 == __last1 && __first2 != __last2;
3532 template<input_range _Range1, input_range _Range2,
3533 typename _Proj1 = identity,
typename _Proj2 = identity,
3534 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3535 projected<iterator_t<_Range2>, _Proj2>>
3536 _Comp = ranges::less>
3538 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3539 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3548 template<
typename _Iter,
typename _Ref = iter_reference_t<_Iter>>
3549 static constexpr
bool __ptr_to_nonvolatile
3550 = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3553 inline constexpr __lexicographical_compare_fn lexicographical_compare;
3555 template<
typename _Iter>
3556 struct in_found_result
3558 [[no_unique_address]] _Iter in;
3561 template<
typename _Iter2>
3562 requires convertible_to<const _Iter&, _Iter2>
3564 operator in_found_result<_Iter2>() const &
3565 {
return {in, found}; }
3567 template<
typename _Iter2>
3568 requires convertible_to<_Iter, _Iter2>
3570 operator in_found_result<_Iter2>() &&
3574 template<
typename _Iter>
3575 using next_permutation_result = in_found_result<_Iter>;
3577 struct __next_permutation_fn
3579 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3580 typename _Comp = ranges::less,
typename _Proj =
identity>
3581 requires sortable<_Iter, _Comp, _Proj>
3582 constexpr next_permutation_result<_Iter>
3583 operator()(_Iter __first, _Sent __last,
3584 _Comp __comp = {}, _Proj __proj = {})
const
3586 if (__first == __last)
3594 auto __lasti = ranges::next(__first, __last);
3611 ranges::iter_swap(__i, __j);
3612 ranges::reverse(__ii, __last);
3617 ranges::reverse(__first, __last);
3623 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3624 typename _Proj = identity>
3625 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3626 constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3627 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3634 inline constexpr __next_permutation_fn next_permutation{};
3636 template<
typename _Iter>
3637 using prev_permutation_result = in_found_result<_Iter>;
3639 struct __prev_permutation_fn
3641 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3642 typename _Comp = ranges::less,
typename _Proj =
identity>
3643 requires sortable<_Iter, _Comp, _Proj>
3644 constexpr prev_permutation_result<_Iter>
3645 operator()(_Iter __first, _Sent __last,
3646 _Comp __comp = {}, _Proj __proj = {})
const
3648 if (__first == __last)
3656 auto __lasti = ranges::next(__first, __last);
3673 ranges::iter_swap(__i, __j);
3674 ranges::reverse(__ii, __last);
3679 ranges::reverse(__first, __last);
3685 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3686 typename _Proj = identity>
3687 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3688 constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3689 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3696 inline constexpr __prev_permutation_fn prev_permutation{};
3700 #define __cpp_lib_shift 201806L
3701 template<
typename _ForwardIterator>
3702 constexpr _ForwardIterator
3703 shift_left(_ForwardIterator __first, _ForwardIterator __last,
3704 typename iterator_traits<_ForwardIterator>::difference_type __n)
3706 __glibcxx_assert(__n >= 0);
3710 auto __mid = ranges::next(__first, __n, __last);
3711 if (__mid == __last)
3716 template<
typename _ForwardIterator>
3717 constexpr _ForwardIterator
3718 shift_right(_ForwardIterator __first, _ForwardIterator __last,
3719 typename iterator_traits<_ForwardIterator>::difference_type __n)
3721 __glibcxx_assert(__n >= 0);
3726 =
typename iterator_traits<_ForwardIterator>::iterator_category;
3727 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
3729 auto __mid = ranges::next(__last, -__n, __first);
3730 if (__mid == __first)
3738 auto __result = ranges::next(__first, __n, __last);
3739 if (__result == __last)
3742 auto __dest_head = __first, __dest_tail = __result;
3743 while (__dest_head != __result)
3745 if (__dest_tail == __last)
3770 auto __cursor = __first;
3771 while (__cursor != __result)
3773 if (__dest_tail == __last)
3778 __dest_head =
std::move(__cursor, __result,
3784 std::iter_swap(__cursor, __dest_head);
3793 _GLIBCXX_END_NAMESPACE_VERSION
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
constexpr _InputIterator for_each_n(_InputIterator __first, _Size __n, _Function __f)
Apply a function to every element of a sequence.
constexpr const _Tp & clamp(const _Tp &, const _Tp &, const _Tp &)
Returns the value clamped between lo and hi.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.
_SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomBitGenerator &&__g)
Take a random sample from a population.