// Core algorithmic facilities -*- C++ -*-
-// Copyright (C) 2001-2020 Free Software Foundation, Inc.
+// Copyright (C) 2001-2024 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
#if __cplusplus >= 201103L
# include <type_traits>
#endif
-#if __cplusplus > 201703L
+#if __cplusplus >= 201402L
+# include <bit> // std::__bit_width
+#endif
+#if __cplusplus >= 202002L
# include <compare>
#endif
* A constexpr wrapper for __builtin_memcmp.
* @param __num The number of elements of type _Tp (not bytes).
*/
- template<typename _Tp>
+ template<typename _Tp, typename _Up>
_GLIBCXX14_CONSTEXPR
inline int
- __memcmp(const _Tp* __first1, const _Tp* __first2, size_t __num)
+ __memcmp(const _Tp* __first1, const _Up* __first2, size_t __num)
{
+#if __cplusplus >= 201103L
+ static_assert(sizeof(_Tp) == sizeof(_Up), "can be compared with memcmp");
+#endif
#ifdef __cpp_lib_is_constant_evaluated
if (std::is_constant_evaluated())
{
_GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
{ return __it; }
+ template<typename _Ite, typename _Seq>
+ _GLIBCXX20_CONSTEXPR
+ _Ite
+ __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
+ std::random_access_iterator_tag>&);
+
// Reverse the __niter_base transformation to get a
// __normal_iterator back again (this assumes that __normal_iterator
// is only used to wrap random access iterators, like pointers).
}
return __result;
}
+
+ template<typename _Tp, typename _Up>
+ static void
+ __assign_one(_Tp* __to, _Up* __from)
+ { *__to = *__from; }
};
#if __cplusplus >= 201103L
}
return __result;
}
+
+ template<typename _Tp, typename _Up>
+ static void
+ __assign_one(_Tp* __to, _Up* __from)
+ { *__to = std::move(*__from); }
};
#endif
template<bool _IsMove>
struct __copy_move<_IsMove, true, random_access_iterator_tag>
{
- template<typename _Tp>
+ template<typename _Tp, typename _Up>
_GLIBCXX20_CONSTEXPR
- static _Tp*
- __copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
+ static _Up*
+ __copy_m(_Tp* __first, _Tp* __last, _Up* __result)
{
-#if __cplusplus >= 201103L
- using __assignable = conditional<_IsMove,
- is_move_assignable<_Tp>,
- is_copy_assignable<_Tp>>;
- // trivial types can have deleted assignment
- static_assert( __assignable::type::value, "type is not assignable" );
-#endif
const ptrdiff_t _Num = __last - __first;
- if (_Num)
+ if (__builtin_expect(_Num > 1, true))
__builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
+ else if (_Num == 1)
+ std::__copy_move<_IsMove, false, random_access_iterator_tag>::
+ __assign_one(__result, __first);
return __result + _Num;
}
};
+_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
+
+ template<typename _Tp, typename _Ref, typename _Ptr>
+ struct _Deque_iterator;
+
+ struct _Bit_iterator;
+
+_GLIBCXX_END_NAMESPACE_CONTAINER
+
+#if _GLIBCXX_HOSTED
// Helpers for streambuf iterators (either istream or ostream).
// NB: avoid including <iosfwd>, relatively large.
template<typename _CharT>
__copy_move_a2(istreambuf_iterator<_CharT, char_traits<_CharT> >,
istreambuf_iterator<_CharT, char_traits<_CharT> >, _CharT*);
+ template<bool _IsMove, typename _CharT>
+ typename __gnu_cxx::__enable_if<
+ __is_char<_CharT>::__value,
+ _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
+ __copy_move_a2(
+ istreambuf_iterator<_CharT, char_traits<_CharT> >,
+ istreambuf_iterator<_CharT, char_traits<_CharT> >,
+ _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>);
+#endif // HOSTED
+
template<bool _IsMove, typename _II, typename _OI>
_GLIBCXX20_CONSTEXPR
inline _OI
return std::__copy_move<_IsMove, false, _Category>::
__copy_m(__first, __last, __result);
#endif
- typedef typename iterator_traits<_II>::value_type _ValueTypeI;
- typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
- const bool __simple = (__is_trivially_copyable(_ValueTypeI)
- && __is_pointer<_II>::__value
- && __is_pointer<_OI>::__value
- && __are_same<_ValueTypeI, _ValueTypeO>::__value);
- return std::__copy_move<_IsMove, __simple,
+ return std::__copy_move<_IsMove, __memcpyable<_OI, _II>::__value,
_Category>::__copy_m(__first, __last, __result);
}
-_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
-
- template<typename _Tp, typename _Ref, typename _Ptr>
- struct _Deque_iterator;
-
-_GLIBCXX_END_NAMESPACE_CONTAINER
-
template<bool _IsMove,
typename _Tp, typename _Ref, typename _Ptr, typename _OI>
_OI
template<bool _IsMove,
typename _Ite, typename _Seq, typename _Cat, typename _OI>
+ _GLIBCXX20_CONSTEXPR
_OI
__copy_move_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
template<bool _IsMove,
typename _II, typename _Ite, typename _Seq, typename _Cat>
+ _GLIBCXX20_CONSTEXPR
__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
__copy_move_a(_II, _II,
const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
template<bool _IsMove,
typename _IIte, typename _ISeq, typename _ICat,
typename _OIte, typename _OSeq, typename _OCat>
+ _GLIBCXX20_CONSTEXPR
::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
__copy_move_a(const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>&);
+ template<typename _InputIterator, typename _Size, typename _OutputIterator>
+ _GLIBCXX20_CONSTEXPR
+ _OutputIterator
+ __copy_n_a(_InputIterator __first, _Size __n, _OutputIterator __result,
+ bool)
+ {
+ if (__n > 0)
+ {
+ while (true)
+ {
+ *__result = *__first;
+ ++__result;
+ if (--__n > 0)
+ ++__first;
+ else
+ break;
+ }
+ }
+ return __result;
+ }
+
+#if _GLIBCXX_HOSTED
+ template<typename _CharT, typename _Size>
+ typename __gnu_cxx::__enable_if<
+ __is_char<_CharT>::__value, _CharT*>::__type
+ __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >,
+ _Size, _CharT*, bool);
+
+ template<typename _CharT, typename _Size>
+ typename __gnu_cxx::__enable_if<
+ __is_char<_CharT>::__value,
+ _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
+ __copy_n_a(istreambuf_iterator<_CharT, char_traits<_CharT> >, _Size,
+ _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*>,
+ bool);
+#endif
+
/**
* @brief Copies the range [first,last) into result.
* @ingroup mutating_algorithms
* @param __first An input iterator.
* @param __last An input iterator.
* @param __result An output iterator.
- * @return result + (first - last)
+ * @return result + (last - first)
*
* This inline function will boil down to a call to @c memmove whenever
* possible. Failing that, if random access iterators are passed, then the
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_II>)
__glibcxx_function_requires(_OutputIteratorConcept<_OI,
- typename iterator_traits<_II>::value_type>)
+ typename iterator_traits<_II>::reference>)
__glibcxx_requires_can_increment_range(__first, __last, __result);
return std::__copy_move_a<__is_move_iterator<_II>::__value>
* @param __first An input iterator.
* @param __last An input iterator.
* @param __result An output iterator.
- * @return result + (first - last)
+ * @return result + (last - first)
*
* This inline function will boil down to a call to @c memmove whenever
* possible. Failing that, if random access iterators are passed, then the
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_II>)
__glibcxx_function_requires(_OutputIteratorConcept<_OI,
- typename iterator_traits<_II>::value_type>)
+ typename iterator_traits<_II>::value_type&&>)
__glibcxx_requires_can_increment_range(__first, __last, __result);
return std::__copy_move_a<true>(std::__miter_base(__first),
template<bool _IsMove>
struct __copy_move_backward<_IsMove, true, random_access_iterator_tag>
{
- template<typename _Tp>
+ template<typename _Tp, typename _Up>
_GLIBCXX20_CONSTEXPR
- static _Tp*
- __copy_move_b(const _Tp* __first, const _Tp* __last, _Tp* __result)
+ static _Up*
+ __copy_move_b(_Tp* __first, _Tp* __last, _Up* __result)
{
-#if __cplusplus >= 201103L
- using __assignable = conditional<_IsMove,
- is_move_assignable<_Tp>,
- is_copy_assignable<_Tp>>;
- // trivial types can have deleted assignment
- static_assert( __assignable::type::value, "type is not assignable" );
-#endif
const ptrdiff_t _Num = __last - __first;
- if (_Num)
+ if (__builtin_expect(_Num > 1, true))
__builtin_memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
+ else if (_Num == 1)
+ std::__copy_move<_IsMove, false, random_access_iterator_tag>::
+ __assign_one(__result - 1, __first);
return __result - _Num;
}
};
return std::__copy_move_backward<_IsMove, false, _Category>::
__copy_move_b(__first, __last, __result);
#endif
- typedef typename iterator_traits<_BI1>::value_type _ValueType1;
- typedef typename iterator_traits<_BI2>::value_type _ValueType2;
- const bool __simple = (__is_trivially_copyable(_ValueType1)
- && __is_pointer<_BI1>::__value
- && __is_pointer<_BI2>::__value
- && __are_same<_ValueType1, _ValueType2>::__value);
-
- return std::__copy_move_backward<_IsMove, __simple,
+ return std::__copy_move_backward<_IsMove,
+ __memcpyable<_BI2, _BI1>::__value,
_Category>::__copy_move_b(__first,
__last,
__result);
template<bool _IsMove,
typename _Ite, typename _Seq, typename _Cat, typename _OI>
+ _GLIBCXX20_CONSTEXPR
_OI
__copy_move_backward_a(
const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
template<bool _IsMove,
typename _II, typename _Ite, typename _Seq, typename _Cat>
+ _GLIBCXX20_CONSTEXPR
__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
__copy_move_backward_a(_II, _II,
const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&);
template<bool _IsMove,
typename _IIte, typename _ISeq, typename _ICat,
typename _OIte, typename _OSeq, typename _OCat>
+ _GLIBCXX20_CONSTEXPR
::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>
__copy_move_backward_a(
const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>&,
* @param __first A bidirectional iterator.
* @param __last A bidirectional iterator.
* @param __result A bidirectional iterator.
- * @return result - (first - last)
+ * @return result - (last - first)
*
* The function has the same effect as copy, but starts at the end of the
* range and works its way to the start, returning the start of the result.
// concept requirements
__glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
- __glibcxx_function_requires(_ConvertibleConcept<
- typename iterator_traits<_BI1>::value_type,
- typename iterator_traits<_BI2>::value_type>)
+ __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
+ typename iterator_traits<_BI1>::reference>)
__glibcxx_requires_can_decrement_range(__first, __last, __result);
return std::__copy_move_backward_a<__is_move_iterator<_BI1>::__value>
* @param __first A bidirectional iterator.
* @param __last A bidirectional iterator.
* @param __result A bidirectional iterator.
- * @return result - (first - last)
+ * @return result - (last - first)
*
* The function has the same effect as move, but starts at the end of the
* range and works its way to the start, returning the start of the result.
// concept requirements
__glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
__glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
- __glibcxx_function_requires(_ConvertibleConcept<
- typename iterator_traits<_BI1>::value_type,
- typename iterator_traits<_BI2>::value_type>)
+ __glibcxx_function_requires(_OutputIteratorConcept<_BI2,
+ typename iterator_traits<_BI1>::value_type&&>)
__glibcxx_requires_can_decrement_range(__first, __last, __result);
return std::__copy_move_backward_a<true>(std::__miter_base(__first),
// Specialization: for char types we can use memset.
template<typename _Tp>
+ _GLIBCXX20_CONSTEXPR
inline typename
__gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
__fill_a1(_Tp* __first, _Tp* __last, const _Tp& __c)
{
const _Tp __tmp = __c;
+#if __cpp_lib_is_constant_evaluated
+ if (std::is_constant_evaluated())
+ {
+ for (; __first != __last; ++__first)
+ *__first = __tmp;
+ return;
+ }
+#endif
if (const size_t __len = __last - __first)
__builtin_memset(__first, static_cast<unsigned char>(__tmp), __len);
}
const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>&,
const _VTp&);
+ _GLIBCXX20_CONSTEXPR
+ void
+ __fill_a1(_GLIBCXX_STD_C::_Bit_iterator, _GLIBCXX_STD_C::_Bit_iterator,
+ const bool&);
+
template<typename _FIte, typename _Tp>
_GLIBCXX20_CONSTEXPR
inline void
{ std::__fill_a1(__first, __last, __value); }
template<typename _Ite, typename _Seq, typename _Cat, typename _Tp>
+ _GLIBCXX20_CONSTEXPR
void
__fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>&,
__size_to_integer(unsigned long long __n) { return __n; }
#if defined(__GLIBCXX_TYPE_INT_N_0)
- inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
+ __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_0
__size_to_integer(__GLIBCXX_TYPE_INT_N_0 __n) { return __n; }
- inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_0
+ __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_0
__size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_0 __n) { return __n; }
#endif
#if defined(__GLIBCXX_TYPE_INT_N_1)
- inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
+ __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_1
__size_to_integer(__GLIBCXX_TYPE_INT_N_1 __n) { return __n; }
- inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_1
+ __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_1
__size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_1 __n) { return __n; }
#endif
#if defined(__GLIBCXX_TYPE_INT_N_2)
- inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
+ __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_2
__size_to_integer(__GLIBCXX_TYPE_INT_N_2 __n) { return __n; }
- inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_2
+ __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_2
__size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_2 __n) { return __n; }
#endif
#if defined(__GLIBCXX_TYPE_INT_N_3)
- inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_3
+ __extension__ inline _GLIBCXX_CONSTEXPR unsigned __GLIBCXX_TYPE_INT_N_3
__size_to_integer(__GLIBCXX_TYPE_INT_N_3 __n) { return __n; }
- inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
+ __extension__ inline _GLIBCXX_CONSTEXPR __GLIBCXX_TYPE_INT_N_3
__size_to_integer(unsigned __GLIBCXX_TYPE_INT_N_3 __n) { return __n; }
#endif
inline _GLIBCXX_CONSTEXPR long long
- __size_to_integer(float __n) { return __n; }
+ __size_to_integer(float __n) { return (long long)__n; }
inline _GLIBCXX_CONSTEXPR long long
- __size_to_integer(double __n) { return __n; }
+ __size_to_integer(double __n) { return (long long)__n; }
inline _GLIBCXX_CONSTEXPR long long
- __size_to_integer(long double __n) { return __n; }
+ __size_to_integer(long double __n) { return (long long)__n; }
#if !defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_FLOAT128)
- inline _GLIBCXX_CONSTEXPR long long
- __size_to_integer(__float128 __n) { return __n; }
+ __extension__ inline _GLIBCXX_CONSTEXPR long long
+ __size_to_integer(__float128 __n) { return (long long)__n; }
#endif
template<typename _OutputIterator, typename _Size, typename _Tp>
template<typename _Ite, typename _Seq, typename _Cat, typename _Size,
typename _Tp>
+ _GLIBCXX20_CONSTEXPR
::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>
__fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first,
_Size __n, const _Tp& __value,
fill_n(_OI __first, _Size __n, const _Tp& __value)
{
// concept requirements
- __glibcxx_function_requires(_OutputIteratorConcept<_OI, _Tp>)
+ __glibcxx_function_requires(_OutputIteratorConcept<_OI, const _Tp&>)
return std::__fill_n_a(__first, std::__size_to_integer(__n), __value,
std::__iterator_category(__first));
__equal_aux1(_II1 __first1, _II1 __last1, _II2 __first2)
{
typedef typename iterator_traits<_II1>::value_type _ValueType1;
- typedef typename iterator_traits<_II2>::value_type _ValueType2;
const bool __simple = ((__is_integer<_ValueType1>::__value
|| __is_pointer<_ValueType1>::__value)
- && __is_pointer<_II1>::__value
- && __is_pointer<_II2>::__value
- && __are_same<_ValueType1, _ValueType2>::__value);
-
+ && __memcmpable<_II1, _II2>::__value);
return std::__equal<__simple>::equal(__first1, __last1, __first2);
}
}
template<typename _II1, typename _Seq1, typename _Cat1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
bool
__equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
_II2);
template<typename _II1, typename _II2, typename _Seq2, typename _Cat2>
+ _GLIBCXX20_CONSTEXPR
bool
__equal_aux(_II1, _II1,
const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>&);
template<typename _II1, typename _Seq1, typename _Cat1,
typename _II2, typename _Seq2, typename _Cat2>
+ _GLIBCXX20_CONSTEXPR
bool
__equal_aux(const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>&,
__first2, __last2,
__iter_less_iter());
}
+
+ template<typename _II1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ static int
+ __3way(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
+ {
+ while (__first1 != __last1)
+ {
+ if (__first2 == __last2)
+ return +1;
+ if (*__first1 < *__first2)
+ return -1;
+ if (*__first2 < *__first1)
+ return +1;
+ ++__first1;
+ ++__first2;
+ }
+ return int(__first2 == __last2) - 1;
+ }
};
template<>
static bool
__lc(const _Tp* __first1, const _Tp* __last1,
const _Up* __first2, const _Up* __last2)
+ { return __3way(__first1, __last1, __first2, __last2) < 0; }
+
+ template<typename _Tp, typename _Up>
+ _GLIBCXX20_CONSTEXPR
+ static ptrdiff_t
+ __3way(const _Tp* __first1, const _Tp* __last1,
+ const _Up* __first2, const _Up* __last2)
{
const size_t __len1 = __last1 - __first1;
const size_t __len2 = __last2 - __first2;
if (const size_t __len = std::min(__len1, __len2))
if (int __result = std::__memcmp(__first1, __first2, __len))
- return __result < 0;
- return __len1 < __len2;
+ return __result;
+ return ptrdiff_t(__len1 - __len2);
}
};
template<typename _II1, typename _II2>
_GLIBCXX20_CONSTEXPR
inline bool
- __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
- _II2 __first2, _II2 __last2)
+ __lexicographical_compare_aux1(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
{
typedef typename iterator_traits<_II1>::value_type _ValueType1;
typedef typename iterator_traits<_II2>::value_type _ValueType2;
const bool __simple =
- (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value
- && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
- && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
+ (__is_memcmp_ordered_with<_ValueType1, _ValueType2>::__value
&& __is_pointer<_II1>::__value
- && __is_pointer<_II2>::__value);
+ && __is_pointer<_II2>::__value
+#if __cplusplus > 201703L && __glibcxx_concepts
+ // For C++20 iterator_traits<volatile T*>::value_type is non-volatile
+ // so __is_byte<T> could be true, but we can't use memcmp with
+ // volatile data.
+ && !is_volatile_v<remove_reference_t<iter_reference_t<_II1>>>
+ && !is_volatile_v<remove_reference_t<iter_reference_t<_II2>>>
+#endif
+ );
return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
__first2, __last2);
}
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2>
+ bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _Tp2*, _Tp2*);
+
+ template<typename _Tp1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ bool
+ __lexicographical_compare_aux1(_Tp1*, _Tp1*,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+ template<typename _Tp1, typename _Ref1, typename _Ptr1,
+ typename _Tp2, typename _Ref2, typename _Ptr2>
+ bool
+ __lexicographical_compare_aux1(
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>,
+ _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2>);
+
+ template<typename _II1, typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ inline bool
+ __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
+ _II2 __first2, _II2 __last2)
+ {
+ return std::__lexicographical_compare_aux1(std::__niter_base(__first1),
+ std::__niter_base(__last1),
+ std::__niter_base(__first2),
+ std::__niter_base(__last2));
+ }
+
+ template<typename _Iter1, typename _Seq1, typename _Cat1,
+ typename _II2>
+ _GLIBCXX20_CONSTEXPR
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ _II2, _II2);
+
+ template<typename _II1,
+ typename _Iter2, typename _Seq2, typename _Cat2>
+ _GLIBCXX20_CONSTEXPR
+ bool
+ __lexicographical_compare_aux(
+ _II1, _II1,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
+
+ template<typename _Iter1, typename _Seq1, typename _Cat1,
+ typename _Iter2, typename _Seq2, typename _Cat2>
+ _GLIBCXX20_CONSTEXPR
+ bool
+ __lexicographical_compare_aux(
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter1, _Seq1, _Cat1>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&,
+ const ::__gnu_debug::_Safe_iterator<_Iter2, _Seq2, _Cat2>&);
+
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
/// This is a helper function for the sort routines and for random.tcc.
// Precondition: __n > 0.
- inline _GLIBCXX_CONSTEXPR int
- __lg(int __n)
- { return (int)sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
-
- inline _GLIBCXX_CONSTEXPR unsigned
- __lg(unsigned __n)
- { return (int)sizeof(int) * __CHAR_BIT__ - 1 - __builtin_clz(__n); }
-
- inline _GLIBCXX_CONSTEXPR long
- __lg(long __n)
- { return (int)sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
-
- inline _GLIBCXX_CONSTEXPR unsigned long
- __lg(unsigned long __n)
- { return (int)sizeof(long) * __CHAR_BIT__ - 1 - __builtin_clzl(__n); }
-
- inline _GLIBCXX_CONSTEXPR long long
- __lg(long long __n)
- { return (int)sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
-
- inline _GLIBCXX_CONSTEXPR unsigned long long
- __lg(unsigned long long __n)
- { return (int)sizeof(long long) * __CHAR_BIT__ - 1 - __builtin_clzll(__n); }
+ template<typename _Tp>
+ inline _GLIBCXX_CONSTEXPR _Tp
+ __lg(_Tp __n)
+ {
+#if __cplusplus >= 201402L
+ return std::__bit_width(make_unsigned_t<_Tp>(__n)) - 1;
+#else
+ // Use +__n so it promotes to at least int.
+ return (sizeof(+__n) * __CHAR_BIT__ - 1)
+ - (sizeof(+__n) == sizeof(long long)
+ ? __builtin_clzll(+__n)
+ : (sizeof(+__n) == sizeof(long)
+ ? __builtin_clzl(+__n)
+ : __builtin_clz(+__n)));
+#endif
+ }
_GLIBCXX_BEGIN_NAMESPACE_ALGO
}
#endif // C++11
-#if __cplusplus > 201103L
-
-#define __cpp_lib_robust_nonmodifying_seq_ops 201304
-
+#ifdef __glibcxx_robust_nonmodifying_seq_ops // C++ >= 14
/**
* @brief Tests a range for element-wise equality.
* @ingroup non_mutating_algorithms
return _GLIBCXX_STD_A::__equal4(__first1, __last1, __first2, __last2,
__binary_pred);
}
-#endif // C++14
+#endif // __glibcxx_robust_nonmodifying_seq_ops
/**
* @brief Performs @b dictionary comparison on ranges.
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- return std::__lexicographical_compare_aux(std::__niter_base(__first1),
- std::__niter_base(__last1),
- std::__niter_base(__first2),
- std::__niter_base(__last2));
+ return std::__lexicographical_compare_aux(__first1, __last1,
+ __first2, __last2);
}
/**
// or std::byte, suitable for comparison by memcmp.
template<typename _Iter>
concept __is_byte_iter = contiguous_iterator<_Iter>
- && __is_byte<iter_value_t<_Iter>>::__value != 0
- && !__gnu_cxx::__numeric_traits<iter_value_t<_Iter>>::__is_signed;
+ && __is_memcmp_ordered<iter_value_t<_Iter>>::__value;
// Return a struct with two members, initialized to the smaller of x and y
// (or x if they compare equal) and the result of the comparison x <=> y.
__glibcxx_requires_valid_range(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
-#if __cpp_lib_is_constant_evaluated
using _Cat = decltype(__comp(*__first1, *__first2));
static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
- if (!std::is_constant_evaluated())
+ if (!std::__is_constant_evaluated())
if constexpr (same_as<_Comp, __detail::_Synth3way>
|| same_as<_Comp, compare_three_way>)
if constexpr (__is_byte_iter<_InputIter1>)
if constexpr (__is_byte_iter<_InputIter2>)
{
- const auto [__len, __lencmp]
- = std::__min_cmp(__last1 - __first1, __last2 - __first2);
+ const auto [__len, __lencmp] = _GLIBCXX_STD_A::
+ __min_cmp(__last1 - __first1, __last2 - __first2);
if (__len)
{
const auto __c
}
return __lencmp;
}
-#endif // is_constant_evaluated
- while (__first1 != __last1 && __first2 != __last2)
+
+ while (__first1 != __last1)
{
+ if (__first2 == __last2)
+ return strong_ordering::greater;
if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
return __cmp;
++__first1;
++__first2;
}
- return __first1 != __last1 ? strong_ordering::greater
- : __first2 != __last2 ? strong_ordering::less : strong_ordering::equal;
+ return (__first2 == __last2) <=> true; // See PR 94006
}
template<typename _InputIter1, typename _InputIter2>
_InputIter2 __first2,
_InputIter2 __last2)
{
- return std::lexicographical_compare_three_way(__first1, __last1,
- __first2, __last2,
- compare_three_way{});
+ return _GLIBCXX_STD_A::
+ lexicographical_compare_three_way(__first1, __last1, __first2, __last2,
+ compare_three_way{});
}
#endif // three_way_comparison
__gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
}
-#if __cplusplus > 201103L
-
+#if __glibcxx_robust_nonmodifying_seq_ops // C++ >= 14
template<typename _InputIterator1, typename _InputIterator2,
typename _BinaryPredicate>
_GLIBCXX20_CONSTEXPR
}
#endif
+_GLIBCXX_END_NAMESPACE_ALGO
+
+ /// This is an overload used by find algos for the Input Iterator case.
+ template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
+ inline _InputIterator
+ __find_if(_InputIterator __first, _InputIterator __last,
+ _Predicate __pred, input_iterator_tag)
+ {
+ while (__first != __last && !__pred(__first))
+ ++__first;
+ return __first;
+ }
+
+ /// This is an overload used by find algos for the RAI case.
+ template<typename _RandomAccessIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
+ _RandomAccessIterator
+ __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
+ _Predicate __pred, random_access_iterator_tag)
+ {
+ typename iterator_traits<_RandomAccessIterator>::difference_type
+ __trip_count = (__last - __first) >> 2;
+
+ for (; __trip_count > 0; --__trip_count)
+ {
+ if (__pred(__first))
+ return __first;
+ ++__first;
+
+ if (__pred(__first))
+ return __first;
+ ++__first;
+
+ if (__pred(__first))
+ return __first;
+ ++__first;
+
+ if (__pred(__first))
+ return __first;
+ ++__first;
+ }
+
+ switch (__last - __first)
+ {
+ case 3:
+ if (__pred(__first))
+ return __first;
+ ++__first;
+ // FALLTHRU
+ case 2:
+ if (__pred(__first))
+ return __first;
+ ++__first;
+ // FALLTHRU
+ case 1:
+ if (__pred(__first))
+ return __first;
+ ++__first;
+ // FALLTHRU
+ case 0:
+ default:
+ return __last;
+ }
+ }
+
+ template<typename _Iterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
+ inline _Iterator
+ __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
+ {
+ return __find_if(__first, __last, __pred,
+ std::__iterator_category(__first));
+ }
+
+ template<typename _InputIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
+ typename iterator_traits<_InputIterator>::difference_type
+ __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
+ {
+ typename iterator_traits<_InputIterator>::difference_type __n = 0;
+ for (; __first != __last; ++__first)
+ if (__pred(__first))
+ ++__n;
+ return __n;
+ }
+
+ template<typename _ForwardIterator, typename _Predicate>
+ _GLIBCXX20_CONSTEXPR
+ _ForwardIterator
+ __remove_if(_ForwardIterator __first, _ForwardIterator __last,
+ _Predicate __pred)
+ {
+ __first = std::__find_if(__first, __last, __pred);
+ if (__first == __last)
+ return __first;
+ _ForwardIterator __result = __first;
+ ++__first;
+ for (; __first != __last; ++__first)
+ if (!__pred(__first))
+ {
+ *__result = _GLIBCXX_MOVE(*__first);
+ ++__result;
+ }
+ return __result;
+ }
+
+ template<typename _ForwardIterator1, typename _ForwardIterator2,
+ typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
+ _ForwardIterator1
+ __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2, _ForwardIterator2 __last2,
+ _BinaryPredicate __predicate)
+ {
+ // Test for empty ranges
+ if (__first1 == __last1 || __first2 == __last2)
+ return __first1;
+
+ // Test for a pattern of length 1.
+ _ForwardIterator2 __p1(__first2);
+ if (++__p1 == __last2)
+ return std::__find_if(__first1, __last1,
+ __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
+
+ // General case.
+ _ForwardIterator1 __current = __first1;
+
+ for (;;)
+ {
+ __first1 =
+ std::__find_if(__first1, __last1,
+ __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
+
+ if (__first1 == __last1)
+ return __last1;
+
+ _ForwardIterator2 __p = __p1;
+ __current = __first1;
+ if (++__current == __last1)
+ return __last1;
+
+ while (__predicate(__current, __p))
+ {
+ if (++__p == __last2)
+ return __first1;
+ if (++__current == __last1)
+ return __last1;
+ }
+ ++__first1;
+ }
+ return __first1;
+ }
+
+#if __cplusplus >= 201103L
+ template<typename _ForwardIterator1, typename _ForwardIterator2,
+ typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
+ bool
+ __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2, _BinaryPredicate __pred)
+ {
+ // Efficiently compare identical prefixes: O(N) if sequences
+ // have the same elements in the same order.
+ for (; __first1 != __last1; ++__first1, (void)++__first2)
+ if (!__pred(__first1, __first2))
+ break;
+
+ if (__first1 == __last1)
+ return true;
+
+ // Establish __last2 assuming equal ranges by iterating over the
+ // rest of the list.
+ _ForwardIterator2 __last2 = __first2;
+ std::advance(__last2, std::distance(__first1, __last1));
+ for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
+ {
+ if (__scan != std::__find_if(__first1, __scan,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
+ continue; // We've seen this one before.
+
+ auto __matches
+ = std::__count_if(__first2, __last2,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
+ if (0 == __matches ||
+ std::__count_if(__scan, __last1,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
+ != __matches)
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * @brief Checks whether a permutation of the second sequence is equal
+ * to the first sequence.
+ * @ingroup non_mutating_algorithms
+ * @param __first1 Start of first range.
+ * @param __last1 End of first range.
+ * @param __first2 Start of second range.
+ * @return true if there exists a permutation of the elements in the range
+ * [__first2, __first2 + (__last1 - __first1)), beginning with
+ * ForwardIterator2 begin, such that equal(__first1, __last1, begin)
+ * returns true; otherwise, returns false.
+ */
+ template<typename _ForwardIterator1, typename _ForwardIterator2>
+ _GLIBCXX20_CONSTEXPR
+ inline bool
+ is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
+ __glibcxx_function_requires(_EqualOpConcept<
+ typename iterator_traits<_ForwardIterator1>::value_type,
+ typename iterator_traits<_ForwardIterator2>::value_type>)
+ __glibcxx_requires_valid_range(__first1, __last1);
+
+ return std::__is_permutation(__first1, __last1, __first2,
+ __gnu_cxx::__ops::__iter_equal_to_iter());
+ }
+#endif // C++11
+
+_GLIBCXX_BEGIN_NAMESPACE_ALGO
+
+ /**
+ * @brief Search a sequence for a matching sub-sequence using a predicate.
+ * @ingroup non_mutating_algorithms
+ * @param __first1 A forward iterator.
+ * @param __last1 A forward iterator.
+ * @param __first2 A forward iterator.
+ * @param __last2 A forward iterator.
+ * @param __predicate A binary predicate.
+ * @return The first iterator @c i in the range
+ * @p [__first1,__last1-(__last2-__first2)) such that
+ * @p __predicate(*(i+N),*(__first2+N)) is true for each @c N in the range
+ * @p [0,__last2-__first2), or @p __last1 if no such iterator exists.
+ *
+ * Searches the range @p [__first1,__last1) for a sub-sequence that
+ * compares equal value-by-value with the sequence given by @p
+ * [__first2,__last2), using @p __predicate to determine equality,
+ * and returns an iterator to the first element of the
+ * sub-sequence, or @p __last1 if no such iterator exists.
+ *
+ * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2)
+ */
+ template<typename _ForwardIterator1, typename _ForwardIterator2,
+ typename _BinaryPredicate>
+ _GLIBCXX20_CONSTEXPR
+ inline _ForwardIterator1
+ search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2, _ForwardIterator2 __last2,
+ _BinaryPredicate __predicate)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
+ __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
+ __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
+ typename iterator_traits<_ForwardIterator1>::value_type,
+ typename iterator_traits<_ForwardIterator2>::value_type>)
+ __glibcxx_requires_valid_range(__first1, __last1);
+ __glibcxx_requires_valid_range(__first2, __last2);
+
+ return std::__search(__first1, __last1, __first2, __last2,
+ __gnu_cxx::__ops::__iter_comp_iter(__predicate));
+ }
+
_GLIBCXX_END_NAMESPACE_ALGO
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std