Jonathan Boccara's blog

How to Emulate the Spaceship Operator Before C++20 with CRTP

Published April 9, 2019 - 0 Comments

Today’s post is written by Henrik Sjöström . Henrik is currently working at Starcounter building an SQL queryprocessor. He enjoys working on algorithmically complex issues and prioritises expressive code so the actual problem is visible rather than hidden by hard to follow code.

Making a class comparable is usually something of a chore. In C++20 we’ll get the “three-way comparison operator” or informally spaceship operator <=>. It will allow the compiler to create comparison operators when we want a simple lexicographical comparison and when we have a more complex comparison we only need to implement a single operator to be able to do all comparisons.

Let us take a simple struct:

In order to make it comparable with a simple lexicographical comparison we’d simply add a default generated <=> operator.

Effectively this class now has all comparison operators, ==,!=,>,<,>=,<=. That saves quite a bit of effort. There is a good description by Simon Brand available here for more information about <=>.

Emulating the spaceship operator

Now since C++20 and <=> is some time away we can simply implement the full set of comparison operators. We’ll do it with the help of std::tie, which allows us to use the comparison operators of a tuple with references to our values, rather than implementing everything ourselves:

That is quite a lot of code and if we want to use the same logic on another struct we’ll get the dubious pleasure of writing it all again.

So how do we avoid that?

Comparisons using CRTP

We’ll define a skill TieComparable and use it as a CRTP base class to avoid having to put all this code into every little struct.

The private constructors and destructor are simply so that it can’t (easily) be used outside of the class we want to compare.

Now we only need to write:

This makes MyStruct comparable with a full set of comparison operators. This only works as long as all elements in Tie() have the appropriate operators. However that is a flaw easily fixed by making those classes themselves TieComparable.

Doing a non lexical comparison

If we want to do some more complex comparisons we can manage this too. For example using MyStruct from above but we want to start by comparing the length of the text member before doing the other comparisons we can do that too.

We couldn’t simply use std::tie here since it returns references and text.size() returns a temporary by value, however we can still use it for the other members since references to them are still valid.

It is possible to write comparison operators that can’t easily be replicated by a comparison of tuples however this covers many cases.

Performance impact

So this saves writing quite a bit of code which is nice. What is the performance impact?

Compiling this example with -O3 on GCC 8.2 gives exactly the same binary as a manually implemented operator== so we can safely say that there is no performance impact for that case.

For the case of operator< a quick benchmark implies that there is negligible change. The benchmark uses MyStruct from above and times std::is_sorted over a vector with 1000000 identical elements:

Another implementation with fewer restrictions

If the comparison is more complex it might not be possible to represent it as a tuple to be compared. For example if there is some extra logic in the comparison operator:

We can implement the CRTP base class so that it deduces the other operators from operator<. We then only have to implement a single operator, and get the rest for free:

So why even bother with the first implementation since this is more general?

Firstly I generally have an easier time implementing the Tie() function, the only easy mistake there is to forget a member when calling std::tie. Implementing a operator< is quite easy to mess up particularly for classes with several member variables of the same type.

Secondly TieComparable has no overhead but implementing comparison as in IneqComparable is a bit less efficient for == and !=. About a factor of 2 slower.

So when possible use TieComparable.

You will also like

Become a Patron!
Share this post! Facebooktwittergoogle_pluslinkedin    Don't want to miss out ? Follow:   twitterlinkedinrss

Get a free ebook on C++ smart pointers

Get a free ebook of more than 50 pages that will teach you the basic, medium and advanced aspects of C++ smart pointers, by subscribing to our mailing list! On top of that, you will also receive regular updates to make your code more expressive.

No spam. You can unsubscribe at any time.