30 #ifndef _RANGES_ALGO_H
31 #define _RANGES_ALGO_H 1
33 #if __cplusplus > 201703L
44 #if __cpp_lib_concepts
45 namespace std _GLIBCXX_VISIBILITY(default)
47 _GLIBCXX_BEGIN_NAMESPACE_VERSION
52 template<
typename _Tp>
53 constexpr
inline bool __is_normal_iterator =
false;
55 template<
typename _Iterator,
typename _Container>
57 __is_normal_iterator<__gnu_cxx::__normal_iterator<_Iterator,
60 template<
typename _Tp>
61 constexpr
inline bool __is_reverse_iterator =
false;
63 template<
typename _Iterator>
65 __is_reverse_iterator<reverse_iterator<_Iterator>> =
true;
67 template<
typename _Tp>
68 constexpr
inline bool __is_move_iterator =
false;
70 template<
typename _Iterator>
72 __is_move_iterator<move_iterator<_Iterator>> =
true;
74 template<
typename _Comp,
typename _Proj>
76 __make_comp_proj(_Comp& __comp, _Proj& __proj)
78 return [&] (
auto&& __lhs,
auto&& __rhs) ->
bool {
79 using _TL = decltype(__lhs);
80 using _TR = decltype(__rhs);
87 template<
typename _Pred,
typename _Proj>
89 __make_pred_proj(_Pred& __pred, _Proj& __proj)
91 return [&] <
typename _Tp> (_Tp&& __arg) ->
bool {
98 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
99 typename _Proj =
identity,
100 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
102 all_of(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
104 for (; __first != __last; ++__first)
110 template<input_range _Range,
typename _Proj = identity,
111 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
113 all_of(_Range&& __r, _Pred __pred, _Proj __proj = {})
119 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
120 typename _Proj =
identity,
121 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
123 any_of(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
125 for (; __first != __last; ++__first)
131 template<input_range _Range,
typename _Proj = identity,
132 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
134 any_of(_Range&& __r, _Pred __pred, _Proj __proj = {})
140 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
141 typename _Proj =
identity,
142 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
144 none_of(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
146 for (; __first != __last; ++__first)
152 template<input_range _Range,
typename _Proj = identity,
153 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
155 none_of(_Range&& __r, _Pred __pred, _Proj __proj = {})
161 template<
typename _Iter,
typename _Fp>
162 struct for_each_result
164 [[no_unique_address]] _Iter in;
165 [[no_unique_address]] _Fp fun;
167 template<
typename _Iter2,
typename _F2p>
168 requires convertible_to<const _Iter&, _Iter2>
169 && convertible_to<const _Fp&, _F2p>
170 operator for_each_result<_Iter2, _F2p>() const &
171 {
return {in, fun}; }
173 template<
typename _Iter2,
typename _F2p>
174 requires convertible_to<_Iter, _Iter2> && convertible_to<_Fp, _F2p>
175 operator for_each_result<_Iter2, _F2p>() &&
179 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
180 typename _Proj =
identity,
181 indirectly_unary_invocable<projected<_Iter, _Proj>> _Fun>
182 constexpr for_each_result<_Iter, _Fun>
183 for_each(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {})
185 for (; __first != __last; ++__first)
190 template<input_range _Range,
typename _Proj = identity,
191 indirectly_unary_invocable<projected<iterator_t<_Range>, _Proj>>
193 constexpr for_each_result<safe_iterator_t<_Range>, _Fun>
194 for_each(_Range&& __r, _Fun __f, _Proj __proj = {})
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 find(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
207 while (__first != __last
213 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
214 requires indirect_binary_predicate<ranges::equal_to,
215 projected<iterator_t<_Range>, _Proj>,
217 constexpr safe_iterator_t<_Range>
218 find(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
224 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
225 typename _Proj =
identity,
226 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
228 find_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
230 while (__first != __last
236 template<input_range _Range,
typename _Proj = identity,
237 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
239 constexpr safe_iterator_t<_Range>
240 find_if(_Range&& __r, _Pred __pred, _Proj __proj = {})
246 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
247 typename _Proj =
identity,
248 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
250 find_if_not(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
252 while (__first != __last
258 template<input_range _Range,
typename _Proj = identity,
259 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>>
261 constexpr safe_iterator_t<_Range>
262 find_if_not(_Range&& __r, _Pred __pred, _Proj __proj = {})
268 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
269 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
270 typename _Pred = ranges::equal_to,
271 typename _Proj1 =
identity,
typename _Proj2 =
identity>
272 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
274 find_first_of(_Iter1 __first1, _Sent1 __last1,
275 _Iter2 __first2, _Sent2 __last2,
276 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
278 for (; __first1 != __last1; ++__first1)
279 for (
auto __iter = __first2; __iter != __last2; ++__iter)
287 template<input_range _Range1, forward_range _Range2,
288 typename _Pred = ranges::equal_to,
289 typename _Proj1 = identity,
typename _Proj2 = identity>
290 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
291 _Pred, _Proj1, _Proj2>
292 constexpr safe_iterator_t<_Range1>
293 find_first_of(_Range1&& __r1, _Range2&& __r2,
294 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
302 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
303 typename _Tp,
typename _Proj =
identity>
304 requires indirect_binary_predicate<ranges::equal_to,
305 projected<_Iter, _Proj>,
307 constexpr iter_difference_t<_Iter>
308 count(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
310 iter_difference_t<_Iter> __n = 0;
311 for (; __first != __last; ++__first)
317 template<input_range _Range,
typename _Tp,
typename _Proj =
identity>
318 requires indirect_binary_predicate<ranges::equal_to,
319 projected<iterator_t<_Range>, _Proj>,
321 constexpr range_difference_t<_Range>
322 count(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
328 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
329 typename _Proj =
identity,
330 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
331 constexpr iter_difference_t<_Iter>
332 count_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
334 iter_difference_t<_Iter> __n = 0;
335 for (; __first != __last; ++__first)
341 template<input_range _Range,
342 typename _Proj = identity,
343 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
344 constexpr range_difference_t<_Range>
345 count_if(_Range&& __r, _Pred __pred, _Proj __proj = {})
351 template<
typename _Iter1,
typename _Iter2>
352 struct mismatch_result
354 [[no_unique_address]] _Iter1 in1;
355 [[no_unique_address]] _Iter2 in2;
357 template<
typename _IIter1,
typename _IIter2>
358 requires convertible_to<const _Iter1&, _IIter1>
359 && convertible_to<const _Iter2&, _IIter2>
360 operator mismatch_result<_IIter1, _IIter2>() const &
361 {
return {in1, in2}; }
363 template<
typename _IIter1,
typename _IIter2>
364 requires convertible_to<_Iter1, _IIter1>
365 && convertible_to<_Iter2, _IIter2>
366 operator mismatch_result<_IIter1, _IIter2>() &&
370 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
371 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
372 typename _Pred = ranges::equal_to,
373 typename _Proj1 =
identity,
typename _Proj2 =
identity>
374 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
375 constexpr mismatch_result<_Iter1, _Iter2>
376 mismatch(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
377 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
379 while (__first1 != __last1 && __first2 != __last2
390 template<input_range _Range1, input_range _Range2,
391 typename _Pred = ranges::equal_to,
392 typename _Proj1 = identity,
typename _Proj2 = identity>
393 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
394 _Pred, _Proj1, _Proj2>
395 constexpr mismatch_result<iterator_t<_Range1>, iterator_t<_Range2>>
396 mismatch(_Range1&& __r1, _Range2&& __r2,
397 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
405 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
406 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
407 typename _Pred = ranges::equal_to,
408 typename _Proj1 =
identity,
typename _Proj2 =
identity>
409 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
410 constexpr subrange<_Iter1>
411 search(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
412 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
414 if (__first1 == __last1 || __first2 == __last2)
415 return {__first1, __first1};
421 if (__first1 == __last1)
422 return {__first1, __first1};
429 auto __cur1 = __first1;
430 auto __cur2 = __first2;
433 if (++__cur2 == __last2)
434 return {__first1, ++__cur1};
435 if (++__cur1 == __last1)
436 return {__cur1, __cur1};
448 template<forward_range _Range1, forward_range _Range2,
449 typename _Pred = ranges::equal_to,
450 typename _Proj1 = identity,
typename _Proj2 = identity>
451 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
452 _Pred, _Proj1, _Proj2>
453 constexpr safe_subrange_t<_Range1>
454 search(_Range1&& __r1, _Range2&& __r2,
455 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
463 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
typename _Tp,
464 typename _Pred = ranges::equal_to,
typename _Proj =
identity>
465 requires indirectly_comparable<_Iter, const _Tp*, _Pred, _Proj>
466 constexpr subrange<_Iter>
467 search_n(_Iter __first, _Sent __last, iter_difference_t<_Iter> __count,
468 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
471 return {__first, __first};
473 auto __value_comp = [&] <
typename _Rp> (_Rp&& __arg) {
474 return std::__invoke(__pred, std::forward<_Rp>(__arg), __value);
478 __first = ranges::find_if(
std::move(__first), __last,
480 if (__first == __last)
481 return {__first, __first};
484 auto __end = __first;
485 return {__first, ++__end};
489 if constexpr (sized_sentinel_for<_Sent, _Iter>)
491 auto __tail_size = __last - __first;
492 auto __remainder = __count;
494 while (__remainder <= __tail_size)
496 __first += __remainder;
497 __tail_size -= __remainder;
498 auto __backtrack = __first;
501 if (--__remainder == 0)
502 return {__first - __count, __first};
505 auto __i = __first + __tail_size;
510 __first = ranges::find_if(__first, __last, __value_comp, __proj);
511 while (__first != __last)
516 while (__i != __last && __n != 1
523 return {__first, __i};
526 __first = ranges::find_if(++__i, __last, __value_comp, __proj);
528 return {__first, __first};
532 template<forward_range _Range,
typename _Tp,
533 typename _Pred = ranges::equal_to,
typename _Proj = identity>
534 requires indirectly_comparable<iterator_t<_Range>,
const _Tp*, _Pred, _Proj>
535 constexpr safe_subrange_t<_Range>
536 search_n(_Range&& __r, range_difference_t<_Range> __count,
537 const _Tp& __value, _Pred __pred = {}, _Proj __proj = {})
544 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
545 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
546 typename _Pred = ranges::equal_to,
547 typename _Proj1 =
identity,
typename _Proj2 =
identity>
548 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
549 constexpr subrange<_Iter1>
550 __find_end(_Iter1 __first1, _Sent1 __last1,
551 _Iter2 __first2, _Sent2 __last2,
552 _Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
554 auto __i = ranges::next(__first1, __last1);
555 if (__first2 == __last2)
558 auto __result_begin = __i;
559 auto __result_end = __i;
562 auto __new_range = ranges::search(__first1, __last1,
564 __pred, __proj1, __proj2);
567 if (__new_result_begin == __last1)
568 return {__result_begin, __result_end};
571 __result_begin = __new_result_begin;
572 __result_end = __new_result_end;
573 __first1 = __result_begin;
579 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
580 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
581 typename _Pred = ranges::equal_to,
582 typename _Proj1 =
identity,
typename _Proj2 =
identity>
583 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
584 constexpr subrange<_Iter1>
585 find_end(_Iter1 __first1, _Sent1 __last1,
586 _Iter2 __first2, _Sent2 __last2,
587 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
589 if constexpr (bidirectional_iterator<_Iter1>
590 && bidirectional_iterator<_Iter2>)
592 auto __i1 = ranges::next(__first1, __last1);
593 auto __i2 = ranges::next(__first2, __last2);
595 = ranges::search(reverse_iterator<_Iter1>{__i1},
596 reverse_iterator<_Iter1>{__first1},
597 reverse_iterator<_Iter2>{__i2},
598 reverse_iterator<_Iter2>{__first2},
601 auto __result_first =
ranges::end(__rresult).base();
603 if (__result_last == __first1)
606 return {__result_first, __result_last};
609 return ranges::__find_end(__first1, __last1, __first2, __last2,
614 template<forward_range _Range1, forward_range _Range2,
615 typename _Pred = ranges::equal_to,
616 typename _Proj1 = identity,
typename _Proj2 = identity>
617 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
618 _Pred, _Proj1, _Proj2>
619 constexpr safe_subrange_t<_Range1>
620 find_end(_Range1&& __r1, _Range2&& __r2,
621 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
629 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
630 typename _Proj =
identity,
631 indirect_binary_predicate<projected<_Iter, _Proj>,
632 projected<_Iter, _Proj>> _Pred
635 adjacent_find(_Iter __first, _Sent __last,
636 _Pred __pred = {}, _Proj __proj = {})
638 if (__first == __last)
640 auto __next = __first;
641 for (; ++__next != __last; __first = __next)
651 template<forward_range _Range,
typename _Proj = identity,
652 indirect_binary_predicate<
653 projected<iterator_t<_Range>, _Proj>,
654 projected<iterator_t<_Range>, _Proj>> _Pred = ranges::equal_to>
655 constexpr safe_iterator_t<_Range>
656 adjacent_find(_Range&& __r, _Pred __pred = {}, _Proj __proj = {})
662 template<forward_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
663 forward_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
664 typename _Proj1 =
identity,
typename _Proj2 =
identity,
665 indirect_equivalence_relation<projected<_Iter1, _Proj1>,
666 projected<_Iter2, _Proj2>> _Pred
669 is_permutation(_Iter1 __first1, _Sent1 __last1,
670 _Iter2 __first2, _Sent2 __last2, _Pred __pred = {},
671 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
673 constexpr
bool __sized_iters
674 = (sized_sentinel_for<_Sent1, _Iter1>
675 && sized_sentinel_for<_Sent2, _Iter2>);
676 if constexpr (__sized_iters)
686 for (; __first1 != __last1 && __first2 != __last2;
687 ++__first1, (void)++__first2)
693 if constexpr (__sized_iters)
695 if (__first1 == __last1)
702 if (__d1 == 0 && __d2 == 0)
708 for (
auto __scan = __first1; __scan != __last1; ++__scan)
711 auto __comp_scan = [&] <
typename _Tp> (_Tp&& __arg) {
713 std::forward<_Tp>(__arg));
715 if (__scan != ranges::find_if(__first1, __scan,
716 __comp_scan, __proj1))
719 auto __matches = ranges::count_if(__first2, __last2,
720 __comp_scan, __proj2);
722 || ranges::count_if(__scan, __last1,
723 __comp_scan, __proj1) != __matches)
729 template<forward_range _Range1, forward_range _Range2,
730 typename _Proj1 = identity,
typename _Proj2 = identity,
731 indirect_equivalence_relation<
732 projected<iterator_t<_Range1>, _Proj1>,
733 projected<iterator_t<_Range2>, _Proj2>> _Pred = ranges::equal_to>
735 is_permutation(_Range1&& __r1, _Range2&& __r2, _Pred __pred = {},
736 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
744 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
745 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
746 typename _Pred,
typename _Proj1,
typename _Proj2>
747 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
749 __equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
750 _Pred __pred, _Proj1 __proj1, _Proj2 __proj2)
754 constexpr
bool __sized_iters
755 = (sized_sentinel_for<_Sent1, _Iter1>
756 && sized_sentinel_for<_Sent2, _Iter2>);
757 if constexpr (__sized_iters)
764 using _ValueType1 = iter_value_t<_Iter1>;
765 using _ValueType2 = iter_value_t<_Iter2>;
766 constexpr
bool __use_memcmp
767 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
768 && is_same_v<_ValueType1, _ValueType2>
769 && is_pointer_v<_Iter1>
770 && is_pointer_v<_Iter2>
771 && is_same_v<_Pred, ranges::equal_to>
772 && is_same_v<_Proj1, identity>
773 && is_same_v<_Proj2, identity>);
774 if constexpr (__use_memcmp)
776 if (
const size_t __len = (__last1 - __first1))
777 return !std::__memcmp(__first1, __first2, __len);
782 for (; __first1 != __last1; ++__first1, (void)++__first2)
792 for (; __first1 != __last1 && __first2 != __last2;
793 ++__first1, (void)++__first2)
798 return __first1 == __last1 && __first2 == __last2;
802 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
803 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
804 typename _Pred = ranges::equal_to,
805 typename _Proj1 =
identity,
typename _Proj2 =
identity>
806 requires indirectly_comparable<_Iter1, _Iter2, _Pred, _Proj1, _Proj2>
808 equal(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
809 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
811 return ranges::__equal(std::__niter_base(
std::move(__first1)),
819 template<input_range _Range1, input_range _Range2,
820 typename _Pred = ranges::equal_to,
821 typename _Proj1 = identity,
typename _Proj2 = identity>
822 requires indirectly_comparable<iterator_t<_Range1>, iterator_t<_Range2>,
823 _Pred, _Proj1, _Proj2>
825 equal(_Range1&& __r1, _Range2&& __r2,
826 _Pred __pred = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
834 template<
typename _Iter,
typename _Out>
837 [[no_unique_address]] _Iter in;
838 [[no_unique_address]] _Out out;
840 template<
typename _Iter2,
typename _Out2>
841 requires convertible_to<const _Iter&, _Iter2>
842 && convertible_to<const _Out&, _Out2>
843 operator copy_result<_Iter2, _Out2>() const &
844 {
return {in, out}; }
846 template<
typename _Iter2,
typename _Out2>
847 requires convertible_to<_Iter, _Iter2>
848 && convertible_to<_Out, _Out2>
849 operator copy_result<_Iter2, _Out2>() &&
853 template<
typename _Iter,
typename _Out>
854 using move_result = copy_result<_Iter, _Out>;
856 template<
typename _Iter1,
typename _Iter2>
857 using move_backward_result = copy_result<_Iter1, _Iter2>;
859 template<
typename _Iter1,
typename _Iter2>
860 using copy_backward_result = copy_result<_Iter1, _Iter2>;
862 template<
bool _IsMove,
863 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
864 bidirectional_iterator _Out>
866 ? indirectly_movable<_Iter, _Out>
867 : indirectly_copyable<_Iter, _Out>)
869 move_backward_result<_Iter, _Out>,
870 copy_backward_result<_Iter, _Out>>
871 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result);
873 template<
bool _IsMove,
874 input_iterator _Iter, sentinel_for<_Iter> _Sent,
875 weakly_incrementable _Out>
877 ? indirectly_movable<_Iter, _Out>
878 : indirectly_copyable<_Iter, _Out>)
880 move_result<_Iter, _Out>,
881 copy_result<_Iter, _Out>>
882 __copy_or_move(_Iter __first, _Sent __last, _Out __result)
886 constexpr
bool __normal_iterator_p
887 = (__detail::__is_normal_iterator<_Iter>
888 || __detail::__is_normal_iterator<_Out>);
889 constexpr
bool __reverse_p
890 = (__detail::__is_reverse_iterator<_Iter>
891 && __detail::__is_reverse_iterator<_Out>);
892 constexpr
bool __move_iterator_p = __detail::__is_move_iterator<_Iter>;
893 if constexpr (__move_iterator_p)
896 = ranges::__copy_or_move<true>(
std::move(__first).base(),
901 else if constexpr (__reverse_p)
904 = ranges::__copy_or_move_backward<_IsMove>(__last.base(),
907 return {reverse_iterator{
std::move(__in)},
910 else if constexpr (__normal_iterator_p)
913 = ranges::__copy_or_move<_IsMove>(std::__niter_base(__first),
914 std::__niter_base(__last),
915 std::__niter_base(__result));
916 return {std::__niter_wrap(__first,
std::move(__in)),
917 std::__niter_wrap(__result,
std::move(__out))};
919 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
921 using _ValueTypeI = iter_value_t<_Iter>;
922 using _ValueTypeO = iter_value_t<_Out>;
923 constexpr
bool __use_memmove
924 = (is_trivially_copyable_v<_ValueTypeI>
925 && is_same_v<_ValueTypeI, _ValueTypeO>
926 && is_pointer_v<_Iter>
927 && is_pointer_v<_Out>);
929 if constexpr (__use_memmove)
931 static_assert(_IsMove
932 ? is_move_assignable_v<_ValueTypeI>
933 : is_copy_assignable_v<_ValueTypeI>);
934 auto __num = __last - __first;
936 std::__memmove<_IsMove>(__result, __first, __num);
937 return {__first + __num, __result + __num};
941 for (
auto __n = __last - __first; __n > 0; --__n)
943 if constexpr (_IsMove)
946 *__result = *__first;
955 while (__first != __last)
957 if constexpr (_IsMove)
960 *__result = *__first;
968 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
969 weakly_incrementable _Out>
970 requires indirectly_copyable<_Iter, _Out>
971 constexpr copy_result<_Iter, _Out>
972 copy(_Iter __first, _Sent __last, _Out __result)
974 return ranges::__copy_or_move<false>(
std::move(__first),
979 template<input_range _Range, weakly_incrementable _Out>
980 requires indirectly_copyable<iterator_t<_Range>, _Out>
981 constexpr copy_result<safe_iterator_t<_Range>, _Out>
982 copy(_Range&& __r, _Out __result)
988 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
989 weakly_incrementable _Out>
990 requires indirectly_movable<_Iter, _Out>
991 constexpr move_result<_Iter, _Out>
992 move(_Iter __first, _Sent __last, _Out __result)
994 return ranges::__copy_or_move<true>(
std::move(__first),
999 template<input_range _Range, weakly_incrementable _Out>
1000 requires indirectly_movable<iterator_t<_Range>, _Out>
1001 constexpr move_result<safe_iterator_t<_Range>, _Out>
1002 move(_Range&& __r, _Out __result)
1008 template<
bool _IsMove,
1009 bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1010 bidirectional_iterator _Out>
1012 ? indirectly_movable<_Iter, _Out>
1013 : indirectly_copyable<_Iter, _Out>)
1015 move_backward_result<_Iter, _Out>,
1016 copy_backward_result<_Iter, _Out>>
1017 __copy_or_move_backward(_Iter __first, _Sent __last, _Out __result)
1021 constexpr
bool __normal_iterator_p
1022 = (__detail::__is_normal_iterator<_Iter>
1023 || __detail::__is_normal_iterator<_Out>);
1024 constexpr
bool __reverse_p
1025 = (__detail::__is_reverse_iterator<_Iter>
1026 && __detail::__is_reverse_iterator<_Out>);
1027 if constexpr (__reverse_p)
1030 = ranges::__copy_or_move<_IsMove>(__last.base(),
1033 return {reverse_iterator{
std::move(__in)},
1036 else if constexpr (__normal_iterator_p)
1039 = ranges::__copy_or_move_backward<_IsMove>
1040 (std::__niter_base(__first),
1041 std::__niter_base(__last),
1042 std::__niter_base(__result));
1043 return {std::__niter_wrap(__first,
std::move(__in)),
1044 std::__niter_wrap(__result,
std::move(__out))};
1046 else if constexpr (sized_sentinel_for<_Sent, _Iter>)
1048 using _ValueTypeI = iter_value_t<_Iter>;
1049 using _ValueTypeO = iter_value_t<_Out>;
1050 constexpr
bool __use_memmove
1051 = (is_trivially_copyable_v<_ValueTypeI>
1052 && is_same_v<_ValueTypeI, _ValueTypeO>
1053 && is_pointer_v<_Iter>
1054 && is_pointer_v<_Out>);
1055 if constexpr (__use_memmove)
1057 static_assert(_IsMove
1058 ? is_move_assignable_v<_ValueTypeI>
1059 : is_copy_assignable_v<_ValueTypeI>);
1060 auto __num = __last - __first;
1062 std::__memmove<_IsMove>(__result - __num, __first, __num);
1063 return {__first + __num, __result - __num};
1067 auto __lasti = ranges::next(__first, __last);
1068 auto __tail = __lasti;
1070 for (
auto __n = __last - __first; __n > 0; --__n)
1074 if constexpr (_IsMove)
1077 *__result = *__tail;
1084 auto __lasti = ranges::next(__first, __last);
1085 auto __tail = __lasti;
1087 while (__first != __tail)
1091 if constexpr (_IsMove)
1094 *__result = *__tail;
1100 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1101 b
idirectional_iterator _Iter2>
1102 requires indirectly_copyable<_Iter1, _Iter2>
1103 constexpr copy_backward_result<_Iter1, _Iter2>
1104 copy_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result)
1106 return ranges::__copy_or_move_backward<false>(
std::move(__first),
1111 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
1112 requires indirectly_copyable<iterator_t<_Range>, _Iter>
1113 constexpr copy_backward_result<safe_iterator_t<_Range>, _Iter>
1114 copy_backward(_Range&& __r, _Iter __result)
1120 template<b
idirectional_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1121 b
idirectional_iterator _Iter2>
1122 requires indirectly_movable<_Iter1, _Iter2>
1123 constexpr move_backward_result<_Iter1, _Iter2>
1124 move_backward(_Iter1 __first, _Sent1 __last, _Iter2 __result)
1126 return ranges::__copy_or_move_backward<true>(
std::move(__first),
1131 template<b
idirectional_range _Range, b
idirectional_iterator _Iter>
1132 requires indirectly_movable<iterator_t<_Range>, _Iter>
1133 constexpr move_backward_result<safe_iterator_t<_Range>, _Iter>
1140 template<
typename _Iter,
typename _Out>
1141 using copy_n_result = copy_result<_Iter, _Out>;
1143 template<input_iterator _Iter, weakly_incrementable _Out>
1144 requires indirectly_copyable<_Iter, _Out>
1145 constexpr copy_n_result<_Iter, _Out>
1146 copy_n(_Iter __first, iter_difference_t<_Iter> __n, _Out __result)
1148 if constexpr (random_access_iterator<_Iter>)
1149 return ranges::copy(__first, __first + __n,
std::move(__result));
1152 for (; __n > 0; --__n, (void)++__result, (
void)++__first)
1153 *__result = *__first;
1158 template<
typename _Iter,
typename _Out>
1159 using copy_if_result = copy_result<_Iter, _Out>;
1161 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1162 weakly_incrementable _Out,
typename _Proj =
identity,
1163 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1164 requires indirectly_copyable<_Iter, _Out>
1165 constexpr copy_if_result<_Iter, _Out>
1166 copy_if(_Iter __first, _Sent __last, _Out __result,
1167 _Pred __pred, _Proj __proj = {})
1169 for (; __first != __last; ++__first)
1172 *__result = *__first;
1178 template<input_range _Range, weakly_incrementable _Out,
1179 typename _Proj = identity,
1180 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
1181 requires indirectly_copyable<iterator_t<_Range>, _Out>
1182 constexpr copy_if_result<safe_iterator_t<_Range>, _Out>
1183 copy_if(_Range&& __r, _Out __result, _Pred __pred, _Proj __proj = {})
1190 template<
typename _Iter1,
typename _Iter2>
1191 using swap_ranges_result = mismatch_result<_Iter1, _Iter2>;
1193 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1194 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2>
1195 requires indirectly_swappable<_Iter1, _Iter2>
1196 constexpr swap_ranges_result<_Iter1, _Iter2>
1197 swap_ranges(_Iter1 __first1, _Sent1 __last1,
1198 _Iter2 __first2, _Sent2 __last2)
1200 for (; __first1 != __last1 && __first2 != __last2;
1201 ++__first1, (void)++__first2)
1202 ranges::iter_swap(__first1, __first2);
1206 template<input_range _Range1, input_range _Range2>
1207 requires indirectly_swappable<iterator_t<_Range1>, iterator_t<_Range2>>
1208 constexpr swap_ranges_result<safe_iterator_t<_Range1>,
1209 safe_iterator_t<_Range2>>
1210 swap_ranges(_Range1&& __r1, _Range2&& __r2)
1216 template<
typename _Iter,
typename _Out>
1217 using unary_transform_result = copy_result<_Iter, _Out>;
1219 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1220 weakly_incrementable _Out,
1221 copy_constructible _Fp,
typename _Proj =
identity>
1222 requires indirectly_writable<_Out,
1223 indirect_result_t<_Fp&,
1224 projected<_Iter, _Proj>>>
1225 constexpr unary_transform_result<_Iter, _Out>
1226 transform(_Iter __first1, _Sent __last1, _Out __result,
1227 _Fp __op, _Proj __proj = {})
1229 for (; __first1 != __last1; ++__first1, (void)++__result)
1234 template<input_range _Range, weakly_incrementable _Out,
1235 copy_constructible _Fp,
typename _Proj = identity>
1236 requires indirectly_writable<_Out,
1237 indirect_result_t<_Fp&,
1238 projected<iterator_t<_Range>, _Proj>>>
1239 constexpr unary_transform_result<safe_iterator_t<_Range>, _Out>
1240 transform(_Range&& __r, _Out __result, _Fp __op, _Proj __proj = {})
1247 template<
typename _Iter1,
typename _Iter2,
typename _Out>
1248 struct binary_transform_result
1250 [[no_unique_address]] _Iter1 in1;
1251 [[no_unique_address]] _Iter2 in2;
1252 [[no_unique_address]] _Out out;
1254 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
1255 requires convertible_to<const _Iter1&, _IIter1>
1256 && convertible_to<const _Iter2&, _IIter2>
1257 && convertible_to<const _Out&, _OOut>
1258 operator binary_transform_result<_IIter1, _IIter2, _OOut>() const &
1259 {
return {in1, in2, out}; }
1261 template<
typename _IIter1,
typename _IIter2,
typename _OOut>
1262 requires convertible_to<_Iter1, _IIter1>
1263 && convertible_to<_Iter2, _IIter2>
1264 && convertible_to<_Out, _OOut>
1265 operator binary_transform_result<_IIter1, _IIter2, _OOut>() &&
1269 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
1270 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
1271 weakly_incrementable _Out, copy_constructible _Fp,
1272 typename _Proj1 =
identity,
typename _Proj2 =
identity>
1273 requires indirectly_writable<_Out,
1274 indirect_result_t<_Fp&,
1275 projected<_Iter1, _Proj1>,
1276 projected<_Iter2, _Proj2>>>
1277 constexpr binary_transform_result<_Iter1, _Iter2, _Out>
1278 transform(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
1279 _Out __result, _Fp __binary_op,
1280 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
1282 for (; __first1 != __last1 && __first2 != __last2;
1283 ++__first1, (void)++__first2, ++__result)
1290 template<input_range _Range1, input_range _Range2,
1291 weakly_incrementable _Out, copy_constructible _Fp,
1292 typename _Proj1 = identity,
typename _Proj2 = identity>
1293 requires indirectly_writable<_Out,
1294 indirect_result_t<_Fp&,
1295 projected<iterator_t<_Range1>, _Proj1>,
1296 projected<iterator_t<_Range2>, _Proj2>>>
1297 constexpr binary_transform_result<safe_iterator_t<_Range1>,
1298 safe_iterator_t<_Range2>, _Out>
1299 transform(_Range1&& __r1, _Range2&& __r2, _Out __result,
1300 _Fp __binary_op, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
1308 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1309 typename _Tp1,
typename _Tp2,
typename _Proj =
identity>
1310 requires indirectly_writable<_Iter, const _Tp2&>
1311 && indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>,
1314 replace(_Iter __first, _Sent __last,
1315 const _Tp1& __old_value,
const _Tp2& __new_value,
1318 for (; __first != __last; ++__first)
1320 *__first = __new_value;
1324 template<input_range _Range,
1325 typename _Tp1,
typename _Tp2,
typename _Proj = identity>
1326 requires indirectly_writable<iterator_t<_Range>,
const _Tp2&>
1327 && indirect_binary_predicate<ranges::equal_to,
1328 projected<iterator_t<_Range>, _Proj>,
1330 constexpr safe_iterator_t<_Range>
1331 replace(_Range&& __r,
1332 const _Tp1& __old_value,
const _Tp2& __new_value,
1336 __old_value, __new_value,
std::move(__proj));
1339 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1340 typename _Tp,
typename _Proj =
identity,
1341 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1342 requires indirectly_writable<_Iter, const _Tp&>
1344 replace_if(_Iter __first, _Sent __last,
1345 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
1347 for (; __first != __last; ++__first)
1349 *__first = __new_value;
1353 template<input_range _Range,
typename _Tp,
typename _Proj = identity,
1354 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
1355 requires indirectly_writable<iterator_t<_Range>,
const _Tp&>
1356 constexpr safe_iterator_t<_Range>
1357 replace_if(_Range&& __r,
1358 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
1365 template<
typename _Iter,
typename _Out>
1366 using replace_copy_result = copy_result<_Iter, _Out>;
1368 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1369 typename _Tp1,
typename _Tp2, output_iterator<const _Tp2&> _Out,
1370 typename _Proj =
identity>
1371 requires indirectly_copyable<_Iter, _Out>
1372 && indirect_binary_predicate<ranges::equal_to,
1373 projected<_Iter, _Proj>,
const _Tp1*>
1374 constexpr replace_copy_result<_Iter, _Out>
1375 replace_copy(_Iter __first, _Sent __last, _Out __result,
1376 const _Tp1& __old_value,
const _Tp2& __new_value,
1379 for (; __first != __last; ++__first, (void)++__result)
1381 *__result = __new_value;
1383 *__result = *__first;
1387 template<input_range _Range,
typename _Tp1,
typename _Tp2,
1388 output_iterator<const _Tp2&> _Out,
typename _Proj = identity>
1389 requires indirectly_copyable<iterator_t<_Range>, _Out>
1390 && indirect_binary_predicate<ranges::equal_to,
1391 projected<iterator_t<_Range>, _Proj>,
1393 constexpr replace_copy_result<safe_iterator_t<_Range>, _Out>
1394 replace_copy(_Range&& __r, _Out __result,
1395 const _Tp1& __old_value,
const _Tp2& __new_value,
1403 template<
typename _Iter,
typename _Out>
1404 using replace_copy_if_result = copy_result<_Iter, _Out>;
1406 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1407 typename _Tp, output_iterator<const _Tp&> _Out,
1408 typename _Proj =
identity,
1409 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1410 requires indirectly_copyable<_Iter, _Out>
1411 constexpr replace_copy_if_result<_Iter, _Out>
1412 replace_copy_if(_Iter __first, _Sent __last, _Out __result,
1413 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
1415 for (; __first != __last; ++__first, (void)++__result)
1417 *__result = __new_value;
1419 *__result = *__first;
1423 template<input_range _Range,
1424 typename _Tp, output_iterator<const _Tp&> _Out,
1425 typename _Proj = identity,
1426 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
1427 requires indirectly_copyable<iterator_t<_Range>, _Out>
1428 constexpr replace_copy_if_result<safe_iterator_t<_Range>, _Out>
1429 replace_copy_if(_Range&& __r, _Out __result,
1430 _Pred __pred,
const _Tp& __new_value, _Proj __proj = {})
1437 template<
typename _Tp, output_iterator<const _Tp&> _Out>
1439 fill_n(_Out __first, iter_difference_t<_Out> __n,
const _Tp& __value)
1447 if constexpr (is_pointer_v<_Out> && __is_byte<_Tp>::__value)
1449 __builtin_memset(__first, static_cast<unsigned char>(__value), __n);
1450 return __first + __n;
1452 else if constexpr (is_scalar_v<_Tp>)
1454 const auto __tmp = __value;
1455 for (; __n > 0; --__n, (void)++__first)
1461 for (; __n > 0; --__n, (void)++__first)
1467 template<
typename _Tp,
1468 output_iterator<const _Tp&> _Out, sentinel_for<_Out> _Sent>
1470 fill(_Out __first, _Sent __last,
const _Tp& __value)
1474 if constexpr (sized_sentinel_for<_Sent, _Out>)
1476 const auto __len = __last - __first;
1477 return ranges::fill_n(__first, __len, __value);
1479 else if constexpr (is_scalar_v<_Tp>)
1481 const auto __tmp = __value;
1482 for (; __first != __last; ++__first)
1488 for (; __first != __last; ++__first)
1494 template<
typename _Tp, output_range<const _Tp&> _Range>
1495 constexpr safe_iterator_t<_Range>
1496 fill(_Range&& __r,
const _Tp& __value)
1501 template<input_or_output_iterator _Out, copy_constructible _Fp>
1502 requires invocable<_Fp&>
1503 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
1505 generate_n(_Out __first, iter_difference_t<_Out> __n, _Fp __gen)
1507 for (; __n > 0; --__n, (void)++__first)
1512 template<input_or_output_iterator _Out, sentinel_for<_Out> _Sent,
1513 copy_constructible _Fp>
1514 requires invocable<_Fp&>
1515 && indirectly_writable<_Out, invoke_result_t<_Fp&>>
1517 generate(_Out __first, _Sent __last, _Fp __gen)
1519 for (; __first != __last; ++__first)
1524 template<
typename _Range, copy_constructible _Fp>
1525 requires invocable<_Fp&> && output_range<_Range, invoke_result_t<_Fp&>>
1526 constexpr safe_iterator_t<_Range>
1527 generate(_Range&& __r, _Fp __gen)
1533 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1534 typename _Proj =
identity,
1535 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1536 constexpr subrange<_Iter>
1537 remove_if(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
1539 __first = ranges::find_if(__first, __last, __pred, __proj);
1540 if (__first == __last)
1541 return {__first, __first};
1543 auto __result = __first;
1545 for (; __first != __last; ++__first)
1552 return {__result, __first};
1555 template<forward_range _Range,
typename _Proj = identity,
1556 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
1557 requires permutable<iterator_t<_Range>>
1558 constexpr safe_subrange_t<_Range>
1559 remove_if(_Range&& __r, _Pred __pred, _Proj __proj = {})
1565 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1566 typename _Tp,
typename _Proj =
identity>
1567 requires indirect_binary_predicate<ranges::equal_to,
1568 projected<_Iter, _Proj>,
1570 constexpr subrange<_Iter>
1571 remove(_Iter __first, _Sent __last,
const _Tp& __value, _Proj __proj = {})
1573 auto __pred = [&] (
auto&& __arg) {
1574 return std::forward<decltype(__arg)>(__arg) == __value;
1576 return ranges::remove_if(__first, __last,
1580 template<forward_range _Range,
typename _Tp,
typename _Proj =
identity>
1581 requires permutable<iterator_t<_Range>>
1582 && indirect_binary_predicate<ranges::equal_to,
1583 projected<iterator_t<_Range>, _Proj>,
1585 constexpr safe_subrange_t<_Range>
1586 remove(_Range&& __r,
const _Tp& __value, _Proj __proj = {})
1592 template<
typename _Iter,
typename _Out>
1593 using remove_copy_if_result = copy_result<_Iter, _Out>;
1595 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1596 weakly_incrementable _Out,
typename _Proj =
identity,
1597 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
1598 requires indirectly_copyable<_Iter, _Out>
1599 constexpr remove_copy_if_result<_Iter, _Out>
1600 remove_copy_if(_Iter __first, _Sent __last, _Out __result,
1601 _Pred __pred, _Proj __proj = {})
1603 for (; __first != __last; ++__first)
1606 *__result = *__first;
1612 template<input_range _Range, weakly_incrementable _Out,
1613 typename _Proj = identity,
1614 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
1615 requires indirectly_copyable<iterator_t<_Range>, _Out>
1616 constexpr remove_copy_if_result<safe_iterator_t<_Range>, _Out>
1617 remove_copy_if(_Range&& __r, _Out __result,
1618 _Pred __pred, _Proj __proj = {})
1625 template<
typename _Iter,
typename _Out>
1626 using remove_copy_result = copy_result<_Iter, _Out>;
1628 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1629 weakly_incrementable _Out,
typename _Tp,
typename _Proj =
identity>
1630 requires indirectly_copyable<_Iter, _Out>
1631 && indirect_binary_predicate<ranges::equal_to,
1632 projected<_Iter, _Proj>,
1634 constexpr remove_copy_result<_Iter, _Out>
1635 remove_copy(_Iter __first, _Sent __last, _Out __result,
1636 const _Tp& __value, _Proj __proj = {})
1638 for (; __first != __last; ++__first)
1641 *__result = *__first;
1647 template<input_range _Range, weakly_incrementable _Out,
1648 typename _Tp,
typename _Proj = identity>
1649 requires indirectly_copyable<iterator_t<_Range>, _Out>
1650 && indirect_binary_predicate<ranges::equal_to,
1651 projected<iterator_t<_Range>, _Proj>,
1653 constexpr remove_copy_result<safe_iterator_t<_Range>, _Out>
1654 remove_copy(_Range&& __r, _Out __result,
1655 const _Tp& __value, _Proj __proj = {})
1663 template<permutable _Iter, sentinel_for<_Iter> _Sent,
1664 typename _Proj =
identity,
1665 indirect_equivalence_relation<
1666 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1667 constexpr subrange<_Iter>
1668 unique(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {})
1670 __first = ranges::adjacent_find(__first, __last, __comp, __proj);
1671 if (__first == __last)
1672 return {__first, __first};
1674 auto __dest = __first;
1676 while (++__first != __last)
1681 return {++__dest, __first};
1684 template<forward_range _Range,
typename _Proj = identity,
1685 indirect_equivalence_relation<
1686 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1687 requires permutable<iterator_t<_Range>>
1688 constexpr safe_subrange_t<_Range>
1689 unique(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
1695 template<
typename _Iter,
typename _Out>
1696 using unique_copy_result = copy_result<_Iter, _Out>;
1698 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
1699 weakly_incrementable _Out,
typename _Proj =
identity,
1700 indirect_equivalence_relation<
1701 projected<_Iter, _Proj>> _Comp = ranges::equal_to>
1702 requires indirectly_copyable<_Iter, _Out>
1703 && (forward_iterator<_Iter>
1704 || (input_iterator<_Out>
1705 && same_as<iter_value_t<_Iter>, iter_value_t<_Out>>)
1706 || indirectly_copyable_storable<_Iter, _Out>)
1707 constexpr unique_copy_result<_Iter, _Out>
1708 unique_copy(_Iter __first, _Sent __last, _Out __result,
1709 _Comp __comp = {}, _Proj __proj = {})
1711 if (__first == __last)
1715 if constexpr (forward_iterator<_Iter>)
1717 auto __next = __first;
1718 *__result = *__next;
1719 while (++__next != __last)
1725 *++__result = *__first;
1729 else if constexpr (input_iterator<_Out>
1730 && same_as<iter_value_t<_Iter>, iter_value_t<_Out>>)
1732 *__result = *__first;
1733 while (++__first != __last)
1737 *++__result = *__first;
1742 auto __value = *__first;
1743 *__result = __value;
1744 while (++__first != __last)
1751 *++__result = __value;
1758 template<input_range _Range,
1759 weakly_incrementable _Out,
typename _Proj = identity,
1760 indirect_equivalence_relation<
1761 projected<iterator_t<_Range>, _Proj>> _Comp = ranges::equal_to>
1762 requires indirectly_copyable<iterator_t<_Range>, _Out>
1763 && (forward_iterator<iterator_t<_Range>>
1764 || (input_iterator<_Out>
1765 && same_as<range_value_t<_Range>, iter_value_t<_Out>>)
1766 || indirectly_copyable_storable<iterator_t<_Range>, _Out>)
1767 constexpr unique_copy_result<safe_iterator_t<_Range>, _Out>
1768 unique_copy(_Range&& __r, _Out __result,
1769 _Comp __comp = {}, _Proj __proj = {})
1776 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
1777 requires permutable<_Iter>
1779 reverse(_Iter __first, _Sent __last)
1781 auto __i = ranges::next(__first, __last);
1784 if constexpr (random_access_iterator<_Iter>)
1786 if (__first != __last)
1789 while (__first < __tail)
1791 ranges::iter_swap(__first, __tail);
1801 if (__first == __tail || __first == --__tail)
1805 ranges::iter_swap(__first, __tail);
1812 template<b
idirectional_range _Range>
1813 requires permutable<iterator_t<_Range>>
1814 constexpr safe_iterator_t<_Range>
1815 reverse(_Range&& __r)
1820 template<
typename _Iter,
typename _Out>
1821 using reverse_copy_result = copy_result<_Iter, _Out>;
1823 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
1824 weakly_incrementable _Out>
1825 requires indirectly_copyable<_Iter, _Out>
1826 constexpr reverse_copy_result<_Iter, _Out>
1827 reverse_copy(_Iter __first, _Sent __last, _Out __result)
1829 auto __i = ranges::next(__first, __last);
1831 while (__first != __tail)
1834 *__result = *__tail;
1837 return {__i, __result};
1840 template<b
idirectional_range _Range, weakly_incrementable _Out>
1841 requires indirectly_copyable<iterator_t<_Range>, _Out>
1842 constexpr reverse_copy_result<safe_iterator_t<_Range>, _Out>
1843 reverse_copy(_Range&& __r, _Out __result)
1849 template<permutable _Iter, sentinel_for<_Iter> _Sent>
1850 constexpr subrange<_Iter>
1851 rotate(_Iter __first, _Iter __middle, _Sent __last)
1853 auto __lasti = ranges::next(__first, __last);
1854 if (__first == __middle)
1855 return {__lasti, __lasti};
1856 if (__last == __middle)
1859 if constexpr (random_access_iterator<_Iter>)
1861 auto __n = __lasti - __first;
1862 auto __k = __middle - __first;
1864 if (__k == __n - __k)
1866 ranges::swap_ranges(__first, __middle, __middle, __middle + __k);
1871 auto __ret = __first + (__lasti - __middle);
1875 if (__k < __n - __k)
1879 if constexpr (__is_pod(iter_value_t<_Iter>))
1887 auto __q = __p + __k;
1888 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1890 ranges::iter_swap(__p, __q);
1897 ranges::swap(__n, __k);
1905 if constexpr (__is_pod(iter_value_t<_Iter>))
1913 auto __q = __p + __n;
1915 for (decltype(__n) __i = 0; __i < __n - __k; ++ __i)
1919 ranges::iter_swap(__p, __q);
1924 std::swap(__n, __k);
1928 else if constexpr (bidirectional_iterator<_Iter>)
1930 auto __tail = __lasti;
1932 ranges::reverse(__first, __middle);
1933 ranges::reverse(__middle, __tail);
1935 while (__first != __middle && __middle != __tail)
1937 ranges::iter_swap(__first, --__tail);
1941 if (__first == __middle)
1943 ranges::reverse(__middle, __tail);
1948 ranges::reverse(__first, __middle);
1954 auto __first2 = __middle;
1957 ranges::iter_swap(__first, __first2);
1960 if (__first == __middle)
1961 __middle = __first2;
1962 }
while (__first2 != __last);
1964 auto __ret = __first;
1966 __first2 = __middle;
1968 while (__first2 != __last)
1970 ranges::iter_swap(__first, __first2);
1973 if (__first == __middle)
1974 __middle = __first2;
1975 else if (__first2 == __last)
1976 __first2 = __middle;
1982 template<forward_range _Range>
1983 requires permutable<iterator_t<_Range>>
1984 constexpr safe_subrange_t<_Range>
1985 rotate(_Range&& __r, iterator_t<_Range> __middle)
1992 template<
typename _Iter,
typename _Out>
1993 using rotate_copy_result = copy_result<_Iter, _Out>;
1995 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
1996 weakly_incrementable _Out>
1997 requires indirectly_copyable<_Iter, _Out>
1998 constexpr rotate_copy_result<_Iter, _Out>
1999 rotate_copy(_Iter __first, _Iter __middle, _Sent __last, _Out __result)
2001 auto __copy1 = ranges::copy(__middle,
2004 auto __copy2 = ranges::copy(
std::move(__first),
2010 template<forward_range _Range, weakly_incrementable _Out>
2011 requires indirectly_copyable<iterator_t<_Range>, _Out>
2012 constexpr rotate_copy_result<safe_iterator_t<_Range>, _Out>
2013 rotate_copy(_Range&& __r, iterator_t<_Range> __middle, _Out __result)
2021 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
2022 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2024 requires permutable<_Iter>
2025 && uniform_random_bit_generator<remove_reference_t<_Gen>>
2027 shuffle(_Iter __first, _Sent __last, _Gen&& __g)
2029 auto __lasti = ranges::next(__first, __last);
2034 template<random_access_range _Range,
typename _Gen>
2035 requires permutable<iterator_t<_Range>>
2036 && uniform_random_bit_generator<remove_reference_t<_Gen>>
2037 safe_iterator_t<_Range>
2038 shuffle(_Range&& __r, _Gen&& __g)
2041 std::forward<_Gen>(__g));
2045 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2046 typename _Comp = ranges::less,
typename _Proj =
identity>
2047 requires sortable<_Iter, _Comp, _Proj>
2049 push_heap(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {})
2051 auto __lasti = ranges::next(__first, __last);
2053 __detail::__make_comp_proj(__comp, __proj));
2057 template<random_access_range _Range,
2058 typename _Comp = ranges::less,
typename _Proj = identity>
2059 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2060 constexpr safe_iterator_t<_Range>
2061 push_heap(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
2067 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2068 typename _Comp = ranges::less,
typename _Proj =
identity>
2069 requires sortable<_Iter, _Comp, _Proj>
2071 pop_heap(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {})
2073 auto __lasti = ranges::next(__first, __last);
2075 __detail::__make_comp_proj(__comp, __proj));
2079 template<random_access_range _Range,
2080 typename _Comp = ranges::less,
typename _Proj = identity>
2081 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2082 constexpr safe_iterator_t<_Range>
2083 pop_heap(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
2089 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2090 typename _Comp = ranges::less,
typename _Proj =
identity>
2091 requires sortable<_Iter, _Comp, _Proj>
2093 make_heap(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {})
2095 auto __lasti = ranges::next(__first, __last);
2097 __detail::__make_comp_proj(__comp, __proj));
2101 template<random_access_range _Range,
2102 typename _Comp = ranges::less,
typename _Proj = identity>
2103 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2104 constexpr safe_iterator_t<_Range>
2105 make_heap(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
2111 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2112 typename _Comp = ranges::less,
typename _Proj =
identity>
2113 requires sortable<_Iter, _Comp, _Proj>
2115 sort_heap(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {})
2117 auto __lasti = ranges::next(__first, __last);
2119 __detail::__make_comp_proj(__comp, __proj));
2123 template<random_access_range _Range,
2124 typename _Comp = ranges::less,
typename _Proj = identity>
2125 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2126 constexpr safe_iterator_t<_Range>
2127 sort_heap(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
2133 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2134 typename _Proj =
identity,
2135 indirect_strict_weak_order<projected<_Iter, _Proj>>
2136 _Comp = ranges::less>
2138 is_heap_until(_Iter __first, _Sent __last,
2139 _Comp __comp = {}, _Proj __proj = {})
2142 iter_difference_t<_Iter> __parent = 0, __child = 1;
2143 for (; __child < __n; ++__child)
2147 return __first + __child;
2148 else if ((__child & 1) == 0)
2151 return __first + __n;
2154 template<random_access_range _Range,
2155 typename _Proj = identity,
2156 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2157 _Comp = ranges::less>
2158 constexpr safe_iterator_t<_Range>
2159 is_heap_until(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
2165 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2166 typename _Proj =
identity,
2167 indirect_strict_weak_order<projected<_Iter, _Proj>>
2168 _Comp = ranges::less>
2170 is_heap(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {})
2173 == ranges::is_heap_until(__first, __last,
2178 template<random_access_range _Range,
2179 typename _Proj = identity,
2180 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2181 _Comp = ranges::less>
2183 is_heap(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
2189 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2190 typename _Comp = ranges::less,
typename _Proj =
identity>
2191 requires sortable<_Iter, _Comp, _Proj>
2193 sort(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {})
2195 auto __lasti = ranges::next(__first, __last);
2197 __detail::__make_comp_proj(__comp, __proj));
2201 template<random_access_range _Range,
2202 typename _Comp = ranges::less,
typename _Proj = identity>
2203 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2204 constexpr safe_iterator_t<_Range>
2205 sort(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
2211 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2212 typename _Comp = ranges::less,
typename _Proj =
identity>
2213 requires sortable<_Iter, _Comp, _Proj>
2215 stable_sort(_Iter __first, _Sent __last,
2216 _Comp __comp = {}, _Proj __proj = {})
2218 auto __lasti = ranges::next(__first, __last);
2220 __detail::__make_comp_proj(__comp, __proj));
2224 template<random_access_range _Range,
2225 typename _Comp = ranges::less,
typename _Proj = identity>
2226 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2227 safe_iterator_t<_Range>
2228 stable_sort(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
2234 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2235 typename _Comp = ranges::less,
typename _Proj =
identity>
2236 requires sortable<_Iter, _Comp, _Proj>
2238 partial_sort(_Iter __first, _Iter __middle, _Sent __last,
2239 _Comp __comp = {}, _Proj __proj = {})
2241 if (__first == __middle)
2242 return ranges::next(__first, __last);
2244 ranges::make_heap(__first, __middle, __comp, __proj);
2245 auto __i = __middle;
2246 for (; __i != __last; ++__i)
2251 ranges::pop_heap(__first, __middle, __comp, __proj);
2252 ranges::iter_swap(__middle-1, __i);
2253 ranges::push_heap(__first, __middle, __comp, __proj);
2255 ranges::sort_heap(__first, __middle, __comp, __proj);
2260 template<random_access_range _Range,
2261 typename _Comp = ranges::less,
typename _Proj = identity>
2262 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2263 constexpr safe_iterator_t<_Range>
2264 partial_sort(_Range&& __r, iterator_t<_Range> __middle,
2265 _Comp __comp = {}, _Proj __proj = {})
2273 template<
typename _Iter,
typename _Out>
2274 using partial_sort_copy_result = copy_result<_Iter, _Out>;
2276 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2277 random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2278 typename _Comp = ranges::less,
2279 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2280 requires indirectly_copyable<_Iter1, _Iter2>
2281 && sortable<_Iter2, _Comp, _Proj2>
2282 && indirect_strict_weak_order<_Comp,
2283 projected<_Iter1, _Proj1>,
2284 projected<_Iter2, _Proj2>>
2285 constexpr partial_sort_copy_result<_Iter1, _Iter2>
2286 partial_sort_copy(_Iter1 __first, _Sent1 __last,
2287 _Iter2 __result_first, _Sent2 __result_last,
2289 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
2291 if (__result_first == __result_last)
2294 auto __lasti = ranges::next(
std::move(__first),
2299 auto __result_real_last = __result_first;
2300 while (__first != __last && __result_real_last != __result_last)
2302 *__result_real_last = *__first;
2303 ++__result_real_last;
2307 ranges::make_heap(__result_first, __result_real_last, __comp, __proj2);
2308 for (; __first != __last; ++__first)
2313 ranges::pop_heap(__result_first, __result_real_last,
2315 *(__result_real_last-1) = *__first;
2316 ranges::push_heap(__result_first, __result_real_last,
2319 ranges::sort_heap(__result_first, __result_real_last, __comp, __proj2);
2324 template<input_range _Range1, random_access_range _Range2,
2325 typename _Comp = ranges::less,
2326 typename _Proj1 = identity,
typename _Proj2 = identity>
2327 requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>>
2328 && sortable<iterator_t<_Range2>, _Comp, _Proj2>
2329 && indirect_strict_weak_order<_Comp,
2330 projected<iterator_t<_Range1>, _Proj1>,
2331 projected<iterator_t<_Range2>, _Proj2>>
2332 constexpr partial_sort_copy_result<safe_iterator_t<_Range1>,
2333 safe_iterator_t<_Range2>>
2334 partial_sort_copy(_Range1&& __r, _Range2&& __out, _Comp __comp = {},
2335 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
2343 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2344 typename _Proj =
identity,
2345 indirect_strict_weak_order<projected<_Iter, _Proj>>
2346 _Comp = ranges::less>
2348 is_sorted_until(_Iter __first, _Sent __last,
2349 _Comp __comp = {}, _Proj __proj = {})
2351 if (__first == __last)
2354 auto __next = __first;
2355 for (++__next; __next != __last; __first = __next, (void)++__next)
2363 template<forward_range _Range,
typename _Proj = identity,
2364 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2365 _Comp = ranges::less>
2366 constexpr safe_iterator_t<_Range>
2367 is_sorted_until(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
2373 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2374 typename _Proj =
identity,
2375 indirect_strict_weak_order<projected<_Iter, _Proj>>
2376 _Comp = ranges::less>
2378 is_sorted(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {})
2380 if (__first == __last)
2383 auto __next = __first;
2384 for (++__next; __next != __last; __first = __next, (void)++__next)
2392 template<forward_range _Range,
typename _Proj = identity,
2393 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
2394 _Comp = ranges::less>
2396 is_sorted(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
2402 template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
2403 typename _Comp = ranges::less,
typename _Proj =
identity>
2404 requires sortable<_Iter, _Comp, _Proj>
2406 nth_element(_Iter __first, _Iter __nth, _Sent __last,
2407 _Comp __comp = {}, _Proj __proj = {})
2409 auto __lasti = ranges::next(__first, __last);
2411 __detail::__make_comp_proj(__comp, __proj));
2415 template<random_access_range _Range,
2416 typename _Comp = ranges::less,
typename _Proj = identity>
2417 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2418 constexpr safe_iterator_t<_Range>
2419 nth_element(_Range&& __r, iterator_t<_Range> __nth,
2420 _Comp __comp = {}, _Proj __proj = {})
2427 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2428 typename _Tp,
typename _Proj =
identity,
2429 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2430 _Comp = ranges::less>
2432 lower_bound(_Iter __first, _Sent __last,
2433 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
2439 auto __half = __len / 2;
2440 auto __middle = __first;
2446 __len = __len - __half - 1;
2454 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2455 indirect_strict_weak_order<
const _Tp*,
2456 projected<iterator_t<_Range>, _Proj>>
2457 _Comp = ranges::less>
2458 constexpr safe_iterator_t<_Range>
2459 lower_bound(_Range&& __r,
2460 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
2467 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2468 typename _Tp,
typename _Proj =
identity,
2469 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2470 _Comp = ranges::less>
2472 upper_bound(_Iter __first, _Sent __last,
2473 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
2479 auto __half = __len / 2;
2480 auto __middle = __first;
2488 __len = __len - __half - 1;
2494 template<forward_range _Range,
typename _Tp,
typename _Proj = identity,
2495 indirect_strict_weak_order<
const _Tp*,
2496 projected<iterator_t<_Range>, _Proj>>
2497 _Comp = ranges::less>
2498 constexpr safe_iterator_t<_Range>
2499 upper_bound(_Range&& __r,
2500 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
2507 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2508 typename _Tp,
typename _Proj =
identity,
2509 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2510 _Comp = ranges::less>
2511 constexpr subrange<_Iter>
2512 equal_range(_Iter __first, _Sent __last,
2513 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
2519 auto __half = __len / 2;
2520 auto __middle = __first;
2528 __len = __len - __half - 1;
2537 = ranges::lower_bound(__first, __middle,
2538 __value, __comp, __proj);
2541 = ranges::upper_bound(++__middle, __first,
2542 __value, __comp, __proj);
2543 return {__left, __right};
2546 return {__first, __first};
2549 template<forward_range _Range,
2550 typename _Tp,
typename _Proj = identity,
2551 indirect_strict_weak_order<
const _Tp*,
2552 projected<iterator_t<_Range>, _Proj>>
2553 _Comp = ranges::less>
2554 constexpr safe_subrange_t<_Range>
2555 equal_range(_Range&& __r,
const _Tp& __value,
2556 _Comp __comp = {}, _Proj __proj = {})
2563 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2564 typename _Tp,
typename _Proj =
identity,
2565 indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>>
2566 _Comp = ranges::less>
2568 binary_search(_Iter __first, _Sent __last,
2569 const _Tp& __value, _Comp __comp = {}, _Proj __proj = {})
2571 auto __i = ranges::lower_bound(__first, __last, __value, __comp, __proj);
2577 template<forward_range _Range,
2578 typename _Tp,
typename _Proj = identity,
2579 indirect_strict_weak_order<
const _Tp*,
2580 projected<iterator_t<_Range>, _Proj>>
2581 _Comp = ranges::less>
2583 binary_search(_Range&& __r,
const _Tp& __value, _Comp __comp = {},
2591 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2592 typename _Proj =
identity,
2593 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2595 is_partitioned(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
2597 __first = ranges::find_if_not(
std::move(__first), __last, __pred, __proj);
2598 if (__first == __last)
2605 template<input_range _Range,
typename _Proj = identity,
2606 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
2608 is_partitioned(_Range&& __r, _Pred __pred, _Proj __proj = {})
2614 template<permutable _Iter, sentinel_for<_Iter> _Sent,
2615 typename _Proj =
identity,
2616 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2617 constexpr subrange<_Iter>
2618 partition(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
2620 if constexpr (bidirectional_iterator<_Iter>)
2622 auto __lasti = ranges::next(__first, __last);
2623 auto __tail = __lasti;
2627 if (__first == __tail)
2635 if (__first == __tail)
2642 ranges::iter_swap(__first, __tail);
2648 if (__first == __last)
2652 if (++__first == __last)
2655 auto __next = __first;
2656 while (++__next != __last)
2659 ranges::iter_swap(__first, __next);
2667 template<forward_range _Range,
typename _Proj = identity,
2668 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
2669 requires permutable<iterator_t<_Range>>
2670 constexpr safe_subrange_t<_Range>
2671 partition(_Range&& __r, _Pred __pred, _Proj __proj = {})
2677 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2678 typename _Proj =
identity,
2679 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2680 requires permutable<_Iter>
2682 stable_partition(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {})
2684 auto __lasti = ranges::next(__first, __last);
2687 __detail::__make_pred_proj(__pred, __proj));
2691 template<bidirectional_range _Range,
typename _Proj = identity,
2692 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
2693 requires permutable<iterator_t<_Range>>
2694 safe_subrange_t<_Range>
2695 stable_partition(_Range&& __r, _Pred __pred, _Proj __proj = {})
2701 template<
typename _Iter,
typename _Out1,
typename _O2>
2702 struct partition_copy_result
2704 [[no_unique_address]] _Iter in;
2705 [[no_unique_address]] _Out1 out1;
2706 [[no_unique_address]] _O2 out2;
2708 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2709 requires convertible_to<const _Iter&, _IIter>
2710 && convertible_to<const _Out1&, _OOut1>
2711 && convertible_to<const _O2&, _OOut2>
2712 operator partition_copy_result<_IIter, _OOut1, _OOut2>() const &
2713 {
return {in, out1, out2}; }
2715 template<
typename _IIter,
typename _OOut1,
typename _OOut2>
2716 requires convertible_to<_Iter, _IIter>
2717 && convertible_to<_Out1, _OOut1>
2718 && convertible_to<_O2, _OOut2>
2719 operator partition_copy_result<_IIter, _OOut1, _OOut2>() &&
2723 template<input_iterator _Iter, sentinel_for<_Iter> _Sent,
2724 weakly_incrementable _Out1, weakly_incrementable _O2,
2725 typename _Proj =
identity,
2726 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2727 requires indirectly_copyable<_Iter, _Out1>
2728 && indirectly_copyable<_Iter, _O2>
2729 constexpr partition_copy_result<_Iter, _Out1, _O2>
2730 partition_copy(_Iter __first, _Sent __last,
2731 _Out1 __out_true, _O2 __out_false,
2732 _Pred __pred, _Proj __proj = {})
2734 for (; __first != __last; ++__first)
2737 *__out_true = *__first;
2742 *__out_false = *__first;
2749 template<input_range _Range, weakly_incrementable _Out1,
2750 weakly_incrementable _O2,
2751 typename _Proj = identity,
2752 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
2753 requires indirectly_copyable<iterator_t<_Range>, _Out1>
2754 && indirectly_copyable<iterator_t<_Range>, _O2>
2755 constexpr partition_copy_result<safe_iterator_t<_Range>, _Out1, _O2>
2756 partition_copy(_Range&& __r, _Out1 out_true, _O2 out_false,
2757 _Pred __pred, _Proj __proj = {})
2764 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
2765 typename _Proj =
identity,
2766 indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
2768 partition_point(_Iter __first, _Sent __last,
2769 _Pred __pred, _Proj __proj = {})
2775 auto __half = __len / 2;
2776 auto __middle = __first;
2782 __len = __len - __half - 1;
2790 template<forward_range _Range,
typename _Proj = identity,
2791 indirect_unary_predicate<projected<iterator_t<_Range>, _Proj>> _Pred>
2792 constexpr safe_iterator_t<_Range>
2793 partition_point(_Range&& __r, _Pred __pred, _Proj __proj = {})
2799 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2800 using merge_result = binary_transform_result<_Iter1, _Iter2, _Out>;
2802 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2803 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2804 weakly_incrementable _Out,
typename _Comp = ranges::less,
2805 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2806 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2807 constexpr merge_result<_Iter1, _Iter2, _Out>
2808 merge(_Iter1 __first1, _Sent1 __last1,
2809 _Iter2 __first2, _Sent2 __last2, _Out __result,
2810 _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
2812 while (__first1 != __last1 && __first2 != __last2)
2818 *__result = *__first2;
2823 *__result = *__first1;
2836 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2837 typename _Comp = ranges::less,
2838 typename _Proj1 = identity,
typename _Proj2 = identity>
2839 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2840 _Comp, _Proj1, _Proj2>
2841 constexpr merge_result<safe_iterator_t<_Range1>,
2842 safe_iterator_t<_Range2>,
2844 merge(_Range1&& __r1, _Range2&& __r2, _Out __result,
2845 _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
2853 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
2854 typename _Comp = ranges::less,
2855 typename _Proj =
identity>
2856 requires sortable<_Iter, _Comp, _Proj>
2858 inplace_merge(_Iter __first, _Iter __middle, _Sent __last,
2859 _Comp __comp = {}, _Proj __proj = {})
2861 auto __lasti = ranges::next(__first, __last);
2863 __detail::__make_comp_proj(__comp, __proj));
2867 template<bidirectional_range _Range,
2868 typename _Comp = ranges::less,
typename _Proj = identity>
2869 requires sortable<iterator_t<_Range>, _Comp, _Proj>
2870 safe_iterator_t<_Range>
2871 inplace_merge(_Range&& __r, iterator_t<_Range> __middle,
2872 _Comp __comp = {}, _Proj __proj = {})
2879 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2880 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2881 typename _Proj1 =
identity,
typename _Proj2 =
identity,
2882 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
2883 projected<_Iter2, _Proj2>>
2884 _Comp = ranges::less>
2886 includes(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
2887 _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
2889 while (__first1 != __last1 && __first2 != __last2)
2904 return __first2 == __last2;
2907 template<input_range _Range1, input_range _Range2,
typename _Proj1 = identity,
2908 typename _Proj2 = identity,
2909 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
2910 projected<iterator_t<_Range2>, _Proj2>>
2911 _Comp = ranges::less>
2913 includes(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
2914 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
2922 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2923 using set_union_result = binary_transform_result<_Iter1, _Iter2, _Out>;
2925 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2926 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2927 weakly_incrementable _Out,
typename _Comp = ranges::less,
2928 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2929 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2930 constexpr set_union_result<_Iter1, _Iter2, _Out>
2931 set_union(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2,
2932 _Out __result, _Comp __comp = {},
2933 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
2935 while (__first1 != __last1 && __first2 != __last2)
2941 *__result = *__first1;
2948 *__result = *__first2;
2953 *__result = *__first1;
2967 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
2968 typename _Comp = ranges::less,
2969 typename _Proj1 = identity,
typename _Proj2 = identity>
2970 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
2971 _Comp, _Proj1, _Proj2>
2972 constexpr set_union_result<safe_iterator_t<_Range1>,
2973 safe_iterator_t<_Range2>, _Out>
2974 set_union(_Range1&& __r1, _Range2&& __r2, _Out __result, _Comp __comp = {},
2975 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
2983 template<
typename _Iter1,
typename _Iter2,
typename _Out>
2984 using set_intersection_result = binary_transform_result<_Iter1, _Iter2, _Out>;
2986 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
2987 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
2988 weakly_incrementable _Out,
typename _Comp = ranges::less,
2989 typename _Proj1 =
identity,
typename _Proj2 =
identity>
2990 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
2991 constexpr set_intersection_result<_Iter1, _Iter2, _Out>
2992 set_intersection(_Iter1 __first1, _Sent1 __last1,
2993 _Iter2 __first2, _Sent2 __last2, _Out __result,
2995 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
2997 while (__first1 != __last1 && __first2 != __last2)
3008 *__result = *__first1;
3019 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3020 typename _Comp = ranges::less,
3021 typename _Proj1 = identity,
typename _Proj2 = identity>
3022 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3023 _Comp, _Proj1, _Proj2>
3024 constexpr set_intersection_result<safe_iterator_t<_Range1>,
3025 safe_iterator_t<_Range2>, _Out>
3026 set_intersection(_Range1&& __r1, _Range2&& __r2, _Out __result,
3027 _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
3035 template<
typename _Iter,
typename _Out>
3036 using set_difference_result = copy_result<_Iter, _Out>;
3038 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3039 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3040 weakly_incrementable _Out,
typename _Comp = ranges::less,
3041 typename _Proj1 =
identity,
typename _Proj2 =
identity>
3042 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
3043 constexpr set_difference_result<_Iter1, _Out>
3044 set_difference(_Iter1 __first1, _Sent1 __last1,
3045 _Iter2 __first2, _Sent2 __last2, _Out __result,
3046 _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
3048 while (__first1 != __last1 && __first2 != __last2)
3053 *__result = *__first1;
3070 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3071 typename _Comp = ranges::less,
3072 typename _Proj1 = identity,
typename _Proj2 = identity>
3073 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3074 _Comp, _Proj1, _Proj2>
3075 constexpr set_difference_result<safe_iterator_t<_Range1>, _Out>
3076 set_difference(_Range1&& __r1, _Range2&& __r2, _Out __result,
3077 _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
3085 template<
typename _Iter1,
typename _Iter2,
typename _Out>
3086 using set_symmetric_difference_result
3087 = binary_transform_result<_Iter1, _Iter2, _Out>;
3089 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3090 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3091 weakly_incrementable _Out,
typename _Comp = ranges::less,
3092 typename _Proj1 =
identity,
typename _Proj2 =
identity>
3093 requires mergeable<_Iter1, _Iter2, _Out, _Comp, _Proj1, _Proj2>
3094 constexpr set_symmetric_difference_result<_Iter1, _Iter2, _Out>
3095 set_symmetric_difference(_Iter1 __first1, _Sent1 __last1,
3096 _Iter2 __first2, _Sent2 __last2,
3097 _Out __result, _Comp __comp = {},
3098 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
3100 while (__first1 != __last1 && __first2 != __last2)
3105 *__result = *__first1;
3113 *__result = *__first2;
3130 template<input_range _Range1, input_range _Range2, weakly_incrementable _Out,
3131 typename _Comp = ranges::less,
3132 typename _Proj1 = identity,
typename _Proj2 = identity>
3133 requires mergeable<iterator_t<_Range1>, iterator_t<_Range2>, _Out,
3134 _Comp, _Proj1, _Proj2>
3135 constexpr set_symmetric_difference_result<safe_iterator_t<_Range1>,
3136 safe_iterator_t<_Range2>,
3138 set_symmetric_difference(_Range1&& __r1, _Range2&& __r2, _Out __result,
3140 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
3142 return (ranges::set_symmetric_difference
3149 template<
typename _Tp,
typename _Proj = identity,
3150 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3151 _Comp = ranges::less>
3152 constexpr
const _Tp&
3153 min(
const _Tp& __a,
const _Tp& __b, _Comp __comp = {}, _Proj __proj = {})
3163 template<input_range _Range,
typename _Proj = identity,
3164 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3165 _Comp = ranges::less>
3166 requires indirectly_copyable_storable<iterator_t<_Range>,
3167 range_value_t<_Range>*>
3168 constexpr range_value_t<_Range>
3169 min(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
3173 __glibcxx_assert(__first != __last);
3174 auto __result = *__first;
3175 while (++__first != __last)
3177 auto __tmp = *__first;
3186 template<copyable _Tp,
typename _Proj = identity,
3187 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3188 _Comp = ranges::less>
3190 min(initializer_list<_Tp> __r, _Comp __comp = {}, _Proj __proj = {})
3196 template<
typename _Tp,
typename _Proj = identity,
3197 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3198 _Comp = ranges::less>
3199 constexpr
const _Tp&
3200 max(
const _Tp& __a,
const _Tp& __b, _Comp __comp = {}, _Proj __proj = {})
3210 template<input_range _Range,
typename _Proj = identity,
3211 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3212 _Comp = ranges::less>
3213 requires indirectly_copyable_storable<iterator_t<_Range>,
3214 range_value_t<_Range>*>
3215 constexpr range_value_t<_Range>
3216 max(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
3220 __glibcxx_assert(__first != __last);
3221 auto __result = *__first;
3222 while (++__first != __last)
3224 auto __tmp = *__first;
3233 template<copyable _Tp,
typename _Proj = identity,
3234 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3235 _Comp = ranges::less>
3237 max(initializer_list<_Tp> __r, _Comp __comp = {}, _Proj __proj = {})
3243 template<
typename _Tp>
3244 struct minmax_result
3246 [[no_unique_address]] _Tp
min;
3247 [[no_unique_address]] _Tp
max;
3249 template<
typename _Tp2>
3250 requires convertible_to<const _Tp&, _Tp2>
3251 operator minmax_result<_Tp2>() const &
3254 template<
typename _Tp2>
3255 requires convertible_to<_Tp, _Tp2>
3256 operator minmax_result<_Tp2>() &&
3260 template<
typename _Tp,
typename _Proj = identity,
3261 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3262 _Comp = ranges::less>
3263 constexpr minmax_result<const _Tp&>
3264 minmax(
const _Tp& __a,
const _Tp& __b, _Comp __comp = {}, _Proj __proj = {})
3274 template<input_range _Range,
typename _Proj = identity,
3275 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3276 _Comp = ranges::less>
3277 requires indirectly_copyable_storable<iterator_t<_Range>,
3278 range_value_t<_Range>*>
3279 constexpr minmax_result<range_value_t<_Range>>
3280 minmax(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
3284 __glibcxx_assert(__first != __last);
3285 minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
3286 while (++__first != __last)
3288 auto __tmp = *__first;
3301 template<copyable _Tp,
typename _Proj = identity,
3302 indirect_strict_weak_order<projected<const _Tp*, _Proj>>
3303 _Comp = ranges::less>
3304 constexpr minmax_result<_Tp>
3305 minmax(initializer_list<_Tp> __r, _Comp __comp = {}, _Proj __proj = {})
3311 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3312 typename _Proj =
identity,
3313 indirect_strict_weak_order<projected<_Iter, _Proj>>
3314 _Comp = ranges::less>
3316 min_element(_Iter __first, _Sent __last,
3317 _Comp __comp = {}, _Proj __proj = {})
3319 if (__first == __last)
3323 while (++__i != __last)
3333 template<forward_range _Range,
typename _Proj = identity,
3334 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3335 _Comp = ranges::less>
3336 constexpr safe_iterator_t<_Range>
3337 min_element(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
3343 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3344 typename _Proj =
identity,
3345 indirect_strict_weak_order<projected<_Iter, _Proj>>
3346 _Comp = ranges::less>
3348 max_element(_Iter __first, _Sent __last,
3349 _Comp __comp = {}, _Proj __proj = {})
3351 if (__first == __last)
3355 while (++__i != __last)
3365 template<forward_range _Range,
typename _Proj = identity,
3366 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3367 _Comp = ranges::less>
3368 constexpr safe_iterator_t<_Range>
3369 max_element(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
3375 template<
typename _Iter>
3376 using minmax_element_result = minmax_result<_Iter>;
3378 template<forward_iterator _Iter, sentinel_for<_Iter> _Sent,
3379 typename _Proj =
identity,
3380 indirect_strict_weak_order<projected<_Iter, _Proj>>
3381 _Comp = ranges::less>
3382 constexpr minmax_element_result<_Iter>
3383 minmax_element(_Iter __first, _Sent __last,
3384 _Comp __comp = {}, _Proj __proj = {})
3386 if (__first == __last)
3387 return {__first, __first};
3389 minmax_element_result<_Iter> __result = {__first, __first};
3391 while (++__i != __last)
3405 template<forward_range _Range,
typename _Proj = identity,
3406 indirect_strict_weak_order<projected<iterator_t<_Range>, _Proj>>
3407 _Comp = ranges::less>
3408 constexpr minmax_element_result<safe_iterator_t<_Range>>
3409 minmax_element(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
3415 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3416 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3417 typename _Proj1,
typename _Proj2,
3418 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3419 projected<_Iter2, _Proj2>> _Comp>
3421 __lexicographical_compare(_Iter1 __first1, _Sent1 __last1,
3422 _Iter2 __first2, _Sent2 __last2,
3423 _Comp __comp, _Proj1 __proj1, _Proj2 __proj2)
3425 constexpr
bool __sized_iters
3426 = (sized_sentinel_for<_Sent1, _Iter1>
3427 && sized_sentinel_for<_Sent2, _Iter2>);
3428 if constexpr (__sized_iters)
3433 using _ValueType1 = iter_value_t<_Iter1>;
3434 using _ValueType2 = iter_value_t<_Iter2>;
3435 constexpr
bool __use_memcmp
3436 = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>)
3437 && is_same_v<_ValueType1, _ValueType2>
3438 && is_pointer_v<_Iter1>
3439 && is_pointer_v<_Iter2>
3440 && (is_same_v<_Comp, ranges::less>
3441 || is_same_v<_Comp, ranges::greater>)
3442 && is_same_v<_Proj1, identity>
3443 && is_same_v<_Proj2, identity>);
3444 if constexpr (__use_memcmp)
3446 if (
const auto __len =
std::min(__d1, __d2))
3448 const auto __c = std::__memcmp(__first1, __first2, __len);
3449 if constexpr (is_same_v<_Comp, ranges::less>)
3456 else if constexpr (is_same_v<_Comp, ranges::greater>)
3464 __builtin_unreachable();
3466 return (__last1 - __first1 < __last2 - __first2);
3470 for (; __first1 != __last1 && __first2 != __last2;
3471 ++__first1, (void) ++__first2)
3482 return __first1 == __last1 && __first2 != __last2;
3485 template<input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
3486 input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
3487 typename _Proj1 =
identity,
typename _Proj2 =
identity,
3488 indirect_strict_weak_order<projected<_Iter1, _Proj1>,
3489 projected<_Iter2, _Proj2>>
3490 _Comp = ranges::less>
3492 lexicographical_compare(_Iter1 __first1, _Sent1 __last1,
3493 _Iter2 __first2, _Sent2 __last2,
3495 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
3497 return (ranges::__lexicographical_compare
3498 (std::__niter_base(
std::move(__first1)),
3506 template<input_range _Range1, input_range _Range2,
typename _Proj1 = identity,
3507 typename _Proj2 = identity,
3508 indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
3509 projected<iterator_t<_Range2>, _Proj2>>
3510 _Comp = ranges::less>
3512 lexicographical_compare(_Range1&& __r1, _Range2&& __r2, _Comp __comp = {},
3513 _Proj1 __proj1 = {}, _Proj2 __proj2 = {})
3515 return (ranges::lexicographical_compare
3522 template<
typename _Iter>
3523 struct next_permutation_result
3529 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3530 typename _Comp = ranges::less,
typename _Proj =
identity>
3531 requires sortable<_Iter, _Comp, _Proj>
3532 constexpr next_permutation_result<_Iter>
3533 next_permutation(_Iter __first, _Sent __last,
3534 _Comp __comp = {}, _Proj __proj = {})
3536 if (__first == __last)
3544 auto __lasti = ranges::next(__first, __last);
3561 ranges::iter_swap(__i, __j);
3562 ranges::reverse(__ii, __last);
3567 ranges::reverse(__first, __last);
3573 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3574 typename _Proj = identity>
3575 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3576 constexpr next_permutation_result<safe_iterator_t<_Range>>
3577 next_permutation(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
3583 template<
typename _Iter>
3584 using prev_permutation_result = next_permutation_result<_Iter>;
3586 template<b
idirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
3587 typename _Comp = ranges::less,
typename _Proj =
identity>
3588 requires sortable<_Iter, _Comp, _Proj>
3589 constexpr prev_permutation_result<_Iter>
3590 prev_permutation(_Iter __first, _Sent __last,
3591 _Comp __comp = {}, _Proj __proj = {})
3593 if (__first == __last)
3601 auto __lasti = ranges::next(__first, __last);
3618 ranges::iter_swap(__i, __j);
3619 ranges::reverse(__ii, __last);
3624 ranges::reverse(__first, __last);
3630 template<bidirectional_range _Range,
typename _Comp = ranges::less,
3631 typename _Proj = identity>
3632 requires sortable<iterator_t<_Range>, _Comp, _Proj>
3633 constexpr prev_permutation_result<safe_iterator_t<_Range>>
3634 prev_permutation(_Range&& __r, _Comp __comp = {}, _Proj __proj = {})
3641 _GLIBCXX_END_NAMESPACE_VERSION
3645 #endif // _RANGES_ALGO_H