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);
59 template<
typename _Pred,
typename _Proj>
61 __make_pred_proj(_Pred& __pred, _Proj& __proj)
63 return [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
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)
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)
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)
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>
155 struct for_each_result
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>
163 operator for_each_result<_Iter2, _F2p>() const &
164 {
return {in, fun}; }
166 template<
typename _Iter2,
typename _F2p>
167 requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
168 operator for_each_result<_Iter2, _F2p>() &&
174 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
175 typename _Proj =
identity,
176 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
177 constexpr for_each_result<_Iter, _Fun>
178 operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {})
const
180 for (; __first != __last; ++__first)
185 template<input_range _Range,
typename _Proj = identity,
186 indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
188 constexpr for_each_result<safe_iterator_t<_Range>, _Fun>
189 operator()(_Range&& __r, _Fun __f, _Proj __proj = {})
const
196 inline constexpr __for_each_fn for_each{};
200 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
201 typename _Proj =
identity>
202 requires indirect_binary_predicate<ranges::equal_to,
203 projected<_Iter, _Proj>,
const _Tp*>
205 operator()(_Iter __first, _Sent __last,
206 const _Tp& __value, _Proj __proj = {})
const
208 while (__first != __last
214 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
215 requires indirect_binary_predicate<ranges::equal_to,
216 projected<iterator_t<_Range>, _Proj>,
218 constexpr safe_iterator_t<_Range>
219 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
226 inline constexpr __find_fn find{};
230 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
231 typename _Proj =
identity,
232 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
234 operator()(_Iter __first, _Sent __last,
235 _Pred __pred, _Proj __proj = {})
const
237 while (__first != __last
243 template<input_range _Range,
typename _Proj = identity,
244 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
246 constexpr safe_iterator_t<_Range>
247 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
254 inline constexpr __find_if_fn find_if{};
256 struct __find_if_not_fn
258 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
259 typename _Proj =
identity,
260 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
262 operator()(_Iter __first, _Sent __last,
263 _Pred __pred, _Proj __proj = {})
const
265 while (__first != __last
271 template<input_range _Range,
typename _Proj = identity,
272 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
274 constexpr safe_iterator_t<_Range>
275 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
282 inline constexpr __find_if_not_fn find_if_not{};
284 struct __find_first_of_fn
286 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
287 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
288 typename _Pred = ranges::equal_to,
289 typename _Proj1 =
identity,
typename _Proj2 =
identity>
290 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
292 operator()(_Iter1 __first1, _Sent1 __last1,
293 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
294 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
296 for (; __first1 != __last1; ++__first1)
297 for (
auto __iter = __first2; __iter != __last2; ++__iter)
305 template<input_range _Range1, forward_range _Range2,
306 typename _Pred = ranges::equal_to,
307 typename _Proj1 = identity,
typename _Proj2 = identity>
308 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
309 _Pred, _Proj1, _Proj2>
310 constexpr safe_iterator_t<_Range1>
311 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
312 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
321 inline constexpr __find_first_of_fn find_first_of{};
325 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
326 typename _Tp,
typename _Proj =
identity>
327 requires indirect_binary_predicate<ranges::equal_to,
328 projected<_Iter, _Proj>,
330 constexpr iter_difference_t<_Iter>
331 operator()(_Iter __first, _Sent __last,
332 const _Tp& __value, _Proj __proj = {})
const
334 iter_difference_t<_Iter> __n = 0;
335 for (; __first != __last; ++__first)
341 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
342 requires indirect_binary_predicate<ranges::equal_to,
343 projected<iterator_t<_Range>, _Proj>,
345 constexpr range_difference_t<_Range>
346 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
353 inline constexpr __count_fn count{};
357 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
358 typename _Proj =
identity,
359 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
360 constexpr iter_difference_t<_Iter>
361 operator()(_Iter __first, _Sent __last,
362 _Pred __pred, _Proj __proj = {})
const
364 iter_difference_t<_Iter> __n = 0;
365 for (; __first != __last; ++__first)
371 template<input_range _Range,
372 typename _Proj = identity,
373 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
375 constexpr range_difference_t<_Range>
376 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
383 inline constexpr __count_if_fn count_if{};
385 template<
typename _Iter1,
typename _Iter2>
386 struct mismatch_result
388 [[no_unique_address]] _Iter1 in1;
389 [[no_unique_address]] _Iter2 in2;
391 template<
typename _IIter1,
typename _IIter2>
392 requires convertible_to<const _Iter1&, _IIter1>
393 && convertible_to<const _Iter2&, _IIter2>
394 operator mismatch_result<_IIter1, _IIter2>() const &
395 {
return {in1, in2}; }
397 template<
typename _IIter1,
typename _IIter2>
398 requires convertible_to<_Iter1, _IIter1>
399 && convertible_to<_Iter2, _IIter2>
400 operator mismatch_result<_IIter1, _IIter2>() &&
406 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
407 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
408 typename _Pred = ranges::equal_to,
409 typename _Proj1 =
identity,
typename _Proj2 =
identity>
410 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
411 constexpr mismatch_result<_Iter1, _Iter2>
412 operator()(_Iter1 __first1, _Sent1 __last1,
413 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
414 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
416 while (__first1 != __last1 && __first2 != __last2
427 template<input_range _Range1, input_range _Range2,
428 typename _Pred = ranges::equal_to,
429 typename _Proj1 = identity,
typename _Proj2 = identity>
430 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
431 _Pred, _Proj1, _Proj2>
432 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
433 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
434 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
443 inline constexpr __mismatch_fn mismatch{};
447 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
448 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
449 typename _Pred = ranges::equal_to,
450 typename _Proj1 =
identity,
typename _Proj2 =
identity>
451 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
452 constexpr subrange<_Iter1>
453 operator()(_Iter1 __first1, _Sent1 __last1,
454 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
455 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
457 if (__first1 == __last1 || __first2 == __last2)
458 return {__first1, __first1};
464 if (__first1 == __last1)
465 return {__first1, __first1};
472 auto __cur1 = __first1;
473 auto __cur2 = __first2;
476 if (++__cur2 == __last2)
477 return {__first1, ++__cur1};
478 if (++__cur1 == __last1)
479 return {__cur1, __cur1};
491 template<forward_range _Range1, forward_range _Range2,
492 typename _Pred = ranges::equal_to,
493 typename _Proj1 = identity,
typename _Proj2 = identity>
494 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
495 _Pred, _Proj1, _Proj2>
496 constexpr safe_subrange_t<_Range1>
497 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
498 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
507 inline constexpr __search_fn search{};
511 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
512 typename _Pred = ranges::equal_to,
typename _Proj =
identity>
513 requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
514 constexpr subrange<_Iter>
515 operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
516 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const
519 return {__first, __first};
521 auto __value_comp = [&] <
typename _Rp> (_Rp&& __arg) {
522 return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
526 __first = ranges::find_if(
std::move(__first), __last,
529 if (__first == __last)
530 return {__first, __first};
533 auto __end = __first;
534 return {__first, ++__end};
538 if constexpr (sized_sentinel_for<_Sent, _Iter>)
540 auto __tail_size = __last - __first;
541 auto __remainder = __count;
543 while (__remainder <= __tail_size)
545 __first += __remainder;
546 __tail_size -= __remainder;
547 auto __backtrack = __first;
550 if (--__remainder == 0)
551 return {__first - __count, __first};
554 auto __i = __first + __tail_size;
559 __first = ranges::find_if(__first, __last, __value_comp, __proj);
560 while (__first != __last)
565 while (__i != __last && __n != 1
572 return {__first, __i};
575 __first = ranges::find_if(++__i, __last, __value_comp, __proj);
577 return {__first, __first};
581 template<forward_range _Range,
typename _Tp,
582 typename _Pred = ranges::equal_to,
typename _Proj = identity>
583 requires indirectly_comparable<iterator_t<_Range>,
const _Tp*,
585 constexpr safe_subrange_t<_Range>
586 operator()(_Range&& __r, range_difference_t<_Range> __count,
587 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const
595 inline constexpr __search_n_fn search_n{};
599 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
600 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
601 typename _Pred = ranges::equal_to,
602 typename _Proj1 =
identity,
typename _Proj2 =
identity>
603 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
604 constexpr subrange<_Iter1>
605 operator()(_Iter1 __first1, _Sent1 __last1,
606 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
607 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
609 if constexpr (bidirectional_iterator<_Iter1>
610 && bidirectional_iterator<_Iter2>)
612 auto __i1 = ranges::next(__first1, __last1);
613 auto __i2 = ranges::next(__first2, __last2);
615 = ranges::search(reverse_iterator<_Iter1>{__i1},
616 reverse_iterator<_Iter1>{__first1},
617 reverse_iterator<_Iter2>{__i2},
618 reverse_iterator<_Iter2>{__first2},
621 auto __result_first =
ranges::end(__rresult).base();
623 if (__result_last == __first1)
626 return {__result_first, __result_last};
630 auto __i = ranges::next(__first1, __last1);
631 if (__first2 == __last2)
634 auto __result_begin = __i;
635 auto __result_end = __i;
638 auto __new_range = ranges::search(__first1, __last1,
640 __pred, __proj1, __proj2);
643 if (__new_result_begin == __last1)
644 return {__result_begin, __result_end};
647 __result_begin = __new_result_begin;
648 __result_end = __new_result_end;
649 __first1 = __result_begin;
656 template<forward_range _Range1, forward_range _Range2,
657 typename _Pred = ranges::equal_to,
658 typename _Proj1 = identity,
typename _Proj2 = identity>
659 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
660 _Pred, _Proj1, _Proj2>
661 constexpr safe_subrange_t<_Range1>
662 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
663 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
672 inline constexpr __find_end_fn find_end{};
674 struct __adjacent_find_fn
676 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
677 typename _Proj =
identity,
678 indirect_binary_predicate<projected<_Iter, _Proj>,
679 projected<_Iter, _Proj>> _Pred
682 operator()(_Iter __first, _Sent __last,
683 _Pred __pred = {}, _Proj __proj = {})
const
685 if (__first == __last)
687 auto __next = __first;
688 for (; ++__next != __last; __first = __next)
698 template<forward_range _Range,
typename _Proj = identity,
699 indirect_binary_predicate<
700 projected<iterator_t<_Range>, _Proj>,
701 projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
702 constexpr safe_iterator_t<_Range>
703 operator()(_Range&& __r, _Pred __pred = {}, _Proj __proj = {})
const
710 inline constexpr __adjacent_find_fn adjacent_find{};
712 struct __is_permutation_fn
714 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
715 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
716 typename _Proj1 =
identity,
typename _Proj2 =
identity,
717 indirect_equivalence_relation<projected<_Iter1, _Proj1>,
718 projected<_Iter2, _Proj2>> _Pred
721 operator()(_Iter1 __first1, _Sent1 __last1,
722 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
723 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
725 constexpr
bool __sized_iters
726 = (sized_sentinel_for<_Sent1, _Iter1>
727 && sized_sentinel_for<_Sent2, _Iter2>);
728 if constexpr (__sized_iters)
738 for (; __first1 != __last1 && __first2 != __last2;
739 ++__first1, (void)++__first2)
745 if constexpr (__sized_iters)
747 if (__first1 == __last1)
754 if (__d1 == 0 && __d2 == 0)
760 for (
auto __scan = __first1; __scan != __last1; ++__scan)
763 auto __comp_scan = [&] <
typename _Tp> (_Tp&& __arg) {
765 std::forward<_Tp>(__arg));
767 if (__scan != ranges::find_if(__first1, __scan,
768 __comp_scan, __proj1))
771 auto __matches = ranges::count_if(__first2, __last2,
772 __comp_scan, __proj2);
774 || ranges::count_if(__scan, __last1,
775 __comp_scan, __proj1) != __matches)
781 template<forward_range _Range1, forward_range _Range2,
782 typename _Proj1 = identity,
typename _Proj2 = identity,
783 indirect_equivalence_relation<
784 projected<iterator_t<_Range1>, _Proj1>,
785 projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
787 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
788 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
797 inline constexpr __is_permutation_fn is_permutation{};
799 template<
typename _Iter,
typename _Out>
800 using copy_if_result = copy_result<_Iter, _Out>;
804 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
805 weakly_incrementable _Out,
typename _Proj =
identity,
806 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
807 requires indirectly_copyable<_Iter, _Out>
808 constexpr copy_if_result<_Iter, _Out>
809 operator()(_Iter __first, _Sent __last, _Out __result,
810 _Pred __pred, _Proj __proj = {})
const
812 for (; __first != __last; ++__first)
815 *__result = *__first;
821 template<input_range _Range, weakly_incrementable _Out,
822 typename _Proj = identity,
823 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
825 requires indirectly_copyable<iterator_t<_Range>, _Out>
826 constexpr copy_if_result<safe_iterator_t<_Range>, _Out>
827 operator()(_Range&& __r, _Out __result,
828 _Pred __pred, _Proj __proj = {})
const
836 inline constexpr __copy_if_fn copy_if{};
838 template<
typename _Iter1,
typename _Iter2>
839 using swap_ranges_result = mismatch_result<_Iter1, _Iter2>;
841 struct __swap_ranges_fn
843 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
844 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
845 requires indirectly_swappable<_Iter1, _Iter2>
846 constexpr swap_ranges_result<_Iter1, _Iter2>
847 operator()(_Iter1 __first1, _Sent1 __last1,
848 _Iter2 __first2, _Sent2 __last2)
const
850 for (; __first1 != __last1 && __first2 != __last2;
851 ++__first1, (void)++__first2)
852 ranges::iter_swap(__first1, __first2);
856 template<input_range _Range1, input_range _Range2>
857 requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
858 constexpr swap_ranges_result<safe_iterator_t<_Range1>,
859 safe_iterator_t<_Range2>>
860 operator()(_Range1&& __r1, _Range2&& __r2)
const
867 inline constexpr __swap_ranges_fn swap_ranges{};
869 template<
typename _Iter,
typename _Out>
870 using unary_transform_result = copy_result<_Iter, _Out>;
872 template<
typename _Iter1,
typename _Iter2,
typename _Out>
873 struct binary_transform_result
875 [[no_unique_address]] _Iter1 in1;
876 [[no_unique_address]] _Iter2 in2;
877 [[no_unique_address]] _Out out;
879 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
880 requires convertible_to<const _Iter1&, _IIter1>
881 && convertible_to<const _Iter2&, _IIter2>
882 && convertible_to<const _Out&, _OOut>
883 operator binary_transform_result<_IIter1, _IIter2, _OOut>() const &
884 {
return {in1, in2, out}; }
886 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
887 requires convertible_to<_Iter1, _IIter1>
888 && convertible_to<_Iter2, _IIter2>
889 && convertible_to<_Out, _OOut>
890 operator binary_transform_result<_IIter1, _IIter2, _OOut>() &&
894 struct __transform_fn
896 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
897 weakly_incrementable _Out,
898 copy_constructible _Fp,
typename _Proj =
identity>
899 requires indirectly_writable<_Out,
900 indirect_result_t<_Fp&,
901 projected<_Iter, _Proj>>>
902 constexpr unary_transform_result<_Iter, _Out>
903 operator()(_Iter __first1, _Sent __last1, _Out __result,
904 _Fp __op, _Proj __proj = {})
const
906 for (; __first1 != __last1; ++__first1, (void)++__result)
911 template<input_range _Range, weakly_incrementable _Out,
912 copy_constructible _Fp,
typename _Proj = identity>
913 requires indirectly_writable<_Out,
914 indirect_result_t<_Fp&,
915 projected<iterator_t<_Range>, _Proj>>>
916 constexpr unary_transform_result<safe_iterator_t<_Range>, _Out>
917 operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {})
const
924 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
925 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
926 weakly_incrementable _Out, copy_constructible _Fp,
927 typename _Proj1 =
identity,
typename _Proj2 =
identity>
928 requires indirectly_writable<_Out,
929 indirect_result_t<_Fp&,
930 projected<_Iter1, _Proj1>,
931 projected<_Iter2, _Proj2>>>
932 constexpr binary_transform_result<_Iter1, _Iter2, _Out>
933 operator()(_Iter1 __first1, _Sent1 __last1,
934 _Iter2 __first2, _Sent2 __last2,
935 _Out __result, _Fp __binary_op,
936 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
938 for (; __first1 != __last1 && __first2 != __last2;
939 ++__first1, (void)++__first2, ++__result)
946 template<input_range _Range1, input_range _Range2,
947 weakly_incrementable _Out, copy_constructible _Fp,
948 typename _Proj1 = identity,
typename _Proj2 = identity>
949 requires indirectly_writable<_Out,
950 indirect_result_t<_Fp&,
951 projected<iterator_t<_Range1>, _Proj1>,
952 projected<iterator_t<_Range2>, _Proj2>>>
953 constexpr binary_transform_result<safe_iterator_t<_Range1>,
954 safe_iterator_t<_Range2>, _Out>
955 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
956 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
965 inline constexpr __transform_fn transform{};
969 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
970 typename _Tp1,
typename _Tp2,
typename _Proj =
identity>
971 requires indirectly_writable<_Iter, const _Tp2&>
972 && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
975 operator()(_Iter __first, _Sent __last,
976 const _Tp1& __old_value,
const _Tp2& __new_value,
977 _Proj __proj = {})
const
979 for (; __first != __last; ++__first)
981 *__first = __new_value;
985 template<input_range _Range,
986 typename _Tp1,
typename _Tp2,
typename _Proj = identity>
987 requires indirectly_writable<iterator_t<_Range>,
const _Tp2&>
988 && indirect_binary_predicate<ranges::equal_to,
989 projected<iterator_t<_Range>, _Proj>,
991 constexpr safe_iterator_t<_Range>
992 operator()(_Range&& __r,
993 const _Tp1& __old_value,
const _Tp2& __new_value,
994 _Proj __proj = {})
const
997 __old_value, __new_value,
std::move(__proj));
1001 inline constexpr __replace_fn replace{};
1003 struct __replace_if_fn
1005 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1006 typename _Tp,
typename _Proj =
identity,
1007 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1008 requires indirectly_writable<_Iter, const _Tp&>
1010 operator()(_Iter __first, _Sent __last,
1011 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
1013 for (; __first != __last; ++__first)
1015 *__first = __new_value;
1019 template<input_range _Range,
typename _Tp,
typename _Proj = identity,
1020 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1022 requires indirectly_writable<iterator_t<_Range>,
const _Tp&>
1023 constexpr safe_iterator_t<_Range>
1024 operator()(_Range&& __r,
1025 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
1032 inline constexpr __replace_if_fn replace_if{};
1034 template<
typename _Iter,
typename _Out>
1035 using replace_copy_result = copy_result<_Iter, _Out>;
1037 struct __replace_copy_fn
1039 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1040 typename _Tp1,
typename _Tp2, output_iterator<const _Tp2&> _Out,
1041 typename _Proj =
identity>
1042 requires indirectly_copyable<_Iter, _Out>
1043 && indirect_binary_predicate<ranges::equal_to,
1044 projected<_Iter, _Proj>,
const _Tp1*>
1045 constexpr replace_copy_result<_Iter, _Out>
1046 operator()(_Iter __first, _Sent __last, _Out __result,
1047 const _Tp1& __old_value,
const _Tp2& __new_value,
1048 _Proj __proj = {})
const
1050 for (; __first != __last; ++__first, (void)++__result)
1052 *__result = __new_value;
1054 *__result = *__first;
1058 template<input_range _Range,
typename _Tp1,
typename _Tp2,
1059 output_iterator<const _Tp2&> _Out,
typename _Proj = identity>
1060 requires indirectly_copyable<iterator_t<_Range>, _Out>
1061 && indirect_binary_predicate<ranges::equal_to,
1062 projected<iterator_t<_Range>, _Proj>,
1064 constexpr replace_copy_result<safe_iterator_t<_Range>, _Out>
1065 operator()(_Range&& __r, _Out __result,
1066 const _Tp1& __old_value,
const _Tp2& __new_value,
1067 _Proj __proj = {})
const
1075 inline constexpr __replace_copy_fn replace_copy{};
1077 template<
typename _Iter,
typename _Out>
1078 using replace_copy_if_result = copy_result<_Iter, _Out>;
1080 struct __replace_copy_if_fn
1082 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1083 typename _Tp, output_iterator<const _Tp&> _Out,
1084 typename _Proj =
identity,
1085 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1086 requires indirectly_copyable<_Iter, _Out>
1087 constexpr replace_copy_if_result<_Iter, _Out>
1088 operator()(_Iter __first, _Sent __last, _Out __result,
1089 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
1091 for (; __first != __last; ++__first, (void)++__result)
1093 *__result = __new_value;
1095 *__result = *__first;
1099 template<input_range _Range,
1100 typename _Tp, output_iterator<const _Tp&> _Out,
1101 typename _Proj = identity,
1102 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1104 requires indirectly_copyable<iterator_t<_Range>, _Out>
1105 constexpr replace_copy_if_result<safe_iterator_t<_Range>, _Out>
1106 operator()(_Range&& __r, _Out __result,
1107 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
1115 inline constexpr __replace_copy_if_fn replace_copy_if{};
1117 struct __generate_n_fn
1119 template<input_or_output_iterator _Out, copy_constructible _Fp>
1120 requires invocable<_Fp&>
1121 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
1123 operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen)
const
1125 for (; __n > 0; --__n, (void)++__first)
1131 inline constexpr __generate_n_fn generate_n{};
1133 struct __generate_fn
1135 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
1136 copy_constructible _Fp>
1137 requires invocable<_Fp&>
1138 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
1140 operator()(_Out __first, _Sent __last, _Fp __gen)
const
1142 for (; __first != __last; ++__first)
1147 template<
typename _Range, copy_constructible _Fp>
1148 requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
1149 constexpr safe_iterator_t<_Range>
1150 operator()(_Range&& __r, _Fp __gen)
const
1156 inline constexpr __generate_fn generate{};
1158 struct __remove_if_fn
1160 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1161 typename _Proj =
identity,
1162 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1163 constexpr subrange<_Iter>
1164 operator()(_Iter __first, _Sent __last,
1165 _Pred __pred, _Proj __proj = {})
const
1167 __first = ranges::find_if(__first, __last, __pred, __proj);
1168 if (__first == __last)
1169 return {__first, __first};
1171 auto __result = __first;
1173 for (; __first != __last; ++__first)
1180 return {__result, __first};
1183 template<forward_range _Range,
typename _Proj = identity,
1184 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1186 requires permutable<iterator_t<_Range>>
1187 constexpr safe_subrange_t<_Range>
1188 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
1195 inline constexpr __remove_if_fn remove_if{};
1199 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1200 typename _Tp,
typename _Proj =
identity>
1201 requires indirect_binary_predicate<ranges::equal_to,
1202 projected<_Iter, _Proj>,
1204 constexpr subrange<_Iter>
1205 operator()(_Iter __first, _Sent __last,
1206 const _Tp& __value, _Proj __proj = {})
const
1208 auto __pred = [&] (
auto&& __arg) {
1209 return std::forward<decltype(__arg)>(__arg) == __value;
1211 return ranges::remove_if(__first, __last,
1215 template<forward_range _Range,
typename _Tp,
typename _Proj =
identity>
1216 requires permutable<iterator_t<_Range>>
1217 && indirect_binary_predicate<ranges::equal_to,
1218 projected<iterator_t<_Range>, _Proj>,
1220 constexpr safe_subrange_t<_Range>
1221 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
1228 inline constexpr __remove_fn remove{};
1230 template<
typename _Iter,
typename _Out>
1231 using remove_copy_if_result = copy_result<_Iter, _Out>;
1233 struct __remove_copy_if_fn
1235 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1236 weakly_incrementable _Out,
typename _Proj =
identity,
1237 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1238 requires indirectly_copyable<_Iter, _Out>
1239 constexpr remove_copy_if_result<_Iter, _Out>
1240 operator()(_Iter __first, _Sent __last, _Out __result,
1241 _Pred __pred, _Proj __proj = {})
const
1243 for (; __first != __last; ++__first)
1246 *__result = *__first;
1252 template<input_range _Range, weakly_incrementable _Out,
1253 typename _Proj = identity,
1254 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1256 requires indirectly_copyable<iterator_t<_Range>, _Out>
1257 constexpr remove_copy_if_result<safe_iterator_t<_Range>, _Out>
1258 operator()(_Range&& __r, _Out __result,
1259 _Pred __pred, _Proj __proj = {})
const
1267 inline constexpr __remove_copy_if_fn remove_copy_if{};
1269 template<
typename _Iter,
typename _Out>
1270 using remove_copy_result = copy_result<_Iter, _Out>;
1272 struct __remove_copy_fn
1274 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1275 weakly_incrementable _Out,
typename _Tp,
typename _Proj =
identity>
1276 requires indirectly_copyable<_Iter, _Out>
1277 && indirect_binary_predicate<ranges::equal_to,
1278 projected<_Iter, _Proj>,
1280 constexpr remove_copy_result<_Iter, _Out>
1281 operator()(_Iter __first, _Sent __last, _Out __result,
1282 const _Tp& __value, _Proj __proj = {})
const
1284 for (; __first != __last; ++__first)
1287 *__result = *__first;
1293 template<input_range _Range, weakly_incrementable _Out,
1294 typename _Tp,
typename _Proj = identity>
1295 requires indirectly_copyable<iterator_t<_Range>, _Out>
1296 && indirect_binary_predicate<ranges::equal_to,
1297 projected<iterator_t<_Range>, _Proj>,
1299 constexpr remove_copy_result<safe_iterator_t<_Range>, _Out>
1300 operator()(_Range&& __r, _Out __result,
1301 const _Tp& __value, _Proj __proj = {})
const
1308 inline constexpr __remove_copy_fn remove_copy{};
1312 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1313 typename _Proj =
identity,
1314 indirect_equivalence_relation<
1315 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1316 constexpr subrange<_Iter>
1317 operator()(_Iter __first, _Sent __last,
1318 _Comp __comp = {}, _Proj __proj = {})
const
1320 __first = ranges::adjacent_find(__first, __last, __comp, __proj);
1321 if (__first == __last)
1322 return {__first, __first};
1324 auto __dest = __first;
1326 while (++__first != __last)
1331 return {++__dest, __first};
1334 template<forward_range _Range,
typename _Proj = identity,
1335 indirect_equivalence_relation<
1336 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1337 requires permutable<iterator_t<_Range>>
1338 constexpr safe_subrange_t<_Range>
1339 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1346 inline constexpr __unique_fn unique{};
1348 template<
typename _Iter,
typename _Out>
1349 using unique_copy_result = copy_result<_Iter, _Out>;
1351 struct __unique_copy_fn
1353 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1354 weakly_incrementable _Out,
typename _Proj =
identity,
1355 indirect_equivalence_relation<
1356 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1357 requires indirectly_copyable<_Iter, _Out>
1358 && (forward_iterator<_Iter>
1359 || (input_iterator<_Out>
1360 && same_as<iter_value_t<_Iter>, iter_value_t<_Out>>)
1361 || indirectly_copyable_storable<_Iter, _Out>)
1362 constexpr unique_copy_result<_Iter, _Out>
1363 operator()(_Iter __first, _Sent __last, _Out __result,
1364 _Comp __comp = {}, _Proj __proj = {})
const
1366 if (__first == __last)
1370 if constexpr (forward_iterator<_Iter>)
1372 auto __next = __first;
1373 *__result = *__next;
1374 while (++__next != __last)
1380 *++__result = *__first;
1384 else if constexpr (input_iterator<_Out>
1385 && same_as<iter_value_t<_Iter>, iter_value_t<_Out>>)
1387 *__result = *__first;
1388 while (++__first != __last)
1392 *++__result = *__first;
1397 auto __value = *__first;
1398 *__result = __value;
1399 while (++__first != __last)
1406 *++__result = __value;
1413 template<input_range _Range,
1414 weakly_incrementable _Out,
typename _Proj = identity,
1415 indirect_equivalence_relation<
1416 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1417 requires indirectly_copyable<iterator_t<_Range>, _Out>
1418 && (forward_iterator<iterator_t<_Range>>
1419 || (input_iterator<_Out>
1420 && same_as<range_value_t<_Range>, iter_value_t<_Out>>)
1421 || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1422 constexpr unique_copy_result<safe_iterator_t<_Range>, _Out>
1423 operator()(_Range&& __r, _Out __result,
1424 _Comp __comp = {}, _Proj __proj = {})
const
1432 inline constexpr __unique_copy_fn unique_copy{};
1436 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1437 requires permutable<_Iter>
1439 operator()(_Iter __first, _Sent __last)
const
1441 auto __i = ranges::next(__first, __last);
1444 if constexpr (random_access_iterator<_Iter>)
1446 if (__first != __last)
1449 while (__first < __tail)
1451 ranges::iter_swap(__first, __tail);
1461 if (__first == __tail || __first == --__tail)
1465 ranges::iter_swap(__first, __tail);
1472 template<b
idirectional_range _Range>
1473 requires permutable<iterator_t<_Range>>
1474 constexpr safe_iterator_t<_Range>
1475 operator()(_Range&& __r)
const
1481 inline constexpr __reverse_fn reverse{};
1483 template<
typename _Iter,
typename _Out>
1484 using reverse_copy_result = copy_result<_Iter, _Out>;
1486 struct __reverse_copy_fn
1488 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1489 weakly_incrementable _Out>
1490 requires indirectly_copyable<_Iter, _Out>
1491 constexpr reverse_copy_result<_Iter, _Out>
1492 operator()(_Iter __first, _Sent __last, _Out __result)
const
1494 auto __i = ranges::next(__first, __last);
1496 while (__first != __tail)
1499 *__result = *__tail;
1502 return {__i, __result};
1505 template<b
idirectional_range _Range, weakly_incrementable _Out>
1506 requires indirectly_copyable<iterator_t<_Range>, _Out>
1507 constexpr reverse_copy_result<safe_iterator_t<_Range>, _Out>
1508 operator()(_Range&& __r, _Out __result)
const
1515 inline constexpr __reverse_copy_fn reverse_copy{};
1519 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1520 constexpr subrange<_Iter>
1521 operator()(_Iter __first, _Iter __middle, _Sent __last)
const
1523 auto __lasti = ranges::next(__first, __last);
1524 if (__first == __middle)
1525 return {__lasti, __lasti};
1526 if (__last == __middle)
1529 if constexpr (random_access_iterator<_Iter>)
1531 auto __n = __lasti - __first;
1532 auto __k = __middle - __first;
1534 if (__k == __n - __k)
1536 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1541 auto __ret = __first + (__lasti - __middle);
1545 if (__k < __n - __k)
1549 if constexpr (__is_pod(iter_value_t<_Iter>))
1557 auto __q = __p + __k;
1558 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1560 ranges::iter_swap(__p, __q);
1567 ranges::swap(__n, __k);
1575 if constexpr (__is_pod(iter_value_t<_Iter>))
1583 auto __q = __p + __n;
1585 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1589 ranges::iter_swap(__p, __q);
1594 std::swap(__n, __k);
1598 else if constexpr (bidirectional_iterator<_Iter>)
1600 auto __tail = __lasti;
1602 ranges::reverse(__first, __middle);
1603 ranges::reverse(__middle, __tail);
1605 while (__first != __middle && __middle != __tail)
1607 ranges::iter_swap(__first, --__tail);
1611 if (__first == __middle)
1613 ranges::reverse(__middle, __tail);
1618 ranges::reverse(__first, __middle);
1624 auto __first2 = __middle;
1627 ranges::iter_swap(__first, __first2);
1630 if (__first == __middle)
1631 __middle = __first2;
1632 }
while (__first2 != __last);
1634 auto __ret = __first;
1636 __first2 = __middle;
1638 while (__first2 != __last)
1640 ranges::iter_swap(__first, __first2);
1643 if (__first == __middle)
1644 __middle = __first2;
1645 else if (__first2 == __last)
1646 __first2 = __middle;
1652 template<forward_range _Range>
1653 requires permutable<iterator_t<_Range>>
1654 constexpr safe_subrange_t<_Range>
1655 operator()(_Range&& __r, iterator_t<_Range> __middle)
const
1662 inline constexpr __rotate_fn rotate{};
1664 template<
typename _Iter,
typename _Out>
1665 using rotate_copy_result = copy_result<_Iter, _Out>;
1667 struct __rotate_copy_fn
1669 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1670 weakly_incrementable _Out>
1671 requires indirectly_copyable<_Iter, _Out>
1672 constexpr rotate_copy_result<_Iter, _Out>
1673 operator()(_Iter __first, _Iter __middle, _Sent __last,
1674 _Out __result)
const
1676 auto __copy1 = ranges::copy(__middle,
1679 auto __copy2 = ranges::copy(
std::move(__first),
1685 template<forward_range _Range, weakly_incrementable _Out>
1686 requires indirectly_copyable<iterator_t<_Range>, _Out>
1687 constexpr rotate_copy_result<safe_iterator_t<_Range>, _Out>
1688 operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result)
const
1695 inline constexpr __rotate_copy_fn rotate_copy{};
1697 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
1700 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1702 requires permutable<_Iter>
1703 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1705 operator()(_Iter __first, _Sent __last, _Gen&& __g)
const
1707 auto __lasti = ranges::next(__first, __last);
1712 template<random_access_range _Range,
typename _Gen>
1713 requires permutable<iterator_t<_Range>>
1714 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1715 safe_iterator_t<_Range>
1716 operator()(_Range&& __r, _Gen&& __g)
const
1719 std::forward<_Gen>(__g));
1723 inline constexpr __shuffle_fn shuffle{};
1726 struct __push_heap_fn
1728 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1729 typename _Comp = ranges::less,
typename _Proj =
identity>
1730 requires sortable<_Iter, _Comp, _Proj>
1732 operator()(_Iter __first, _Sent __last,
1733 _Comp __comp = {}, _Proj __proj = {})
const
1735 auto __lasti = ranges::next(__first, __last);
1737 __detail::__make_comp_proj(__comp, __proj));
1741 template<random_access_range _Range,
1742 typename _Comp = ranges::less,
typename _Proj = identity>
1743 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1744 constexpr safe_iterator_t<_Range>
1745 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1752 inline constexpr __push_heap_fn push_heap{};
1754 struct __pop_heap_fn
1756 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1757 typename _Comp = ranges::less,
typename _Proj =
identity>
1758 requires sortable<_Iter, _Comp, _Proj>
1760 operator()(_Iter __first, _Sent __last,
1761 _Comp __comp = {}, _Proj __proj = {})
const
1763 auto __lasti = ranges::next(__first, __last);
1765 __detail::__make_comp_proj(__comp, __proj));
1769 template<random_access_range _Range,
1770 typename _Comp = ranges::less,
typename _Proj = identity>
1771 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1772 constexpr safe_iterator_t<_Range>
1773 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1780 inline constexpr __pop_heap_fn pop_heap{};
1782 struct __make_heap_fn
1784 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1785 typename _Comp = ranges::less,
typename _Proj =
identity>
1786 requires sortable<_Iter, _Comp, _Proj>
1788 operator()(_Iter __first, _Sent __last,
1789 _Comp __comp = {}, _Proj __proj = {})
const
1791 auto __lasti = ranges::next(__first, __last);
1793 __detail::__make_comp_proj(__comp, __proj));
1797 template<random_access_range _Range,
1798 typename _Comp = ranges::less,
typename _Proj = identity>
1799 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1800 constexpr safe_iterator_t<_Range>
1801 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1808 inline constexpr __make_heap_fn make_heap{};
1810 struct __sort_heap_fn
1812 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1813 typename _Comp = ranges::less,
typename _Proj =
identity>
1814 requires sortable<_Iter, _Comp, _Proj>
1816 operator()(_Iter __first, _Sent __last,
1817 _Comp __comp = {}, _Proj __proj = {})
const
1819 auto __lasti = ranges::next(__first, __last);
1821 __detail::__make_comp_proj(__comp, __proj));
1825 template<random_access_range _Range,
1826 typename _Comp = ranges::less,
typename _Proj = identity>
1827 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1828 constexpr safe_iterator_t<_Range>
1829 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1836 inline constexpr __sort_heap_fn sort_heap{};
1838 struct __is_heap_until_fn
1840 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1841 typename _Proj =
identity,
1842 indirect_strict_weak_order<projected<_Iter, _Proj>>
1843 _Comp = ranges::less>
1845 operator()(_Iter __first, _Sent __last,
1846 _Comp __comp = {}, _Proj __proj = {})
const
1849 iter_difference_t<_Iter> __parent = 0, __child = 1;
1850 for (; __child < __n; ++__child)
1854 return __first + __child;
1855 else if ((__child & 1) == 0)
1858 return __first + __n;
1861 template<random_access_range _Range,
1862 typename _Proj = identity,
1863 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1864 _Comp = ranges::less>
1865 constexpr safe_iterator_t<_Range>
1866 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1873 inline constexpr __is_heap_until_fn is_heap_until{};
1877 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1878 typename _Proj =
identity,
1879 indirect_strict_weak_order<projected<_Iter, _Proj>>
1880 _Comp = ranges::less>
1882 operator()(_Iter __first, _Sent __last,
1883 _Comp __comp = {}, _Proj __proj = {})
const
1886 == ranges::is_heap_until(__first, __last,
1891 template<random_access_range _Range,
1892 typename _Proj = identity,
1893 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1894 _Comp = ranges::less>
1896 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1903 inline constexpr __is_heap_fn is_heap{};
1907 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1908 typename _Comp = ranges::less,
typename _Proj =
identity>
1909 requires sortable<_Iter, _Comp, _Proj>
1911 operator()(_Iter __first, _Sent __last,
1912 _Comp __comp = {}, _Proj __proj = {})
const
1914 auto __lasti = ranges::next(__first, __last);
1916 __detail::__make_comp_proj(__comp, __proj));
1920 template<random_access_range _Range,
1921 typename _Comp = ranges::less,
typename _Proj = identity>
1922 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1923 constexpr safe_iterator_t<_Range>
1924 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1931 inline constexpr __sort_fn sort{};
1933 struct __stable_sort_fn
1935 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1936 typename _Comp = ranges::less,
typename _Proj =
identity>
1937 requires sortable<_Iter, _Comp, _Proj>
1939 operator()(_Iter __first, _Sent __last,
1940 _Comp __comp = {}, _Proj __proj = {})
const
1942 auto __lasti = ranges::next(__first, __last);
1944 __detail::__make_comp_proj(__comp, __proj));
1948 template<random_access_range _Range,
1949 typename _Comp = ranges::less,
typename _Proj = identity>
1950 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1951 safe_iterator_t<_Range>
1952 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1959 inline constexpr __stable_sort_fn stable_sort{};
1961 struct __partial_sort_fn
1963 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1964 typename _Comp = ranges::less,
typename _Proj =
identity>
1965 requires sortable<_Iter, _Comp, _Proj>
1967 operator()(_Iter __first, _Iter __middle, _Sent __last,
1968 _Comp __comp = {}, _Proj __proj = {})
const
1970 if (__first == __middle)
1971 return ranges::next(__first, __last);
1973 ranges::make_heap(__first, __middle, __comp, __proj);
1974 auto __i = __middle;
1975 for (; __i != __last; ++__i)
1980 ranges::pop_heap(__first, __middle, __comp, __proj);
1981 ranges::iter_swap(__middle-1, __i);
1982 ranges::push_heap(__first, __middle, __comp, __proj);
1984 ranges::sort_heap(__first, __middle, __comp, __proj);
1989 template<random_access_range _Range,
1990 typename _Comp = ranges::less,
typename _Proj = identity>
1991 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1992 constexpr safe_iterator_t<_Range>
1993 operator()(_Range&& __r, iterator_t<_Range> __middle,
1994 _Comp __comp = {}, _Proj __proj = {})
const
2002 inline constexpr __partial_sort_fn partial_sort{};
2004 template<
typename _Iter,
typename _Out>
2005 using partial_sort_copy_result = copy_result<_Iter, _Out>;
2007 struct __partial_sort_copy_fn
2009 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2010 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2011 typename _Comp = ranges::less,
2012 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2013 requires indirectly_copyable<_Iter1, _Iter2>
2014 && sortable<_Iter2, _Comp, _Proj2>
2015 && indirect_strict_weak_order<_Comp,
2016 projected<_Iter1, _Proj1>,
2017 projected<_Iter2, _Proj2>>
2018 constexpr partial_sort_copy_result<_Iter1, _Iter2>
2019 operator()(_Iter1 __first, _Sent1 __last,
2020 _Iter2 __result_first, _Sent2 __result_last,
2022 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2024 if (__result_first == __result_last)
2027 auto __lasti = ranges::next(
std::move(__first),
2032 auto __result_real_last = __result_first;
2033 while (__first != __last && __result_real_last != __result_last)
2035 *__result_real_last = *__first;
2036 ++__result_real_last;
2040 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
2041 for (; __first != __last; ++__first)
2046 ranges::pop_heap(__result_first, __result_real_last,
2048 *(__result_real_last-1) = *__first;
2049 ranges::push_heap(__result_first, __result_real_last,
2052 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
2057 template<input_range _Range1, random_access_range _Range2,
2058 typename _Comp = ranges::less,
2059 typename _Proj1 = identity,
typename _Proj2 = identity>
2060 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
2061 && sortable<iterator_t<_Range2>, _Comp, _Proj2>
2062 && indirect_strict_weak_order<_Comp,
2063 projected<iterator_t<_Range1>, _Proj1>,
2064 projected<iterator_t<_Range2>, _Proj2>>
2065 constexpr partial_sort_copy_result<safe_iterator_t<_Range1>,
2066 safe_iterator_t<_Range2>>
2067 operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
2068 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2077 inline constexpr __partial_sort_copy_fn partial_sort_copy{};
2079 struct __is_sorted_until_fn
2081 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2082 typename _Proj =
identity,
2083 indirect_strict_weak_order<projected<_Iter, _Proj>>
2084 _Comp = ranges::less>
2086 operator()(_Iter __first, _Sent __last,
2087 _Comp __comp = {}, _Proj __proj = {})
const
2089 if (__first == __last)
2092 auto __next = __first;
2093 for (++__next; __next != __last; __first = __next, (void)++__next)
2101 template<forward_range _Range,
typename _Proj = identity,
2102 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2103 _Comp = ranges::less>
2104 constexpr safe_iterator_t<_Range>
2105 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2112 inline constexpr __is_sorted_until_fn is_sorted_until{};
2114 struct __is_sorted_fn
2116 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2117 typename _Proj =
identity,
2118 indirect_strict_weak_order<projected<_Iter, _Proj>>
2119 _Comp = ranges::less>
2121 operator()(_Iter __first, _Sent __last,
2122 _Comp __comp = {}, _Proj __proj = {})
const
2124 if (__first == __last)
2127 auto __next = __first;
2128 for (++__next; __next != __last; __first = __next, (void)++__next)
2136 template<forward_range _Range,
typename _Proj = identity,
2137 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2138 _Comp = ranges::less>
2140 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2147 inline constexpr __is_sorted_fn is_sorted{};
2149 struct __nth_element_fn
2151 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2152 typename _Comp = ranges::less,
typename _Proj =
identity>
2153 requires sortable<_Iter, _Comp, _Proj>
2155 operator()(_Iter __first, _Iter __nth, _Sent __last,
2156 _Comp __comp = {}, _Proj __proj = {})
const
2158 auto __lasti = ranges::next(__first, __last);
2160 __detail::__make_comp_proj(__comp, __proj));
2164 template<random_access_range _Range,
2165 typename _Comp = ranges::less,
typename _Proj = identity>
2166 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2167 constexpr safe_iterator_t<_Range>
2168 operator()(_Range&& __r, iterator_t<_Range> __nth,
2169 _Comp __comp = {}, _Proj __proj = {})
const
2176 inline constexpr __nth_element_fn nth_element{};
2178 struct __lower_bound_fn
2180 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2181 typename _Tp,
typename _Proj =
identity,
2182 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2183 _Comp = ranges::less>
2185 operator()(_Iter __first, _Sent __last,
2186 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2192 auto __half = __len / 2;
2193 auto __middle = __first;
2199 __len = __len - __half - 1;
2207 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2208 indirect_strict_weak_order<
const _Tp*,
2209 projected<iterator_t<_Range>, _Proj>>
2210 _Comp = ranges::less>
2211 constexpr safe_iterator_t<_Range>
2212 operator()(_Range&& __r,
2213 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2220 inline constexpr __lower_bound_fn lower_bound{};
2222 struct __upper_bound_fn
2224 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2225 typename _Tp,
typename _Proj =
identity,
2226 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2227 _Comp = ranges::less>
2229 operator()(_Iter __first, _Sent __last,
2230 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2236 auto __half = __len / 2;
2237 auto __middle = __first;
2245 __len = __len - __half - 1;
2251 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2252 indirect_strict_weak_order<
const _Tp*,
2253 projected<iterator_t<_Range>, _Proj>>
2254 _Comp = ranges::less>
2255 constexpr safe_iterator_t<_Range>
2256 operator()(_Range&& __r,
2257 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2264 inline constexpr __upper_bound_fn upper_bound{};
2266 struct __equal_range_fn
2268 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2269 typename _Tp,
typename _Proj =
identity,
2270 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2271 _Comp = ranges::less>
2272 constexpr subrange<_Iter>
2273 operator()(_Iter __first, _Sent __last,
2274 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2280 auto __half = __len / 2;
2281 auto __middle = __first;
2289 __len = __len - __half - 1;
2298 = ranges::lower_bound(__first, __middle,
2299 __value, __comp, __proj);
2302 = ranges::upper_bound(++__middle, __first,
2303 __value, __comp, __proj);
2304 return {__left, __right};
2307 return {__first, __first};
2310 template<forward_range _Range,
2311 typename _Tp,
typename _Proj = identity,
2312 indirect_strict_weak_order<
const _Tp*,
2313 projected<iterator_t<_Range>, _Proj>>
2314 _Comp = ranges::less>
2315 constexpr safe_subrange_t<_Range>
2316 operator()(_Range&& __r,
const _Tp& __value,
2317 _Comp __comp = {}, _Proj __proj = {})
const
2324 inline constexpr __equal_range_fn equal_range{};
2326 struct __binary_search_fn
2328 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2329 typename _Tp,
typename _Proj =
identity,
2330 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2331 _Comp = ranges::less>
2333 operator()(_Iter __first, _Sent __last,
2334 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2336 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2343 template<forward_range _Range,
2344 typename _Tp,
typename _Proj = identity,
2345 indirect_strict_weak_order<
const _Tp*,
2346 projected<iterator_t<_Range>, _Proj>>
2347 _Comp = ranges::less>
2349 operator()(_Range&& __r,
const _Tp& __value, _Comp __comp = {},
2350 _Proj __proj = {})
const
2357 inline constexpr __binary_search_fn binary_search{};
2359 struct __is_partitioned_fn
2361 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2362 typename _Proj =
identity,
2363 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2365 operator()(_Iter __first, _Sent __last,
2366 _Pred __pred, _Proj __proj = {})
const
2368 __first = ranges::find_if_not(
std::move(__first), __last,
2370 if (__first == __last)
2377 template<input_range _Range,
typename _Proj = identity,
2378 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2381 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2388 inline constexpr __is_partitioned_fn is_partitioned{};
2390 struct __partition_fn
2392 template<permutable _Iter, sentinel_for<_Iter> _Sent,
2393 typename _Proj =
identity,
2394 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2395 constexpr subrange<_Iter>
2396 operator()(_Iter __first, _Sent __last,
2397 _Pred __pred, _Proj __proj = {})
const
2399 if constexpr (bidirectional_iterator<_Iter>)
2401 auto __lasti = ranges::next(__first, __last);
2402 auto __tail = __lasti;
2406 if (__first == __tail)
2415 if (__first == __tail)
2422 ranges::iter_swap(__first, __tail);
2428 if (__first == __last)
2432 if (++__first == __last)
2435 auto __next = __first;
2436 while (++__next != __last)
2439 ranges::iter_swap(__first, __next);
2447 template<forward_range _Range,
typename _Proj = identity,
2448 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2450 requires permutable<iterator_t<_Range>>
2451 constexpr safe_subrange_t<_Range>
2452 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2459 inline constexpr __partition_fn partition{};
2461 struct __stable_partition_fn
2463 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2464 typename _Proj =
identity,
2465 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2466 requires permutable<_Iter>
2468 operator()(_Iter __first, _Sent __last,
2469 _Pred __pred, _Proj __proj = {})
const
2471 auto __lasti = ranges::next(__first, __last);
2474 __detail::__make_pred_proj(__pred, __proj));
2478 template<bidirectional_range _Range,
typename _Proj = identity,
2479 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2481 requires permutable<iterator_t<_Range>>
2482 safe_subrange_t<_Range>
2483 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2490 inline constexpr __stable_partition_fn stable_partition{};
2492 template<
typename _Iter,
typename _Out1,
typename _O2>
2493 struct partition_copy_result
2495 [[no_unique_address]] _Iter in;
2496 [[no_unique_address]] _Out1 out1;
2497 [[no_unique_address]] _O2 out2;
2499 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2500 requires convertible_to<const _Iter&, _IIter>
2501 && convertible_to<const _Out1&, _OOut1>
2502 && convertible_to<const _O2&, _OOut2>
2503 operator partition_copy_result<_IIter, _OOut1, _OOut2>() const &
2504 {
return {in, out1, out2}; }
2506 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2507 requires convertible_to<_Iter, _IIter>
2508 && convertible_to<_Out1, _OOut1>
2509 && convertible_to<_O2, _OOut2>
2510 operator partition_copy_result<_IIter, _OOut1, _OOut2>() &&
2514 struct __partition_copy_fn
2516 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2517 weakly_incrementable _Out1, weakly_incrementable _O2,
2518 typename _Proj =
identity,
2519 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2520 requires indirectly_copyable<_Iter, _Out1>
2521 && indirectly_copyable<_Iter, _O2>
2522 constexpr partition_copy_result<_Iter, _Out1, _O2>
2523 operator()(_Iter __first, _Sent __last,
2524 _Out1 __out_true, _O2 __out_false,
2525 _Pred __pred, _Proj __proj = {})
const
2527 for (; __first != __last; ++__first)
2530 *__out_true = *__first;
2535 *__out_false = *__first;
2543 template<input_range _Range, weakly_incrementable _Out1,
2544 weakly_incrementable _O2,
2545 typename _Proj = identity,
2546 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2548 requires indirectly_copyable<iterator_t<_Range>, _Out1>
2549 && indirectly_copyable<iterator_t<_Range>, _O2>
2550 constexpr partition_copy_result<safe_iterator_t<_Range>, _Out1, _O2>
2551 operator()(_Range&& __r, _Out1 out_true, _O2 out_false,
2552 _Pred __pred, _Proj __proj = {})
const
2560 inline constexpr __partition_copy_fn partition_copy{};
2562 struct __partition_point_fn
2564 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2565 typename _Proj =
identity,
2566 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2568 operator()(_Iter __first, _Sent __last,
2569 _Pred __pred, _Proj __proj = {})
const
2575 auto __half = __len / 2;
2576 auto __middle = __first;
2582 __len = __len - __half - 1;
2590 template<forward_range _Range,
typename _Proj = identity,
2591 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2593 constexpr safe_iterator_t<_Range>
2594 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2601 inline constexpr __partition_point_fn partition_point{};
2603 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2604 using merge_result = binary_transform_result<_Iter1, _Iter2, _Out>;
2608 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2609 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2610 weakly_incrementable _Out,
typename _Comp = ranges::less,
2611 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2612 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2613 constexpr merge_result<_Iter1, _Iter2, _Out>
2614 operator()(_Iter1 __first1, _Sent1 __last1,
2615 _Iter2 __first2, _Sent2 __last2, _Out __result,
2617 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2619 while (__first1 != __last1 && __first2 != __last2)
2625 *__result = *__first2;
2630 *__result = *__first1;
2643 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2644 typename _Comp = ranges::less,
2645 typename _Proj1 = identity,
typename _Proj2 = identity>
2646 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2647 _Comp, _Proj1, _Proj2>
2648 constexpr merge_result<safe_iterator_t<_Range1>,
2649 safe_iterator_t<_Range2>,
2651 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2653 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2662 inline constexpr __merge_fn merge{};
2664 struct __inplace_merge_fn
2666 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2667 typename _Comp = ranges::less,
2668 typename _Proj =
identity>
2669 requires sortable<_Iter, _Comp, _Proj>
2671 operator()(_Iter __first, _Iter __middle, _Sent __last,
2672 _Comp __comp = {}, _Proj __proj = {})
const
2674 auto __lasti = ranges::next(__first, __last);
2676 __detail::__make_comp_proj(__comp, __proj));
2680 template<bidirectional_range _Range,
2681 typename _Comp = ranges::less,
typename _Proj = identity>
2682 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2683 safe_iterator_t<_Range>
2684 operator()(_Range&& __r, iterator_t<_Range> __middle,
2685 _Comp __comp = {}, _Proj __proj = {})
const
2693 inline constexpr __inplace_merge_fn inplace_merge{};
2695 struct __includes_fn
2697 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2698 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2699 typename _Proj1 =
identity,
typename _Proj2 =
identity,
2700 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2701 projected<_Iter2, _Proj2>>
2702 _Comp = ranges::less>
2704 operator()(_Iter1 __first1, _Sent1 __last1,
2705 _Iter2 __first2, _Sent2 __last2,
2707 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2709 while (__first1 != __last1 && __first2 != __last2)
2724 return __first2 == __last2;
2727 template<input_range _Range1, input_range _Range2,
2728 typename _Proj1 = identity,
typename _Proj2 = identity,
2729 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2730 projected<iterator_t<_Range2>, _Proj2>>
2731 _Comp = ranges::less>
2733 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2734 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2743 inline constexpr __includes_fn includes{};
2745 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2746 using set_union_result = binary_transform_result<_Iter1, _Iter2, _Out>;
2748 struct __set_union_fn
2750 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2751 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2752 weakly_incrementable _Out,
typename _Comp = ranges::less,
2753 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2754 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2755 constexpr set_union_result<_Iter1, _Iter2, _Out>
2756 operator()(_Iter1 __first1, _Sent1 __last1,
2757 _Iter2 __first2, _Sent2 __last2,
2758 _Out __result, _Comp __comp = {},
2759 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2761 while (__first1 != __last1 && __first2 != __last2)
2767 *__result = *__first1;
2774 *__result = *__first2;
2779 *__result = *__first1;
2793 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2794 typename _Comp = ranges::less,
2795 typename _Proj1 = identity,
typename _Proj2 = identity>
2796 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2797 _Comp, _Proj1, _Proj2>
2798 constexpr set_union_result<safe_iterator_t<_Range1>,
2799 safe_iterator_t<_Range2>, _Out>
2800 operator()(_Range1&& __r1, _Range2&& __r2,
2801 _Out __result, _Comp __comp = {},
2802 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2811 inline constexpr __set_union_fn set_union{};
2813 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2814 using set_intersection_result
2815 = binary_transform_result<_Iter1, _Iter2, _Out>;
2817 struct __set_intersection_fn
2819 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2820 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2821 weakly_incrementable _Out,
typename _Comp = ranges::less,
2822 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2823 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2824 constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2825 operator()(_Iter1 __first1, _Sent1 __last1,
2826 _Iter2 __first2, _Sent2 __last2, _Out __result,
2828 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2830 while (__first1 != __last1 && __first2 != __last2)
2841 *__result = *__first1;
2852 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2853 typename _Comp = ranges::less,
2854 typename _Proj1 = identity,
typename _Proj2 = identity>
2855 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2856 _Comp, _Proj1, _Proj2>
2857 constexpr set_intersection_result<safe_iterator_t<_Range1>,
2858 safe_iterator_t<_Range2>, _Out>
2859 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2861 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2870 inline constexpr __set_intersection_fn set_intersection{};
2872 template<
typename _Iter,
typename _Out>
2873 using set_difference_result = copy_result<_Iter, _Out>;
2875 struct __set_difference_fn
2877 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2878 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2879 weakly_incrementable _Out,
typename _Comp = ranges::less,
2880 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2881 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2882 constexpr set_difference_result<_Iter1, _Out>
2883 operator()(_Iter1 __first1, _Sent1 __last1,
2884 _Iter2 __first2, _Sent2 __last2, _Out __result,
2886 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2888 while (__first1 != __last1 && __first2 != __last2)
2893 *__result = *__first1;
2910 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2911 typename _Comp = ranges::less,
2912 typename _Proj1 = identity,
typename _Proj2 = identity>
2913 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2914 _Comp, _Proj1, _Proj2>
2915 constexpr set_difference_result<safe_iterator_t<_Range1>, _Out>
2916 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2918 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2927 inline constexpr __set_difference_fn set_difference{};
2929 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2930 using set_symmetric_difference_result
2931 = binary_transform_result<_Iter1, _Iter2, _Out>;
2933 struct __set_symmetric_difference_fn
2935 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2936 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2937 weakly_incrementable _Out,
typename _Comp = ranges::less,
2938 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2939 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2940 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
2941 operator()(_Iter1 __first1, _Sent1 __last1,
2942 _Iter2 __first2, _Sent2 __last2,
2943 _Out __result, _Comp __comp = {},
2944 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2946 while (__first1 != __last1 && __first2 != __last2)
2951 *__result = *__first1;
2959 *__result = *__first2;
2976 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2977 typename _Comp = ranges::less,
2978 typename _Proj1 = identity,
typename _Proj2 = identity>
2979 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2980 _Comp, _Proj1, _Proj2>
2981 constexpr set_symmetric_difference_result<safe_iterator_t<_Range1>,
2982 safe_iterator_t<_Range2>,
2984 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2986 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2995 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
2999 template<
typename _Tp,
typename _Proj = identity,
3000 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3001 _Comp = ranges::less>
3002 constexpr
const _Tp&
3003 operator()(
const _Tp& __a,
const _Tp& __b,
3004 _Comp __comp = {}, _Proj __proj = {})
const
3014 template<input_range _Range,
typename _Proj = identity,
3015 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3016 _Comp = ranges::less>
3017 requires indirectly_copyable_storable<iterator_t<_Range>,
3018 range_value_t<_Range>*>
3019 constexpr range_value_t<_Range>
3020 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3024 __glibcxx_assert(__first != __last);
3025 auto __result = *__first;
3026 while (++__first != __last)
3028 auto __tmp = *__first;
3037 template<copyable _Tp,
typename _Proj = identity,
3038 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3039 _Comp = ranges::less>
3041 operator()(initializer_list<_Tp> __r,
3042 _Comp __comp = {}, _Proj __proj = {})
const
3044 return (*
this)(ranges::subrange(__r),
3049 inline constexpr __min_fn
min{};
3053 template<
typename _Tp,
typename _Proj = identity,
3054 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3055 _Comp = ranges::less>
3056 constexpr
const _Tp&
3057 operator()(
const _Tp& __a,
const _Tp& __b,
3058 _Comp __comp = {}, _Proj __proj = {})
const
3068 template<input_range _Range,
typename _Proj = identity,
3069 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3070 _Comp = ranges::less>
3071 requires indirectly_copyable_storable<iterator_t<_Range>,
3072 range_value_t<_Range>*>
3073 constexpr range_value_t<_Range>
3074 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3078 __glibcxx_assert(__first != __last);
3079 auto __result = *__first;
3080 while (++__first != __last)
3082 auto __tmp = *__first;
3091 template<copyable _Tp,
typename _Proj = identity,
3092 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3093 _Comp = ranges::less>
3095 operator()(initializer_list<_Tp> __r,
3096 _Comp __comp = {}, _Proj __proj = {})
const
3098 return (*
this)(ranges::subrange(__r),
3103 inline constexpr __max_fn
max{};
3105 template<
typename _Tp>
3106 struct minmax_result
3108 [[no_unique_address]] _Tp
min;
3109 [[no_unique_address]] _Tp
max;
3111 template<
typename _Tp2>
3112 requires convertible_to<const _Tp&, _Tp2>
3113 operator minmax_result<_Tp2>() const &
3116 template<
typename _Tp2>
3117 requires convertible_to<_Tp, _Tp2>
3118 operator minmax_result<_Tp2>() &&
3124 template<
typename _Tp,
typename _Proj = identity,
3125 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3126 _Comp = ranges::less>
3127 constexpr minmax_result<const _Tp&>
3128 operator()(
const _Tp& __a,
const _Tp& __b,
3129 _Comp __comp = {}, _Proj __proj = {})
const
3139 template<input_range _Range,
typename _Proj = identity,
3140 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3141 _Comp = ranges::less>
3142 requires indirectly_copyable_storable<iterator_t<_Range>,
3143 range_value_t<_Range>*>
3144 constexpr minmax_result<range_value_t<_Range>>
3145 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3149 __glibcxx_assert(__first != __last);
3150 minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
3151 while (++__first != __last)
3153 auto __tmp = *__first;
3166 template<copyable _Tp,
typename _Proj = identity,
3167 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3168 _Comp = ranges::less>
3169 constexpr minmax_result<_Tp>
3170 operator()(initializer_list<_Tp> __r,
3171 _Comp __comp = {}, _Proj __proj = {})
const
3173 return (*
this)(ranges::subrange(__r),
3178 inline constexpr __minmax_fn
minmax{};
3180 struct __min_element_fn
3182 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3183 typename _Proj =
identity,
3184 indirect_strict_weak_order<projected<_Iter, _Proj>>
3185 _Comp = ranges::less>
3187 operator()(_Iter __first, _Sent __last,
3188 _Comp __comp = {}, _Proj __proj = {})
const
3190 if (__first == __last)
3194 while (++__i != __last)
3204 template<forward_range _Range,
typename _Proj = identity,
3205 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3206 _Comp = ranges::less>
3207 constexpr safe_iterator_t<_Range>
3208 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3215 inline constexpr __min_element_fn min_element{};
3217 struct __max_element_fn
3219 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3220 typename _Proj =
identity,
3221 indirect_strict_weak_order<projected<_Iter, _Proj>>
3222 _Comp = ranges::less>
3224 operator()(_Iter __first, _Sent __last,
3225 _Comp __comp = {}, _Proj __proj = {})
const
3227 if (__first == __last)
3231 while (++__i != __last)
3241 template<forward_range _Range,
typename _Proj = identity,
3242 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3243 _Comp = ranges::less>
3244 constexpr safe_iterator_t<_Range>
3245 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3252 inline constexpr __max_element_fn max_element{};
3254 template<
typename _Iter>
3255 using minmax_element_result = minmax_result<_Iter>;
3257 struct __minmax_element_fn
3259 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3260 typename _Proj =
identity,
3261 indirect_strict_weak_order<projected<_Iter, _Proj>>
3262 _Comp = ranges::less>
3263 constexpr minmax_element_result<_Iter>
3264 operator()(_Iter __first, _Sent __last,
3265 _Comp __comp = {}, _Proj __proj = {})
const
3267 if (__first == __last)
3268 return {__first, __first};
3270 minmax_element_result<_Iter> __result = {__first, __first};
3272 while (++__i != __last)
3286 template<forward_range _Range,
typename _Proj = identity,
3287 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3288 _Comp = ranges::less>
3289 constexpr minmax_element_result<safe_iterator_t<_Range>>
3290 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3297 inline constexpr __minmax_element_fn minmax_element{};
3299 struct __lexicographical_compare_fn
3301 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3302 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3303 typename _Proj1 =
identity,
typename _Proj2 =
identity,
3304 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3305 projected<_Iter2, _Proj2>>
3306 _Comp = ranges::less>
3308 operator()(_Iter1 __first1, _Sent1 __last1,
3309 _Iter2 __first2, _Sent2 __last2,
3311 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3313 if constexpr (__detail::__is_normal_iterator<_Iter1>
3314 || __detail::__is_normal_iterator<_Iter2>)
3315 return (*
this)(std::__niter_base(
std::move(__first1)),
3323 constexpr
bool __sized_iters
3324 = (sized_sentinel_for<_Sent1, _Iter1>
3325 && sized_sentinel_for<_Sent2, _Iter2>);
3326 if constexpr (__sized_iters)
3331 using _ValueType1 = iter_value_t<_Iter1>;
3332 using _ValueType2 = iter_value_t<_Iter2>;
3333 constexpr
bool __use_memcmp
3334 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
3335 && is_same_v<_ValueType1, _ValueType2>
3336 && is_pointer_v<_Iter1>
3337 && is_pointer_v<_Iter2>
3338 && (is_same_v<_Comp, ranges::less>
3339 || is_same_v<_Comp, ranges::greater>)
3340 && is_same_v<_Proj1, identity>
3341 && is_same_v<_Proj2, identity>);
3342 if constexpr (__use_memcmp)
3344 if (
const auto __len =
std::min(__d1, __d2))
3347 = std::__memcmp(__first1, __first2, __len);
3348 if constexpr (is_same_v<_Comp, ranges::less>)
3355 else if constexpr (is_same_v<_Comp, ranges::greater>)
3363 __builtin_unreachable();
3365 return (__last1 - __first1 < __last2 - __first2);
3369 for (; __first1 != __last1 && __first2 != __last2;
3370 ++__first1, (void) ++__first2)
3381 return __first1 == __last1 && __first2 != __last2;
3385 template<input_range _Range1, input_range _Range2,
3386 typename _Proj1 = identity,
typename _Proj2 = identity,
3387 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3388 projected<iterator_t<_Range2>, _Proj2>>
3389 _Comp = ranges::less>
3391 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3392 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3401 inline constexpr __lexicographical_compare_fn lexicographical_compare;
3403 template<
typename _Iter>
3404 struct next_permutation_result
3410 struct __next_permutation_fn
3412 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3413 typename _Comp = ranges::less,
typename _Proj =
identity>
3414 requires sortable<_Iter, _Comp, _Proj>
3415 constexpr next_permutation_result<_Iter>
3416 operator()(_Iter __first, _Sent __last,
3417 _Comp __comp = {}, _Proj __proj = {})
const
3419 if (__first == __last)
3427 auto __lasti = ranges::next(__first, __last);
3444 ranges::iter_swap(__i, __j);
3445 ranges::reverse(__ii, __last);
3450 ranges::reverse(__first, __last);
3456 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3457 typename _Proj = identity>
3458 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3459 constexpr next_permutation_result<safe_iterator_t<_Range>>
3460 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3467 inline constexpr __next_permutation_fn next_permutation{};
3469 template<
typename _Iter>
3470 using prev_permutation_result = next_permutation_result<_Iter>;
3472 struct __prev_permutation_fn
3474 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3475 typename _Comp = ranges::less,
typename _Proj =
identity>
3476 requires sortable<_Iter, _Comp, _Proj>
3477 constexpr prev_permutation_result<_Iter>
3478 operator()(_Iter __first, _Sent __last,
3479 _Comp __comp = {}, _Proj __proj = {})
const
3481 if (__first == __last)
3489 auto __lasti = ranges::next(__first, __last);
3506 ranges::iter_swap(__i, __j);
3507 ranges::reverse(__ii, __last);
3512 ranges::reverse(__first, __last);
3518 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3519 typename _Proj = identity>
3520 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3521 constexpr prev_permutation_result<safe_iterator_t<_Range>>
3522 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3529 inline constexpr __prev_permutation_fn prev_permutation{};
3532 _GLIBCXX_END_NAMESPACE_VERSION
3536 #endif // _RANGES_ALGO_H