30 #ifndef _RANGES_ALGO_H
31 #define _RANGES_ALGO_H 1
33 #if __cplusplus > 201703L
38 #if __cpp_lib_concepts
39 namespace std _GLIBCXX_VISIBILITY(default)
41 _GLIBCXX_BEGIN_NAMESPACE_VERSION
46 template<
typename _Comp,
typename _Proj>
48 __make_comp_proj(_Comp& __comp, _Proj& __proj)
50 return [&] (
auto&& __lhs,
auto&& __rhs) ->
bool {
51 using _TL = decltype(__lhs);
52 using _TR = decltype(__rhs);
53 return std::__invoke(__comp,
54 std::__invoke(__proj, std::forward<_TL>(__lhs)),
55 std::__invoke(__proj, std::forward<_TR>(__rhs)));
59 template<
typename _Pred,
typename _Proj>
61 __make_pred_proj(_Pred& __pred, _Proj& __proj)
63 return [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
64 return std::__invoke(__pred,
65 std::__invoke(__proj, std::forward<_Tp>(__arg)));
72 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
73 typename _Proj =
identity,
74 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
76 operator()(_Iter __first, _Sent __last,
77 _Pred __pred, _Proj __proj = {})
const
79 for (; __first != __last; ++__first)
80 if (!(
bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
85 template<input_range _Range,
typename _Proj = identity,
86 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
89 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
96 inline constexpr __all_of_fn all_of{};
100 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
101 typename _Proj =
identity,
102 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
104 operator()(_Iter __first, _Sent __last,
105 _Pred __pred, _Proj __proj = {})
const
107 for (; __first != __last; ++__first)
108 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
113 template<input_range _Range,
typename _Proj = identity,
114 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
117 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
124 inline constexpr __any_of_fn any_of{};
128 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
129 typename _Proj =
identity,
130 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
132 operator()(_Iter __first, _Sent __last,
133 _Pred __pred, _Proj __proj = {})
const
135 for (; __first != __last; ++__first)
136 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
141 template<input_range _Range,
typename _Proj = identity,
142 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
145 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
152 inline constexpr __none_of_fn none_of{};
154 template<
typename _Iter,
typename _Fp>
157 [[no_unique_address]] _Iter in;
158 [[no_unique_address]] _Fp fun;
160 template<
typename _Iter2,
typename _F2p>
161 requires convertible_to<const _Iter&, _Iter2>
162 && convertible_to<const _Fp&, _F2p>
164 operator in_fun_result<_Iter2, _F2p>()
const &
165 {
return {in, fun}; }
167 template<
typename _Iter2,
typename _F2p>
168 requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
170 operator in_fun_result<_Iter2, _F2p>() &&
174 template<
typename _Iter,
typename _Fp>
175 using for_each_result = in_fun_result<_Iter, _Fp>;
179 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
180 typename _Proj =
identity,
181 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
182 constexpr for_each_result<_Iter, _Fun>
183 operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {})
const
185 for (; __first != __last; ++__first)
186 std::__invoke(__f, std::__invoke(__proj, *__first));
190 template<input_range _Range,
typename _Proj = identity,
191 indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
193 constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun>
194 operator()(_Range&& __r, _Fun __f, _Proj __proj = {})
const
201 inline constexpr __for_each_fn for_each{};
203 template<
typename _Iter,
typename _Fp>
204 using for_each_n_result = in_fun_result<_Iter, _Fp>;
206 struct __for_each_n_fn
208 template<input_iterator _Iter,
typename _Proj = identity,
209 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
210 constexpr for_each_n_result<_Iter, _Fun>
211 operator()(_Iter __first, iter_difference_t<_Iter> __n,
212 _Fun __f, _Proj __proj = {})
const
214 if constexpr (random_access_iterator<_Iter>)
218 auto __last = __first + __n;
226 std::__invoke(__f, std::__invoke(__proj, *__first));
234 inline constexpr __for_each_n_fn for_each_n{};
238 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
239 typename _Proj =
identity>
240 requires indirect_binary_predicate<ranges::equal_to,
241 projected<_Iter, _Proj>,
const _Tp*>
243 operator()(_Iter __first, _Sent __last,
244 const _Tp& __value, _Proj __proj = {})
const
246 while (__first != __last
247 && !(std::__invoke(__proj, *__first) == __value))
252 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
253 requires indirect_binary_predicate<ranges::equal_to,
254 projected<iterator_t<_Range>, _Proj>,
256 constexpr borrowed_iterator_t<_Range>
257 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
264 inline constexpr __find_fn find{};
268 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
269 typename _Proj =
identity,
270 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
272 operator()(_Iter __first, _Sent __last,
273 _Pred __pred, _Proj __proj = {})
const
275 while (__first != __last
276 && !(
bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
281 template<input_range _Range,
typename _Proj = identity,
282 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
284 constexpr borrowed_iterator_t<_Range>
285 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
292 inline constexpr __find_if_fn find_if{};
294 struct __find_if_not_fn
296 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
297 typename _Proj =
identity,
298 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
300 operator()(_Iter __first, _Sent __last,
301 _Pred __pred, _Proj __proj = {})
const
303 while (__first != __last
304 && (
bool)std::__invoke(__pred, std::__invoke(__proj, *__first)))
309 template<input_range _Range,
typename _Proj = identity,
310 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
312 constexpr borrowed_iterator_t<_Range>
313 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
320 inline constexpr __find_if_not_fn find_if_not{};
322 struct __find_first_of_fn
324 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
325 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
326 typename _Pred = ranges::equal_to,
327 typename _Proj1 =
identity,
typename _Proj2 =
identity>
328 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
330 operator()(_Iter1 __first1, _Sent1 __last1,
331 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
332 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
334 for (; __first1 != __last1; ++__first1)
335 for (
auto __iter = __first2; __iter != __last2; ++__iter)
336 if (std::__invoke(__pred,
337 std::__invoke(__proj1, *__first1),
338 std::__invoke(__proj2, *__iter)))
343 template<input_range _Range1, forward_range _Range2,
344 typename _Pred = ranges::equal_to,
345 typename _Proj1 = identity,
typename _Proj2 = identity>
346 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
347 _Pred, _Proj1, _Proj2>
348 constexpr borrowed_iterator_t<_Range1>
349 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
350 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
359 inline constexpr __find_first_of_fn find_first_of{};
363 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
364 typename _Tp,
typename _Proj =
identity>
365 requires indirect_binary_predicate<ranges::equal_to,
366 projected<_Iter, _Proj>,
368 constexpr iter_difference_t<_Iter>
369 operator()(_Iter __first, _Sent __last,
370 const _Tp& __value, _Proj __proj = {})
const
372 iter_difference_t<_Iter> __n = 0;
373 for (; __first != __last; ++__first)
374 if (std::__invoke(__proj, *__first) == __value)
379 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
380 requires indirect_binary_predicate<ranges::equal_to,
381 projected<iterator_t<_Range>, _Proj>,
383 constexpr range_difference_t<_Range>
384 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
391 inline constexpr __count_fn count{};
395 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
396 typename _Proj =
identity,
397 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
398 constexpr iter_difference_t<_Iter>
399 operator()(_Iter __first, _Sent __last,
400 _Pred __pred, _Proj __proj = {})
const
402 iter_difference_t<_Iter> __n = 0;
403 for (; __first != __last; ++__first)
404 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
409 template<input_range _Range,
410 typename _Proj = identity,
411 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
413 constexpr range_difference_t<_Range>
414 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
421 inline constexpr __count_if_fn count_if{};
423 template<
typename _Iter1,
typename _Iter2>
426 [[no_unique_address]] _Iter1 in1;
427 [[no_unique_address]] _Iter2 in2;
429 template<
typename _IIter1,
typename _IIter2>
430 requires convertible_to<const _Iter1&, _IIter1>
431 && convertible_to<const _Iter2&, _IIter2>
433 operator in_in_result<_IIter1, _IIter2>()
const &
434 {
return {in1, in2}; }
436 template<
typename _IIter1,
typename _IIter2>
437 requires convertible_to<_Iter1, _IIter1>
438 && convertible_to<_Iter2, _IIter2>
440 operator in_in_result<_IIter1, _IIter2>() &&
444 template<
typename _Iter1,
typename _Iter2>
445 using mismatch_result = in_in_result<_Iter1, _Iter2>;
449 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
450 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
451 typename _Pred = ranges::equal_to,
452 typename _Proj1 =
identity,
typename _Proj2 =
identity>
453 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
454 constexpr mismatch_result<_Iter1, _Iter2>
455 operator()(_Iter1 __first1, _Sent1 __last1,
456 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
457 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
459 while (__first1 != __last1 && __first2 != __last2
460 && (
bool)std::__invoke(__pred,
461 std::__invoke(__proj1, *__first1),
462 std::__invoke(__proj2, *__first2)))
470 template<input_range _Range1, input_range _Range2,
471 typename _Pred = ranges::equal_to,
472 typename _Proj1 = identity,
typename _Proj2 = identity>
473 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
474 _Pred, _Proj1, _Proj2>
475 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
476 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
477 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
486 inline constexpr __mismatch_fn mismatch{};
490 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
491 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
492 typename _Pred = ranges::equal_to,
493 typename _Proj1 =
identity,
typename _Proj2 =
identity>
494 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
495 constexpr subrange<_Iter1>
496 operator()(_Iter1 __first1, _Sent1 __last1,
497 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
498 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
500 if (__first1 == __last1 || __first2 == __last2)
501 return {__first1, __first1};
507 if (__first1 == __last1)
508 return {__first1, __first1};
509 if (std::__invoke(__pred,
510 std::__invoke(__proj1, *__first1),
511 std::__invoke(__proj2, *__first2)))
515 auto __cur1 = __first1;
516 auto __cur2 = __first2;
519 if (++__cur2 == __last2)
520 return {__first1, ++__cur1};
521 if (++__cur1 == __last1)
522 return {__cur1, __cur1};
523 if (!(
bool)std::__invoke(__pred,
524 std::__invoke(__proj1, *__cur1),
525 std::__invoke(__proj2, *__cur2)))
534 template<forward_range _Range1, forward_range _Range2,
535 typename _Pred = ranges::equal_to,
536 typename _Proj1 = identity,
typename _Proj2 = identity>
537 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
538 _Pred, _Proj1, _Proj2>
539 constexpr borrowed_subrange_t<_Range1>
540 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
541 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
550 inline constexpr __search_fn search{};
554 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
555 typename _Pred = ranges::equal_to,
typename _Proj =
identity>
556 requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
557 constexpr subrange<_Iter>
558 operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
559 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const
562 return {__first, __first};
564 auto __value_comp = [&] <
typename _Rp> (_Rp&& __arg) {
565 return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
569 __first = ranges::find_if(
std::move(__first), __last,
572 if (__first == __last)
573 return {__first, __first};
576 auto __end = __first;
577 return {__first, ++__end};
581 if constexpr (sized_sentinel_for<_Sent, _Iter>
582 && random_access_iterator<_Iter>)
584 auto __tail_size = __last - __first;
585 auto __remainder = __count;
587 while (__remainder <= __tail_size)
589 __first += __remainder;
590 __tail_size -= __remainder;
591 auto __backtrack = __first;
592 while (__value_comp(std::__invoke(__proj, *--__backtrack)))
594 if (--__remainder == 0)
595 return {__first - __count, __first};
597 __remainder = __count + 1 - (__first - __backtrack);
599 auto __i = __first + __tail_size;
604 __first = ranges::find_if(__first, __last, __value_comp, __proj);
605 while (__first != __last)
610 while (__i != __last && __n != 1
611 && __value_comp(std::__invoke(__proj, *__i)))
617 return {__first, __i};
620 __first = ranges::find_if(++__i, __last, __value_comp, __proj);
622 return {__first, __first};
626 template<forward_range _Range,
typename _Tp,
627 typename _Pred = ranges::equal_to,
typename _Proj = identity>
628 requires indirectly_comparable<iterator_t<_Range>,
const _Tp*,
630 constexpr borrowed_subrange_t<_Range>
631 operator()(_Range&& __r, range_difference_t<_Range> __count,
632 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const
640 inline constexpr __search_n_fn search_n{};
644 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
645 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
646 typename _Pred = ranges::equal_to,
647 typename _Proj1 =
identity,
typename _Proj2 =
identity>
648 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
649 constexpr subrange<_Iter1>
650 operator()(_Iter1 __first1, _Sent1 __last1,
651 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
652 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
654 if constexpr (bidirectional_iterator<_Iter1>
655 && bidirectional_iterator<_Iter2>)
657 auto __i1 = ranges::next(__first1, __last1);
658 auto __i2 = ranges::next(__first2, __last2);
660 = ranges::search(reverse_iterator<_Iter1>{__i1},
661 reverse_iterator<_Iter1>{__first1},
662 reverse_iterator<_Iter2>{__i2},
663 reverse_iterator<_Iter2>{__first2},
666 auto __result_first =
ranges::end(__rresult).base();
668 if (__result_last == __first1)
671 return {__result_first, __result_last};
675 auto __i = ranges::next(__first1, __last1);
676 if (__first2 == __last2)
679 auto __result_begin = __i;
680 auto __result_end = __i;
683 auto __new_range = ranges::search(__first1, __last1,
685 __pred, __proj1, __proj2);
688 if (__new_result_begin == __last1)
689 return {__result_begin, __result_end};
692 __result_begin = __new_result_begin;
693 __result_end = __new_result_end;
694 __first1 = __result_begin;
701 template<forward_range _Range1, forward_range _Range2,
702 typename _Pred = ranges::equal_to,
703 typename _Proj1 = identity,
typename _Proj2 = identity>
704 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
705 _Pred, _Proj1, _Proj2>
706 constexpr borrowed_subrange_t<_Range1>
707 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
708 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
717 inline constexpr __find_end_fn find_end{};
719 struct __adjacent_find_fn
721 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
722 typename _Proj =
identity,
723 indirect_binary_predicate<projected<_Iter, _Proj>,
724 projected<_Iter, _Proj>> _Pred
727 operator()(_Iter __first, _Sent __last,
728 _Pred __pred = {}, _Proj __proj = {})
const
730 if (__first == __last)
732 auto __next = __first;
733 for (; ++__next != __last; __first = __next)
735 if (std::__invoke(__pred,
736 std::__invoke(__proj, *__first),
737 std::__invoke(__proj, *__next)))
743 template<forward_range _Range,
typename _Proj = identity,
744 indirect_binary_predicate<
745 projected<iterator_t<_Range>, _Proj>,
746 projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
747 constexpr borrowed_iterator_t<_Range>
748 operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {})
const
755 inline constexpr __adjacent_find_fn adjacent_find{};
757 struct __is_permutation_fn
759 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
760 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
761 typename _Proj1 =
identity,
typename _Proj2 =
identity,
762 indirect_equivalence_relation<projected<_Iter1, _Proj1>,
763 projected<_Iter2, _Proj2>> _Pred
766 operator()(_Iter1 __first1, _Sent1 __last1,
767 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
768 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
770 constexpr
bool __sized_iters
771 = (sized_sentinel_for<_Sent1, _Iter1>
772 && sized_sentinel_for<_Sent2, _Iter2>);
773 if constexpr (__sized_iters)
783 for (; __first1 != __last1 && __first2 != __last2;
784 ++__first1, (void)++__first2)
785 if (!(
bool)std::__invoke(__pred,
786 std::__invoke(__proj1, *__first1),
787 std::__invoke(__proj2, *__first2)))
790 if constexpr (__sized_iters)
792 if (__first1 == __last1)
799 if (__d1 == 0 && __d2 == 0)
805 for (
auto __scan = __first1; __scan != __last1; ++__scan)
807 auto __proj_scan = std::__invoke(__proj1, *__scan);
808 auto __comp_scan = [&] <
typename _Tp> (_Tp&& __arg) {
809 return std::__invoke(__pred, __proj_scan,
810 std::forward<_Tp>(__arg));
812 if (__scan != ranges::find_if(__first1, __scan,
813 __comp_scan, __proj1))
816 auto __matches = ranges::count_if(__first2, __last2,
817 __comp_scan, __proj2);
819 || ranges::count_if(__scan, __last1,
820 __comp_scan, __proj1) != __matches)
826 template<forward_range _Range1, forward_range _Range2,
827 typename _Proj1 = identity,
typename _Proj2 = identity,
828 indirect_equivalence_relation<
829 projected<iterator_t<_Range1>, _Proj1>,
830 projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
832 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
833 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
842 inline constexpr __is_permutation_fn is_permutation{};
844 template<
typename _Iter,
typename _Out>
845 using copy_if_result = in_out_result<_Iter, _Out>;
849 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
850 weakly_incrementable _Out,
typename _Proj =
identity,
851 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
852 requires indirectly_copyable<_Iter, _Out>
853 constexpr copy_if_result<_Iter, _Out>
854 operator()(_Iter __first, _Sent __last, _Out __result,
855 _Pred __pred, _Proj __proj = {})
const
857 for (; __first != __last; ++__first)
858 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
860 *__result = *__first;
866 template<input_range _Range, weakly_incrementable _Out,
867 typename _Proj = identity,
868 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
870 requires indirectly_copyable<iterator_t<_Range>, _Out>
871 constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
872 operator()(_Range&& __r, _Out __result,
873 _Pred __pred, _Proj __proj = {})
const
881 inline constexpr __copy_if_fn copy_if{};
883 template<
typename _Iter1,
typename _Iter2>
884 using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
886 struct __swap_ranges_fn
888 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
889 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
890 requires indirectly_swappable<_Iter1, _Iter2>
891 constexpr swap_ranges_result<_Iter1, _Iter2>
892 operator()(_Iter1 __first1, _Sent1 __last1,
893 _Iter2 __first2, _Sent2 __last2)
const
895 for (; __first1 != __last1 && __first2 != __last2;
896 ++__first1, (void)++__first2)
897 ranges::iter_swap(__first1, __first2);
901 template<input_range _Range1, input_range _Range2>
902 requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
903 constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
904 borrowed_iterator_t<_Range2>>
905 operator()(_Range1&& __r1, _Range2&& __r2)
const
912 inline constexpr __swap_ranges_fn swap_ranges{};
914 template<
typename _Iter,
typename _Out>
915 using unary_transform_result = in_out_result<_Iter, _Out>;
917 template<
typename _Iter1,
typename _Iter2,
typename _Out>
918 struct in_in_out_result
920 [[no_unique_address]] _Iter1 in1;
921 [[no_unique_address]] _Iter2 in2;
922 [[no_unique_address]] _Out out;
924 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
925 requires convertible_to<const _Iter1&, _IIter1>
926 && convertible_to<const _Iter2&, _IIter2>
927 && convertible_to<const _Out&, _OOut>
929 operator in_in_out_result<_IIter1, _IIter2, _OOut>()
const &
930 {
return {in1, in2, out}; }
932 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
933 requires convertible_to<_Iter1, _IIter1>
934 && convertible_to<_Iter2, _IIter2>
935 && convertible_to<_Out, _OOut>
937 operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
941 template<
typename _Iter1,
typename _Iter2,
typename _Out>
942 using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
944 struct __transform_fn
946 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
947 weakly_incrementable _Out,
948 copy_constructible _Fp,
typename _Proj =
identity>
949 requires indirectly_writable<_Out,
950 indirect_result_t<_Fp&,
951 projected<_Iter, _Proj>>>
952 constexpr unary_transform_result<_Iter, _Out>
953 operator()(_Iter __first1, _Sent __last1, _Out __result,
954 _Fp __op, _Proj __proj = {})
const
956 for (; __first1 != __last1; ++__first1, (void)++__result)
957 *__result = std::__invoke(__op, std::__invoke(__proj, *__first1));
961 template<input_range _Range, weakly_incrementable _Out,
962 copy_constructible _Fp,
typename _Proj = identity>
963 requires indirectly_writable<_Out,
964 indirect_result_t<_Fp&,
965 projected<iterator_t<_Range>, _Proj>>>
966 constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
967 operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {})
const
974 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
975 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
976 weakly_incrementable _Out, copy_constructible _Fp,
977 typename _Proj1 =
identity,
typename _Proj2 =
identity>
978 requires indirectly_writable<_Out,
979 indirect_result_t<_Fp&,
980 projected<_Iter1, _Proj1>,
981 projected<_Iter2, _Proj2>>>
982 constexpr binary_transform_result<_Iter1, _Iter2, _Out>
983 operator()(_Iter1 __first1, _Sent1 __last1,
984 _Iter2 __first2, _Sent2 __last2,
985 _Out __result, _Fp __binary_op,
986 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
988 for (; __first1 != __last1 && __first2 != __last2;
989 ++__first1, (void)++__first2, ++__result)
990 *__result = std::__invoke(__binary_op,
991 std::__invoke(__proj1, *__first1),
992 std::__invoke(__proj2, *__first2));
996 template<input_range _Range1, input_range _Range2,
997 weakly_incrementable _Out, copy_constructible _Fp,
998 typename _Proj1 = identity,
typename _Proj2 = identity>
999 requires indirectly_writable<_Out,
1000 indirect_result_t<_Fp&,
1001 projected<iterator_t<_Range1>, _Proj1>,
1002 projected<iterator_t<_Range2>, _Proj2>>>
1003 constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
1004 borrowed_iterator_t<_Range2>, _Out>
1005 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
1006 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1015 inline constexpr __transform_fn transform{};
1019 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1020 typename _Tp1,
typename _Tp2,
typename _Proj =
identity>
1021 requires indirectly_writable<_Iter, const _Tp2&>
1022 && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
1025 operator()(_Iter __first, _Sent __last,
1026 const _Tp1& __old_value,
const _Tp2& __new_value,
1027 _Proj __proj = {})
const
1029 for (; __first != __last; ++__first)
1030 if (std::__invoke(__proj, *__first) == __old_value)
1031 *__first = __new_value;
1035 template<input_range _Range,
1036 typename _Tp1,
typename _Tp2,
typename _Proj = identity>
1037 requires indirectly_writable<iterator_t<_Range>,
const _Tp2&>
1038 && indirect_binary_predicate<ranges::equal_to,
1039 projected<iterator_t<_Range>, _Proj>,
1041 constexpr borrowed_iterator_t<_Range>
1042 operator()(_Range&& __r,
1043 const _Tp1& __old_value,
const _Tp2& __new_value,
1044 _Proj __proj = {})
const
1047 __old_value, __new_value,
std::move(__proj));
1051 inline constexpr __replace_fn replace{};
1053 struct __replace_if_fn
1055 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1056 typename _Tp,
typename _Proj =
identity,
1057 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1058 requires indirectly_writable<_Iter, const _Tp&>
1060 operator()(_Iter __first, _Sent __last,
1061 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
1063 for (; __first != __last; ++__first)
1064 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
1065 *__first = __new_value;
1069 template<input_range _Range,
typename _Tp,
typename _Proj = identity,
1070 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1072 requires indirectly_writable<iterator_t<_Range>,
const _Tp&>
1073 constexpr borrowed_iterator_t<_Range>
1074 operator()(_Range&& __r,
1075 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
1082 inline constexpr __replace_if_fn replace_if{};
1084 template<
typename _Iter,
typename _Out>
1085 using replace_copy_result = in_out_result<_Iter, _Out>;
1087 struct __replace_copy_fn
1089 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1090 typename _Tp1,
typename _Tp2, output_iterator<const _Tp2&> _Out,
1091 typename _Proj =
identity>
1092 requires indirectly_copyable<_Iter, _Out>
1093 && indirect_binary_predicate<ranges::equal_to,
1094 projected<_Iter, _Proj>,
const _Tp1*>
1095 constexpr replace_copy_result<_Iter, _Out>
1096 operator()(_Iter __first, _Sent __last, _Out __result,
1097 const _Tp1& __old_value,
const _Tp2& __new_value,
1098 _Proj __proj = {})
const
1100 for (; __first != __last; ++__first, (void)++__result)
1101 if (std::__invoke(__proj, *__first) == __old_value)
1102 *__result = __new_value;
1104 *__result = *__first;
1108 template<input_range _Range,
typename _Tp1,
typename _Tp2,
1109 output_iterator<const _Tp2&> _Out,
typename _Proj = identity>
1110 requires indirectly_copyable<iterator_t<_Range>, _Out>
1111 && indirect_binary_predicate<ranges::equal_to,
1112 projected<iterator_t<_Range>, _Proj>,
1114 constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
1115 operator()(_Range&& __r, _Out __result,
1116 const _Tp1& __old_value,
const _Tp2& __new_value,
1117 _Proj __proj = {})
const
1125 inline constexpr __replace_copy_fn replace_copy{};
1127 template<
typename _Iter,
typename _Out>
1128 using replace_copy_if_result = in_out_result<_Iter, _Out>;
1130 struct __replace_copy_if_fn
1132 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1133 typename _Tp, output_iterator<const _Tp&> _Out,
1134 typename _Proj =
identity,
1135 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1136 requires indirectly_copyable<_Iter, _Out>
1137 constexpr replace_copy_if_result<_Iter, _Out>
1138 operator()(_Iter __first, _Sent __last, _Out __result,
1139 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
1141 for (; __first != __last; ++__first, (void)++__result)
1142 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
1143 *__result = __new_value;
1145 *__result = *__first;
1149 template<input_range _Range,
1150 typename _Tp, output_iterator<const _Tp&> _Out,
1151 typename _Proj = identity,
1152 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1154 requires indirectly_copyable<iterator_t<_Range>, _Out>
1155 constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1156 operator()(_Range&& __r, _Out __result,
1157 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
1165 inline constexpr __replace_copy_if_fn replace_copy_if{};
1167 struct __generate_n_fn
1169 template<input_or_output_iterator _Out, copy_constructible _Fp>
1170 requires invocable<_Fp&>
1171 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
1173 operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen)
const
1175 for (; __n > 0; --__n, (void)++__first)
1176 *__first = std::__invoke(__gen);
1181 inline constexpr __generate_n_fn generate_n{};
1183 struct __generate_fn
1185 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
1186 copy_constructible _Fp>
1187 requires invocable<_Fp&>
1188 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
1190 operator()(_Out __first, _Sent __last, _Fp __gen)
const
1192 for (; __first != __last; ++__first)
1193 *__first = std::__invoke(__gen);
1197 template<
typename _Range, copy_constructible _Fp>
1198 requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
1199 constexpr borrowed_iterator_t<_Range>
1200 operator()(_Range&& __r, _Fp __gen)
const
1206 inline constexpr __generate_fn generate{};
1208 struct __remove_if_fn
1210 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1211 typename _Proj =
identity,
1212 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1213 constexpr subrange<_Iter>
1214 operator()(_Iter __first, _Sent __last,
1215 _Pred __pred, _Proj __proj = {})
const
1217 __first = ranges::find_if(__first, __last, __pred, __proj);
1218 if (__first == __last)
1219 return {__first, __first};
1221 auto __result = __first;
1223 for (; __first != __last; ++__first)
1224 if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
1230 return {__result, __first};
1233 template<forward_range _Range,
typename _Proj = identity,
1234 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1236 requires permutable<iterator_t<_Range>>
1237 constexpr borrowed_subrange_t<_Range>
1238 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
1245 inline constexpr __remove_if_fn remove_if{};
1249 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1250 typename _Tp,
typename _Proj =
identity>
1251 requires indirect_binary_predicate<ranges::equal_to,
1252 projected<_Iter, _Proj>,
1254 constexpr subrange<_Iter>
1255 operator()(_Iter __first, _Sent __last,
1256 const _Tp& __value, _Proj __proj = {})
const
1258 auto __pred = [&] (
auto&& __arg) {
1259 return std::forward<decltype(__arg)>(__arg) == __value;
1261 return ranges::remove_if(__first, __last,
1265 template<forward_range _Range,
typename _Tp,
typename _Proj =
identity>
1266 requires permutable<iterator_t<_Range>>
1267 && indirect_binary_predicate<ranges::equal_to,
1268 projected<iterator_t<_Range>, _Proj>,
1270 constexpr borrowed_subrange_t<_Range>
1271 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
1278 inline constexpr __remove_fn
remove{};
1280 template<
typename _Iter,
typename _Out>
1281 using remove_copy_if_result = in_out_result<_Iter, _Out>;
1283 struct __remove_copy_if_fn
1285 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1286 weakly_incrementable _Out,
typename _Proj =
identity,
1287 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1288 requires indirectly_copyable<_Iter, _Out>
1289 constexpr remove_copy_if_result<_Iter, _Out>
1290 operator()(_Iter __first, _Sent __last, _Out __result,
1291 _Pred __pred, _Proj __proj = {})
const
1293 for (; __first != __last; ++__first)
1294 if (!std::__invoke(__pred, std::__invoke(__proj, *__first)))
1296 *__result = *__first;
1302 template<input_range _Range, weakly_incrementable _Out,
1303 typename _Proj = identity,
1304 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1306 requires indirectly_copyable<iterator_t<_Range>, _Out>
1307 constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1308 operator()(_Range&& __r, _Out __result,
1309 _Pred __pred, _Proj __proj = {})
const
1317 inline constexpr __remove_copy_if_fn remove_copy_if{};
1319 template<
typename _Iter,
typename _Out>
1320 using remove_copy_result = in_out_result<_Iter, _Out>;
1322 struct __remove_copy_fn
1324 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1325 weakly_incrementable _Out,
typename _Tp,
typename _Proj =
identity>
1326 requires indirectly_copyable<_Iter, _Out>
1327 && indirect_binary_predicate<ranges::equal_to,
1328 projected<_Iter, _Proj>,
1330 constexpr remove_copy_result<_Iter, _Out>
1331 operator()(_Iter __first, _Sent __last, _Out __result,
1332 const _Tp& __value, _Proj __proj = {})
const
1334 for (; __first != __last; ++__first)
1335 if (!(std::__invoke(__proj, *__first) == __value))
1337 *__result = *__first;
1343 template<input_range _Range, weakly_incrementable _Out,
1344 typename _Tp,
typename _Proj = identity>
1345 requires indirectly_copyable<iterator_t<_Range>, _Out>
1346 && indirect_binary_predicate<ranges::equal_to,
1347 projected<iterator_t<_Range>, _Proj>,
1349 constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
1350 operator()(_Range&& __r, _Out __result,
1351 const _Tp& __value, _Proj __proj = {})
const
1358 inline constexpr __remove_copy_fn remove_copy{};
1362 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1363 typename _Proj =
identity,
1364 indirect_equivalence_relation<
1365 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1366 constexpr subrange<_Iter>
1367 operator()(_Iter __first, _Sent __last,
1368 _Comp __comp = {}, _Proj __proj = {})
const
1370 __first = ranges::adjacent_find(__first, __last, __comp, __proj);
1371 if (__first == __last)
1372 return {__first, __first};
1374 auto __dest = __first;
1376 while (++__first != __last)
1377 if (!std::__invoke(__comp,
1378 std::__invoke(__proj, *__dest),
1379 std::__invoke(__proj, *__first)))
1381 return {++__dest, __first};
1384 template<forward_range _Range,
typename _Proj = identity,
1385 indirect_equivalence_relation<
1386 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1387 requires permutable<iterator_t<_Range>>
1388 constexpr borrowed_subrange_t<_Range>
1389 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1396 inline constexpr __unique_fn unique{};
1398 template<
typename _Iter,
typename _Out>
1399 using unique_copy_result = in_out_result<_Iter, _Out>;
1401 struct __unique_copy_fn
1403 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1404 weakly_incrementable _Out,
typename _Proj =
identity,
1405 indirect_equivalence_relation<
1406 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1407 requires indirectly_copyable<_Iter, _Out>
1408 && (forward_iterator<_Iter>
1409 || (input_iterator<_Out>
1410 && same_as<iter_value_t<_Iter>, iter_value_t<_Out>>)
1411 || indirectly_copyable_storable<_Iter, _Out>)
1412 constexpr unique_copy_result<_Iter, _Out>
1413 operator()(_Iter __first, _Sent __last, _Out __result,
1414 _Comp __comp = {}, _Proj __proj = {})
const
1416 if (__first == __last)
1420 if constexpr (forward_iterator<_Iter>)
1422 auto __next = __first;
1423 *__result = *__next;
1424 while (++__next != __last)
1425 if (!std::__invoke(__comp,
1426 std::__invoke(__proj, *__first),
1427 std::__invoke(__proj, *__next)))
1430 *++__result = *__first;
1434 else if constexpr (input_iterator<_Out>
1435 && same_as<iter_value_t<_Iter>, iter_value_t<_Out>>)
1437 *__result = *__first;
1438 while (++__first != __last)
1439 if (!std::__invoke(__comp,
1440 std::__invoke(__proj, *__result),
1441 std::__invoke(__proj, *__first)))
1442 *++__result = *__first;
1447 auto __value = *__first;
1448 *__result = __value;
1449 while (++__first != __last)
1451 if (!(
bool)std::__invoke(__comp,
1452 std::__invoke(__proj, *__first),
1453 std::__invoke(__proj, __value)))
1456 *++__result = __value;
1463 template<input_range _Range,
1464 weakly_incrementable _Out,
typename _Proj = identity,
1465 indirect_equivalence_relation<
1466 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1467 requires indirectly_copyable<iterator_t<_Range>, _Out>
1468 && (forward_iterator<iterator_t<_Range>>
1469 || (input_iterator<_Out>
1470 && same_as<range_value_t<_Range>, iter_value_t<_Out>>)
1471 || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1472 constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1473 operator()(_Range&& __r, _Out __result,
1474 _Comp __comp = {}, _Proj __proj = {})
const
1482 inline constexpr __unique_copy_fn unique_copy{};
1486 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1487 requires permutable<_Iter>
1489 operator()(_Iter __first, _Sent __last)
const
1491 auto __i = ranges::next(__first, __last);
1494 if constexpr (random_access_iterator<_Iter>)
1496 if (__first != __last)
1499 while (__first < __tail)
1501 ranges::iter_swap(__first, __tail);
1511 if (__first == __tail || __first == --__tail)
1515 ranges::iter_swap(__first, __tail);
1522 template<b
idirectional_range _Range>
1523 requires permutable<iterator_t<_Range>>
1524 constexpr borrowed_iterator_t<_Range>
1525 operator()(_Range&& __r)
const
1531 inline constexpr __reverse_fn reverse{};
1533 template<
typename _Iter,
typename _Out>
1534 using reverse_copy_result = in_out_result<_Iter, _Out>;
1536 struct __reverse_copy_fn
1538 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1539 weakly_incrementable _Out>
1540 requires indirectly_copyable<_Iter, _Out>
1541 constexpr reverse_copy_result<_Iter, _Out>
1542 operator()(_Iter __first, _Sent __last, _Out __result)
const
1544 auto __i = ranges::next(__first, __last);
1546 while (__first != __tail)
1549 *__result = *__tail;
1552 return {__i, __result};
1555 template<b
idirectional_range _Range, weakly_incrementable _Out>
1556 requires indirectly_copyable<iterator_t<_Range>, _Out>
1557 constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1558 operator()(_Range&& __r, _Out __result)
const
1565 inline constexpr __reverse_copy_fn reverse_copy{};
1569 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1570 constexpr subrange<_Iter>
1571 operator()(_Iter __first, _Iter __middle, _Sent __last)
const
1573 auto __lasti = ranges::next(__first, __last);
1574 if (__first == __middle)
1575 return {__lasti, __lasti};
1576 if (__last == __middle)
1579 if constexpr (random_access_iterator<_Iter>)
1581 auto __n = __lasti - __first;
1582 auto __k = __middle - __first;
1584 if (__k == __n - __k)
1586 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1591 auto __ret = __first + (__lasti - __middle);
1595 if (__k < __n - __k)
1599 if constexpr (__is_pod(iter_value_t<_Iter>))
1607 auto __q = __p + __k;
1608 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1610 ranges::iter_swap(__p, __q);
1617 ranges::swap(__n, __k);
1625 if constexpr (__is_pod(iter_value_t<_Iter>))
1633 auto __q = __p + __n;
1635 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1639 ranges::iter_swap(__p, __q);
1644 std::swap(__n, __k);
1648 else if constexpr (bidirectional_iterator<_Iter>)
1650 auto __tail = __lasti;
1652 ranges::reverse(__first, __middle);
1653 ranges::reverse(__middle, __tail);
1655 while (__first != __middle && __middle != __tail)
1657 ranges::iter_swap(__first, --__tail);
1661 if (__first == __middle)
1663 ranges::reverse(__middle, __tail);
1668 ranges::reverse(__first, __middle);
1674 auto __first2 = __middle;
1677 ranges::iter_swap(__first, __first2);
1680 if (__first == __middle)
1681 __middle = __first2;
1682 }
while (__first2 != __last);
1684 auto __ret = __first;
1686 __first2 = __middle;
1688 while (__first2 != __last)
1690 ranges::iter_swap(__first, __first2);
1693 if (__first == __middle)
1694 __middle = __first2;
1695 else if (__first2 == __last)
1696 __first2 = __middle;
1702 template<forward_range _Range>
1703 requires permutable<iterator_t<_Range>>
1704 constexpr borrowed_subrange_t<_Range>
1705 operator()(_Range&& __r, iterator_t<_Range> __middle)
const
1712 inline constexpr __rotate_fn rotate{};
1714 template<
typename _Iter,
typename _Out>
1715 using rotate_copy_result = in_out_result<_Iter, _Out>;
1717 struct __rotate_copy_fn
1719 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1720 weakly_incrementable _Out>
1721 requires indirectly_copyable<_Iter, _Out>
1722 constexpr rotate_copy_result<_Iter, _Out>
1723 operator()(_Iter __first, _Iter __middle, _Sent __last,
1724 _Out __result)
const
1726 auto __copy1 = ranges::copy(__middle,
1729 auto __copy2 = ranges::copy(
std::move(__first),
1735 template<forward_range _Range, weakly_incrementable _Out>
1736 requires indirectly_copyable<iterator_t<_Range>, _Out>
1737 constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1738 operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result)
const
1745 inline constexpr __rotate_copy_fn rotate_copy{};
1749 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1750 weakly_incrementable _Out,
typename _Gen>
1751 requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
1752 && indirectly_copyable<_Iter, _Out>
1753 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1755 operator()(_Iter __first, _Sent __last, _Out __out,
1756 iter_difference_t<_Iter> __n, _Gen&& __g)
const
1758 if constexpr (forward_iterator<_Iter>)
1762 auto __lasti = ranges::next(__first, __last);
1764 std::move(__out), __n, std::forward<_Gen>(__g));
1768 using __distrib_type
1769 = uniform_int_distribution<iter_difference_t<_Iter>>;
1770 using __param_type =
typename __distrib_type::param_type;
1771 __distrib_type __d{};
1772 iter_difference_t<_Iter> __sample_sz = 0;
1773 while (__first != __last && __sample_sz != __n)
1775 __out[__sample_sz++] = *__first;
1778 for (
auto __pop_sz = __sample_sz; __first != __last;
1779 ++__first, (void) ++__pop_sz)
1781 const auto __k = __d(__g, __param_type{0, __pop_sz});
1783 __out[__k] = *__first;
1785 return __out + __sample_sz;
1789 template<input_range _Range, weakly_incrementable _Out,
typename _Gen>
1790 requires (forward_range<_Range> || random_access_iterator<_Out>)
1791 && indirectly_copyable<iterator_t<_Range>, _Out>
1792 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1794 operator()(_Range&& __r, _Out __out,
1795 range_difference_t<_Range> __n, _Gen&& __g)
const
1799 std::forward<_Gen>(__g));
1803 inline constexpr __sample_fn sample{};
1805 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
1808 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1810 requires permutable<_Iter>
1811 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1813 operator()(_Iter __first, _Sent __last, _Gen&& __g)
const
1815 auto __lasti = ranges::next(__first, __last);
1820 template<random_access_range _Range,
typename _Gen>
1821 requires permutable<iterator_t<_Range>>
1822 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1823 borrowed_iterator_t<_Range>
1824 operator()(_Range&& __r, _Gen&& __g)
const
1827 std::forward<_Gen>(__g));
1831 inline constexpr __shuffle_fn shuffle{};
1834 struct __push_heap_fn
1836 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1837 typename _Comp = ranges::less,
typename _Proj =
identity>
1838 requires sortable<_Iter, _Comp, _Proj>
1840 operator()(_Iter __first, _Sent __last,
1841 _Comp __comp = {}, _Proj __proj = {})
const
1843 auto __lasti = ranges::next(__first, __last);
1845 __detail::__make_comp_proj(__comp, __proj));
1849 template<random_access_range _Range,
1850 typename _Comp = ranges::less,
typename _Proj = identity>
1851 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1852 constexpr borrowed_iterator_t<_Range>
1853 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1860 inline constexpr __push_heap_fn push_heap{};
1862 struct __pop_heap_fn
1864 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1865 typename _Comp = ranges::less,
typename _Proj =
identity>
1866 requires sortable<_Iter, _Comp, _Proj>
1868 operator()(_Iter __first, _Sent __last,
1869 _Comp __comp = {}, _Proj __proj = {})
const
1871 auto __lasti = ranges::next(__first, __last);
1873 __detail::__make_comp_proj(__comp, __proj));
1877 template<random_access_range _Range,
1878 typename _Comp = ranges::less,
typename _Proj = identity>
1879 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1880 constexpr borrowed_iterator_t<_Range>
1881 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1888 inline constexpr __pop_heap_fn pop_heap{};
1890 struct __make_heap_fn
1892 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1893 typename _Comp = ranges::less,
typename _Proj =
identity>
1894 requires sortable<_Iter, _Comp, _Proj>
1896 operator()(_Iter __first, _Sent __last,
1897 _Comp __comp = {}, _Proj __proj = {})
const
1899 auto __lasti = ranges::next(__first, __last);
1901 __detail::__make_comp_proj(__comp, __proj));
1905 template<random_access_range _Range,
1906 typename _Comp = ranges::less,
typename _Proj = identity>
1907 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1908 constexpr borrowed_iterator_t<_Range>
1909 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1916 inline constexpr __make_heap_fn make_heap{};
1918 struct __sort_heap_fn
1920 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1921 typename _Comp = ranges::less,
typename _Proj =
identity>
1922 requires sortable<_Iter, _Comp, _Proj>
1924 operator()(_Iter __first, _Sent __last,
1925 _Comp __comp = {}, _Proj __proj = {})
const
1927 auto __lasti = ranges::next(__first, __last);
1929 __detail::__make_comp_proj(__comp, __proj));
1933 template<random_access_range _Range,
1934 typename _Comp = ranges::less,
typename _Proj = identity>
1935 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1936 constexpr borrowed_iterator_t<_Range>
1937 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1944 inline constexpr __sort_heap_fn sort_heap{};
1946 struct __is_heap_until_fn
1948 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1949 typename _Proj =
identity,
1950 indirect_strict_weak_order<projected<_Iter, _Proj>>
1951 _Comp = ranges::less>
1953 operator()(_Iter __first, _Sent __last,
1954 _Comp __comp = {}, _Proj __proj = {})
const
1957 iter_difference_t<_Iter> __parent = 0, __child = 1;
1958 for (; __child < __n; ++__child)
1959 if (std::__invoke(__comp,
1960 std::__invoke(__proj, *(__first + __parent)),
1961 std::__invoke(__proj, *(__first + __child))))
1962 return __first + __child;
1963 else if ((__child & 1) == 0)
1966 return __first + __n;
1969 template<random_access_range _Range,
1970 typename _Proj = identity,
1971 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1972 _Comp = ranges::less>
1973 constexpr borrowed_iterator_t<_Range>
1974 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1981 inline constexpr __is_heap_until_fn is_heap_until{};
1985 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1986 typename _Proj =
identity,
1987 indirect_strict_weak_order<projected<_Iter, _Proj>>
1988 _Comp = ranges::less>
1990 operator()(_Iter __first, _Sent __last,
1991 _Comp __comp = {}, _Proj __proj = {})
const
1994 == ranges::is_heap_until(__first, __last,
1999 template<random_access_range _Range,
2000 typename _Proj = identity,
2001 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2002 _Comp = ranges::less>
2004 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2011 inline constexpr __is_heap_fn is_heap{};
2015 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2016 typename _Comp = ranges::less,
typename _Proj =
identity>
2017 requires sortable<_Iter, _Comp, _Proj>
2019 operator()(_Iter __first, _Sent __last,
2020 _Comp __comp = {}, _Proj __proj = {})
const
2022 auto __lasti = ranges::next(__first, __last);
2024 __detail::__make_comp_proj(__comp, __proj));
2028 template<random_access_range _Range,
2029 typename _Comp = ranges::less,
typename _Proj = identity>
2030 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2031 constexpr borrowed_iterator_t<_Range>
2032 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2039 inline constexpr __sort_fn sort{};
2041 struct __stable_sort_fn
2043 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2044 typename _Comp = ranges::less,
typename _Proj =
identity>
2045 requires sortable<_Iter, _Comp, _Proj>
2047 operator()(_Iter __first, _Sent __last,
2048 _Comp __comp = {}, _Proj __proj = {})
const
2050 auto __lasti = ranges::next(__first, __last);
2052 __detail::__make_comp_proj(__comp, __proj));
2056 template<random_access_range _Range,
2057 typename _Comp = ranges::less,
typename _Proj = identity>
2058 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2059 borrowed_iterator_t<_Range>
2060 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2067 inline constexpr __stable_sort_fn stable_sort{};
2069 struct __partial_sort_fn
2071 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2072 typename _Comp = ranges::less,
typename _Proj =
identity>
2073 requires sortable<_Iter, _Comp, _Proj>
2075 operator()(_Iter __first, _Iter __middle, _Sent __last,
2076 _Comp __comp = {}, _Proj __proj = {})
const
2078 if (__first == __middle)
2079 return ranges::next(__first, __last);
2081 ranges::make_heap(__first, __middle, __comp, __proj);
2082 auto __i = __middle;
2083 for (; __i != __last; ++__i)
2084 if (std::__invoke(__comp,
2085 std::__invoke(__proj, *__i),
2086 std::__invoke(__proj, *__first)))
2088 ranges::pop_heap(__first, __middle, __comp, __proj);
2089 ranges::iter_swap(__middle-1, __i);
2090 ranges::push_heap(__first, __middle, __comp, __proj);
2092 ranges::sort_heap(__first, __middle, __comp, __proj);
2097 template<random_access_range _Range,
2098 typename _Comp = ranges::less,
typename _Proj = identity>
2099 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2100 constexpr borrowed_iterator_t<_Range>
2101 operator()(_Range&& __r, iterator_t<_Range> __middle,
2102 _Comp __comp = {}, _Proj __proj = {})
const
2110 inline constexpr __partial_sort_fn partial_sort{};
2112 template<
typename _Iter,
typename _Out>
2113 using partial_sort_copy_result = in_out_result<_Iter, _Out>;
2115 struct __partial_sort_copy_fn
2117 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2118 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2119 typename _Comp = ranges::less,
2120 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2121 requires indirectly_copyable<_Iter1, _Iter2>
2122 && sortable<_Iter2, _Comp, _Proj2>
2123 && indirect_strict_weak_order<_Comp,
2124 projected<_Iter1, _Proj1>,
2125 projected<_Iter2, _Proj2>>
2126 constexpr partial_sort_copy_result<_Iter1, _Iter2>
2127 operator()(_Iter1 __first, _Sent1 __last,
2128 _Iter2 __result_first, _Sent2 __result_last,
2130 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2132 if (__result_first == __result_last)
2135 auto __lasti = ranges::next(
std::move(__first),
2140 auto __result_real_last = __result_first;
2141 while (__first != __last && __result_real_last != __result_last)
2143 *__result_real_last = *__first;
2144 ++__result_real_last;
2148 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
2149 for (; __first != __last; ++__first)
2150 if (std::__invoke(__comp,
2151 std::__invoke(__proj1, *__first),
2152 std::__invoke(__proj2, *__result_first)))
2154 ranges::pop_heap(__result_first, __result_real_last,
2156 *(__result_real_last-1) = *__first;
2157 ranges::push_heap(__result_first, __result_real_last,
2160 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
2165 template<input_range _Range1, random_access_range _Range2,
2166 typename _Comp = ranges::less,
2167 typename _Proj1 = identity,
typename _Proj2 = identity>
2168 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
2169 && sortable<iterator_t<_Range2>, _Comp, _Proj2>
2170 && indirect_strict_weak_order<_Comp,
2171 projected<iterator_t<_Range1>, _Proj1>,
2172 projected<iterator_t<_Range2>, _Proj2>>
2173 constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
2174 borrowed_iterator_t<_Range2>>
2175 operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
2176 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2185 inline constexpr __partial_sort_copy_fn partial_sort_copy{};
2187 struct __is_sorted_until_fn
2189 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2190 typename _Proj =
identity,
2191 indirect_strict_weak_order<projected<_Iter, _Proj>>
2192 _Comp = ranges::less>
2194 operator()(_Iter __first, _Sent __last,
2195 _Comp __comp = {}, _Proj __proj = {})
const
2197 if (__first == __last)
2200 auto __next = __first;
2201 for (++__next; __next != __last; __first = __next, (void)++__next)
2202 if (std::__invoke(__comp,
2203 std::__invoke(__proj, *__next),
2204 std::__invoke(__proj, *__first)))
2209 template<forward_range _Range,
typename _Proj = identity,
2210 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2211 _Comp = ranges::less>
2212 constexpr borrowed_iterator_t<_Range>
2213 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2220 inline constexpr __is_sorted_until_fn is_sorted_until{};
2222 struct __is_sorted_fn
2224 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2225 typename _Proj =
identity,
2226 indirect_strict_weak_order<projected<_Iter, _Proj>>
2227 _Comp = ranges::less>
2229 operator()(_Iter __first, _Sent __last,
2230 _Comp __comp = {}, _Proj __proj = {})
const
2232 if (__first == __last)
2235 auto __next = __first;
2236 for (++__next; __next != __last; __first = __next, (void)++__next)
2237 if (std::__invoke(__comp,
2238 std::__invoke(__proj, *__next),
2239 std::__invoke(__proj, *__first)))
2244 template<forward_range _Range,
typename _Proj = identity,
2245 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2246 _Comp = ranges::less>
2248 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2255 inline constexpr __is_sorted_fn is_sorted{};
2257 struct __nth_element_fn
2259 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2260 typename _Comp = ranges::less,
typename _Proj =
identity>
2261 requires sortable<_Iter, _Comp, _Proj>
2263 operator()(_Iter __first, _Iter __nth, _Sent __last,
2264 _Comp __comp = {}, _Proj __proj = {})
const
2266 auto __lasti = ranges::next(__first, __last);
2268 __detail::__make_comp_proj(__comp, __proj));
2272 template<random_access_range _Range,
2273 typename _Comp = ranges::less,
typename _Proj = identity>
2274 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2275 constexpr borrowed_iterator_t<_Range>
2276 operator()(_Range&& __r, iterator_t<_Range> __nth,
2277 _Comp __comp = {}, _Proj __proj = {})
const
2284 inline constexpr __nth_element_fn nth_element{};
2286 struct __lower_bound_fn
2288 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2289 typename _Tp,
typename _Proj =
identity,
2290 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2291 _Comp = ranges::less>
2293 operator()(_Iter __first, _Sent __last,
2294 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2300 auto __half = __len / 2;
2301 auto __middle = __first;
2303 if (std::__invoke(__comp, std::__invoke(__proj, *__middle), __value))
2307 __len = __len - __half - 1;
2315 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2316 indirect_strict_weak_order<
const _Tp*,
2317 projected<iterator_t<_Range>, _Proj>>
2318 _Comp = ranges::less>
2319 constexpr borrowed_iterator_t<_Range>
2320 operator()(_Range&& __r,
2321 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2328 inline constexpr __lower_bound_fn lower_bound{};
2330 struct __upper_bound_fn
2332 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2333 typename _Tp,
typename _Proj =
identity,
2334 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2335 _Comp = ranges::less>
2337 operator()(_Iter __first, _Sent __last,
2338 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2344 auto __half = __len / 2;
2345 auto __middle = __first;
2347 if (std::__invoke(__comp, __value, std::__invoke(__proj, *__middle)))
2353 __len = __len - __half - 1;
2359 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2360 indirect_strict_weak_order<
const _Tp*,
2361 projected<iterator_t<_Range>, _Proj>>
2362 _Comp = ranges::less>
2363 constexpr borrowed_iterator_t<_Range>
2364 operator()(_Range&& __r,
2365 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2372 inline constexpr __upper_bound_fn upper_bound{};
2374 struct __equal_range_fn
2376 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2377 typename _Tp,
typename _Proj =
identity,
2378 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2379 _Comp = ranges::less>
2380 constexpr subrange<_Iter>
2381 operator()(_Iter __first, _Sent __last,
2382 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2388 auto __half = __len / 2;
2389 auto __middle = __first;
2391 if (std::__invoke(__comp,
2392 std::__invoke(__proj, *__middle),
2397 __len = __len - __half - 1;
2399 else if (std::__invoke(__comp,
2401 std::__invoke(__proj, *__middle)))
2406 = ranges::lower_bound(__first, __middle,
2407 __value, __comp, __proj);
2410 = ranges::upper_bound(++__middle, __first,
2411 __value, __comp, __proj);
2412 return {__left, __right};
2415 return {__first, __first};
2418 template<forward_range _Range,
2419 typename _Tp,
typename _Proj = identity,
2420 indirect_strict_weak_order<
const _Tp*,
2421 projected<iterator_t<_Range>, _Proj>>
2422 _Comp = ranges::less>
2423 constexpr borrowed_subrange_t<_Range>
2424 operator()(_Range&& __r,
const _Tp& __value,
2425 _Comp __comp = {}, _Proj __proj = {})
const
2432 inline constexpr __equal_range_fn equal_range{};
2434 struct __binary_search_fn
2436 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2437 typename _Tp,
typename _Proj =
identity,
2438 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2439 _Comp = ranges::less>
2441 operator()(_Iter __first, _Sent __last,
2442 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2444 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2447 return !(bool)std::__invoke(__comp, __value,
2448 std::__invoke(__proj, *__i));
2451 template<forward_range _Range,
2452 typename _Tp,
typename _Proj = identity,
2453 indirect_strict_weak_order<
const _Tp*,
2454 projected<iterator_t<_Range>, _Proj>>
2455 _Comp = ranges::less>
2457 operator()(_Range&& __r,
const _Tp& __value, _Comp __comp = {},
2458 _Proj __proj = {})
const
2465 inline constexpr __binary_search_fn binary_search{};
2467 struct __is_partitioned_fn
2469 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2470 typename _Proj =
identity,
2471 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2473 operator()(_Iter __first, _Sent __last,
2474 _Pred __pred, _Proj __proj = {})
const
2476 __first = ranges::find_if_not(
std::move(__first), __last,
2478 if (__first == __last)
2485 template<input_range _Range,
typename _Proj = identity,
2486 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2489 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2496 inline constexpr __is_partitioned_fn is_partitioned{};
2498 struct __partition_fn
2500 template<permutable _Iter, sentinel_for<_Iter> _Sent,
2501 typename _Proj =
identity,
2502 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2503 constexpr subrange<_Iter>
2504 operator()(_Iter __first, _Sent __last,
2505 _Pred __pred, _Proj __proj = {})
const
2507 if constexpr (bidirectional_iterator<_Iter>)
2509 auto __lasti = ranges::next(__first, __last);
2510 auto __tail = __lasti;
2514 if (__first == __tail)
2516 else if (std::__invoke(__pred,
2517 std::__invoke(__proj, *__first)))
2523 if (__first == __tail)
2525 else if (!(
bool)std::__invoke(__pred,
2526 std::__invoke(__proj, *__tail)))
2530 ranges::iter_swap(__first, __tail);
2536 if (__first == __last)
2539 while (std::__invoke(__pred, std::__invoke(__proj, *__first)))
2540 if (++__first == __last)
2543 auto __next = __first;
2544 while (++__next != __last)
2545 if (std::__invoke(__pred, std::__invoke(__proj, *__next)))
2547 ranges::iter_swap(__first, __next);
2555 template<forward_range _Range,
typename _Proj = identity,
2556 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2558 requires permutable<iterator_t<_Range>>
2559 constexpr borrowed_subrange_t<_Range>
2560 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2567 inline constexpr __partition_fn partition{};
2569 struct __stable_partition_fn
2571 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2572 typename _Proj =
identity,
2573 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2574 requires permutable<_Iter>
2576 operator()(_Iter __first, _Sent __last,
2577 _Pred __pred, _Proj __proj = {})
const
2579 auto __lasti = ranges::next(__first, __last);
2582 __detail::__make_pred_proj(__pred, __proj));
2586 template<bidirectional_range _Range,
typename _Proj = identity,
2587 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2589 requires permutable<iterator_t<_Range>>
2590 borrowed_subrange_t<_Range>
2591 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2598 inline constexpr __stable_partition_fn stable_partition{};
2600 template<
typename _Iter,
typename _Out1,
typename _Out2>
2601 struct in_out_out_result
2603 [[no_unique_address]] _Iter in;
2604 [[no_unique_address]] _Out1 out1;
2605 [[no_unique_address]] _Out2 out2;
2607 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2608 requires convertible_to<const _Iter&, _IIter>
2609 && convertible_to<const _Out1&, _OOut1>
2610 && convertible_to<const _Out2&, _OOut2>
2612 operator in_out_out_result<_IIter, _OOut1, _OOut2>()
const &
2613 {
return {in, out1, out2}; }
2615 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2616 requires convertible_to<_Iter, _IIter>
2617 && convertible_to<_Out1, _OOut1>
2618 && convertible_to<_Out2, _OOut2>
2620 operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2624 template<
typename _Iter,
typename _Out1,
typename _Out2>
2625 using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2627 struct __partition_copy_fn
2629 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2630 weakly_incrementable _Out1, weakly_incrementable _O2,
2631 typename _Proj =
identity,
2632 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2633 requires indirectly_copyable<_Iter, _Out1>
2634 && indirectly_copyable<_Iter, _O2>
2635 constexpr partition_copy_result<_Iter, _Out1, _O2>
2636 operator()(_Iter __first, _Sent __last,
2637 _Out1 __out_true, _O2 __out_false,
2638 _Pred __pred, _Proj __proj = {})
const
2640 for (; __first != __last; ++__first)
2641 if (std::__invoke(__pred, std::__invoke(__proj, *__first)))
2643 *__out_true = *__first;
2648 *__out_false = *__first;
2656 template<input_range _Range, weakly_incrementable _Out1,
2657 weakly_incrementable _O2,
2658 typename _Proj = identity,
2659 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2661 requires indirectly_copyable<iterator_t<_Range>, _Out1>
2662 && indirectly_copyable<iterator_t<_Range>, _O2>
2663 constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _O2>
2664 operator()(_Range&& __r, _Out1 out_true, _O2 out_false,
2665 _Pred __pred, _Proj __proj = {})
const
2673 inline constexpr __partition_copy_fn partition_copy{};
2675 struct __partition_point_fn
2677 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2678 typename _Proj =
identity,
2679 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2681 operator()(_Iter __first, _Sent __last,
2682 _Pred __pred, _Proj __proj = {})
const
2688 auto __half = __len / 2;
2689 auto __middle = __first;
2691 if (std::__invoke(__pred, std::__invoke(__proj, *__middle)))
2695 __len = __len - __half - 1;
2703 template<forward_range _Range,
typename _Proj = identity,
2704 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2706 constexpr borrowed_iterator_t<_Range>
2707 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2714 inline constexpr __partition_point_fn partition_point{};
2716 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2717 using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2721 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2722 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2723 weakly_incrementable _Out,
typename _Comp = ranges::less,
2724 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2725 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2726 constexpr merge_result<_Iter1, _Iter2, _Out>
2727 operator()(_Iter1 __first1, _Sent1 __last1,
2728 _Iter2 __first2, _Sent2 __last2, _Out __result,
2730 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2732 while (__first1 != __last1 && __first2 != __last2)
2734 if (std::__invoke(__comp,
2735 std::__invoke(__proj2, *__first2),
2736 std::__invoke(__proj1, *__first1)))
2738 *__result = *__first2;
2743 *__result = *__first1;
2756 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2757 typename _Comp = ranges::less,
2758 typename _Proj1 = identity,
typename _Proj2 = identity>
2759 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2760 _Comp, _Proj1, _Proj2>
2761 constexpr merge_result<borrowed_iterator_t<_Range1>,
2762 borrowed_iterator_t<_Range2>,
2764 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2766 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2775 inline constexpr __merge_fn merge{};
2777 struct __inplace_merge_fn
2779 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2780 typename _Comp = ranges::less,
2781 typename _Proj =
identity>
2782 requires sortable<_Iter, _Comp, _Proj>
2784 operator()(_Iter __first, _Iter __middle, _Sent __last,
2785 _Comp __comp = {}, _Proj __proj = {})
const
2787 auto __lasti = ranges::next(__first, __last);
2789 __detail::__make_comp_proj(__comp, __proj));
2793 template<bidirectional_range _Range,
2794 typename _Comp = ranges::less,
typename _Proj = identity>
2795 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2796 borrowed_iterator_t<_Range>
2797 operator()(_Range&& __r, iterator_t<_Range> __middle,
2798 _Comp __comp = {}, _Proj __proj = {})
const
2806 inline constexpr __inplace_merge_fn inplace_merge{};
2808 struct __includes_fn
2810 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2811 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2812 typename _Proj1 =
identity,
typename _Proj2 =
identity,
2813 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2814 projected<_Iter2, _Proj2>>
2815 _Comp = ranges::less>
2817 operator()(_Iter1 __first1, _Sent1 __last1,
2818 _Iter2 __first2, _Sent2 __last2,
2820 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2822 while (__first1 != __last1 && __first2 != __last2)
2823 if (std::__invoke(__comp,
2824 std::__invoke(__proj2, *__first2),
2825 std::__invoke(__proj1, *__first1)))
2827 else if (std::__invoke(__comp,
2828 std::__invoke(__proj1, *__first1),
2829 std::__invoke(__proj2, *__first2)))
2837 return __first2 == __last2;
2840 template<input_range _Range1, input_range _Range2,
2841 typename _Proj1 = identity,
typename _Proj2 = identity,
2842 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2843 projected<iterator_t<_Range2>, _Proj2>>
2844 _Comp = ranges::less>
2846 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2847 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2856 inline constexpr __includes_fn includes{};
2858 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2859 using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2861 struct __set_union_fn
2863 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2864 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2865 weakly_incrementable _Out,
typename _Comp = ranges::less,
2866 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2867 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2868 constexpr set_union_result<_Iter1, _Iter2, _Out>
2869 operator()(_Iter1 __first1, _Sent1 __last1,
2870 _Iter2 __first2, _Sent2 __last2,
2871 _Out __result, _Comp __comp = {},
2872 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2874 while (__first1 != __last1 && __first2 != __last2)
2876 if (std::__invoke(__comp,
2877 std::__invoke(__proj1, *__first1),
2878 std::__invoke(__proj2, *__first2)))
2880 *__result = *__first1;
2883 else if (std::__invoke(__comp,
2884 std::__invoke(__proj2, *__first2),
2885 std::__invoke(__proj1, *__first1)))
2887 *__result = *__first2;
2892 *__result = *__first1;
2906 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2907 typename _Comp = ranges::less,
2908 typename _Proj1 = identity,
typename _Proj2 = identity>
2909 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2910 _Comp, _Proj1, _Proj2>
2911 constexpr set_union_result<borrowed_iterator_t<_Range1>,
2912 borrowed_iterator_t<_Range2>, _Out>
2913 operator()(_Range1&& __r1, _Range2&& __r2,
2914 _Out __result, _Comp __comp = {},
2915 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2924 inline constexpr __set_union_fn set_union{};
2926 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2927 using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2929 struct __set_intersection_fn
2931 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2932 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2933 weakly_incrementable _Out,
typename _Comp = ranges::less,
2934 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2935 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2936 constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2937 operator()(_Iter1 __first1, _Sent1 __last1,
2938 _Iter2 __first2, _Sent2 __last2, _Out __result,
2940 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2942 while (__first1 != __last1 && __first2 != __last2)
2943 if (std::__invoke(__comp,
2944 std::__invoke(__proj1, *__first1),
2945 std::__invoke(__proj2, *__first2)))
2947 else if (std::__invoke(__comp,
2948 std::__invoke(__proj2, *__first2),
2949 std::__invoke(__proj1, *__first1)))
2953 *__result = *__first1;
2964 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2965 typename _Comp = ranges::less,
2966 typename _Proj1 = identity,
typename _Proj2 = identity>
2967 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2968 _Comp, _Proj1, _Proj2>
2969 constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
2970 borrowed_iterator_t<_Range2>, _Out>
2971 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2973 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2982 inline constexpr __set_intersection_fn set_intersection{};
2984 template<
typename _Iter,
typename _Out>
2985 using set_difference_result = in_out_result<_Iter, _Out>;
2987 struct __set_difference_fn
2989 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2990 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2991 weakly_incrementable _Out,
typename _Comp = ranges::less,
2992 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2993 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2994 constexpr set_difference_result<_Iter1, _Out>
2995 operator()(_Iter1 __first1, _Sent1 __last1,
2996 _Iter2 __first2, _Sent2 __last2, _Out __result,
2998 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3000 while (__first1 != __last1 && __first2 != __last2)
3001 if (std::__invoke(__comp,
3002 std::__invoke(__proj1, *__first1),
3003 std::__invoke(__proj2, *__first2)))
3005 *__result = *__first1;
3009 else if (std::__invoke(__comp,
3010 std::__invoke(__proj2, *__first2),
3011 std::__invoke(__proj1, *__first1)))
3022 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3023 typename _Comp = ranges::less,
3024 typename _Proj1 = identity,
typename _Proj2 = identity>
3025 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3026 _Comp, _Proj1, _Proj2>
3027 constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
3028 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
3030 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3039 inline constexpr __set_difference_fn set_difference{};
3041 template<
typename _Iter1,
typename _Iter2,
typename _Out>
3042 using set_symmetric_difference_result
3043 = in_in_out_result<_Iter1, _Iter2, _Out>;
3045 struct __set_symmetric_difference_fn
3047 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3048 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3049 weakly_incrementable _Out,
typename _Comp = ranges::less,
3050 typename _Proj1 =
identity,
typename _Proj2 =
identity>
3051 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
3052 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
3053 operator()(_Iter1 __first1, _Sent1 __last1,
3054 _Iter2 __first2, _Sent2 __last2,
3055 _Out __result, _Comp __comp = {},
3056 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3058 while (__first1 != __last1 && __first2 != __last2)
3059 if (std::__invoke(__comp,
3060 std::__invoke(__proj1, *__first1),
3061 std::__invoke(__proj2, *__first2)))
3063 *__result = *__first1;
3067 else if (std::__invoke(__comp,
3068 std::__invoke(__proj2, *__first2),
3069 std::__invoke(__proj1, *__first1)))
3071 *__result = *__first2;
3088 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3089 typename _Comp = ranges::less,
3090 typename _Proj1 = identity,
typename _Proj2 = identity>
3091 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3092 _Comp, _Proj1, _Proj2>
3093 constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
3094 borrowed_iterator_t<_Range2>,
3096 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
3098 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3107 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
3111 template<
typename _Tp,
typename _Proj = identity,
3112 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3113 _Comp = ranges::less>
3114 constexpr
const _Tp&
3115 operator()(
const _Tp& __a,
const _Tp& __b,
3116 _Comp __comp = {}, _Proj __proj = {})
const
3119 std::__invoke(__proj, __b),
3120 std::__invoke(__proj, __a)))
3126 template<input_range _Range,
typename _Proj = identity,
3127 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3128 _Comp = ranges::less>
3129 requires indirectly_copyable_storable<iterator_t<_Range>,
3130 range_value_t<_Range>*>
3131 constexpr range_value_t<_Range>
3132 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3136 __glibcxx_assert(__first != __last);
3137 auto __result = *__first;
3138 while (++__first != __last)
3140 auto __tmp = *__first;
3141 if (std::__invoke(__comp,
3142 std::__invoke(__proj, __tmp),
3143 std::__invoke(__proj, __result)))
3149 template<copyable _Tp,
typename _Proj = identity,
3150 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3151 _Comp = ranges::less>
3153 operator()(initializer_list<_Tp> __r,
3154 _Comp __comp = {}, _Proj __proj = {})
const
3156 return (*
this)(ranges::subrange(__r),
3161 inline constexpr __min_fn
min{};
3165 template<
typename _Tp,
typename _Proj = identity,
3166 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3167 _Comp = ranges::less>
3168 constexpr
const _Tp&
3169 operator()(
const _Tp& __a,
const _Tp& __b,
3170 _Comp __comp = {}, _Proj __proj = {})
const
3173 std::__invoke(__proj, __a),
3174 std::__invoke(__proj, __b)))
3180 template<input_range _Range,
typename _Proj = identity,
3181 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3182 _Comp = ranges::less>
3183 requires indirectly_copyable_storable<iterator_t<_Range>,
3184 range_value_t<_Range>*>
3185 constexpr range_value_t<_Range>
3186 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3190 __glibcxx_assert(__first != __last);
3191 auto __result = *__first;
3192 while (++__first != __last)
3194 auto __tmp = *__first;
3195 if (std::__invoke(__comp,
3196 std::__invoke(__proj, __result),
3197 std::__invoke(__proj, __tmp)))
3203 template<copyable _Tp,
typename _Proj = identity,
3204 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3205 _Comp = ranges::less>
3207 operator()(initializer_list<_Tp> __r,
3208 _Comp __comp = {}, _Proj __proj = {})
const
3210 return (*
this)(ranges::subrange(__r),
3215 inline constexpr __max_fn
max{};
3219 template<
typename _Tp,
typename _Proj = identity,
3220 indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
3222 constexpr
const _Tp&
3223 operator()(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi,
3224 _Comp __comp = {}, _Proj __proj = {})
const
3226 __glibcxx_assert(!(std::__invoke(__comp,
3227 std::__invoke(__proj, __hi),
3228 std::__invoke(__proj, __lo))));
3229 auto&& __proj_val = std::__invoke(__proj, __val);
3230 if (std::__invoke(__comp, __proj_val, std::__invoke(__proj, __lo)))
3232 else if (std::__invoke(__comp, std::__invoke(__proj, __hi), __proj_val))
3239 inline constexpr __clamp_fn clamp{};
3241 template<
typename _Tp>
3242 struct min_max_result
3244 [[no_unique_address]] _Tp
min;
3245 [[no_unique_address]] _Tp
max;
3247 template<
typename _Tp2>
3248 requires convertible_to<const _Tp&, _Tp2>
3250 operator min_max_result<_Tp2>()
const &
3253 template<
typename _Tp2>
3254 requires convertible_to<_Tp, _Tp2>
3256 operator min_max_result<_Tp2>() &&
3260 template<
typename _Tp>
3261 using minmax_result = min_max_result<_Tp>;
3265 template<
typename _Tp,
typename _Proj = identity,
3266 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3267 _Comp = ranges::less>
3268 constexpr minmax_result<const _Tp&>
3269 operator()(
const _Tp& __a,
const _Tp& __b,
3270 _Comp __comp = {}, _Proj __proj = {})
const
3273 std::__invoke(__proj, __b),
3274 std::__invoke(__proj, __a)))
3280 template<input_range _Range,
typename _Proj = identity,
3281 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3282 _Comp = ranges::less>
3283 requires indirectly_copyable_storable<iterator_t<_Range>,
3284 range_value_t<_Range>*>
3285 constexpr minmax_result<range_value_t<_Range>>
3286 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3290 __glibcxx_assert(__first != __last);
3291 minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
3292 while (++__first != __last)
3294 auto __tmp = *__first;
3295 if (std::__invoke(__comp,
3296 std::__invoke(__proj, __tmp),
3297 std::__invoke(__proj, __result.min)))
3299 if (!(
bool)std::__invoke(__comp,
3300 std::__invoke(__proj, __tmp),
3301 std::__invoke(__proj, __result.max)))
3307 template<copyable _Tp,
typename _Proj = identity,
3308 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3309 _Comp = ranges::less>
3310 constexpr minmax_result<_Tp>
3311 operator()(initializer_list<_Tp> __r,
3312 _Comp __comp = {}, _Proj __proj = {})
const
3314 return (*
this)(ranges::subrange(__r),
3319 inline constexpr __minmax_fn
minmax{};
3321 struct __min_element_fn
3323 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3324 typename _Proj =
identity,
3325 indirect_strict_weak_order<projected<_Iter, _Proj>>
3326 _Comp = ranges::less>
3328 operator()(_Iter __first, _Sent __last,
3329 _Comp __comp = {}, _Proj __proj = {})
const
3331 if (__first == __last)
3335 while (++__i != __last)
3337 if (std::__invoke(__comp,
3338 std::__invoke(__proj, *__i),
3339 std::__invoke(__proj, *__first)))
3345 template<forward_range _Range,
typename _Proj = identity,
3346 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3347 _Comp = ranges::less>
3348 constexpr borrowed_iterator_t<_Range>
3349 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3356 inline constexpr __min_element_fn min_element{};
3358 struct __max_element_fn
3360 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3361 typename _Proj =
identity,
3362 indirect_strict_weak_order<projected<_Iter, _Proj>>
3363 _Comp = ranges::less>
3365 operator()(_Iter __first, _Sent __last,
3366 _Comp __comp = {}, _Proj __proj = {})
const
3368 if (__first == __last)
3372 while (++__i != __last)
3374 if (std::__invoke(__comp,
3375 std::__invoke(__proj, *__first),
3376 std::__invoke(__proj, *__i)))
3382 template<forward_range _Range,
typename _Proj = identity,
3383 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3384 _Comp = ranges::less>
3385 constexpr borrowed_iterator_t<_Range>
3386 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3393 inline constexpr __max_element_fn max_element{};
3395 template<
typename _Iter>
3396 using minmax_element_result = min_max_result<_Iter>;
3398 struct __minmax_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>
3404 constexpr minmax_element_result<_Iter>
3405 operator()(_Iter __first, _Sent __last,
3406 _Comp __comp = {}, _Proj __proj = {})
const
3408 if (__first == __last)
3409 return {__first, __first};
3411 minmax_element_result<_Iter> __result = {__first, __first};
3413 while (++__i != __last)
3415 if (std::__invoke(__comp,
3416 std::__invoke(__proj, *__i),
3417 std::__invoke(__proj, *__result.min)))
3419 if (!(
bool)std::__invoke(__comp,
3420 std::__invoke(__proj, *__i),
3421 std::__invoke(__proj, *__result.max)))
3427 template<forward_range _Range,
typename _Proj = identity,
3428 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3429 _Comp = ranges::less>
3430 constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3431 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3438 inline constexpr __minmax_element_fn minmax_element{};
3440 struct __lexicographical_compare_fn
3442 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3443 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3444 typename _Proj1 =
identity,
typename _Proj2 =
identity,
3445 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3446 projected<_Iter2, _Proj2>>
3447 _Comp = ranges::less>
3449 operator()(_Iter1 __first1, _Sent1 __last1,
3450 _Iter2 __first2, _Sent2 __last2,
3452 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3454 if constexpr (__detail::__is_normal_iterator<_Iter1>
3455 && same_as<_Iter1, _Sent1>)
3456 return (*this)(__first1.base(), __last1.base(),
3457 std::
move(__first2), std::
move(__last2),
3459 std::
move(__proj1), std::
move(__proj2));
3460 else if constexpr (__detail::__is_normal_iterator<_Iter2>
3461 && same_as<_Iter2, _Sent2>)
3462 return (*this)(std::
move(__first1), std::
move(__last1),
3463 __first2.base(), __last2.base(),
3465 std::
move(__proj1), std::
move(__proj2));
3468 constexpr
bool __sized_iters
3469 = (sized_sentinel_for<_Sent1, _Iter1>
3470 && sized_sentinel_for<_Sent2, _Iter2>);
3471 if constexpr (__sized_iters)
3473 using _ValueType1 = iter_value_t<_Iter1>;
3474 using _ValueType2 = iter_value_t<_Iter2>;
3477 constexpr
bool __use_memcmp
3478 = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3479 && __ptr_to_nonvolatile<_Iter1>
3480 && __ptr_to_nonvolatile<_Iter2>
3481 && (is_same_v<_Comp, ranges::less>
3482 || is_same_v<_Comp, ranges::greater>)
3483 && is_same_v<_Proj1, identity>
3484 && is_same_v<_Proj2, identity>);
3485 if constexpr (__use_memcmp)
3487 const auto __d1 = __last1 - __first1;
3488 const auto __d2 = __last2 - __first2;
3490 if (
const auto __len =
std::min(__d1, __d2))
3493 = std::__memcmp(__first1, __first2, __len);
3494 if constexpr (is_same_v<_Comp, ranges::less>)
3501 else if constexpr (is_same_v<_Comp, ranges::greater>)
3513 for (; __first1 != __last1 && __first2 != __last2;
3514 ++__first1, (void) ++__first2)
3516 if (std::__invoke(__comp,
3517 std::__invoke(__proj1, *__first1),
3518 std::__invoke(__proj2, *__first2)))
3520 if (std::__invoke(__comp,
3521 std::__invoke(__proj2, *__first2),
3522 std::__invoke(__proj1, *__first1)))
3525 return __first1 == __last1 && __first2 != __last2;
3529 template<input_range _Range1, input_range _Range2,
3530 typename _Proj1 = identity,
typename _Proj2 = identity,
3531 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3532 projected<iterator_t<_Range2>, _Proj2>>
3533 _Comp = ranges::less>
3535 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3536 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3545 template<
typename _Iter,
typename _Ref = iter_reference_t<_Iter>>
3546 static constexpr
bool __ptr_to_nonvolatile
3547 = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3550 inline constexpr __lexicographical_compare_fn lexicographical_compare;
3552 template<
typename _Iter>
3553 struct in_found_result
3555 [[no_unique_address]] _Iter in;
3558 template<
typename _Iter2>
3559 requires convertible_to<const _Iter&, _Iter2>
3561 operator in_found_result<_Iter2>()
const &
3562 {
return {in, found}; }
3564 template<
typename _Iter2>
3565 requires convertible_to<_Iter, _Iter2>
3567 operator in_found_result<_Iter2>() &&
3571 template<
typename _Iter>
3572 using next_permutation_result = in_found_result<_Iter>;
3574 struct __next_permutation_fn
3576 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3577 typename _Comp = ranges::less,
typename _Proj =
identity>
3578 requires sortable<_Iter, _Comp, _Proj>
3579 constexpr next_permutation_result<_Iter>
3580 operator()(_Iter __first, _Sent __last,
3581 _Comp __comp = {}, _Proj __proj = {})
const
3583 if (__first == __last)
3591 auto __lasti = ranges::next(__first, __last);
3599 if (std::__invoke(__comp,
3600 std::__invoke(__proj, *__i),
3601 std::__invoke(__proj, *__ii)))
3604 while (!(
bool)std::__invoke(__comp,
3605 std::__invoke(__proj, *__i),
3606 std::__invoke(__proj, *--__j)))
3608 ranges::iter_swap(__i, __j);
3609 ranges::reverse(__ii, __last);
3614 ranges::reverse(__first, __last);
3620 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3621 typename _Proj = identity>
3622 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3623 constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3624 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3631 inline constexpr __next_permutation_fn next_permutation{};
3633 template<
typename _Iter>
3634 using prev_permutation_result = in_found_result<_Iter>;
3636 struct __prev_permutation_fn
3638 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3639 typename _Comp = ranges::less,
typename _Proj =
identity>
3640 requires sortable<_Iter, _Comp, _Proj>
3641 constexpr prev_permutation_result<_Iter>
3642 operator()(_Iter __first, _Sent __last,
3643 _Comp __comp = {}, _Proj __proj = {})
const
3645 if (__first == __last)
3653 auto __lasti = ranges::next(__first, __last);
3661 if (std::__invoke(__comp,
3662 std::__invoke(__proj, *__ii),
3663 std::__invoke(__proj, *__i)))
3666 while (!(
bool)std::__invoke(__comp,
3667 std::__invoke(__proj, *--__j),
3668 std::__invoke(__proj, *__i)))
3670 ranges::iter_swap(__i, __j);
3671 ranges::reverse(__ii, __last);
3676 ranges::reverse(__first, __last);
3682 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3683 typename _Proj = identity>
3684 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3685 constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3686 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3693 inline constexpr __prev_permutation_fn prev_permutation{};
3697 #define __cpp_lib_shift 201806L
3698 template<
typename _ForwardIterator>
3699 constexpr _ForwardIterator
3700 shift_left(_ForwardIterator __first, _ForwardIterator __last,
3701 typename iterator_traits<_ForwardIterator>::difference_type __n)
3703 __glibcxx_assert(__n >= 0);
3707 auto __mid = ranges::next(__first, __n, __last);
3708 if (__mid == __last)
3713 template<
typename _ForwardIterator>
3714 constexpr _ForwardIterator
3715 shift_right(_ForwardIterator __first, _ForwardIterator __last,
3716 typename iterator_traits<_ForwardIterator>::difference_type __n)
3718 __glibcxx_assert(__n >= 0);
3723 =
typename iterator_traits<_ForwardIterator>::iterator_category;
3724 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
3726 auto __mid = ranges::next(__last, -__n, __first);
3727 if (__mid == __first)
3735 auto __result = ranges::next(__first, __n, __last);
3736 if (__result == __last)
3739 auto __dest_head = __first, __dest_tail = __result;
3740 while (__dest_head != __result)
3742 if (__dest_tail == __last)
3767 auto __cursor = __first;
3768 while (__cursor != __result)
3770 if (__dest_tail == __last)
3775 __dest_head =
std::move(__cursor, __result,
3790 _GLIBCXX_END_NAMESPACE_VERSION
3794 #endif // _RANGES_ALGO_H
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
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 void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Construct a heap over a range using comparison functor.
constexpr void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort a heap using comparison functor.
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...
constexpr void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
Sort a sequence just enough to find a particular position using a predicate for comparison.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp)
Merges two sorted ranges in place.
constexpr void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Pop an element off a heap using comparison functor.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last, _UniformRandomNumberGenerator &&__g)
Shuffle the elements of a sequence using a uniform random number generator.
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
_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...
constexpr void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
Sort the elements of a sequence using a predicate for comparison.