[libc++][ranges] implement `std::ranges::equal_range`

[huixie90]

Summary

[libc++][ranges] implement std::ranges::equal_range

[huixie90]

added tests

[huixie90]

update status csv

[huixie90]

fix CI

[huixie90]

try again to fix CI

[huixie90]

try again to fix CI

[huixie90]

try again

[var-const]

Thanks!

libcxx/include/__algorithm/equal_range.h

43

Why not use __make_projected? Wouldn't this cause a visible change in behavior for the classic algorithm (now accepting a pointer-to-member as the comparator)? (alternatively, you could do a static_assert(__is_callable) like in e.g. lower_bound).

52

Does this need to be forwarded, or not?

52

You probably need to pass _Compare explicitly as well, I'm not sure why it wasn't done before (_Compare is normally a reference, so type deduction would decay it to a value).

56

Nit: make_pair?

64

Why is this cast necessary, and does it work in debug mode? (when _Comp_ref is a struct)

libcxx/include/__algorithm/upper_bound.h

50

Move?

57

Please don't remove the inlines -- this could increase binary size. We plan to do some investigation and potentially make a dedicated patch to clean up these unwanted inlines.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/equal.range/ranges_equal_range.pass.cpp

40

Do these have to be forwarded as well?

55

Nit: I know it's a pattern, but perhaps we could rename this? RangeRange looks a little awkward.

71

Nit: s/N1/N/.

96

Nit: consider s/is in the middle/would be in the middle/.

120

Ultranit: s/exact/exactly/.

164

This can be omitted -- I'll merge the robust_against_dangling patch very soon.

192

Optional: share this comparator across the two test cases?

[philnik]

libcxx/include/__algorithm/equal_range.h

52

You don't have to (and can't really) pass _Compare explicitly. __lower_bound_impl always takes the comparator by reference instead of by value. I don't know why this hasn't been done this way before, but that makes a lot more sense that explicitly passing the template parameter around everywhere.

[var-const]

libcxx/include/__algorithm/equal_range.h

52

I think it was done that way to support _Comp_ref resolving to either a reference type (in a regular build) or a non-reference type (in a debug build). Does that not apply here?

[philnik]

libcxx/include/__algorithm/equal_range.h

52

That does apply, but why wouldn't you just pass _Comp_ref by reference? The only thing may be that passing it by value is more efficient, but I would expect the functions to be inlined anyways, so it shouldn't matter.

[huixie90]

address feedback

libcxx/include/__algorithm/equal_range.h

43

__make_projected cannot be used here because the __comp takes two arguments but we only want to apply __proj to only one of arguments. And tricky thing is sometimes we want to apply __proj for the first argument (see line above) and sometimes we want to apply __proj to the second argument (see few lines below).

It is just much easier to pass in the comp and proj and explicitly write how to apply the projection. I will add static_assert

52

re "Does this need to be forwarded, or not?"
I think it is not. the same expression used the variables twice and you cannot decide which one is executed first so forwarding them just introduces possibility of use-after-move

re pass _Compare explicitly, I agree with @philnik , we shouldn't explicit specify the template argument here and should let it deduced. would decay it to a value is not correct anymore as both functions take arguments by reference.

Actually "explicit specifying the template argument creates problems". My intent of __upper_bound is taking comp by forwarding reference, but explicitly specifying the template arguments makes it pass by rvalue reference. (which triggers some ci failure)

56

Extra nit nit: make_pair in c++03 does extra copies. since it is similar readability, perhaps just leave it as it is? (the original code on the left uses the constructor)

64

I added static_cast to fix a CI failure but it was in the wrong place. The problem is the one I explained above. In debug mode, the _Comp_ref is debug_less and the __equal_range deduced _Compare to debug_less . then later, it calls __upper_bound<policy, _Compare>
However, __upper_bound meant to take __comp by forwarding reference T&&. But by explicitly specifying the template argument _Compare, it changes the meaning and makes it take the rvalue-reference debug_less&&. But in the context of __equal_range, __comp is an l-value expression of type debug_less&&. And an lvalue cannot be bond to an r-value reference input, thus caused failure.

So we should not really explicit specifying template arguments now as most algorithms takes _Compare by reference (either lvalue reference or forwarding reference). and explicit writing the type can only cause harm.

It was useful in the past because they used to take _Compare by value. But now we are trying our best not to make copies so _Compare are mostly passed by references. If the passing-by-reference causes performance regression, we should revisit all the algorithms. But explicit writing the template argument does not help because you cannot stop them being passed by reference

Here I will just remove the explicit template argument and leave the static_cast. In normal build it does nothing because it casts an l-value to an lvalue reference. In debug mode, it will construct the temporary debug_less struct

[huixie90]

update one more caller

[huixie90]

rebase

[var-const]

libcxx/include/__algorithm/equal_range.h

64

Hmm, using an rvalue reference as the argument type looks promising. The _Comp_ref quirk makes things pretty inconvenient, in the future it would be great to clean it up as much as possible without losing the functionality.

libcxx/include/__algorithm/upper_bound.h

60

@philnik has previously pointed out in one of my patches that this could make the classic algorithm more permissive than mandated by the standard by accepting move-only iterator types. FWIW, I worked around that by adding a static_assert(is_copy_constructible<>::value).

Feel free to address in a follow-up.

[huixie90]

add static_assert

[huixie90]

fix merge conflicts

[var-const]

I think the CI failure is unrelated and was fixed in main, so rebasing would hopefully fix it.

[huixie90]

rebase

libcxx/docs/Status/RangesAlgorithms.csv

 Category,Algorithm,Assignee,CL,Complete
 Search,any_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 Search,all_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 Search,none_of,Nikolas Klauser,`D123016 <https://llvm.org/D123016>`_,✅
 Search,find,Nikolas Klauser,`D121248 <https://llvm.org/D121248>`_,✅
 Search,find_if,Nikolas Klauser,`D121248 <https://llvm.org/D121248>`_,✅
 Search,find_if_not,Nikolas Klauser,`D121248 <https://llvm.org/D121248>`_,✅
 Search,find_first_of,Nikolas Klauser,`D126529 <https://llvm.org/D126529>`_,✅
 Search,adjacent_find,Nikolas Klauser,`D126610 <https://llvm.org/D126610>`_,✅
 Search,mismatch,Nikolas Klauser,`D117817 <https://llvm.org/D117817>`_,✅
 Search,equal,Nikolas Klauser,`D123681 <https://llvm.org/D123681>`_,✅
 Search,lexicographical_compare,Nikolas Klauser,`D127130 <https://llvm.org/D127130>`_,✅
 Search,partition_point,Konstantin Varlamov,`D130070 <https://llvm.org/D130070>`_,✅
 Search,lower_bound,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,upper_bound,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
-Search,equal_range,Christopher Di Bella,n/a,Not started
+Search,equal_range,Hui Xie,`D129796 <https://llvm.org/D129796>`,✅
 Search,binary_search,Nikolas Klauser,`D121964 <https://llvm.org/D121964>`_,✅
 Search,min,Nikolas Klauser,`D119589 <https://llvm.org/D119589>`_,✅
 Search,max,Nikolas Klauser,`D122002 <https://llvm.org/D122002>`_,✅
 Search,minmax,Nikolas Klauser,`D120637 <https://llvm.org/D120637>`_,✅
 Search,min_element,Nikolas Klauser,`D117025 <https://llvm.org/D117025>`_,✅
 Search,max_element,Nikolas Klauser,`D117523 <https://llvm.org/D117523>`_,✅
 Search,minmax_element,Nikolas Klauser,`D120637 <https://llvm.org/D120637>`_,✅
 Search,count,Nikolas Klauser,`D121523 <https://llvm.org/D121523>`_,✅

libcxx/include/__algorithm/equal_range.h

 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/half_positive.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/upper_bound.h>
 #include <__config>
 #include <__functional/identity.h>
+#include <__functional/invoke.h>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
+#include <__type_traits/is_callable.h>
+#include <__type_traits/is_copy_constructible.h>
+#include <__utility/move.h>
 #include <__utility/pair.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _ForwardIterator, class _Tp>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
-__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
-{
-    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
-    difference_type __len = _VSTD::distance(__first, __last);
-    while (__len != 0)
-    {
-        difference_type __l2 = _VSTD::__half_positive(__len);
-        _ForwardIterator __m = __first;
-        _VSTD::advance(__m, __l2);
-        if (__comp(*__m, __value))
-        {
-            __first = ++__m;
-            __len -= __l2 + 1;
-        }
-        else if (__comp(__value, *__m))
-        {
-            __last = __m;
-            __len = __l2;
-        }
-        else
-        {
-            auto __proj = std::__identity();
-            _ForwardIterator __mp1 = __m;
-            return pair<_ForwardIterator, _ForwardIterator>
-                   (
-                      _VSTD::__lower_bound_impl<_ClassicAlgPolicy>(__first, __m, __value, __comp, __proj),
-                      _VSTD::__upper_bound<_Compare>(++__mp1, __last, __value, __comp)
-                   );
-        }
-    }
-    return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
+template <class _AlgPolicy, class _Compare, class _Iter, class _Sent, class _Tp, class _Proj>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_Iter, _Iter>
+__equal_range(_Iter __first, _Sent __last, const _Tp& __value, _Compare&& __comp, _Proj&& __proj) {
+  auto __len  = _IterOps<_AlgPolicy>::distance(__first, __last);
+  _Iter __end = _IterOps<_AlgPolicy>::next(__first, __last);
+  while (__len != 0) {
+    auto __half_len = std::__half_positive(__len);
+    _Iter __mid     = _IterOps<_AlgPolicy>::next(__first, __half_len);
+    if (std::__invoke(__comp, std::__invoke(__proj, *__mid), __value)) {
+      __first = ++__mid;
+      __len -= __half_len + 1;
+    } else if (std::__invoke(__comp, __value, std::__invoke(__proj, *__mid))) {
+      __end = __mid;
+      __len = __half_len;
+    } else {
+      _Iter __mp1 = __mid;
+      return pair<_Iter, _Iter>(
+          std::__lower_bound_impl<_AlgPolicy>(__first, __mid, __value, __comp, __proj),
+          std::__upper_bound<_AlgPolicy>(++__mp1, __end, __value, __comp, __proj));
+  return pair<_Iter, _Iter>(__first, __first);
 }
 
 template <class _ForwardIterator, class _Tp, class _Compare>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-pair<_ForwardIterator, _ForwardIterator>
-equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
-{
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__equal_range<_Comp_ref>(__first, __last, __value, __comp);
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
+equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp) {
+  static_assert(__is_callable<_Compare, decltype(*__first), const _Tp&>::value,
+                "The comparator has to be callable");
+  static_assert(is_copy_constructible<_ForwardIterator>::value,
+                "Iterator has to be copy constructible");
+  return std::__equal_range<_ClassicAlgPolicy>(
+      std::move(__first), std::move(__last), __value, static_cast<_Comp_ref>(__comp), std::__identity());
 }
 
 template <class _ForwardIterator, class _Tp>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-pair<_ForwardIterator, _ForwardIterator>
-equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
-{
-    return _VSTD::equal_range(__first, __last, __value,
-                             __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_ForwardIterator, _ForwardIterator>
+equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+  return std::equal_range(
+      std::move(__first),
+      std::move(__last),
+      __value,
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_EQUAL_RANGE_H

libcxx/include/__algorithm/inplace_merge.h

 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/lower_bound.h>
 #include <__algorithm/min.h>
 #include <__algorithm/move.h>
 #include <__algorithm/rotate.h>
 #include <__algorithm/upper_bound.h>
 #include <__config>
+#include <__functional/identity.h>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
 #include <memory>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
while (true)
         difference_type __len11;      // distance(__first, __m1)
         difference_type __len21;      // distance(__middle, __m2)
         // binary search smaller range
         if (__len1 < __len2)
         {   // __len >= 1, __len2 >= 2
             __len21 = __len2 / 2;
             __m2 = __middle;
             _Ops::advance(__m2, __len21);
-            __m1 = _VSTD::__upper_bound<_Compare>(__first, __middle, *__m2, __comp);
+            // TODO: replace _ClassicAlgPolicy and __identity with _AlgPolicy and projection
+            __m1 = std::__upper_bound<_ClassicAlgPolicy>(__first, __middle, *__m2, __comp, std::__identity());
             __len11 = _Ops::distance(__first, __m1);
         }
         else
         {
             if (__len1 == 1)
             {   // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1
                 // It is known *__first > *__middle
               _Ops::iter_swap(__first, __middle);

libcxx/include/__algorithm/iterator_operations.h

struct _IterOps<_ClassicAlgPolicy> {
   template <class _Iterator>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   _Iterator next(_Iterator, _Iterator __last) {
     return __last;
   }
 
   template <class _Iter>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
-  __uncvref_t<_Iter> next(_Iter&& __it,
+  __uncvref_t<_Iter> next(_Iter&& __it, 
                           typename iterator_traits<__uncvref_t<_Iter> >::difference_type __n = 1){
     return std::next(std::forward<_Iter>(__it), __n);
   }
 
   template <class _Iter>
   _LIBCPP_HIDE_FROM_ABI static _LIBCPP_CONSTEXPR_AFTER_CXX11
   void __advance_to(_Iter& __first, _Iter __last) {
     __first = __last;
   }
 };
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_ITERATOR_OPERATIONS_H

libcxx/include/__algorithm/ranges_equal_range.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_RANGES_EQUAL_RANGE_H
 #define _LIBCPP___ALGORITHM_RANGES_EQUAL_RANGE_H
 
 #include <__algorithm/equal_range.h>
-#include <__algorithm/make_projected.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__functional/ranges_operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/projected.h>
 #include <__ranges/access.h>

 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 namespace __equal_range {
 
 struct __fn {
-
-  template <forward_iterator _Iter, sentinel_for<_Iter> _Sent, class _Tp, class _Proj = identity,
-            indirect_strict_weak_order<const _Tp*, projected<_Iter, _Proj>> _Comp = ranges::less>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  subrange<_Iter> operator()(_Iter __first, _Sent __last, const _Tp& __value, _Comp __comp = {},
-                             _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__first; (void)__last; (void)__value; (void)__comp; (void)__proj;
-    return {};
+  template <
+      forward_iterator _Iter,
+      sentinel_for<_Iter> _Sent,
+      class _Tp,
+      class _Proj                                                           = identity,
+  _LIBCPP_HIDE_FROM_ABI constexpr subrange<_Iter>
+  operator()(_Iter __first, _Sent __last, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+    auto __ret = std::__equal_range<_RangeAlgPolicy>(
+        std::move(__first), std::move(__last), __value, __comp, __proj);
+    return {std::move(__ret.first), std::move(__ret.second)};
   }
 
-  template <forward_range _Range, class _Tp, class _Proj = identity,
-            indirect_strict_weak_order<const _Tp*, projected<iterator_t<_Range>, _Proj>> _Comp = ranges::less>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  borrowed_subrange_t<_Range> operator()(_Range&& __range, const _Tp& __value, _Comp __comp = {},
-                                         _Proj __proj = {}) const {
-    // TODO: implement
-    (void)__range; (void)__value; (void)__comp; (void)__proj;
-    return {};
+  template <
+      forward_range _Range,
+      class _Tp,
+      class _Proj                                                                        = identity,
+  _LIBCPP_HIDE_FROM_ABI constexpr borrowed_subrange_t<_Range>
+  operator()(_Range&& __range, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+    auto __ret = std::__equal_range<_RangeAlgPolicy>(
+        ranges::begin(__range), ranges::end(__range), __value, __comp, __proj);
+    return {std::move(__ret.first), std::move(__ret.second)};
   }
-
 };
 
 } // namespace __equal_range
 
 inline namespace __cpo {
   inline constexpr auto equal_range = __equal_range::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_EQUAL_RANGE_H

libcxx/include/__algorithm/upper_bound.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_UPPER_BOUND_H
 #define _LIBCPP___ALGORITHM_UPPER_BOUND_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/half_positive.h>
+#include <__algorithm/iterator_operations.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
 #include <__iterator/advance.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
+#include <__type_traits/is_copy_constructible.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _ForwardIterator, class _Tp>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
-__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, _Compare __comp)
-{
-    typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type;
-    difference_type __len = _VSTD::distance(__first, __last);
-    while (__len != 0)
-    {
-        difference_type __l2 = _VSTD::__half_positive(__len);
-        _ForwardIterator __m = __first;
-        _VSTD::advance(__m, __l2);
-        if (__comp(__value, *__m))
-            __len = __l2;
-        else
-        {
-            __first = ++__m;
-            __len -= __l2 + 1;
-        }
-    }
-    return __first;
+template <class _AlgPolicy, class _Compare, class _Iter, class _Sent, class _Tp, class _Proj>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _Iter
+__upper_bound(_Iter __first, _Sent __last, const _Tp& __value, _Compare&& __comp, _Proj&& __proj) {
+  auto __len = _IterOps<_AlgPolicy>::distance(__first, __last);
+  while (__len != 0) {
+    auto __half_len = std::__half_positive(__len);
+    auto __mid      = _IterOps<_AlgPolicy>::next(__first, __half_len);
+    if (std::__invoke(__comp, __value, std::__invoke(__proj, *__mid)))
+      __len = __half_len;
+    else {
+      __first = ++__mid;
+      __len -= __half_len + 1;
 }
 
 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)
-{
-    return _VSTD::__upper_bound<_Compare&>(__first, __last, __value, __comp);
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _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");
+  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_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-_ForwardIterator
-upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
-{
-    return _VSTD::upper_bound(__first, __last, __value,
-                             __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 _ForwardIterator
+upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+  return std::upper_bound(
+      std::move(__first),
+      std::move(__last),
+      __value,
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_UPPER_BOUND_H

libcxx/include/algorithm

template<input_range R1, input_range R2, class Pred = ranges::equal_to,
   
   template<input_range R1, input_range R2, weakly_incrementable O,
            class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
     requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
     constexpr set_symmetric_difference_result<borrowed_iterator_t<R1>,
                                                       borrowed_iterator_t<R2>, O>
       set_symmetric_difference(R1&& r1, R2&& r2, O result, Comp comp = {},
                                Proj1 proj1 = {}, Proj2 proj2 = {});                                 // since C++20
-  
+  template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
+           indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
+    constexpr subrange<I>
+      equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});                 // since C++20
+  
+  template<forward_range R, class T, class Proj = identity,
+           indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
+             ranges::less>
+    constexpr borrowed_subrange_t<R>
+      equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});                           // since C++20
+  
   template<class I1, class I2, class O>
     using set_union_result = in_in_out_result<I1, I2, O>;                                           // since C++20
 
   template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
            weakly_incrementable O, class Comp = ranges::less,
            class Proj1 = identity, class Proj2 = identity>
     requires mergeable<I1, I2, O, Comp, Proj1, Proj2>
     constexpr set_union_result<I1, I2, O>

 #include <__algorithm/ranges_binary_search.h>
 #include <__algorithm/ranges_copy.h>
 #include <__algorithm/ranges_copy_backward.h>
 #include <__algorithm/ranges_copy_if.h>
 #include <__algorithm/ranges_copy_n.h>
 #include <__algorithm/ranges_count.h>
 #include <__algorithm/ranges_count_if.h>
 #include <__algorithm/ranges_equal.h>
+#include <__algorithm/ranges_equal_range.h>
 #include <__algorithm/ranges_fill.h>
 #include <__algorithm/ranges_fill_n.h>
 #include <__algorithm/ranges_find.h>
 #include <__algorithm/ranges_find_end.h>
 #include <__algorithm/ranges_find_first_of.h>
 #include <__algorithm/ranges_find_if.h>
 #include <__algorithm/ranges_find_if_not.h>
 #include <__algorithm/ranges_for_each.h>

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

constexpr bool all_the_algorithms()
     (void)std::ranges::count_if(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0);
 #if TEST_STD_VER > 20
     //(void)std::ranges::ends_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
 #endif
     (void)std::ranges::equal(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::equal(a, b, Equal(&copies)); assert(copies == 0);
-    //(void)std::ranges::equal_range(first, last, value, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::equal_range(a, value, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::equal_range(first, last, value, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::equal_range(a, value, Less(&copies)); assert(copies == 0);
     (void)std::ranges::find_end(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::find_end(a, b, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::find_first_of(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::find_first_of(a, b, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::find_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::find_if(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::find_if_not(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::find_if_not(a, UnaryTrue(&copies)); assert(copies == 0);

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

constexpr bool all_the_algorithms()
     (void)std::ranges::count_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::copy_if(first, last, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::copy_if(a, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
 #if TEST_STD_VER > 20
     //(void)std::ranges::ends_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
 #endif
     (void)std::ranges::equal(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::equal(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::equal_range(first, last, value, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::equal_range(a, value, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::equal_range(first, last, value, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::equal_range(a, value, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find(first, last, value, Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find(a, value, Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_end(first, last, first2, mid2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_end(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_first_of(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_first_of(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/equal.range/ranges_equal_range.pass.cpp

 #include <algorithm>
 #include <array>
 #include <concepts>
 #include <functional>
 #include <ranges>
 
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
+#include "../../sortable_helpers.h"
 
-// TODO: SFINAE tests.
+struct Foo {};
+
+template <class Iter, class Sent, class T, class Proj = std::identity, class Comp = std::ranges::less>
+concept HasEqualRangeIter =
+    requires(Iter&& iter, Sent&& sent, const T& value, Comp&& comp, Proj&& proj) {
+      std::ranges::equal_range(
+          std::forward<Iter>(iter),
+          std::forward<Sent>(sent),
+          value,
+          std::forward<Comp>(comp),
+          std::forward<Proj>(proj));
+    };
+
+static_assert(HasEqualRangeIter<int*, int*, int>);
+
+// !forward_iterator<I>
+static_assert(!HasEqualRangeIter<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>, int>);
+
+// !sentinel_for<S, I>
+static_assert(!HasEqualRangeIter<int*, SentinelForNotSemiregular, int>);
+
+// !indirect_strict_weak_order<Comp, const T*, projected<I, Proj>>
+static_assert(!HasEqualRangeIter<int*, int*, Foo>);
+
+template <class R, class T, class Proj = std::identity, class Comp = std::ranges::less>
+concept HasEqualRangeForRange =
+    requires(R&& r, const T& value, Comp&& comp, Proj&& proj) {
+      std::ranges::equal_range(std::forward<R>(r), value, comp, proj);
+    };
+
+template <class T>
+using R = UncheckedRange<T>;
+
+static_assert(HasEqualRangeForRange<R<int*>, int>);
+
+// !forward_range<R>
+static_assert(!HasEqualRangeForRange<R<cpp20_input_iterator<int*>>, int>);
+
+// !indirect_strict_weak_order<Comp, const T*, projected<ranges::iterator_t<R>, Proj>>
+static_assert(!HasEqualRangeForRange<R<int*>, Foo>);
+
+template <class InIter, std::size_t N>
+constexpr void testEqualRangeImpl(std::array<int, N>& in, int value, std::ranges::subrange<int*> expected) {
+  using Sent = sentinel_wrapper<InIter>;
+
+  // iterator overload
+  {
+    std::same_as<std::ranges::subrange<InIter, InIter>> decltype(auto) result =
+        std::ranges::equal_range(InIter{in.data()}, Sent{InIter{in.data() + in.size()}}, value);
+
+    assert(base(result.begin()) == expected.begin());
+    assert(base(result.end()) == expected.end());
+  }
+
+  // range overload
+  {
+    std::ranges::subrange r{InIter{in.data()}, Sent{InIter{in.data() + in.size()}}};
+    std::same_as<std::ranges::subrange<InIter, InIter>> decltype(auto) result = std::ranges::equal_range(r, value);
+
+    assert(base(result.begin()) == expected.begin());
+    assert(base(result.end()) == expected.end());
+  }
+}
+
+template <class InIter>
+constexpr void testImpl() {
+  // no match and the searched value would be in the middle
+  {
+    std::array in{0, 1, 5, 6, 9, 10};
+    int value = 7;
+    std::ranges::subrange<int*> expected{in.data() + 4, in.data() + 4};
+    testEqualRangeImpl<InIter>(in, value, expected);
+  }
+
+  // value smaller than all the elements
+  {
+    std::array in{0, 1, 5, 6, 9, 10};
+    int value = -1;
+    std::ranges::subrange<int*> expected{in.data(), in.data()};
+    testEqualRangeImpl<InIter>(in, value, expected);
+  }
+
+  // value bigger than all the elements
+  {
+    std::array in{0, 1, 5, 6, 9, 10};
+    int value = 20;
+    std::ranges::subrange<int*> expected{in.data() + in.size(), in.data() + in.size()};
+    testEqualRangeImpl<InIter>(in, value, expected);
+  }
+
+  // exactly one match
+  {
+    std::array in{0, 1, 5, 6, 9, 10};
+    int value = 5;
+    std::ranges::subrange<int*> expected{in.data() + 2, in.data() + 3};
+    testEqualRangeImpl<InIter>(in, value, expected);
+  }
+
+  // multiple matches
+  {
+    std::array in{0, 1, 5, 6, 6, 6, 9, 10};
+    int value = 6;
+    std::ranges::subrange<int*> expected{in.data() + 3, in.data() + 6};
+    testEqualRangeImpl<InIter>(in, value, expected);
+  }
+
+  // all matches
+  {
+    std::array in{6, 6, 6, 6, 6};
+    int value = 6;
+    std::ranges::subrange<int*> expected{in.data(), in.data() + in.size()};
+    testEqualRangeImpl<InIter>(in, value, expected);
+  }
+
+  // empty range
+  {
+    std::array<int, 0> in{};
+    int value = 6;
+    std::ranges::subrange<int*> expected{in.data(), in.data()};
+    testEqualRangeImpl<InIter>(in, value, expected);
+  }
+
+  // partially sorted
+  {
+    std::array in{3, 1, 5, 2, 6, 6, 10, 7, 8};
+    int value = 6;
+    std::ranges::subrange<int*> expected{in.data() + 4, in.data() + 6};
+    testEqualRangeImpl<InIter>(in, value, expected);
+  }
+}
 
 constexpr bool test() {
-  // TODO: main tests.
-  // TODO: A custom comparator works.
-  // TODO: A custom projection works.
+  testImpl<forward_iterator<int*>>();
+  testImpl<bidirectional_iterator<int*>>();
+  testImpl<random_access_iterator<int*>>();
+  testImpl<contiguous_iterator<int*>>();
+
+  struct Data {
+    int data;
+  };
+
+  // Test custom comparator
+  {
+    std::array<Data, 10> in{{{2}, {1}, {3}, {3}, {3}, {10}, {9}, {5}, {5}, {7}}};
+    Data value{3};
+
+    const auto comp = [](const Data& x, const Data& y) { return x.data < y.data; };
+    // iterator overload
+    {
+      auto result = std::ranges::equal_range(in.begin(), in.end(), value, comp);
 
+      assert(result.begin() == in.begin() + 2);
+      assert(result.end() == in.begin() + 5);
+    }
+
+    // range overload
+    {
+      auto result = std::ranges::equal_range(in, value, comp);
+
+      assert(result.begin() == in.begin() + 2);
+      assert(result.end() == in.begin() + 5);
+    }
+  }
+
+  // Test custom projection
+  {
+    std::array<Data, 10> in{{{2}, {1}, {3}, {3}, {3}, {10}, {9}, {5}, {5}, {7}}};
+    int value = 3;
+
+    const auto proj = [](const Data& d) { return d.data; };
+    // iterator overload
+    {
+      auto result = std::ranges::equal_range(in.begin(), in.end(), value, {}, proj);
+
+      assert(result.begin() == in.begin() + 2);
+      assert(result.end() == in.begin() + 5);
+    }
+
+    // range overload
+    {
+      auto result = std::ranges::equal_range(in, value, {}, proj);
+
+      assert(result.begin() == in.begin() + 2);
+      assert(result.end() == in.begin() + 5);
+    }
+  }
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp

constexpr bool test_all() {
   test(std::ranges::find_first_of, in, in2, binary_pred);
   test(std::ranges::adjacent_find, in, binary_pred);
   test(std::ranges::mismatch, in, in2, binary_pred);
   test(std::ranges::equal, in, in2, binary_pred);
   test(std::ranges::lexicographical_compare, in, in2, binary_pred);
   test(std::ranges::partition_point, in, unary_pred);
   test(std::ranges::lower_bound, in, x, binary_pred);
   test(std::ranges::upper_bound, in, x, binary_pred);
-  //test(std::ranges::equal_range, in, x, binary_pred);
+  test(std::ranges::equal_range, in, x, binary_pred);
   test(std::ranges::binary_search, in, x, binary_pred);
 
   // min
   std::ranges::min(1, 2, binary_pred);
   std::ranges::min(std::initializer_list<int>{1, 2}, binary_pred);
   std::ranges::min(in, binary_pred);
   // max
   std::ranges::max(1, 2, binary_pred);

libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp

constexpr bool test_all() {
   test(std::ranges::find_first_of, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::adjacent_find, in, &Foo::binary_pred, &Bar::val);
   test(std::ranges::mismatch, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::equal, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::lexicographical_compare, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::partition_point, in, &Foo::unary_pred, &Bar::val);
   test(std::ranges::lower_bound, in, x, &Foo::binary_pred, &Bar::val);
   test(std::ranges::upper_bound, in, x, &Foo::binary_pred, &Bar::val);
-  //test(std::ranges::equal_range, in, x, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::equal_range, in, x, &Foo::binary_pred, &Bar::val);
   test(std::ranges::binary_search, in, x, &Foo::binary_pred, &Bar::val);
 
   // min
   std::ranges::min(a, b, &Foo::binary_pred, &Bar::val);
   std::ranges::min(std::initializer_list<Bar>{a, b}, &Foo::binary_pred, &Bar::val);
   std::ranges::min(in, &Foo::binary_pred, &Bar::val);
   // max
   std::ranges::max(a, b, &Foo::binary_pred, &Bar::val);

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 static_assert(test(std::ranges::copy, a, a));
 static_assert(test(std::ranges::copy_backward, a, a));
 static_assert(test(std::ranges::copy_if, a, a, odd));
 static_assert(test(std::ranges::copy_n, a, 10, a));
 static_assert(test(std::ranges::count, a, 42));
 static_assert(test(std::ranges::count_if, a, odd));
 //static_assert(test(std::ranges::ends_with, a, a));
 static_assert(test(std::ranges::equal, a, a));
-//static_assert(test(std::ranges::equal_range, a, 42));
+static_assert(test(std::ranges::equal_range, a, 42));
 static_assert(test(std::ranges::fill, a, 42));
 static_assert(test(std::ranges::fill_n, a, 10, 42));
 static_assert(test(std::ranges::find, a, 42));
 static_assert(test(std::ranges::find_end, a, a));
 //static_assert(test(std::ranges::find_first_of, a, a));
 static_assert(test(std::ranges::find_if, a, odd));
 static_assert(test(std::ranges::find_if_not, a, odd));
 static_assert(test(std::ranges::for_each, a, odd));