CRTP-ed std::vectors 的三向比较

Question

在这篇文章中，我偶然发现了这段晦涩的代码（随意呈现，就像这是一个完全正常的 C++ 代码）：

struct Tree : std::vector<Tree> {};

然后创建并比较两棵树（参见演示）：

Tree tree(size_t h)
{
  Tree s;
  if (h > 0)
    s.insert(s.end(), 2, tree(h - 1));
  return s;
}

int main()
{
  size_t h = 15;
  Tree s1 = tree(h);
  Tree s2 = tree(h);
  clock_t t = clock();
  s1 < s2;
  double d = clock() - t;
  d /= CLOCKS_PER_SEC;
  std::cout << d << std::endl; // 4.1s
}

经过一番思考，我意识到这种比较似乎是合法的，并且总是会产生错误。

本文的想法是，由于C ++矢量与17个工具比较std::lexicographical_compare，其对应元素进行比较a，并b在两个序列既是a<b和b<a（见cpppreference“可能的实现”一节），为深似结构的性能Tree以上会降低深度的二次方。确实如此。

文章也说三路比较不存在这样的问题。但是等等，这正是 C++20 中使用operator<=>. 但这里有一个警告。

此代码不能在 C++20 中编译：

/opt/compiler-explorer/gcc-snapshot/lib/gcc/x86_64-linux-gnu/11.0.1/../../../../include/c++/11.0.1/compare:914:35: fatal error: recursive template instantiation exceeded maximum depth of 1024
        = decltype(__detail::__synth3way(std::declval<_Tp&>(),

这是我的问题。这个编译错误是编译器中的一个错误，还是这段代码实际上格式错误？如果代码格式错误，是仅适用于 C++20 还是适用于 C++17 和 C++20？（后者意味着此代码只能在 C++17 下偶然编译）。

Answer 1

这里的问题是约束递归。

在 C++17 中，vector<T>soperator<有一个<为 定义的前提条件T，但 libstdc++ 没有检查这一点。他们的实施基本上是：

template <typename T>
inline bool operator<(vector<T> const& a, vector<T> const& b) {
    return lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
}

这...只是有效。

但在 C++20 中，vector<T>改为 has operator<=>，它有一个约束：

template <typename T>
    // this checks either <=> or <
    requires synth_3way_comparable<T>
auto operator<=>(vector<T> const& a, vector<T> const& b) { ... }

这里的问题是：为了弄清楚Tree是否是三向可比较的，我们必须弄清楚是否可以调用<=>两个Trees，这两个 s 会找到这个operator<=>(vector<Tree>, vector<Tree>)候选者，只有在Tree是三向可比较时才定义它，所以我们必须弄清楚我们是否可以调用<=>两个Trees，这会发现......

所以说……不起作用，也不可能起作用。

不幸的是，这甚至不是一个问题：只需将==和<=>添加到Tree，因为vectors<=>仍然是候选者，并且仅询问它是否有效的问题就会爆炸。

因此，这不是在 C++20 中实现比较的可行策略。你将无法vector像这样继承。您只需将其添加为成员即可。