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实现了向量与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 中格式正确，在 C++20 中格式错误。

考虑以下两棵 2 高的树：

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

int main() {
  Tree s1 = tree(1);
  Tree s2 = tree(1);
  s1 < s2;
}

在 C++17 中，我们只需调用 vector 的 operator<:

bool operator<(const vector<Tree>& x, const vector<Tree>& y) { 
  return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); 
}

这将调用 std::lexicographical_compare:

template <class InputIt1, class InputIt2>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
                             InputIt2 first2, InputIt2 last2) {
  for (; (first1 != last1) && (first2 != last2); ++first1, (void)++first2) {
    if (*first1 < *first2) return true;
    if (*first2 < *first1) return false;
  }
  return (first1 == last1) && (first2 != last2);
}

第一次比较*first1 < *first2，*first1是s1的左节点，*first2是s2的左节点，它们的类型是Tree，所以我们回去比较两个Tree。这个时候，我们没有Tree的operator<，所以我们像第一次一样调用他们的基数operator<，即：

bool operator<(const vector<Tree>& x, const vector<Tree>& y) { 
  return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); 
}

但是这次两个节点的底vector实际上是空的，所以在更深层次的lexicographical_compare函数中，我们只是returnfalse。第二次比较*first2 < *first1遵循相同的程序。

至此，我们完成了左节点的比较，接下来可以++first1, (void)++first2继续进行右节点的比较

在C++20中，s1 < s2重写为：

(s1 <=> s2) < 0

所以我们称 vector 的 operator<=>:

auto operator<=>(const vector<Tree>& x, const vector<Tree>& y) {
  return std::lexicographical_compare_three_way(
    x.begin(), x.end(), y.begin(), y.end(), std::compare_three_way()
  );
}

compare_three_way() contrains the value_type of vector which is Tree must satisfied the std::three_way_comparable_with概念，但是我们没有为Tree定义任何operator<=>，所以我们得到Constraints not satisfied.

Answer 2

这里的问题是约束递归。

在 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 上调用 <=> , 它找到了这个 operator<=>(vector<Tree>, vector<Tree>) 候选者，它只在 Tree 是三向可比较的情况下定义，所以我们必须弄清楚我们是否可以在两个 Tree 上调用 <=> s，找到 ...

所以那...行不通，行不通。

不幸的是，这甚至不是一个问题：只需将 == 和 <=> 添加到 Tree，因为 vector 的 <=> 仍然是一个候选人，只是问它是否有效爆炸。

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

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

Three-way comparison of CRTP-ed std::vectors

c++

comparison

crtp

c++20