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

Question

在 this article我偶然发现了这个晦涩的代码(随意呈现，就像这是一个完全正常的 C++ 代码):

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

然后创建并比较两棵树(参见 the demo ):

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 实现了 vector 与 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>的operator<有一个前提条件是<为 T 定义，但 libstdc++ 没有检查这个。他们的实现was basically :

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>而是有 operator<=> ，它有一个约束:

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

这里的问题是:为了弄清楚 Tree是三向可比的，我们必须弄清楚我们是否可以调用 <=>在两个 Tree s，找到这个 operator<=>(vector<Tree>, vector<Tree>)候选，仅在 Tree 时定义是三路可比的，所以我们必须弄清楚我们是否可以调用 <=>在两个 Tree s，它发现...
所以那... 行不通，也行不通。
不幸的是，这甚至不是一个问题:只需添加 ==和 <=>至 Tree , 自 vector的 <=>仍然是候选人，只是问它是否有效的问题会爆炸。
因此，这不是在 C++20 中实现比较的可行策略。您将无法从 vector 继承像这样。您只需将其添加为成员即可。