[libc++] Refactor __less

[philnik]

Summary

This simplifies the usage of __less by making the class not depend on the types compared, but instead the operator(). We can't remove the template completely because we explicitly instantiate std::__sort with __less<T>.

[EricWF]

This cleanup seems incomplete. Why keep __less as a template at all given it's never actually used as one?

Also does the iterator's ::value_type always have to exactly match the type returned from dereferencing it?

libcxx/include/__algorithm/comp.h

37

This doesn't at all seem correct to me.

This takes away an explicit conversion

libcxx/include/__algorithm/includes.h

64

Is this correct? What if the iterator returns a type convertible to value_type?

[EricWF]

libcxx/include/__algorithm/comp.h

37

*The implicit conversion.

[philnik]

In D145285#4176202, @EricWF wrote:

This cleanup seems incomplete. Why keep __less as a template at all given it's never actually used as one?

If you block other reviews on there not being a description, at least read it.

libcxx/include/__algorithm/includes.h

64

AFAICT the standard it either very silent on this, or says one should use less{} as the comparator, which does what __less<>{} does after this change. So this change is either a conforming change, or arguably a bugfix. Although funnily enough std::less{} isn't actually well-formed, and it doesn't specifically use ranges::less{} for the classic algorithms.

[philnik]

Try to fix CI

[ldionne]

libcxx/include/__algorithm/comp.h

32

So there's actually a behavior change in this patch (the removal of implicit conversions noticed by @EricWF). However, I think it is desirable -- right now I don't think we are conforming in C++20. For example, take lower_bound: http://eel.is/c++draft/lower.bound#1. It specifically says Let comp be less{} and proj be identity{} for overloads with no parameters by those names., which implies that we should be using the transparent comparator, but we are not (before this patch).

I think this mandates a change everywhere along with tests. We should also confirm what's the expected behavior in prior Standards and make sure we conform in those as well.

33

Please add a comment explaining why it's empty.

[philnik]

libcxx/include/__algorithm/comp.h

32

I'm not actually convinced this behaviour change is reliably observable. AFAICT it would only be possible to observe with an input_iterator that returns a proxy reference which is comparable to the referenced type. Even then, an implementation is most likely allowed to call both operator<(value_type&, proxy) and operator<(value_type&, value_type&). I'd argue that this case is unspecified behaviour.

[ldionne]

libcxx/include/__algorithm/comp.h

32

I am not sure whether this is actually spelled out explicitly in the standard, but it's definitely observable: https://godbolt.org/z/51WKExTxK

At the very least, I think we need to provide this guarantee as a QOI, and so we should have tests for that under libcxx/test/libcxx if not in libcxx/test/std.

libcxx/src/algorithm.cpp

24

Clearer IMO

[philnik]

Address comments

[ldionne]

libcxx/include/__algorithm/sort.h

895

901

908

916

libcxx/test/libcxx/algorithms/robust_against_using_non_transparent_comparators.pass.cpp

8 ↗

(On Diff #527639)

Let's add a comment explaining what this test does, in particular the fact that this is technically not mandated by the standard but we provide it as QOI.

28 ↗

(On Diff #527639)

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

libcxx/include/__algorithm/binary_search.h

 }
 
 template <class _ForwardIterator, class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 bool
 binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
 {
-    return std::binary_search(__first, __last, __value,
-                              __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
+    return std::binary_search(__first, __last, __value, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_BINARY_SEARCH_H

libcxx/include/__algorithm/clamp.h

 }
 
 template<class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY constexpr
 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
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_CLAMP_H

libcxx/include/__algorithm/comp.h

struct __equal_to {
   _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool operator()(const _T1& __x, const _T2& __y) const {
     return __x == __y;
   }
 };
 
 template <class _Lhs, class _Rhs>
 struct __is_trivial_equality_predicate<__equal_to, _Lhs, _Rhs> : true_type {};
 
-template <class _T1, class _T2 = _T1>
-struct __less
-{
-    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
-    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
+template <class _T1 = void, class _T2 = _T1>
+struct __less {};
 
-    _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 <class _T1>
-struct __less<_T1, _T1>
-{
-    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
-    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
-};
-
-template <class _T1>
-struct __less<const _T1, _T1>
-{
-    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
-    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
-};
-
-template <class _T1>
-struct __less<_T1, const _T1>
-{
-    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
-    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
+template <>
+struct __less<void, void> {
+  template <class _Tp, class _Up>
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 bool operator()(const _Tp& __lhs, const _Up& __rhs) const {
+    return __lhs < __rhs;
+  }
 };
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_COMP_H

libcxx/include/__algorithm/equal_range.h

return std::__equal_range<_ClassicAlgPolicy>(
       __value,
       static_cast<__comp_ref_type<_Compare> >(__comp),
       std::__identity());
 }
 
 template <class _ForwardIterator, class _Tp>
 _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<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
+  return std::equal_range(std::move(__first), std::move(__last), __value, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_EQUAL_RANGE_H

libcxx/include/__algorithm/includes.h

return std::__includes(
       static_cast<__comp_ref_type<_Compare> >(__comp),
       __identity(),
       __identity());
 }
 
 template <class _InputIterator1, class _InputIterator2>
 _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<typename iterator_traits<_InputIterator1>::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
 
 #endif // _LIBCPP___ALGORITHM_INCLUDES_H

libcxx/include/__algorithm/inplace_merge.h

std::__inplace_merge<_ClassicAlgPolicy>(
       std::move(__first), std::move(__middle), std::move(__last), static_cast<__comp_ref_type<_Compare> >(__comp));
 }
 
 template <class _BidirectionalIterator>
 inline _LIBCPP_HIDE_FROM_ABI
 void
 inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last)
 {
-    std::inplace_merge(std::move(__first), std::move(__middle), std::move(__last),
-                        __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
+    std::inplace_merge(std::move(__first), std::move(__middle), std::move(__last), __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_INPLACE_MERGE_H

libcxx/include/__algorithm/is_heap.h

 }
 
 template<class _RandomAccessIterator>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 bool
 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
-    return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+    return _VSTD::is_heap(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_IS_HEAP_H

libcxx/include/__algorithm/is_heap_until.h

 {
     return std::__is_heap_until(__first, __last, static_cast<__comp_ref_type<_Compare> >(__comp));
 }
 
 template<class _RandomAccessIterator>
 _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<typename iterator_traits<_RandomAccessIterator>::value_type>());
+    return _VSTD::__is_heap_until(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_IS_HEAP_UNTIL_H

libcxx/include/__algorithm/is_sorted.h

 }
 
 template<class _ForwardIterator>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 bool
 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
 {
-    return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());
+    return _VSTD::is_sorted(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_IS_SORTED_H

libcxx/include/__algorithm/is_sorted_until.h

 {
     return _VSTD::__is_sorted_until<__comp_ref_type<_Compare> >(__first, __last, __comp);
 }
 
 template<class _ForwardIterator>
 _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<typename iterator_traits<_ForwardIterator>::value_type>());
+    return _VSTD::is_sorted_until(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_IS_SORTED_UNTIL_H

libcxx/include/__algorithm/lexicographical_compare.h

 
 template <class _InputIterator1, class _InputIterator2>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 bool
 lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
                         _InputIterator2 __first2, _InputIterator2 __last2)
 {
-    return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2,
-                                         __less<typename iterator_traits<_InputIterator1>::value_type,
-                                                typename iterator_traits<_InputIterator2>::value_type>());
+    return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_H

libcxx/include/__algorithm/lower_bound.h

static_assert(__is_callable<_Compare, decltype(*__first), const _Tp&>::value,
                 "The comparator has to be callable");
   auto __proj = std::__identity();
   return std::__lower_bound_impl<_ClassicAlgPolicy>(__first, __last, __value, __comp, __proj);
 }
 
 template <class _ForwardIterator, class _Tp>
 _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<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
+  return std::lower_bound(__first, __last, __value, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_LOWER_BOUND_H

libcxx/include/__algorithm/make_heap.h

 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   std::__make_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 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<typename iterator_traits<_RandomAccessIterator>::value_type>());
+  std::make_heap(std::move(__first), std::move(__last), __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MAKE_HEAP_H

libcxx/include/__algorithm/max.h

 }
 
 template <class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
 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
 
 template<class _Tp, class _Compare>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
 _Tp
 max(initializer_list<_Tp> __t, _Compare __comp)
 {
     return *_VSTD::__max_element<__comp_ref_type<_Compare> >(__t.begin(), __t.end(), __comp);
 }
 
 template<class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
 _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
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_MAX_H

libcxx/include/__algorithm/max_element.h

max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
     return _VSTD::__max_element<__comp_ref_type<_Compare> >(__first, __last, __comp);
 }
 
 
 template <class _ForwardIterator>
 _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<typename iterator_traits<_ForwardIterator>::value_type>());
+    return _VSTD::max_element(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MAX_ELEMENT_H

libcxx/include/__algorithm/merge.h

 }
 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 _OutputIterator
 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
 
 #endif // _LIBCPP___ALGORITHM_MERGE_H

libcxx/include/__algorithm/min.h

 }
 
 template <class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
 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
 
 template<class _Tp, class _Compare>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
 _Tp
 min(initializer_list<_Tp> __t, _Compare __comp)
 {
     return *_VSTD::__min_element<__comp_ref_type<_Compare> >(__t.begin(), __t.end(), __comp);
 }
 
 template<class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
 _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
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_MIN_H

libcxx/include/__algorithm/min_element.h

min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
 
   return std::__min_element<__comp_ref_type<_Compare> >(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _ForwardIterator>
 _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<typename iterator_traits<_ForwardIterator>::value_type>());
+    return _VSTD::min_element(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MIN_ELEMENT_H

libcxx/include/__algorithm/minmax.h

 }
 
 template<class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
 pair<const _Tp&, const _Tp&>
 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
 
 template<class _Tp, class _Compare>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14
 pair<_Tp, _Tp> minmax(initializer_list<_Tp> __t, _Compare __comp) {
     static_assert(__is_callable<_Compare, _Tp, _Tp>::value, "The comparator has to be callable");
     __identity __proj;
     auto __ret = std::__minmax_element_impl(__t.begin(), __t.end(), __comp, __proj);
     return pair<_Tp, _Tp>(*__ret.first, *__ret.second);
 }
 
 template<class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX14
 pair<_Tp, _Tp>
 minmax(initializer_list<_Tp> __t)
 {
-    return std::minmax(__t, __less<_Tp>());
+    return std::minmax(__t, __less<>());
 }
 
 #endif // _LIBCPP_CXX03_LANG
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MINMAX_H

libcxx/include/__algorithm/minmax_element.h

static_assert(__is_callable<_Compare, decltype(*__first), decltype(*__first)>::value,
                 "The comparator has to be callable");
   auto __proj = __identity();
   return std::__minmax_element_impl(__first, __last, __comp, __proj);
 }
 
 template <class _ForwardIterator>
 _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<typename iterator_traits<_ForwardIterator>::value_type>());
+    return std::minmax_element(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MINMAX_ELEMENT_H

libcxx/include/__algorithm/next_permutation.h

return std::__next_permutation<_ClassicAlgPolicy>(
       std::move(__first), std::move(__last), static_cast<__comp_ref_type<_Compare> >(__comp)).second;
 }
 
 template <class _BidirectionalIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 bool
 next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
-    return _VSTD::next_permutation(__first, __last,
-                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
+    return _VSTD::next_permutation(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_NEXT_PERMUTATION_H

libcxx/include/__algorithm/partial_sort.h

partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
   (void)std::__partial_sort<_ClassicAlgPolicy>(std::move(__first), std::move(__middle), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
-    _VSTD::partial_sort(__first, __middle, __last,
-                        __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+    _VSTD::partial_sort(__first, __middle, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PARTIAL_SORT_H

libcxx/include/__algorithm/partial_sort_copy.h

 }
 
 template <class _InputIterator, class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 _RandomAccessIterator
 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<typename iterator_traits<_RandomAccessIterator>::value_type>());
+    return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PARTIAL_SORT_COPY_H

libcxx/include/__algorithm/pop_heap.h

void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
 
   typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;
   std::__pop_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp, __len);
 }
 
 template <class _RandomAccessIterator>
 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<typename iterator_traits<_RandomAccessIterator>::value_type>());
+  std::pop_heap(std::move(__first), std::move(__last), __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_POP_HEAP_H

libcxx/include/__algorithm/prev_permutation.h

return std::__prev_permutation<_ClassicAlgPolicy>(
       std::move(__first), std::move(__last), static_cast<__comp_ref_type<_Compare> >(__comp)).second;
 }
 
 template <class _BidirectionalIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20
 bool
 prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last)
 {
-    return _VSTD::prev_permutation(__first, __last,
-                                  __less<typename iterator_traits<_BidirectionalIterator>::value_type>());
+    return _VSTD::prev_permutation(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PREV_PERMUTATION_H

libcxx/include/__algorithm/push_heap.h

void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
 
   std::__push_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 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<typename iterator_traits<_RandomAccessIterator>::value_type>());
+  std::push_heap(std::move(__first), std::move(__last), __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PUSH_HEAP_H

libcxx/include/__algorithm/set_difference.h

 
 template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_difference(
     _InputIterator1 __first1,
     _InputIterator1 __last1,
     _InputIterator2 __first2,
     _InputIterator2 __last2,
     _OutputIterator __result) {
-  return std::__set_difference<_ClassicAlgPolicy>(
-      __first1,
-      __last1,
-      __first2,
-      __last2,
-      __result,
-      __less<typename iterator_traits<_InputIterator1>::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
 
 #endif // _LIBCPP___ALGORITHM_SET_DIFFERENCE_H

libcxx/include/__algorithm/set_intersection.h

inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_intersection(
     _InputIterator2 __last2,
     _OutputIterator __result) {
   return std::__set_intersection<_ClassicAlgPolicy>(
              std::move(__first1),
              std::move(__last1),
              std::move(__first2),
              std::move(__last2),
              std::move(__result),
-             __less<typename iterator_traits<_InputIterator1>::value_type,
-                    typename iterator_traits<_InputIterator2>::value_type>())
+             __less<>())
       .__out_;
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SET_INTERSECTION_H

libcxx/include/__algorithm/set_symmetric_difference.h

_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_symmetric_difference(
     _InputIterator2 __last2,
     _OutputIterator __result) {
   return std::set_symmetric_difference(
       std::move(__first1),
       std::move(__last1),
       std::move(__first2),
       std::move(__last2),
       std::move(__result),
-      __less<typename iterator_traits<_InputIterator1>::value_type,
-             typename iterator_traits<_InputIterator2>::value_type>());
+      __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SET_SYMMETRIC_DIFFERENCE_H

libcxx/include/__algorithm/set_union.h

_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator set_union(
     _InputIterator2 __last2,
     _OutputIterator __result) {
   return std::set_union(
       std::move(__first1),
       std::move(__last1),
       std::move(__first2),
       std::move(__last2),
       std::move(__result),
-      __less<typename iterator_traits<_InputIterator1>::value_type,
-             typename iterator_traits<_InputIterator2>::value_type>());
+      __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SET_UNION_H

libcxx/include/__algorithm/sort.h

if (__comp(*__x4, *__x3)) {
       }
     }
   }
 }
 
 // The comparator being simple is a prerequisite for using the branchless optimization.
 template <class _Tp>
 struct __is_simple_comparator : false_type {};
-template <class _Tp>
-struct __is_simple_comparator<__less<_Tp>&> : true_type {};
+template <>
+struct __is_simple_comparator<__less<>&> : true_type {};
 template <class _Tp>
 struct __is_simple_comparator<less<_Tp>&> : true_type {};
 template <class _Tp>
 struct __is_simple_comparator<greater<_Tp>&> : true_type {};
 #if _LIBCPP_STD_VER >= 20
 template <>
 struct __is_simple_comparator<ranges::less&> : true_type {};
 template <>
#endif
     unsigned long,
     long long,
     unsigned long long,
     float,
     double,
     long double>;
 
 template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::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<>& __comp) {
   std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
 }
 
 template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
 _LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<_Type>&) {
   __less<_Type> __comp;
   std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
 }
 
 #if _LIBCPP_STD_VER >= 14
 template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
 _LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, less<>&) {
   __less<_Type> __comp;
   std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
 }
 #endif
 
 #if _LIBCPP_STD_VER >= 20
 template <class _AlgPolicy, class _Type, __enable_if_t<__sort_is_specialized_in_library<_Type>::value, int> = 0>
 _LIBCPP_HIDE_FROM_ABI void __sort_dispatch(_Type* __first, _Type* __last, ranges::less&) {
   __less<_Type> __comp;
   std::__sort<__less<_Type>&, _Type*>(__first, __last, __comp);
 }
 #endif
 
 template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
   std::__debug_randomize_range<_AlgPolicy>(__first, __last);
 

 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
   std::__sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
 void sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
-  std::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+  std::sort(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SORT_H

libcxx/include/__algorithm/sort_heap.h

void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
 
   std::__sort_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 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<typename iterator_traits<_RandomAccessIterator>::value_type>());
+  std::sort_heap(std::move(__first), std::move(__last), __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SORT_HEAP_H

libcxx/include/__algorithm/stable_sort.h

 inline _LIBCPP_HIDE_FROM_ABI
 void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   std::__stable_sort_impl<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI
 void stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
-  std::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+  std::stable_sort(__first, __last, __less<>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_STABLE_SORT_H

libcxx/include/__algorithm/upper_bound.h

while (__len != 0) {
     }
   }
   return __first;
 }
 
 template <class _ForwardIterator, class _Tp, class _Compare>
 _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());
 }
 
 template <class _ForwardIterator, class _Tp>
 _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
 
 #endif // _LIBCPP___ALGORITHM_UPPER_BOUND_H

libcxx/include/forward_list

void splice_after(const_iterator __p, forward_list& __x,
                       const_iterator __f, const_iterator __l);
     __remove_return_type remove(const value_type& __v);
     template <class _Predicate> __remove_return_type remove_if(_Predicate __pred);
     _LIBCPP_INLINE_VISIBILITY
     __remove_return_type unique() { return unique(__equal_to()); }
     template <class _BinaryPredicate> __remove_return_type unique(_BinaryPredicate __binary_pred);
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
-    void merge(forward_list&& __x) {merge(__x, __less<value_type>());}
+    void merge(forward_list&& __x) {merge(__x, __less<>());}
     template <class _Compare>
         _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<value_type>());}
+    void merge(forward_list& __x) {merge(__x, __less<>());}
     template <class _Compare> void merge(forward_list& __x, _Compare __comp);
     _LIBCPP_INLINE_VISIBILITY
-    void sort() {sort(__less<value_type>());}
+    void sort() {sort(__less<>());}
     template <class _Compare> _LIBCPP_INLINE_VISIBILITY void sort(_Compare __comp);
     void reverse() _NOEXCEPT;
 
 private:
 
 #ifndef _LIBCPP_CXX03_LANG
     void __move_assign(forward_list& __x, true_type)
         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);

libcxx/include/list

list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
     return (__remove_return_type) __deleted_nodes.size();
 }
 
 template <class _Tp, class _Alloc>
 inline
 void
 list<_Tp, _Alloc>::merge(list& __c)
 {
-    merge(__c, __less<value_type>());
+    merge(__c, __less<>());
 }
 
 template <class _Tp, class _Alloc>
 template <class _Comp>
 void
 list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
 {
     if (this != _VSTD::addressof(__c))
#endif
     }
 }
 
 template <class _Tp, class _Alloc>
 inline
 void
 list<_Tp, _Alloc>::sort()
 {
-    sort(__less<value_type>());
+    sort(__less<>());
 }
 
 template <class _Tp, class _Alloc>
 template <class _Comp>
 inline
 void
 list<_Tp, _Alloc>::sort(_Comp __comp)
 {

libcxx/src/algorithm.cpp

 template <class Comp, class RandomAccessIterator>
 void __sort(RandomAccessIterator first, RandomAccessIterator last, Comp comp) {
   auto depth_limit = 2 * std::__bit_log2(static_cast<size_t>(last - first));
 
   // Only use bitset partitioning for arithmetic types.  We should also check
   // 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<Comp, RandomAccessIterator>::value>(first, last, comp, depth_limit);
+                   __use_branchless_sort<ranges::less, RandomAccessIterator>::value>(first, last, {}, depth_limit);
 }
 
 // clang-format off
 template void __sort<__less<char>&, char*>(char*, char*, __less<char>&);
 #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
 template void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&);
 #endif
 template void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&);

libcxx/utils/data/ignore_format.txt

 libcxx/benchmarks/ordered_set.bench.cpp
 libcxx/benchmarks/random.bench.cpp
 libcxx/benchmarks/string.bench.cpp
 libcxx/benchmarks/stringstream.bench.cpp
 libcxx/benchmarks/unordered_set_operations.bench.cpp
 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.h
 libcxx/include/__algorithm/copy_if.h
 libcxx/include/__algorithm/copy_move_common.h
 libcxx/include/__algorithm/copy_n.h
 libcxx/include/__algorithm/equal.h
 libcxx/include/__algorithm/equal_range.h

 libcxx/include/__algorithm/sort_heap.h
 libcxx/include/__algorithm/stable_partition.h
 libcxx/include/__algorithm/stable_sort.h
 libcxx/include/__algorithm/swap_ranges.h
 libcxx/include/__algorithm/transform.h
 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
 libcxx/include/__atomic/atomic_base.h
 libcxx/include/__atomic/atomic_flag.h
 libcxx/include/__atomic/atomic.h
 libcxx/include/__atomic/atomic_init.h
 libcxx/include/__atomic/atomic_lock_free.h