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>::__width),
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)
961 if (
const size_t __len = __last - __first)
962 __builtin_memset(__first,
static_cast<unsigned char>(__val), __len);
965 template<
typename _Ite,
typename _Cont,
typename _Tp>
966 __attribute__((__always_inline__))
969 __fill_a1(::__gnu_cxx::__normal_iterator<_Ite, _Cont> __first,
970 ::__gnu_cxx::__normal_iterator<_Ite, _Cont> __last,
972 { std::__fill_a1(__first.base(), __last.base(), __value); }
974 template<
typename _Tp,
typename _VTp>
976 __fill_a1(
const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
977 const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
982 __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator,
985 template<
typename _FIte,
typename _Tp>
986 __attribute__((__always_inline__))
989 __fill_a(_FIte __first, _FIte __last,
const _Tp& __value)
990 { std::__fill_a1(__first, __last, __value); }
992 template<
typename _Ite,
typename _Seq,
typename _Cat,
typename _Tp>
995 __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
996 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
1011 template<
typename _ForwardIterator,
typename _Tp>
1012 __attribute__((__always_inline__))
1013 _GLIBCXX20_CONSTEXPR
1015 fill(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __value)
1018 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1020 __glibcxx_requires_valid_range(__first, __last);
1022 std::__fill_a(__first, __last, __value);
1025#pragma GCC diagnostic push
1026#pragma GCC diagnostic ignored "-Wlong-long"
1028 inline _GLIBCXX_CONSTEXPR
int
1029 __size_to_integer(
int __n) {
return __n; }
1030 inline _GLIBCXX_CONSTEXPR
unsigned
1031 __size_to_integer(
unsigned __n) {
return __n; }
1032 inline _GLIBCXX_CONSTEXPR
long
1033 __size_to_integer(
long __n) {
return __n; }
1034 inline _GLIBCXX_CONSTEXPR
unsigned long
1035 __size_to_integer(
unsigned long __n) {
return __n; }
1036 inline _GLIBCXX_CONSTEXPR
long long
1037 __size_to_integer(
long long __n) {
return __n; }
1038 inline _GLIBCXX_CONSTEXPR
unsigned long long
1039 __size_to_integer(
unsigned long long __n) {
return __n; }
1041#if defined(__GLIBCXX_TYPE_INT_N_0)
1042 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
1043 __size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1044 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_0
1045 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_0 __n) {
return __n; }
1047#if defined(__GLIBCXX_TYPE_INT_N_1)
1048 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
1049 __size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1050 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_1
1051 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_1 __n) {
return __n; }
1053#if defined(__GLIBCXX_TYPE_INT_N_2)
1054 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
1055 __size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1056 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_2
1057 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_2 __n) {
return __n; }
1059#if defined(__GLIBCXX_TYPE_INT_N_3)
1060 __extension__
inline _GLIBCXX_CONSTEXPR
unsigned __GLIBCXX_TYPE_INT_N_3
1061 __size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1062 __extension__
inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
1063 __size_to_integer(
unsigned __GLIBCXX_TYPE_INT_N_3 __n) {
return __n; }
1066 inline _GLIBCXX_CONSTEXPR
long long
1067 __size_to_integer(
float __n) {
return (
long long)__n; }
1068 inline _GLIBCXX_CONSTEXPR
long long
1069 __size_to_integer(
double __n) {
return (
long long)__n; }
1070 inline _GLIBCXX_CONSTEXPR
long long
1071 __size_to_integer(
long double __n) {
return (
long long)__n; }
1072#if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128) && !defined(__CUDACC__)
1073 __extension__
inline _GLIBCXX_CONSTEXPR
long long
1074 __size_to_integer(__float128 __n) {
return (
long long)__n; }
1076#pragma GCC diagnostic pop
1078#pragma GCC diagnostic push
1079#pragma GCC diagnostic ignored "-Wc++17-extensions"
1080#pragma GCC diagnostic ignored "-Wlong-long"
1081 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1082 _GLIBCXX20_CONSTEXPR
1083 inline _OutputIterator
1084 __fill_n_a1(_OutputIterator __first, _Size __n,
const _Tp& __value)
1087 const bool __load_outside_loop =
1088#if __has_builtin(__is_trivially_constructible) \
1089 && __has_builtin(__is_trivially_assignable)
1090 __is_trivially_constructible(_Tp,
const _Tp&)
1091 && __is_trivially_assignable(__decltype(*__first),
const _Tp&)
1093 __is_trivially_copyable(_Tp)
1094 && __is_same(_Tp, __typeof__(*__first))
1096 &&
sizeof(_Tp) <=
sizeof(
long long);
1100 typedef typename __gnu_cxx::__conditional_type<__load_outside_loop,
1102 const _Tp&>::__type _Up;
1104 for (; __n > 0; --__n, (void) ++__first)
1108#pragma GCC diagnostic pop
1110 template<
typename _Ite,
typename _Seq,
typename _Cat,
typename _Size,
1112 _GLIBCXX20_CONSTEXPR
1113 ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
1114 __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
1115 _Size __n,
const _Tp& __value,
1118 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1119 __attribute__((__always_inline__))
1120 _GLIBCXX20_CONSTEXPR
1121 inline _OutputIterator
1122 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1125#if __cplusplus >= 201103L
1126 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1128 return __fill_n_a1(__first, __n, __value);
1131 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1132 __attribute__((__always_inline__))
1133 _GLIBCXX20_CONSTEXPR
1134 inline _OutputIterator
1135 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1138#if __cplusplus >= 201103L
1139 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1141 return __fill_n_a1(__first, __n, __value);
1144 template<
typename _OutputIterator,
typename _Size,
typename _Tp>
1145 __attribute__((__always_inline__))
1146 _GLIBCXX20_CONSTEXPR
1147 inline _OutputIterator
1148 __fill_n_a(_OutputIterator __first, _Size __n,
const _Tp& __value,
1151#if __cplusplus >= 201103L
1152 static_assert(is_integral<_Size>{},
"fill_n must pass integral size");
1157 __glibcxx_requires_can_increment(__first, __n);
1159 std::__fill_a(__first, __first + __n, __value);
1160 return __first + __n;
1180 template<
typename _OI,
typename _Size,
typename _Tp>
1181 __attribute__((__always_inline__))
1182 _GLIBCXX20_CONSTEXPR
1184 fill_n(_OI __first, _Size __n,
const _Tp& __value)
1187 __glibcxx_function_requires(_OutputIteratorConcept<_OI, const _Tp&>)
1189 return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
1193 template<
bool _BoolType>
1196 template<
typename _II1,
typename _II2>
1197 _GLIBCXX20_CONSTEXPR
1199 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1201 for (; __first1 != __last1; ++__first1, (void) ++__first2)
1202 if (!(*__first1 == *__first2))
1209 struct __equal<true>
1211 template<
typename _Tp>
1212 _GLIBCXX20_CONSTEXPR
1214 equal(
const _Tp* __first1,
const _Tp* __last1,
const _Tp* __first2)
1216 if (
const size_t __len = (__last1 - __first1))
1217 return !std::__memcmp(__first1, __first2, __len);
1222 template<
typename _Tp,
typename _Ref,
typename _Ptr,
typename _II>
1223 typename __gnu_cxx::__enable_if<
1224 __is_random_access_iter<_II>::__value,
bool>::__type
1225 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1226 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>,
1229 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1230 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1232 __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1233 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1234 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1236 template<
typename _II,
typename _Tp,
typename _Ref,
typename _Ptr>
1237 typename __gnu_cxx::__enable_if<
1238 __is_random_access_iter<_II>::__value,
bool>::__type
1239 __equal_aux1(_II, _II,
1240 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>);
1242 template<
typename _II1,
typename _II2>
1243 _GLIBCXX20_CONSTEXPR
1245 __equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
1247 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1248 const bool __simple = ((__is_integer<_ValueType1>::__value
1249#if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1250 || __is_pointer(_ValueType1)
1252#if __glibcxx_byte && __glibcxx_type_trait_variable_templates
1254 || is_same_v<_ValueType1, byte>
1256 ) && __memcmpable<_II1, _II2>::__value);
1257 return std::__equal<__simple>::equal(__first1, __last1, __first2);
1260 template<
typename _II1,
typename _II2>
1261 __attribute__((__always_inline__))
1262 _GLIBCXX20_CONSTEXPR
1264 __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2)
1266 return std::__equal_aux1(std::__niter_base(__first1),
1267 std::__niter_base(__last1),
1268 std::__niter_base(__first2));
1271 template<
typename _II1,
typename _Seq1,
typename _Cat1,
typename _II2>
1272 _GLIBCXX20_CONSTEXPR
1274 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1275 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1278 template<
typename _II1,
typename _II2,
typename _Seq2,
typename _Cat2>
1279 _GLIBCXX20_CONSTEXPR
1281 __equal_aux(_II1, _II1,
1282 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1284 template<
typename _II1,
typename _Seq1,
typename _Cat1,
1285 typename _II2,
typename _Seq2,
typename _Cat2>
1286 _GLIBCXX20_CONSTEXPR
1288 __equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1289 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
1290 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
1292 template<
typename,
typename>
1295 template<
typename _II1,
typename _II2>
1296 _GLIBCXX20_CONSTEXPR
1298 __newlast1(_II1, _II1 __last1, _II2, _II2)
1301 template<
typename _II>
1302 _GLIBCXX20_CONSTEXPR
1304 __cnd2(_II __first, _II __last)
1305 {
return __first != __last; }
1309 struct __lc_rai<random_access_iterator_tag, random_access_iterator_tag>
1311 template<
typename _RAI1,
typename _RAI2>
1312 _GLIBCXX20_CONSTEXPR
1314 __newlast1(_RAI1 __first1, _RAI1 __last1,
1315 _RAI2 __first2, _RAI2 __last2)
1317 const typename iterator_traits<_RAI1>::difference_type
1318 __diff1 = __last1 - __first1;
1319 const typename iterator_traits<_RAI2>::difference_type
1320 __diff2 = __last2 - __first2;
1321 return __diff2 < __diff1 ? __first1 + __diff2 : __last1;
1324 template<
typename _RAI>
1325 static _GLIBCXX20_CONSTEXPR
bool
1330 template<
typename _II1,
typename _II2,
typename _Compare>
1331 _GLIBCXX20_CONSTEXPR
1333 __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
1334 _II2 __first2, _II2 __last2,
1337 typedef typename iterator_traits<_II1>::iterator_category _Category1;
1338 typedef typename iterator_traits<_II2>::iterator_category _Category2;
1339 typedef std::__lc_rai<_Category1, _Category2> __rai_type;
1341 __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
1342 for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
1343 ++__first1, (void)++__first2)
1345 if (__comp(__first1, __first2))
1347 if (__comp(__first2, __first1))
1350 return __first1 == __last1 && __first2 != __last2;
1353 template<
bool _BoolType>
1354 struct __lexicographical_compare
1356 template<
typename _II1,
typename _II2>
1357 _GLIBCXX20_CONSTEXPR
1359 __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1361 using __gnu_cxx::__ops::__iter_less_iter;
1362 return std::__lexicographical_compare_impl(__first1, __last1,
1364 __iter_less_iter());
1367 template<
typename _II1,
typename _II2>
1368 _GLIBCXX20_CONSTEXPR
1370 __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1372 while (__first1 != __last1)
1374 if (__first2 == __last2)
1376 if (*__first1 < *__first2)
1378 if (*__first2 < *__first1)
1383 return int(__first2 == __last2) - 1;
1388 struct __lexicographical_compare<true>
1390 template<
typename _Tp,
typename _Up>
1391 _GLIBCXX20_CONSTEXPR
1393 __lc(
const _Tp* __first1,
const _Tp* __last1,
1394 const _Up* __first2,
const _Up* __last2)
1395 {
return __3way(__first1, __last1, __first2, __last2) < 0; }
1397 template<
typename _Tp,
typename _Up>
1398 _GLIBCXX20_CONSTEXPR
1400 __3way(
const _Tp* __first1,
const _Tp* __last1,
1401 const _Up* __first2,
const _Up* __last2)
1403 const size_t __len1 = __last1 - __first1;
1404 const size_t __len2 = __last2 - __first2;
1405 if (
const size_t __len =
std::min(__len1, __len2))
1406 if (
int __result = std::__memcmp(__first1, __first2, __len))
1408 return ptrdiff_t(__len1 - __len2);
1412 template<
typename _II1,
typename _II2>
1413 _GLIBCXX20_CONSTEXPR
1415 __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
1416 _II2 __first2, _II2 __last2)
1418 typedef typename iterator_traits<_II1>::value_type _ValueType1;
1419 typedef typename iterator_traits<_II2>::value_type _ValueType2;
1420#if _GLIBCXX_USE_BUILTIN_TRAIT(__is_pointer)
1421 const bool __simple =
1422 (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
1423 && __is_pointer(_II1) && __is_pointer(_II2)
1424#if __cplusplus > 201703L && __glibcxx_concepts
1428 && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>>
1429 && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>>
1433 const bool __simple =
false;
1436 return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
1440 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1443 __lexicographical_compare_aux1(
1444 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1445 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1448 template<
typename _Tp1,
1449 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1451 __lexicographical_compare_aux1(_Tp1*, _Tp1*,
1452 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1453 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1455 template<
typename _Tp1,
typename _Ref1,
typename _Ptr1,
1456 typename _Tp2,
typename _Ref2,
typename _Ptr2>
1458 __lexicographical_compare_aux1(
1459 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1460 _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
1461 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
1462 _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
1464 template<
typename _II1,
typename _II2>
1465 _GLIBCXX20_CONSTEXPR
1467 __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
1468 _II2 __first2, _II2 __last2)
1470 return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
1471 std::__niter_base(__last1),
1472 std::__niter_base(__first2),
1473 std::__niter_base(__last2));
1476 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
1478 _GLIBCXX20_CONSTEXPR
1480 __lexicographical_compare_aux(
1481 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1482 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1485 template<
typename _II1,
1486 typename _Iter2,
typename _Seq2,
typename _Cat2>
1487 _GLIBCXX20_CONSTEXPR
1489 __lexicographical_compare_aux(
1491 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1492 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1494 template<
typename _Iter1,
typename _Seq1,
typename _Cat1,
1495 typename _Iter2,
typename _Seq2,
typename _Cat2>
1496 _GLIBCXX20_CONSTEXPR
1498 __lexicographical_compare_aux(
1499 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1500 const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
1501 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
1502 const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
1504 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
1505 _GLIBCXX20_CONSTEXPR
1507 __lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1508 const _Tp& __val, _Compare __comp)
1510 typedef typename iterator_traits<_ForwardIterator>::difference_type
1517 _DistanceType __half = __len >> 1;
1518 _ForwardIterator __middle = __first;
1520 if (__comp(__middle, __val))
1524 __len = __len - __half - 1;
1543 template<
typename _ForwardIterator,
typename _Tp>
1544 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1545 inline _ForwardIterator
1546 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
1550 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1551 __glibcxx_function_requires(_LessThanOpConcept<
1553 __glibcxx_requires_partitioned_lower(__first, __last, __val);
1555 return std::__lower_bound(__first, __last, __val,
1556 __gnu_cxx::__ops::__iter_less_val());
1561 template<
typename _Tp>
1562 inline _GLIBCXX_CONSTEXPR _Tp
1565#if __cplusplus >= 201402L
1568#pragma GCC diagnostic push
1569#pragma GCC diagnostic ignored "-Wlong-long"
1571 return (
sizeof(+__n) * __CHAR_BIT__ - 1)
1572 - (
sizeof(+__n) ==
sizeof(
long long)
1573 ? __builtin_clzll(+__n)
1574 : (
sizeof(+__n) ==
sizeof(
long)
1575 ? __builtin_clzl(+__n)
1576 : __builtin_clz(+__n)));
1577#pragma GCC diagnostic pop
1581_GLIBCXX_BEGIN_NAMESPACE_ALGO
1595 template<
typename _II1,
typename _II2>
1596 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1598 equal(_II1 __first1, _II1 __last1, _II2 __first2)
1601 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1602 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1603 __glibcxx_function_requires(_EqualOpConcept<
1606 __glibcxx_requires_can_increment_range(__first1, __last1, __first2);
1608 return std::__equal_aux(__first1, __last1, __first2);
1626 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1627 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1629 equal(_IIter1 __first1, _IIter1 __last1,
1630 _IIter2 __first2, _BinaryPredicate __binary_pred)
1633 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1634 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1635 __glibcxx_requires_valid_range(__first1, __last1);
1637 for (; __first1 != __last1; ++__first1, (void)++__first2)
1638 if (!
bool(__binary_pred(*__first1, *__first2)))
1643#if __cplusplus >= 201103L
1644#pragma GCC diagnostic push
1645#pragma GCC diagnostic ignored "-Wc++17-extensions"
1648 template<
typename _II1,
typename _II2>
1649 _GLIBCXX20_CONSTEXPR
1651 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1653 using _RATag = random_access_iterator_tag;
1654 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1655 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1656 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1657 if constexpr (_RAIters::value)
1659 if ((__last1 - __first1) != (__last2 - __first2))
1661 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2);
1665 for (; __first1 != __last1 && __first2 != __last2;
1666 ++__first1, (void)++__first2)
1667 if (!(*__first1 == *__first2))
1669 return __first1 == __last1 && __first2 == __last2;
1674 template<
typename _II1,
typename _II2,
typename _BinaryPredicate>
1675 _GLIBCXX20_CONSTEXPR
1677 __equal4(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2,
1678 _BinaryPredicate __binary_pred)
1680 using _RATag = random_access_iterator_tag;
1681 using _Cat1 =
typename iterator_traits<_II1>::iterator_category;
1682 using _Cat2 =
typename iterator_traits<_II2>::iterator_category;
1683 using _RAIters = __and_<is_same<_Cat1, _RATag>, is_same<_Cat2, _RATag>>;
1684 if constexpr (_RAIters::value)
1686 if ((__last1 - __first1) != (__last2 - __first2))
1688 return _GLIBCXX_STD_A::equal(__first1, __last1, __first2,
1693 for (; __first1 != __last1 && __first2 != __last2;
1694 ++__first1, (void)++__first2)
1695 if (!
bool(__binary_pred(*__first1, *__first2)))
1697 return __first1 == __last1 && __first2 == __last2;
1700#pragma GCC diagnostic pop
1703#ifdef __glibcxx_robust_nonmodifying_seq_ops
1717 template<
typename _II1,
typename _II2>
1718 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1720 equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
1723 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1724 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1725 __glibcxx_function_requires(_EqualOpConcept<
1728 __glibcxx_requires_valid_range(__first1, __last1);
1729 __glibcxx_requires_valid_range(__first2, __last2);
1731 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2);
1750 template<
typename _IIter1,
typename _IIter2,
typename _BinaryPredicate>
1751 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1753 equal(_IIter1 __first1, _IIter1 __last1,
1754 _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
1757 __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
1758 __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
1759 __glibcxx_requires_valid_range(__first1, __last1);
1760 __glibcxx_requires_valid_range(__first2, __last2);
1762 return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2,
1782 template<
typename _II1,
typename _II2>
1783 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1785 lexicographical_compare(_II1 __first1, _II1 __last1,
1786 _II2 __first2, _II2 __last2)
1788#ifdef _GLIBCXX_CONCEPT_CHECKS
1793 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1794 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1795 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
1796 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
1797 __glibcxx_requires_valid_range(__first1, __last1);
1798 __glibcxx_requires_valid_range(__first2, __last2);
1800 return std::__lexicographical_compare_aux(__first1, __last1,
1817 template<
typename _II1,
typename _II2,
typename _Compare>
1818 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1820 lexicographical_compare(_II1 __first1, _II1 __last1,
1821 _II2 __first2, _II2 __last2, _Compare __comp)
1824 __glibcxx_function_requires(_InputIteratorConcept<_II1>)
1825 __glibcxx_function_requires(_InputIteratorConcept<_II2>)
1826 __glibcxx_requires_valid_range(__first1, __last1);
1827 __glibcxx_requires_valid_range(__first2, __last2);
1829 return std::__lexicographical_compare_impl
1830 (__first1, __last1, __first2, __last2,
1831 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1834#if __cpp_lib_three_way_comparison
1838 template<
typename _Iter1,
typename _Iter2>
1839 concept __memcmp_ordered_with
1840 = (__is_memcmp_ordered_with<iter_value_t<_Iter1>,
1841 iter_value_t<_Iter2>>::__value)
1842 && contiguous_iterator<_Iter1> && contiguous_iterator<_Iter2>;
1846 template<
typename _Tp>
1848 __min_cmp(_Tp __x, _Tp __y)
1852 decltype(__x <=> __y) _M_cmp;
1854 auto __c = __x <=> __y;
1856 return _Res{__y, __c};
1857 return _Res{__x, __c};
1871 template<
typename _InputIter1,
typename _InputIter2,
typename _Comp>
1872 [[nodiscard]]
constexpr auto
1874 _InputIter1 __last1,
1875 _InputIter2 __first2,
1876 _InputIter2 __last2,
1878 ->
decltype(__comp(*__first1, *__first2))
1881 __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
1882 __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
1883 __glibcxx_requires_valid_range(__first1, __last1);
1884 __glibcxx_requires_valid_range(__first2, __last2);
1886 using _Cat =
decltype(__comp(*__first1, *__first2));
1887 static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
1889 if (!std::__is_constant_evaluated())
1890 if constexpr (same_as<_Comp, __detail::_Synth3way>
1891 || same_as<_Comp, compare_three_way>)
1892 if constexpr (__memcmp_ordered_with<_InputIter1, _InputIter2>)
1894 const auto [__len, __lencmp] = _GLIBCXX_STD_A::
1895 __min_cmp(__last1 - __first1, __last2 - __first2);
1898 const auto __blen = __len *
sizeof(*__first1);
1900 = __builtin_memcmp(&*__first1, &*__first2, __blen) <=> 0;
1907 while (__first1 != __last1)
1909 if (__first2 == __last2)
1910 return strong_ordering::greater;
1911 if (
auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
1916 return (__first2 == __last2) <=>
true;
1919 template<
typename _InputIter1,
typename _InputIter2>
1922 _InputIter1 __last1,
1923 _InputIter2 __first2,
1924 _InputIter2 __last2)
1926 return _GLIBCXX_STD_A::
1927 lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
1928 compare_three_way{});
1932 template<
typename _InputIterator1,
typename _InputIterator2,
1933 typename _BinaryPredicate>
1934 _GLIBCXX20_CONSTEXPR
1935 pair<_InputIterator1, _InputIterator2>
1936 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1937 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
1939 while (__first1 != __last1 && __binary_pred(__first1, __first2))
1944 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
1960 template<
typename _InputIterator1,
typename _InputIterator2>
1961 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1962 inline pair<_InputIterator1, _InputIterator2>
1963 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1964 _InputIterator2 __first2)
1967 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
1968 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
1969 __glibcxx_function_requires(_EqualOpConcept<
1972 __glibcxx_requires_valid_range(__first1, __last1);
1974 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
1975 __gnu_cxx::__ops::__iter_equal_to_iter());
1994 template<
typename _InputIterator1,
typename _InputIterator2,
1995 typename _BinaryPredicate>
1996 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1997 inline pair<_InputIterator1, _InputIterator2>
1998 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
1999 _InputIterator2 __first2, _BinaryPredicate __binary_pred)
2002 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2003 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2004 __glibcxx_requires_valid_range(__first1, __last1);
2006 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
2007 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
2010#if __glibcxx_robust_nonmodifying_seq_ops
2011 template<
typename _InputIterator1,
typename _InputIterator2,
2012 typename _BinaryPredicate>
2013 _GLIBCXX20_CONSTEXPR
2014 pair<_InputIterator1, _InputIterator2>
2015 __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2016 _InputIterator2 __first2, _InputIterator2 __last2,
2017 _BinaryPredicate __binary_pred)
2019 while (__first1 != __last1 && __first2 != __last2
2020 && __binary_pred(__first1, __first2))
2025 return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
2042 template<
typename _InputIterator1,
typename _InputIterator2>
2043 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2044 inline pair<_InputIterator1, _InputIterator2>
2045 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2046 _InputIterator2 __first2, _InputIterator2 __last2)
2049 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2050 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2051 __glibcxx_function_requires(_EqualOpConcept<
2054 __glibcxx_requires_valid_range(__first1, __last1);
2055 __glibcxx_requires_valid_range(__first2, __last2);
2057 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2058 __gnu_cxx::__ops::__iter_equal_to_iter());
2078 template<
typename _InputIterator1,
typename _InputIterator2,
2079 typename _BinaryPredicate>
2080 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
2081 inline pair<_InputIterator1, _InputIterator2>
2082 mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
2083 _InputIterator2 __first2, _InputIterator2 __last2,
2084 _BinaryPredicate __binary_pred)
2087 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2088 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2089 __glibcxx_requires_valid_range(__first1, __last1);
2090 __glibcxx_requires_valid_range(__first2, __last2);
2092 return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
2093 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
2097_GLIBCXX_END_NAMESPACE_ALGO
2100 template<
typename _Iterator,
typename _Predicate>
2101 _GLIBCXX20_CONSTEXPR
2103 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
2106 while (__first != __last && !__pred(__first))
2111 template<
typename _InputIterator,
typename _Predicate>
2112 _GLIBCXX20_CONSTEXPR
2113 typename iterator_traits<_InputIterator>::difference_type
2114 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
2116 typename iterator_traits<_InputIterator>::difference_type __n = 0;
2117 for (; __first != __last; ++__first)
2118 if (__pred(__first))
2123 template<
typename _ForwardIterator,
typename _Predicate>
2124 _GLIBCXX20_CONSTEXPR
2126 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
2129 __first = std::__find_if(__first, __last, __pred);
2130 if (__first == __last)
2132 _ForwardIterator __result = __first;
2134 for (; __first != __last; ++__first)
2135 if (!__pred(__first))
2137 *__result = _GLIBCXX_MOVE(*__first);
2143 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2144 typename _BinaryPredicate>
2145 _GLIBCXX20_CONSTEXPR
2147 __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2148 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2149 _BinaryPredicate __predicate)
2152 if (__first1 == __last1 || __first2 == __last2)
2156 _ForwardIterator2 __p1(__first2);
2157 if (++__p1 == __last2)
2158 return std::__find_if(__first1, __last1,
2159 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2162 _ForwardIterator1 __current = __first1;
2167 std::__find_if(__first1, __last1,
2168 __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
2170 if (__first1 == __last1)
2173 _ForwardIterator2 __p = __p1;
2174 __current = __first1;
2175 if (++__current == __last1)
2178 while (__predicate(__current, __p))
2180 if (++__p == __last2)
2182 if (++__current == __last1)
2190#if __cplusplus >= 201103L
2191 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2192 typename _BinaryPredicate>
2193 _GLIBCXX20_CONSTEXPR
2195 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2196 _ForwardIterator2 __first2, _BinaryPredicate __pred)
2200 for (; __first1 != __last1; ++__first1, (void)++__first2)
2201 if (!__pred(__first1, __first2))
2204 if (__first1 == __last1)
2209 _ForwardIterator2 __last2 = __first2;
2211 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
2213 if (__scan != std::__find_if(__first1, __scan,
2214 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
2218 = std::__count_if(__first2, __last2,
2219 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
2220 if (0 == __matches ||
2221 std::__count_if(__scan, __last1,
2222 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
2241 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
2242 _GLIBCXX20_CONSTEXPR
2244 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2245 _ForwardIterator2 __first2)
2248 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2249 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2250 __glibcxx_function_requires(_EqualOpConcept<
2253 __glibcxx_requires_valid_range(__first1, __last1);
2255 return std::__is_permutation(__first1, __last1, __first2,
2256 __gnu_cxx::__ops::__iter_equal_to_iter());
2260_GLIBCXX_BEGIN_NAMESPACE_ALGO
2283 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
2284 typename _BinaryPredicate>
2285 _GLIBCXX20_CONSTEXPR
2286 inline _ForwardIterator1
2287 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
2288 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
2289 _BinaryPredicate __predicate)
2292 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
2293 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
2294 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
2297 __glibcxx_requires_valid_range(__first1, __last1);
2298 __glibcxx_requires_valid_range(__first2, __last2);
2300 return std::__search(__first1, __last1, __first2, __last2,
2301 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
2304_GLIBCXX_END_NAMESPACE_ALGO
2305_GLIBCXX_END_NAMESPACE_VERSION
2311#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.
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.