diff --git a/libcxx/include/__algorithm/binary_search.h b/libcxx/include/__algorithm/binary_search.h --- a/libcxx/include/__algorithm/binary_search.h +++ b/libcxx/include/__algorithm/binary_search.h @@ -37,8 +37,7 @@ bool binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return std::binary_search(__first, __last, __value, - __less::value_type, _Tp>()); + return std::binary_search(__first, __last, __value, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/clamp.h b/libcxx/include/__algorithm/clamp.h --- a/libcxx/include/__algorithm/clamp.h +++ b/libcxx/include/__algorithm/clamp.h @@ -37,7 +37,7 @@ const _Tp& clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi) { - return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>()); + return _VSTD::clamp(__v, __lo, __hi, __less<>()); } #endif diff --git a/libcxx/include/__algorithm/comp.h b/libcxx/include/__algorithm/comp.h --- a/libcxx/include/__algorithm/comp.h +++ b/libcxx/include/__algorithm/comp.h @@ -29,41 +29,17 @@ template struct __is_trivial_equality_predicate<__equal_to, _Lhs, _Rhs> : true_type {}; -template -struct __less -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;} - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;} - - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;} -}; - -template -struct __less<_T1, _T1> -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} -}; - -template -struct __less -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} -}; - -template -struct __less<_T1, const _T1> -{ - _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14 - bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} +// The definition is required because __less is part of the ABI, but it's empty +// because all comparitons should be transparent. +template +struct __less {}; + +template <> +struct __less { + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool operator()(const _Tp& __lhs, const _Up& __rhs) const { + return __lhs < __rhs; + } }; _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/equal_range.h b/libcxx/include/__algorithm/equal_range.h --- a/libcxx/include/__algorithm/equal_range.h +++ b/libcxx/include/__algorithm/equal_range.h @@ -75,11 +75,7 @@ template _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<_ForwardIterator, _ForwardIterator> equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return std::equal_range( - std::move(__first), - std::move(__last), - __value, - __less::value_type, _Tp>()); + return std::equal_range(std::move(__first), std::move(__last), __value, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/includes.h b/libcxx/include/__algorithm/includes.h --- a/libcxx/include/__algorithm/includes.h +++ b/libcxx/include/__algorithm/includes.h @@ -61,13 +61,7 @@ template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { - return std::includes( - std::move(__first1), - std::move(__last1), - std::move(__first2), - std::move(__last2), - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); + return std::includes(std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/inplace_merge.h b/libcxx/include/__algorithm/inplace_merge.h --- a/libcxx/include/__algorithm/inplace_merge.h +++ b/libcxx/include/__algorithm/inplace_merge.h @@ -246,8 +246,7 @@ void inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last) { - std::inplace_merge(std::move(__first), std::move(__middle), std::move(__last), - __less::value_type>()); + std::inplace_merge(std::move(__first), std::move(__middle), std::move(__last), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_heap.h b/libcxx/include/__algorithm/is_heap.h --- a/libcxx/include/__algorithm/is_heap.h +++ b/libcxx/include/__algorithm/is_heap.h @@ -36,7 +36,7 @@ bool is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { - return _VSTD::is_heap(__first, __last, __less::value_type>()); + return _VSTD::is_heap(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_heap_until.h b/libcxx/include/__algorithm/is_heap_until.h --- a/libcxx/include/__algorithm/is_heap_until.h +++ b/libcxx/include/__algorithm/is_heap_until.h @@ -58,7 +58,7 @@ _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _RandomAccessIterator is_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last) { - return _VSTD::__is_heap_until(__first, __last, __less::value_type>()); + return _VSTD::__is_heap_until(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_sorted.h b/libcxx/include/__algorithm/is_sorted.h --- a/libcxx/include/__algorithm/is_sorted.h +++ b/libcxx/include/__algorithm/is_sorted.h @@ -36,7 +36,7 @@ bool is_sorted(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::is_sorted(__first, __last, __less::value_type>()); + return _VSTD::is_sorted(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/is_sorted_until.h b/libcxx/include/__algorithm/is_sorted_until.h --- a/libcxx/include/__algorithm/is_sorted_until.h +++ b/libcxx/include/__algorithm/is_sorted_until.h @@ -48,7 +48,7 @@ _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::is_sorted_until(__first, __last, __less::value_type>()); + return _VSTD::is_sorted_until(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/lexicographical_compare.h b/libcxx/include/__algorithm/lexicographical_compare.h --- a/libcxx/include/__algorithm/lexicographical_compare.h +++ b/libcxx/include/__algorithm/lexicographical_compare.h @@ -52,9 +52,7 @@ lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) { - return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2, - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); + return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/lower_bound.h b/libcxx/include/__algorithm/lower_bound.h --- a/libcxx/include/__algorithm/lower_bound.h +++ b/libcxx/include/__algorithm/lower_bound.h @@ -58,8 +58,7 @@ template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return std::lower_bound(__first, __last, __value, - __less::value_type, _Tp>()); + return std::lower_bound(__first, __last, __value, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/make_heap.h b/libcxx/include/__algorithm/make_heap.h --- a/libcxx/include/__algorithm/make_heap.h +++ b/libcxx/include/__algorithm/make_heap.h @@ -47,8 +47,7 @@ template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::make_heap(std::move(__first), std::move(__last), - __less::value_type>()); + std::make_heap(std::move(__first), std::move(__last), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/max.h b/libcxx/include/__algorithm/max.h --- a/libcxx/include/__algorithm/max.h +++ b/libcxx/include/__algorithm/max.h @@ -39,7 +39,7 @@ const _Tp& max(_LIBCPP_LIFETIMEBOUND const _Tp& __a, _LIBCPP_LIFETIMEBOUND const _Tp& __b) { - return _VSTD::max(__a, __b, __less<_Tp>()); + return _VSTD::max(__a, __b, __less<>()); } #ifndef _LIBCPP_CXX03_LANG @@ -59,7 +59,7 @@ _Tp max(initializer_list<_Tp> __t) { - return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>()); + return *_VSTD::max_element(__t.begin(), __t.end(), __less<>()); } #endif // _LIBCPP_CXX03_LANG diff --git a/libcxx/include/__algorithm/max_element.h b/libcxx/include/__algorithm/max_element.h --- a/libcxx/include/__algorithm/max_element.h +++ b/libcxx/include/__algorithm/max_element.h @@ -48,8 +48,7 @@ _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::max_element(__first, __last, - __less::value_type>()); + return _VSTD::max_element(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/merge.h b/libcxx/include/__algorithm/merge.h --- a/libcxx/include/__algorithm/merge.h +++ b/libcxx/include/__algorithm/merge.h @@ -60,9 +60,7 @@ merge(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) { - typedef typename iterator_traits<_InputIterator1>::value_type __v1; - typedef typename iterator_traits<_InputIterator2>::value_type __v2; - return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>()); + return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/min.h b/libcxx/include/__algorithm/min.h --- a/libcxx/include/__algorithm/min.h +++ b/libcxx/include/__algorithm/min.h @@ -39,7 +39,7 @@ const _Tp& min(_LIBCPP_LIFETIMEBOUND const _Tp& __a, _LIBCPP_LIFETIMEBOUND const _Tp& __b) { - return _VSTD::min(__a, __b, __less<_Tp>()); + return _VSTD::min(__a, __b, __less<>()); } #ifndef _LIBCPP_CXX03_LANG @@ -59,7 +59,7 @@ _Tp min(initializer_list<_Tp> __t) { - return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>()); + return *_VSTD::min_element(__t.begin(), __t.end(), __less<>()); } #endif // _LIBCPP_CXX03_LANG diff --git a/libcxx/include/__algorithm/min_element.h b/libcxx/include/__algorithm/min_element.h --- a/libcxx/include/__algorithm/min_element.h +++ b/libcxx/include/__algorithm/min_element.h @@ -61,8 +61,7 @@ _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last) { - return _VSTD::min_element(__first, __last, - __less::value_type>()); + return _VSTD::min_element(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/minmax.h b/libcxx/include/__algorithm/minmax.h --- a/libcxx/include/__algorithm/minmax.h +++ b/libcxx/include/__algorithm/minmax.h @@ -39,7 +39,7 @@ pair minmax(_LIBCPP_LIFETIMEBOUND const _Tp& __a, _LIBCPP_LIFETIMEBOUND const _Tp& __b) { - return std::minmax(__a, __b, __less<_Tp>()); + return std::minmax(__a, __b, __less<>()); } #ifndef _LIBCPP_CXX03_LANG @@ -59,7 +59,7 @@ pair<_Tp, _Tp> minmax(initializer_list<_Tp> __t) { - return std::minmax(__t, __less<_Tp>()); + return std::minmax(__t, __less<>()); } #endif // _LIBCPP_CXX03_LANG diff --git a/libcxx/include/__algorithm/minmax_element.h b/libcxx/include/__algorithm/minmax_element.h --- a/libcxx/include/__algorithm/minmax_element.h +++ b/libcxx/include/__algorithm/minmax_element.h @@ -94,7 +94,7 @@ template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_ForwardIterator, _ForwardIterator> minmax_element(_ForwardIterator __first, _ForwardIterator __last) { - return std::minmax_element(__first, __last, __less::value_type>()); + return std::minmax_element(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/next_permutation.h b/libcxx/include/__algorithm/next_permutation.h --- a/libcxx/include/__algorithm/next_permutation.h +++ b/libcxx/include/__algorithm/next_permutation.h @@ -69,8 +69,7 @@ bool next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) { - return _VSTD::next_permutation(__first, __last, - __less::value_type>()); + return _VSTD::next_permutation(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/partial_sort.h b/libcxx/include/__algorithm/partial_sort.h --- a/libcxx/include/__algorithm/partial_sort.h +++ b/libcxx/include/__algorithm/partial_sort.h @@ -88,8 +88,7 @@ void partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last) { - _VSTD::partial_sort(__first, __middle, __last, - __less::value_type>()); + _VSTD::partial_sort(__first, __middle, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/partial_sort_copy.h b/libcxx/include/__algorithm/partial_sort_copy.h --- a/libcxx/include/__algorithm/partial_sort_copy.h +++ b/libcxx/include/__algorithm/partial_sort_copy.h @@ -79,8 +79,7 @@ partial_sort_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result_first, _RandomAccessIterator __result_last) { - return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last, - __less::value_type>()); + return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/pop_heap.h b/libcxx/include/__algorithm/pop_heap.h --- a/libcxx/include/__algorithm/pop_heap.h +++ b/libcxx/include/__algorithm/pop_heap.h @@ -65,8 +65,7 @@ template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::pop_heap(std::move(__first), std::move(__last), - __less::value_type>()); + std::pop_heap(std::move(__first), std::move(__last), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/prev_permutation.h b/libcxx/include/__algorithm/prev_permutation.h --- a/libcxx/include/__algorithm/prev_permutation.h +++ b/libcxx/include/__algorithm/prev_permutation.h @@ -70,8 +70,7 @@ bool prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last) { - return _VSTD::prev_permutation(__first, __last, - __less::value_type>()); + return _VSTD::prev_permutation(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/push_heap.h b/libcxx/include/__algorithm/push_heap.h --- a/libcxx/include/__algorithm/push_heap.h +++ b/libcxx/include/__algorithm/push_heap.h @@ -69,8 +69,7 @@ template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::push_heap(std::move(__first), std::move(__last), - __less::value_type>()); + std::push_heap(std::move(__first), std::move(__last), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_difference.h b/libcxx/include/__algorithm/set_difference.h --- a/libcxx/include/__algorithm/set_difference.h +++ b/libcxx/include/__algorithm/set_difference.h @@ -66,14 +66,7 @@ _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) { - return std::__set_difference<_ClassicAlgPolicy>( - __first1, - __last1, - __first2, - __last2, - __result, - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()).second; + return std::__set_difference<_ClassicAlgPolicy>(__first1, __last1, __first2, __last2, __result, __less<>()).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_intersection.h b/libcxx/include/__algorithm/set_intersection.h --- a/libcxx/include/__algorithm/set_intersection.h +++ b/libcxx/include/__algorithm/set_intersection.h @@ -89,8 +89,7 @@ std::move(__first2), std::move(__last2), std::move(__result), - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()) + __less<>()) .__out_; } diff --git a/libcxx/include/__algorithm/set_symmetric_difference.h b/libcxx/include/__algorithm/set_symmetric_difference.h --- a/libcxx/include/__algorithm/set_symmetric_difference.h +++ b/libcxx/include/__algorithm/set_symmetric_difference.h @@ -96,8 +96,7 @@ std::move(__first2), std::move(__last2), std::move(__result), - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); + __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/set_union.h b/libcxx/include/__algorithm/set_union.h --- a/libcxx/include/__algorithm/set_union.h +++ b/libcxx/include/__algorithm/set_union.h @@ -92,8 +92,7 @@ std::move(__first2), std::move(__last2), std::move(__result), - __less::value_type, - typename iterator_traits<_InputIterator2>::value_type>()); + __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -123,8 +123,8 @@ // The comparator being simple is a prerequisite for using the branchless optimization. template struct __is_simple_comparator : false_type {}; -template -struct __is_simple_comparator<__less<_Tp>&> : true_type {}; +template <> +struct __is_simple_comparator<__less<>&> : true_type {}; template struct __is_simple_comparator&> : true_type {}; template @@ -884,7 +884,8 @@ long double>; template ::value, int> = 0> -_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, __less<_Type>& __comp) { +_LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, __less<>&) { + __less<_Type> __comp; std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp); } @@ -932,7 +933,7 @@ template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::sort(__first, __last, __less::value_type>()); + std::sort(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/sort_heap.h b/libcxx/include/__algorithm/sort_heap.h --- a/libcxx/include/__algorithm/sort_heap.h +++ b/libcxx/include/__algorithm/sort_heap.h @@ -47,8 +47,7 @@ template inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::sort_heap(std::move(__first), std::move(__last), - __less::value_type>()); + std::sort_heap(std::move(__first), std::move(__last), __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/stable_sort.h b/libcxx/include/__algorithm/stable_sort.h --- a/libcxx/include/__algorithm/stable_sort.h +++ b/libcxx/include/__algorithm/stable_sort.h @@ -270,7 +270,7 @@ template inline _LIBCPP_HIDE_FROM_ABI void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) { - std::stable_sort(__first, __last, __less::value_type>()); + std::stable_sort(__first, __last, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__algorithm/upper_bound.h b/libcxx/include/__algorithm/upper_bound.h --- a/libcxx/include/__algorithm/upper_bound.h +++ b/libcxx/include/__algorithm/upper_bound.h @@ -47,8 +47,7 @@ template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) { - static_assert(is_copy_constructible<_ForwardIterator>::value, - "Iterator has to be copy constructible"); + static_assert(is_copy_constructible<_ForwardIterator>::value, "Iterator has to be copy constructible"); return std::__upper_bound<_ClassicAlgPolicy>( std::move(__first), std::move(__last), __value, std::move(__comp), std::__identity()); } @@ -56,11 +55,7 @@ template _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) { - return std::upper_bound( - std::move(__first), - std::move(__last), - __value, - __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>()); + return std::upper_bound(std::move(__first), std::move(__last), __value, __less<>()); } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/forward_list b/libcxx/include/forward_list --- a/libcxx/include/forward_list +++ b/libcxx/include/forward_list @@ -865,18 +865,18 @@ _LIBCPP_HIDE_FROM_ABI __remove_return_type unique(_BinaryPredicate __binary_pred); #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY - void merge(forward_list&& __x) {merge(__x, __less());} + void merge(forward_list&& __x) {merge(__x, __less<>());} template _LIBCPP_INLINE_VISIBILITY void merge(forward_list&& __x, _Compare __comp) {merge(__x, _VSTD::move(__comp));} #endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY - void merge(forward_list& __x) {merge(__x, __less());} + void merge(forward_list& __x) {merge(__x, __less<>());} template _LIBCPP_HIDE_FROM_ABI void merge(forward_list& __x, _Compare __comp); _LIBCPP_INLINE_VISIBILITY - void sort() {sort(__less());} + void sort() {sort(__less<>());} template _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp); _LIBCPP_HIDE_FROM_ABI void reverse() _NOEXCEPT; diff --git a/libcxx/include/list b/libcxx/include/list --- a/libcxx/include/list +++ b/libcxx/include/list @@ -2101,7 +2101,7 @@ void list<_Tp, _Alloc>::merge(list& __c) { - merge(__c, __less()); + merge(__c, __less<>()); } template @@ -2163,7 +2163,7 @@ void list<_Tp, _Alloc>::sort() { - sort(__less()); + sort(__less<>()); } template diff --git a/libcxx/src/algorithm.cpp b/libcxx/src/algorithm.cpp --- a/libcxx/src/algorithm.cpp +++ b/libcxx/src/algorithm.cpp @@ -19,9 +19,10 @@ // that the default comparator is in use so that we are sure that there are no // branches in the comparator. std::__introsort<_ClassicAlgPolicy, - Comp&, + ranges::less, RandomAccessIterator, - __use_branchless_sort::value>(first, last, comp, depth_limit); + __use_branchless_sort::value>( + first, last, ranges::less{}, depth_limit); } // clang-format off diff --git a/libcxx/test/libcxx/algorithms/robust_against_using_non_transparent_comparators.pass.cpp b/libcxx/test/libcxx/algorithms/robust_against_using_non_transparent_comparators.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/algorithms/robust_against_using_non_transparent_comparators.pass.cpp @@ -0,0 +1,77 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include +#include +#include + +#include "test_macros.h" + +template +struct Iterator { + using value_type = T; + using pointer = value_type*; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + struct reference { + T* ptr_; + + friend bool operator<(reference a, reference b) { return *a.ptr_ < *b.ptr_; } + friend bool operator<(reference a, value_type const& b) { return *a.ptr_ < b; } + friend bool operator<(value_type const& a, reference b) { return a < *b.ptr_; } + + operator T&() const; + }; + + Iterator& operator++() { + ptr_++; + return *this; + } + + Iterator operator++(int) { + Iterator tmp = *this; + ptr_++; + return tmp; + } + + friend bool operator==(Iterator const& a, Iterator const& b) { return a.ptr_ == b.ptr_; } + friend bool operator!=(Iterator const& a, Iterator const& b) { return !(a == b); } + + reference operator*() const { return reference{ptr_}; } + + explicit Iterator(T* ptr) : ptr_(ptr) {} + Iterator() = default; + Iterator(Iterator const&) = default; + Iterator(Iterator&&) = default; + + Iterator& operator=(Iterator const&) = default; + Iterator& operator=(Iterator&&) = default; + +private: + T* ptr_; +}; + +int main() { + int array[5] = {1, 2, 3, 4, 5}; + int out[10]; + Iterator first{array}; + Iterator middle{array + 3}; + Iterator last{array + 5}; + (void)std::ranges::lexicographical_compare(first, last, first, last); + (void)std::binary_search(first, last, 3); + (void)std::equal_range(first, last, 3); + (void)std::includes(first, last, first, last); + (void)std::is_sorted_until(first, last); + (void)std::is_sorted(first, last); + (void)std::lexicographical_compare(first, last, first, last); + (void)std::lower_bound(first, last, 3); + (void)std::max_element(first, last); + (void)std::min_element(first, last); + (void)std::minmax_element(first, last); + (void)std::upper_bound(first, last, 3); +} diff --git a/libcxx/utils/data/ignore_format.txt b/libcxx/utils/data/ignore_format.txt --- a/libcxx/utils/data/ignore_format.txt +++ b/libcxx/utils/data/ignore_format.txt @@ -37,7 +37,6 @@ libcxx/benchmarks/vector_operations.bench.cpp libcxx/include/__algorithm/binary_search.h libcxx/include/__algorithm/clamp.h -libcxx/include/__algorithm/comp.h libcxx/include/__algorithm/comp_ref_type.h libcxx/include/__algorithm/copy_backward.h libcxx/include/__algorithm/copy_if.h @@ -207,7 +206,6 @@ libcxx/include/__algorithm/uniform_random_bit_generator_adaptor.h libcxx/include/__algorithm/unwrap_iter.h libcxx/include/__algorithm/unwrap_range.h -libcxx/include/__algorithm/upper_bound.h libcxx/include/any libcxx/include/array libcxx/include/__atomic/atomic_base.h