56#ifndef _STL_ALGOBASE_H
57#define _STL_ALGOBASE_H 1
72#if __cplusplus >= 201103L
75#if __cplusplus >= 201402L
78#if __cplusplus >= 202002L
82namespace std _GLIBCXX_VISIBILITY(default)
84_GLIBCXX_BEGIN_NAMESPACE_VERSION
90 template<
typename _Tp,
typename _Up>
93 __memcmp(
const _Tp* __first1,
const _Up* __first2,
size_t __num)
95#if __cplusplus >= 201103L
96 static_assert(
sizeof(_Tp) ==
sizeof(_Up),
"can be compared with memcmp");
98#ifdef __cpp_lib_is_constant_evaluated
99 if (std::is_constant_evaluated())
101 for(; __num > 0; ++__first1, ++__first2, --__num)
102 if (*__first1 != *__first2)
103 return *__first1 < *__first2 ? -1 : 1;
108 return __builtin_memcmp(__first1, __first2,
sizeof(_Tp) * __num);
111#if __cplusplus < 201103L
115 template<
bool _BoolType>
118 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
120 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
122 typedef typename iterator_traits<_ForwardIterator1>::value_type
124 _ValueType1 __tmp = *__a;
131 struct __iter_swap<true>
133 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
135 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
152 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
155 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
158 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
160 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
163#if __cplusplus < 201103L
169 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
171 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
178 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
179 && __are_same<_ValueType1&, _ReferenceType1>::__value
180 && __are_same<_ValueType2&, _ReferenceType2>::__value>::
201 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
204 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
205 _ForwardIterator2 __first2)
208 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
210 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
212 __glibcxx_requires_valid_range(__first1, __last1);
214 for (; __first1 != __last1; ++__first1, (void)++__first2)
215 std::iter_swap(__first1, __first2);
230 template<
typename _Tp>
233 min(
const _Tp& __a,
const _Tp& __b)
236 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
254 template<
typename _Tp>
257 max(
const _Tp& __a,
const _Tp& __b)
260 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
278 template<
typename _Tp,
typename _Compare>
281 min(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
284 if (__comp(__b, __a))
300 template<
typename _Tp,
typename _Compare>
303 max(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
306 if (__comp(__a, __b))
313 template<
typename _Iterator>
316 __niter_base(_Iterator __it)
320 template<
typename _Ite,
typename _Seq>
323 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
329 template<
typename _From,
typename _To>
332 __niter_wrap(_From __from, _To __res)
333 {
return __from + (__res - std::__niter_base(__from)); }
336 template<
typename _Iterator>
339 __niter_wrap(
const _Iterator&, _Iterator __res)
348 template<
bool _IsMove,
bool _IsSimple,
typename _Category>
351 template<
typename _II,
typename _OI>
354 __copy_m(_II __first, _II __last, _OI __result)
356 for (; __first != __last; ++__result, (void)++__first)
357 *__result = *__first;
362#if __cplusplus >= 201103L
363 template<
typename _Category>
364 struct __copy_move<true, false, _Category>
366 template<
typename _II,
typename _OI>
369 __copy_m(_II __first, _II __last, _OI __result)
371 for (; __first != __last; ++__result, (void)++__first)
379 struct __copy_move<false, false, random_access_iterator_tag>
381 template<
typename _II,
typename _OI>
384 __copy_m(_II __first, _II __last, _OI __result)
386 typedef typename iterator_traits<_II>::difference_type _Distance;
387 for(_Distance __n = __last - __first; __n > 0; --__n)
389 *__result = *__first;
396 template<
typename _Tp,
typename _Up>
398 __assign_one(_Tp* __to, _Up* __from)
402#if __cplusplus >= 201103L
404 struct __copy_move<true, false, random_access_iterator_tag>
406 template<
typename _II,
typename _OI>
409 __copy_m(_II __first, _II __last, _OI __result)
411 typedef typename iterator_traits<_II>::difference_type _Distance;
412 for(_Distance __n = __last - __first; __n > 0; --__n)
421 template<
typename _Tp,
typename _Up>
423 __assign_one(_Tp* __to, _Up* __from)
428 template<
bool _IsMove>
429 struct __copy_move<_IsMove, true, random_access_iterator_tag>
431 template<
typename _Tp,
typename _Up>
434 __copy_m(_Tp* __first, _Tp* __last, _Up* __result)
436 const ptrdiff_t _Num = __last - __first;
437 if (__builtin_expect(_Num > 1,
true))
438 __builtin_memmove(__result, __first,
sizeof(_Tp) * _Num);
440 std::__copy_move<_IsMove, false, random_access_iterator_tag>::
441 __assign_one(__result, __first);
442 return __result + _Num;
446_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
448 template<
typename _Tp,
typename _Ref,
typename _Ptr>
449 struct _Deque_iterator;
451 struct _Bit_iterator;
453_GLIBCXX_END_NAMESPACE_CONTAINER
458 template<
typename _CharT>
461 template<
typename _CharT,
typename _Traits>
462 class istreambuf_iterator;
464 template<
typename _CharT,
typename _Traits>
465 class ostreambuf_iterator;
467 template<
bool _IsMove,
typename _CharT>
468 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
469 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
470 __copy_move_a2(_CharT*, _CharT*,
471 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
473 template<
bool _IsMove,
typename _CharT>
474 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
475 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
476 __copy_move_a2(
const _CharT*,
const _CharT*,
477 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
479 template<
bool _IsMove,
typename _CharT>
480 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
482 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
483 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
485 template<
bool _IsMove,
typename _CharT>
486 typename __gnu_cxx::__enable_if<
487 __is_char<_CharT>::__value,
488 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
490 istreambuf_iterator<_CharT, char_traits<_CharT> >,
491 istreambuf_iterator<_CharT, char_traits<_CharT> >,
492 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>);
495 template<
bool _IsMove,
typename _II,
typename _OI>
498 __copy_move_a2(_II __first, _II __last, _OI __result)
500 typedef typename iterator_traits<_II>::iterator_category _Category;
501#ifdef __cpp_lib_is_constant_evaluated
502 if (std::is_constant_evaluated())
503 return std::__copy_move<_IsMove, false, _Category>::
504 __copy_m(__first, __last, __result);
506 return std::__copy_move<_IsMove, __memcpyable<_OI, _II>::__value,
507 _Category>::__copy_m(__first, __last, __result);
510 template<
bool _IsMove,
511 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
513 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
514 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
517 template<
bool _IsMove,
518 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
519 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
520 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
521 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
522 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
524 template<
bool _IsMove,
typename _II,
typename _Tp>
525 typename __gnu_cxx::__enable_if<
526 __is_random_access_iter<_II>::__value,
527 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
528 __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
530 template<
bool _IsMove,
typename _II,
typename _OI>
533 __copy_move_a1(_II __first, _II __last, _OI __result)
534 {
return std::__copy_move_a2<_IsMove>(__first, __last, __result); }
536 template<
bool _IsMove,
typename _II,
typename _OI>
539 __copy_move_a(_II __first, _II __last, _OI __result)
541 return std::__niter_wrap(__result,
542 std::__copy_move_a1<_IsMove>(std::__niter_base(__first),
543 std::__niter_base(__last),
544 std::__niter_base(__result)));
547 template<
bool _IsMove,
548 typename _Ite,
typename _Seq,
typename _Cat,
typename _OI>
551 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
552 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
555 template<
bool _IsMove,
556 typename _II,
typename _Ite,
typename _Seq,
typename _Cat>
559 __copy_move_a(_II, _II,
560 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
562 template<
bool _IsMove,
563 typename _IIte,
typename _ISeq,
typename _ICat,
564 typename _OIte,
typename _OSeq,
typename _OCat>
566 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
567 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
568 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
569 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
571 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
574 __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result,
581 *__result = *__first;
593 template<
typename _CharT,
typename _Size>
594 typename __gnu_cxx::__enable_if<
595 __is_char<_CharT>::__value, _CharT*>::__type
596 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >,
597 _Size, _CharT*,
bool);
599 template<
typename _CharT,
typename _Size>
600 typename __gnu_cxx::__enable_if<
601 __is_char<_CharT>::__value,
602 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
603 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, _Size,
604 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>,
625 template<
typename _II,
typename _OI>
628 copy(_II __first, _II __last, _OI __result)
631 __glibcxx_function_requires(_InputIteratorConcept<_II>)
632 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
634 __glibcxx_requires_can_increment_range(__first, __last, __result);
636 return std::__copy_move_a<__is_move_iterator<_II>::__value>
637 (std::__miter_base(__first), std::__miter_base(__last), __result);
640#if __cplusplus >= 201103L
658 template<
typename _II,
typename _OI>
661 move(_II __first, _II __last, _OI __result)
664 __glibcxx_function_requires(_InputIteratorConcept<_II>)
665 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
667 __glibcxx_requires_can_increment_range(__first, __last, __result);
669 return std::__copy_move_a<true>(std::__miter_base(__first),
670 std::__miter_base(__last), __result);
673#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
675#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
678 template<
bool _IsMove,
bool _IsSimple,
typename _Category>
679 struct __copy_move_backward
681 template<
typename _BI1,
typename _BI2>
684 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
686 while (__first != __last)
687 *--__result = *--__last;
692#if __cplusplus >= 201103L
693 template<
typename _Category>
694 struct __copy_move_backward<true, false, _Category>
696 template<
typename _BI1,
typename _BI2>
699 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
701 while (__first != __last)
709 struct __copy_move_backward<false, false, random_access_iterator_tag>
711 template<
typename _BI1,
typename _BI2>
714 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
716 typename iterator_traits<_BI1>::difference_type
717 __n = __last - __first;
718 for (; __n > 0; --__n)
719 *--__result = *--__last;
724#if __cplusplus >= 201103L
726 struct __copy_move_backward<true, false, random_access_iterator_tag>
728 template<
typename _BI1,
typename _BI2>
731 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
733 typename iterator_traits<_BI1>::difference_type
734 __n = __last - __first;
735 for (; __n > 0; --__n)
742 template<
bool _IsMove>
743 struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
745 template<
typename _Tp,
typename _Up>
748 __copy_move_b(_Tp* __first, _Tp* __last, _Up* __result)
750 const ptrdiff_t _Num = __last - __first;
751 if (__builtin_expect(_Num > 1,
true))
752 __builtin_memmove(__result - _Num, __first,
sizeof(_Tp) * _Num);
754 std::__copy_move<_IsMove, false, random_access_iterator_tag>::
755 __assign_one(__result - 1, __first);
756 return __result - _Num;
760 template<
bool _IsMove,
typename _BI1,
typename _BI2>
763 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
765 typedef typename iterator_traits<_BI1>::iterator_category _Category;
766#ifdef __cpp_lib_is_constant_evaluated
767 if (std::is_constant_evaluated())
768 return std::__copy_move_backward<_IsMove, false, _Category>::
769 __copy_move_b(__first, __last, __result);
771 return std::__copy_move_backward<_IsMove,
772 __memcpyable<_BI2, _BI1>::__value,
773 _Category>::__copy_move_b(__first,
778 template<
bool _IsMove,
typename _BI1,
typename _BI2>
781 __copy_move_backward_a1(_BI1 __first, _BI1 __last, _BI2 __result)
782 {
return std::__copy_move_backward_a2<_IsMove>(__first, __last, __result); }
784 template<
bool _IsMove,
785 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
787 __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
788 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
791 template<
bool _IsMove,
792 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
793 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
794 __copy_move_backward_a1(
795 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
796 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
797 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
799 template<
bool _IsMove,
typename _II,
typename _Tp>
800 typename __gnu_cxx::__enable_if<
801 __is_random_access_iter<_II>::__value,
802 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
803 __copy_move_backward_a1(_II, _II,
804 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
806 template<
bool _IsMove,
typename _II,
typename _OI>
809 __copy_move_backward_a(_II __first, _II __last, _OI __result)
811 return std::__niter_wrap(__result,
812 std::__copy_move_backward_a1<_IsMove>
813 (std::__niter_base(__first), std::__niter_base(__last),
814 std::__niter_base(__result)));
817 template<
bool _IsMove,
818 typename _Ite,
typename _Seq,
typename _Cat,
typename _OI>
821 __copy_move_backward_a(
822 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
823 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
826 template<
bool _IsMove,
827 typename _II,
typename _Ite,
typename _Seq,
typename _Cat>
830 __copy_move_backward_a(_II, _II,
831 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
833 template<
bool _IsMove,
834 typename _IIte,
typename _ISeq,
typename _ICat,
835 typename _OIte,
typename _OSeq,
typename _OCat>
837 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
838 __copy_move_backward_a(
839 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
840 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
841 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
861 template<
typename _BI1,
typename _BI2>
864 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
867 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
868 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
869 __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
871 __glibcxx_requires_can_decrement_range(__first, __last, __result);
873 return std::__copy_move_backward_a<__is_move_iterator<_BI1>::__value>
874 (std::__miter_base(__first), std::__miter_base(__last), __result);
877#if __cplusplus >= 201103L
896 template<
typename _BI1,
typename _BI2>
902 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
903 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
904 __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
906 __glibcxx_requires_can_decrement_range(__first, __last, __result);
908 return std::__copy_move_backward_a<true>(std::__miter_base(__first),
909 std::__miter_base(__last),
913#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
915#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
918 template<
typename _ForwardIterator,
typename _Tp>
921 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value,
void>::__type
922 __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
925 for (; __first != __last; ++__first)
929 template<
typename _ForwardIterator,
typename _Tp>
932 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value,
void>::__type
933 __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
936 const _Tp __tmp = __value;
937 for (; __first != __last; ++__first)
942 template<
typename _Tp>
945 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value,
void>::__type
946 __fill_a1(_Tp* __first, _Tp* __last,
const _Tp& __c)
948 const _Tp __tmp = __c;
949#if __cpp_lib_is_constant_evaluated
950 if (std::is_constant_evaluated())
952 for (; __first != __last; ++__first)
957 if (
const size_t __len = __last - __first)
958 __builtin_memset(__first,
static_cast<unsigned char>(__tmp), __len);
961 template<
typename _Ite,
typename _Cont,
typename _Tp>
964 __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first,
965 ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last,
967 { std::__fill_a1(__first.base(), __last.base(), __value); }
969 template<
typename _Tp,
typename _VTp>
971 __fill_a1(
const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
972 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
977 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator,
980 template<
typename _FIte,
typename _Tp>
983 __fill_a(_FIte __first, _FIte __last,
const _Tp& __value)
984 { std::__fill_a1(__first, __last, __value); }
986 template<
typename _Ite,
typename _Seq,
typename _Cat,
typename _Tp>
989 __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
990 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
1005 template<
typename _ForwardIterator,
typename _Tp>
1006 _GLIBCXX20_CONSTEXPR
1008 fill(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __value)
1011 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1013 __glibcxx_requires_valid_range(__first, __last);
1015 std::__fill_a(__first, __last, __value);
1019 inline _GLIBCXX_CONSTEXPR
int
1020 __size_to_integer(
int __n) {
return __n; }
1021 inline _GLIBCXX_CONSTEXPR
unsigned
1022 __size_to_integer(
unsigned __n) {
return __n; }
1023 inline _GLIBCXX_CONSTEXPR
long
1024 __size_to_integer(
long __n) {
return __n; }
1025 inline _GLIBCXX_CONSTEXPR
unsigned long
1026 __size_to_integer(
unsigned long __n) {
return __n; }
1027 inline _GLIBCXX_CONSTEXPR
long long
1028 __size_to_integer(
long long __n) {
return __n; }
1029 inline _GLIBCXX_CONSTEXPR
unsigned long long
1030 __size_to_integer(
unsigned long long __n) {
return __n; }
1032#if defined(__GLIBCXX_TYPE_INT_N_0)
1033 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
1034 __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1035 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_0
1036 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1038#if defined(__GLIBCXX_TYPE_INT_N_1)
1039 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
1040 __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1041 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_1
1042 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1044#if defined(__GLIBCXX_TYPE_INT_N_2)
1045 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
1046 __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1047 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_2
1048 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1050#if defined(__GLIBCXX_TYPE_INT_N_3)
1051 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_3
1052 __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1053 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
1054 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1057 inline _GLIBCXX_CONSTEXPR
long long
1058 __size_to_integer(
float __n) {
return (
long long)__n; }
1059 inline _GLIBCXX_CONSTEXPR
long long
1060 __size_to_integer(
double __n) {
return (
long long)__n; }
1061 inline _GLIBCXX_CONSTEXPR
long long
1062 __size_to_integer(
long double __n) {
return (
long long)__n; }
1063#if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128) && !defined(__CUDACC__)
1064 __extension__
inline _GLIBCXX_CONSTEXPR
long long
1065 __size_to_integer(__float128 __n) {
return (
long long)__n; }
1068 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1069 _GLIBCXX20_CONSTEXPR
1071 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
1072 __fill_n_a1(_OutputIterator __first, _Size __n,
const _Tp& __value)
1074 for (; __n > 0; --__n, (void) ++__first)
1079 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1080 _GLIBCXX20_CONSTEXPR
1082 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
1083 __fill_n_a1(_OutputIterator __first, _Size __n,
const _Tp& __value)
1085 const _Tp __tmp = __value;
1086 for (; __n > 0; --__n, (void) ++__first)
1091 template<
typename _Ite,
typename _Seq,
typename _Cat,
typename _Size,
1093 _GLIBCXX20_CONSTEXPR
1094 ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
1095 __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
1096 _Size __n,
const _Tp& __value,
1099 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1100 _GLIBCXX20_CONSTEXPR
1101 inline _OutputIterator
1102 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1105#if __cplusplus >= 201103L
1106 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1108 return __fill_n_a1(__first, __n, __value);
1111 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1112 _GLIBCXX20_CONSTEXPR
1113 inline _OutputIterator
1114 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1117#if __cplusplus >= 201103L
1118 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1120 return __fill_n_a1(__first, __n, __value);
1123 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1124 _GLIBCXX20_CONSTEXPR
1125 inline _OutputIterator
1126 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1129#if __cplusplus >= 201103L
1130 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1135 __glibcxx_requires_can_increment(__first, __n);
1137 std::__fill_a(__first, __first + __n, __value);
1138 return __first + __n;
1158 template<
typename _OI,
typename _Size,
typename _Tp>
1159 _GLIBCXX20_CONSTEXPR
1161 fill_n(_OI __first, _Size __n,
const _Tp& __value)
1164 __glibcxx_function_requires(_OutputIteratorConcept<_OI, const _Tp&>)
1166 return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
1170 template<
bool _BoolType>
1173 template<
typename _II1,
typename _II2>
1174 _GLIBCXX20_CONSTEXPR
1176 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1178 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1179 if (!(*__first1 == *__first2))
1186 struct __equal<true>
1188 template<
typename _Tp>
1189 _GLIBCXX20_CONSTEXPR
1191 equal(
const _Tp* __first1,
const _Tp* __last1,
const _Tp* __first2)
1193 if (
const size_t __len = (__last1 - __first1))
1194 return !std::__memcmp(__first1, __first2, __len);
1199 template<
typename _Tp,
typename _Ref,
typename _Ptr,
typename _II>
1200 typename __gnu_cxx::__enable_if<
1201 __is_random_access_iter<_II>::__value,
bool>::__type
1202 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1203 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1206 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1207 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1209 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1210 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1211 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1213 template<
typename _II,
typename _Tp,
typename _Ref,
typename _Ptr>
1214 typename __gnu_cxx::__enable_if<
1215 __is_random_access_iter<_II>::__value,
bool>::__type
1216 __equal_aux1(_II, _II,
1217 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>);
1219 template<
typename _II1,
typename _II2>
1220 _GLIBCXX20_CONSTEXPR
1222 __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
1224 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1225 const bool __simple = ((__is_integer<_ValueType1>::__value
1226 || __is_pointer<_ValueType1>::__value)
1227 && __memcmpable<_II1, _II2>::__value);
1228 return std::__equal<__simple>::equal(__first1, __last1, __first2);
1231 template<
typename _II1,
typename _II2>
1232 _GLIBCXX20_CONSTEXPR
1234 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
1236 return std::__equal_aux1(std::__niter_base(__first1),
1237 std::__niter_base(__last1),
1238 std::__niter_base(__first2));
1241 template<
typename _II1,
typename _Seq1,
typename _Cat1,
typename _II2>
1242 _GLIBCXX20_CONSTEXPR
1244 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1245 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1248 template<
typename _II1,
typename _II2,
typename _Seq2,
typename _Cat2>
1249 _GLIBCXX20_CONSTEXPR
1251 __equal_aux(_II1, _II1,
1252 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1254 template<
typename _II1,
typename _Seq1,
typename _Cat1,
1255 typename _II2,
typename _Seq2,
typename _Cat2>
1256 _GLIBCXX20_CONSTEXPR
1258 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1259 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1260 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1262 template<
typename,
typename>
1265 template<
typename _II1,
typename _II2>
1266 _GLIBCXX20_CONSTEXPR
1268 __newlast1(_II1, _II1 __last1, _II2, _II2)
1271 template<
typename _II>
1272 _GLIBCXX20_CONSTEXPR
1274 __cnd2(_II __first, _II __last)
1275 {
return __first != __last; }
1279 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
1281 template<
typename _RAI1,
typename _RAI2>
1282 _GLIBCXX20_CONSTEXPR
1284 __newlast1(_RAI1 __first1, _RAI1 __last1,
1285 _RAI2 __first2, _RAI2 __last2)
1287 const typename iterator_traits<_RAI1>::difference_type
1288 __diff1 = __last1 - __first1;
1289 const typename iterator_traits<_RAI2>::difference_type
1290 __diff2 = __last2 - __first2;
1291 return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
1294 template<
typename _RAI>
1295 static _GLIBCXX20_CONSTEXPR
bool
1300 template<
typename _II1,
typename _II2,
typename _Compare>
1301 _GLIBCXX20_CONSTEXPR
1303 __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
1304 _II2 __first2, _II2 __last2,
1307 typedef typename iterator_traits<_II1>::iterator_category _Category1;
1308 typedef typename iterator_traits<_II2>::iterator_category _Category2;
1309 typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1311 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1312 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1313 ++__first1, (void)++__first2)
1315 if (__comp(__first1, __first2))
1317 if (__comp(__first2, __first1))
1320 return __first1 == __last1 && __first2 != __last2;
1323 template<
bool _BoolType>
1324 struct __lexicographical_compare
1326 template<
typename _II1,
typename _II2>
1327 _GLIBCXX20_CONSTEXPR
1329 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1331 using __gnu_cxx::__ops::__iter_less_iter;
1332 return std::__lexicographical_compare_impl(__first1, __last1,
1334 __iter_less_iter());
1337 template<
typename _II1,
typename _II2>
1338 _GLIBCXX20_CONSTEXPR
1340 __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1342 while (__first1 != __last1)
1344 if (__first2 == __last2)
1346 if (*__first1 < *__first2)
1348 if (*__first2 < *__first1)
1353 return int(__first2 == __last2) - 1;
1358 struct __lexicographical_compare<true>
1360 template<
typename _Tp,
typename _Up>
1361 _GLIBCXX20_CONSTEXPR
1363 __lc(
const _Tp* __first1,
const _Tp* __last1,
1364 const _Up* __first2,
const _Up* __last2)
1365 {
return __3way(__first1, __last1, __first2, __last2) < 0; }
1367 template<
typename _Tp,
typename _Up>
1368 _GLIBCXX20_CONSTEXPR
1370 __3way(
const _Tp* __first1,
const _Tp* __last1,
1371 const _Up* __first2,
const _Up* __last2)
1373 const size_t __len1 = __last1 - __first1;
1374 const size_t __len2 = __last2 - __first2;
1375 if (
const size_t __len =
std::min(__len1, __len2))
1376 if (
int __result = std::__memcmp(__first1, __first2, __len))
1378 return ptrdiff_t(__len1 - __len2);
1382 template<
typename _II1,
typename _II2>
1383 _GLIBCXX20_CONSTEXPR
1385 __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
1386 _II2 __first2, _II2 __last2)
1388 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1389 typedef typename iterator_traits<_II2>::value_type _ValueType2;
1390 const bool __simple =
1391 (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
1392 && __is_pointer<_II1>::__value
1393 && __is_pointer<_II2>::__value
1394#if __cplusplus > 201703L && __glibcxx_concepts
1398 && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>>
1399 && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>>
1403 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
1407 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1410 __lexicographical_compare_aux1(
1411 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1412 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1415 template<
typename _Tp1,
1416 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1418 __lexicographical_compare_aux1(_Tp1*, _Tp1*,
1419 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1420 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1422 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1423 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1425 __lexicographical_compare_aux1(
1426 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1427 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1428 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1429 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1431 template<
typename _II1,
typename _II2>
1432 _GLIBCXX20_CONSTEXPR
1434 __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
1435 _II2 __first2, _II2 __last2)
1437 return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
1438 std::__niter_base(__last1),
1439 std::__niter_base(__first2),
1440 std::__niter_base(__last2));
1443 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
1445 _GLIBCXX20_CONSTEXPR
1447 __lexicographical_compare_aux(
1448 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1449 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1452 template<
typename _II1,
1453 typename _Iter2,
typename _Seq2,
typename _Cat2>
1454 _GLIBCXX20_CONSTEXPR
1456 __lexicographical_compare_aux(
1458 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1459 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1461 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
1462 typename _Iter2,
typename _Seq2,
typename _Cat2>
1463 _GLIBCXX20_CONSTEXPR
1465 __lexicographical_compare_aux(
1466 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1467 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1468 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1469 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1471 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1472 _GLIBCXX20_CONSTEXPR
1474 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1475 const _Tp& __val, _Compare __comp)
1477 typedef typename iterator_traits<_ForwardIterator>::difference_type
1484 _DistanceType __half = __len >> 1;
1485 _ForwardIterator __middle = __first;
1487 if (__comp(__middle, __val))
1491 __len = __len - __half - 1;
1510 template<
typename _ForwardIterator,
typename _Tp>
1511 _GLIBCXX20_CONSTEXPR
1512 inline _ForwardIterator
1513 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1517 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1518 __glibcxx_function_requires(_LessThanOpConcept<
1520 __glibcxx_requires_partitioned_lower(__first, __last, __val);
1522 return std::__lower_bound(__first, __last, __val,
1523 __gnu_cxx::__ops::__iter_less_val());
1528 template<
typename _Tp>
1529 inline _GLIBCXX_CONSTEXPR _Tp
1532#if __cplusplus >= 201402L
1536 return (
sizeof(+__n) * __CHAR_BIT__ - 1)
1537 - (
sizeof(+__n) ==
sizeof(
long long)
1538 ? __builtin_clzll(+__n)
1539 : (
sizeof(+__n) ==
sizeof(
long)
1540 ? __builtin_clzl(+__n)
1541 : __builtin_clz(+__n)));
1545_GLIBCXX_BEGIN_NAMESPACE_ALGO
1559 template<
typename _II1,
typename _II2>
1560 _GLIBCXX20_CONSTEXPR
1562 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1565 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1566 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1567 __glibcxx_function_requires(_EqualOpConcept<
1570 __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
1572 return std::__equal_aux(__first1, __last1, __first2);
1590 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1591 _GLIBCXX20_CONSTEXPR
1593 equal(_IIter1 __first1, _IIter1 __last1,
1594 _IIter2 __first2, _BinaryPredicate __binary_pred)
1597 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1598 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1599 __glibcxx_requires_valid_range(__first1, __last1);
1601 for (; __first1 != __last1; ++__first1, (void)++__first2)
1602 if (!
bool(__binary_pred(*__first1, *__first2)))
1607#if __cplusplus >= 201103L
1609 template<
typename _II1,
typename _II2>
1610 _GLIBCXX20_CONSTEXPR
1612 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1614 using _RATag = random_access_iterator_tag;
1615 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1616 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1617 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1624 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1627 for (; __first1 != __last1 && __first2 != __last2;
1628 ++__first1, (void)++__first2)
1629 if (!(*__first1 == *__first2))
1631 return __first1 == __last1 && __first2 == __last2;
1635 template<
typename _II1,
typename _II2,
typename _BinaryPredicate>
1636 _GLIBCXX20_CONSTEXPR
1638 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2,
1639 _BinaryPredicate __binary_pred)
1641 using _RATag = random_access_iterator_tag;
1642 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1643 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1644 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1651 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1655 for (; __first1 != __last1 && __first2 != __last2;
1656 ++__first1, (void)++__first2)
1657 if (!
bool(__binary_pred(*__first1, *__first2)))
1659 return __first1 == __last1 && __first2 == __last2;
1663#ifdef __glibcxx_robust_nonmodifying_seq_ops
1677 template<
typename _II1,
typename _II2>
1678 _GLIBCXX20_CONSTEXPR
1680 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1683 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1684 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1685 __glibcxx_function_requires(_EqualOpConcept<
1688 __glibcxx_requires_valid_range(__first1, __last1);
1689 __glibcxx_requires_valid_range(__first2, __last2);
1691 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2);
1710 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1711 _GLIBCXX20_CONSTEXPR
1713 equal(_IIter1 __first1, _IIter1 __last1,
1714 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
1717 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1718 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1719 __glibcxx_requires_valid_range(__first1, __last1);
1720 __glibcxx_requires_valid_range(__first2, __last2);
1722 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2,
1742 template<
typename _II1,
typename _II2>
1743 _GLIBCXX20_CONSTEXPR
1745 lexicographical_compare(_II1 __first1, _II1 __last1,
1746 _II2 __first2, _II2 __last2)
1748#ifdef _GLIBCXX_CONCEPT_CHECKS
1753 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1754 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1755 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1756 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1757 __glibcxx_requires_valid_range(__first1, __last1);
1758 __glibcxx_requires_valid_range(__first2, __last2);
1760 return std::__lexicographical_compare_aux(__first1, __last1,
1777 template<
typename _II1,
typename _II2,
typename _Compare>
1778 _GLIBCXX20_CONSTEXPR
1780 lexicographical_compare(_II1 __first1, _II1 __last1,
1781 _II2 __first2, _II2 __last2, _Compare __comp)
1784 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1785 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1786 __glibcxx_requires_valid_range(__first1, __last1);
1787 __glibcxx_requires_valid_range(__first2, __last2);
1789 return std::__lexicographical_compare_impl
1790 (__first1, __last1, __first2, __last2,
1791 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1794#if __cpp_lib_three_way_comparison
1797 template<
typename _Iter>
1798 concept __is_byte_iter = contiguous_iterator<_Iter>
1799 && __is_memcmp_ordered<iter_value_t<_Iter>>::__value;
1803 template<
typename _Tp>
1805 __min_cmp(_Tp __x, _Tp __y)
1809 decltype(__x <=> __y) _M_cmp;
1811 auto __c = __x <=> __y;
1813 return _Res{__y, __c};
1814 return _Res{__x, __c};
1828 template<
typename _InputIter1,
typename _InputIter2,
typename _Comp>
1831 _InputIter1 __last1,
1832 _InputIter2 __first2,
1833 _InputIter2 __last2,
1835 ->
decltype(__comp(*__first1, *__first2))
1838 __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
1839 __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
1840 __glibcxx_requires_valid_range(__first1, __last1);
1841 __glibcxx_requires_valid_range(__first2, __last2);
1843 using _Cat =
decltype(__comp(*__first1, *__first2));
1844 static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
1846 if (!std::__is_constant_evaluated())
1847 if constexpr (same_as<_Comp, __detail::_Synth3way>
1848 || same_as<_Comp, compare_three_way>)
1849 if constexpr (__is_byte_iter<_InputIter1>)
1850 if constexpr (__is_byte_iter<_InputIter2>)
1852 const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1853 __min_cmp(__last1 - __first1, __last2 - __first2);
1857 = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0;
1864 while (__first1 != __last1)
1866 if (__first2 == __last2)
1867 return strong_ordering::greater;
1868 if (
auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
1873 return (__first2 == __last2) <=>
true;
1876 template<
typename _InputIter1,
typename _InputIter2>
1879 _InputIter1 __last1,
1880 _InputIter2 __first2,
1881 _InputIter2 __last2)
1883 return _GLIBCXX_STD_A::
1884 lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
1885 compare_three_way{});
1889 template<
typename _InputIterator1,
typename _InputIterator2,
1890 typename _BinaryPredicate>
1891 _GLIBCXX20_CONSTEXPR
1892 pair<_InputIterator1, _InputIterator2>
1893 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1894 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1896 while (__first1 != __last1 && __binary_pred(__first1, __first2))
1901 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1917 template<
typename _InputIterator1,
typename _InputIterator2>
1918 _GLIBCXX20_CONSTEXPR
1919 inline pair<_InputIterator1, _InputIterator2>
1920 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1921 _InputIterator2 __first2)
1924 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1925 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1926 __glibcxx_function_requires(_EqualOpConcept<
1929 __glibcxx_requires_valid_range(__first1, __last1);
1931 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1932 __gnu_cxx::__ops::__iter_equal_to_iter());
1951 template<
typename _InputIterator1,
typename _InputIterator2,
1952 typename _BinaryPredicate>
1953 _GLIBCXX20_CONSTEXPR
1954 inline pair<_InputIterator1, _InputIterator2>
1955 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1956 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1959 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1960 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1961 __glibcxx_requires_valid_range(__first1, __last1);
1963 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1964 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1967#if __glibcxx_robust_nonmodifying_seq_ops
1968 template<
typename _InputIterator1,
typename _InputIterator2,
1969 typename _BinaryPredicate>
1970 _GLIBCXX20_CONSTEXPR
1971 pair<_InputIterator1, _InputIterator2>
1972 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1973 _InputIterator2 __first2, _InputIterator2 __last2,
1974 _BinaryPredicate __binary_pred)
1976 while (__first1 != __last1 && __first2 != __last2
1977 && __binary_pred(__first1, __first2))
1982 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1999 template<
typename _InputIterator1,
typename _InputIterator2>
2000 _GLIBCXX20_CONSTEXPR
2001 inline pair<_InputIterator1, _InputIterator2>
2002 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2003 _InputIterator2 __first2, _InputIterator2 __last2)
2006 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2007 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2008 __glibcxx_function_requires(_EqualOpConcept<
2011 __glibcxx_requires_valid_range(__first1, __last1);
2012 __glibcxx_requires_valid_range(__first2, __last2);
2014 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2015 __gnu_cxx::__ops::__iter_equal_to_iter());
2035 template<
typename _InputIterator1,
typename _InputIterator2,
2036 typename _BinaryPredicate>
2037 _GLIBCXX20_CONSTEXPR
2038 inline pair<_InputIterator1, _InputIterator2>
2039 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2040 _InputIterator2 __first2, _InputIterator2 __last2,
2041 _BinaryPredicate __binary_pred)
2044 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2045 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2046 __glibcxx_requires_valid_range(__first1, __last1);
2047 __glibcxx_requires_valid_range(__first2, __last2);
2049 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2050 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
2054_GLIBCXX_END_NAMESPACE_ALGO
2057 template<
typename _InputIterator,
typename _Predicate>
2058 _GLIBCXX20_CONSTEXPR
2059 inline _InputIterator
2063 while (__first != __last && !__pred(__first))
2069 template<
typename _RandomAccessIterator,
typename _Predicate>
2070 _GLIBCXX20_CONSTEXPR
2071 _RandomAccessIterator
2072 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
2076 __trip_count = (__last - __first) >> 2;
2078 for (; __trip_count > 0; --__trip_count)
2080 if (__pred(__first))
2084 if (__pred(__first))
2088 if (__pred(__first))
2092 if (__pred(__first))
2097 switch (__last - __first)
2100 if (__pred(__first))
2105 if (__pred(__first))
2110 if (__pred(__first))
2120 template<
typename _Iterator,
typename _Predicate>
2121 _GLIBCXX20_CONSTEXPR
2123 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
2125 return __find_if(__first, __last, __pred,
2129 template<
typename _InputIterator,
typename _Predicate>
2130 _GLIBCXX20_CONSTEXPR
2131 typename iterator_traits<_InputIterator>::difference_type
2132 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2134 typename iterator_traits<_InputIterator>::difference_type __n = 0;
2135 for (; __first != __last; ++__first)
2136 if (__pred(__first))
2141 template<
typename _ForwardIterator,
typename _Predicate>
2142 _GLIBCXX20_CONSTEXPR
2144 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
2148 if (__first == __last)
2150 _ForwardIterator __result = __first;
2152 for (; __first != __last; ++__first)
2153 if (!__pred(__first))
2155 *__result = _GLIBCXX_MOVE(*__first);
2161 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2162 typename _BinaryPredicate>
2163 _GLIBCXX20_CONSTEXPR
2165 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2166 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2167 _BinaryPredicate __predicate)
2170 if (__first1 == __last1 || __first2 == __last2)
2174 _ForwardIterator2 __p1(__first2);
2175 if (++__p1 == __last2)
2177 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2180 _ForwardIterator1 __current = __first1;
2186 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2188 if (__first1 == __last1)
2191 _ForwardIterator2 __p = __p1;
2192 __current = __first1;
2193 if (++__current == __last1)
2196 while (__predicate(__current, __p))
2198 if (++__p == __last2)
2200 if (++__current == __last1)
2208#if __cplusplus >= 201103L
2209 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2210 typename _BinaryPredicate>
2211 _GLIBCXX20_CONSTEXPR
2213 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2214 _ForwardIterator2 __first2, _BinaryPredicate __pred)
2218 for (; __first1 != __last1; ++__first1, (void)++__first2)
2219 if (!__pred(__first1, __first2))
2222 if (__first1 == __last1)
2227 _ForwardIterator2 __last2 = __first2;
2229 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
2232 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
2236 = std::__count_if(__first2, __last2,
2237 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
2238 if (0 == __matches ||
2239 std::__count_if(__scan, __last1,
2240 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
2259 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
2260 _GLIBCXX20_CONSTEXPR
2262 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2263 _ForwardIterator2 __first2)
2266 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2267 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2268 __glibcxx_function_requires(_EqualOpConcept<
2271 __glibcxx_requires_valid_range(__first1, __last1);
2273 return std::__is_permutation(__first1, __last1, __first2,
2274 __gnu_cxx::__ops::__iter_equal_to_iter());
2278_GLIBCXX_BEGIN_NAMESPACE_ALGO
2301 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2302 typename _BinaryPredicate>
2303 _GLIBCXX20_CONSTEXPR
2304 inline _ForwardIterator1
2305 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2306 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2307 _BinaryPredicate __predicate)
2310 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2311 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2312 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
2315 __glibcxx_requires_valid_range(__first1, __last1);
2316 __glibcxx_requires_valid_range(__first2, __last2);
2318 return std::__search(__first1, __last1, __first2, __last2,
2319 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
2322_GLIBCXX_END_NAMESPACE_ALGO
2323_GLIBCXX_END_NAMESPACE_VERSION
2329#ifdef _GLIBCXX_PARALLEL
Parallel STL function calls corresponding to the stl_algobase.h header. The functions defined here ma...
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
constexpr auto lexicographical_compare_three_way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2, _Comp __comp) -> decltype(__comp(*__first1, *__first2))
Performs dictionary comparison on ranges.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr _Tp __lg(_Tp __n)
This is a helper function for the sort routines and for random.tcc.
constexpr _InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find algos for the Input Iterator case.
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
is_nothrow_copy_constructible
Traits class for iterators.
Marking output iterators.
Random-access iterators support a superset of bidirectional iterator operations.