为什么 std::ranges::upper_bound 不接受异构比较？

Question

此代码有效，returns 一个迭代器从向量 foo{5}：

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;
            }
    );
}

但是，这不会编译：

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;
}

行为的改变是有意还是无意？

错误消息归结为不满足以下约束：

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

嗯，是的，你不能用两个 int& 来调用它。我怀疑这可能是故意的，因为“标准”方式是像这样使用投影：

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;
}

是这个道理吗？查看 std::ranges::upper_bound 的模板参数的相当复杂的签名对我来说并没有真正照亮它。

Answer 1

Is the alteration of the behavior intentional or accidental?

这是故意的。

ranges::upper_bound的函数签名如下：

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 = {});

当你打电话时：

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

编译器需要检查indirect_strict_weak_order是否满足。在您的示例中，T 是 int，Comp 是 lambda 的类型，I 是 vector<foo>::iterator，并且由于您没有指定 Proj，约束可以简化为

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

而indirect_strict_weak_order定义如下

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>&> && 
  //...

其中，std::strict_weak_order<...>替换为

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

也就是

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

而strict_weak_order定义如下

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

需要std::relation<R, T, U>需要：

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>;

在上述约束中，需要满足std::predicate<R, T, T>，其中R是Comp&，是左值lambda类型，T是int&，因为你的 lambda 不能用 {int&, int&} 调用，所以约束不满足。

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

是的，推荐这个。

引自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.

Answer 2

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

这基本上是预测的动机。来自 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.

而 std::sort 采用同质比较，而 std::lower_bound 和 std::upper_bound 各自采用异质比较（参数顺序相反），这些的 std::ranges:: 版本算法都采用同质比较。 std::ranges::lower_bound 和 std::ranges::upper_bound 通过投影实现异质性，在将其传递到同构比较之前简单地在内部应用于范围的元素，而 std::ranges::sort 将投影应用于两个参数。

这更易于使用，编写的代码更少，也更不容易出错：因为您只需对所有三种算法进行一次比较，而不必记住参数的顺序对于两个 bound 算法。

为什么 std::ranges::upper_bound 不接受异构比较？

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

c++

projection

c++-concepts

c++20

std-ranges