[libcxx][algorithms] adds ranges::lower_bound and ranges::upper_bound

[cjdb]

Summary

Implements part of http://wg21.link/p0896.
Implements [lower.bound] and [upper.bound].

Depends on D105794.

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[tcanens]

libcxx/include/__algorithm/lower_bound.h

95

indirect_strict_weak_order doesn't guarantee that the projected element is comparable after it's been turned into a const lvalue.

boolean-testable doesn't guarantee that it can be copied or moved.

[cjdb]

libcxx/include/__algorithm/lower_bound.h

95

indirect_strict_weak_order doesn't guarantee that the projected element is comparable after it's been turned into a const lvalue.

If this were your only comment, I'd change it to this.

auto __pred = [&__value, &__comp]<class _ProjElem>(_ProjElem&& __proj_elem) {
  return _VSTD::invoke(__comp, _VSTD::forward<_ProjElem>(__proj_elem), __value);
};

boolean-testable doesn't guarantee that it can be copied or moved.

This gives me pause. Can I rely on perfect forwarding to do the right thing here?

[tcanens]

libcxx/include/__algorithm/lower_bound.h

95

boolean-testable doesn't guarantee that it can be copied or moved.

This gives me pause. Can I rely on perfect forwarding to do the right thing here?

You can just have __pred explicitly return bool and let the implicit conversion handle it. There's no real reason to forward the result all the way through.

[cjdb]

rebases to activate CI

[zoecarver]

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp

34

libcxx_log2? Why can't we use std::log2?

42

Nit: space.

[cjdb]

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp

34

std::log2 isn't constexpr :(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((

[ldionne]

I think it would be fine to have a couple of test cases that use the complexity_xxx machinery, but it shouldn't be *all* the test cases. It increases the complexity of understanding the test cases and also we end up only testing with the complexity_invocable, not the actual predicates.

libcxx/include/__algorithm/lower_bound.h

101

We definitely want to enable this check only when the user requests a stronger level of debugging. It should be possible to enable _LIBCPP_ASSERT without violating any complexity guarantee, such that one could in theory enable _LIBCPP_ASSERT in the released version of an application. Those expensive checks should be enabled only when a proper debug mode is requested.

However, things are a bit of a mess and we already can't do that today with _LIBCPP_ASSERT, so I won't hold you to that here. You can leave as-is, I just wanted to mention it so it's known that we should eventually go back and decide which checks are to be enabled in "debug" mode and which ones when "minimal assertions" are enabled.

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp

84

Here and elsewhere, please make sure you assign the result of lower_bound to a variable with a proper type. In the tests, it's useful to pin down the type of things to test that we return the right types (whereas I would agree in normal code auto improves readability).

153

Just it?

[miscco]

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp

84

Actually that would be a bit harmfull due to implicit conversions.

You should assign to auto and then check the type of the variable via a static assert.

With concepts you could also do a same_as<expected_type> auto it = ...

[• Quuxplusone]

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp

64

Maybe this is redundant with a point @ldionne has already made re complexity_foo; but it's important that we test some of these algorithms with predicates that are not std::reference_wrapper.

84

"A bit harmful" is overstating the case (since that's libc++ style everywhere). But in any test that already requires C++20 Concepts support, I agree:

std::same_as<decltype(input.begin())> auto it = ranges::lower_bound(input.begin(), input.end(), ...);

would be a pretty neat way to encode the assertion into the test. Let's do that (in tests that already require Concepts, at least).

libcxx/benchmarks/ranges_algorithms.bench.cpp

+#include <algorithm>
+#include <numeric>
+#include <random>
+#include <vector>
+
+#include "benchmark/benchmark.h"
+
+namespace {
+  constexpr std::size_t size = 1'000'000'000;
+  std::vector<int> const ints = []{
+    auto ints = std::vector<int>(size);
+    std::iota(ints.begin(), ints.end(), 0);
+    return ints;
+  }();
+  int const sample = []{
+    auto generator = std::mt19937_64(std::random_device()());
+    auto distribution = std::uniform_int_distribution(0, static_cast<int>(size));
+    return distribution(generator);
+  }();
+
+  void std_lower_bound(benchmark::State& state) {
+    for (auto _ : state) {
+      auto result = std::lower_bound(ints.begin(), ints.end(), sample);
+      benchmark::DoNotOptimize(result);
+    }
+  }
+
+  void ranges_lower_bound(benchmark::State& state) {
+    for (auto _ : state) {
+      auto result = std::lower_bound(ints.begin(), ints.end(), sample);
+      benchmark::DoNotOptimize(result);
+    }
+  }
+}
+
+BENCHMARK(std_lower_bound);
+BENCHMARK(ranges_lower_bound);
+BENCHMARK_MAIN();

libcxx/include/__algorithm/lower_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_LOWER_BOUND_H
 #define _LIBCPP___ALGORITHM_LOWER_BOUND_H
 
-#include <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/half_positive.h>
-#include <iterator>
+#include <__algorithm/is_partitioned.h>
+#include <__algorithm/partition_point.h>
+#include <__config>
+#include <__debug>
+#include <__function_like.h>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/reference_wrapper.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/advance.h>
+#include <__iterator/distance.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.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_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _ForwardIterator
 lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
 {
     return _VSTD::lower_bound(__first, __last, __value_,
                              __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
 }
 
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace ranges {
+  struct __lower_bound_fn final : __function_like {
+    constexpr explicit __lower_bound_fn(__tag __x) noexcept : __function_like(__x) {}
+
+    template<forward_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, class _Proj = identity,
+             indirect_strict_weak_order<const _Tp*, projected<_Ip, _Proj>> _Comp = ranges::less>
+    _LIBCPP_NODISCARD_EXT constexpr
+    _Ip operator()(_Ip __first, _Sp __last, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+      auto __pred = [&__value, &__comp](const auto& __proj_elem){
+        return _VSTD::invoke(__comp, __proj_elem, __value);
+      };
+      // This assertion breaks the logarithmic complexity requirement, but since it is only evaluated
+      // when a user opts into a debug level, the non-conformance is deemed acceptable, since it is
+      // useful for catching violated precondition bugs.
+      _LIBCPP_ASSERT(ranges::is_partitioned(__first, __last, _VSTD::ref(__pred), _VSTD::ref(__proj)),
+                     "lower_bound precondition:\n"
+                     "\tthe projected elements of the range [`first`, `last`) are partitioned with respect to "
+                     "`comp(*proj_elem, value)`.");
+      return ranges::partition_point(_VSTD::move(__first), _VSTD::move(__last), _VSTD::move(__pred), _VSTD::ref(__proj));
+    }
+
+    template<forward_range _Rp, class _Tp, class _Proj = identity,
+             indirect_strict_weak_order<const _Tp*, projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less>
+    _LIBCPP_NODISCARD_EXT constexpr
+    borrowed_iterator_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+      return (*this)(ranges::begin(__r), ranges::end(__r), __value, _VSTD::ref(__comp), _VSTD::ref(__proj));
+    }
+  };
+
+  inline constexpr auto lower_bound = __lower_bound_fn(__function_like::__tag());
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_LOWER_BOUND_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 <__config>
 #include <__algorithm/comp.h>
 #include <__algorithm/half_positive.h>
-#include <iterator>
+#include <__algorithm/is_partitioned.h>
+#include <__algorithm/partition_point.h>
+#include <__config>
+#include <__debug>
+#include <__function_like.h>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/reference_wrapper.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/advance.h>
+#include <__iterator/distance.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.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_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>());
 }
 
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace ranges {
+  struct __upper_bound_fn final : __function_like {
+    constexpr explicit __upper_bound_fn(__tag __x) noexcept : __function_like(__x) {}
+
+    template<forward_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, class _Proj = identity,
+             indirect_strict_weak_order<const _Tp*, projected<_Ip, _Proj>> _Comp = ranges::less>
+    _LIBCPP_NODISCARD_EXT constexpr
+    _Ip operator()(_Ip __first, _Sp __last, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+      auto __pred = [&__value, &__comp](const auto& __proj_elem){
+        return !_VSTD::invoke(__comp, __value, __proj_elem);
+      };
+      // This assertion breaks the logarithmic complexity requirement, but since it is only evaluated
+      // when a user opts into a debug level, the non-conformance is deemed acceptable, since it is
+      // useful for catching violated precondition bugs.
+      _LIBCPP_ASSERT(ranges::is_partitioned(__first, __last, _VSTD::ref(__pred), _VSTD::ref(__proj)),
+                     "upper_bound precondition:\n"
+                     "\tthe projected elements of the range [`first`, `last`) are partitioned with respect to "
+                     "`not comp(value, *proj_elem)`.");
+      return ranges::partition_point(_VSTD::move(__first), _VSTD::move(__last), _VSTD::move(__pred), _VSTD::ref(__proj));
+    }
+
+    template<forward_range _Rp, class _Tp, class _Proj = identity,
+             indirect_strict_weak_order<const _Tp*, projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less>
+    _LIBCPP_NODISCARD_EXT constexpr
+    borrowed_iterator_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Comp __comp = {}, _Proj __proj = {}) const {
+      return (*this)(ranges::begin(__r), ranges::end(__r), __value, _VSTD::ref(__comp), _VSTD::ref(__proj));
+    }
+  };
+
+  inline constexpr auto upper_bound = __upper_bound_fn(__function_like::__tag());
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_UPPER_BOUND_H

libcxx/include/algorithm

 template <class ForwardIterator, class T>
     constexpr ForwardIterator                         // constexpr in C++20
     lower_bound(ForwardIterator first, ForwardIterator last, const T& value);
 
 template <class ForwardIterator, class T, class Compare>
     constexpr ForwardIterator                         // constexpr in C++20
     lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
 
+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 I ranges::lower_bound(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_iterator_t<R>
+    ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
+
 template <class ForwardIterator, class T>
     constexpr ForwardIterator                         // constexpr in C++20
     upper_bound(ForwardIterator first, ForwardIterator last, const T& value);
 
 template <class ForwardIterator, class T, class Compare>
     constexpr ForwardIterator                         // constexpr in C++20
     upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
 
+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 I ranges::upper_bound(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_iterator_t<R>
+    ranges::upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
+
 template <class ForwardIterator, class T>
     constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++20
     equal_range(ForwardIterator first, ForwardIterator last, const T& value);
 
 template <class ForwardIterator, class T, class Compare>
     constexpr pair<ForwardIterator, ForwardIterator>  // constexpr in C++20
     equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);
 

libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp

int main(int, char**) {
   ranges::find_if_not(arr, [](auto) { return true; });
 
   ranges::is_partitioned(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
   ranges::is_partitioned(arr, [](auto) { return true; });
 
   ranges::partition_point(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
   ranges::partition_point(arr, [](auto) { return true; });
 
+  ranges::lower_bound(arr.begin(), arr.end(), 0);
+  ranges::lower_bound(arr, 0);
+
+  ranges::upper_bound(arr.begin(), arr.end(), 0);
+  ranges::upper_bound(arr, 0);
+
   return 0;
 }

libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp

int main()
   // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
   ranges::is_partitioned(arr, [](auto) { return true; });
 
   // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
   ranges::partition_point(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
 
   // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
   ranges::partition_point(arr, [](auto) { return true; });
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::lower_bound(arr.begin(), arr.end(), 0);
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::lower_bound(arr, 0);
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::upper_bound(arr.begin(), arr.end(), 0);
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::upper_bound(arr, 0);
 }

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/ranges_lower_bound.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// ranges::lower_bound
+
+#include <algorithm>
+
+#include <array>
+#include <cassert>
+#include <cmath>
+#include <functional>
+#include <ranges>
+#include <vector>
+
+#include "test_algorithm.h"
+#include "test_iterators.h"
+#include "test_macros.h"
+
+namespace ranges = std::ranges;
+
+template<std::ranges::range R>
+constexpr void check_complexity(R&& r, std::ptrdiff_t const count)
+{
+  auto const complexity = static_cast<std::ptrdiff_t>(libcxx_log2(ranges::ssize(r))) + 1;
+  // We halve the complexity so that each test case can check both `alg(first, last)` and `alg(r)`
+  // in the same lambda.
+  assert((count / 2) <= complexity);
+}
+
+template<template<class...> class I, class T>
+constexpr bool check_lower_bound() {
+
+  auto no_duplicates = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+
+  auto successor = [](T const x) { return x + 1; };
+
+  test_algorithm<I>(no_duplicates, [](auto& input) {
+    assert(ranges::lower_bound(input.begin(), input.end(), static_cast<T>(0)) == input.begin());
+    assert(ranges::lower_bound(input, static_cast<T>(0)) == input.begin());
+  });
+  test_algorithm<I>(no_duplicates, [](auto& input) {
+    auto iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast<T>(5));
+    assert(iterator_result == ranges::next(input.begin(), 5));
+    assert(ranges::lower_bound(input, static_cast<T>(5)) == iterator_result);
+  });
+  test_algorithm<I>(no_duplicates, [](auto& input) {
+    assert(ranges::lower_bound(input.begin(), input.end(), static_cast<T>(-10)) == input.begin());
+    assert(ranges::lower_bound(input, static_cast<T>(-10)) == input.begin());
+  });
+  test_algorithm<I>(no_duplicates, [](auto& input) {
+    assert(ranges::lower_bound(input.begin(), input.end(), static_cast<T>(100)) == input.end());
+    assert(ranges::lower_bound(input, static_cast<T>(100)) == input.end());
+  });
+  test_algorithm<I>(no_duplicates, ranges::greater(), [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    assert(ranges::lower_bound(input.begin(), input.end(), static_cast<T>(5), comp_ref) == input.begin());
+    assert(ranges::lower_bound(input, static_cast<T>(5), comp_ref) == input.begin());
+  });
+  test_algorithm<I>(no_duplicates, ranges::greater(), [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    assert(ranges::lower_bound(input.begin(), input.end(), static_cast<T>(-5), comp_ref) == input.end());
+    assert(ranges::lower_bound(input, static_cast<T>(-5), comp_ref) == input.end());
+  });
+  test_algorithm<I>(no_duplicates, ranges::less(), successor, [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+
+    auto iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast<T>(2), comp_ref, proj_ref);
+    assert(iterator_result == ranges::next(input.begin(), 1));
+    assert(ranges::lower_bound(input, static_cast<T>(2), comp_ref, proj_ref) == iterator_result);
+  });
+  test_algorithm<I>(no_duplicates, ranges::greater(), std::negate(), [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+    auto iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast<T>(-5), comp_ref, proj_ref);
+    assert(iterator_result == ranges::next(input.begin(), 5));
+    assert(ranges::lower_bound(input, static_cast<T>(-5), comp_ref, proj_ref) == iterator_result);
+  });
+
+  // Check duplicates by arranging ints into equivalence classes. To further ensure the integrity of
+  // `lower_bound`, we'll shuffle two of the equivalence classes, so that they're not sorted.
+  // The final equivalence class is omitted so that we can add tests using the pre-defined `successor`
+  // projection.
+  auto mod4_equivalence_classes = std::array{0, 4, 8, 16, 73, 13, 22, 110, 70};
+
+  // Check that we really do have equivalence classes and that 2/3 of them aren't sorted.
+  assert(ranges::is_partitioned(mod4_equivalence_classes.begin(), mod4_equivalence_classes.end(),
+                                [](int const x) { return x % 4 == 0; }));
+  assert(std::is_sorted(mod4_equivalence_classes.begin(), mod4_equivalence_classes.begin() + 4));
+
+  assert(ranges::is_partitioned(mod4_equivalence_classes.begin() + 4, mod4_equivalence_classes.end(),
+                                [](int const x) { return x % 4 == 1; }));
+  assert(!std::is_sorted(mod4_equivalence_classes.begin() + 4, mod4_equivalence_classes.begin() + 6));
+
+  assert(ranges::is_partitioned(mod4_equivalence_classes.begin() + 6, mod4_equivalence_classes.end(),
+                                [](int const x) { return x % 4 == 2; }));
+  assert(!std::is_sorted(mod4_equivalence_classes.begin() + 6, mod4_equivalence_classes.end()));
+
+  auto strict_weak_order = [](auto const x, auto const y) {
+    return (static_cast<int>(x) % 4) < (static_cast<int>(y) % 4);
+  };
+
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    assert(ranges::lower_bound(input.begin(), input.end(), static_cast<T>(0), comp_ref) == input.begin());
+    assert(ranges::lower_bound(input, static_cast<T>(0), comp_ref) == input.begin());
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    auto const iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast<T>(1), comp_ref);
+    assert(iterator_result == ranges::next(input.begin(), 4));
+    assert(ranges::lower_bound(input, static_cast<T>(1), comp_ref) == iterator_result);
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    auto const iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast<T>(2), comp_ref);
+    assert(iterator_result == ranges::next(input.begin(), 6));
+    assert(ranges::lower_bound(input, static_cast<T>(2), comp_ref) == iterator_result);
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    assert(ranges::lower_bound(input.begin(), input.end(), static_cast<T>(3), comp_ref) == input.end());
+    assert(ranges::lower_bound(input, static_cast<T>(3), comp_ref) == input.end());
+  });
+
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+    assert(ranges::lower_bound(input.begin(), input.end(), static_cast<T>(0), comp_ref, proj_ref) == input.begin());
+    assert(ranges::lower_bound(input, static_cast<T>(0), comp_ref, proj_ref) == input.begin());
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+
+    auto const iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast<T>(1), comp_ref, proj_ref);
+    assert(iterator_result == input.begin());
+    assert(ranges::lower_bound(input, static_cast<T>(1), comp_ref, proj_ref) == iterator_result);
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+
+    auto const iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast<T>(2), comp_ref, proj_ref);
+    assert(iterator_result == ranges::next(input.begin(), 4));
+    assert(ranges::lower_bound(input, static_cast<T>(2), comp_ref, proj_ref) == iterator_result);
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+
+    auto const iterator_result = ranges::lower_bound(input.begin(), input.end(), static_cast<T>(3), comp_ref, proj_ref);
+    assert(iterator_result == ranges::next(input.begin(), 6));
+    assert(ranges::lower_bound(input, static_cast<T>(3), comp_ref, proj_ref) == iterator_result);
+  });
+
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(check_lower_bound<forward_iterator, int>());
+  static_assert(check_lower_bound<forward_iterator, double>());
+  check_lower_bound<forward_iterator, int>();
+  check_lower_bound<forward_iterator, double>();
+
+  static_assert(check_lower_bound<bidirectional_iterator, int>());
+  static_assert(check_lower_bound<bidirectional_iterator, double>());
+  check_lower_bound<bidirectional_iterator, int>();
+  check_lower_bound<bidirectional_iterator, double>();
+
+  static_assert(check_lower_bound<random_access_iterator, int>());
+  static_assert(check_lower_bound<random_access_iterator, double>());
+  check_lower_bound<random_access_iterator, int>();
+  check_lower_bound<random_access_iterator, double>();
+
+  static_assert(check_lower_bound<contiguous_iterator, int>());
+  static_assert(check_lower_bound<contiguous_iterator, double>());
+  check_lower_bound<contiguous_iterator, int>();
+  check_lower_bound<contiguous_iterator, double>();
+
+  ASSERT_SAME_TYPE(decltype(ranges::lower_bound(std::vector<int>(10), 0)),
+                   ranges::dangling);
+  ASSERT_SAME_TYPE(decltype(ranges::lower_bound(std::vector<int>(10), 0, {})),
+                   ranges::dangling);
+  ASSERT_SAME_TYPE(decltype(ranges::lower_bound(std::vector<int>(10), 0, {}, {})),
+                   ranges::dangling);
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/lower.bound/ranges_lower_bound/special_function.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// ranges::lower_bound
+
+#include <algorithm>
+
+#include <array>
+#include <iterator>
+#include <ranges>
+#include <utility>
+
+#include "test_range.h"
+#include "test_standard_function.h"
+
+static_assert(is_function_like<decltype(std::ranges::lower_bound)>());
+
+namespace ranges = std::ranges;
+
+namespace std::ranges {
+  template<class T>
+  class basic_istream_view {
+    struct iterator;
+  public:
+    iterator begin();
+    default_sentinel_t end() const;
+  };
+} // namespace std::ranges
+
+auto f = [](auto, auto) { return true; };
+
+// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent
+// name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for
+// the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup.
+template <class T>
+constexpr bool no_unqualified_lookup() {
+  auto identity = ranges::basic_istream_view<T>();
+  static_assert(!requires(T const value) { lower_bound(ranges::begin(identity), ranges::end(identity), value, f); });
+  static_assert(!requires(T const value) { lower_bound(ranges::begin(identity), ranges::end(identity), value, f, &T::first); });
+  static_assert(!requires(T const value) { lower_bound(identity, value, f); });
+  static_assert(!requires(T const value) { lower_bound(identity, value, f, &T::first); });
+  return true;
+};
+
+static_assert(no_unqualified_lookup<std::pair<int, int>>());
+
+namespace test {
+template <class>
+struct iterator {
+  using value_type = std::pair<int, int>;
+  using difference_type = std::ptrdiff_t;
+  using iterator_category = std::forward_iterator_tag;
+
+  iterator() = default;
+
+  value_type operator*() const;
+  iterator& operator++();
+  iterator operator++(int);
+
+  bool operator==(iterator const&) const = default;
+};
+
+template<class>
+struct range {
+  std::pair<int, int> const* begin() const;
+  std::pair<int, int> const* end() const;
+};
+
+template <class I>
+void lower_bound(iterator<I>, iterator<I>, auto, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I>
+void lower_bound(iterator<I>, iterator<I>, auto, auto, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class R>
+void lower_bound(R&&, auto, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+
+template <class R>
+void lower_bound(R&&, auto, auto, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+} // namespace test
+
+// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a
+// function call ([expr.call]), they inhibit argument-dependent name lookup.
+void adl_inhibition() {
+  using std::ranges::lower_bound;
+
+  test::iterator<std::pair<int, int>*> x;
+  std::pair<int, int> value;
+  (void)lower_bound(x, x, value, f);
+  (void)lower_bound(x, x, value, f, &std::pair<int, int>::first);
+
+  test::range<int*> r;
+  (void)lower_bound(r, value, f);
+  (void)lower_bound(r, value, f, &std::pair<int, int>::first);
+}

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges_upper_bound/ranges_upper_bound.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// ranges::upper_bound
+
+#include <algorithm>
+
+#include <array>
+#include <cassert>
+#include <cmath>
+#include <functional>
+#include <ranges>
+#include <vector>
+
+#include "test_algorithm.h"
+#include "test_iterators.h"
+#include "test_macros.h"
+
+namespace ranges = std::ranges;
+
+template<std::ranges::range R>
+constexpr void check_complexity(R&& r, std::ptrdiff_t const count)
+{
+  auto const complexity = static_cast<std::ptrdiff_t>(libcxx_log2(ranges::ssize(r))) + 1;
+  // We halve the complexity so that each test case can check both `alg(first, last)` and `alg(r)`
+  // in the same lambda.
+  assert((count / 2) <= complexity);
+}
+
+template<template<class...> class I, class T>
+constexpr bool check_upper_bound() {
+
+  auto no_duplicates = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+
+  auto successor = [](T const x) { return x + 1; };
+
+  test_algorithm<I>(no_duplicates, [](auto& input) {
+    assert(ranges::upper_bound(input.begin(), input.end(), static_cast<T>(0)) == ranges::next(input.begin()));
+    assert(ranges::upper_bound(input, static_cast<T>(0)) == ranges::next(input.begin()));
+  });
+  test_algorithm<I>(no_duplicates, [](auto& input) {
+    auto result = ranges::upper_bound(input.begin(), input.end(), static_cast<T>(5));
+    assert(result == ranges::next(input.begin(), 6));
+    assert(ranges::upper_bound(input, static_cast<T>(5)) == result);
+  });
+  test_algorithm<I>(no_duplicates, [](auto& input) {
+    assert(ranges::upper_bound(input.begin(), input.end(), static_cast<T>(-10)) == input.begin());
+    assert(ranges::upper_bound(input, static_cast<T>(-10)) == input.begin());
+  });
+  test_algorithm<I>(no_duplicates, [](auto& input) {
+    assert(ranges::upper_bound(input.begin(), input.end(), static_cast<T>(100)) == input.end());
+    assert(ranges::upper_bound(input, static_cast<T>(100)) == input.end());
+  });
+  test_algorithm<I>(no_duplicates, ranges::less(), successor, [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+
+    auto result = ranges::upper_bound(input.begin(), input.end(), static_cast<T>(2), comp_ref, proj_ref);
+    assert(result == ranges::next(input.begin(), 2));
+    assert(ranges::upper_bound(input, static_cast<T>(2), comp_ref, proj_ref) == result);
+  });
+
+  auto no_duplicates_reversed = std::array{9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
+
+  test_algorithm<I>(no_duplicates_reversed, ranges::greater(), [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast<T>(5), comp_ref);
+    assert(result == ranges::next(input.begin(), 5));
+    assert(ranges::upper_bound(input, static_cast<T>(5), comp_ref) == result);
+  });
+  test_algorithm<I>(no_duplicates_reversed, ranges::greater(), [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    assert(ranges::upper_bound(input.begin(), input.end(), static_cast<T>(-5), comp_ref) == input.end());
+    assert(ranges::upper_bound(input, static_cast<T>(-5), comp_ref) == input.end());
+  });
+  test_algorithm<I>(no_duplicates_reversed, ranges::greater(), std::negate(), [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+    auto result = ranges::upper_bound(input.begin(), input.end(), static_cast<T>(-5), comp_ref, proj_ref);
+    assert(result == input.end());
+    assert(ranges::upper_bound(input, static_cast<T>(-5), comp_ref, proj_ref) == result);
+  });
+
+  // Check duplicates by arranging ints into equivalence classes. To further ensure the integrity of
+  // `upper_bound`, we'll shuffle two of the equivalence classes, so that they're not sorted.
+  // The final equivalence class is omitted so that we can add tests using the pre-defined `successor`
+  // projection.
+  auto mod4_equivalence_classes = std::array{0, 4, 8, 16, 73, 13, 22, 110, 70};
+
+  // Check that we really do have equivalence classes and that 2/3 of them aren't sorted.
+  assert(ranges::is_partitioned(mod4_equivalence_classes.begin(), mod4_equivalence_classes.end(),
+                                [](int const x) { return x % 4 == 0; }));
+  assert(std::is_sorted(mod4_equivalence_classes.begin(), mod4_equivalence_classes.begin() + 4));
+
+  assert(ranges::is_partitioned(mod4_equivalence_classes.begin() + 4, mod4_equivalence_classes.end(),
+                                [](int const x) { return x % 4 == 1; }));
+  assert(!std::is_sorted(mod4_equivalence_classes.begin() + 4, mod4_equivalence_classes.begin() + 6));
+
+  assert(ranges::is_partitioned(mod4_equivalence_classes.begin() + 6, mod4_equivalence_classes.end(),
+                                [](int const x) { return x % 4 == 2; }));
+  assert(!std::is_sorted(mod4_equivalence_classes.begin() + 6, mod4_equivalence_classes.end()));
+
+  auto strict_weak_order = [](auto const x, auto const y) {
+    return (static_cast<int>(x) % 4) < (static_cast<int>(y) % 4);
+  };
+
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast<T>(0), comp_ref);
+    assert(result == ranges::next(input.begin(), 4));
+    assert(ranges::upper_bound(input, static_cast<T>(0), comp_ref) == result);
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast<T>(1), comp_ref);
+    assert(result == ranges::next(input.begin(), 6));
+    assert(ranges::upper_bound(input, static_cast<T>(1), comp_ref) == result);
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast<T>(2), comp_ref);
+    assert(result == input.end());
+    assert(ranges::upper_bound(input, static_cast<T>(2), comp_ref) == result);
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, [](auto& input, auto& comp) {
+    auto comp_ref = std::ref(comp);
+    assert(ranges::upper_bound(input.begin(), input.end(), static_cast<T>(3), comp_ref) == input.end());
+    assert(ranges::upper_bound(input, static_cast<T>(3), comp_ref) == input.end());
+  });
+
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+    auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast<T>(0), comp_ref, proj_ref);
+    assert(result == input.begin());
+    assert(ranges::upper_bound(input, static_cast<T>(0), comp_ref, proj_ref) == result);
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+
+    auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast<T>(1), comp_ref, proj_ref);
+    assert(result == ranges::next(input.begin(), 4));
+    assert(ranges::upper_bound(input, static_cast<T>(1), comp_ref, proj_ref) == result);
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+
+    auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast<T>(2), comp_ref, proj_ref);
+    assert(result == ranges::next(input.begin(), 6));
+    assert(ranges::upper_bound(input, static_cast<T>(2), comp_ref, proj_ref) == result);
+  });
+  test_algorithm<I>(mod4_equivalence_classes, strict_weak_order, successor, [](auto& input, auto& comp, auto& proj) {
+    auto comp_ref = std::ref(comp);
+    auto proj_ref = std::ref(proj);
+
+    auto const result = ranges::upper_bound(input.begin(), input.end(), static_cast<T>(3), comp_ref, proj_ref);
+    assert(result == input.end());
+    assert(ranges::upper_bound(input, static_cast<T>(3), comp_ref, proj_ref) == result);
+  });
+
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(check_upper_bound<forward_iterator, int>());
+  static_assert(check_upper_bound<forward_iterator, double>());
+  check_upper_bound<forward_iterator, int>();
+  check_upper_bound<forward_iterator, double>();
+
+  static_assert(check_upper_bound<bidirectional_iterator, int>());
+  static_assert(check_upper_bound<bidirectional_iterator, double>());
+  check_upper_bound<bidirectional_iterator, int>();
+  check_upper_bound<bidirectional_iterator, double>();
+
+  static_assert(check_upper_bound<random_access_iterator, int>());
+  static_assert(check_upper_bound<random_access_iterator, double>());
+  check_upper_bound<random_access_iterator, int>();
+  check_upper_bound<random_access_iterator, double>();
+
+  static_assert(check_upper_bound<contiguous_iterator, int>());
+  static_assert(check_upper_bound<contiguous_iterator, double>());
+  check_upper_bound<contiguous_iterator, int>();
+  check_upper_bound<contiguous_iterator, double>();
+
+  ASSERT_SAME_TYPE(decltype(ranges::upper_bound(std::vector<int>(10), 0)),
+                   ranges::dangling);
+  ASSERT_SAME_TYPE(decltype(ranges::upper_bound(std::vector<int>(10), 0, {})),
+                   ranges::dangling);
+  ASSERT_SAME_TYPE(decltype(ranges::upper_bound(std::vector<int>(10), 0, {}, {})),
+                   ranges::dangling);
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/ranges_upper_bound/special_function.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: gcc-10
+
+// ranges::upper_bound
+
+#include <algorithm>
+
+#include <array>
+#include <iterator>
+#include <ranges>
+#include <utility>
+
+#include "test_range.h"
+#include "test_standard_function.h"
+
+static_assert(is_function_like<decltype(std::ranges::upper_bound)>());
+
+namespace ranges = std::ranges;
+
+namespace std::ranges {
+  template<class T>
+  class basic_istream_view {
+    struct iterator;
+  public:
+    iterator begin();
+    default_sentinel_t end() const;
+  };
+} // namespace std::ranges
+
+auto f = [](auto, auto) { return true; };
+
+// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent
+// name lookup ([basic.lookup.argdep]). When found by unqualified ([basic.lookup.unqual]) name lookup for
+// the postfix-expression in a function call ([expr.call]), they inhibit argument-dependent name lookup.
+template <class T>
+constexpr bool no_unqualified_lookup() {
+  auto identity = ranges::basic_istream_view<T>();
+  static_assert(!requires(T const value) { upper_bound(ranges::begin(identity), ranges::end(identity), value, f); });
+  static_assert(!requires(T const value) { upper_bound(ranges::begin(identity), ranges::end(identity), value, f, &T::first); });
+  static_assert(!requires(T const value) { upper_bound(identity, value, f); });
+  static_assert(!requires(T const value) { upper_bound(identity, value, f, &T::first); });
+  return true;
+};
+
+static_assert(no_unqualified_lookup<std::pair<int, int>>());
+
+namespace test {
+template <class>
+struct iterator {
+  using value_type = std::pair<int, int>;
+  using difference_type = std::ptrdiff_t;
+  using iterator_category = std::forward_iterator_tag;
+
+  iterator() = default;
+
+  value_type operator*() const;
+  iterator& operator++();
+  iterator operator++(int);
+
+  bool operator==(iterator const&) const = default;
+};
+
+template<class>
+struct range {
+  std::pair<int, int> const* begin() const;
+  std::pair<int, int> const* end() const;
+};
+
+template <class I>
+void upper_bound(iterator<I>, iterator<I>, auto, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I>
+void upper_bound(iterator<I>, iterator<I>, auto, auto, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class R>
+void upper_bound(R&&, auto, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+
+template <class R>
+void upper_bound(R&&, auto, auto, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+} // namespace test
+
+// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a
+// function call ([expr.call]), they inhibit argument-dependent name lookup.
+void adl_inhibition() {
+  using std::ranges::upper_bound;
+
+  test::iterator<std::pair<int, int>*> x;
+  std::pair<int, int> value;
+  (void)upper_bound(x, x, value, f);
+  (void)upper_bound(x, x, value, f, &std::pair<int, int>::first);
+
+  test::range<int*> r;
+  (void)upper_bound(r, value, f);
+  (void)upper_bound(r, value, f, &std::pair<int, int>::first);
+}