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

Question

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

7

在这篇文章中，我碰到了这段晦涩的代码（仅以随意的方式呈现，就好像这是一段完全正常的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 和 b<a 的大小关系（请参见cpppreference上的“Possible implementation”部分），因此对于像上面的 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下偶然可以编译通过）。

- Mikhail

1

看起来GCC 11中的compare_three_way存在问题，它甚至无法编译示例代码。 - rustyx

@rustyx 不，那是正确的。compare_three_way只比检查<=>有更严格的要求：three_way_comparable_with还需要equality_comparable。 - Barry

这是指数级的，而不仅仅是二次方的。 - Davis Herring

2个回答

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函数中，我们只返回false。第二个比较*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() 包含了 vector 的 value_type，它必须满足 std::three_way_comparable_with 的概念，但我们没有为 Tree 定义任何 operator<=>，因此我们得到了 Constraints not satisfied。

- 康桓瑋

嗯，这解释了为什么标准库的当前实现会失败，但严格来说，这并不意味着程序是非法的。我不清楚为什么在其他stdlib实现中std::three_way_comparable_with不能在Tree上工作。 - Mikhail

你能举个例子说明你不清楚的是什么吗？ - 康桓瑋

我不喜欢短语“我们没有为Tree定义任何operator <=>，因此我们得到了Constraints not satisfied”。std::vector包含operator<=>成员，Tree继承了该成员，因此应满足std::three_way_comparable_with。 - Mikhail

1

Tree 继承自 std::vector<Tree> 而不是 std::vector，而且 std::vector<Tree> 的 operator<=> 取决于 Tree 的 operator<=>。如果我们没有为 Tree 定义 operator<=>，那么我们就无法使用 three_way_comparable_with 比较 std::vector<Tree>，因为它们是相互依赖的。 - 康桓瑋

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Barry · Accepted Answer

这里的问题是约束递归。

在C++17中，向量`vector`的操作符`operator<`有一个前置条件，即必须定义了类型`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> 有了 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 调用 <=>，这会找到……

所以这种方法行不通，也不能行。

不幸的是，问题甚至不是仅仅添加 == 和 <=> 到 Tree 中，因为 vector 的 <=> 仍然是一个候选项，而仅仅询问它是否有效就会导致程序崩溃。

因此，这不是在 C++20 中实现比较的可行策略。你不能像这样从 vector 继承。你必须将其作为成员添加。