56#ifndef _STL_ALGOBASE_H
57#define _STL_ALGOBASE_H 1
72#if __cplusplus >= 201103L
75#if __cplusplus > 201703L
79namespace std _GLIBCXX_VISIBILITY(default)
81_GLIBCXX_BEGIN_NAMESPACE_VERSION
87 template<
typename _Tp,
typename _Up>
90 __memcmp(
const _Tp* __first1,
const _Up* __first2,
size_t __num)
92#if __cplusplus >= 201103L
93 static_assert(
sizeof(_Tp) ==
sizeof(_Up),
"can be compared with memcmp");
95#ifdef __cpp_lib_is_constant_evaluated
98 for(; __num > 0; ++__first1, ++__first2, --__num)
99 if (*__first1 != *__first2)
100 return *__first1 < *__first2 ? -1 : 1;
105 return __builtin_memcmp(__first1, __first2,
sizeof(_Tp) * __num);
108#if __cplusplus < 201103L
112 template<
bool _BoolType>
115 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
117 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
119 typedef typename iterator_traits<_ForwardIterator1>::value_type
121 _ValueType1 __tmp = *__a;
128 struct __iter_swap<true>
130 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
132 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
149 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
155 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
157 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
160#if __cplusplus < 201103L
166 __glibcxx_function_requires(_ConvertibleConcept<
_ValueType1,
168 __glibcxx_function_requires(_ConvertibleConcept<
_ValueType2,
176 && __are_same<_ValueType1&, _ReferenceType1>::__value
177 && __are_same<_ValueType2&, _ReferenceType2>::__value>::
198 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
205 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
207 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
227 template<
typename _Tp>
230 min(
const _Tp& __a,
const _Tp& __b)
251 template<
typename _Tp>
254 max(
const _Tp& __a,
const _Tp& __b)
275 template<
typename _Tp,
typename _Compare>
278 min(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
281 if (__comp(__b, __a))
297 template<
typename _Tp,
typename _Compare>
300 max(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
303 if (__comp(__a, __b))
310 template<
typename _Iterator>
313 __niter_base(_Iterator __it)
317 template<
typename _Ite,
typename _Seq>
319 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
325 template<
typename _From,
typename _To>
328 __niter_wrap(_From __from, _To __res)
329 {
return __from + (__res - std::__niter_base(__from)); }
332 template<
typename _Iterator>
335 __niter_wrap(
const _Iterator&, _Iterator __res)
344 template<
bool _IsMove,
bool _IsSimple,
typename _Category>
347 template<
typename _II,
typename _OI>
350 __copy_m(_II __first, _II __last, _OI __result)
352 for (; __first != __last; ++__result, (void)++__first)
353 *__result = *__first;
358#if __cplusplus >= 201103L
359 template<
typename _Category>
360 struct __copy_move<true, false, _Category>
362 template<
typename _II,
typename _OI>
365 __copy_m(_II __first, _II __last, _OI __result)
367 for (; __first != __last; ++__result, (void)++__first)
375 struct __copy_move<false, false, random_access_iterator_tag>
377 template<
typename _II,
typename _OI>
380 __copy_m(_II __first, _II __last, _OI __result)
382 typedef typename iterator_traits<_II>::difference_type _Distance;
383 for(_Distance __n = __last - __first; __n > 0; --__n)
385 *__result = *__first;
392 template<
typename _Tp,
typename _Up>
394 __assign_one(_Tp* __to, _Up* __from)
398#if __cplusplus >= 201103L
400 struct __copy_move<true, false, random_access_iterator_tag>
402 template<
typename _II,
typename _OI>
405 __copy_m(_II __first, _II __last, _OI __result)
407 typedef typename iterator_traits<_II>::difference_type _Distance;
408 for(_Distance __n = __last - __first; __n > 0; --__n)
417 template<
typename _Tp,
typename _Up>
419 __assign_one(_Tp* __to, _Up* __from)
424 template<
bool _IsMove>
425 struct __copy_move<_IsMove, true, random_access_iterator_tag>
427 template<
typename _Tp,
typename _Up>
430 __copy_m(_Tp* __first, _Tp* __last, _Up* __result)
432 const ptrdiff_t _Num = __last - __first;
433 if (__builtin_expect(_Num > 1,
true))
434 __builtin_memmove(__result, __first,
sizeof(_Tp) * _Num);
436 std::__copy_move<_IsMove, false, random_access_iterator_tag>::
437 __assign_one(__result, __first);
438 return __result + _Num;
442_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
444 template<
typename _Tp,
typename _Ref,
typename _Ptr>
445 struct _Deque_iterator;
447 struct _Bit_iterator;
449_GLIBCXX_END_NAMESPACE_CONTAINER
453 template<
typename _CharT>
456 template<
typename _CharT,
typename _Traits>
457 class istreambuf_iterator;
459 template<
typename _CharT,
typename _Traits>
460 class ostreambuf_iterator;
462 template<
bool _IsMove,
typename _CharT>
463 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
464 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
465 __copy_move_a2(_CharT*, _CharT*,
466 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
468 template<
bool _IsMove,
typename _CharT>
469 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
470 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
471 __copy_move_a2(
const _CharT*,
const _CharT*,
472 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
474 template<
bool _IsMove,
typename _CharT>
475 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
477 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
478 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
480 template<
bool _IsMove,
typename _CharT>
481 typename __gnu_cxx::__enable_if<
482 __is_char<_CharT>::__value,
483 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
485 istreambuf_iterator<_CharT, char_traits<_CharT> >,
486 istreambuf_iterator<_CharT, char_traits<_CharT> >,
487 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>);
489 template<
bool _IsMove,
typename _II,
typename _OI>
492 __copy_move_a2(_II __first, _II __last, _OI __result)
494 typedef typename iterator_traits<_II>::iterator_category _Category;
495#ifdef __cpp_lib_is_constant_evaluated
497 return std::__copy_move<_IsMove, false, _Category>::
498 __copy_m(__first, __last, __result);
501 _Category>::__copy_m(__first, __last, __result);
504 template<
bool _IsMove,
505 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
507 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
508 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
511 template<
bool _IsMove,
512 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
513 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
514 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
515 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
516 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
518 template<
bool _IsMove,
typename _II,
typename _Tp>
519 typename __gnu_cxx::__enable_if<
520 __is_random_access_iter<_II>::__value,
521 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
522 __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
524 template<
bool _IsMove,
typename _II,
typename _OI>
527 __copy_move_a1(_II __first, _II __last, _OI __result)
530 template<
bool _IsMove,
typename _II,
typename _OI>
533 __copy_move_a(_II __first, _II __last, _OI __result)
535 return std::__niter_wrap(__result,
537 std::__niter_base(__last),
538 std::__niter_base(__result)));
541 template<
bool _IsMove,
542 typename _Ite,
typename _Seq,
typename _Cat,
typename _OI>
544 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
545 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
548 template<
bool _IsMove,
549 typename _II,
typename _Ite,
typename _Seq,
typename _Cat>
551 __copy_move_a(_II, _II,
552 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
554 template<
bool _IsMove,
555 typename _IIte,
typename _ISeq,
typename _ICat,
556 typename _OIte,
typename _OSeq,
typename _OCat>
558 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
559 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
560 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
562 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
565 __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result,
572 *__result = *__first;
583 template<
typename _CharT,
typename _Size>
584 typename __gnu_cxx::__enable_if<
585 __is_char<_CharT>::__value, _CharT*>::__type
586 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >,
587 _Size, _CharT*,
bool);
589 template<
typename _CharT,
typename _Size>
590 typename __gnu_cxx::__enable_if<
591 __is_char<_CharT>::__value,
592 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
593 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, _Size,
594 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>,
614 template<
typename _II,
typename _OI>
621 __glibcxx_function_requires(_OutputIteratorConcept<
_OI,
623 __glibcxx_requires_can_increment_range(__first, __last, __result);
626 (std::__miter_base(__first), std::__miter_base(__last), __result);
629#if __cplusplus >= 201103L
647 template<
typename _II,
typename _OI>
654 __glibcxx_function_requires(_OutputIteratorConcept<
_OI,
656 __glibcxx_requires_can_increment_range(__first, __last, __result);
659 std::__miter_base(__last), __result);
662#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
664#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
667 template<
bool _IsMove,
bool _IsSimple,
typename _Category>
668 struct __copy_move_backward
670 template<
typename _BI1,
typename _BI2>
673 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
675 while (__first != __last)
676 *--__result = *--__last;
681#if __cplusplus >= 201103L
682 template<
typename _Category>
683 struct __copy_move_backward<true, false, _Category>
685 template<
typename _BI1,
typename _BI2>
688 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
690 while (__first != __last)
698 struct __copy_move_backward<false, false, random_access_iterator_tag>
700 template<
typename _BI1,
typename _BI2>
703 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
705 typename iterator_traits<_BI1>::difference_type
706 __n = __last - __first;
707 for (; __n > 0; --__n)
708 *--__result = *--__last;
713#if __cplusplus >= 201103L
715 struct __copy_move_backward<true, false, random_access_iterator_tag>
717 template<
typename _BI1,
typename _BI2>
720 __copy_move_b(_BI1 __first, _BI1 __last, _BI2 __result)
722 typename iterator_traits<_BI1>::difference_type
723 __n = __last - __first;
724 for (; __n > 0; --__n)
731 template<
bool _IsMove>
732 struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
734 template<
typename _Tp,
typename _Up>
737 __copy_move_b(_Tp* __first, _Tp* __last, _Up* __result)
739 const ptrdiff_t _Num = __last - __first;
740 if (__builtin_expect(_Num > 1,
true))
741 __builtin_memmove(__result - _Num, __first,
sizeof(_Tp) * _Num);
743 std::__copy_move<_IsMove, false, random_access_iterator_tag>::
744 __assign_one(__result - 1, __first);
745 return __result - _Num;
749 template<
bool _IsMove,
typename _BI1,
typename _BI2>
752 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
754 typedef typename iterator_traits<_BI1>::iterator_category _Category;
755#ifdef __cpp_lib_is_constant_evaluated
757 return std::__copy_move_backward<_IsMove, false, _Category>::
758 __copy_move_b(__first, __last, __result);
760 return std::__copy_move_backward<_IsMove,
761 __memcpyable<_BI2, _BI1>::__value,
762 _Category>::__copy_move_b(__first,
767 template<
bool _IsMove,
typename _BI1,
typename _BI2>
770 __copy_move_backward_a1(_BI1 __first, _BI1 __last, _BI2 __result)
773 template<
bool _IsMove,
774 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
776 __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
777 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
780 template<
bool _IsMove,
781 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
782 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
783 __copy_move_backward_a1(
784 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
785 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
786 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
788 template<
bool _IsMove,
typename _II,
typename _Tp>
789 typename __gnu_cxx::__enable_if<
790 __is_random_access_iter<_II>::__value,
791 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
792 __copy_move_backward_a1(_II, _II,
793 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
795 template<
bool _IsMove,
typename _II,
typename _OI>
798 __copy_move_backward_a(_II __first, _II __last, _OI __result)
800 return std::__niter_wrap(__result,
802 (std::__niter_base(__first), std::__niter_base(__last),
803 std::__niter_base(__result)));
806 template<
bool _IsMove,
807 typename _Ite,
typename _Seq,
typename _Cat,
typename _OI>
809 __copy_move_backward_a(
810 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
811 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
814 template<
bool _IsMove,
815 typename _II,
typename _Ite,
typename _Seq,
typename _Cat>
817 __copy_move_backward_a(_II, _II,
818 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
820 template<
bool _IsMove,
821 typename _IIte,
typename _ISeq,
typename _ICat,
822 typename _OIte,
typename _OSeq,
typename _OCat>
824 __copy_move_backward_a(
825 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
826 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
827 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
847 template<
typename _BI1,
typename _BI2>
855 __glibcxx_function_requires(_OutputIteratorConcept<
_BI2,
857 __glibcxx_requires_can_decrement_range(__first, __last, __result);
860 (std::__miter_base(__first), std::__miter_base(__last), __result);
863#if __cplusplus >= 201103L
882 template<
typename _BI1,
typename _BI2>
890 __glibcxx_function_requires(_OutputIteratorConcept<
_BI2,
892 __glibcxx_requires_can_decrement_range(__first, __last, __result);
895 std::__miter_base(__last),
899#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
901#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
904 template<
typename _ForwardIterator,
typename _Tp>
907 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value,
void>::__type
908 __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
911 for (; __first != __last; ++__first)
915 template<
typename _ForwardIterator,
typename _Tp>
918 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value,
void>::__type
919 __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
922 const _Tp __tmp = __value;
923 for (; __first != __last; ++__first)
928 template<
typename _Tp>
931 __gnu_cxx::__enable_if<__is_byte<_Tp>::__value,
void>::__type
932 __fill_a1(_Tp* __first, _Tp* __last,
const _Tp& __c)
934 const _Tp __tmp = __c;
935#if __cpp_lib_is_constant_evaluated
938 for (; __first != __last; ++__first)
943 if (
const size_t __len = __last - __first)
944 __builtin_memset(__first,
static_cast<unsigned char>(__tmp), __len);
947 template<
typename _Ite,
typename _Cont,
typename _Tp>
950 __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first,
951 ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last,
953 { std::__fill_a1(__first.base(), __last.base(), __value); }
955 template<
typename _Tp,
typename _VTp>
957 __fill_a1(
const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
958 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
963 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator,
966 template<
typename _FIte,
typename _Tp>
969 __fill_a(_FIte __first, _FIte __last,
const _Tp& __value)
970 { std::__fill_a1(__first, __last, __value); }
972 template<
typename _Ite,
typename _Seq,
typename _Cat,
typename _Tp>
974 __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
975 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
990 template<
typename _ForwardIterator,
typename _Tp>
996 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
998 __glibcxx_requires_valid_range(__first, __last);
1000 std::__fill_a(__first, __last, __value);
1004 inline _GLIBCXX_CONSTEXPR
int
1005 __size_to_integer(
int __n) {
return __n; }
1006 inline _GLIBCXX_CONSTEXPR
unsigned
1007 __size_to_integer(
unsigned __n) {
return __n; }
1008 inline _GLIBCXX_CONSTEXPR
long
1009 __size_to_integer(
long __n) {
return __n; }
1010 inline _GLIBCXX_CONSTEXPR
unsigned long
1011 __size_to_integer(
unsigned long __n) {
return __n; }
1012 inline _GLIBCXX_CONSTEXPR
long long
1013 __size_to_integer(
long long __n) {
return __n; }
1014 inline _GLIBCXX_CONSTEXPR
unsigned long long
1015 __size_to_integer(
unsigned long long __n) {
return __n; }
1017#if defined(__GLIBCXX_TYPE_INT_N_0)
1018 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
1019 __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1020 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_0
1021 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1023#if defined(__GLIBCXX_TYPE_INT_N_1)
1024 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
1025 __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1026 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_1
1027 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1029#if defined(__GLIBCXX_TYPE_INT_N_2)
1030 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
1031 __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1032 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_2
1033 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1035#if defined(__GLIBCXX_TYPE_INT_N_3)
1036 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_3
1037 __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1038 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
1039 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1042 inline _GLIBCXX_CONSTEXPR
long long
1043 __size_to_integer(
float __n) {
return (
long long)__n; }
1044 inline _GLIBCXX_CONSTEXPR
long long
1045 __size_to_integer(
double __n) {
return (
long long)__n; }
1046 inline _GLIBCXX_CONSTEXPR
long long
1047 __size_to_integer(
long double __n) {
return (
long long)__n; }
1048#if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128) && !defined(__CUDACC__)
1049 __extension__
inline _GLIBCXX_CONSTEXPR
long long
1050 __size_to_integer(__float128 __n) {
return (
long long)__n; }
1053 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1054 _GLIBCXX20_CONSTEXPR
1056 __gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, _OutputIterator>::__type
1057 __fill_n_a1(_OutputIterator __first, _Size __n,
const _Tp& __value)
1059 for (; __n > 0; --__n, (void) ++__first)
1064 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1065 _GLIBCXX20_CONSTEXPR
1067 __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, _OutputIterator>::__type
1068 __fill_n_a1(_OutputIterator __first, _Size __n,
const _Tp& __value)
1070 const _Tp __tmp = __value;
1071 for (; __n > 0; --__n, (void) ++__first)
1076 template<
typename _Ite,
typename _Seq,
typename _Cat,
typename _Size,
1079 __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
1080 _Size __n,
const _Tp& __value,
1083 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1084 _GLIBCXX20_CONSTEXPR
1085 inline _OutputIterator
1086 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1089#if __cplusplus >= 201103L
1090 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1092 return __fill_n_a1(__first, __n, __value);
1095 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1096 _GLIBCXX20_CONSTEXPR
1097 inline _OutputIterator
1098 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1101#if __cplusplus >= 201103L
1102 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1104 return __fill_n_a1(__first, __n, __value);
1107 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1108 _GLIBCXX20_CONSTEXPR
1109 inline _OutputIterator
1110 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1113#if __cplusplus >= 201103L
1114 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1119 __glibcxx_requires_can_increment(__first, __n);
1121 std::__fill_a(__first, __first + __n, __value);
1122 return __first + __n;
1142 template<
typename _OI,
typename _Size,
typename _Tp>
1143 _GLIBCXX20_CONSTEXPR
1145 fill_n(
_OI __first, _Size __n,
const _Tp& __value)
1150 return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
1154 template<
bool _BoolType>
1157 template<
typename _II1,
typename _II2>
1158 _GLIBCXX20_CONSTEXPR
1160 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1162 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1163 if (!(*__first1 == *__first2))
1170 struct __equal<true>
1172 template<
typename _Tp>
1173 _GLIBCXX20_CONSTEXPR
1175 equal(
const _Tp* __first1,
const _Tp* __last1,
const _Tp* __first2)
1177 if (
const size_t __len = (__last1 - __first1))
1178 return !std::__memcmp(__first1, __first2, __len);
1183 template<
typename _Tp,
typename _Ref,
typename _Ptr,
typename _II>
1184 typename __gnu_cxx::__enable_if<
1185 __is_random_access_iter<_II>::__value,
bool>::__type
1186 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1187 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1190 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1191 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1193 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1194 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1195 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1197 template<
typename _II,
typename _Tp,
typename _Ref,
typename _Ptr>
1198 typename __gnu_cxx::__enable_if<
1199 __is_random_access_iter<_II>::__value,
bool>::__type
1200 __equal_aux1(_II, _II,
1201 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>);
1203 template<
typename _II1,
typename _II2>
1204 _GLIBCXX20_CONSTEXPR
1206 __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
1208 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1209 const bool __simple = ((__is_integer<_ValueType1>::__value
1210 || __is_pointer<_ValueType1>::__value)
1211 && __memcmpable<_II1, _II2>::__value);
1212 return std::__equal<__simple>::equal(__first1, __last1, __first2);
1215 template<
typename _II1,
typename _II2>
1216 _GLIBCXX20_CONSTEXPR
1218 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
1220 return std::__equal_aux1(std::__niter_base(__first1),
1221 std::__niter_base(__last1),
1222 std::__niter_base(__first2));
1225 template<
typename _II1,
typename _Seq1,
typename _Cat1,
typename _II2>
1227 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1228 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1231 template<
typename _II1,
typename _II2,
typename _Seq2,
typename _Cat2>
1233 __equal_aux(_II1, _II1,
1234 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1236 template<
typename _II1,
typename _Seq1,
typename _Cat1,
1237 typename _II2,
typename _Seq2,
typename _Cat2>
1239 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1240 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1241 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1243 template<
typename,
typename>
1246 template<
typename _II1,
typename _II2>
1247 _GLIBCXX20_CONSTEXPR
1249 __newlast1(_II1, _II1 __last1, _II2, _II2)
1252 template<
typename _II>
1253 _GLIBCXX20_CONSTEXPR
1255 __cnd2(_II __first, _II __last)
1256 {
return __first != __last; }
1260 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
1262 template<
typename _RAI1,
typename _RAI2>
1263 _GLIBCXX20_CONSTEXPR
1265 __newlast1(_RAI1 __first1, _RAI1 __last1,
1266 _RAI2 __first2, _RAI2 __last2)
1268 const typename iterator_traits<_RAI1>::difference_type
1269 __diff1 = __last1 - __first1;
1270 const typename iterator_traits<_RAI2>::difference_type
1271 __diff2 = __last2 - __first2;
1272 return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
1275 template<
typename _RAI>
1276 static _GLIBCXX20_CONSTEXPR
bool
1281 template<
typename _II1,
typename _II2,
typename _Compare>
1282 _GLIBCXX20_CONSTEXPR
1284 __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
1285 _II2 __first2, _II2 __last2,
1288 typedef typename iterator_traits<_II1>::iterator_category _Category1;
1289 typedef typename iterator_traits<_II2>::iterator_category _Category2;
1292 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1293 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1294 ++__first1, (void)++__first2)
1296 if (__comp(__first1, __first2))
1298 if (__comp(__first2, __first1))
1301 return __first1 == __last1 && __first2 != __last2;
1304 template<
bool _BoolType>
1305 struct __lexicographical_compare
1307 template<
typename _II1,
typename _II2>
1308 _GLIBCXX20_CONSTEXPR
1310 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1312 using __gnu_cxx::__ops::__iter_less_iter;
1313 return std::__lexicographical_compare_impl(__first1, __last1,
1315 __iter_less_iter());
1318 template<
typename _II1,
typename _II2>
1319 _GLIBCXX20_CONSTEXPR
1321 __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1323 while (__first1 != __last1)
1325 if (__first2 == __last2)
1327 if (*__first1 < *__first2)
1329 if (*__first2 < *__first1)
1334 return int(__first2 == __last2) - 1;
1339 struct __lexicographical_compare<true>
1341 template<
typename _Tp,
typename _Up>
1342 _GLIBCXX20_CONSTEXPR
1344 __lc(
const _Tp* __first1,
const _Tp* __last1,
1345 const _Up* __first2,
const _Up* __last2)
1346 {
return __3way(__first1, __last1, __first2, __last2) < 0; }
1348 template<
typename _Tp,
typename _Up>
1349 _GLIBCXX20_CONSTEXPR
1351 __3way(
const _Tp* __first1,
const _Tp* __last1,
1352 const _Up* __first2,
const _Up* __last2)
1354 const size_t __len1 = __last1 - __first1;
1355 const size_t __len2 = __last2 - __first2;
1356 if (
const size_t __len =
std::min(__len1, __len2))
1357 if (
int __result = std::__memcmp(__first1, __first2, __len))
1359 return ptrdiff_t(__len1 - __len2);
1363 template<
typename _II1,
typename _II2>
1364 _GLIBCXX20_CONSTEXPR
1366 __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
1367 _II2 __first2, _II2 __last2)
1369 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1370 typedef typename iterator_traits<_II2>::value_type _ValueType2;
1371 const bool __simple =
1372 (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
1373 && __is_pointer<_II1>::__value
1374 && __is_pointer<_II2>::__value
1375#if __cplusplus > 201703L && __cpp_lib_concepts
1379 && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>>
1380 && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>>
1384 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
1388 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1391 __lexicographical_compare_aux1(
1392 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1393 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1396 template<
typename _Tp1,
1397 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1399 __lexicographical_compare_aux1(_Tp1*, _Tp1*,
1400 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1401 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1403 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1404 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1406 __lexicographical_compare_aux1(
1407 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1408 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1409 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1410 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1412 template<
typename _II1,
typename _II2>
1413 _GLIBCXX20_CONSTEXPR
1415 __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
1416 _II2 __first2, _II2 __last2)
1418 return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
1419 std::__niter_base(__last1),
1420 std::__niter_base(__first2),
1421 std::__niter_base(__last2));
1424 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
1427 __lexicographical_compare_aux(
1428 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1429 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1432 template<
typename _II1,
1433 typename _Iter2,
typename _Seq2,
typename _Cat2>
1435 __lexicographical_compare_aux(
1437 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1438 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1440 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
1441 typename _Iter2,
typename _Seq2,
typename _Cat2>
1443 __lexicographical_compare_aux(
1444 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1445 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1446 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1447 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1449 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1450 _GLIBCXX20_CONSTEXPR
1452 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1453 const _Tp& __val, _Compare __comp)
1455 typedef typename iterator_traits<_ForwardIterator>::difference_type
1462 _DistanceType __half = __len >> 1;
1463 _ForwardIterator __middle = __first;
1465 if (__comp(__middle, __val))
1469 __len = __len - __half - 1;
1488 template<
typename _ForwardIterator,
typename _Tp>
1489 _GLIBCXX20_CONSTEXPR
1490 inline _ForwardIterator
1496 __glibcxx_function_requires(_LessThanOpConcept<
1498 __glibcxx_requires_partitioned_lower(__first, __last, __val);
1500 return std::__lower_bound(__first, __last, __val,
1501 __gnu_cxx::__ops::__iter_less_val());
1506 inline _GLIBCXX_CONSTEXPR
int
1510 inline _GLIBCXX_CONSTEXPR
unsigned
1512 {
return (
int)
sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
1514 inline _GLIBCXX_CONSTEXPR
long
1516 {
return (
int)
sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
1518 inline _GLIBCXX_CONSTEXPR
unsigned long
1519 __lg(
unsigned long __n)
1520 {
return (
int)
sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
1522 inline _GLIBCXX_CONSTEXPR
long long
1524 {
return (
int)
sizeof(
long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
1526 inline _GLIBCXX_CONSTEXPR
unsigned long long
1527 __lg(
unsigned long long __n)
1528 {
return (
int)
sizeof(
long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
1530_GLIBCXX_BEGIN_NAMESPACE_ALGO
1544 template<
typename _II1,
typename _II2>
1545 _GLIBCXX20_CONSTEXPR
1552 __glibcxx_function_requires(_EqualOpConcept<
1575 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1576 _GLIBCXX20_CONSTEXPR
1592#if __cplusplus >= 201103L
1594 template<
typename _II1,
typename _II2>
1595 _GLIBCXX20_CONSTEXPR
1597 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1599 using _RATag = random_access_iterator_tag;
1600 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1601 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1602 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1609 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1612 for (; __first1 != __last1 && __first2 != __last2;
1613 ++__first1, (void)++__first2)
1614 if (!(*__first1 == *__first2))
1616 return __first1 == __last1 && __first2 == __last2;
1620 template<
typename _II1,
typename _II2,
typename _BinaryPredicate>
1621 _GLIBCXX20_CONSTEXPR
1623 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2,
1624 _BinaryPredicate __binary_pred)
1626 using _RATag = random_access_iterator_tag;
1627 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1628 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1629 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1636 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1640 for (; __first1 != __last1 && __first2 != __last2;
1641 ++__first1, (void)++__first2)
1642 if (!
bool(__binary_pred(*__first1, *__first2)))
1644 return __first1 == __last1 && __first2 == __last2;
1648#if __cplusplus > 201103L
1650#define __cpp_lib_robust_nonmodifying_seq_ops 201304L
1665 template<
typename _II1,
typename _II2>
1666 _GLIBCXX20_CONSTEXPR
1673 __glibcxx_function_requires(_EqualOpConcept<
1698 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1699 _GLIBCXX20_CONSTEXPR
1730 template<
typename _II1,
typename _II2>
1731 _GLIBCXX20_CONSTEXPR
1736#ifdef _GLIBCXX_CONCEPT_CHECKS
1765 template<
typename _II1,
typename _II2,
typename _Compare>
1766 _GLIBCXX20_CONSTEXPR
1777 return std::__lexicographical_compare_impl
1779 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1782#if __cpp_lib_three_way_comparison
1786 template<
typename _Iter1,
typename _Iter2>
1787 concept __memcmp_ordered_with
1788 = (__is_memcmp_ordered_with<iter_value_t<_Iter1>,
1789 iter_value_t<_Iter2>>::__value)
1790 && contiguous_iterator<_Iter1> && contiguous_iterator<_Iter2>;
1794 template<
typename _Tp>
1796 __min_cmp(_Tp __x, _Tp __y)
1800 decltype(__x <=> __y) _M_cmp;
1802 auto __c = __x <=> __y;
1804 return _Res{__y, __c};
1805 return _Res{__x, __c};
1819 template<
typename _InputIter1,
typename _InputIter2,
typename _Comp>
1821 lexicographical_compare_three_way(_InputIter1 __first1,
1822 _InputIter1 __last1,
1823 _InputIter2 __first2,
1824 _InputIter2 __last2,
1826 ->
decltype(__comp(*__first1, *__first2))
1829 __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
1830 __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
1831 __glibcxx_requires_valid_range(__first1, __last1);
1832 __glibcxx_requires_valid_range(__first2, __last2);
1834 using _Cat =
decltype(__comp(*__first1, *__first2));
1835 static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
1837 if (!std::__is_constant_evaluated())
1838 if constexpr (same_as<_Comp, __detail::_Synth3way>
1839 || same_as<_Comp, compare_three_way>)
1840 if constexpr (__memcmp_ordered_with<_InputIter1, _InputIter2>)
1842 const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1843 __min_cmp(__last1 - __first1, __last2 - __first2);
1846 const auto __blen = __len *
sizeof(*__first1);
1848 = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 0;
1855 while (__first1 != __last1)
1857 if (__first2 == __last2)
1858 return strong_ordering::greater;
1859 if (
auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
1864 return (__first2 == __last2) <=>
true;
1867 template<
typename _InputIter1,
typename _InputIter2>
1869 lexicographical_compare_three_way(_InputIter1 __first1,
1870 _InputIter1 __last1,
1871 _InputIter2 __first2,
1872 _InputIter2 __last2)
1874 return _GLIBCXX_STD_A::
1875 lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
1876 compare_three_way{});
1880 template<
typename _InputIterator1,
typename _InputIterator2,
1881 typename _BinaryPredicate>
1882 _GLIBCXX20_CONSTEXPR
1883 pair<_InputIterator1, _InputIterator2>
1884 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1885 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1887 while (__first1 != __last1 && __binary_pred(__first1, __first2))
1892 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1908 template<
typename _InputIterator1,
typename _InputIterator2>
1909 _GLIBCXX20_CONSTEXPR
1910 inline pair<_InputIterator1, _InputIterator2>
1917 __glibcxx_function_requires(_EqualOpConcept<
1923 __gnu_cxx::__ops::__iter_equal_to_iter());
1942 template<
typename _InputIterator1,
typename _InputIterator2,
1943 typename _BinaryPredicate>
1944 _GLIBCXX20_CONSTEXPR
1945 inline pair<_InputIterator1, _InputIterator2>
1958#if __cplusplus > 201103L
1960 template<
typename _InputIterator1,
typename _InputIterator2,
1961 typename _BinaryPredicate>
1962 _GLIBCXX20_CONSTEXPR
1963 pair<_InputIterator1, _InputIterator2>
1964 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1965 _InputIterator2 __first2, _InputIterator2 __last2,
1966 _BinaryPredicate __binary_pred)
1968 while (__first1 != __last1 && __first2 != __last2
1969 && __binary_pred(__first1, __first2))
1974 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1991 template<
typename _InputIterator1,
typename _InputIterator2>
1992 _GLIBCXX20_CONSTEXPR
1993 inline pair<_InputIterator1, _InputIterator2>
2000 __glibcxx_function_requires(_EqualOpConcept<
2007 __gnu_cxx::__ops::__iter_equal_to_iter());
2027 template<
typename _InputIterator1,
typename _InputIterator2,
2028 typename _BinaryPredicate>
2029 _GLIBCXX20_CONSTEXPR
2030 inline pair<_InputIterator1, _InputIterator2>
2046_GLIBCXX_END_NAMESPACE_ALGO
2049 template<
typename _InputIterator,
typename _Predicate>
2050 _GLIBCXX20_CONSTEXPR
2051 inline _InputIterator
2055 while (__first != __last && !
__pred(__first))
2061 template<
typename _RandomAccessIterator,
typename _Predicate>
2062 _GLIBCXX20_CONSTEXPR
2063 _RandomAccessIterator
2089 switch (__last - __first)
2112 template<
typename _Iterator,
typename _Predicate>
2113 _GLIBCXX20_CONSTEXPR
2115 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
2117 return __find_if(__first, __last, __pred,
2121 template<
typename _InputIterator,
typename _Predicate>
2122 _GLIBCXX20_CONSTEXPR
2123 typename iterator_traits<_InputIterator>::difference_type
2124 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2126 typename iterator_traits<_InputIterator>::difference_type __n = 0;
2127 for (; __first != __last; ++__first)
2128 if (__pred(__first))
2133 template<
typename _ForwardIterator,
typename _Predicate>
2134 _GLIBCXX20_CONSTEXPR
2136 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
2140 if (__first == __last)
2142 _ForwardIterator __result = __first;
2144 for (; __first != __last; ++__first)
2145 if (!__pred(__first))
2147 *__result = _GLIBCXX_MOVE(*__first);
2153#if __cplusplus >= 201103L
2154 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2155 typename _BinaryPredicate>
2156 _GLIBCXX20_CONSTEXPR
2158 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2159 _ForwardIterator2 __first2, _BinaryPredicate __pred)
2163 for (; __first1 != __last1; ++__first1, (void)++__first2)
2164 if (!__pred(__first1, __first2))
2167 if (__first1 == __last1)
2172 _ForwardIterator2 __last2 = __first2;
2174 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
2177 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
2181 = std::__count_if(__first2, __last2,
2182 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
2183 if (0 == __matches ||
2184 std::__count_if(__scan, __last1,
2185 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
2204 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
2205 _GLIBCXX20_CONSTEXPR
2213 __glibcxx_function_requires(_EqualOpConcept<
2219 __gnu_cxx::__ops::__iter_equal_to_iter());
2223_GLIBCXX_END_NAMESPACE_VERSION
2229#ifdef _GLIBCXX_PARALLEL
Parallel STL function calls corresponding to the stl_algobase.h header. The functions defined here ma...
constexpr bool is_constant_evaluated() noexcept
Returns true only when called during constant evaluation.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
constexpr _BI2 move_backward(_BI1 __first, _BI1 __last, _BI2 __result)
Moves the range [first,last) into result.
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 _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 int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
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.