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);
1032#pragma GCC diagnostic push
1033#pragma GCC diagnostic ignored "-Wlong-long"
1035 inline _GLIBCXX_CONSTEXPR
int
1036 __size_to_integer(
int __n) {
return __n; }
1037 inline _GLIBCXX_CONSTEXPR
unsigned
1038 __size_to_integer(
unsigned __n) {
return __n; }
1039 inline _GLIBCXX_CONSTEXPR
long
1040 __size_to_integer(
long __n) {
return __n; }
1041 inline _GLIBCXX_CONSTEXPR
unsigned long
1042 __size_to_integer(
unsigned long __n) {
return __n; }
1043 inline _GLIBCXX_CONSTEXPR
long long
1044 __size_to_integer(
long long __n) {
return __n; }
1045 inline _GLIBCXX_CONSTEXPR
unsigned long long
1046 __size_to_integer(
unsigned long long __n) {
return __n; }
1048#if defined(__GLIBCXX_TYPE_INT_N_0)
1049 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
1050 __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1051 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_0
1052 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1054#if defined(__GLIBCXX_TYPE_INT_N_1)
1055 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
1056 __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1057 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_1
1058 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1060#if defined(__GLIBCXX_TYPE_INT_N_2)
1061 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
1062 __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1063 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_2
1064 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1066#if defined(__GLIBCXX_TYPE_INT_N_3)
1067 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_3
1068 __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1069 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
1070 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1073 inline _GLIBCXX_CONSTEXPR
long long
1074 __size_to_integer(
float __n) {
return (
long long)__n; }
1075 inline _GLIBCXX_CONSTEXPR
long long
1076 __size_to_integer(
double __n) {
return (
long long)__n; }
1077 inline _GLIBCXX_CONSTEXPR
long long
1078 __size_to_integer(
long double __n) {
return (
long long)__n; }
1079#if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128)
1080 __extension__
inline _GLIBCXX_CONSTEXPR
long long
1081 __size_to_integer(__float128 __n) {
return (
long long)__n; }
1083#pragma GCC diagnostic pop
1085 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1086 _GLIBCXX20_CONSTEXPR
1088 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
1089 __fill_n_a1(_OutputIterator __first, _Size __n,
const _Tp& __value)
1091 for (; __n > 0; --__n, (void) ++__first)
1096 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1097 _GLIBCXX20_CONSTEXPR
1099 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
1100 __fill_n_a1(_OutputIterator __first, _Size __n,
const _Tp& __value)
1102 const _Tp __tmp = __value;
1103 for (; __n > 0; --__n, (void) ++__first)
1108 template<
typename _Ite,
typename _Seq,
typename _Cat,
typename _Size,
1110 _GLIBCXX20_CONSTEXPR
1111 ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
1112 __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
1113 _Size __n,
const _Tp& __value,
1116 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1117 _GLIBCXX20_CONSTEXPR
1118 inline _OutputIterator
1119 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1122#if __cplusplus >= 201103L
1123 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1125 return __fill_n_a1(__first, __n, __value);
1128 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1129 _GLIBCXX20_CONSTEXPR
1130 inline _OutputIterator
1131 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1134#if __cplusplus >= 201103L
1135 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1137 return __fill_n_a1(__first, __n, __value);
1140 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1141 _GLIBCXX20_CONSTEXPR
1142 inline _OutputIterator
1143 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1146#if __cplusplus >= 201103L
1147 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1152 __glibcxx_requires_can_increment(__first, __n);
1154 std::__fill_a(__first, __first + __n, __value);
1155 return __first + __n;
1175 template<
typename _OI,
typename _Size,
typename _Tp>
1176 _GLIBCXX20_CONSTEXPR
1178 fill_n(_OI __first, _Size __n,
const _Tp& __value)
1181 __glibcxx_function_requires(_OutputIteratorConcept<_OI, const _Tp&>)
1183 return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
1187 template<
bool _BoolType>
1190 template<
typename _II1,
typename _II2>
1191 _GLIBCXX20_CONSTEXPR
1193 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1195 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1196 if (!(*__first1 == *__first2))
1203 struct __equal<true>
1205 template<
typename _Tp>
1206 _GLIBCXX20_CONSTEXPR
1208 equal(
const _Tp* __first1,
const _Tp* __last1,
const _Tp* __first2)
1210 if (
const size_t __len = (__last1 - __first1))
1211 return !std::__memcmp(__first1, __first2, __len);
1216 template<
typename _Tp,
typename _Ref,
typename _Ptr,
typename _II>
1217 typename __gnu_cxx::__enable_if<
1218 __is_random_access_iter<_II>::__value,
bool>::__type
1219 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1220 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1223 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1224 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1226 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1227 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1228 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1230 template<
typename _II,
typename _Tp,
typename _Ref,
typename _Ptr>
1231 typename __gnu_cxx::__enable_if<
1232 __is_random_access_iter<_II>::__value,
bool>::__type
1233 __equal_aux1(_II, _II,
1234 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>);
1236 template<
typename _II1,
typename _II2>
1237 _GLIBCXX20_CONSTEXPR
1239 __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
1241 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1242 const bool __simple = ((__is_integer<_ValueType1>::__value
1243 || __is_pointer<_ValueType1>::__value)
1244 && __memcmpable<_II1, _II2>::__value);
1245 return std::__equal<__simple>::equal(__first1, __last1, __first2);
1248 template<
typename _II1,
typename _II2>
1249 _GLIBCXX20_CONSTEXPR
1251 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
1253 return std::__equal_aux1(std::__niter_base(__first1),
1254 std::__niter_base(__last1),
1255 std::__niter_base(__first2));
1258 template<
typename _II1,
typename _Seq1,
typename _Cat1,
typename _II2>
1259 _GLIBCXX20_CONSTEXPR
1261 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1262 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1265 template<
typename _II1,
typename _II2,
typename _Seq2,
typename _Cat2>
1266 _GLIBCXX20_CONSTEXPR
1268 __equal_aux(_II1, _II1,
1269 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1271 template<
typename _II1,
typename _Seq1,
typename _Cat1,
1272 typename _II2,
typename _Seq2,
typename _Cat2>
1273 _GLIBCXX20_CONSTEXPR
1275 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1276 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1277 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1279 template<
typename,
typename>
1282 template<
typename _II1,
typename _II2>
1283 _GLIBCXX20_CONSTEXPR
1285 __newlast1(_II1, _II1 __last1, _II2, _II2)
1288 template<
typename _II>
1289 _GLIBCXX20_CONSTEXPR
1291 __cnd2(_II __first, _II __last)
1292 {
return __first != __last; }
1296 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
1298 template<
typename _RAI1,
typename _RAI2>
1299 _GLIBCXX20_CONSTEXPR
1301 __newlast1(_RAI1 __first1, _RAI1 __last1,
1302 _RAI2 __first2, _RAI2 __last2)
1304 const typename iterator_traits<_RAI1>::difference_type
1305 __diff1 = __last1 - __first1;
1306 const typename iterator_traits<_RAI2>::difference_type
1307 __diff2 = __last2 - __first2;
1308 return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
1311 template<
typename _RAI>
1312 static _GLIBCXX20_CONSTEXPR
bool
1317 template<
typename _II1,
typename _II2,
typename _Compare>
1318 _GLIBCXX20_CONSTEXPR
1320 __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
1321 _II2 __first2, _II2 __last2,
1324 typedef typename iterator_traits<_II1>::iterator_category _Category1;
1325 typedef typename iterator_traits<_II2>::iterator_category _Category2;
1326 typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1328 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1329 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1330 ++__first1, (void)++__first2)
1332 if (__comp(__first1, __first2))
1334 if (__comp(__first2, __first1))
1337 return __first1 == __last1 && __first2 != __last2;
1340 template<
bool _BoolType>
1341 struct __lexicographical_compare
1343 template<
typename _II1,
typename _II2>
1344 _GLIBCXX20_CONSTEXPR
1346 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1348 using __gnu_cxx::__ops::__iter_less_iter;
1349 return std::__lexicographical_compare_impl(__first1, __last1,
1351 __iter_less_iter());
1354 template<
typename _II1,
typename _II2>
1355 _GLIBCXX20_CONSTEXPR
1357 __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1359 while (__first1 != __last1)
1361 if (__first2 == __last2)
1363 if (*__first1 < *__first2)
1365 if (*__first2 < *__first1)
1370 return int(__first2 == __last2) - 1;
1375 struct __lexicographical_compare<true>
1377 template<
typename _Tp,
typename _Up>
1378 _GLIBCXX20_CONSTEXPR
1380 __lc(
const _Tp* __first1,
const _Tp* __last1,
1381 const _Up* __first2,
const _Up* __last2)
1382 {
return __3way(__first1, __last1, __first2, __last2) < 0; }
1384 template<
typename _Tp,
typename _Up>
1385 _GLIBCXX20_CONSTEXPR
1387 __3way(
const _Tp* __first1,
const _Tp* __last1,
1388 const _Up* __first2,
const _Up* __last2)
1390 const size_t __len1 = __last1 - __first1;
1391 const size_t __len2 = __last2 - __first2;
1392 if (
const size_t __len =
std::min(__len1, __len2))
1393 if (
int __result = std::__memcmp(__first1, __first2, __len))
1395 return ptrdiff_t(__len1 - __len2);
1399 template<
typename _II1,
typename _II2>
1400 _GLIBCXX20_CONSTEXPR
1402 __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
1403 _II2 __first2, _II2 __last2)
1405 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1406 typedef typename iterator_traits<_II2>::value_type _ValueType2;
1407 const bool __simple =
1408 (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
1409 && __is_pointer<_II1>::__value
1410 && __is_pointer<_II2>::__value
1411#if __cplusplus > 201703L && __glibcxx_concepts
1415 && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>>
1416 && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>>
1420 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
1424 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1427 __lexicographical_compare_aux1(
1428 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1429 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1432 template<
typename _Tp1,
1433 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1435 __lexicographical_compare_aux1(_Tp1*, _Tp1*,
1436 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1437 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1439 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1440 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1442 __lexicographical_compare_aux1(
1443 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1444 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1445 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1446 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1448 template<
typename _II1,
typename _II2>
1449 _GLIBCXX20_CONSTEXPR
1451 __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
1452 _II2 __first2, _II2 __last2)
1454 return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
1455 std::__niter_base(__last1),
1456 std::__niter_base(__first2),
1457 std::__niter_base(__last2));
1460 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
1462 _GLIBCXX20_CONSTEXPR
1464 __lexicographical_compare_aux(
1465 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1466 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1469 template<
typename _II1,
1470 typename _Iter2,
typename _Seq2,
typename _Cat2>
1471 _GLIBCXX20_CONSTEXPR
1473 __lexicographical_compare_aux(
1475 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1476 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1478 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
1479 typename _Iter2,
typename _Seq2,
typename _Cat2>
1480 _GLIBCXX20_CONSTEXPR
1482 __lexicographical_compare_aux(
1483 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1484 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1485 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1486 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1488 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1489 _GLIBCXX20_CONSTEXPR
1491 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1492 const _Tp& __val, _Compare __comp)
1494 typedef typename iterator_traits<_ForwardIterator>::difference_type
1501 _DistanceType __half = __len >> 1;
1502 _ForwardIterator __middle = __first;
1504 if (__comp(__middle, __val))
1508 __len = __len - __half - 1;
1527 template<
typename _ForwardIterator,
typename _Tp>
1528 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1529 inline _ForwardIterator
1530 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1534 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1535 __glibcxx_function_requires(_LessThanOpConcept<
1537 __glibcxx_requires_partitioned_lower(__first, __last, __val);
1539 return std::__lower_bound(__first, __last, __val,
1540 __gnu_cxx::__ops::__iter_less_val());
1545 template<
typename _Tp>
1546 inline _GLIBCXX_CONSTEXPR _Tp
1549#if __cplusplus >= 201402L
1552#pragma GCC diagnostic push
1553#pragma GCC diagnostic ignored "-Wlong-long"
1555 return (
sizeof(+__n) * __CHAR_BIT__ - 1)
1556 - (
sizeof(+__n) ==
sizeof(
long long)
1557 ? __builtin_clzll(+__n)
1558 : (
sizeof(+__n) ==
sizeof(long)
1559 ? __builtin_clzl(+__n)
1560 : __builtin_clz(+__n)));
1561#pragma GCC diagnostic pop
1565_GLIBCXX_BEGIN_NAMESPACE_ALGO
1579 template<
typename _II1,
typename _II2>
1580 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1582 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1585 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1586 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1587 __glibcxx_function_requires(_EqualOpConcept<
1590 __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
1592 return std::__equal_aux(__first1, __last1, __first2);
1610 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1611 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1613 equal(_IIter1 __first1, _IIter1 __last1,
1614 _IIter2 __first2, _BinaryPredicate __binary_pred)
1617 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1618 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1619 __glibcxx_requires_valid_range(__first1, __last1);
1621 for (; __first1 != __last1; ++__first1, (void)++__first2)
1622 if (!
bool(__binary_pred(*__first1, *__first2)))
1627#if __cplusplus >= 201103L
1628#pragma GCC diagnostic push
1629#pragma GCC diagnostic ignored "-Wc++17-extensions"
1632 template<
typename _II1,
typename _II2>
1633 _GLIBCXX20_CONSTEXPR
1635 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1637 using _RATag = random_access_iterator_tag;
1638 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1639 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1640 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1641 if constexpr (_RAIters::value)
1643 if ((__last1 - __first1) != (__last2 - __first2))
1645 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1649 for (; __first1 != __last1 && __first2 != __last2;
1650 ++__first1, (void)++__first2)
1651 if (!(*__first1 == *__first2))
1653 return __first1 == __last1 && __first2 == __last2;
1658 template<
typename _II1,
typename _II2,
typename _BinaryPredicate>
1659 _GLIBCXX20_CONSTEXPR
1661 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2,
1662 _BinaryPredicate __binary_pred)
1664 using _RATag = random_access_iterator_tag;
1665 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1666 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1667 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1668 if constexpr (_RAIters::value)
1670 if ((__last1 - __first1) != (__last2 - __first2))
1672 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1677 for (; __first1 != __last1 && __first2 != __last2;
1678 ++__first1, (void)++__first2)
1679 if (!
bool(__binary_pred(*__first1, *__first2)))
1681 return __first1 == __last1 && __first2 == __last2;
1684#pragma GCC diagnostic pop
1687#ifdef __glibcxx_robust_nonmodifying_seq_ops
1701 template<
typename _II1,
typename _II2>
1702 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1704 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1707 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1708 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1709 __glibcxx_function_requires(_EqualOpConcept<
1712 __glibcxx_requires_valid_range(__first1, __last1);
1713 __glibcxx_requires_valid_range(__first2, __last2);
1715 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2);
1734 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1735 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1737 equal(_IIter1 __first1, _IIter1 __last1,
1738 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
1741 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1742 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1743 __glibcxx_requires_valid_range(__first1, __last1);
1744 __glibcxx_requires_valid_range(__first2, __last2);
1746 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2,
1766 template<
typename _II1,
typename _II2>
1767 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1769 lexicographical_compare(_II1 __first1, _II1 __last1,
1770 _II2 __first2, _II2 __last2)
1772#ifdef _GLIBCXX_CONCEPT_CHECKS
1777 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1778 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1779 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1780 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1781 __glibcxx_requires_valid_range(__first1, __last1);
1782 __glibcxx_requires_valid_range(__first2, __last2);
1784 return std::__lexicographical_compare_aux(__first1, __last1,
1801 template<
typename _II1,
typename _II2,
typename _Compare>
1802 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1804 lexicographical_compare(_II1 __first1, _II1 __last1,
1805 _II2 __first2, _II2 __last2, _Compare __comp)
1808 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1809 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1810 __glibcxx_requires_valid_range(__first1, __last1);
1811 __glibcxx_requires_valid_range(__first2, __last2);
1813 return std::__lexicographical_compare_impl
1814 (__first1, __last1, __first2, __last2,
1815 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1818#if __cpp_lib_three_way_comparison
1822 template<
typename _Iter1,
typename _Iter2>
1823 concept __memcmp_ordered_with
1824 = (__is_memcmp_ordered_with<iter_value_t<_Iter1>,
1825 iter_value_t<_Iter2>>::__value)
1826 && contiguous_iterator<_Iter1> && contiguous_iterator<_Iter2>;
1830 template<
typename _Tp>
1832 __min_cmp(_Tp __x, _Tp __y)
1836 decltype(__x <=> __y) _M_cmp;
1838 auto __c = __x <=> __y;
1840 return _Res{__y, __c};
1841 return _Res{__x, __c};
1855 template<
typename _InputIter1,
typename _InputIter2,
typename _Comp>
1856 [[nodiscard]]
constexpr auto
1858 _InputIter1 __last1,
1859 _InputIter2 __first2,
1860 _InputIter2 __last2,
1862 ->
decltype(__comp(*__first1, *__first2))
1865 __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
1866 __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
1867 __glibcxx_requires_valid_range(__first1, __last1);
1868 __glibcxx_requires_valid_range(__first2, __last2);
1870 using _Cat =
decltype(__comp(*__first1, *__first2));
1871 static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
1873 if (!std::__is_constant_evaluated())
1874 if constexpr (same_as<_Comp, __detail::_Synth3way>
1875 || same_as<_Comp, compare_three_way>)
1876 if constexpr (__memcmp_ordered_with<_InputIter1, _InputIter2>)
1878 const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1879 __min_cmp(__last1 - __first1, __last2 - __first2);
1882 const auto __blen = __len *
sizeof(*__first1);
1884 = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 0;
1891 while (__first1 != __last1)
1893 if (__first2 == __last2)
1894 return strong_ordering::greater;
1895 if (
auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
1900 return (__first2 == __last2) <=>
true;
1903 template<
typename _InputIter1,
typename _InputIter2>
1906 _InputIter1 __last1,
1907 _InputIter2 __first2,
1908 _InputIter2 __last2)
1910 return _GLIBCXX_STD_A::
1911 lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
1912 compare_three_way{});
1916 template<
typename _InputIterator1,
typename _InputIterator2,
1917 typename _BinaryPredicate>
1918 _GLIBCXX20_CONSTEXPR
1920 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1921 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1923 while (__first1 != __last1 && __binary_pred(__first1, __first2))
1944 template<
typename _InputIterator1,
typename _InputIterator2>
1945 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1947 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1948 _InputIterator2 __first2)
1951 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1952 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1953 __glibcxx_function_requires(_EqualOpConcept<
1956 __glibcxx_requires_valid_range(__first1, __last1);
1958 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1959 __gnu_cxx::__ops::__iter_equal_to_iter());
1978 template<
typename _InputIterator1,
typename _InputIterator2,
1979 typename _BinaryPredicate>
1980 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1982 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1983 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1986 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1987 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1988 __glibcxx_requires_valid_range(__first1, __last1);
1990 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1991 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1994#if __glibcxx_robust_nonmodifying_seq_ops
1995 template<
typename _InputIterator1,
typename _InputIterator2,
1996 typename _BinaryPredicate>
1997 _GLIBCXX20_CONSTEXPR
1999 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2000 _InputIterator2 __first2, _InputIterator2 __last2,
2001 _BinaryPredicate __binary_pred)
2003 while (__first1 != __last1 && __first2 != __last2
2004 && __binary_pred(__first1, __first2))
2026 template<
typename _InputIterator1,
typename _InputIterator2>
2027 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2029 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2030 _InputIterator2 __first2, _InputIterator2 __last2)
2033 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2034 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2035 __glibcxx_function_requires(_EqualOpConcept<
2038 __glibcxx_requires_valid_range(__first1, __last1);
2039 __glibcxx_requires_valid_range(__first2, __last2);
2041 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2042 __gnu_cxx::__ops::__iter_equal_to_iter());
2062 template<
typename _InputIterator1,
typename _InputIterator2,
2063 typename _BinaryPredicate>
2064 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2066 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2067 _InputIterator2 __first2, _InputIterator2 __last2,
2068 _BinaryPredicate __binary_pred)
2071 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2072 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2073 __glibcxx_requires_valid_range(__first1, __last1);
2074 __glibcxx_requires_valid_range(__first2, __last2);
2076 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2077 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
2081_GLIBCXX_END_NAMESPACE_ALGO
2084 template<
typename _InputIterator,
typename _Predicate>
2085 _GLIBCXX20_CONSTEXPR
2086 inline _InputIterator
2090 while (__first != __last && !__pred(__first))
2096 template<
typename _RandomAccessIterator,
typename _Predicate>
2097 _GLIBCXX20_CONSTEXPR
2098 _RandomAccessIterator
2099 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
2103 __trip_count = (__last - __first) >> 2;
2105 for (; __trip_count > 0; --__trip_count)
2107 if (__pred(__first))
2111 if (__pred(__first))
2115 if (__pred(__first))
2119 if (__pred(__first))
2124 switch (__last - __first)
2127 if (__pred(__first))
2132 if (__pred(__first))
2137 if (__pred(__first))
2147 template<
typename _Iterator,
typename _Predicate>
2148 _GLIBCXX20_CONSTEXPR
2150 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
2152 return __find_if(__first, __last, __pred,
2156 template<
typename _InputIterator,
typename _Predicate>
2157 _GLIBCXX20_CONSTEXPR
2158 typename iterator_traits<_InputIterator>::difference_type
2159 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2161 typename iterator_traits<_InputIterator>::difference_type __n = 0;
2162 for (; __first != __last; ++__first)
2163 if (__pred(__first))
2168 template<
typename _ForwardIterator,
typename _Predicate>
2169 _GLIBCXX20_CONSTEXPR
2171 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
2175 if (__first == __last)
2177 _ForwardIterator __result = __first;
2179 for (; __first != __last; ++__first)
2180 if (!__pred(__first))
2182 *__result = _GLIBCXX_MOVE(*__first);
2188 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2189 typename _BinaryPredicate>
2190 _GLIBCXX20_CONSTEXPR
2192 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2193 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2194 _BinaryPredicate __predicate)
2197 if (__first1 == __last1 || __first2 == __last2)
2201 _ForwardIterator2 __p1(__first2);
2202 if (++__p1 == __last2)
2204 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2207 _ForwardIterator1 __current = __first1;
2213 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2215 if (__first1 == __last1)
2218 _ForwardIterator2 __p = __p1;
2219 __current = __first1;
2220 if (++__current == __last1)
2223 while (__predicate(__current, __p))
2225 if (++__p == __last2)
2227 if (++__current == __last1)
2235#if __cplusplus >= 201103L
2236 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2237 typename _BinaryPredicate>
2238 _GLIBCXX20_CONSTEXPR
2240 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2241 _ForwardIterator2 __first2, _BinaryPredicate __pred)
2245 for (; __first1 != __last1; ++__first1, (void)++__first2)
2246 if (!__pred(__first1, __first2))
2249 if (__first1 == __last1)
2254 _ForwardIterator2 __last2 = __first2;
2256 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
2259 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
2263 = std::__count_if(__first2, __last2,
2264 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
2265 if (0 == __matches ||
2266 std::__count_if(__scan, __last1,
2267 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
2286 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
2287 _GLIBCXX20_CONSTEXPR
2289 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2290 _ForwardIterator2 __first2)
2293 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2294 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2295 __glibcxx_function_requires(_EqualOpConcept<
2298 __glibcxx_requires_valid_range(__first1, __last1);
2300 return std::__is_permutation(__first1, __last1, __first2,
2301 __gnu_cxx::__ops::__iter_equal_to_iter());
2305_GLIBCXX_BEGIN_NAMESPACE_ALGO
2328 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2329 typename _BinaryPredicate>
2330 _GLIBCXX20_CONSTEXPR
2331 inline _ForwardIterator1
2332 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2333 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2334 _BinaryPredicate __predicate)
2337 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2338 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2339 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
2342 __glibcxx_requires_valid_range(__first1, __last1);
2343 __glibcxx_requires_valid_range(__first2, __last2);
2345 return std::__search(__first1, __last1, __first2, __last2,
2346 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
2349_GLIBCXX_END_NAMESPACE_ALGO
2350_GLIBCXX_END_NAMESPACE_VERSION
2356#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.