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

Question

In this article I've stumbled upon this obscure code (which is presented casually, like this is a totally normal C++ code):

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

Two trees are then created and compared (see 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
}

After some thinking, I've realized this comparison seems legal and will always yield false.

The idea of the article is that since C++17 implements comparisons of vectors with std::lexicographical_compare, which compares corresponding elements a and b in two sequences as both a<b and b<a (see "Possible implementation" section on cpppreference), the performance for deep structures like the Tree above will degrade quadratically on the depth. And indeed it does.

The article also says that three-way comparison does not have such a problem. But wait, that's exactly what emerged in C++20 with operator<=>. But here is the caveat.

This code does not compile in 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&>(),

Here is my question. Is this compile error a bug in the compiler, or is this code actually ill-formed? If the code is ill-formed, is it so only for C++20 or for both C++17 and C++20? (The latter would imply that this code compiles under C++17 only by chance).

Answer 1

The issue here is constraint recursion.

In C++17, vector<T>'s operator< had a precondition that < was defined for T, but libstdc++ didn't check this. Their implementation 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());
}

This... just works.

But in C++20, vector<T> instead has operator<=>, which has a constraint:

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

The problem here is that: in order to figure out of Tree is three-way comparable, we have to figure out if we can call <=> on two Trees, which finds this operator<=>(vector<Tree>, vector<Tree>) candidate, which is only defined if Tree is three-way-comparable, so we have to figure out if we can call <=> on two Trees, which finds ...

So that... doesn't work, and can't work.

Unfortunately it's not even a question of: just adding == and <=> to Tree, since vector's <=> will still be a candidate and just asking the question of whether or not it is valid explodes.

As a result, this isn't a viable strategy for implementing comparisons in C++20. You won't be able to inherit from vector like this. You'll have to just add it as a member.