std::ranges::make_heap有哪些限制？

Question

以下代码在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);

我遇到了这个编译器错误：

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 的要求，但我不知道具体是什么问题，请问有人能帮忙吗？

- 康桓瑋

---

在错误信息中找到预期的重载，并查看为该重载详细说明的失败约束。 - chris

Answer 1

std::ranges::make_heap使用std::ranges::less，该函数有一个约束：

与std::less不同，std::ranges::less要求所有六个比较运算符<、<=、>、>=、==和!=都是有效的（通过totally_ordered_with约束）。

你的类型S没有等于运算符；航天员运算符只提供了其他比较运算符.*

为了解决这个问题，请为您的类型提供operator==：

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

Godbolt链接：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的文档了。

- Justin

---

在这里添加==确实解决了问题，但我认为解释不正确。例如，如果<=>被默认，则可以工作。 - cigien

@cigien 实际上，宇宙飞船运算符的工作方式与我想象的有些不同，如果默认情况下提供 operator==，则会提供一个 operator<=>。来自 https://en.cppreference.com/w/cpp/language/default_comparisons 的说明是：“如果 operator<=> 被默认化且根本没有声明 operator==，则 operator== 会被隐式地默认化。” - Justin

啊，好发现。我想那就解释了 :) 你可能想要提一下。像是“因为你有一个非默认的<=>，所以==没有被生成”。 - cigien