56#ifndef _STL_ALGOBASE_H
57#define _STL_ALGOBASE_H 1
72#if __cplusplus >= 201103L
75#if __cplusplus >= 201402L
78#if __cplusplus >= 202002L
83namespace std _GLIBCXX_VISIBILITY(default)
85_GLIBCXX_BEGIN_NAMESPACE_VERSION
91 template<
typename _Tp,
typename _Up>
94 __memcmp(
const _Tp* __first1,
const _Up* __first2,
size_t __num)
96#if __cplusplus >= 201103L
97 static_assert(
sizeof(_Tp) ==
sizeof(_Up),
"can be compared with memcmp");
99#ifdef __cpp_lib_is_constant_evaluated
100 if (std::is_constant_evaluated())
102 for(; __num > 0; ++__first1, ++__first2, --__num)
103 if (*__first1 != *__first2)
104 return *__first1 < *__first2 ? -1 : 1;
109 return __builtin_memcmp(__first1, __first2,
sizeof(_Tp) * __num);
112#if __cplusplus < 201103L
116 template<
bool _BoolType>
119 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
121 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
123 typedef typename iterator_traits<_ForwardIterator1>::value_type
125 _ValueType1 __tmp = *__a;
132 struct __iter_swap<true>
134 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
136 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
153 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
156 iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
159 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
161 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
164#if __cplusplus < 201103L
170 __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
172 __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
179 std::__iter_swap<__are_same<_ValueType1, _ValueType2>::__value
180 && __are_same<_ValueType1&, _ReferenceType1>::__value
181 && __are_same<_ValueType2&, _ReferenceType2>::__value>::
202 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
205 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
206 _ForwardIterator2 __first2)
209 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
211 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
213 __glibcxx_requires_valid_range(__first1, __last1);
215 for (; __first1 != __last1; ++__first1, (void)++__first2)
216 std::iter_swap(__first1, __first2);
231 template<
typename _Tp>
232 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
234 min(
const _Tp& __a,
const _Tp& __b)
237 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
255 template<
typename _Tp>
256 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
258 max(
const _Tp& __a,
const _Tp& __b)
261 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
279 template<
typename _Tp,
typename _Compare>
280 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
282 min(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
285 if (__comp(__b, __a))
301 template<
typename _Tp,
typename _Compare>
302 _GLIBCXX_NODISCARD _GLIBCXX14_CONSTEXPR
304 max(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
307 if (__comp(__a, __b))
312_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
314 template<
typename _Tp,
typename _Ref,
typename _Ptr>
315 struct _Deque_iterator;
317 struct _Bit_iterator;
319_GLIBCXX_END_NAMESPACE_CONTAINER
324 template<
typename _CharT>
327 template<
typename _CharT,
typename _Traits>
328 class istreambuf_iterator;
330 template<
typename _CharT,
typename _Traits>
331 class ostreambuf_iterator;
333 template<
bool _IsMove,
typename _CharT>
334 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
335 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
336 __copy_move_a2(_CharT*, _CharT*,
337 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
339 template<
bool _IsMove,
typename _CharT>
340 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
341 ostreambuf_iterator<_CharT, char_traits<_CharT> > >::__type
342 __copy_move_a2(
const _CharT*,
const _CharT*,
343 ostreambuf_iterator<_CharT, char_traits<_CharT> >);
345 template<
bool _IsMove,
typename _CharT>
346 typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value,
348 __copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
349 istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
351 template<
bool _IsMove,
typename _CharT>
352 typename __gnu_cxx::__enable_if<
353 __is_char<_CharT>::__value,
354 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
356 istreambuf_iterator<_CharT, char_traits<_CharT> >,
357 istreambuf_iterator<_CharT, char_traits<_CharT> >,
358 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>);
361#if __cpp_lib_concepts
365 template<
typename _Iter>
366 concept __nothrow_contiguous_iterator
367 = contiguous_iterator<_Iter> &&
requires (_Iter __i) {
374 template<
typename _OutIter,
typename _InIter,
typename _Sent = _InIter>
375 concept __memcpyable_iterators
376 = __nothrow_contiguous_iterator<_OutIter>
377 && __nothrow_contiguous_iterator<_InIter>
378 && sized_sentinel_for<_Sent, _InIter>
379 &&
requires (_OutIter __o, _InIter __i, _Sent __s) {
382 { __i != __s }
noexcept;
386#if __cplusplus < 201103L
391 template<
typename _Iter> __attribute__((__always_inline__))
392 inline void* __ptr_or_null(_Iter) {
return 0; }
393 template<
typename _Tp> __attribute__((__always_inline__))
394 inline void* __ptr_or_null(_Tp* __p) {
return (
void*)__p; }
395# define _GLIBCXX_TO_ADDR(P) std::__ptr_or_null(P)
397 template<
typename _Iter> __attribute__((__always_inline__))
398 inline void __ptr_advance(_Iter&, ptrdiff_t) { }
399 template<
typename _Tp> __attribute__((__always_inline__))
400 inline void __ptr_advance(_Tp*& __p, ptrdiff_t __n) { __p += __n; }
401# define _GLIBCXX_ADVANCE(P, N) std::__ptr_advance(P, N)
405# define _GLIBCXX_TO_ADDR(P) P
406# define _GLIBCXX_ADVANCE(P, N) P += N
409#pragma GCC diagnostic push
410#pragma GCC diagnostic ignored "-Wc++17-extensions"
411 template<
bool _IsMove,
typename _OutIter,
typename _InIter>
412 __attribute__((__always_inline__)) _GLIBCXX20_CONSTEXPR
414 __assign_one(_OutIter& __out, _InIter& __in)
416#if __cplusplus >= 201103L
417 if constexpr (_IsMove)
424 template<
bool _IsMove,
typename _InIter,
typename _Sent,
typename _OutIter>
427 __copy_move_a2(_InIter __first, _Sent __last, _OutIter __result)
429 typedef __decltype(*__first) _InRef;
430 typedef __decltype(*__result) _OutRef;
431 if _GLIBCXX_CONSTEXPR (!__is_trivially_assignable(_OutRef, _InRef))
433 else if (std::__is_constant_evaluated())
435 else if _GLIBCXX_CONSTEXPR (__memcpyable<_OutIter, _InIter>::__value)
438 if (__builtin_expect(__n > 1,
true))
440 __builtin_memmove(_GLIBCXX_TO_ADDR(__result),
441 _GLIBCXX_TO_ADDR(__first),
442 __n *
sizeof(*__first));
443 _GLIBCXX_ADVANCE(__result, __n);
447 std::__assign_one<_IsMove>(__result, __first);
452#if __cpp_lib_concepts
453 else if constexpr (__memcpyable_iterators<_OutIter, _InIter, _Sent>)
455 if (
auto __n = __last - __first; __n > 1) [[likely]]
459 size_t __nbytes = __n *
sizeof(iter_value_t<_InIter>);
463 __builtin_memmove(__dest, __src, __nbytes);
467 std::__assign_one<_IsMove>(__result, __first);
474 for (; __first != __last; ++__result, (void)++__first)
475 std::__assign_one<_IsMove>(__result, __first);
478#pragma GCC diagnostic pop
480 template<
bool _IsMove,
481 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
483 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
484 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
487 template<
bool _IsMove,
488 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
489 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
490 __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
491 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
492 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
494 template<
bool _IsMove,
typename _II,
typename _Tp>
495 typename __gnu_cxx::__enable_if<
496 __is_random_access_iter<_II>::__value,
497 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
498 __copy_move_a1(_II, _II, _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
500 template<
bool _IsMove,
typename _II,
typename _OI>
501 __attribute__((__always_inline__))
504 __copy_move_a1(_II __first, _II __last, _OI __result)
505 {
return std::__copy_move_a2<_IsMove>(__first, __last, __result); }
507 template<
bool _IsMove,
typename _II,
typename _OI>
508 __attribute__((__always_inline__))
511 __copy_move_a(_II __first, _II __last, _OI __result)
513 return std::__niter_wrap(__result,
514 std::__copy_move_a1<_IsMove>(std::__niter_base(__first),
515 std::__niter_base(__last),
516 std::__niter_base(__result)));
519 template<
bool _IsMove,
520 typename _Ite,
typename _Seq,
typename _Cat,
typename _OI>
523 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
524 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
527 template<
bool _IsMove,
528 typename _II,
typename _Ite,
typename _Seq,
typename _Cat>
531 __copy_move_a(_II, _II,
532 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
534 template<
bool _IsMove,
535 typename _IIte,
typename _ISeq,
typename _ICat,
536 typename _OIte,
typename _OSeq,
typename _OCat>
538 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
539 __copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
540 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
541 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
543#pragma GCC diagnostic push
544#pragma GCC diagnostic ignored "-Wc++17-extensions"
545 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
548 __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result,
551 typedef __decltype(*__first) _InRef;
552 typedef __decltype(*__result) _OutRef;
553 if _GLIBCXX_CONSTEXPR (!__is_trivially_assignable(_OutRef, _InRef))
555#ifdef __cpp_lib_is_constant_evaluated
556 else if (std::is_constant_evaluated())
559 else if _GLIBCXX_CONSTEXPR (__memcpyable<_OutputIterator,
560 _InputIterator>::__value)
562 if (__builtin_expect(__n > 1,
true))
564 __builtin_memmove(_GLIBCXX_TO_ADDR(__result),
565 _GLIBCXX_TO_ADDR(__first),
566 __n *
sizeof(*__first));
567 _GLIBCXX_ADVANCE(__result, __n);
570 *__result++ = *__first;
573#if __cpp_lib_concepts
574 else if constexpr (__memcpyable_iterators<_OutputIterator,
577 if (__n > 1) [[likely]]
581 size_t __nbytes = __n *
sizeof(iter_value_t<_InputIterator>);
585 __builtin_memmove(__dest, __src, __nbytes);
588 *__result++ = *__first;
597 *__result = *__first;
607#pragma GCC diagnostic pop
610 template<
typename _CharT,
typename _Size>
611 typename __gnu_cxx::__enable_if<
612 __is_char<_CharT>::__value, _CharT*>::__type
613 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >,
614 _Size, _CharT*,
bool);
616 template<
typename _CharT,
typename _Size>
617 typename __gnu_cxx::__enable_if<
618 __is_char<_CharT>::__value,
619 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
620 __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, _Size,
621 _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>,
642 template<
typename _II,
typename _OI>
645 copy(_II __first, _II __last, _OI __result)
648 __glibcxx_function_requires(_InputIteratorConcept<_II>)
649 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
651 __glibcxx_requires_can_increment_range(__first, __last, __result);
653 return std::__copy_move_a<__is_move_iterator<_II>::__value>
654 (std::__miter_base(__first), std::__miter_base(__last), __result);
657#if __cplusplus >= 201103L
675 template<
typename _II,
typename _OI>
678 move(_II __first, _II __last, _OI __result)
681 __glibcxx_function_requires(_InputIteratorConcept<_II>)
682 __glibcxx_function_requires(_OutputIteratorConcept<_OI,
684 __glibcxx_requires_can_increment_range(__first, __last, __result);
686 return std::__copy_move_a<true>(std::__miter_base(__first),
687 std::__miter_base(__last), __result);
690#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::move(_Tp, _Up, _Vp)
692#define _GLIBCXX_MOVE3(_Tp, _Up, _Vp) std::copy(_Tp, _Up, _Vp)
695#pragma GCC diagnostic push
696#pragma GCC diagnostic ignored "-Wc++17-extensions"
697 template<
bool _IsMove,
typename _BI1,
typename _BI2>
700 __copy_move_backward_a2(_BI1 __first, _BI1 __last, _BI2 __result)
702 typedef __decltype(*__first) _InRef;
703 typedef __decltype(*__result) _OutRef;
704 if _GLIBCXX_CONSTEXPR (!__is_trivially_assignable(_OutRef, _InRef))
706#ifdef __cpp_lib_is_constant_evaluated
707 else if (std::is_constant_evaluated())
710 else if _GLIBCXX_CONSTEXPR (__memcpyable<_BI2, _BI1>::__value)
714 if (__builtin_expect(__n > 1,
true))
716 __builtin_memmove(_GLIBCXX_TO_ADDR(__result),
717 _GLIBCXX_TO_ADDR(__first),
718 __n *
sizeof(*__first));
721 std::__assign_one<_IsMove>(__result, __first);
724#if __cpp_lib_concepts
725 else if constexpr (__memcpyable_iterators<_BI2, _BI1>)
727 if (
auto __n = __last - __first; __n > 1) [[likely]]
734 size_t __nbytes = __n *
sizeof(iter_value_t<_BI1>);
735 __builtin_memmove(__dest, __src, __nbytes);
740 std::__assign_one<_IsMove>(__result, __first);
746 while (__first != __last)
750 std::__assign_one<_IsMove>(__result, __last);
754#pragma GCC diagnostic pop
756#undef _GLIBCXX_TO_ADDR
757#undef _GLIBCXX_ADVANCE
759 template<
bool _IsMove,
typename _BI1,
typename _BI2>
760 __attribute__((__always_inline__))
763 __copy_move_backward_a1(_BI1 __first, _BI1 __last, _BI2 __result)
764 {
return std::__copy_move_backward_a2<_IsMove>(__first, __last, __result); }
766 template<
bool _IsMove,
767 typename _Tp,
typename _Ref,
typename _Ptr,
typename _OI>
769 __copy_move_backward_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
770 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
773 template<
bool _IsMove,
774 typename _ITp,
typename _IRef,
typename _IPtr,
typename _OTp>
775 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
776 __copy_move_backward_a1(
777 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
778 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr>,
779 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>);
781 template<
bool _IsMove,
typename _II,
typename _Tp>
782 typename __gnu_cxx::__enable_if<
783 __is_random_access_iter<_II>::__value,
784 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
785 __copy_move_backward_a1(_II, _II,
786 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>);
788 template<
bool _IsMove,
typename _II,
typename _OI>
789 __attribute__((__always_inline__))
792 __copy_move_backward_a(_II __first, _II __last, _OI __result)
794 return std::__niter_wrap(__result,
795 std::__copy_move_backward_a1<_IsMove>
796 (std::__niter_base(__first), std::__niter_base(__last),
797 std::__niter_base(__result)));
800 template<
bool _IsMove,
801 typename _Ite,
typename _Seq,
typename _Cat,
typename _OI>
804 __copy_move_backward_a(
805 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
806 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
809 template<
bool _IsMove,
810 typename _II,
typename _Ite,
typename _Seq,
typename _Cat>
813 __copy_move_backward_a(_II, _II,
814 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
816 template<
bool _IsMove,
817 typename _IIte,
typename _ISeq,
typename _ICat,
818 typename _OIte,
typename _OSeq,
typename _OCat>
820 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
821 __copy_move_backward_a(
822 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
823 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
824 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
844 template<
typename _BI1,
typename _BI2>
845 __attribute__((__always_inline__))
848 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
851 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
852 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
853 __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
855 __glibcxx_requires_can_decrement_range(__first, __last, __result);
857 return std::__copy_move_backward_a<__is_move_iterator<_BI1>::__value>
858 (std::__miter_base(__first), std::__miter_base(__last), __result);
861#if __cplusplus >= 201103L
880 template<
typename _BI1,
typename _BI2>
881 __attribute__((__always_inline__))
887 __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
888 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
889 __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
891 __glibcxx_requires_can_decrement_range(__first, __last, __result);
893 return std::__copy_move_backward_a<true>(std::__miter_base(__first),
894 std::__miter_base(__last),
898#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::move_backward(_Tp, _Up, _Vp)
900#define _GLIBCXX_MOVE_BACKWARD3(_Tp, _Up, _Vp) std::copy_backward(_Tp, _Up, _Vp)
903#pragma GCC diagnostic push
904#pragma GCC diagnostic ignored "-Wc++17-extensions"
905 template<
typename _ForwardIterator,
typename _Tp>
908 __fill_a1(_ForwardIterator __first, _ForwardIterator __last,
911#pragma GCC diagnostic push
912#pragma GCC diagnostic ignored "-Wlong-long"
917 const bool __load_outside_loop =
918#if __has_builtin(__is_trivially_constructible) \
919 && __has_builtin(__is_trivially_assignable)
920 __is_trivially_constructible(_Tp,
const _Tp&)
921 && __is_trivially_assignable(__decltype(*__first),
const _Tp&)
923 __is_trivially_copyable(_Tp)
924 && __is_same(_Tp, __typeof__(*__first))
926 &&
sizeof(_Tp) <=
sizeof(
long long);
927#pragma GCC diagnostic pop
931 typedef typename __gnu_cxx::__conditional_type<__load_outside_loop,
933 const _Tp&>::__type _Up;
935 for (; __first != __last; ++__first)
938#pragma GCC diagnostic pop
941 template<
typename _Up,
typename _Tp>
944 __gnu_cxx::__enable_if<__is_byte<_Up>::__value
945 && (__are_same<_Up, _Tp>::__value
946 || __memcpyable_integer<_Tp>::__value),
948 __fill_a1(_Up* __first, _Up* __last,
const _Tp& __x)
952 const _Up __val = __x;
953#if __cpp_lib_is_constant_evaluated
954 if (std::is_constant_evaluated())
956 for (; __first != __last; ++__first)
960 if (
const size_t __len = __last - __first)
961 __builtin_memset(__first,
static_cast<unsigned char>(__val), __len);
964 template<
typename _Ite,
typename _Cont,
typename _Tp>
965 __attribute__((__always_inline__))
968 __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first,
969 ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last,
971 { std::__fill_a1(__first.base(), __last.base(), __value); }
973 template<
typename _Tp,
typename _VTp>
975 __fill_a1(
const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
976 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
981 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator,
984 template<
typename _FIte,
typename _Tp>
985 __attribute__((__always_inline__))
988 __fill_a(_FIte __first, _FIte __last,
const _Tp& __value)
989 { std::__fill_a1(__first, __last, __value); }
991 template<
typename _Ite,
typename _Seq,
typename _Cat,
typename _Tp>
994 __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
995 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
1010 template<
typename _ForwardIterator,
typename _Tp>
1011 __attribute__((__always_inline__))
1012 _GLIBCXX20_CONSTEXPR
1014 fill(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __value)
1017 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1019 __glibcxx_requires_valid_range(__first, __last);
1021 std::__fill_a(__first, __last, __value);
1024#pragma GCC diagnostic push
1025#pragma GCC diagnostic ignored "-Wlong-long"
1027 inline _GLIBCXX_CONSTEXPR
int
1028 __size_to_integer(
int __n) {
return __n; }
1029 inline _GLIBCXX_CONSTEXPR
unsigned
1030 __size_to_integer(
unsigned __n) {
return __n; }
1031 inline _GLIBCXX_CONSTEXPR
long
1032 __size_to_integer(
long __n) {
return __n; }
1033 inline _GLIBCXX_CONSTEXPR
unsigned long
1034 __size_to_integer(
unsigned long __n) {
return __n; }
1035 inline _GLIBCXX_CONSTEXPR
long long
1036 __size_to_integer(
long long __n) {
return __n; }
1037 inline _GLIBCXX_CONSTEXPR
unsigned long long
1038 __size_to_integer(
unsigned long long __n) {
return __n; }
1040#if defined(__GLIBCXX_TYPE_INT_N_0)
1041 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
1042 __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1043 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_0
1044 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1046#if defined(__GLIBCXX_TYPE_INT_N_1)
1047 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
1048 __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1049 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_1
1050 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1052#if defined(__GLIBCXX_TYPE_INT_N_2)
1053 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
1054 __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1055 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_2
1056 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1058#if defined(__GLIBCXX_TYPE_INT_N_3)
1059 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_3
1060 __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1061 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
1062 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1065 inline _GLIBCXX_CONSTEXPR
long long
1066 __size_to_integer(
float __n) {
return (
long long)__n; }
1067 inline _GLIBCXX_CONSTEXPR
long long
1068 __size_to_integer(
double __n) {
return (
long long)__n; }
1069 inline _GLIBCXX_CONSTEXPR
long long
1070 __size_to_integer(
long double __n) {
return (
long long)__n; }
1071#if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128)
1072 __extension__
inline _GLIBCXX_CONSTEXPR
long long
1073 __size_to_integer(__float128 __n) {
return (
long long)__n; }
1075#pragma GCC diagnostic pop
1077#pragma GCC diagnostic push
1078#pragma GCC diagnostic ignored "-Wc++17-extensions"
1079#pragma GCC diagnostic ignored "-Wlong-long"
1080 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1081 _GLIBCXX20_CONSTEXPR
1082 inline _OutputIterator
1083 __fill_n_a1(_OutputIterator __first, _Size __n,
const _Tp& __value)
1086 const bool __load_outside_loop =
1087#if __has_builtin(__is_trivially_constructible) \
1088 && __has_builtin(__is_trivially_assignable)
1089 __is_trivially_constructible(_Tp,
const _Tp&)
1090 && __is_trivially_assignable(__decltype(*__first),
const _Tp&)
1092 __is_trivially_copyable(_Tp)
1093 && __is_same(_Tp, __typeof__(*__first))
1095 &&
sizeof(_Tp) <=
sizeof(
long long);
1099 typedef typename __gnu_cxx::__conditional_type<__load_outside_loop,
1101 const _Tp&>::__type _Up;
1103 for (; __n > 0; --__n, (void) ++__first)
1107#pragma GCC diagnostic pop
1109 template<
typename _Ite,
typename _Seq,
typename _Cat,
typename _Size,
1111 _GLIBCXX20_CONSTEXPR
1112 ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
1113 __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
1114 _Size __n,
const _Tp& __value,
1117 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1118 __attribute__((__always_inline__))
1119 _GLIBCXX20_CONSTEXPR
1120 inline _OutputIterator
1121 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1124#if __cplusplus >= 201103L
1125 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1127 return __fill_n_a1(__first, __n, __value);
1130 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1131 __attribute__((__always_inline__))
1132 _GLIBCXX20_CONSTEXPR
1133 inline _OutputIterator
1134 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1137#if __cplusplus >= 201103L
1138 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1140 return __fill_n_a1(__first, __n, __value);
1143 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1144 __attribute__((__always_inline__))
1145 _GLIBCXX20_CONSTEXPR
1146 inline _OutputIterator
1147 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1150#if __cplusplus >= 201103L
1151 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1156 __glibcxx_requires_can_increment(__first, __n);
1158 std::__fill_a(__first, __first + __n, __value);
1159 return __first + __n;
1179 template<
typename _OI,
typename _Size,
typename _Tp>
1180 __attribute__((__always_inline__))
1181 _GLIBCXX20_CONSTEXPR
1183 fill_n(_OI __first, _Size __n,
const _Tp& __value)
1186 __glibcxx_function_requires(_OutputIteratorConcept<_OI, const _Tp&>)
1188 return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
1192 template<
bool _BoolType>
1195 template<
typename _II1,
typename _II2>
1196 _GLIBCXX20_CONSTEXPR
1198 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1200 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1201 if (!(*__first1 == *__first2))
1208 struct __equal<true>
1210 template<
typename _Tp>
1211 _GLIBCXX20_CONSTEXPR
1213 equal(
const _Tp* __first1,
const _Tp* __last1,
const _Tp* __first2)
1215 if (
const size_t __len = (__last1 - __first1))
1216 return !std::__memcmp(__first1, __first2, __len);
1221 template<
typename _Tp,
typename _Ref,
typename _Ptr,
typename _II>
1222 typename __gnu_cxx::__enable_if<
1223 __is_random_access_iter<_II>::__value,
bool>::__type
1224 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1225 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1228 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1229 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1231 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1232 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1233 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1235 template<
typename _II,
typename _Tp,
typename _Ref,
typename _Ptr>
1236 typename __gnu_cxx::__enable_if<
1237 __is_random_access_iter<_II>::__value,
bool>::__type
1238 __equal_aux1(_II, _II,
1239 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>);
1241 template<
typename _II1,
typename _II2>
1242 _GLIBCXX20_CONSTEXPR
1244 __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
1246 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1247 const bool __simple = ((__is_integer<_ValueType1>::__value
1248#if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1249 || __is_pointer(_ValueType1)
1251#if __glibcxx_byte && __glibcxx_type_trait_variable_templates
1253 || is_same_v<_ValueType1, byte>
1255 ) && __memcmpable<_II1, _II2>::__value);
1256 return std::__equal<__simple>::equal(__first1, __last1, __first2);
1259 template<
typename _II1,
typename _II2>
1260 __attribute__((__always_inline__))
1261 _GLIBCXX20_CONSTEXPR
1263 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
1265 return std::__equal_aux1(std::__niter_base(__first1),
1266 std::__niter_base(__last1),
1267 std::__niter_base(__first2));
1270 template<
typename _II1,
typename _Seq1,
typename _Cat1,
typename _II2>
1271 _GLIBCXX20_CONSTEXPR
1273 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1274 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1277 template<
typename _II1,
typename _II2,
typename _Seq2,
typename _Cat2>
1278 _GLIBCXX20_CONSTEXPR
1280 __equal_aux(_II1, _II1,
1281 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1283 template<
typename _II1,
typename _Seq1,
typename _Cat1,
1284 typename _II2,
typename _Seq2,
typename _Cat2>
1285 _GLIBCXX20_CONSTEXPR
1287 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1288 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1289 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1291 template<
typename,
typename>
1294 template<
typename _II1,
typename _II2>
1295 _GLIBCXX20_CONSTEXPR
1297 __newlast1(_II1, _II1 __last1, _II2, _II2)
1300 template<
typename _II>
1301 _GLIBCXX20_CONSTEXPR
1303 __cnd2(_II __first, _II __last)
1304 {
return __first != __last; }
1308 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
1310 template<
typename _RAI1,
typename _RAI2>
1311 _GLIBCXX20_CONSTEXPR
1313 __newlast1(_RAI1 __first1, _RAI1 __last1,
1314 _RAI2 __first2, _RAI2 __last2)
1316 const typename iterator_traits<_RAI1>::difference_type
1317 __diff1 = __last1 - __first1;
1318 const typename iterator_traits<_RAI2>::difference_type
1319 __diff2 = __last2 - __first2;
1320 return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
1323 template<
typename _RAI>
1324 static _GLIBCXX20_CONSTEXPR
bool
1329 template<
typename _II1,
typename _II2,
typename _Compare>
1330 _GLIBCXX20_CONSTEXPR
1332 __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
1333 _II2 __first2, _II2 __last2,
1336 typedef typename iterator_traits<_II1>::iterator_category _Category1;
1337 typedef typename iterator_traits<_II2>::iterator_category _Category2;
1338 typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1340 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1341 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1342 ++__first1, (void)++__first2)
1344 if (__comp(__first1, __first2))
1346 if (__comp(__first2, __first1))
1349 return __first1 == __last1 && __first2 != __last2;
1352 template<
bool _BoolType>
1353 struct __lexicographical_compare
1355 template<
typename _II1,
typename _II2>
1356 _GLIBCXX20_CONSTEXPR
1358 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1360 using __gnu_cxx::__ops::__iter_less_iter;
1361 return std::__lexicographical_compare_impl(__first1, __last1,
1363 __iter_less_iter());
1366 template<
typename _II1,
typename _II2>
1367 _GLIBCXX20_CONSTEXPR
1369 __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1371 while (__first1 != __last1)
1373 if (__first2 == __last2)
1375 if (*__first1 < *__first2)
1377 if (*__first2 < *__first1)
1382 return int(__first2 == __last2) - 1;
1387 struct __lexicographical_compare<true>
1389 template<
typename _Tp,
typename _Up>
1390 _GLIBCXX20_CONSTEXPR
1392 __lc(
const _Tp* __first1,
const _Tp* __last1,
1393 const _Up* __first2,
const _Up* __last2)
1394 {
return __3way(__first1, __last1, __first2, __last2) < 0; }
1396 template<
typename _Tp,
typename _Up>
1397 _GLIBCXX20_CONSTEXPR
1399 __3way(
const _Tp* __first1,
const _Tp* __last1,
1400 const _Up* __first2,
const _Up* __last2)
1402 const size_t __len1 = __last1 - __first1;
1403 const size_t __len2 = __last2 - __first2;
1404 if (
const size_t __len =
std::min(__len1, __len2))
1405 if (
int __result = std::__memcmp(__first1, __first2, __len))
1407 return ptrdiff_t(__len1 - __len2);
1411 template<
typename _II1,
typename _II2>
1412 _GLIBCXX20_CONSTEXPR
1414 __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
1415 _II2 __first2, _II2 __last2)
1417 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1418 typedef typename iterator_traits<_II2>::value_type _ValueType2;
1419#if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1420 const bool __simple =
1421 (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
1422 && __is_pointer(_II1) && __is_pointer(_II2)
1423#if __cplusplus > 201703L && __glibcxx_concepts
1427 && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>>
1428 && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>>
1432 const bool __simple =
false;
1435 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
1439 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1442 __lexicographical_compare_aux1(
1443 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1444 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1447 template<
typename _Tp1,
1448 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1450 __lexicographical_compare_aux1(_Tp1*, _Tp1*,
1451 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1452 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1454 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1455 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1457 __lexicographical_compare_aux1(
1458 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1459 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1460 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1461 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1463 template<
typename _II1,
typename _II2>
1464 _GLIBCXX20_CONSTEXPR
1466 __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
1467 _II2 __first2, _II2 __last2)
1469 return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
1470 std::__niter_base(__last1),
1471 std::__niter_base(__first2),
1472 std::__niter_base(__last2));
1475 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
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>&,
1484 template<
typename _II1,
1485 typename _Iter2,
typename _Seq2,
typename _Cat2>
1486 _GLIBCXX20_CONSTEXPR
1488 __lexicographical_compare_aux(
1490 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1491 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1493 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
1494 typename _Iter2,
typename _Seq2,
typename _Cat2>
1495 _GLIBCXX20_CONSTEXPR
1497 __lexicographical_compare_aux(
1498 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1499 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1500 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1501 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1503 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1504 _GLIBCXX20_CONSTEXPR
1506 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1507 const _Tp& __val, _Compare __comp)
1509 typedef typename iterator_traits<_ForwardIterator>::difference_type
1516 _DistanceType __half = __len >> 1;
1517 _ForwardIterator __middle = __first;
1519 if (__comp(__middle, __val))
1523 __len = __len - __half - 1;
1542 template<
typename _ForwardIterator,
typename _Tp>
1543 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1544 inline _ForwardIterator
1545 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1549 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1550 __glibcxx_function_requires(_LessThanOpConcept<
1552 __glibcxx_requires_partitioned_lower(__first, __last, __val);
1554 return std::__lower_bound(__first, __last, __val,
1555 __gnu_cxx::__ops::__iter_less_val());
1560 template<
typename _Tp>
1561 inline _GLIBCXX_CONSTEXPR _Tp
1564#if __cplusplus >= 201402L
1567#pragma GCC diagnostic push
1568#pragma GCC diagnostic ignored "-Wlong-long"
1570 return (
sizeof(+__n) * __CHAR_BIT__ - 1)
1571 - (
sizeof(+__n) ==
sizeof(
long long)
1572 ? __builtin_clzll(+__n)
1573 : (
sizeof(+__n) ==
sizeof(long)
1574 ? __builtin_clzl(+__n)
1575 : __builtin_clz(+__n)));
1576#pragma GCC diagnostic pop
1580_GLIBCXX_BEGIN_NAMESPACE_ALGO
1594 template<
typename _II1,
typename _II2>
1595 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1597 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1600 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1601 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1602 __glibcxx_function_requires(_EqualOpConcept<
1605 __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
1607 return std::__equal_aux(__first1, __last1, __first2);
1625 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1626 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1628 equal(_IIter1 __first1, _IIter1 __last1,
1629 _IIter2 __first2, _BinaryPredicate __binary_pred)
1632 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1633 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1634 __glibcxx_requires_valid_range(__first1, __last1);
1636 for (; __first1 != __last1; ++__first1, (void)++__first2)
1637 if (!
bool(__binary_pred(*__first1, *__first2)))
1642#if __cplusplus >= 201103L
1643#pragma GCC diagnostic push
1644#pragma GCC diagnostic ignored "-Wc++17-extensions"
1647 template<
typename _II1,
typename _II2>
1648 _GLIBCXX20_CONSTEXPR
1650 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1652 using _RATag = random_access_iterator_tag;
1653 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1654 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1655 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1656 if constexpr (_RAIters::value)
1658 if ((__last1 - __first1) != (__last2 - __first2))
1660 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1664 for (; __first1 != __last1 && __first2 != __last2;
1665 ++__first1, (void)++__first2)
1666 if (!(*__first1 == *__first2))
1668 return __first1 == __last1 && __first2 == __last2;
1673 template<
typename _II1,
typename _II2,
typename _BinaryPredicate>
1674 _GLIBCXX20_CONSTEXPR
1676 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2,
1677 _BinaryPredicate __binary_pred)
1679 using _RATag = random_access_iterator_tag;
1680 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1681 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1682 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1683 if constexpr (_RAIters::value)
1685 if ((__last1 - __first1) != (__last2 - __first2))
1687 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1692 for (; __first1 != __last1 && __first2 != __last2;
1693 ++__first1, (void)++__first2)
1694 if (!
bool(__binary_pred(*__first1, *__first2)))
1696 return __first1 == __last1 && __first2 == __last2;
1699#pragma GCC diagnostic pop
1702#ifdef __glibcxx_robust_nonmodifying_seq_ops
1716 template<
typename _II1,
typename _II2>
1717 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1719 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1722 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1723 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1724 __glibcxx_function_requires(_EqualOpConcept<
1727 __glibcxx_requires_valid_range(__first1, __last1);
1728 __glibcxx_requires_valid_range(__first2, __last2);
1730 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2);
1749 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1750 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1752 equal(_IIter1 __first1, _IIter1 __last1,
1753 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
1756 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1757 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1758 __glibcxx_requires_valid_range(__first1, __last1);
1759 __glibcxx_requires_valid_range(__first2, __last2);
1761 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2,
1781 template<
typename _II1,
typename _II2>
1782 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1784 lexicographical_compare(_II1 __first1, _II1 __last1,
1785 _II2 __first2, _II2 __last2)
1787#ifdef _GLIBCXX_CONCEPT_CHECKS
1792 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1793 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1794 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1795 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1796 __glibcxx_requires_valid_range(__first1, __last1);
1797 __glibcxx_requires_valid_range(__first2, __last2);
1799 return std::__lexicographical_compare_aux(__first1, __last1,
1816 template<
typename _II1,
typename _II2,
typename _Compare>
1817 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1819 lexicographical_compare(_II1 __first1, _II1 __last1,
1820 _II2 __first2, _II2 __last2, _Compare __comp)
1823 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1824 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1825 __glibcxx_requires_valid_range(__first1, __last1);
1826 __glibcxx_requires_valid_range(__first2, __last2);
1828 return std::__lexicographical_compare_impl
1829 (__first1, __last1, __first2, __last2,
1830 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1833#if __cpp_lib_three_way_comparison
1837 template<
typename _Iter1,
typename _Iter2>
1838 concept __memcmp_ordered_with
1839 = (__is_memcmp_ordered_with<iter_value_t<_Iter1>,
1840 iter_value_t<_Iter2>>::__value)
1841 && contiguous_iterator<_Iter1> && contiguous_iterator<_Iter2>;
1845 template<
typename _Tp>
1847 __min_cmp(_Tp __x, _Tp __y)
1851 decltype(__x <=> __y) _M_cmp;
1853 auto __c = __x <=> __y;
1855 return _Res{__y, __c};
1856 return _Res{__x, __c};
1870 template<
typename _InputIter1,
typename _InputIter2,
typename _Comp>
1871 [[nodiscard]]
constexpr auto
1873 _InputIter1 __last1,
1874 _InputIter2 __first2,
1875 _InputIter2 __last2,
1877 ->
decltype(__comp(*__first1, *__first2))
1880 __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
1881 __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
1882 __glibcxx_requires_valid_range(__first1, __last1);
1883 __glibcxx_requires_valid_range(__first2, __last2);
1885 using _Cat =
decltype(__comp(*__first1, *__first2));
1886 static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
1888 if (!std::__is_constant_evaluated())
1889 if constexpr (same_as<_Comp, __detail::_Synth3way>
1890 || same_as<_Comp, compare_three_way>)
1891 if constexpr (__memcmp_ordered_with<_InputIter1, _InputIter2>)
1893 const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1894 __min_cmp(__last1 - __first1, __last2 - __first2);
1897 const auto __blen = __len *
sizeof(*__first1);
1899 = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 0;
1906 while (__first1 != __last1)
1908 if (__first2 == __last2)
1909 return strong_ordering::greater;
1910 if (
auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
1915 return (__first2 == __last2) <=>
true;
1918 template<
typename _InputIter1,
typename _InputIter2>
1921 _InputIter1 __last1,
1922 _InputIter2 __first2,
1923 _InputIter2 __last2)
1925 return _GLIBCXX_STD_A::
1926 lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
1927 compare_three_way{});
1931 template<
typename _InputIterator1,
typename _InputIterator2,
1932 typename _BinaryPredicate>
1933 _GLIBCXX20_CONSTEXPR
1935 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1936 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1938 while (__first1 != __last1 && __binary_pred(__first1, __first2))
1959 template<
typename _InputIterator1,
typename _InputIterator2>
1960 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1962 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1963 _InputIterator2 __first2)
1966 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1967 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1968 __glibcxx_function_requires(_EqualOpConcept<
1971 __glibcxx_requires_valid_range(__first1, __last1);
1973 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1974 __gnu_cxx::__ops::__iter_equal_to_iter());
1993 template<
typename _InputIterator1,
typename _InputIterator2,
1994 typename _BinaryPredicate>
1995 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1997 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1998 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
2001 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2002 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2003 __glibcxx_requires_valid_range(__first1, __last1);
2005 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
2006 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
2009#if __glibcxx_robust_nonmodifying_seq_ops
2010 template<
typename _InputIterator1,
typename _InputIterator2,
2011 typename _BinaryPredicate>
2012 _GLIBCXX20_CONSTEXPR
2014 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2015 _InputIterator2 __first2, _InputIterator2 __last2,
2016 _BinaryPredicate __binary_pred)
2018 while (__first1 != __last1 && __first2 != __last2
2019 && __binary_pred(__first1, __first2))
2041 template<
typename _InputIterator1,
typename _InputIterator2>
2042 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2044 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2045 _InputIterator2 __first2, _InputIterator2 __last2)
2048 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2049 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2050 __glibcxx_function_requires(_EqualOpConcept<
2053 __glibcxx_requires_valid_range(__first1, __last1);
2054 __glibcxx_requires_valid_range(__first2, __last2);
2056 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2057 __gnu_cxx::__ops::__iter_equal_to_iter());
2077 template<
typename _InputIterator1,
typename _InputIterator2,
2078 typename _BinaryPredicate>
2079 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2081 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2082 _InputIterator2 __first2, _InputIterator2 __last2,
2083 _BinaryPredicate __binary_pred)
2086 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2087 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2088 __glibcxx_requires_valid_range(__first1, __last1);
2089 __glibcxx_requires_valid_range(__first2, __last2);
2091 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2092 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
2096_GLIBCXX_END_NAMESPACE_ALGO
2099 template<
typename _Iterator,
typename _Predicate>
2100 _GLIBCXX20_CONSTEXPR
2102 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
2105 while (__first != __last && !__pred(__first))
2110 template<
typename _InputIterator,
typename _Predicate>
2111 _GLIBCXX20_CONSTEXPR
2112 typename iterator_traits<_InputIterator>::difference_type
2113 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2115 typename iterator_traits<_InputIterator>::difference_type __n = 0;
2116 for (; __first != __last; ++__first)
2117 if (__pred(__first))
2122 template<
typename _ForwardIterator,
typename _Predicate>
2123 _GLIBCXX20_CONSTEXPR
2125 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
2128 __first = std::__find_if(__first, __last, __pred);
2129 if (__first == __last)
2131 _ForwardIterator __result = __first;
2133 for (; __first != __last; ++__first)
2134 if (!__pred(__first))
2136 *__result = _GLIBCXX_MOVE(*__first);
2142 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2143 typename _BinaryPredicate>
2144 _GLIBCXX20_CONSTEXPR
2146 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2147 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2148 _BinaryPredicate __predicate)
2151 if (__first1 == __last1 || __first2 == __last2)
2155 _ForwardIterator2 __p1(__first2);
2156 if (++__p1 == __last2)
2157 return std::__find_if(__first1, __last1,
2158 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2161 _ForwardIterator1 __current = __first1;
2166 std::__find_if(__first1, __last1,
2167 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2169 if (__first1 == __last1)
2172 _ForwardIterator2 __p = __p1;
2173 __current = __first1;
2174 if (++__current == __last1)
2177 while (__predicate(__current, __p))
2179 if (++__p == __last2)
2181 if (++__current == __last1)
2189#if __cplusplus >= 201103L
2190 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2191 typename _BinaryPredicate>
2192 _GLIBCXX20_CONSTEXPR
2194 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2195 _ForwardIterator2 __first2, _BinaryPredicate __pred)
2199 for (; __first1 != __last1; ++__first1, (void)++__first2)
2200 if (!__pred(__first1, __first2))
2203 if (__first1 == __last1)
2208 _ForwardIterator2 __last2 = __first2;
2210 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
2212 if (__scan != std::__find_if(__first1, __scan,
2213 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
2217 = std::__count_if(__first2, __last2,
2218 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
2219 if (0 == __matches ||
2220 std::__count_if(__scan, __last1,
2221 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
2240 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
2241 _GLIBCXX20_CONSTEXPR
2243 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2244 _ForwardIterator2 __first2)
2247 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2248 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2249 __glibcxx_function_requires(_EqualOpConcept<
2252 __glibcxx_requires_valid_range(__first1, __last1);
2254 return std::__is_permutation(__first1, __last1, __first2,
2255 __gnu_cxx::__ops::__iter_equal_to_iter());
2259_GLIBCXX_BEGIN_NAMESPACE_ALGO
2282 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2283 typename _BinaryPredicate>
2284 _GLIBCXX20_CONSTEXPR
2285 inline _ForwardIterator1
2286 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2287 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2288 _BinaryPredicate __predicate)
2291 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2292 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2293 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
2296 __glibcxx_requires_valid_range(__first1, __last1);
2297 __glibcxx_requires_valid_range(__first2, __last2);
2299 return std::__search(__first1, __last1, __first2, __last2,
2300 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
2303_GLIBCXX_END_NAMESPACE_ALGO
2304_GLIBCXX_END_NAMESPACE_VERSION
2310#ifdef _GLIBCXX_PARALLEL
Parallel STL function calls corresponding to the stl_algobase.h header. The functions defined here ma...
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
pair(_T1, _T2) -> pair< _T1, _T2 >
Two pairs are equal iff their members are equal.
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 void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Marking output iterators.
Random-access iterators support a superset of bidirectional iterator operations.
Traits class for iterators.