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>
334 decltype(std::__niter_base(std::declval<_Ite>()))
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) && !defined(__CUDACC__)
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
1623 template<
typename _II1,
typename _II2>
1624 _GLIBCXX20_CONSTEXPR
1626 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1628 using _RATag = random_access_iterator_tag;
1629 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1630 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1631 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1638 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1641 for (; __first1 != __last1 && __first2 != __last2;
1642 ++__first1, (void)++__first2)
1643 if (!(*__first1 == *__first2))
1645 return __first1 == __last1 && __first2 == __last2;
1649 template<
typename _II1,
typename _II2,
typename _BinaryPredicate>
1650 _GLIBCXX20_CONSTEXPR
1652 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2,
1653 _BinaryPredicate __binary_pred)
1655 using _RATag = random_access_iterator_tag;
1656 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1657 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1658 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1665 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1669 for (; __first1 != __last1 && __first2 != __last2;
1670 ++__first1, (void)++__first2)
1671 if (!
bool(__binary_pred(*__first1, *__first2)))
1673 return __first1 == __last1 && __first2 == __last2;
1677#ifdef __glibcxx_robust_nonmodifying_seq_ops
1691 template<
typename _II1,
typename _II2>
1692 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1694 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1697 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1698 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1699 __glibcxx_function_requires(_EqualOpConcept<
1702 __glibcxx_requires_valid_range(__first1, __last1);
1703 __glibcxx_requires_valid_range(__first2, __last2);
1705 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2);
1724 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1725 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1727 equal(_IIter1 __first1, _IIter1 __last1,
1728 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
1731 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1732 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1733 __glibcxx_requires_valid_range(__first1, __last1);
1734 __glibcxx_requires_valid_range(__first2, __last2);
1736 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2,
1756 template<
typename _II1,
typename _II2>
1757 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1759 lexicographical_compare(_II1 __first1, _II1 __last1,
1760 _II2 __first2, _II2 __last2)
1762#ifdef _GLIBCXX_CONCEPT_CHECKS
1767 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1768 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1769 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1770 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1771 __glibcxx_requires_valid_range(__first1, __last1);
1772 __glibcxx_requires_valid_range(__first2, __last2);
1774 return std::__lexicographical_compare_aux(__first1, __last1,
1791 template<
typename _II1,
typename _II2,
typename _Compare>
1792 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1794 lexicographical_compare(_II1 __first1, _II1 __last1,
1795 _II2 __first2, _II2 __last2, _Compare __comp)
1798 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1799 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1800 __glibcxx_requires_valid_range(__first1, __last1);
1801 __glibcxx_requires_valid_range(__first2, __last2);
1803 return std::__lexicographical_compare_impl
1804 (__first1, __last1, __first2, __last2,
1805 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1808#if __cpp_lib_three_way_comparison
1812 template<
typename _Iter1,
typename _Iter2>
1813 concept __memcmp_ordered_with
1814 = (__is_memcmp_ordered_with<iter_value_t<_Iter1>,
1815 iter_value_t<_Iter2>>::__value)
1816 && contiguous_iterator<_Iter1> && contiguous_iterator<_Iter2>;
1820 template<
typename _Tp>
1822 __min_cmp(_Tp __x, _Tp __y)
1826 decltype(__x <=> __y) _M_cmp;
1828 auto __c = __x <=> __y;
1830 return _Res{__y, __c};
1831 return _Res{__x, __c};
1845 template<
typename _InputIter1,
typename _InputIter2,
typename _Comp>
1846 [[nodiscard]]
constexpr auto
1848 _InputIter1 __last1,
1849 _InputIter2 __first2,
1850 _InputIter2 __last2,
1852 ->
decltype(__comp(*__first1, *__first2))
1855 __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
1856 __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
1857 __glibcxx_requires_valid_range(__first1, __last1);
1858 __glibcxx_requires_valid_range(__first2, __last2);
1860 using _Cat =
decltype(__comp(*__first1, *__first2));
1861 static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
1863 if (!std::__is_constant_evaluated())
1864 if constexpr (same_as<_Comp, __detail::_Synth3way>
1865 || same_as<_Comp, compare_three_way>)
1866 if constexpr (__memcmp_ordered_with<_InputIter1, _InputIter2>)
1868 const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1869 __min_cmp(__last1 - __first1, __last2 - __first2);
1872 const auto __blen = __len *
sizeof(*__first1);
1874 = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 0;
1881 while (__first1 != __last1)
1883 if (__first2 == __last2)
1884 return strong_ordering::greater;
1885 if (
auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
1890 return (__first2 == __last2) <=>
true;
1893 template<
typename _InputIter1,
typename _InputIter2>
1896 _InputIter1 __last1,
1897 _InputIter2 __first2,
1898 _InputIter2 __last2)
1900 return _GLIBCXX_STD_A::
1901 lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
1902 compare_three_way{});
1906 template<
typename _InputIterator1,
typename _InputIterator2,
1907 typename _BinaryPredicate>
1908 _GLIBCXX20_CONSTEXPR
1909 pair<_InputIterator1, _InputIterator2>
1910 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1911 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1913 while (__first1 != __last1 && __binary_pred(__first1, __first2))
1918 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1934 template<
typename _InputIterator1,
typename _InputIterator2>
1935 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1936 inline pair<_InputIterator1, _InputIterator2>
1937 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1938 _InputIterator2 __first2)
1941 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1942 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1943 __glibcxx_function_requires(_EqualOpConcept<
1946 __glibcxx_requires_valid_range(__first1, __last1);
1948 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1949 __gnu_cxx::__ops::__iter_equal_to_iter());
1968 template<
typename _InputIterator1,
typename _InputIterator2,
1969 typename _BinaryPredicate>
1970 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1971 inline pair<_InputIterator1, _InputIterator2>
1972 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1973 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1976 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1977 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1978 __glibcxx_requires_valid_range(__first1, __last1);
1980 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1981 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1984#if __glibcxx_robust_nonmodifying_seq_ops
1985 template<
typename _InputIterator1,
typename _InputIterator2,
1986 typename _BinaryPredicate>
1987 _GLIBCXX20_CONSTEXPR
1988 pair<_InputIterator1, _InputIterator2>
1989 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1990 _InputIterator2 __first2, _InputIterator2 __last2,
1991 _BinaryPredicate __binary_pred)
1993 while (__first1 != __last1 && __first2 != __last2
1994 && __binary_pred(__first1, __first2))
1999 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
2016 template<
typename _InputIterator1,
typename _InputIterator2>
2017 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2018 inline pair<_InputIterator1, _InputIterator2>
2019 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2020 _InputIterator2 __first2, _InputIterator2 __last2)
2023 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2024 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2025 __glibcxx_function_requires(_EqualOpConcept<
2028 __glibcxx_requires_valid_range(__first1, __last1);
2029 __glibcxx_requires_valid_range(__first2, __last2);
2031 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2032 __gnu_cxx::__ops::__iter_equal_to_iter());
2052 template<
typename _InputIterator1,
typename _InputIterator2,
2053 typename _BinaryPredicate>
2054 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2055 inline pair<_InputIterator1, _InputIterator2>
2056 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2057 _InputIterator2 __first2, _InputIterator2 __last2,
2058 _BinaryPredicate __binary_pred)
2061 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2062 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2063 __glibcxx_requires_valid_range(__first1, __last1);
2064 __glibcxx_requires_valid_range(__first2, __last2);
2066 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2067 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
2071_GLIBCXX_END_NAMESPACE_ALGO
2074 template<
typename _InputIterator,
typename _Predicate>
2075 _GLIBCXX20_CONSTEXPR
2076 inline _InputIterator
2080 while (__first != __last && !__pred(__first))
2086 template<
typename _RandomAccessIterator,
typename _Predicate>
2087 _GLIBCXX20_CONSTEXPR
2088 _RandomAccessIterator
2089 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
2093 __trip_count = (__last - __first) >> 2;
2095 for (; __trip_count > 0; --__trip_count)
2097 if (__pred(__first))
2101 if (__pred(__first))
2105 if (__pred(__first))
2109 if (__pred(__first))
2114 switch (__last - __first)
2117 if (__pred(__first))
2122 if (__pred(__first))
2127 if (__pred(__first))
2137 template<
typename _Iterator,
typename _Predicate>
2138 _GLIBCXX20_CONSTEXPR
2140 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
2142 return __find_if(__first, __last, __pred,
2146 template<
typename _InputIterator,
typename _Predicate>
2147 _GLIBCXX20_CONSTEXPR
2148 typename iterator_traits<_InputIterator>::difference_type
2149 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2151 typename iterator_traits<_InputIterator>::difference_type __n = 0;
2152 for (; __first != __last; ++__first)
2153 if (__pred(__first))
2158 template<
typename _ForwardIterator,
typename _Predicate>
2159 _GLIBCXX20_CONSTEXPR
2161 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
2165 if (__first == __last)
2167 _ForwardIterator __result = __first;
2169 for (; __first != __last; ++__first)
2170 if (!__pred(__first))
2172 *__result = _GLIBCXX_MOVE(*__first);
2178 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2179 typename _BinaryPredicate>
2180 _GLIBCXX20_CONSTEXPR
2182 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2183 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2184 _BinaryPredicate __predicate)
2187 if (__first1 == __last1 || __first2 == __last2)
2191 _ForwardIterator2 __p1(__first2);
2192 if (++__p1 == __last2)
2194 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2197 _ForwardIterator1 __current = __first1;
2203 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2205 if (__first1 == __last1)
2208 _ForwardIterator2 __p = __p1;
2209 __current = __first1;
2210 if (++__current == __last1)
2213 while (__predicate(__current, __p))
2215 if (++__p == __last2)
2217 if (++__current == __last1)
2225#if __cplusplus >= 201103L
2226 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2227 typename _BinaryPredicate>
2228 _GLIBCXX20_CONSTEXPR
2230 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2231 _ForwardIterator2 __first2, _BinaryPredicate __pred)
2235 for (; __first1 != __last1; ++__first1, (void)++__first2)
2236 if (!__pred(__first1, __first2))
2239 if (__first1 == __last1)
2244 _ForwardIterator2 __last2 = __first2;
2246 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
2249 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
2253 = std::__count_if(__first2, __last2,
2254 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
2255 if (0 == __matches ||
2256 std::__count_if(__scan, __last1,
2257 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
2276 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
2277 _GLIBCXX20_CONSTEXPR
2279 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2280 _ForwardIterator2 __first2)
2283 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2284 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2285 __glibcxx_function_requires(_EqualOpConcept<
2288 __glibcxx_requires_valid_range(__first1, __last1);
2290 return std::__is_permutation(__first1, __last1, __first2,
2291 __gnu_cxx::__ops::__iter_equal_to_iter());
2295_GLIBCXX_BEGIN_NAMESPACE_ALGO
2318 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2319 typename _BinaryPredicate>
2320 _GLIBCXX20_CONSTEXPR
2321 inline _ForwardIterator1
2322 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2323 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2324 _BinaryPredicate __predicate)
2327 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2328 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2329 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
2332 __glibcxx_requires_valid_range(__first1, __last1);
2333 __glibcxx_requires_valid_range(__first2, __last2);
2335 return std::__search(__first1, __last1, __first2, __last2,
2336 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
2339_GLIBCXX_END_NAMESPACE_ALGO
2340_GLIBCXX_END_NAMESPACE_VERSION
2346#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.