[libc++] Eliminate needless `add_lvalue_reference` from <algorithm> helpers. NFCI.

[• Quuxplusone]

Summary

When _Compare is a function parameter already (so it's not void and it's not an abominable function type), add_lvalue_reference_t<_Compare> is simply a synonym for _Compare&. We don't need to pull in <type_traits> and instantiate a template trait to figure that out.

Inspired by D108393.

This is arguably one small step on the path to eventually rationalizing our __comp_ref_type weirdness. (Ultimately, we want our internal predicate type never to be a reference type, so that we can stop specifying template arguments explicitly. This definitely doesn't get us there, but at least it eliminates some reducible complexity in the same general area.)

[ldionne]

LGTM. I landed D108393 separately because those were orthogonal changes IMO. Please rebase and merge this!

libcxx/include/__algorithm/comp_ref_type.h

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_COMP_REF_TYPE_H
 #define _LIBCPP___ALGORITHM_COMP_REF_TYPE_H
 
 #include <__config>
-#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

 
 #endif // _LIBCPP_DEBUG
 
 template <class _Comp>
 struct __comp_ref_type {
   // Pass the comparator by lvalue reference. Or in debug mode, using a
   // debugging wrapper that stores a reference.
 #ifndef _LIBCPP_DEBUG
-  typedef typename add_lvalue_reference<_Comp>::type type;
+  typedef _Comp& type;
 #else
   typedef __debug_less<_Comp> type;
 #endif
 };
 
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_COMP_REF_TYPE_H

libcxx/include/__algorithm/equal.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_EQUAL_H
 #define _LIBCPP___ALGORITHM_EQUAL_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
-#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 __equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2,
         _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag,
         random_access_iterator_tag) {
   if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
     return false;
   return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2,
-                      typename add_lvalue_reference<_BinaryPredicate>::type>(__first1, __last1, __first2, __pred);
+                      _BinaryPredicate&>(__first1, __last1, __first2, __pred);
 }
 
 template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
       _BinaryPredicate __pred) {
-  return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type>(
+  return _VSTD::__equal<_BinaryPredicate&>(
       __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_InputIterator1>::iterator_category(),
       typename iterator_traits<_InputIterator2>::iterator_category());
 }
 
 template <class _InputIterator1, class _InputIterator2>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {
   typedef typename iterator_traits<_InputIterator1>::value_type __v1;

libcxx/include/__algorithm/find_end.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_FIND_END_OF_H
 #define _LIBCPP___ALGORITHM_FIND_END_OF_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__iterator/iterator_traits.h>
-#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
while (true) {
     }
   }
 }
 
 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1
 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2,
          _BinaryPredicate __pred) {
-  return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type>(
+  return _VSTD::__find_end<_BinaryPredicate&>(
       __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(),
       typename iterator_traits<_ForwardIterator2>::iterator_category());
 }
 
 template <class _ForwardIterator1, class _ForwardIterator2>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1
 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) {
   typedef typename iterator_traits<_ForwardIterator1>::value_type __v1;

libcxx/include/__algorithm/is_permutation.h

 #ifndef _LIBCPP___ALGORITHM_IS_PERMUTATION_H
 #define _LIBCPP___ALGORITHM_IS_PERMUTATION_H
 
 #include <__algorithm/comp.h>
 #include <__config>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/next.h>
-#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

 template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>
 _LIBCPP_CONSTEXPR_AFTER_CXX17 bool __is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1,
                                                     _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2,
                                                     _BinaryPredicate __pred, random_access_iterator_tag,
                                                     random_access_iterator_tag) {
   if (_VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2))
     return false;
   return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2,
-                               typename add_lvalue_reference<_BinaryPredicate>::type>(__first1, __last1, __first2,
-                                                                                      __pred);
+                               _BinaryPredicate&>(__first1, __last1, __first2, __pred);
 }
 
 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
                _ForwardIterator2 __last2, _BinaryPredicate __pred) {
-  return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type>(
+  return _VSTD::__is_permutation<_BinaryPredicate&>(
       __first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(),
       typename iterator_traits<_ForwardIterator2>::iterator_category());
 }
 
 template <class _ForwardIterator1, class _ForwardIterator2>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
                _ForwardIterator2 __last2) {

libcxx/include/__algorithm/lower_bound.h

 }
 
 template <class _ForwardIterator, class _Tp, class _Compare>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator
 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
 {
-    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
-    return _VSTD::__lower_bound<_Comp_ref>(__first, __last, __value_, __comp);
+    return _VSTD::__lower_bound<_Compare&>(__first, __last, __value_, __comp);
 }
 
 template <class _ForwardIterator, class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator
 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
 {

libcxx/include/__algorithm/partition.h

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_PARTITION_H
 #define _LIBCPP___ALGORITHM_PARTITION_H
 
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/swap.h>
 #include <utility> // pair
-#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
     }
 }
 
 template <class _ForwardIterator, class _Predicate>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator
 partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
 {
-    return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type>
-                            (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
+    return _VSTD::__partition<_Predicate&>(
+        __first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_PARTITION_H

libcxx/include/__algorithm/remove_if.h

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_REMOVE_IF_H
 #define _LIBCPP___ALGORITHM_REMOVE_IF_H
 
 #include <__config>
 #include <__algorithm/find_if.h>
 #include <utility>
-#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _ForwardIterator, class _Predicate>
 _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
 remove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
 {
-    __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type>
-                           (__first, __last, __pred);
+    __first = _VSTD::find_if<_ForwardIterator, _Predicate&>(__first, __last, __pred);
     if (__first != __last)
     {
         _ForwardIterator __i = __first;
         while (++__i != __last)
         {
             if (!__pred(*__i))
             {
                 *__first = _VSTD::move(*__i);

libcxx/include/__algorithm/search.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_SEARCH_H
 #define _LIBCPP___ALGORITHM_SEARCH_H
 
 #include <__algorithm/comp.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
-#include <type_traits>
 #include <utility>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
while (true) {
     }
   }
 }
 
 template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1
 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2,
        _BinaryPredicate __pred) {
-  return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>(
+  return _VSTD::__search<_BinaryPredicate&>(
              __first1, __last1, __first2, __last2, __pred,
              typename iterator_traits<_ForwardIterator1>::iterator_category(),
              typename iterator_traits<_ForwardIterator2>::iterator_category()).first;
 }
 
 template <class _ForwardIterator1, class _ForwardIterator2>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator1
 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) {

libcxx/include/__algorithm/search_n.h

 // -*- C++ -*-
 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_SEARCH_N_H
 #define _LIBCPP___ALGORITHM_SEARCH_N_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__iterator/iterator_traits.h>
-#include <type_traits>
+#include <type_traits>  // __convert_to_integral
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
while (true) {
       } // else there is a match, check next elements
     }
   }
 }
 
 template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator search_n(
     _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred) {
-  return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type>(
+  return _VSTD::__search_n<_BinaryPredicate&>(
       __first, __last, _VSTD::__convert_to_integral(__count), __value_, __pred,
       typename iterator_traits<_ForwardIterator>::iterator_category());
 }
 
 template <class _ForwardIterator, class _Size, class _Tp>
 _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
 search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_) {
   typedef typename iterator_traits<_ForwardIterator>::value_type __v;
   return _VSTD::search_n(__first, __last, _VSTD::__convert_to_integral(__count), __value_, __equal_to<__v, _Tp>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_SEARCH_N_H

libcxx/include/__algorithm/sort.h

 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/min_element.h>
 #include <__algorithm/partial_sort.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__utility/swap.h>
 #include <memory>
-#include <type_traits> // swap
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 

 // Assumes size > 0
 template <class _Compare, class _BidirectionalIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __selection_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)
 {
     _BidirectionalIterator __lm1 = __last;
     for (--__lm1; __first != __lm1; ++__first)
     {
-        _BidirectionalIterator __i = _VSTD::min_element<_BidirectionalIterator,
-                                                        typename add_lvalue_reference<_Compare>::type>
-                                                       (__first, __last, __comp);
+        _BidirectionalIterator __i = _VSTD::min_element<_BidirectionalIterator, _Compare&>(__first, __last, __comp);
         if (__i != __first)
             swap(*__first, *__i);
     }
 }
 
 template <class _Compare, class _BidirectionalIterator>
 void
 __insertion_sort(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp)

libcxx/include/__algorithm/stable_partition.h

__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
     // Else not enough buffer, do in place
     // __len >= 3
     _ForwardIterator __m = __first;
     _Distance __len2 = __len / 2;  // __len2 >= 2
     _VSTD::advance(__m, __len2);
     // recurse on [__first, __m), *__first know to be false
     // F?????????????????
     // f       m         l
-    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
-    _ForwardIterator __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit);
+    _ForwardIterator __first_false = _VSTD::__stable_partition<_Predicate&>(__first, __m, __pred, __len2, __p, __fit);
     // TTTFFFFF??????????
     // f  ff   m         l
     // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
     _ForwardIterator __m1 = __m;
     _ForwardIterator __second_false = __last;
     _Distance __len_half = __len - __len2;
     while (__pred(*__m1))
     {
         if (++__m1 == __last)
             goto __second_half_done;
         --__len_half;
     }
     // TTTFFFFFTTTF??????
     // f  ff   m  m1     l
-    __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);
+    __second_false = _VSTD::__stable_partition<_Predicate&>(__m1, __last, __pred, __len_half, __p, __fit);
 __second_half_done:
     // TTTFFFFFTTTTTFFFFF
     // f  ff   m    sf   l
     return _VSTD::rotate(__first_false, __m, __second_false);
     // TTTTTTTTFFFFFFFFFF
     //         |
 }
 
__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred,
     difference_type __len = _VSTD::distance(__first, __last);
     pair<value_type*, ptrdiff_t> __p(0, 0);
     unique_ptr<value_type, __return_temporary_buffer> __h;
     if (__len >= __alloc_limit)
     {
         __p = _VSTD::get_temporary_buffer<value_type>(__len);
         __h.reset(__p.first);
     }
-    return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type>
-                             (__first, __last, __pred, __len, __p, forward_iterator_tag());
+    return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, __len, __p, forward_iterator_tag());
 }
 
 template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>
 _BidirectionalIterator
 __stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
                    _Distance __len, _Pair __p, bidirectional_iterator_tag __bit)
 {
     // *__first is known to be false
__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
     while (!__pred(*--__m1))
     {
         if (__m1 == __first)
             goto __first_half_done;
         --__len_half;
     }
     // F???TFFF?????????T
     // f   m1  m        l
-    typedef typename add_lvalue_reference<_Predicate>::type _PredRef;
-    __first_false = _VSTD::__stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);
+    __first_false = _VSTD::__stable_partition<_Predicate&>(__first, __m1, __pred, __len_half, __p, __bit);
 __first_half_done:
     // TTTFFFFF?????????T
     // f  ff   m        l
     // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true
     __m1 = __m;
     _BidirectionalIterator __second_false = __last;
     ++__second_false;
     __len_half = __len - __len2;
     while (__pred(*__m1))
     {
         if (++__m1 == __last)
             goto __second_half_done;
         --__len_half;
     }
     // TTTFFFFFTTTF?????T
     // f  ff   m  m1    l
-    __second_false = _VSTD::__stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);
+    __second_false = _VSTD::__stable_partition<_Predicate&>(__m1, __last, __pred, __len_half, __p, __bit);
 __second_half_done:
     // TTTFFFFFTTTTTFFFFF
     // f  ff   m    sf  l
     return _VSTD::rotate(__first_false, __m, __second_false);
     // TTTTTTTTFFFFFFFFFF
     //         |
 }
 
__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred,
     difference_type __len = _VSTD::distance(__first, __last) + 1;
     pair<value_type*, ptrdiff_t> __p(0, 0);
     unique_ptr<value_type, __return_temporary_buffer> __h;
     if (__len >= __alloc_limit)
     {
         __p = _VSTD::get_temporary_buffer<value_type>(__len);
         __h.reset(__p.first);
     }
-    return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type>
-                             (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
+    return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, __len, __p, bidirectional_iterator_tag());
 }
 
 template <class _ForwardIterator, class _Predicate>
 inline _LIBCPP_INLINE_VISIBILITY
 _ForwardIterator
 stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred)
 {
-    return _VSTD::__stable_partition<typename add_lvalue_reference<_Predicate>::type>
-                             (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
+    return _VSTD::__stable_partition<_Predicate&>(__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_STABLE_PARTITION_H

libcxx/include/__algorithm/unique.h

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_UNIQUE_H
 #define _LIBCPP___ALGORITHM_UNIQUE_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/adjacent_find.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
-#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 // unique
 
 template <class _ForwardIterator, class _BinaryPredicate>
 _LIBCPP_NODISCARD_EXT _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
 unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
 {
-    __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type>
-                                 (__first, __last, __pred);
+    __first = _VSTD::adjacent_find<_ForwardIterator, _BinaryPredicate&>(__first, __last, __pred);
     if (__first != __last)
     {
         // ...  a  a  ?  ...
         //      f     i
         _ForwardIterator __i = __first;
         for (++__i; ++__i != __last;)
             if (!__pred(*__first, *__i))
                 *++__first = _VSTD::move(*__i);

libcxx/include/__algorithm/unique_copy.h

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_UNIQUE_COPY_H
 #define _LIBCPP___ALGORITHM_UNIQUE_COPY_H
 
 #include <__config>
 #include <__algorithm/comp.h>
 #include <__iterator/iterator_traits.h>
 #include <utility>
-#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
__unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred,
     return __result;
 }
 
 template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred)
 {
-    return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type>
-                              (__first, __last, __result, __pred,
+    return _VSTD::__unique_copy<_BinaryPredicate&>(__first, __last, __result, __pred,
                                typename iterator_traits<_InputIterator>::iterator_category(),
                                typename iterator_traits<_OutputIterator>::iterator_category());
 }
 
 template <class _InputIterator, class _OutputIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _OutputIterator
 unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result)

libcxx/include/__algorithm/upper_bound.h

 }
 
 template <class _ForwardIterator, class _Tp, class _Compare>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator
 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp)
 {
-    typedef typename add_lvalue_reference<_Compare>::type _Comp_ref;
-    return _VSTD::__upper_bound<_Comp_ref>(__first, __last, __value_, __comp);
+    return _VSTD::__upper_bound<_Compare&>(__first, __last, __value_, __comp);
 }
 
 template <class _ForwardIterator, class _Tp>
 _LIBCPP_NODISCARD_EXT inline
 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator
 upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
 {