Dave++

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 determines 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 (doubles). 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;
  // returns:
  // -ve if other > this
  // 0 if other == this
  // +ve if other < this

  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 6 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 ints. Here it is.

//=============================================================================
double IntCompare::compare(const IntCompare& other) const
// returns:
// -ve if other > this
// 0 if other == this
// +ve if other < this
{
  // easy ordering because they're ints
  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();
  // Ctor

  // all the comparison operators
  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;
  // pure virtual destructor
  
private:
  virtual int compare(const Compare& other) const = 0;
  // returns:
  // -ve if other > this
  // 0 if other == this
  // +ve if other < this
};

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();
  // Ctor

  // all the comparison operators
  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;
  // pure virtual destructor
  
private:
  virtual double compare(const T& other) const = 0;
  // returns:
  // -ve if other > this
  // 0 if other == this
  // +ve if other < this
};

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);
  // Constructor

  virtual ~IntCompare();
  // Destructor
  
private:

  virtual double compare(const IntCompare& other) const;
  // Comparison function
  
  // variables
  int m_data;
};

With source.

//=============================================================================
IntCompare::IntCompare(int data)
  : m_data(data)
{
}

//=============================================================================
IntCompare::~IntCompare()
{
}

//=============================================================================
double IntCompare::compare(const IntCompare& other) const
// returns:
// -ve if other > this
// 0 if other == this
// +ve if other < this
{
  // easy ordering because they're ints
  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);
  // Constructor

  virtual ~PointCompare();
  // Destructor
  
private:

  virtual double compare(const PointCompare& other) const;
  // Comparison function
  
  // variables
  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
// returns:
// -ve if other > this
// 0 if other == this
// +ve if other < this
{
  double ret_val = m_x - other.m_x;
  if (ret_val == 0) {
    // x coordinates are equal
    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.