std::ranges::make_heap 的限制是什么?

what are the constraints for std::ranges::make_heap?

以下代码适用于 gcc:

struct S {
  int i, j;
  auto operator<(const S& s) const {
    return i < s.i;
  };
};
std::vector<S> v;
std::make_heap(v.begin(), v.end());

但是当我切换到 C++20 的范围算法时:

std::ranges::make_heap(v);

I got this compiler error:

source>:14:27: error: no match for call to '(const std::ranges::__make_heap_fn) (std::vector<S>&)'
14 |   std::ranges::make_heap(v);
   |    
                   ^

似乎struct S不满足ranges::make_heap的要求,但我不知道具体是什么,有人可以帮忙吗?

std::ranges::make_heap 使用 std::ranges::less,它有一个约束:

Unlike std::less, std::ranges::less requires all six comparison operators <, <=, >, >=, == and != to be valid (via the totally_ordered_with constraint).

您的类型 S 没有相等运算符;飞船运算符仅提供其他比较运算符。*

要解决此问题,请为您的类型提供 operator==

constexpr auto operator==(const S& s) const {
  return i == s.i;
}

神马 Link: https://godbolt.org/z/cGfrxs

出于性能原因,

* operator<=> 并不意味着 operator==,因为 operator== 可以使集合短路,而 operator<=> 则不能。但是,从 https://en.cppreference.com/w/cpp/language/default_comparisons 中,我们看到默认的 operator<=> 也将隐式默认 operator==.


我是怎么想出来的?您的代码的错误消息包括以下内容(由我修剪和换字):

note: the expression 'is_invocable_v<_Fn, _Args ...>
    [with _Fn = std::ranges::less&; _Args = {value_type&, value_type&}]'
    evaluated to 'false'
  338 |     concept invocable = is_invocable_v<_Fn, _Args...>;
      |                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

这意味着std::ranges::make_heap发现它不能为我们的类型调用std::ranges::less。对向量的 value_type 上的 std::ranges::less 重复此错误消息调查得到:

note: no operand of the disjunction is satisfied
  123 |       requires totally_ordered_with<_Tp, _Up>
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  124 |         || __detail::__less_builtin_ptr_cmp<_Tp, _Up>

在这一点上,编译器正在努力告诉我们我们不满足 totally_ordered_with,这意味着是时候查看概念和 std::ranges::less 的文档了。