Why doesn't std::ranges::upper_bound accept heterogenous comparing?-CodePudding

This code works and returns an iterator to foo{5} from the vector:

struct foo {
    int value;
};

auto main() -> int {
    auto ints = std::vector<foo>{{3}, {2}, {5}, {6}, {7}, {0}, {4}, {6}};

    std::ranges::sort(ints, {}, &foo::value);
    auto it = std::upper_bound(
            ints.begin(), ints.end(),
            4,
            [](const int v, const foo f) {
                return v < f.value;
            }
    );
}

This, however, doesn't compile:

struct foo {
    int value;
};

auto main() -> int {
    auto ints = std::vector<foo>{{3}, {2}, {5}, {6}, {7}, {0}, {4}, {6}};

    std::ranges::sort(ints, {}, &foo::value);
    auto it = std::ranges::upper_bound(     // the only change - added ::ranges
            ints,
            4,
            [](const int v, const foo f) {
                return v < f.value;
            }
    );
    std::cout << it->value;
}

Is the alteration of the behavior intentional or accidental?

The error message boils down to not satisfying the following constraint:

note: the expression 'is_invocable_v<_Fn, _Args ...> [with _Fn = main::._anon_76&; _Args = {int&, int&}]' evaluated to 'false'

Well, yeah, you can't call that with two int&s. I suspect it may be intentional since the "standard" way would be to use the projection like so:

struct foo {
    int value;
};

auto main() -> int {
    auto ints = std::vector<foo>{{3}, {2}, {5}, {6}, {7}, {0}, {4}, {6}};

    std::ranges::sort(ints, {}, &foo::value);
    auto it = std::ranges::upper_bound(ints, 4, {}, &foo::value); // using projection
    std::cout << it->value;
}

Is this the rationale? Looking at the fairly complilated signature of template parameters of std::ranges::upper_bound didn't really shine any light on it for me.

CodePudding user response：

Is the alteration of the behavior intentional or accidental?

This is intentional.

The function signature of ranges::upper_bound is as follows:

template<std::forward_iterator I, std::sentinel_for<I> S,
         class T, class Proj = std::identity,
         std::indirect_strict_weak_order<
           const T*,
           std::projected<I, Proj>> Comp = ranges::less>
constexpr I 
upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {});

When you call:

auto it = std::ranges::upper_bound(ints, 4, 
  [](const int v, const foo f) { return v < f.value; });

The compiler needs to check whether indirect_strict_weak_order is satisfied. In your example, T is int, Comp is the type of lambda, and I is vector<foo>::iterator, and since you did not specify Proj, the constraint can be simplified as

static_assert(
  std::indirect_strict_weak_order<Comp, const int*, std::vector<foo>::iterator>);

And indirect_strict_weak_order is defined as follows

template< class F, class I1, class I2 = I1 >
concept indirect_strict_weak_order =
  std::indirectly_readable<I1> &&
  std::indirectly_readable<I2> &&
  std::copy_constructible<F> &&
  std::strict_weak_order<F&, std::iter_value_t<I1>&, std::iter_value_t<I2>&> && 
  //...

Among them, std::strict_weak_order<...> is replaced with

static_assert(
  std::strict_weak_order<Comp&, 
    std::iter_value_t<const int*>&, 
    std::iter_value_t<std::vector<foo>::iterator>&>);

That is

static_assert(std::strict_weak_order<Comp&, int&, foo&>);

And strict_weak_order is defined as follows

template<class R, class T, class U>
concept strict_weak_order = std::relation<R, T, U>;

which requires std::relation<R, T, U> which requires:

template<class R, class T, class U>
concept relation =
  std::predicate<R, T, T> && std::predicate<R, U, U> &&
  std::predicate<R, T, U> && std::predicate<R, U, T>;

In the above constraints, it requires std::predicate<R, T, T> to be satisfied, where R is Comp& which is an lvalue lambda type, and T is int&, since your lambda cannot invoke with {int&, int&}, so the constraints are not satisfied.

I suspect it may be intentional since the "standard" way would be to use the projection like so:

Yes, this is recommended.

Quoting from the N4128 13.2 Algorithms Should Take Invokable Projections:

With today’s STL, when using sort and lower_bound together with user-defined predicates, the predicate must sometimes differ. Consider:
std::sort(a, [](const employee& x, const employee& y)
             { return x.last < y.last; }); 
auto p = std::lower_bound(a, "Parent", [](const employee& x, const string& y) 
                                       { return x.last < y; }); 
Notice the different predicates used in the invocations of sort and lower_bound. Since the predicates are different, there is a chance they might get out of sync leading to subtle bugs.

By introducing the use of projections, this code is simplified to:
 std::sort(a, std::less<>(), &employee::last); 
 auto p = std::lower_bound(a, "Parent", std::less<>(), &employee::last);
Every element in the input sequence is first passed through the projection &employee::last. As a result, the simple comparison predicate std::less<> can be used in both places.

CodePudding user response：

I suspect it may be intentional since the "standard" way would be to use the projection like so:

This is basically the motivation for projections. From N4128:

The Adobe Source Libraries (ASL)[1] pioneered the use of “projections” to make the algorithms more powerful and expressive by increasing interface symmetry. Sean Parent gives a motivating example in his “C Seasoning” talk[15], on slide 38. With today’s STL, when using sort and lower_bound together with user-defined predicates, the predicate must sometimes differ. Consider:
std::sort(a, [](const employee& x, const employee& y)
             { return x.last < y.last; });
auto p = std::lower_bound(a, "Parent", [](const employee& x, const string& y)
                                       { return x.last < y; });
Notice the different predicates used in the invocations of sort and lower_bound. Since the predicates are different, there is a chance they might get out of sync leading to subtle bugs.

By introducing the use of projections, this code is simplified to:
std::sort(a, std::less<>(), &employee::last);
auto p = std::lower_bound(a, "Parent", std::less<>(), &employee::last);
Every element in the input sequence is first passed through the projection &employee::last. As a result, the simple comparison predicate std::less<> can be used in both places.

Whereas std::sort takes a homogeneous comparison and std::lower_bound and std::upper_bound each take a heterogeneous comparison (with the arguments in opposite order), the std::ranges:: versions of these algorithms all take homogeneous comparisons. std::ranges::lower_bound and std::ranges::upper_bound achieve heterogeneity with the projection, which is simply internally applied to the range's element before passing it into the homogeneous comparison, while std::ranges::sort applies the projection to both arguments.

This is a lot easier to use, less code to write, and less error prone: because you just have the one comparison that you use for all three algorithms, and you don't have to remember the order of arguments for the two bound algorithms.