Introduction
This is about the comparison operators in C++ and making them easy to implement. There are 6 comparison operators in C++; ==, !=, <, <=, >, and >=. If you want to be able to apply all of these to a class, and you have the right type of order, you only need to implement one function which will determine them all. Incidentally, this is called a total order, but I won’t go into what that means here.
The tl;dr of this is look at this repository and use a class from there to easily implement custom comparison operators.
This idea is to map the order onto the real numbers (double
s). So you have a function which takes two instances of a class and returns a double
. If this function returns a negative number, then the first instance is less than the second, if it returns 0
they are equal and if it returns a positive number then the first instance is greater than the second.
This will be easier to see with an example, so here is a class which is just data storage for an int
.
This is the header.
class IntCompare {
public:
IntCompare(int data)
: m_data(data)
{
}
bool operator<(const IntCompare&) const;
bool operator<=(const IntCompare&) const;
bool operator==(const IntCompare&) const;
bool operator!=(const IntCompare&) const;
bool operator>=(const IntCompare&) const;
bool operator>(const IntCompare&) const;
private:
double compare(const IntCompare& other) const;
int m_data;
};
All 6 operators will be defined in terms of the compare()
function. You could also just implement operator< then implement the others in terms of this, but that would be harder to abstract in the way I will show you later in this post. Also in this case compare()
could return an int
not a double
, but I return a double
so I can abstract this more easily.
Here are the trivial parts of the source.
bool IntCompare::operator<(const IntCompare& other) const
{
return compare(other) < 0;
}
bool IntCompare::operator<=(const IntCompare& other) const
{
return compare(other) <= 0;
}
bool IntCompare::operator==(const IntCompare& other) const
{
return compare(other) == 0;
}
bool IntCompare::operator>=(const IntCompare& other) const
{
return compare(other) >= 0;
}
bool IntCompare::operator>(const IntCompare& other) const
{
return compare(other) > 0;
}
There are the six operators which will be the same for any class you implement using this design.
Now for the compare()
function. This will be different for every class you implement comparisons this way.
For IntCompare
, it is very easy as they are just int
s. Here it is.
double IntCompare::compare(const IntCompare& other) const
{
return m_data - other.m_data;
}
This code is used in the following calling code:
int main() {
IntCompare one(1);
IntCompare two(2);
IntCompare three(3);
cout << "one < two " << (one < two) << endl;
cout << "one == one " << (one == one) <<endl;
cout << "two < two " << (two < two) <<endl;
cout << "three < two " << (three < two) << endl;
cout << "one < three " << (one < three) <<endl;
cout << "three > two " << (three > two) << endl;
return 0;
}
Which has the output:
one < two 1
one == one 1
two < two 0
three < two 0
one < three 1
three > two 1
You can find all this code in this file.
I have mentioned that you may want to implement several classes in this way, so now we abstract this logic.
When I did this I first tried an abstract
base class, like this.
class Compare {
public:
Compare();
bool operator<(const Compare&) const;
bool operator<=(const Compare&) const;
bool operator==(const Compare&) const;
bool operator!=(const Compare&) const;
bool operator>=(const Compare&) const;
bool operator>(const Compare&) const;
virtual ~Compare() = 0;
private:
virtual int compare(const Compare& other) const = 0;
};
This has the advantage that you override compare()
but cannot call it as it is private
to the base class. The advantages of this are nicely explained in an article by Herb Sutter found here.
This is a good start, but has a serious bug. If you have two derived classes, IntCompare
and StringCompare
, you will be able to ask if a string
is less than an int
. That does not make sense so I’m going to make some adjustments to this.
This is a classic use case of what is called the curiously recurring template pattern. In this, you make a derived class inherit from a templatised base class using the derived class as the template parameter. This is easier to follow with an example.
template<class T>
class Base
{
};
class Derived : Base<Derived>
{
};
Using this, we can abstract the implementation into a base class and make it type safe. Here is the templatised base class:
template <typename T>
class Compare {
public:
Compare();
bool operator<(const T&) const;
bool operator<=(const T&) const;
bool operator==(const T&) const;
bool operator!=(const T&) const;
bool operator>=(const T&) const;
bool operator>(const T&) const;
virtual ~Compare() = 0;
private:
virtual double compare(const T& other) const = 0;
};
This then has the trivial source:
template <typename T>
Compare<T>::Compare()
{
}
template <typename T>
Compare<T>::~Compare()
{
}
template <typename T>
bool Compare<T>::operator<(const T& other) const
{
return compare(other) < 0;
}
template <typename T>
bool Compare<T>::operator<=(const T& other) const
{
return compare(other) <= 0;
}
template <typename T>
bool Compare<T>::operator==(const T& other) const
{
return compare(other) == 0;
}
template <typename T>
bool Compare<T>::operator!=(const T& other) const
{
return compare(other) != 0;
}
template <typename T>
bool Compare<T>::operator>=(const T& other) const
{
return compare(other) >= 0;
}
template <typename T>
bool Compare<T>::operator>(const T& other) const
{
return compare(other) > 0;
}
Compare can then be used as a base class in the following way:
class IntCompare : public Compare<IntCompare> {
public:
IntCompare(int data);
virtual ~IntCompare();
private:
virtual double compare(const IntCompare& other) const;
int m_data;
};
With source:
IntCompare::IntCompare(int data)
: m_data(data)
{
}
IntCompare::~IntCompare()
{
}
double IntCompare::compare(const IntCompare& other) const
{
return m_data - other.m_data;
}
This removes a lot of boilerplate code. So if you have anything which can be totally ordered, all you need to do is you can derive from Compare
and implement one function. After that, you will be able to use any ordering function.
To show this with a less trivial example, I’ll show how to implement ordering on points.
For points, you can order them coordinatewise. This means that in 2D, it checks the x
then the y
.
So (1, -5) > (0.5, 100) as 1 > 0.5.
You may ask what is the purpose of ordering points in this way? Sorting is a common need in software, for various reasons such as removing duplicates or applying operations more efficiently. And to sort a collection, you need to have an order on the objects.
Here is an implementation of this order using the Compare
base class.
Header:
class PointCompare : public Compare<PointCompare> {
public:
PointCompare(double x, double y);
virtual ~PointCompare();
private:
virtual double compare(const PointCompare& other) const;
double m_x;
double m_y;
};
And the source:
PointCompare::PointCompare(double x, double y)
: m_x(x),
m_y(y)
{
}
PointCompare::~PointCompare()
{
}
double PointCompare::compare(const PointCompare& other) const
{
double ret_val = m_x - other.m_x;
if (ret_val == 0) {
ret_val = m_y - other.m_y;
}
return ret_val;
}
If you want to see the finished code, including a unit test, you can find it in this mercurial repository.
That repository (and all of my recent projects) is built using premake a great cross platform utility for making projects. It means I can describe the project in one file, and users will be able to build it using Visual Studio/GNU make/Code::Blocks/… This is a great little tool and I would recommend it to anyone.
Thanks for reading.