How to Emulate the Spaceship Operator Before C++20 with CRTP
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:
struct MyStruct
{
int i;
double d;
std::string text;
};
In order to make it comparable with a simple lexicographical comparison we’d simply add a default generated <=> operator.
struct MyStruct
{
int i;
double d;
std::string text;
auto operator<=>(const MyStruct&) = default;
};
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:
struct MyStruct
{
int i;
double d;
std::string text;
const auto Tie() const { return std::tie(i, d, text); }
[[nodiscard]] bool operator==(const MyStruct& other) const
{
return Tie() == other.Tie();
}
[[nodiscard]] bool operator!=(const MyStruct& other) const
{
return Tie() != other.Tie();
}
[[nodiscard]] bool operator<(const MyStruct& other) const
{
return Tie() < other.Tie();
}
[[nodiscard]] bool operator>(const MyStruct& other) const
{
return Tie() > other.Tie();
}
[[nodiscard]] bool operator>=(const MyStruct& other) const
{
return Tie() >= other.Tie();
}
[[nodiscard]] bool operator<=(const MyStruct& other) const
{
return Tie() <= other.Tie();
}
};
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.
template <typename T>
class TieComparable
{
private:
constexpr T const& Underlying() const { return static_cast<const T&>(*this); }
TieComparable() = default;
~TieComparable<T>() = default;
TieComparable<T>(const TieComparable<T>& other) = default;
TieComparable<T>(TieComparable<T>&& other) = default;
TieComparable<T>& operator=(const TieComparable<T>& other) = default;
TieComparable<T>& operator=(TieComparable<T>&& other) = default;
friend T;
public:
[[nodiscard]] constexpr bool operator==(const T& other) const
{
return Underlying().Tie() == other.Tie();
}
[[nodiscard]] constexpr bool operator!=(const T& other) const
{
return Underlying().Tie() != other.Tie();
}
[[nodiscard]] constexpr bool operator<(const T& other) const
{
return Underlying().Tie() < other.Tie();
}
[[nodiscard]] constexpr bool operator>(const T& other) const
{
return Underlying().Tie() > other.Tie();
}
[[nodiscard]] constexpr bool operator>=(const T& other) const
{
return Underlying().Tie() >= other.Tie();
}
[[nodiscard]] constexpr bool operator<=(const T& other) const
{
return Underlying().Tie() <= other.Tie();
}
};
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:
struct MyStruct : public TieComparable<MyStruct>
{
int i;
double d;
std::string text;
const auto Tie() const { return std::tie(i, d, text); }
};
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.
struct NonLexicalCompare : public TieComparable<NonLexicalCompare>
{
int i;
double d;
std::string text;
const auto Tie() const
{
return std::make_tuple(text.size(), std::tie(i, d, text));
}
};
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:
struct MaybeMeaningfulValue
{
bool meaningful;
double value;
constexpr bool operator<(const MaybeMeaningfulValue& other) const
{
// if !meaningful, value shouldn’t participate in comparison
if (meaningful && other.meaningful)
{
return value < other.value;
}
else
{
return meaningful < other.meaningful;
}
}
};
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:
template <typename T>
class IneqComparable
{
private:
constexpr T const& Underlying() const
{
return static_cast<const T&>(*this);
}
IneqComparable() = default;
~IneqComparable<T>() = default;
IneqComparable<T>(const IneqComparable<T>& other) = default;
IneqComparable<T>(IneqComparable<T>&& other) = default;
IneqComparable<T>& operator=(const IneqComparable<T>& other) = default;
IneqComparable<T>& operator=(IneqComparable<T>&& other) = default;
friend T;
public:
[[nodiscard]] constexpr bool operator==(const T& other) const
{
return !(Underlying() < other) && !(other < Underlying());
}
[[nodiscard]] constexpr bool operator!=(const T& other) const
{
return (Underlying() < other) || (other < Underlying());
}
[[nodiscard]] constexpr bool operator>(const T& other) const
{
return other < Underlying();
}
[[nodiscard]] constexpr bool operator>=(const T& other) const
{
return !(Underlying() < other);
}
[[nodiscard]] constexpr bool operator<=(const T& other) const
{
return !(other < Underlying());
}
};
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
- What the Curiously Recurring Template Pattern can bring to your code
- Variadic CRTP: An Opt-in for Class Features, at Compile Time
- Variadic CRTP Packs: From Opt-in Skills to Opt-in Skillsets
- Removing Duplicates in C++ CRTP Base Classes
Share this post!
