31#define _RANGES_ALGO_H 1
33#if __cplusplus > 201703L
40namespace std _GLIBCXX_VISIBILITY(default)
42_GLIBCXX_BEGIN_NAMESPACE_VERSION
47 template<
typename _Comp,
typename _Proj>
49 __make_comp_proj(_Comp& __comp, _Proj& __proj)
51 return [&] (
auto&& __lhs,
auto&& __rhs) ->
bool {
52 using _TL =
decltype(__lhs);
53 using _TR =
decltype(__rhs);
60 template<
typename _Pred,
typename _Proj>
62 __make_pred_proj(_Pred& __pred, _Proj& __proj)
64 return [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
73 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
74 typename _Proj =
identity,
75 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
77 operator()(_Iter __first, _Sent __last,
78 _Pred __pred, _Proj __proj = {})
const
80 for (; __first != __last; ++__first)
86 template<input_range _Range,
typename _Proj = identity,
87 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
90 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
92 return (*
this)(ranges::begin(__r), ranges::end(__r),
97 inline constexpr __all_of_fn all_of{};
101 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
102 typename _Proj =
identity,
103 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
105 operator()(_Iter __first, _Sent __last,
106 _Pred __pred, _Proj __proj = {})
const
108 for (; __first != __last; ++__first)
114 template<input_range _Range,
typename _Proj = identity,
115 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
118 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
120 return (*
this)(ranges::begin(__r), ranges::end(__r),
125 inline constexpr __any_of_fn any_of{};
129 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
130 typename _Proj =
identity,
131 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
133 operator()(_Iter __first, _Sent __last,
134 _Pred __pred, _Proj __proj = {})
const
136 for (; __first != __last; ++__first)
142 template<input_range _Range,
typename _Proj = identity,
143 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
146 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
148 return (*
this)(ranges::begin(__r), ranges::end(__r),
153 inline constexpr __none_of_fn none_of{};
155 template<
typename _Iter,
typename _Fp>
158 [[no_unique_address]] _Iter in;
159 [[no_unique_address]] _Fp fun;
161 template<
typename _Iter2,
typename _F2p>
162 requires convertible_to<const _Iter&, _Iter2>
163 && convertible_to<const _Fp&, _F2p>
165 operator in_fun_result<_Iter2, _F2p>() const &
166 {
return {in, fun}; }
168 template<
typename _Iter2,
typename _F2p>
169 requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
171 operator in_fun_result<_Iter2, _F2p>() &&
175 template<
typename _Iter,
typename _Fp>
176 using for_each_result = in_fun_result<_Iter, _Fp>;
180 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
181 typename _Proj =
identity,
182 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
183 constexpr for_each_result<_Iter, _Fun>
184 operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {})
const
186 for (; __first != __last; ++__first)
191 template<input_range _Range,
typename _Proj = identity,
192 indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
194 constexpr for_each_result<borrowed_iterator_t<_Range>, _Fun>
195 operator()(_Range&& __r, _Fun __f, _Proj __proj = {})
const
197 return (*
this)(ranges::begin(__r), ranges::end(__r),
202 inline constexpr __for_each_fn for_each{};
204 template<
typename _Iter,
typename _Fp>
205 using for_each_n_result = in_fun_result<_Iter, _Fp>;
207 struct __for_each_n_fn
209 template<input_iterator _Iter,
typename _Proj = identity,
210 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
211 constexpr for_each_n_result<_Iter, _Fun>
212 operator()(_Iter __first, iter_difference_t<_Iter> __n,
213 _Fun __f, _Proj __proj = {})
const
215 if constexpr (random_access_iterator<_Iter>)
219 auto __last = __first + __n;
235 inline constexpr __for_each_n_fn
for_each_n{};
239 struct __find_first_of_fn
241 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
242 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
243 typename _Pred = ranges::equal_to,
244 typename _Proj1 =
identity,
typename _Proj2 =
identity>
245 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
247 operator()(_Iter1 __first1, _Sent1 __last1,
248 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
249 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
251 for (; __first1 != __last1; ++__first1)
252 for (
auto __iter = __first2; __iter != __last2; ++__iter)
260 template<input_range _Range1, forward_range _Range2,
261 typename _Pred = ranges::equal_to,
262 typename _Proj1 = identity,
typename _Proj2 = identity>
263 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
264 _Pred, _Proj1, _Proj2>
265 constexpr borrowed_iterator_t<_Range1>
266 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
267 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
269 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
270 ranges::begin(__r2), ranges::end(__r2),
276 inline constexpr __find_first_of_fn find_first_of{};
280 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
281 typename _Tp,
typename _Proj =
identity>
282 requires indirect_binary_predicate<ranges::equal_to,
283 projected<_Iter, _Proj>,
285 constexpr iter_difference_t<_Iter>
286 operator()(_Iter __first, _Sent __last,
287 const _Tp& __value, _Proj __proj = {})
const
289 iter_difference_t<_Iter> __n = 0;
290 for (; __first != __last; ++__first)
296 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
297 requires indirect_binary_predicate<ranges::equal_to,
298 projected<iterator_t<_Range>, _Proj>,
300 constexpr range_difference_t<_Range>
301 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
303 return (*
this)(ranges::begin(__r), ranges::end(__r),
308 inline constexpr __count_fn count{};
312 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
313 typename _Proj =
identity,
314 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
315 constexpr iter_difference_t<_Iter>
316 operator()(_Iter __first, _Sent __last,
317 _Pred __pred, _Proj __proj = {})
const
319 iter_difference_t<_Iter> __n = 0;
320 for (; __first != __last; ++__first)
326 template<input_range _Range,
327 typename _Proj = identity,
328 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
330 constexpr range_difference_t<_Range>
331 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
333 return (*
this)(ranges::begin(__r), ranges::end(__r),
338 inline constexpr __count_if_fn count_if{};
344 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
345 typename _Pred = ranges::equal_to,
typename _Proj =
identity>
346 requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
347 constexpr subrange<_Iter>
348 operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
349 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const
352 return {__first, __first};
354 auto __value_comp = [&] <
typename _Rp> (_Rp&& __arg) ->
bool {
355 return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
359 __first = ranges::find_if(
std::move(__first), __last,
362 if (__first == __last)
363 return {__first, __first};
366 auto __end = __first;
367 return {__first, ++__end};
371 if constexpr (sized_sentinel_for<_Sent, _Iter>
372 && random_access_iterator<_Iter>)
374 auto __tail_size = __last - __first;
375 auto __remainder = __count;
377 while (__remainder <= __tail_size)
379 __first += __remainder;
380 __tail_size -= __remainder;
381 auto __backtrack = __first;
384 if (--__remainder == 0)
385 return {__first - __count, __first};
387 __remainder = __count + 1 - (__first - __backtrack);
389 auto __i = __first + __tail_size;
394 __first = ranges::find_if(__first, __last, __value_comp, __proj);
395 while (__first != __last)
400 while (__i != __last && __n != 1
407 return {__first, __i};
410 __first = ranges::find_if(++__i, __last, __value_comp, __proj);
412 return {__first, __first};
416 template<forward_range _Range,
typename _Tp,
417 typename _Pred = ranges::equal_to,
typename _Proj = identity>
418 requires indirectly_comparable<iterator_t<_Range>,
const _Tp*,
420 constexpr borrowed_subrange_t<_Range>
421 operator()(_Range&& __r, range_difference_t<_Range> __count,
422 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
const
424 return (*
this)(ranges::begin(__r), ranges::end(__r),
430 inline constexpr __search_n_fn search_n{};
434 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
435 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
436 typename _Pred = ranges::equal_to,
437 typename _Proj1 =
identity,
typename _Proj2 =
identity>
438 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
439 constexpr subrange<_Iter1>
440 operator()(_Iter1 __first1, _Sent1 __last1,
441 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
442 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
444 if constexpr (bidirectional_iterator<_Iter1>
445 && bidirectional_iterator<_Iter2>)
447 auto __i1 = ranges::next(__first1, __last1);
448 auto __i2 = ranges::next(__first2, __last2);
450 = ranges::search(reverse_iterator<_Iter1>{__i1},
451 reverse_iterator<_Iter1>{__first1},
452 reverse_iterator<_Iter2>{__i2},
453 reverse_iterator<_Iter2>{__first2},
456 auto __result_first = ranges::end(__rresult).base();
457 auto __result_last = ranges::begin(__rresult).base();
458 if (__result_last == __first1)
461 return {__result_first, __result_last};
465 auto __i = ranges::next(__first1, __last1);
466 if (__first2 == __last2)
469 auto __result_begin = __i;
470 auto __result_end = __i;
473 auto __new_range = ranges::search(__first1, __last1,
475 __pred, __proj1, __proj2);
476 auto __new_result_begin = ranges::begin(__new_range);
477 auto __new_result_end = ranges::end(__new_range);
478 if (__new_result_begin == __last1)
479 return {__result_begin, __result_end};
482 __result_begin = __new_result_begin;
483 __result_end = __new_result_end;
484 __first1 = __result_begin;
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 borrowed_subrange_t<_Range1>
497 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
498 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
500 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
501 ranges::begin(__r2), ranges::end(__r2),
507 inline constexpr __find_end_fn find_end{};
511 struct __is_permutation_fn
513 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
514 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
515 typename _Proj1 =
identity,
typename _Proj2 =
identity,
516 indirect_equivalence_relation<projected<_Iter1, _Proj1>,
517 projected<_Iter2, _Proj2>> _Pred
520 operator()(_Iter1 __first1, _Sent1 __last1,
521 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
522 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
524 constexpr bool __sized_iters
525 = (sized_sentinel_for<_Sent1, _Iter1>
526 && sized_sentinel_for<_Sent2, _Iter2>);
527 if constexpr (__sized_iters)
529 auto __d1 = ranges::distance(__first1, __last1);
530 auto __d2 = ranges::distance(__first2, __last2);
537 for (; __first1 != __last1 && __first2 != __last2;
538 ++__first1, (void)++__first2)
544 if constexpr (__sized_iters)
546 if (__first1 == __last1)
551 auto __d1 = ranges::distance(__first1, __last1);
552 auto __d2 = ranges::distance(__first2, __last2);
553 if (__d1 == 0 && __d2 == 0)
559 for (
auto __scan = __first1; __scan != __last1; ++__scan)
562 auto __comp_scan = [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
564 std::forward<_Tp>(__arg));
566 if (__scan != ranges::find_if(__first1, __scan,
567 __comp_scan, __proj1))
570 auto __matches = ranges::count_if(__first2, __last2,
571 __comp_scan, __proj2);
573 || ranges::count_if(__scan, __last1,
574 __comp_scan, __proj1) != __matches)
580 template<forward_range _Range1, forward_range _Range2,
581 typename _Proj1 = identity,
typename _Proj2 = identity,
582 indirect_equivalence_relation<
583 projected<iterator_t<_Range1>, _Proj1>,
584 projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
586 operator()(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
587 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
589 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
590 ranges::begin(__r2), ranges::end(__r2),
596 inline constexpr __is_permutation_fn is_permutation{};
598 template<
typename _Iter,
typename _Out>
599 using copy_if_result = in_out_result<_Iter, _Out>;
603 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
604 weakly_incrementable _Out,
typename _Proj =
identity,
605 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
606 requires indirectly_copyable<_Iter, _Out>
607 constexpr copy_if_result<_Iter, _Out>
608 operator()(_Iter __first, _Sent __last, _Out __result,
609 _Pred __pred, _Proj __proj = {})
const
611 for (; __first != __last; ++__first)
614 *__result = *__first;
620 template<input_range _Range, weakly_incrementable _Out,
621 typename _Proj = identity,
622 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
624 requires indirectly_copyable<iterator_t<_Range>, _Out>
625 constexpr copy_if_result<borrowed_iterator_t<_Range>, _Out>
626 operator()(_Range&& __r, _Out __result,
627 _Pred __pred, _Proj __proj = {})
const
629 return (*
this)(ranges::begin(__r), ranges::end(__r),
635 inline constexpr __copy_if_fn copy_if{};
637 template<
typename _Iter1,
typename _Iter2>
638 using swap_ranges_result = in_in_result<_Iter1, _Iter2>;
640 struct __swap_ranges_fn
642 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
643 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
644 requires indirectly_swappable<_Iter1, _Iter2>
645 constexpr swap_ranges_result<_Iter1, _Iter2>
646 operator()(_Iter1 __first1, _Sent1 __last1,
647 _Iter2 __first2, _Sent2 __last2)
const
649 for (; __first1 != __last1 && __first2 != __last2;
650 ++__first1, (void)++__first2)
651 ranges::iter_swap(__first1, __first2);
655 template<input_range _Range1, input_range _Range2>
656 requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
657 constexpr swap_ranges_result<borrowed_iterator_t<_Range1>,
658 borrowed_iterator_t<_Range2>>
659 operator()(_Range1&& __r1, _Range2&& __r2)
const
661 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
662 ranges::begin(__r2), ranges::end(__r2));
666 inline constexpr __swap_ranges_fn swap_ranges{};
668 template<
typename _Iter,
typename _Out>
669 using unary_transform_result = in_out_result<_Iter, _Out>;
671 template<
typename _Iter1,
typename _Iter2,
typename _Out>
672 struct in_in_out_result
674 [[no_unique_address]] _Iter1 in1;
675 [[no_unique_address]] _Iter2 in2;
676 [[no_unique_address]] _Out out;
678 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
679 requires convertible_to<const _Iter1&, _IIter1>
680 && convertible_to<const _Iter2&, _IIter2>
681 && convertible_to<const _Out&, _OOut>
683 operator in_in_out_result<_IIter1, _IIter2, _OOut>() const &
684 {
return {in1, in2, out}; }
686 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
687 requires convertible_to<_Iter1, _IIter1>
688 && convertible_to<_Iter2, _IIter2>
689 && convertible_to<_Out, _OOut>
691 operator in_in_out_result<_IIter1, _IIter2, _OOut>() &&
695 template<
typename _Iter1,
typename _Iter2,
typename _Out>
696 using binary_transform_result = in_in_out_result<_Iter1, _Iter2, _Out>;
698 struct __transform_fn
700 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
701 weakly_incrementable _Out,
702 copy_constructible _Fp,
typename _Proj =
identity>
703 requires indirectly_writable<_Out,
704 indirect_result_t<_Fp&,
705 projected<_Iter, _Proj>>>
706 constexpr unary_transform_result<_Iter, _Out>
707 operator()(_Iter __first1, _Sent __last1, _Out __result,
708 _Fp __op, _Proj __proj = {})
const
710 for (; __first1 != __last1; ++__first1, (void)++__result)
715 template<input_range _Range, weakly_incrementable _Out,
716 copy_constructible _Fp,
typename _Proj = identity>
717 requires indirectly_writable<_Out,
718 indirect_result_t<_Fp&,
719 projected<iterator_t<_Range>, _Proj>>>
720 constexpr unary_transform_result<borrowed_iterator_t<_Range>, _Out>
721 operator()(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {})
const
723 return (*
this)(ranges::begin(__r), ranges::end(__r),
728 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
729 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
730 weakly_incrementable _Out, copy_constructible _Fp,
731 typename _Proj1 =
identity,
typename _Proj2 =
identity>
732 requires indirectly_writable<_Out,
733 indirect_result_t<_Fp&,
734 projected<_Iter1, _Proj1>,
735 projected<_Iter2, _Proj2>>>
736 constexpr binary_transform_result<_Iter1, _Iter2, _Out>
737 operator()(_Iter1 __first1, _Sent1 __last1,
738 _Iter2 __first2, _Sent2 __last2,
739 _Out __result, _Fp __binary_op,
740 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
742 for (; __first1 != __last1 && __first2 != __last2;
743 ++__first1, (void)++__first2, ++__result)
750 template<input_range _Range1, input_range _Range2,
751 weakly_incrementable _Out, copy_constructible _Fp,
752 typename _Proj1 = identity,
typename _Proj2 = identity>
753 requires indirectly_writable<_Out,
754 indirect_result_t<_Fp&,
755 projected<iterator_t<_Range1>, _Proj1>,
756 projected<iterator_t<_Range2>, _Proj2>>>
757 constexpr binary_transform_result<borrowed_iterator_t<_Range1>,
758 borrowed_iterator_t<_Range2>, _Out>
759 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result, _Fp __binary_op,
760 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
762 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
763 ranges::begin(__r2), ranges::end(__r2),
769 inline constexpr __transform_fn transform{};
773 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
774 typename _Tp1,
typename _Tp2,
typename _Proj =
identity>
775 requires indirectly_writable<_Iter, const _Tp2&>
776 && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
779 operator()(_Iter __first, _Sent __last,
780 const _Tp1& __old_value,
const _Tp2& __new_value,
781 _Proj __proj = {})
const
783 for (; __first != __last; ++__first)
785 *__first = __new_value;
789 template<input_range _Range,
790 typename _Tp1,
typename _Tp2,
typename _Proj = identity>
791 requires indirectly_writable<iterator_t<_Range>,
const _Tp2&>
792 && indirect_binary_predicate<ranges::equal_to,
793 projected<iterator_t<_Range>, _Proj>,
795 constexpr borrowed_iterator_t<_Range>
796 operator()(_Range&& __r,
797 const _Tp1& __old_value,
const _Tp2& __new_value,
798 _Proj __proj = {})
const
800 return (*
this)(ranges::begin(__r), ranges::end(__r),
801 __old_value, __new_value,
std::move(__proj));
805 inline constexpr __replace_fn replace{};
807 struct __replace_if_fn
809 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
810 typename _Tp,
typename _Proj =
identity,
811 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
812 requires indirectly_writable<_Iter, const _Tp&>
814 operator()(_Iter __first, _Sent __last,
815 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
817 for (; __first != __last; ++__first)
819 *__first = __new_value;
823 template<input_range _Range,
typename _Tp,
typename _Proj = identity,
824 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
826 requires indirectly_writable<iterator_t<_Range>,
const _Tp&>
827 constexpr borrowed_iterator_t<_Range>
828 operator()(_Range&& __r,
829 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
831 return (*
this)(ranges::begin(__r), ranges::end(__r),
836 inline constexpr __replace_if_fn replace_if{};
838 template<
typename _Iter,
typename _Out>
839 using replace_copy_result = in_out_result<_Iter, _Out>;
841 struct __replace_copy_fn
843 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
844 typename _Tp1,
typename _Tp2, output_iterator<const _Tp2&> _Out,
845 typename _Proj =
identity>
846 requires indirectly_copyable<_Iter, _Out>
847 && indirect_binary_predicate<ranges::equal_to,
848 projected<_Iter, _Proj>,
const _Tp1*>
849 constexpr replace_copy_result<_Iter, _Out>
850 operator()(_Iter __first, _Sent __last, _Out __result,
851 const _Tp1& __old_value,
const _Tp2& __new_value,
852 _Proj __proj = {})
const
854 for (; __first != __last; ++__first, (void)++__result)
856 *__result = __new_value;
858 *__result = *__first;
862 template<input_range _Range,
typename _Tp1,
typename _Tp2,
863 output_iterator<const _Tp2&> _Out,
typename _Proj = identity>
864 requires indirectly_copyable<iterator_t<_Range>, _Out>
865 && indirect_binary_predicate<ranges::equal_to,
866 projected<iterator_t<_Range>, _Proj>,
868 constexpr replace_copy_result<borrowed_iterator_t<_Range>, _Out>
869 operator()(_Range&& __r, _Out __result,
870 const _Tp1& __old_value,
const _Tp2& __new_value,
871 _Proj __proj = {})
const
873 return (*
this)(ranges::begin(__r), ranges::end(__r),
879 inline constexpr __replace_copy_fn replace_copy{};
881 template<
typename _Iter,
typename _Out>
882 using replace_copy_if_result = in_out_result<_Iter, _Out>;
884 struct __replace_copy_if_fn
886 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
887 typename _Tp, output_iterator<const _Tp&> _Out,
888 typename _Proj =
identity,
889 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
890 requires indirectly_copyable<_Iter, _Out>
891 constexpr replace_copy_if_result<_Iter, _Out>
892 operator()(_Iter __first, _Sent __last, _Out __result,
893 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
895 for (; __first != __last; ++__first, (void)++__result)
897 *__result = __new_value;
899 *__result = *__first;
903 template<input_range _Range,
904 typename _Tp, output_iterator<const _Tp&> _Out,
905 typename _Proj = identity,
906 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
908 requires indirectly_copyable<iterator_t<_Range>, _Out>
909 constexpr replace_copy_if_result<borrowed_iterator_t<_Range>, _Out>
910 operator()(_Range&& __r, _Out __result,
911 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
const
913 return (*
this)(ranges::begin(__r), ranges::end(__r),
919 inline constexpr __replace_copy_if_fn replace_copy_if{};
921 struct __generate_n_fn
923 template<input_or_output_iterator _Out, copy_constructible _Fp>
924 requires invocable<_Fp&>
925 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
927 operator()(_Out __first, iter_difference_t<_Out> __n, _Fp __gen)
const
929 for (; __n > 0; --__n, (void)++__first)
935 inline constexpr __generate_n_fn generate_n{};
939 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
940 copy_constructible _Fp>
941 requires invocable<_Fp&>
942 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
944 operator()(_Out __first, _Sent __last, _Fp __gen)
const
946 for (; __first != __last; ++__first)
951 template<
typename _Range, copy_constructible _Fp>
952 requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
953 constexpr borrowed_iterator_t<_Range>
954 operator()(_Range&& __r, _Fp __gen)
const
956 return (*
this)(ranges::begin(__r), ranges::end(__r),
std::move(__gen));
960 inline constexpr __generate_fn generate{};
962 struct __remove_if_fn
964 template<permutable _Iter, sentinel_for<_Iter> _Sent,
965 typename _Proj =
identity,
966 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
967 constexpr subrange<_Iter>
968 operator()(_Iter __first, _Sent __last,
969 _Pred __pred, _Proj __proj = {})
const
971 __first = ranges::find_if(__first, __last, __pred, __proj);
972 if (__first == __last)
973 return {__first, __first};
975 auto __result = __first;
977 for (; __first != __last; ++__first)
984 return {__result, __first};
987 template<forward_range _Range,
typename _Proj = identity,
988 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
990 requires permutable<iterator_t<_Range>>
991 constexpr borrowed_subrange_t<_Range>
992 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
994 return (*
this)(ranges::begin(__r), ranges::end(__r),
999 inline constexpr __remove_if_fn remove_if{};
1003 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1004 typename _Tp,
typename _Proj =
identity>
1005 requires indirect_binary_predicate<ranges::equal_to,
1006 projected<_Iter, _Proj>,
1008 constexpr subrange<_Iter>
1009 operator()(_Iter __first, _Sent __last,
1010 const _Tp& __value, _Proj __proj = {})
const
1012 auto __pred = [&] (
auto&& __arg) ->
bool {
1013 return std::forward<decltype(__arg)>(__arg) == __value;
1015 return ranges::remove_if(__first, __last,
1019 template<forward_range _Range,
typename _Tp,
typename _Proj =
identity>
1020 requires permutable<iterator_t<_Range>>
1021 && indirect_binary_predicate<ranges::equal_to,
1022 projected<iterator_t<_Range>, _Proj>,
1024 constexpr borrowed_subrange_t<_Range>
1025 operator()(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
const
1027 return (*
this)(ranges::begin(__r), ranges::end(__r),
1032 inline constexpr __remove_fn remove{};
1034 template<
typename _Iter,
typename _Out>
1035 using remove_copy_if_result = in_out_result<_Iter, _Out>;
1037 struct __remove_copy_if_fn
1039 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1040 weakly_incrementable _Out,
typename _Proj =
identity,
1041 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1042 requires indirectly_copyable<_Iter, _Out>
1043 constexpr remove_copy_if_result<_Iter, _Out>
1044 operator()(_Iter __first, _Sent __last, _Out __result,
1045 _Pred __pred, _Proj __proj = {})
const
1047 for (; __first != __last; ++__first)
1050 *__result = *__first;
1056 template<input_range _Range, weakly_incrementable _Out,
1057 typename _Proj = identity,
1058 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
1060 requires indirectly_copyable<iterator_t<_Range>, _Out>
1061 constexpr remove_copy_if_result<borrowed_iterator_t<_Range>, _Out>
1062 operator()(_Range&& __r, _Out __result,
1063 _Pred __pred, _Proj __proj = {})
const
1065 return (*
this)(ranges::begin(__r), ranges::end(__r),
1071 inline constexpr __remove_copy_if_fn remove_copy_if{};
1073 template<
typename _Iter,
typename _Out>
1074 using remove_copy_result = in_out_result<_Iter, _Out>;
1076 struct __remove_copy_fn
1078 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1079 weakly_incrementable _Out,
typename _Tp,
typename _Proj =
identity>
1080 requires indirectly_copyable<_Iter, _Out>
1081 && indirect_binary_predicate<ranges::equal_to,
1082 projected<_Iter, _Proj>,
1084 constexpr remove_copy_result<_Iter, _Out>
1085 operator()(_Iter __first, _Sent __last, _Out __result,
1086 const _Tp& __value, _Proj __proj = {})
const
1088 for (; __first != __last; ++__first)
1091 *__result = *__first;
1097 template<input_range _Range, weakly_incrementable _Out,
1098 typename _Tp,
typename _Proj = identity>
1099 requires indirectly_copyable<iterator_t<_Range>, _Out>
1100 && indirect_binary_predicate<ranges::equal_to,
1101 projected<iterator_t<_Range>, _Proj>,
1103 constexpr remove_copy_result<borrowed_iterator_t<_Range>, _Out>
1104 operator()(_Range&& __r, _Out __result,
1105 const _Tp& __value, _Proj __proj = {})
const
1107 return (*
this)(ranges::begin(__r), ranges::end(__r),
1112 inline constexpr __remove_copy_fn remove_copy{};
1116 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1117 typename _Proj =
identity,
1118 indirect_equivalence_relation<
1119 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1120 constexpr subrange<_Iter>
1121 operator()(_Iter __first, _Sent __last,
1122 _Comp __comp = {}, _Proj __proj = {})
const
1124 __first = ranges::adjacent_find(__first, __last, __comp, __proj);
1125 if (__first == __last)
1126 return {__first, __first};
1128 auto __dest = __first;
1130 while (++__first != __last)
1135 return {++__dest, __first};
1138 template<forward_range _Range,
typename _Proj = identity,
1139 indirect_equivalence_relation<
1140 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1141 requires permutable<iterator_t<_Range>>
1142 constexpr borrowed_subrange_t<_Range>
1143 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1145 return (*
this)(ranges::begin(__r), ranges::end(__r),
1150 inline constexpr __unique_fn unique{};
1154 template<
typename _Out,
typename _Tp>
1155 concept __can_reread_output = input_iterator<_Out>
1156 && same_as<_Tp, iter_value_t<_Out>>;
1159 template<
typename _Iter,
typename _Out>
1160 using unique_copy_result = in_out_result<_Iter, _Out>;
1162 struct __unique_copy_fn
1164 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1165 weakly_incrementable _Out,
typename _Proj =
identity,
1166 indirect_equivalence_relation<
1167 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1168 requires indirectly_copyable<_Iter, _Out>
1169 && (forward_iterator<_Iter>
1170 || __detail::__can_reread_output<_Out, iter_value_t<_Iter>>
1171 || indirectly_copyable_storable<_Iter, _Out>)
1172 constexpr unique_copy_result<_Iter, _Out>
1173 operator()(_Iter __first, _Sent __last, _Out __result,
1174 _Comp __comp = {}, _Proj __proj = {})
const
1176 if (__first == __last)
1180 if constexpr (forward_iterator<_Iter>)
1182 auto __next = __first;
1183 *__result = *__next;
1184 while (++__next != __last)
1190 *++__result = *__first;
1194 else if constexpr (__detail::__can_reread_output<_Out, iter_value_t<_Iter>>)
1196 *__result = *__first;
1197 while (++__first != __last)
1201 *++__result = *__first;
1206 auto __value = *__first;
1207 *__result = __value;
1208 while (++__first != __last)
1215 *++__result = __value;
1222 template<input_range _Range,
1223 weakly_incrementable _Out,
typename _Proj = identity,
1224 indirect_equivalence_relation<
1225 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1226 requires indirectly_copyable<iterator_t<_Range>, _Out>
1227 && (forward_iterator<iterator_t<_Range>>
1228 || __detail::__can_reread_output<_Out, range_value_t<_Range>>
1229 || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1230 constexpr unique_copy_result<borrowed_iterator_t<_Range>, _Out>
1231 operator()(_Range&& __r, _Out __result,
1232 _Comp __comp = {}, _Proj __proj = {})
const
1234 return (*
this)(ranges::begin(__r), ranges::end(__r),
1240 inline constexpr __unique_copy_fn unique_copy{};
1244 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1245 requires permutable<_Iter>
1247 operator()(_Iter __first, _Sent __last)
const
1249 auto __i = ranges::next(__first, __last);
1252 if constexpr (random_access_iterator<_Iter>)
1254 if (__first != __last)
1257 while (__first < __tail)
1259 ranges::iter_swap(__first, __tail);
1269 if (__first == __tail || __first == --__tail)
1273 ranges::iter_swap(__first, __tail);
1280 template<b
idirectional_range _Range>
1281 requires permutable<iterator_t<_Range>>
1282 constexpr borrowed_iterator_t<_Range>
1283 operator()(_Range&& __r)
const
1285 return (*
this)(ranges::begin(__r), ranges::end(__r));
1289 inline constexpr __reverse_fn reverse{};
1291 template<
typename _Iter,
typename _Out>
1292 using reverse_copy_result = in_out_result<_Iter, _Out>;
1294 struct __reverse_copy_fn
1296 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1297 weakly_incrementable _Out>
1298 requires indirectly_copyable<_Iter, _Out>
1299 constexpr reverse_copy_result<_Iter, _Out>
1300 operator()(_Iter __first, _Sent __last, _Out __result)
const
1302 auto __i = ranges::next(__first, __last);
1304 while (__first != __tail)
1307 *__result = *__tail;
1313 template<b
idirectional_range _Range, weakly_incrementable _Out>
1314 requires indirectly_copyable<iterator_t<_Range>, _Out>
1315 constexpr reverse_copy_result<borrowed_iterator_t<_Range>, _Out>
1316 operator()(_Range&& __r, _Out __result)
const
1318 return (*
this)(ranges::begin(__r), ranges::end(__r),
1323 inline constexpr __reverse_copy_fn reverse_copy{};
1327 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1328 constexpr subrange<_Iter>
1329 operator()(_Iter __first, _Iter __middle, _Sent __last)
const
1331 auto __lasti = ranges::next(__first, __last);
1332 if (__first == __middle)
1333 return {__lasti, __lasti};
1334 if (__last == __middle)
1337 if constexpr (random_access_iterator<_Iter>)
1339 auto __n = __lasti - __first;
1340 auto __k = __middle - __first;
1342 if (__k == __n - __k)
1344 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1349 auto __ret = __first + (__lasti - __middle);
1353 if (__k < __n - __k)
1357 if constexpr (__is_pod(iter_value_t<_Iter>))
1361 ranges::move(__p + 1, __p + __n, __p);
1365 auto __q = __p + __k;
1366 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1368 ranges::iter_swap(__p, __q);
1375 ranges::swap(__n, __k);
1383 if constexpr (__is_pod(iter_value_t<_Iter>))
1387 ranges::move_backward(__p, __p + __n - 1, __p + __n);
1391 auto __q = __p + __n;
1393 for (
decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1397 ranges::iter_swap(__p, __q);
1406 else if constexpr (bidirectional_iterator<_Iter>)
1408 auto __tail = __lasti;
1410 ranges::reverse(__first, __middle);
1411 ranges::reverse(__middle, __tail);
1413 while (__first != __middle && __middle != __tail)
1415 ranges::iter_swap(__first, --__tail);
1419 if (__first == __middle)
1421 ranges::reverse(__middle, __tail);
1426 ranges::reverse(__first, __middle);
1432 auto __first2 = __middle;
1435 ranges::iter_swap(__first, __first2);
1438 if (__first == __middle)
1439 __middle = __first2;
1440 }
while (__first2 != __last);
1442 auto __ret = __first;
1444 __first2 = __middle;
1446 while (__first2 != __last)
1448 ranges::iter_swap(__first, __first2);
1451 if (__first == __middle)
1452 __middle = __first2;
1453 else if (__first2 == __last)
1454 __first2 = __middle;
1460 template<forward_range _Range>
1461 requires permutable<iterator_t<_Range>>
1462 constexpr borrowed_subrange_t<_Range>
1463 operator()(_Range&& __r, iterator_t<_Range> __middle)
const
1465 return (*
this)(ranges::begin(__r),
std::move(__middle),
1470 inline constexpr __rotate_fn rotate{};
1472 template<
typename _Iter,
typename _Out>
1473 using rotate_copy_result = in_out_result<_Iter, _Out>;
1475 struct __rotate_copy_fn
1477 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1478 weakly_incrementable _Out>
1479 requires indirectly_copyable<_Iter, _Out>
1480 constexpr rotate_copy_result<_Iter, _Out>
1481 operator()(_Iter __first, _Iter __middle, _Sent __last,
1482 _Out __result)
const
1484 auto __copy1 = ranges::copy(__middle,
1487 auto __copy2 = ranges::copy(
std::move(__first),
1493 template<forward_range _Range, weakly_incrementable _Out>
1494 requires indirectly_copyable<iterator_t<_Range>, _Out>
1495 constexpr rotate_copy_result<borrowed_iterator_t<_Range>, _Out>
1496 operator()(_Range&& __r, iterator_t<_Range> __middle, _Out __result)
const
1498 return (*
this)(ranges::begin(__r),
std::move(__middle),
1503 inline constexpr __rotate_copy_fn rotate_copy{};
1507 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1508 weakly_incrementable _Out,
typename _Gen>
1509 requires (forward_iterator<_Iter> || random_access_iterator<_Out>)
1510 && indirectly_copyable<_Iter, _Out>
1511 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1513 operator()(_Iter __first, _Sent __last, _Out __out,
1514 iter_difference_t<_Iter> __n, _Gen&& __g)
const
1516 if constexpr (forward_iterator<_Iter>)
1520 auto __lasti = ranges::next(__first, __last);
1521 return _GLIBCXX_STD_A::
1523 __n, std::forward<_Gen>(__g));
1527 using __distrib_type
1528 = uniform_int_distribution<iter_difference_t<_Iter>>;
1529 using __param_type =
typename __distrib_type::param_type;
1530 __distrib_type __d{};
1531 iter_difference_t<_Iter> __sample_sz = 0;
1532 while (__first != __last && __sample_sz != __n)
1534 __out[__sample_sz++] = *__first;
1537 for (
auto __pop_sz = __sample_sz; __first != __last;
1538 ++__first, (void) ++__pop_sz)
1540 const auto __k = __d(__g, __param_type{0, __pop_sz});
1542 __out[__k] = *__first;
1544 return __out + __sample_sz;
1548 template<input_range _Range, weakly_incrementable _Out,
typename _Gen>
1549 requires (forward_range<_Range> || random_access_iterator<_Out>)
1550 && indirectly_copyable<iterator_t<_Range>, _Out>
1551 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1553 operator()(_Range&& __r, _Out __out,
1554 range_difference_t<_Range> __n, _Gen&& __g)
const
1556 return (*
this)(ranges::begin(__r), ranges::end(__r),
1558 std::forward<_Gen>(__g));
1562 inline constexpr __sample_fn
sample{};
1564#ifdef _GLIBCXX_USE_C99_STDINT_TR1
1567 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1569 requires permutable<_Iter>
1570 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1572 operator()(_Iter __first, _Sent __last, _Gen&& __g)
const
1574 auto __lasti = ranges::next(__first, __last);
1575 std::shuffle(
std::move(__first), __lasti, std::forward<_Gen>(__g));
1579 template<random_access_range _Range,
typename _Gen>
1580 requires permutable<iterator_t<_Range>>
1581 && uniform_random_bit_generator<remove_reference_t<_Gen>>
1582 borrowed_iterator_t<_Range>
1583 operator()(_Range&& __r, _Gen&& __g)
const
1585 return (*
this)(ranges::begin(__r), ranges::end(__r),
1586 std::forward<_Gen>(__g));
1590 inline constexpr __shuffle_fn shuffle{};
1593 struct __push_heap_fn
1595 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1596 typename _Comp = ranges::less,
typename _Proj =
identity>
1597 requires sortable<_Iter, _Comp, _Proj>
1599 operator()(_Iter __first, _Sent __last,
1600 _Comp __comp = {}, _Proj __proj = {})
const
1602 auto __lasti = ranges::next(__first, __last);
1603 std::push_heap(__first, __lasti,
1604 __detail::__make_comp_proj(__comp, __proj));
1608 template<random_access_range _Range,
1609 typename _Comp = ranges::less,
typename _Proj = identity>
1610 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1611 constexpr borrowed_iterator_t<_Range>
1612 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1614 return (*
this)(ranges::begin(__r), ranges::end(__r),
1619 inline constexpr __push_heap_fn push_heap{};
1621 struct __pop_heap_fn
1623 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1624 typename _Comp = ranges::less,
typename _Proj =
identity>
1625 requires sortable<_Iter, _Comp, _Proj>
1627 operator()(_Iter __first, _Sent __last,
1628 _Comp __comp = {}, _Proj __proj = {})
const
1630 auto __lasti = ranges::next(__first, __last);
1631 std::pop_heap(__first, __lasti,
1632 __detail::__make_comp_proj(__comp, __proj));
1636 template<random_access_range _Range,
1637 typename _Comp = ranges::less,
typename _Proj = identity>
1638 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1639 constexpr borrowed_iterator_t<_Range>
1640 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1642 return (*
this)(ranges::begin(__r), ranges::end(__r),
1647 inline constexpr __pop_heap_fn pop_heap{};
1649 struct __make_heap_fn
1651 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1652 typename _Comp = ranges::less,
typename _Proj =
identity>
1653 requires sortable<_Iter, _Comp, _Proj>
1655 operator()(_Iter __first, _Sent __last,
1656 _Comp __comp = {}, _Proj __proj = {})
const
1658 auto __lasti = ranges::next(__first, __last);
1659 std::make_heap(__first, __lasti,
1660 __detail::__make_comp_proj(__comp, __proj));
1664 template<random_access_range _Range,
1665 typename _Comp = ranges::less,
typename _Proj = identity>
1666 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1667 constexpr borrowed_iterator_t<_Range>
1668 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1670 return (*
this)(ranges::begin(__r), ranges::end(__r),
1675 inline constexpr __make_heap_fn make_heap{};
1677 struct __sort_heap_fn
1679 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1680 typename _Comp = ranges::less,
typename _Proj =
identity>
1681 requires sortable<_Iter, _Comp, _Proj>
1683 operator()(_Iter __first, _Sent __last,
1684 _Comp __comp = {}, _Proj __proj = {})
const
1686 auto __lasti = ranges::next(__first, __last);
1687 std::sort_heap(__first, __lasti,
1688 __detail::__make_comp_proj(__comp, __proj));
1692 template<random_access_range _Range,
1693 typename _Comp = ranges::less,
typename _Proj = identity>
1694 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1695 constexpr borrowed_iterator_t<_Range>
1696 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1698 return (*
this)(ranges::begin(__r), ranges::end(__r),
1703 inline constexpr __sort_heap_fn sort_heap{};
1705 struct __is_heap_until_fn
1707 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1708 typename _Proj =
identity,
1709 indirect_strict_weak_order<projected<_Iter, _Proj>>
1710 _Comp = ranges::less>
1712 operator()(_Iter __first, _Sent __last,
1713 _Comp __comp = {}, _Proj __proj = {})
const
1715 iter_difference_t<_Iter> __n = ranges::distance(__first, __last);
1716 iter_difference_t<_Iter> __parent = 0, __child = 1;
1717 for (; __child < __n; ++__child)
1721 return __first + __child;
1722 else if ((__child & 1) == 0)
1725 return __first + __n;
1728 template<random_access_range _Range,
1729 typename _Proj = identity,
1730 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1731 _Comp = ranges::less>
1732 constexpr borrowed_iterator_t<_Range>
1733 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1735 return (*
this)(ranges::begin(__r), ranges::end(__r),
1740 inline constexpr __is_heap_until_fn is_heap_until{};
1744 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1745 typename _Proj =
identity,
1746 indirect_strict_weak_order<projected<_Iter, _Proj>>
1747 _Comp = ranges::less>
1749 operator()(_Iter __first, _Sent __last,
1750 _Comp __comp = {}, _Proj __proj = {})
const
1753 == ranges::is_heap_until(__first, __last,
1758 template<random_access_range _Range,
1759 typename _Proj = identity,
1760 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1761 _Comp = ranges::less>
1763 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1765 return (*
this)(ranges::begin(__r), ranges::end(__r),
1770 inline constexpr __is_heap_fn is_heap{};
1774 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1775 typename _Comp = ranges::less,
typename _Proj =
identity>
1776 requires sortable<_Iter, _Comp, _Proj>
1778 operator()(_Iter __first, _Sent __last,
1779 _Comp __comp = {}, _Proj __proj = {})
const
1781 auto __lasti = ranges::next(__first, __last);
1782 _GLIBCXX_STD_A::sort(
std::move(__first), __lasti,
1783 __detail::__make_comp_proj(__comp, __proj));
1787 template<random_access_range _Range,
1788 typename _Comp = ranges::less,
typename _Proj = identity>
1789 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1790 constexpr borrowed_iterator_t<_Range>
1791 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1793 return (*
this)(ranges::begin(__r), ranges::end(__r),
1798 inline constexpr __sort_fn sort{};
1800 struct __stable_sort_fn
1802 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1803 typename _Comp = ranges::less,
typename _Proj =
identity>
1804 requires sortable<_Iter, _Comp, _Proj>
1806 operator()(_Iter __first, _Sent __last,
1807 _Comp __comp = {}, _Proj __proj = {})
const
1809 auto __lasti = ranges::next(__first, __last);
1810 std::stable_sort(
std::move(__first), __lasti,
1811 __detail::__make_comp_proj(__comp, __proj));
1815 template<random_access_range _Range,
1816 typename _Comp = ranges::less,
typename _Proj = identity>
1817 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1818 borrowed_iterator_t<_Range>
1819 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1821 return (*
this)(ranges::begin(__r), ranges::end(__r),
1826 inline constexpr __stable_sort_fn stable_sort{};
1828 struct __partial_sort_fn
1830 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
1831 typename _Comp = ranges::less,
typename _Proj =
identity>
1832 requires sortable<_Iter, _Comp, _Proj>
1834 operator()(_Iter __first, _Iter __middle, _Sent __last,
1835 _Comp __comp = {}, _Proj __proj = {})
const
1837 if (__first == __middle)
1838 return ranges::next(__first, __last);
1840 ranges::make_heap(__first, __middle, __comp, __proj);
1841 auto __i = __middle;
1842 for (; __i != __last; ++__i)
1847 ranges::pop_heap(__first, __middle, __comp, __proj);
1848 ranges::iter_swap(__middle-1, __i);
1849 ranges::push_heap(__first, __middle, __comp, __proj);
1851 ranges::sort_heap(__first, __middle, __comp, __proj);
1856 template<random_access_range _Range,
1857 typename _Comp = ranges::less,
typename _Proj = identity>
1858 requires sortable<iterator_t<_Range>, _Comp, _Proj>
1859 constexpr borrowed_iterator_t<_Range>
1860 operator()(_Range&& __r, iterator_t<_Range> __middle,
1861 _Comp __comp = {}, _Proj __proj = {})
const
1863 return (*
this)(ranges::begin(__r),
std::move(__middle),
1869 inline constexpr __partial_sort_fn partial_sort{};
1871 template<
typename _Iter,
typename _Out>
1872 using partial_sort_copy_result = in_out_result<_Iter, _Out>;
1874 struct __partial_sort_copy_fn
1876 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1877 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1878 typename _Comp = ranges::less,
1879 typename _Proj1 =
identity,
typename _Proj2 =
identity>
1880 requires indirectly_copyable<_Iter1, _Iter2>
1881 && sortable<_Iter2, _Comp, _Proj2>
1882 && indirect_strict_weak_order<_Comp,
1883 projected<_Iter1, _Proj1>,
1884 projected<_Iter2, _Proj2>>
1885 constexpr partial_sort_copy_result<_Iter1, _Iter2>
1886 operator()(_Iter1 __first, _Sent1 __last,
1887 _Iter2 __result_first, _Sent2 __result_last,
1889 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1891 if (__result_first == __result_last)
1894 auto __lasti = ranges::next(
std::move(__first),
1899 auto __result_real_last = __result_first;
1900 while (__first != __last && __result_real_last != __result_last)
1902 *__result_real_last = *__first;
1903 ++__result_real_last;
1907 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
1908 for (; __first != __last; ++__first)
1913 ranges::pop_heap(__result_first, __result_real_last,
1915 *(__result_real_last-1) = *__first;
1916 ranges::push_heap(__result_first, __result_real_last,
1919 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
1924 template<input_range _Range1, random_access_range _Range2,
1925 typename _Comp = ranges::less,
1926 typename _Proj1 = identity,
typename _Proj2 = identity>
1927 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
1928 && sortable<iterator_t<_Range2>, _Comp, _Proj2>
1929 && indirect_strict_weak_order<_Comp,
1930 projected<iterator_t<_Range1>, _Proj1>,
1931 projected<iterator_t<_Range2>, _Proj2>>
1932 constexpr partial_sort_copy_result<borrowed_iterator_t<_Range1>,
1933 borrowed_iterator_t<_Range2>>
1934 operator()(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
1935 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
1937 return (*
this)(ranges::begin(__r), ranges::end(__r),
1938 ranges::begin(__out), ranges::end(__out),
1944 inline constexpr __partial_sort_copy_fn partial_sort_copy{};
1946 struct __is_sorted_until_fn
1948 template<forward_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
1956 if (__first == __last)
1959 auto __next = __first;
1960 for (++__next; __next != __last; __first = __next, (void)++__next)
1968 template<forward_range _Range,
typename _Proj = identity,
1969 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
1970 _Comp = ranges::less>
1971 constexpr borrowed_iterator_t<_Range>
1972 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
1974 return (*
this)(ranges::begin(__r), ranges::end(__r),
1979 inline constexpr __is_sorted_until_fn is_sorted_until{};
1981 struct __is_sorted_fn
1983 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1984 typename _Proj =
identity,
1985 indirect_strict_weak_order<projected<_Iter, _Proj>>
1986 _Comp = ranges::less>
1988 operator()(_Iter __first, _Sent __last,
1989 _Comp __comp = {}, _Proj __proj = {})
const
1991 if (__first == __last)
1994 auto __next = __first;
1995 for (++__next; __next != __last; __first = __next, (void)++__next)
2003 template<forward_range _Range,
typename _Proj = identity,
2004 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2005 _Comp = ranges::less>
2007 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2009 return (*
this)(ranges::begin(__r), ranges::end(__r),
2014 inline constexpr __is_sorted_fn is_sorted{};
2016 struct __nth_element_fn
2018 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2019 typename _Comp = ranges::less,
typename _Proj =
identity>
2020 requires sortable<_Iter, _Comp, _Proj>
2022 operator()(_Iter __first, _Iter __nth, _Sent __last,
2023 _Comp __comp = {}, _Proj __proj = {})
const
2025 auto __lasti = ranges::next(__first, __last);
2028 __detail::__make_comp_proj(__comp, __proj));
2032 template<random_access_range _Range,
2033 typename _Comp = ranges::less,
typename _Proj = identity>
2034 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2035 constexpr borrowed_iterator_t<_Range>
2036 operator()(_Range&& __r, iterator_t<_Range> __nth,
2037 _Comp __comp = {}, _Proj __proj = {})
const
2039 return (*
this)(ranges::begin(__r),
std::move(__nth),
2044 inline constexpr __nth_element_fn nth_element{};
2046 struct __lower_bound_fn
2048 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2049 typename _Tp,
typename _Proj =
identity,
2050 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2051 _Comp = ranges::less>
2053 operator()(_Iter __first, _Sent __last,
2054 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2056 auto __len = ranges::distance(__first, __last);
2060 auto __half = __len / 2;
2061 auto __middle = __first;
2062 ranges::advance(__middle, __half);
2067 __len = __len - __half - 1;
2075 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2076 indirect_strict_weak_order<
const _Tp*,
2077 projected<iterator_t<_Range>, _Proj>>
2078 _Comp = ranges::less>
2079 constexpr borrowed_iterator_t<_Range>
2080 operator()(_Range&& __r,
2081 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2083 return (*
this)(ranges::begin(__r), ranges::end(__r),
2088 inline constexpr __lower_bound_fn lower_bound{};
2090 struct __upper_bound_fn
2092 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2093 typename _Tp,
typename _Proj =
identity,
2094 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2095 _Comp = ranges::less>
2097 operator()(_Iter __first, _Sent __last,
2098 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2100 auto __len = ranges::distance(__first, __last);
2104 auto __half = __len / 2;
2105 auto __middle = __first;
2106 ranges::advance(__middle, __half);
2113 __len = __len - __half - 1;
2119 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2120 indirect_strict_weak_order<
const _Tp*,
2121 projected<iterator_t<_Range>, _Proj>>
2122 _Comp = ranges::less>
2123 constexpr borrowed_iterator_t<_Range>
2124 operator()(_Range&& __r,
2125 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2127 return (*
this)(ranges::begin(__r), ranges::end(__r),
2132 inline constexpr __upper_bound_fn upper_bound{};
2134 struct __equal_range_fn
2136 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2137 typename _Tp,
typename _Proj =
identity,
2138 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2139 _Comp = ranges::less>
2140 constexpr subrange<_Iter>
2141 operator()(_Iter __first, _Sent __last,
2142 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2144 auto __len = ranges::distance(__first, __last);
2148 auto __half = __len / 2;
2149 auto __middle = __first;
2150 ranges::advance(__middle, __half);
2157 __len = __len - __half - 1;
2166 = ranges::lower_bound(__first, __middle,
2167 __value, __comp, __proj);
2168 ranges::advance(__first, __len);
2170 = ranges::upper_bound(++__middle, __first,
2171 __value, __comp, __proj);
2172 return {__left, __right};
2175 return {__first, __first};
2178 template<forward_range _Range,
2179 typename _Tp,
typename _Proj = identity,
2180 indirect_strict_weak_order<
const _Tp*,
2181 projected<iterator_t<_Range>, _Proj>>
2182 _Comp = ranges::less>
2183 constexpr borrowed_subrange_t<_Range>
2184 operator()(_Range&& __r,
const _Tp& __value,
2185 _Comp __comp = {}, _Proj __proj = {})
const
2187 return (*
this)(ranges::begin(__r), ranges::end(__r),
2192 inline constexpr __equal_range_fn equal_range{};
2194 struct __binary_search_fn
2196 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2197 typename _Tp,
typename _Proj =
identity,
2198 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2199 _Comp = ranges::less>
2201 operator()(_Iter __first, _Sent __last,
2202 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
const
2204 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2211 template<forward_range _Range,
2212 typename _Tp,
typename _Proj = identity,
2213 indirect_strict_weak_order<
const _Tp*,
2214 projected<iterator_t<_Range>, _Proj>>
2215 _Comp = ranges::less>
2217 operator()(_Range&& __r,
const _Tp& __value, _Comp __comp = {},
2218 _Proj __proj = {})
const
2220 return (*
this)(ranges::begin(__r), ranges::end(__r),
2225 inline constexpr __binary_search_fn binary_search{};
2227 struct __is_partitioned_fn
2229 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2230 typename _Proj =
identity,
2231 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2233 operator()(_Iter __first, _Sent __last,
2234 _Pred __pred, _Proj __proj = {})
const
2236 __first = ranges::find_if_not(
std::move(__first), __last,
2238 if (__first == __last)
2245 template<input_range _Range,
typename _Proj = identity,
2246 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2249 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2251 return (*
this)(ranges::begin(__r), ranges::end(__r),
2256 inline constexpr __is_partitioned_fn is_partitioned{};
2258 struct __partition_fn
2260 template<permutable _Iter, sentinel_for<_Iter> _Sent,
2261 typename _Proj =
identity,
2262 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2263 constexpr subrange<_Iter>
2264 operator()(_Iter __first, _Sent __last,
2265 _Pred __pred, _Proj __proj = {})
const
2267 if constexpr (bidirectional_iterator<_Iter>)
2269 auto __lasti = ranges::next(__first, __last);
2270 auto __tail = __lasti;
2274 if (__first == __tail)
2283 if (__first == __tail)
2290 ranges::iter_swap(__first, __tail);
2296 if (__first == __last)
2297 return {__first, __first};
2300 if (++__first == __last)
2301 return {__first, __first};
2303 auto __next = __first;
2304 while (++__next != __last)
2307 ranges::iter_swap(__first, __next);
2315 template<forward_range _Range,
typename _Proj = identity,
2316 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2318 requires permutable<iterator_t<_Range>>
2319 constexpr borrowed_subrange_t<_Range>
2320 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2322 return (*
this)(ranges::begin(__r), ranges::end(__r),
2327 inline constexpr __partition_fn partition{};
2330 struct __stable_partition_fn
2332 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2333 typename _Proj =
identity,
2334 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2335 requires permutable<_Iter>
2337 operator()(_Iter __first, _Sent __last,
2338 _Pred __pred, _Proj __proj = {})
const
2340 auto __lasti = ranges::next(__first, __last);
2342 = std::stable_partition(
std::move(__first), __lasti,
2343 __detail::__make_pred_proj(__pred, __proj));
2347 template<bidirectional_range _Range,
typename _Proj = identity,
2348 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2350 requires permutable<iterator_t<_Range>>
2351 borrowed_subrange_t<_Range>
2352 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2354 return (*
this)(ranges::begin(__r), ranges::end(__r),
2359 inline constexpr __stable_partition_fn stable_partition{};
2362 template<
typename _Iter,
typename _Out1,
typename _Out2>
2363 struct in_out_out_result
2365 [[no_unique_address]] _Iter in;
2366 [[no_unique_address]] _Out1 out1;
2367 [[no_unique_address]] _Out2 out2;
2369 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2370 requires convertible_to<const _Iter&, _IIter>
2371 && convertible_to<const _Out1&, _OOut1>
2372 && convertible_to<const _Out2&, _OOut2>
2374 operator in_out_out_result<_IIter, _OOut1, _OOut2>() const &
2375 {
return {in, out1, out2}; }
2377 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2378 requires convertible_to<_Iter, _IIter>
2379 && convertible_to<_Out1, _OOut1>
2380 && convertible_to<_Out2, _OOut2>
2382 operator in_out_out_result<_IIter, _OOut1, _OOut2>() &&
2386 template<
typename _Iter,
typename _Out1,
typename _Out2>
2387 using partition_copy_result = in_out_out_result<_Iter, _Out1, _Out2>;
2389 struct __partition_copy_fn
2391 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2392 weakly_incrementable _Out1, weakly_incrementable _Out2,
2393 typename _Proj =
identity,
2394 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2395 requires indirectly_copyable<_Iter, _Out1>
2396 && indirectly_copyable<_Iter, _Out2>
2397 constexpr partition_copy_result<_Iter, _Out1, _Out2>
2398 operator()(_Iter __first, _Sent __last,
2399 _Out1 __out_true, _Out2 __out_false,
2400 _Pred __pred, _Proj __proj = {})
const
2402 for (; __first != __last; ++__first)
2405 *__out_true = *__first;
2410 *__out_false = *__first;
2418 template<input_range _Range, weakly_incrementable _Out1,
2419 weakly_incrementable _Out2,
2420 typename _Proj = identity,
2421 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2423 requires indirectly_copyable<iterator_t<_Range>, _Out1>
2424 && indirectly_copyable<iterator_t<_Range>, _Out2>
2425 constexpr partition_copy_result<borrowed_iterator_t<_Range>, _Out1, _Out2>
2426 operator()(_Range&& __r, _Out1 __out_true, _Out2 __out_false,
2427 _Pred __pred, _Proj __proj = {})
const
2429 return (*
this)(ranges::begin(__r), ranges::end(__r),
2435 inline constexpr __partition_copy_fn partition_copy{};
2437 struct __partition_point_fn
2439 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2440 typename _Proj =
identity,
2441 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2443 operator()(_Iter __first, _Sent __last,
2444 _Pred __pred, _Proj __proj = {})
const
2446 auto __len = ranges::distance(__first, __last);
2450 auto __half = __len / 2;
2451 auto __middle = __first;
2452 ranges::advance(__middle, __half);
2457 __len = __len - __half - 1;
2465 template<forward_range _Range,
typename _Proj = identity,
2466 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
2468 constexpr borrowed_iterator_t<_Range>
2469 operator()(_Range&& __r, _Pred __pred, _Proj __proj = {})
const
2471 return (*
this)(ranges::begin(__r), ranges::end(__r),
2476 inline constexpr __partition_point_fn partition_point{};
2478 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2479 using merge_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2483 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2484 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2485 weakly_incrementable _Out,
typename _Comp = ranges::less,
2486 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2487 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2488 constexpr merge_result<_Iter1, _Iter2, _Out>
2489 operator()(_Iter1 __first1, _Sent1 __last1,
2490 _Iter2 __first2, _Sent2 __last2, _Out __result,
2492 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2494 while (__first1 != __last1 && __first2 != __last2)
2500 *__result = *__first2;
2505 *__result = *__first1;
2518 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2519 typename _Comp = ranges::less,
2520 typename _Proj1 = identity,
typename _Proj2 = identity>
2521 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2522 _Comp, _Proj1, _Proj2>
2523 constexpr merge_result<borrowed_iterator_t<_Range1>,
2524 borrowed_iterator_t<_Range2>,
2526 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2528 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2530 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2531 ranges::begin(__r2), ranges::end(__r2),
2537 inline constexpr __merge_fn merge{};
2539 struct __inplace_merge_fn
2541 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2542 typename _Comp = ranges::less,
2543 typename _Proj =
identity>
2544 requires sortable<_Iter, _Comp, _Proj>
2546 operator()(_Iter __first, _Iter __middle, _Sent __last,
2547 _Comp __comp = {}, _Proj __proj = {})
const
2549 auto __lasti = ranges::next(__first, __last);
2551 __detail::__make_comp_proj(__comp, __proj));
2555 template<bidirectional_range _Range,
2556 typename _Comp = ranges::less,
typename _Proj = identity>
2557 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2558 borrowed_iterator_t<_Range>
2559 operator()(_Range&& __r, iterator_t<_Range> __middle,
2560 _Comp __comp = {}, _Proj __proj = {})
const
2562 return (*
this)(ranges::begin(__r),
std::move(__middle),
2568 inline constexpr __inplace_merge_fn inplace_merge{};
2570 struct __includes_fn
2572 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2573 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2574 typename _Proj1 =
identity,
typename _Proj2 =
identity,
2575 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2576 projected<_Iter2, _Proj2>>
2577 _Comp = ranges::less>
2579 operator()(_Iter1 __first1, _Sent1 __last1,
2580 _Iter2 __first2, _Sent2 __last2,
2582 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2584 while (__first1 != __last1 && __first2 != __last2)
2599 return __first2 == __last2;
2602 template<input_range _Range1, input_range _Range2,
2603 typename _Proj1 = identity,
typename _Proj2 = identity,
2604 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2605 projected<iterator_t<_Range2>, _Proj2>>
2606 _Comp = ranges::less>
2608 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2609 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2611 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2612 ranges::begin(__r2), ranges::end(__r2),
2618 inline constexpr __includes_fn includes{};
2620 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2621 using set_union_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2623 struct __set_union_fn
2625 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2626 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2627 weakly_incrementable _Out,
typename _Comp = ranges::less,
2628 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2629 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2630 constexpr set_union_result<_Iter1, _Iter2, _Out>
2631 operator()(_Iter1 __first1, _Sent1 __last1,
2632 _Iter2 __first2, _Sent2 __last2,
2633 _Out __result, _Comp __comp = {},
2634 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2636 while (__first1 != __last1 && __first2 != __last2)
2642 *__result = *__first1;
2649 *__result = *__first2;
2654 *__result = *__first1;
2668 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2669 typename _Comp = ranges::less,
2670 typename _Proj1 = identity,
typename _Proj2 = identity>
2671 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2672 _Comp, _Proj1, _Proj2>
2673 constexpr set_union_result<borrowed_iterator_t<_Range1>,
2674 borrowed_iterator_t<_Range2>, _Out>
2675 operator()(_Range1&& __r1, _Range2&& __r2,
2676 _Out __result, _Comp __comp = {},
2677 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2679 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2680 ranges::begin(__r2), ranges::end(__r2),
2686 inline constexpr __set_union_fn set_union{};
2688 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2689 using set_intersection_result = in_in_out_result<_Iter1, _Iter2, _Out>;
2691 struct __set_intersection_fn
2693 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2694 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2695 weakly_incrementable _Out,
typename _Comp = ranges::less,
2696 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2697 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2698 constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2699 operator()(_Iter1 __first1, _Sent1 __last1,
2700 _Iter2 __first2, _Sent2 __last2, _Out __result,
2702 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2704 while (__first1 != __last1 && __first2 != __last2)
2715 *__result = *__first1;
2726 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2727 typename _Comp = ranges::less,
2728 typename _Proj1 = identity,
typename _Proj2 = identity>
2729 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2730 _Comp, _Proj1, _Proj2>
2731 constexpr set_intersection_result<borrowed_iterator_t<_Range1>,
2732 borrowed_iterator_t<_Range2>, _Out>
2733 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2735 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2737 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2738 ranges::begin(__r2), ranges::end(__r2),
2744 inline constexpr __set_intersection_fn set_intersection{};
2746 template<
typename _Iter,
typename _Out>
2747 using set_difference_result = in_out_result<_Iter, _Out>;
2749 struct __set_difference_fn
2751 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2752 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2753 weakly_incrementable _Out,
typename _Comp = ranges::less,
2754 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2755 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2756 constexpr set_difference_result<_Iter1, _Out>
2757 operator()(_Iter1 __first1, _Sent1 __last1,
2758 _Iter2 __first2, _Sent2 __last2, _Out __result,
2760 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2762 while (__first1 != __last1 && __first2 != __last2)
2767 *__result = *__first1;
2784 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2785 typename _Comp = ranges::less,
2786 typename _Proj1 = identity,
typename _Proj2 = identity>
2787 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2788 _Comp, _Proj1, _Proj2>
2789 constexpr set_difference_result<borrowed_iterator_t<_Range1>, _Out>
2790 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2792 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2794 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2795 ranges::begin(__r2), ranges::end(__r2),
2801 inline constexpr __set_difference_fn set_difference{};
2803 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2804 using set_symmetric_difference_result
2805 = in_in_out_result<_Iter1, _Iter2, _Out>;
2807 struct __set_symmetric_difference_fn
2809 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2810 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2811 weakly_incrementable _Out,
typename _Comp = ranges::less,
2812 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2813 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2814 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
2815 operator()(_Iter1 __first1, _Sent1 __last1,
2816 _Iter2 __first2, _Sent2 __last2,
2817 _Out __result, _Comp __comp = {},
2818 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2820 while (__first1 != __last1 && __first2 != __last2)
2825 *__result = *__first1;
2833 *__result = *__first2;
2850 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2851 typename _Comp = ranges::less,
2852 typename _Proj1 = identity,
typename _Proj2 = identity>
2853 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2854 _Comp, _Proj1, _Proj2>
2855 constexpr set_symmetric_difference_result<borrowed_iterator_t<_Range1>,
2856 borrowed_iterator_t<_Range2>,
2858 operator()(_Range1&& __r1, _Range2&& __r2, _Out __result,
2860 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
2862 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
2863 ranges::begin(__r2), ranges::end(__r2),
2869 inline constexpr __set_symmetric_difference_fn set_symmetric_difference{};
2875 template<
typename _Tp,
typename _Proj = identity,
2876 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2877 _Comp = ranges::less>
2878 constexpr const _Tp&
2879 operator()(
const _Tp& __a,
const _Tp& __b,
2880 _Comp __comp = {}, _Proj __proj = {})
const
2890 template<input_range _Range,
typename _Proj = identity,
2891 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2892 _Comp = ranges::less>
2893 requires indirectly_copyable_storable<iterator_t<_Range>,
2894 range_value_t<_Range>*>
2895 constexpr range_value_t<_Range>
2896 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2898 auto __first = ranges::begin(__r);
2899 auto __last = ranges::end(__r);
2900 __glibcxx_assert(__first != __last);
2901 auto __result = *__first;
2902 while (++__first != __last)
2904 auto __tmp = *__first;
2913 template<copyable _Tp,
typename _Proj = identity,
2914 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2915 _Comp = ranges::less>
2917 operator()(initializer_list<_Tp> __r,
2918 _Comp __comp = {}, _Proj __proj = {})
const
2920 return (*
this)(ranges::subrange(__r),
2925 inline constexpr __max_fn
max{};
2929 template<
typename _Tp,
typename _Proj = identity,
2930 indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp
2932 constexpr const _Tp&
2933 operator()(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi,
2934 _Comp __comp = {}, _Proj __proj = {})
const
2949 inline constexpr __clamp_fn
clamp{};
2951 template<
typename _Tp>
2952 struct min_max_result
2954 [[no_unique_address]] _Tp
min;
2955 [[no_unique_address]] _Tp
max;
2957 template<
typename _Tp2>
2958 requires convertible_to<const _Tp&, _Tp2>
2960 operator min_max_result<_Tp2>() const &
2963 template<
typename _Tp2>
2964 requires convertible_to<_Tp, _Tp2>
2966 operator min_max_result<_Tp2>() &&
2970 template<
typename _Tp>
2971 using minmax_result = min_max_result<_Tp>;
2975 template<
typename _Tp,
typename _Proj = identity,
2976 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
2977 _Comp = ranges::less>
2978 constexpr minmax_result<const _Tp&>
2979 operator()(
const _Tp& __a,
const _Tp& __b,
2980 _Comp __comp = {}, _Proj __proj = {})
const
2990 template<input_range _Range,
typename _Proj = identity,
2991 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2992 _Comp = ranges::less>
2993 requires indirectly_copyable_storable<iterator_t<_Range>, range_value_t<_Range>*>
2994 constexpr minmax_result<range_value_t<_Range>>
2995 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
2997 auto __first = ranges::begin(__r);
2998 auto __last = ranges::end(__r);
2999 __glibcxx_assert(__first != __last);
3000 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3001 minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};
3002 if (++__first == __last)
3008 auto&& __val = *__first;
3009 if (__comp_proj(__val, __result.min))
3010 __result.min = std::forward<decltype(__val)>(__val);
3012 __result.max = std::forward<decltype(__val)>(__val);
3014 while (++__first != __last)
3019 range_value_t<_Range> __val1 = *__first;
3020 if (++__first == __last)
3025 if (__comp_proj(__val1, __result.min))
3027 else if (!__comp_proj(__val1, __result.max))
3031 auto&& __val2 = *__first;
3032 if (!__comp_proj(__val2, __val1))
3034 if (__comp_proj(__val1, __result.min))
3036 if (!__comp_proj(__val2, __result.max))
3037 __result.max = std::forward<decltype(__val2)>(__val2);
3041 if (__comp_proj(__val2, __result.min))
3042 __result.min = std::forward<decltype(__val2)>(__val2);
3043 if (!__comp_proj(__val1, __result.max))
3050 template<copyable _Tp,
typename _Proj = identity,
3051 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3052 _Comp = ranges::less>
3053 constexpr minmax_result<_Tp>
3054 operator()(initializer_list<_Tp> __r,
3055 _Comp __comp = {}, _Proj __proj = {})
const
3057 return (*
this)(ranges::subrange(__r),
3062 inline constexpr __minmax_fn
minmax{};
3064 struct __min_element_fn
3066 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3067 typename _Proj =
identity,
3068 indirect_strict_weak_order<projected<_Iter, _Proj>>
3069 _Comp = ranges::less>
3071 operator()(_Iter __first, _Sent __last,
3072 _Comp __comp = {}, _Proj __proj = {})
const
3074 if (__first == __last)
3078 while (++__i != __last)
3088 template<forward_range _Range,
typename _Proj = identity,
3089 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3090 _Comp = ranges::less>
3091 constexpr borrowed_iterator_t<_Range>
3092 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3094 return (*
this)(ranges::begin(__r), ranges::end(__r),
3099 inline constexpr __min_element_fn min_element{};
3101 struct __max_element_fn
3103 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3104 typename _Proj =
identity,
3105 indirect_strict_weak_order<projected<_Iter, _Proj>>
3106 _Comp = ranges::less>
3108 operator()(_Iter __first, _Sent __last,
3109 _Comp __comp = {}, _Proj __proj = {})
const
3111 if (__first == __last)
3115 while (++__i != __last)
3125 template<forward_range _Range,
typename _Proj = identity,
3126 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3127 _Comp = ranges::less>
3128 constexpr borrowed_iterator_t<_Range>
3129 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3131 return (*
this)(ranges::begin(__r), ranges::end(__r),
3136 inline constexpr __max_element_fn max_element{};
3138 template<
typename _Iter>
3139 using minmax_element_result = min_max_result<_Iter>;
3141 struct __minmax_element_fn
3143 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3144 typename _Proj =
identity,
3145 indirect_strict_weak_order<projected<_Iter, _Proj>>
3146 _Comp = ranges::less>
3147 constexpr minmax_element_result<_Iter>
3148 operator()(_Iter __first, _Sent __last,
3149 _Comp __comp = {}, _Proj __proj = {})
const
3151 auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
3152 minmax_element_result<_Iter> __result = {__first, __first};
3153 if (__first == __last || ++__first == __last)
3159 if (__comp_proj(*__first, *__result.min))
3160 __result.min = __first;
3162 __result.max = __first;
3164 while (++__first != __last)
3169 auto __prev = __first;
3170 if (++__first == __last)
3175 if (__comp_proj(*__prev, *__result.min))
3176 __result.min = __prev;
3177 else if (!__comp_proj(*__prev, *__result.max))
3178 __result.max = __prev;
3181 if (!__comp_proj(*__first, *__prev))
3183 if (__comp_proj(*__prev, *__result.min))
3184 __result.min = __prev;
3185 if (!__comp_proj(*__first, *__result.max))
3186 __result.max = __first;
3190 if (__comp_proj(*__first, *__result.min))
3191 __result.min = __first;
3192 if (!__comp_proj(*__prev, *__result.max))
3193 __result.max = __prev;
3199 template<forward_range _Range,
typename _Proj = identity,
3200 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3201 _Comp = ranges::less>
3202 constexpr minmax_element_result<borrowed_iterator_t<_Range>>
3203 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3205 return (*
this)(ranges::begin(__r), ranges::end(__r),
3210 inline constexpr __minmax_element_fn minmax_element{};
3212 struct __lexicographical_compare_fn
3214 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3215 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3216 typename _Proj1 =
identity,
typename _Proj2 =
identity,
3217 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3218 projected<_Iter2, _Proj2>>
3219 _Comp = ranges::less>
3221 operator()(_Iter1 __first1, _Sent1 __last1,
3222 _Iter2 __first2, _Sent2 __last2,
3224 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3226 if constexpr (__detail::__is_normal_iterator<_Iter1>
3227 && same_as<_Iter1, _Sent1>)
3228 return (*
this)(__first1.base(), __last1.base(),
3232 else if constexpr (__detail::__is_normal_iterator<_Iter2>
3233 && same_as<_Iter2, _Sent2>)
3235 __first2.base(), __last2.base(),
3240 constexpr bool __sized_iters
3241 = (sized_sentinel_for<_Sent1, _Iter1>
3242 && sized_sentinel_for<_Sent2, _Iter2>);
3243 if constexpr (__sized_iters)
3245 using _ValueType1 = iter_value_t<_Iter1>;
3246 using _ValueType2 = iter_value_t<_Iter2>;
3249 constexpr bool __use_memcmp
3250 = (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
3251 && __ptr_to_nonvolatile<_Iter1>
3252 && __ptr_to_nonvolatile<_Iter2>
3253 && (is_same_v<_Comp, ranges::less>
3254 || is_same_v<_Comp, ranges::greater>)
3255 && is_same_v<_Proj1, identity>
3256 && is_same_v<_Proj2, identity>);
3257 if constexpr (__use_memcmp)
3259 const auto __d1 = __last1 - __first1;
3260 const auto __d2 = __last2 - __first2;
3262 if (
const auto __len =
std::min(__d1, __d2))
3265 = std::__memcmp(__first1, __first2, __len);
3266 if constexpr (is_same_v<_Comp, ranges::less>)
3273 else if constexpr (is_same_v<_Comp, ranges::greater>)
3285 for (; __first1 != __last1 && __first2 != __last2;
3286 ++__first1, (void) ++__first2)
3297 return __first1 == __last1 && __first2 != __last2;
3301 template<input_range _Range1, input_range _Range2,
3302 typename _Proj1 = identity,
typename _Proj2 = identity,
3303 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3304 projected<iterator_t<_Range2>, _Proj2>>
3305 _Comp = ranges::less>
3307 operator()(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3308 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
const
3310 return (*
this)(ranges::begin(__r1), ranges::end(__r1),
3311 ranges::begin(__r2), ranges::end(__r2),
3317 template<
typename _Iter,
typename _Ref = iter_reference_t<_Iter>>
3318 static constexpr bool __ptr_to_nonvolatile
3319 = is_pointer_v<_Iter> && !is_volatile_v<remove_reference_t<_Ref>>;
3322 inline constexpr __lexicographical_compare_fn lexicographical_compare;
3324 template<
typename _Iter>
3325 struct in_found_result
3327 [[no_unique_address]] _Iter in;
3330 template<
typename _Iter2>
3331 requires convertible_to<const _Iter&, _Iter2>
3333 operator in_found_result<_Iter2>() const &
3334 {
return {in, found}; }
3336 template<
typename _Iter2>
3337 requires convertible_to<_Iter, _Iter2>
3339 operator in_found_result<_Iter2>() &&
3343 template<
typename _Iter>
3344 using next_permutation_result = in_found_result<_Iter>;
3346 struct __next_permutation_fn
3348 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3349 typename _Comp = ranges::less,
typename _Proj =
identity>
3350 requires sortable<_Iter, _Comp, _Proj>
3351 constexpr next_permutation_result<_Iter>
3352 operator()(_Iter __first, _Sent __last,
3353 _Comp __comp = {}, _Proj __proj = {})
const
3355 if (__first == __last)
3363 auto __lasti = ranges::next(__first, __last);
3380 ranges::iter_swap(__i, __j);
3381 ranges::reverse(__ii, __last);
3386 ranges::reverse(__first, __last);
3392 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3393 typename _Proj = identity>
3394 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3395 constexpr next_permutation_result<borrowed_iterator_t<_Range>>
3396 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3398 return (*
this)(ranges::begin(__r), ranges::end(__r),
3403 inline constexpr __next_permutation_fn next_permutation{};
3405 template<
typename _Iter>
3406 using prev_permutation_result = in_found_result<_Iter>;
3408 struct __prev_permutation_fn
3410 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3411 typename _Comp = ranges::less,
typename _Proj =
identity>
3412 requires sortable<_Iter, _Comp, _Proj>
3413 constexpr prev_permutation_result<_Iter>
3414 operator()(_Iter __first, _Sent __last,
3415 _Comp __comp = {}, _Proj __proj = {})
const
3417 if (__first == __last)
3425 auto __lasti = ranges::next(__first, __last);
3442 ranges::iter_swap(__i, __j);
3443 ranges::reverse(__ii, __last);
3448 ranges::reverse(__first, __last);
3454 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3455 typename _Proj = identity>
3456 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3457 constexpr prev_permutation_result<borrowed_iterator_t<_Range>>
3458 operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
const
3460 return (*
this)(ranges::begin(__r), ranges::end(__r),
3465 inline constexpr __prev_permutation_fn prev_permutation{};
3469#define __cpp_lib_shift 201806L
3470 template<
typename _ForwardIterator>
3471 constexpr _ForwardIterator
3472 shift_left(_ForwardIterator __first, _ForwardIterator __last,
3473 typename iterator_traits<_ForwardIterator>::difference_type __n)
3475 __glibcxx_assert(__n >= 0);
3479 auto __mid = ranges::next(__first, __n, __last);
3480 if (__mid == __last)
3485 template<
typename _ForwardIterator>
3486 constexpr _ForwardIterator
3487 shift_right(_ForwardIterator __first, _ForwardIterator __last,
3488 typename iterator_traits<_ForwardIterator>::difference_type __n)
3490 __glibcxx_assert(__n >= 0);
3495 =
typename iterator_traits<_ForwardIterator>::iterator_category;
3496 if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
3498 auto __mid = ranges::next(__last, -__n, __first);
3499 if (__mid == __first)
3507 auto __result = ranges::next(__first, __n, __last);
3508 if (__result == __last)
3511 auto __dest_head = __first, __dest_tail = __result;
3512 while (__dest_head != __result)
3514 if (__dest_tail == __last)
3538 auto __cursor = __first;
3539 while (__cursor != __result)
3541 if (__dest_tail == __last)
3546 __dest_head =
std::move(__cursor, __result,
3552 std::iter_swap(__cursor, __dest_head);
3561_GLIBCXX_END_NAMESPACE_VERSION
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr __invoke_result< _Callable, _Args... >::type __invoke(_Callable &&__fn, _Args &&... __args) noexcept(__is_nothrow_invocable< _Callable, _Args... >::value)
Invoke a callable object.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
constexpr _InputIterator for_each_n(_InputIterator __first, _Size __n, _Function __f)
Apply a function to every element of a sequence.
constexpr const _Tp & clamp(const _Tp &, const _Tp &, const _Tp &)
Returns the value clamped between lo and hi.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.
_SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __out, _Distance __n, _UniformRandomBitGenerator &&__g)
Take a random sample from a population.