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

Question

这段代码能够运行并且从向量中返回一个指向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模板参数的相当复杂签名并没有为我提供任何启发。

- Fureeish

Answer 1

我猜测这可能是有意为之的，因为“标准”的方式应该是像这样使用投影：

这基本上是投影的动机所在。来自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算法参数的顺序。

- Barry

Answer 2

这是有意为之。 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&} 调用，所以不满足约束条件。

---

我怀疑这可能是有意为之的，因为“标准”方式是这样使用投影：

是的，这是推荐的做法。

引用来自N4128 13.2 算法应采用可调用的投影：

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.

- 康桓瑋

---

这是我问题的一部分得到了回答（或者说是一个子部分），关于概念中确切指定的内容。已点赞，但我想听听背后的原理，最好能够支持论文或讨论引用。 - Fureeish

@Fureeish。我不是设计范围算法概念的人。关于它的设计哲学，你可以参考原始的范围论文，如P0896以及range-v3的一些早期文档。 - 康桓瑋