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>
231 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
233 min(
const _Tp& __a,
const _Tp& __b)
236 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
254 template<
typename _Tp>
255 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
257 max(
const _Tp& __a,
const _Tp& __b)
260 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
278 template<
typename _Tp,
typename _Compare>
279 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
281 min(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
284 if (__comp(__b, __a))
300 template<
typename _Tp,
typename _Compare>
301 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
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#if __cplusplus < 201103L
321 template<
typename _Ite,
typename _Seq>
323 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
326 template<
typename _Ite,
typename _Cont,
typename _Seq>
328 __niter_base(const ::__gnu_debug::_Safe_iterator<
329 ::__gnu_cxx::__normal_iterator<_Ite, _Cont>, _Seq,
332 template<
typename _Ite,
typename _Seq>
335 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
337 noexcept(
std::is_nothrow_copy_constructible<_Ite>::value);
343 template<
typename _From,
typename _To>
346 __niter_wrap(_From __from, _To __res)
347 {
return __from + (std::__niter_base(__res) - std::__niter_base(__from)); }
350 template<
typename _Iterator>
353 __niter_wrap(
const _Iterator&, _Iterator __res)
362 template<
bool _IsMove,
bool _IsSimple,
typename _Category>
365 template<
typename _II,
typename _OI>
368 __copy_m(_II __first, _II __last, _OI __result)
370 for (; __first != __last; ++__result, (void)++__first)
371 *__result = *__first;
376#if __cplusplus >= 201103L
377 template<
typename _Category>
378 struct __copy_move<true, false, _Category>
380 template<
typename _II,
typename _OI>
383 __copy_m(_II __first, _II __last, _OI __result)
385 for (; __first != __last; ++__result, (void)++__first)
393 struct __copy_move<false, false, random_access_iterator_tag>
395 template<
typename _II,
typename _OI>
398 __copy_m(_II __first, _II __last, _OI __result)
400 typedef typename iterator_traits<_II>::difference_type _Distance;
401 for(_Distance __n = __last - __first; __n > 0; --__n)
403 *__result = *__first;
410 template<
typename _Tp,
typename _Up>
412 __assign_one(_Tp* __to, _Up* __from)
416#if __cplusplus >= 201103L
418 struct __copy_move<true, false, random_access_iterator_tag>
420 template<
typename _II,
typename _OI>
423 __copy_m(_II __first, _II __last, _OI __result)
425 typedef typename iterator_traits<_II>::difference_type _Distance;
426 for(_Distance __n = __last - __first; __n > 0; --__n)
435 template<
typename _Tp,
typename _Up>
437 __assign_one(_Tp* __to, _Up* __from)
442 template<
bool _IsMove>
443 struct __copy_move<_IsMove, true, random_access_iterator_tag>
445 template<
typename _Tp,
typename _Up>
448 __copy_m(_Tp* __first, _Tp* __last, _Up* __result)
450 const ptrdiff_t _Num = __last - __first;
451 if (__builtin_expect(_Num > 1,
true))
452 __builtin_memmove(__result, __first,
sizeof(_Tp) * _Num);
454 std::__copy_move<_IsMove, false, random_access_iterator_tag>::
455 __assign_one(__result, __first);
456 return __result + _Num;
460_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
462 template<
typename _Tp,
typename _Ref,
typename _Ptr>
463 struct _Deque_iterator;
465 struct _Bit_iterator;
467_GLIBCXX_END_NAMESPACE_CONTAINER
472 template<
typename _CharT>
475 template<
typename _CharT,
typename _Traits>
476 class istreambuf_iterator;
478 template<
typename _CharT,
typename _Traits>
479 class ostreambuf_iterator;
481 template<
bool _IsMove,
typename _CharT>
482 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
483 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
484 __copy_move_a2(_CharT*, _CharT*,
485 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
487 template<
bool _IsMove,
typename _CharT>
488 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
489 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
490 __copy_move_a2(
const _CharT*,
const _CharT*,
491 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
493 template<
bool _IsMove,
typename _CharT>
494 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
496 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
497 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
499 template<
bool _IsMove,
typename _CharT>
500 typename __gnu_cxx::__enable_if<
501 __is_char<_CharT>::__value,
502 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
504 istreambuf_iterator<_CharT, char_traits<_CharT> >,
505 istreambuf_iterator<_CharT, char_traits<_CharT> >,
506 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>);
509 template<
bool _IsMove,
typename _II,
typename _OI>
512 __copy_move_a2(_II __first, _II __last, _OI __result)
514 typedef typename iterator_traits<_II>::iterator_category _Category;
515#ifdef __cpp_lib_is_constant_evaluated
516 if (std::is_constant_evaluated())
517 return std::__copy_move<_IsMove, false, _Category>::
518 __copy_m(__first, __last, __result);
520 return std::__copy_move<_IsMove, __memcpyable<_OI, _II>::__value,
521 _Category>::__copy_m(__first, __last, __result);
524 template<
bool _IsMove,
525 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
527 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
528 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
531 template<
bool _IsMove,
532 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
533 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
534 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
535 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
536 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
538 template<
bool _IsMove,
typename _II,
typename _Tp>
539 typename __gnu_cxx::__enable_if<
540 __is_random_access_iter<_II>::__value,
541 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
542 __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
544 template<
bool _IsMove,
typename _II,
typename _OI>
547 __copy_move_a1(_II __first, _II __last, _OI __result)
548 {
return std::__copy_move_a2<_IsMove>(__first, __last, __result); }
550 template<
bool _IsMove,
typename _II,
typename _OI>
553 __copy_move_a(_II __first, _II __last, _OI __result)
555 return std::__niter_wrap(__result,
556 std::__copy_move_a1<_IsMove>(std::__niter_base(__first),
557 std::__niter_base(__last),
558 std::__niter_base(__result)));
561 template<
bool _IsMove,
562 typename _Ite,
typename _Seq,
typename _Cat,
typename _OI>
565 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
566 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
569 template<
bool _IsMove,
570 typename _II,
typename _Ite,
typename _Seq,
typename _Cat>
573 __copy_move_a(_II, _II,
574 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
576 template<
bool _IsMove,
577 typename _IIte,
typename _ISeq,
typename _ICat,
578 typename _OIte,
typename _OSeq,
typename _OCat>
580 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
581 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
582 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
583 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
585 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
588 __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result,
595 *__result = *__first;
607 template<
typename _CharT,
typename _Size>
608 typename __gnu_cxx::__enable_if<
609 __is_char<_CharT>::__value, _CharT*>::__type
610 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >,
611 _Size, _CharT*,
bool);
613 template<
typename _CharT,
typename _Size>
614 typename __gnu_cxx::__enable_if<
615 __is_char<_CharT>::__value,
616 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
617 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, _Size,
618 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>,
639 template<
typename _II,
typename _OI>
642 copy(_II __first, _II __last, _OI __result)
645 __glibcxx_function_requires(_InputIteratorConcept<_II>)
646 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
648 __glibcxx_requires_can_increment_range(__first, __last, __result);
650 return std::__copy_move_a<__is_move_iterator<_II>::__value>
651 (std::__miter_base(__first), std::__miter_base(__last), __result);
654#if __cplusplus >= 201103L
672 template<
typename _II,
typename _OI>
675 move(_II __first, _II __last, _OI __result)
678 __glibcxx_function_requires(_InputIteratorConcept<_II>)
679 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
681 __glibcxx_requires_can_increment_range(__first, __last, __result);
683 return std::__copy_move_a<true>(std::__miter_base(__first),
684 std::__miter_base(__last), __result);
687#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
689#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
692 template<
bool _IsMove,
bool _IsSimple,
typename _Category>
693 struct __copy_move_backward
695 template<
typename _BI1,
typename _BI2>
698 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
700 while (__first != __last)
701 *--__result = *--__last;
706#if __cplusplus >= 201103L
707 template<
typename _Category>
708 struct __copy_move_backward<true, false, _Category>
710 template<
typename _BI1,
typename _BI2>
713 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
715 while (__first != __last)
723 struct __copy_move_backward<false, false, random_access_iterator_tag>
725 template<
typename _BI1,
typename _BI2>
728 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
730 typename iterator_traits<_BI1>::difference_type
731 __n = __last - __first;
732 for (; __n > 0; --__n)
733 *--__result = *--__last;
738#if __cplusplus >= 201103L
740 struct __copy_move_backward<true, false, random_access_iterator_tag>
742 template<
typename _BI1,
typename _BI2>
745 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
747 typename iterator_traits<_BI1>::difference_type
748 __n = __last - __first;
749 for (; __n > 0; --__n)
756 template<
bool _IsMove>
757 struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
759 template<
typename _Tp,
typename _Up>
762 __copy_move_b(_Tp* __first, _Tp* __last, _Up* __result)
764 const ptrdiff_t _Num = __last - __first;
765 if (__builtin_expect(_Num > 1,
true))
766 __builtin_memmove(__result - _Num, __first,
sizeof(_Tp) * _Num);
768 std::__copy_move<_IsMove, false, random_access_iterator_tag>::
769 __assign_one(__result - 1, __first);
770 return __result - _Num;
774 template<
bool _IsMove,
typename _BI1,
typename _BI2>
777 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
779 typedef typename iterator_traits<_BI1>::iterator_category _Category;
780#ifdef __cpp_lib_is_constant_evaluated
781 if (std::is_constant_evaluated())
782 return std::__copy_move_backward<_IsMove, false, _Category>::
783 __copy_move_b(__first, __last, __result);
785 return std::__copy_move_backward<_IsMove,
786 __memcpyable<_BI2, _BI1>::__value,
787 _Category>::__copy_move_b(__first,
792 template<
bool _IsMove,
typename _BI1,
typename _BI2>
795 __copy_move_backward_a1(_BI1 __first, _BI1 __last, _BI2 __result)
796 {
return std::__copy_move_backward_a2<_IsMove>(__first, __last, __result); }
798 template<
bool _IsMove,
799 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
801 __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
802 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
805 template<
bool _IsMove,
806 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
807 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
808 __copy_move_backward_a1(
809 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
810 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
811 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
813 template<
bool _IsMove,
typename _II,
typename _Tp>
814 typename __gnu_cxx::__enable_if<
815 __is_random_access_iter<_II>::__value,
816 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
817 __copy_move_backward_a1(_II, _II,
818 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
820 template<
bool _IsMove,
typename _II,
typename _OI>
823 __copy_move_backward_a(_II __first, _II __last, _OI __result)
825 return std::__niter_wrap(__result,
826 std::__copy_move_backward_a1<_IsMove>
827 (std::__niter_base(__first), std::__niter_base(__last),
828 std::__niter_base(__result)));
831 template<
bool _IsMove,
832 typename _Ite,
typename _Seq,
typename _Cat,
typename _OI>
835 __copy_move_backward_a(
836 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
837 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
840 template<
bool _IsMove,
841 typename _II,
typename _Ite,
typename _Seq,
typename _Cat>
844 __copy_move_backward_a(_II, _II,
845 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
847 template<
bool _IsMove,
848 typename _IIte,
typename _ISeq,
typename _ICat,
849 typename _OIte,
typename _OSeq,
typename _OCat>
851 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
852 __copy_move_backward_a(
853 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
854 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
855 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
875 template<
typename _BI1,
typename _BI2>
878 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
881 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
882 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
883 __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
885 __glibcxx_requires_can_decrement_range(__first, __last, __result);
887 return std::__copy_move_backward_a<__is_move_iterator<_BI1>::__value>
888 (std::__miter_base(__first), std::__miter_base(__last), __result);
891#if __cplusplus >= 201103L
910 template<
typename _BI1,
typename _BI2>
916 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
917 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
918 __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
920 __glibcxx_requires_can_decrement_range(__first, __last, __result);
922 return std::__copy_move_backward_a<true>(std::__miter_base(__first),
923 std::__miter_base(__last),
927#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
929#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
932 template<
typename _ForwardIterator,
typename _Tp>
935 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value,
void>::__type
936 __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
939 for (; __first != __last; ++__first)
943 template<
typename _ForwardIterator,
typename _Tp>
946 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value,
void>::__type
947 __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
950 const _Tp __tmp = __value;
951 for (; __first != __last; ++__first)
956 template<
typename _Tp>
959 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value,
void>::__type
960 __fill_a1(_Tp* __first, _Tp* __last,
const _Tp& __c)
962 const _Tp __tmp = __c;
963#if __cpp_lib_is_constant_evaluated
964 if (std::is_constant_evaluated())
966 for (; __first != __last; ++__first)
971 if (
const size_t __len = __last - __first)
972 __builtin_memset(__first,
static_cast<unsigned char>(__tmp), __len);
975 template<
typename _Ite,
typename _Cont,
typename _Tp>
978 __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first,
979 ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last,
981 { std::__fill_a1(__first.base(), __last.base(), __value); }
983 template<
typename _Tp,
typename _VTp>
985 __fill_a1(
const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
986 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
991 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator,
994 template<
typename _FIte,
typename _Tp>
997 __fill_a(_FIte __first, _FIte __last,
const _Tp& __value)
998 { std::__fill_a1(__first, __last, __value); }
1000 template<
typename _Ite,
typename _Seq,
typename _Cat,
typename _Tp>
1001 _GLIBCXX20_CONSTEXPR
1003 __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
1004 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
1019 template<
typename _ForwardIterator,
typename _Tp>
1020 _GLIBCXX20_CONSTEXPR
1022 fill(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __value)
1025 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1027 __glibcxx_requires_valid_range(__first, __last);
1029 std::__fill_a(__first, __last, __value);
1033 inline _GLIBCXX_CONSTEXPR
int
1034 __size_to_integer(
int __n) {
return __n; }
1035 inline _GLIBCXX_CONSTEXPR
unsigned
1036 __size_to_integer(
unsigned __n) {
return __n; }
1037 inline _GLIBCXX_CONSTEXPR
long
1038 __size_to_integer(
long __n) {
return __n; }
1039 inline _GLIBCXX_CONSTEXPR
unsigned long
1040 __size_to_integer(
unsigned long __n) {
return __n; }
1041 inline _GLIBCXX_CONSTEXPR
long long
1042 __size_to_integer(
long long __n) {
return __n; }
1043 inline _GLIBCXX_CONSTEXPR
unsigned long long
1044 __size_to_integer(
unsigned long long __n) {
return __n; }
1046#if defined(__GLIBCXX_TYPE_INT_N_0)
1047 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
1048 __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1049 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_0
1050 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1052#if defined(__GLIBCXX_TYPE_INT_N_1)
1053 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
1054 __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1055 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_1
1056 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1058#if defined(__GLIBCXX_TYPE_INT_N_2)
1059 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
1060 __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1061 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_2
1062 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1064#if defined(__GLIBCXX_TYPE_INT_N_3)
1065 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_3
1066 __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1067 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
1068 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1071 inline _GLIBCXX_CONSTEXPR
long long
1072 __size_to_integer(
float __n) {
return (
long long)__n; }
1073 inline _GLIBCXX_CONSTEXPR
long long
1074 __size_to_integer(
double __n) {
return (
long long)__n; }
1075 inline _GLIBCXX_CONSTEXPR
long long
1076 __size_to_integer(
long double __n) {
return (
long long)__n; }
1077#if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128)
1078 __extension__
inline _GLIBCXX_CONSTEXPR
long long
1079 __size_to_integer(__float128 __n) {
return (
long long)__n; }
1082 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1083 _GLIBCXX20_CONSTEXPR
1085 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
1086 __fill_n_a1(_OutputIterator __first, _Size __n,
const _Tp& __value)
1088 for (; __n > 0; --__n, (void) ++__first)
1093 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1094 _GLIBCXX20_CONSTEXPR
1096 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
1097 __fill_n_a1(_OutputIterator __first, _Size __n,
const _Tp& __value)
1099 const _Tp __tmp = __value;
1100 for (; __n > 0; --__n, (void) ++__first)
1105 template<
typename _Ite,
typename _Seq,
typename _Cat,
typename _Size,
1107 _GLIBCXX20_CONSTEXPR
1108 ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
1109 __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
1110 _Size __n,
const _Tp& __value,
1113 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1114 _GLIBCXX20_CONSTEXPR
1115 inline _OutputIterator
1116 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1119#if __cplusplus >= 201103L
1120 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1122 return __fill_n_a1(__first, __n, __value);
1125 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1126 _GLIBCXX20_CONSTEXPR
1127 inline _OutputIterator
1128 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1131#if __cplusplus >= 201103L
1132 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1134 return __fill_n_a1(__first, __n, __value);
1137 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1138 _GLIBCXX20_CONSTEXPR
1139 inline _OutputIterator
1140 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1143#if __cplusplus >= 201103L
1144 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1149 __glibcxx_requires_can_increment(__first, __n);
1151 std::__fill_a(__first, __first + __n, __value);
1152 return __first + __n;
1172 template<
typename _OI,
typename _Size,
typename _Tp>
1173 _GLIBCXX20_CONSTEXPR
1175 fill_n(_OI __first, _Size __n,
const _Tp& __value)
1178 __glibcxx_function_requires(_OutputIteratorConcept<_OI, const _Tp&>)
1180 return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
1184 template<
bool _BoolType>
1187 template<
typename _II1,
typename _II2>
1188 _GLIBCXX20_CONSTEXPR
1190 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1192 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1193 if (!(*__first1 == *__first2))
1200 struct __equal<true>
1202 template<
typename _Tp>
1203 _GLIBCXX20_CONSTEXPR
1205 equal(
const _Tp* __first1,
const _Tp* __last1,
const _Tp* __first2)
1207 if (
const size_t __len = (__last1 - __first1))
1208 return !std::__memcmp(__first1, __first2, __len);
1213 template<
typename _Tp,
typename _Ref,
typename _Ptr,
typename _II>
1214 typename __gnu_cxx::__enable_if<
1215 __is_random_access_iter<_II>::__value,
bool>::__type
1216 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1217 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1220 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1221 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1223 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1224 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1225 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1227 template<
typename _II,
typename _Tp,
typename _Ref,
typename _Ptr>
1228 typename __gnu_cxx::__enable_if<
1229 __is_random_access_iter<_II>::__value,
bool>::__type
1230 __equal_aux1(_II, _II,
1231 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>);
1233 template<
typename _II1,
typename _II2>
1234 _GLIBCXX20_CONSTEXPR
1236 __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
1238 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1239 const bool __simple = ((__is_integer<_ValueType1>::__value
1240 || __is_pointer<_ValueType1>::__value)
1241 && __memcmpable<_II1, _II2>::__value);
1242 return std::__equal<__simple>::equal(__first1, __last1, __first2);
1245 template<
typename _II1,
typename _II2>
1246 _GLIBCXX20_CONSTEXPR
1248 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
1250 return std::__equal_aux1(std::__niter_base(__first1),
1251 std::__niter_base(__last1),
1252 std::__niter_base(__first2));
1255 template<
typename _II1,
typename _Seq1,
typename _Cat1,
typename _II2>
1256 _GLIBCXX20_CONSTEXPR
1258 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1259 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1262 template<
typename _II1,
typename _II2,
typename _Seq2,
typename _Cat2>
1263 _GLIBCXX20_CONSTEXPR
1265 __equal_aux(_II1, _II1,
1266 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1268 template<
typename _II1,
typename _Seq1,
typename _Cat1,
1269 typename _II2,
typename _Seq2,
typename _Cat2>
1270 _GLIBCXX20_CONSTEXPR
1272 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1273 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1274 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1276 template<
typename,
typename>
1279 template<
typename _II1,
typename _II2>
1280 _GLIBCXX20_CONSTEXPR
1282 __newlast1(_II1, _II1 __last1, _II2, _II2)
1285 template<
typename _II>
1286 _GLIBCXX20_CONSTEXPR
1288 __cnd2(_II __first, _II __last)
1289 {
return __first != __last; }
1293 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
1295 template<
typename _RAI1,
typename _RAI2>
1296 _GLIBCXX20_CONSTEXPR
1298 __newlast1(_RAI1 __first1, _RAI1 __last1,
1299 _RAI2 __first2, _RAI2 __last2)
1301 const typename iterator_traits<_RAI1>::difference_type
1302 __diff1 = __last1 - __first1;
1303 const typename iterator_traits<_RAI2>::difference_type
1304 __diff2 = __last2 - __first2;
1305 return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
1308 template<
typename _RAI>
1309 static _GLIBCXX20_CONSTEXPR
bool
1314 template<
typename _II1,
typename _II2,
typename _Compare>
1315 _GLIBCXX20_CONSTEXPR
1317 __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
1318 _II2 __first2, _II2 __last2,
1321 typedef typename iterator_traits<_II1>::iterator_category _Category1;
1322 typedef typename iterator_traits<_II2>::iterator_category _Category2;
1323 typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1325 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1326 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1327 ++__first1, (void)++__first2)
1329 if (__comp(__first1, __first2))
1331 if (__comp(__first2, __first1))
1334 return __first1 == __last1 && __first2 != __last2;
1337 template<
bool _BoolType>
1338 struct __lexicographical_compare
1340 template<
typename _II1,
typename _II2>
1341 _GLIBCXX20_CONSTEXPR
1343 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1345 using __gnu_cxx::__ops::__iter_less_iter;
1346 return std::__lexicographical_compare_impl(__first1, __last1,
1348 __iter_less_iter());
1351 template<
typename _II1,
typename _II2>
1352 _GLIBCXX20_CONSTEXPR
1354 __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1356 while (__first1 != __last1)
1358 if (__first2 == __last2)
1360 if (*__first1 < *__first2)
1362 if (*__first2 < *__first1)
1367 return int(__first2 == __last2) - 1;
1372 struct __lexicographical_compare<true>
1374 template<
typename _Tp,
typename _Up>
1375 _GLIBCXX20_CONSTEXPR
1377 __lc(
const _Tp* __first1,
const _Tp* __last1,
1378 const _Up* __first2,
const _Up* __last2)
1379 {
return __3way(__first1, __last1, __first2, __last2) < 0; }
1381 template<
typename _Tp,
typename _Up>
1382 _GLIBCXX20_CONSTEXPR
1384 __3way(
const _Tp* __first1,
const _Tp* __last1,
1385 const _Up* __first2,
const _Up* __last2)
1387 const size_t __len1 = __last1 - __first1;
1388 const size_t __len2 = __last2 - __first2;
1389 if (
const size_t __len =
std::min(__len1, __len2))
1390 if (
int __result = std::__memcmp(__first1, __first2, __len))
1392 return ptrdiff_t(__len1 - __len2);
1396 template<
typename _II1,
typename _II2>
1397 _GLIBCXX20_CONSTEXPR
1399 __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
1400 _II2 __first2, _II2 __last2)
1402 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1403 typedef typename iterator_traits<_II2>::value_type _ValueType2;
1404 const bool __simple =
1405 (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
1406 && __is_pointer<_II1>::__value
1407 && __is_pointer<_II2>::__value
1408#if __cplusplus > 201703L && __glibcxx_concepts
1412 && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>>
1413 && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>>
1417 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
1421 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1424 __lexicographical_compare_aux1(
1425 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1426 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1429 template<
typename _Tp1,
1430 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1432 __lexicographical_compare_aux1(_Tp1*, _Tp1*,
1433 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1434 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1436 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1437 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1439 __lexicographical_compare_aux1(
1440 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1441 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1442 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1443 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1445 template<
typename _II1,
typename _II2>
1446 _GLIBCXX20_CONSTEXPR
1448 __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
1449 _II2 __first2, _II2 __last2)
1451 return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
1452 std::__niter_base(__last1),
1453 std::__niter_base(__first2),
1454 std::__niter_base(__last2));
1457 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
1459 _GLIBCXX20_CONSTEXPR
1461 __lexicographical_compare_aux(
1462 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1463 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1466 template<
typename _II1,
1467 typename _Iter2,
typename _Seq2,
typename _Cat2>
1468 _GLIBCXX20_CONSTEXPR
1470 __lexicographical_compare_aux(
1472 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1473 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1475 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
1476 typename _Iter2,
typename _Seq2,
typename _Cat2>
1477 _GLIBCXX20_CONSTEXPR
1479 __lexicographical_compare_aux(
1480 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1481 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1482 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1483 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1485 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1486 _GLIBCXX20_CONSTEXPR
1488 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1489 const _Tp& __val, _Compare __comp)
1491 typedef typename iterator_traits<_ForwardIterator>::difference_type
1498 _DistanceType __half = __len >> 1;
1499 _ForwardIterator __middle = __first;
1501 if (__comp(__middle, __val))
1505 __len = __len - __half - 1;
1524 template<
typename _ForwardIterator,
typename _Tp>
1525 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1526 inline _ForwardIterator
1527 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1531 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1532 __glibcxx_function_requires(_LessThanOpConcept<
1534 __glibcxx_requires_partitioned_lower(__first, __last, __val);
1536 return std::__lower_bound(__first, __last, __val,
1537 __gnu_cxx::__ops::__iter_less_val());
1542 template<
typename _Tp>
1543 inline _GLIBCXX_CONSTEXPR _Tp
1546#if __cplusplus >= 201402L
1550 return (
sizeof(+__n) * __CHAR_BIT__ - 1)
1551 - (
sizeof(+__n) ==
sizeof(
long long)
1552 ? __builtin_clzll(+__n)
1553 : (
sizeof(+__n) ==
sizeof(long)
1554 ? __builtin_clzl(+__n)
1555 : __builtin_clz(+__n)));
1559_GLIBCXX_BEGIN_NAMESPACE_ALGO
1573 template<
typename _II1,
typename _II2>
1574 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1576 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1579 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1580 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1581 __glibcxx_function_requires(_EqualOpConcept<
1584 __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
1586 return std::__equal_aux(__first1, __last1, __first2);
1604 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1605 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1607 equal(_IIter1 __first1, _IIter1 __last1,
1608 _IIter2 __first2, _BinaryPredicate __binary_pred)
1611 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1612 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1613 __glibcxx_requires_valid_range(__first1, __last1);
1615 for (; __first1 != __last1; ++__first1, (void)++__first2)
1616 if (!
bool(__binary_pred(*__first1, *__first2)))
1621#if __cplusplus >= 201103L
1622#pragma GCC diagnostic push
1623#pragma GCC diagnostic ignored "-Wc++17-extensions"
1626 template<
typename _II1,
typename _II2>
1627 _GLIBCXX20_CONSTEXPR
1629 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1631 using _RATag = random_access_iterator_tag;
1632 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1633 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1634 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1635 if constexpr (_RAIters::value)
1637 if ((__last1 - __first1) != (__last2 - __first2))
1639 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1643 for (; __first1 != __last1 && __first2 != __last2;
1644 ++__first1, (void)++__first2)
1645 if (!(*__first1 == *__first2))
1647 return __first1 == __last1 && __first2 == __last2;
1652 template<
typename _II1,
typename _II2,
typename _BinaryPredicate>
1653 _GLIBCXX20_CONSTEXPR
1655 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2,
1656 _BinaryPredicate __binary_pred)
1658 using _RATag = random_access_iterator_tag;
1659 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1660 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1661 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1662 if constexpr (_RAIters::value)
1664 if ((__last1 - __first1) != (__last2 - __first2))
1666 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1671 for (; __first1 != __last1 && __first2 != __last2;
1672 ++__first1, (void)++__first2)
1673 if (!
bool(__binary_pred(*__first1, *__first2)))
1675 return __first1 == __last1 && __first2 == __last2;
1678#pragma GCC diagnostic pop
1681#ifdef __glibcxx_robust_nonmodifying_seq_ops
1695 template<
typename _II1,
typename _II2>
1696 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1698 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1701 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1702 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1703 __glibcxx_function_requires(_EqualOpConcept<
1706 __glibcxx_requires_valid_range(__first1, __last1);
1707 __glibcxx_requires_valid_range(__first2, __last2);
1709 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2);
1728 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1729 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1731 equal(_IIter1 __first1, _IIter1 __last1,
1732 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
1735 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1736 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1737 __glibcxx_requires_valid_range(__first1, __last1);
1738 __glibcxx_requires_valid_range(__first2, __last2);
1740 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2,
1760 template<
typename _II1,
typename _II2>
1761 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1763 lexicographical_compare(_II1 __first1, _II1 __last1,
1764 _II2 __first2, _II2 __last2)
1766#ifdef _GLIBCXX_CONCEPT_CHECKS
1771 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1772 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1773 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1774 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1775 __glibcxx_requires_valid_range(__first1, __last1);
1776 __glibcxx_requires_valid_range(__first2, __last2);
1778 return std::__lexicographical_compare_aux(__first1, __last1,
1795 template<
typename _II1,
typename _II2,
typename _Compare>
1796 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1798 lexicographical_compare(_II1 __first1, _II1 __last1,
1799 _II2 __first2, _II2 __last2, _Compare __comp)
1802 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1803 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1804 __glibcxx_requires_valid_range(__first1, __last1);
1805 __glibcxx_requires_valid_range(__first2, __last2);
1807 return std::__lexicographical_compare_impl
1808 (__first1, __last1, __first2, __last2,
1809 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1812#if __cpp_lib_three_way_comparison
1816 template<
typename _Iter1,
typename _Iter2>
1817 concept __memcmp_ordered_with
1818 = (__is_memcmp_ordered_with<iter_value_t<_Iter1>,
1819 iter_value_t<_Iter2>>::__value)
1820 && contiguous_iterator<_Iter1> && contiguous_iterator<_Iter2>;
1824 template<
typename _Tp>
1826 __min_cmp(_Tp __x, _Tp __y)
1830 decltype(__x <=> __y) _M_cmp;
1832 auto __c = __x <=> __y;
1834 return _Res{__y, __c};
1835 return _Res{__x, __c};
1849 template<
typename _InputIter1,
typename _InputIter2,
typename _Comp>
1850 [[nodiscard]]
constexpr auto
1852 _InputIter1 __last1,
1853 _InputIter2 __first2,
1854 _InputIter2 __last2,
1856 ->
decltype(__comp(*__first1, *__first2))
1859 __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
1860 __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
1861 __glibcxx_requires_valid_range(__first1, __last1);
1862 __glibcxx_requires_valid_range(__first2, __last2);
1864 using _Cat =
decltype(__comp(*__first1, *__first2));
1865 static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
1867 if (!std::__is_constant_evaluated())
1868 if constexpr (same_as<_Comp, __detail::_Synth3way>
1869 || same_as<_Comp, compare_three_way>)
1870 if constexpr (__memcmp_ordered_with<_InputIter1, _InputIter2>)
1872 const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1873 __min_cmp(__last1 - __first1, __last2 - __first2);
1876 const auto __blen = __len *
sizeof(*__first1);
1878 = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 0;
1885 while (__first1 != __last1)
1887 if (__first2 == __last2)
1888 return strong_ordering::greater;
1889 if (
auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
1894 return (__first2 == __last2) <=>
true;
1897 template<
typename _InputIter1,
typename _InputIter2>
1900 _InputIter1 __last1,
1901 _InputIter2 __first2,
1902 _InputIter2 __last2)
1904 return _GLIBCXX_STD_A::
1905 lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
1906 compare_three_way{});
1910 template<
typename _InputIterator1,
typename _InputIterator2,
1911 typename _BinaryPredicate>
1912 _GLIBCXX20_CONSTEXPR
1914 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1915 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1917 while (__first1 != __last1 && __binary_pred(__first1, __first2))
1938 template<
typename _InputIterator1,
typename _InputIterator2>
1939 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1941 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1942 _InputIterator2 __first2)
1945 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1946 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1947 __glibcxx_function_requires(_EqualOpConcept<
1950 __glibcxx_requires_valid_range(__first1, __last1);
1952 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1953 __gnu_cxx::__ops::__iter_equal_to_iter());
1972 template<
typename _InputIterator1,
typename _InputIterator2,
1973 typename _BinaryPredicate>
1974 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1976 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1977 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1980 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1981 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1982 __glibcxx_requires_valid_range(__first1, __last1);
1984 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1985 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1988#if __glibcxx_robust_nonmodifying_seq_ops
1989 template<
typename _InputIterator1,
typename _InputIterator2,
1990 typename _BinaryPredicate>
1991 _GLIBCXX20_CONSTEXPR
1993 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1994 _InputIterator2 __first2, _InputIterator2 __last2,
1995 _BinaryPredicate __binary_pred)
1997 while (__first1 != __last1 && __first2 != __last2
1998 && __binary_pred(__first1, __first2))
2020 template<
typename _InputIterator1,
typename _InputIterator2>
2021 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2023 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2024 _InputIterator2 __first2, _InputIterator2 __last2)
2027 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2028 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2029 __glibcxx_function_requires(_EqualOpConcept<
2032 __glibcxx_requires_valid_range(__first1, __last1);
2033 __glibcxx_requires_valid_range(__first2, __last2);
2035 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2036 __gnu_cxx::__ops::__iter_equal_to_iter());
2056 template<
typename _InputIterator1,
typename _InputIterator2,
2057 typename _BinaryPredicate>
2058 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2060 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2061 _InputIterator2 __first2, _InputIterator2 __last2,
2062 _BinaryPredicate __binary_pred)
2065 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2066 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2067 __glibcxx_requires_valid_range(__first1, __last1);
2068 __glibcxx_requires_valid_range(__first2, __last2);
2070 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2071 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
2075_GLIBCXX_END_NAMESPACE_ALGO
2078 template<
typename _InputIterator,
typename _Predicate>
2079 _GLIBCXX20_CONSTEXPR
2080 inline _InputIterator
2084 while (__first != __last && !__pred(__first))
2090 template<
typename _RandomAccessIterator,
typename _Predicate>
2091 _GLIBCXX20_CONSTEXPR
2092 _RandomAccessIterator
2093 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
2097 __trip_count = (__last - __first) >> 2;
2099 for (; __trip_count > 0; --__trip_count)
2101 if (__pred(__first))
2105 if (__pred(__first))
2109 if (__pred(__first))
2113 if (__pred(__first))
2118 switch (__last - __first)
2121 if (__pred(__first))
2126 if (__pred(__first))
2131 if (__pred(__first))
2141 template<
typename _Iterator,
typename _Predicate>
2142 _GLIBCXX20_CONSTEXPR
2144 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
2146 return __find_if(__first, __last, __pred,
2150 template<
typename _InputIterator,
typename _Predicate>
2151 _GLIBCXX20_CONSTEXPR
2152 typename iterator_traits<_InputIterator>::difference_type
2153 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2155 typename iterator_traits<_InputIterator>::difference_type __n = 0;
2156 for (; __first != __last; ++__first)
2157 if (__pred(__first))
2162 template<
typename _ForwardIterator,
typename _Predicate>
2163 _GLIBCXX20_CONSTEXPR
2165 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
2169 if (__first == __last)
2171 _ForwardIterator __result = __first;
2173 for (; __first != __last; ++__first)
2174 if (!__pred(__first))
2176 *__result = _GLIBCXX_MOVE(*__first);
2182 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2183 typename _BinaryPredicate>
2184 _GLIBCXX20_CONSTEXPR
2186 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2187 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2188 _BinaryPredicate __predicate)
2191 if (__first1 == __last1 || __first2 == __last2)
2195 _ForwardIterator2 __p1(__first2);
2196 if (++__p1 == __last2)
2198 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2201 _ForwardIterator1 __current = __first1;
2207 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2209 if (__first1 == __last1)
2212 _ForwardIterator2 __p = __p1;
2213 __current = __first1;
2214 if (++__current == __last1)
2217 while (__predicate(__current, __p))
2219 if (++__p == __last2)
2221 if (++__current == __last1)
2229#if __cplusplus >= 201103L
2230 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2231 typename _BinaryPredicate>
2232 _GLIBCXX20_CONSTEXPR
2234 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2235 _ForwardIterator2 __first2, _BinaryPredicate __pred)
2239 for (; __first1 != __last1; ++__first1, (void)++__first2)
2240 if (!__pred(__first1, __first2))
2243 if (__first1 == __last1)
2248 _ForwardIterator2 __last2 = __first2;
2250 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
2253 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
2257 = std::__count_if(__first2, __last2,
2258 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
2259 if (0 == __matches ||
2260 std::__count_if(__scan, __last1,
2261 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
2280 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
2281 _GLIBCXX20_CONSTEXPR
2283 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2284 _ForwardIterator2 __first2)
2287 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2288 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2289 __glibcxx_function_requires(_EqualOpConcept<
2292 __glibcxx_requires_valid_range(__first1, __last1);
2294 return std::__is_permutation(__first1, __last1, __first2,
2295 __gnu_cxx::__ops::__iter_equal_to_iter());
2299_GLIBCXX_BEGIN_NAMESPACE_ALGO
2322 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2323 typename _BinaryPredicate>
2324 _GLIBCXX20_CONSTEXPR
2325 inline _ForwardIterator1
2326 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2327 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2328 _BinaryPredicate __predicate)
2331 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2332 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2333 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
2336 __glibcxx_requires_valid_range(__first1, __last1);
2337 __glibcxx_requires_valid_range(__first2, __last2);
2339 return std::__search(__first1, __last1, __first2, __last2,
2340 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
2343_GLIBCXX_END_NAMESPACE_ALGO
2344_GLIBCXX_END_NAMESPACE_VERSION
2350#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.
pair(_T1, _T2) -> pair< _T1, _T2 >
Two pairs of the same type are equal iff their members are equal.
auto declval() noexcept -> decltype(__declval< _Tp >(0))
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.