Writing comparison operators is still one of the tasks that requires a lot of boilerplate code in C++ even for the simplest of user-defined types. Although it is theoretically possible to let the compiler implement default comparison operators (or more generally, comparison functions), we still have no standardized way of doing so.

This article shows a simple way to add comparison operators with minimal effort for a broad category of simple user-defined types. The technique used is reminiscent of reflection, and can even be implemented non-intrusively for C-like structs.

The current state of affairs

Even in C++14, the compiler won't implement any comparison operators automatically, and there is not even a way to request the compiler to do so. The same issue occurs for arithmetic operators, which won't be covered by this article.

With inheritance, it is possible to compare two objects of derived types where comparison operators have only been defined for a base class. As opposed to special member functions, this is not even prevented by default; it can happen accidentally and may violate certain axioms of comparing objects where the derived type is involved.

There are recent proposals for standardization of compiler-generated comparison functions , and there are proposals to use the proposed reflection utilities to write a library implementing comparison operators .

Post-scriptum: After writing this article, I read the N4239 paper, which unsurprisingly suggests using an approach very similar to the one described here.

A simple implementation of lexicographical comparison

The starting point of this article was some snippet of code I stumbled upon some time ago on StackOverflow. Unfortunately, I cannot remember any details, such as who wrote that code. The snippet show-cased a simplistic implementation of a comparison function:

struct my_simple_type
{
	int x;
	int y;
};

bool operator< (my_simple_type const& lhs, my_simple_type const& rhs) {
	return std::tie(lhs.x, lhs.y) < std::tie(rhs.x, rhs.y);
}

This is much simpler than a straight-forward low-level implementation:

bool operator< (my_simple_type const& lhs, my_simple_type const& rhs) {
	if(lhs.x < rhs.x) return true;
	if(lhs.x > rhs.x) return false;
	return lhs.y < rhs.y;
}

You might immediately see that the std::tie version can even be simplified further:

auto tie_nsdm(my_simple_type const& p) {
	return std::tie(p.x, p.y);
}

bool operator< (my_simple_type const& lhs, my_simple_type const& rhs) {
	return tie_nsdm(lhs) < tie_nsdm(rhs);
}

nsdm stands for Non-Static Data Member.

The implementation of other comparison operators only differs in the operator applied between the two tied tuples:

bool operator== (my_simple_type const& lhs, my_simple_type const& rhs) {
	return tie_nsdm(lhs) == tie_nsdm(rhs);
}

Using a single tie-function to implement multiple operators reduces the number of functions that are dependent on the number and names of the data members, potentially simplifying maintenance.

One might argue that the comparison operators can typically be implemented by a ternary comparison function, without exposing data members:

struct my_comparison_result;
bool implies_less_than(my_comparison_result const&);
bool implies_equal    (my_comparison_result&);

my_comparison_result compare(my_simple_type const& lhs, my_simple_type const& rhs);

bool operator< (my_simple_type const& lhs, my_simple_type const& rhs) {
	return implies_less_than( compare(lhs, rhs) );
}

bool operator== (my_simple_type const& lhs, my_simple_type const& rhs) {
	return implies_equal( compare(lhs, rhs) );
}

But there's another use case that definitely requires more exposition of the data members: Hashing.

Types don't know many things

Howard Hinnant proposed in his talk and paper Types don't know # the Universal hash function, or rather a technique that allows hashing of types with arbitrary hash functions.

I realized there's a common problem in implementing comparison operators and hash functions: accessing the data members of an encapsulated class. This way of formulating the problem is an oversimplification. Quoting the paper by Hinnant, Falco and Bytheway:

[...] types do know what parts of their state should be exposed to a hashing algorithm.

Similarly, types know what parts of their state are relevant for a comparison function. An automatic (reflection-based) implementation of comparison operators is therefore not viable for all types. But there's a set of types for which a reflection-based implementation of both comparison functions and hash_append is useful, and I'd argue this set of types is large enough to warrant a simple solution (since it is, after all, possible to provide one).

For a more general case, the name tie_nsdm is not well-suited: What we need to provide in our cases (comparison, hashing) is unencapsulated reading access to the relevant state of an object. This formulation still lacks a precision, which I hope can be gained by abstracting from examples.

With a function that exposes the relevant state, we can write comparison operators, hashing functions and even some arithmetic operators with very few boilerplate code.

Of course, we could generalize the problem of accessing the data members by passing in a function object from outside:

template<class F>
decltype(auto) apply_to_members(F f) const {
	return f( tie_nsdm(*this) );
}

But this is not any safer than directly exposing the data members themselves: Simply use the identity function for f and the encapsulation is gone. So, why not expose them directly, by making auto tie_nsdm(my_simple_type const&) a publicly accessible feature of an otherwise well-encapsulated class? We'll come back to this later.

A reflection-based implementation of comparison operators

This last bit of boilerplate code for implementing comparison operators can also be removed by implementing the operators via general free function templates:

template<class T>
bool operator< (T const& lhs, T const& rhs) {
	return tie_ndsm(lhs) < tie_nsdm(rhs);
}

But by using an unconstrained template, we have gone too far: Not only have we completely removed encapsulation, we also have introduced a valid operator signature for types that are not comparable conceptually. For any type, if you use a type trait / SFINAE to ask "Is this type less-than-comparable?", the answer will be yes, if the above function template is found.

Additionally, where shall we place such an implementation of operator<, so that it will be found by algorithms in the C++ standard library? Due to the way name lookup works in function templates, we need the declaration of such an operator in a namespace associated with the type of at least one operand of the operator.

Boost.Operators solves this issue by making your class inherit from a helper class that provides additional operators, complementing existing operators in your derived class. These additional operator declarations are therefore bound to this specific type and associated with the base class, hence also with your derived class. Boost.Operators declares those operators as friend functions only, which implies that they cannot even be found for unrelated types.

Inheritance is an intrusive change, and not very well implemented in some compilers with respect to the Empty Base Class Optimization. Hence, I tried to find some machinery that solves these two problems without inheritance:

• restrict the operator declaration to types that support my kind of reflection
• make the operator declaration visible without redefining them in the namespace where the type resides in

The first can be solved with SFINAE of course, or some other implementation or emulation of C++ concepts. The second one is tricky, but I think there's an elegant solution to it as well: using-declarations.

namespace reflection
{
	inline namespace operators
	{
		template<class T>
		bool operator< (T const& lhs, T const& rhs) {
			return tie_nsdm(lhs) < tie_nsdm(rhs);
		}
	}
}

namespace user_namespace
{
	class user_type
	{
		int x;
		int y;
		
		friend auto tie_nsdm(user_type const& o) {
			return tie(o.x, o.y);
		}
	};
	
	// import 
	using reflection::operator<;
}

Names introduced via using-declarations can be found by ADL from the point of definition of a template, as opposed to names introduced via using-directives. And since namespaces are open for extension, we can even add in those operators in our source files on demand:

#include <algorithms>
#include "a_faint_reflection.hpp"
#include "my_library.hpp"

// local extension of user_namespace
// to introduce support for C++ standard algorithms
namespace user_namespace
{
	using reflection::operator<;
}

int main()
{
	std::vector<user_namespace::user_type> v(10);
	std::sort(begin(v), end(v));
}

Of course, you could have passed a comparison function to std::sort instead; using the same pseudo-reflection mechanism to implement said function:

namespace reflection
{
	inline namespace comparison_function_objects
	{
		struct less
		{
			template<typename T>
			bool operator()(T const& lhs, T const& rhs) const {
				return tie_nsdm(lhs) < tie_nsdm(rhs);
			}
		};
	}
}

#include "my_library.hpp"

int main()
{
	std::vector<user_namespace::user_type> v(10);
	std::sort(begin(v), end(v), reflection::less{});
}

And since the function tie_nsdm is found via ADL as a free function, we can implement this non-intrusively if we have access to the relevant state from outside:

// my_library.hpp
namespace user_namespace
{
	struct user_type
	{
		int x;
		int y;
	};
}

// main.cpp
#include <algorithm>
#include "my_library.hpp"
#include "a_faint_reflection.hpp"

// The tie_nsdm function can be placed
//   - either in namespace user_namespace (found via ADL)
//   - or in namespace reflection (found via ordinary unqualified lookup)
// ADL can find it even after importing the reflection machinery,
// but ordinary unqualified lookup cannot.
// However, the operator functions can only be found via ADL
// since you may not inject them into namespace std,
// and they are not guaranteed to be found in the global namespace.
#include <tuple>
namespace user_namespace
{
	// be careful with the linkage when doing this inside a source file
	static auto tie_nsdm(user_type const& o) {
		return std::tie(o.x, o.y);
	}
	
	using reflection::operator<;
}

int main()
{
	std::vector<user_namespace::user_type> v(10);
	std::sort(begin(v), end(v));
}

Restoring encapsulation

I am a bit concerned about the potential of accidental misuse of a function that exposes implementation details so easily and comprehensively. There are several protection mechanism that can be employed to prevent accidental misuse, or in this case, accidentally referring to a function. Any such mechanism typically requires additional complexity, hence they should be employed, as usual, only if their benefits outweigh their costs.

namespace mfd
{
	class some_container {};
	
	// to empty: remove all elements
	template<typename Container>
	void empty(Container& c);
}

namespace ste
{
	class some_container {};
	
	// being empty: contains no elements
	template<typename Container>
	bool empty(Container const& c);
}

namespace pandalib
{
	template<typename Container>
	void generic_function(Container& c) {
		// first, clear container
		empty(c);
		// then, insert new elements
		// ...
	}
}

int main()
{
	mfd::some_container a;
	pandalib::generic_function(a); // fine
	
	ste::some_container b;
	pandalib::generic_function(b); // oops
}

namespace mfd
{
	class some_container {};
	
	struct empty_tag {};
	
	// to empty: remove all elements
	template<typename Container>
	void empty(empty_tag, Container& c);
}

namespace ste
{
	class some_container {};
	
	struct empty_tag {};
	
	// being empty: contains no elements
	template<typename container>
	bool empty(empty_tag, container const& c);
}

namespace pandalib
{
	template<typename Container>
	void generic_function(Container& c) {
		// first, clear container
		empty(mfd::empty_tag{}, c);
		// then, insert new elements
		// ...
	}
}

int main()
{
	mfd::some_container a;
	pandalib::generic_function(a); // fine
	
	ste::some_container b;
	pandalib::generic_function(b); // using mfd::empty, or error if that's not compatible
}

template<typename T>
void generic_function(T const&);

class key_tag
{
private:
	explicit key_tag() = default;
	key_tag(key_tag const&) = default;
	key_tag(key_tag&&) = default;
	~key_tag() = default;
	
	template<typename T>
	friend void generic_function(T const&);
};

template<typename T>
void generic_function(T const& t) {
	auto internals = expose_internals(key_tag{}, t);
	// ...
}

auto expose_internals(key_tag, encapsulated_type const&);

template<typename Key, typename T, typename = void>
struct exposable
	: std::integral_constant<bool, false> {};
template<typename Key, typename T>
struct exposable<Key, T, decltype( expose_internals(Key{}, std::declval<T&>()), void() )>
	: std::integral_constant<bool, true> {};

struct lock;

class key_vault
{
private:
	struct key {};

	friend lock;
	
	template<typename T, std::enable_if_t<exposable<key_vault::key, T>{}>*>
	friend void generic_function(T const&);
};

struct lock
{
	constexpr lock(key_vault::key) noexcept {}
};

class encapsulated_type;
auto expose_internals(lock, encapsulated_type const&);

template<typename T, std::enable_if_t<exposable<key_vault::key, T>{}>* = nullptr>
void generic_function(T const& t) {
	auto internals = expose_internals(key_vault::key{}, t);
	// ...
}

struct str
{
	struct nested {};
	template<nested*> friend void fun();
};

template<str::nested* = nullptr> void fun() {}

struct lock;

class key_vault
{
private:
	struct key {};

	friend lock;
	
	template<typename T>
	friend auto generic_function(T const&)
		-> std::enable_if_t<exposable<key_vault::key, T>{}>;
};

template<typename T>
auto generic_function(T const& t)
	-> std::enable_if_t<exposable<key_vault::key, T>{}>
{
	auto internals = expose_internals(key_vault::key{}, t);
	// ...
}

struct lock;

class key_vault
{
private:
	struct key {};

	friend lock;
	
	template<typename T, std::enable_if_t<exposable<key_vault::key, T>{}>* = nullptr>
	friend void generic_function(T const& t) {
		auto internals = expose_internals(key_vault::key{}, t);
		// ...
	}
};

template<typename T, std::enable_if_t<exposable<key_vault::key, T>{}>*>
void generic_function(T const&);

struct noncopyable_nonmovable
{
	noncopyable_nonmovable() = default;
	
	noncopyable_nonmovable(noncopyable_nonmovable const&) = delete;
	noncopyable_nonmovable(noncopyable_nonmovable&&) = delete;
};

class key_vault
{
private:
	struct key
	{
		explicit key() = default;
	};
	
	friend class lock;
};

class lock : noncopyable_nonmovable
{
public:
	lock() = delete; // prevents expose_internals( {}, t )
	
	template<typename T, std::enable_if_t<not std::is_same<T, key_vault::lock>{}>* = nullptr<
	lock(T) = delete; // prevents expose_internals( {{}}, t )
	
	template<typename T, std::enable_if_t<std::is_same<T, key_vault::lock>{}>* = nullptr<
	constexpr lock(T) noexcept {}
};

template<typename Key, typename T, typename = void>
struct exposable
	: std::integral_constant<bool, false> {};
template<typename Key, typename T> // note:         v----------------v
struct exposable<Key, T, decltype( expose_internals({key_vault::key{}}, std::declval<T&>()), void() )>
	: std::integral_constant<bool, true > {};

What's next?

• Measuring the abstraction penalty in real programs. How well can the compiler optimize the code when using this technique?
• Fine-grained access control to the reflection function. For example, by making the reflection function itself publicly accessible, but returning a class type that exposes the information only to certain friends.

A complete example

For the concepts emulation, I was heavily inspired by StackOverflow user Paul's answer to the question void_t "can implement concepts"?. Although, I think, the answer does not have much to do with void_t, which I therefore ignore in my implementation below. Paul seems to have based his implementation on Concept Checking in C++11 by Eric Niebler . I've chosen to include a minimal implementation of my own below, to make the example complete, i.e. independent from any third-party libraries. Additionally, I had to implement a workaround to avoid using defaulted template parameters in my "requires" clauses, as described above. To find out about the pros and cons of both workarounds, I have implemented both: operator== is implemented in the friend function definition, while operator< uses C++98-style SFINAE in the return type.

#include <type_traits>
#include <tuple>


template<typename... Args>
constexpr auto c_tie(Args&... args) {
	return std::tuple<Args&...>(args...);
}


template<typename T, typename = std::enable_if_t<std::is_rvalue_reference<T&&>{}>>
T&& xval();

template<typename T>
T& lval();

template<typename T, typename = std::enable_if_t< ! std::is_reference<T>{} >>
T prval();

template<typename T>
T&& expr();


struct noncopyable_nonmovable
{
	noncopyable_nonmovable() = default;
	
	noncopyable_nonmovable(noncopyable_nonmovable const&) = delete;
	noncopyable_nonmovable(noncopyable_nonmovable&&) = delete;
};


namespace concepts_emulation
{
	template<typename ConceptCall, typename Matcher = void>
	struct models : std::false_type {};

	template<typename Concept, typename... Args>
	struct models<Concept(Args...), decltype( xval<Concept>().requires_(expr<Args>()...), void() )>
		: std::true_type
	{};
	
	template<typename T>
	using doesnt_model = std::integral_constant<bool, not models<T>{}>;
	
	inline namespace regularity_concepts
	{
		struct EqualityComparable
		{
			template<typename T>
			auto requires_(T&& x) -> decltype( x == x );
		};

		struct LessThanComparable
		{
			template<typename T>
			auto requires_(T&& x) -> decltype( x < x );
		};
	}
	
	
	// We should evaluate multiple requirements lazily,
	// since evaluating a requirement can lead to a hard error
	// if its well-formedness depends on an earlier requirement.
	template<typename... RequiresClauses> struct requires_clause_list {};
	
	
	template<typename... RequiresClauses>
	struct meets_requirements_c : std::true_type {};
	
	template<typename RequiresClause, typename... Rest>
	struct meets_requirements_c<RequiresClause, Rest...>
		: std::conditional_t<RequiresClause{}, meets_requirements_c<Rest...>, std::false_type> {};
	
	template<typename... RequiresClauses, typename... Rest>
	struct meets_requirements_c<requires_clause_list<RequiresClauses...>, Rest...>
		: meets_requirements_c<RequiresClauses..., Rest...> {};
	
	template<typename... RequiresClauses>
	using meets_requirements_t = typename meets_requirements_c<RequiresClauses...>::type;
	
	
	template<typename RequiresClauseList, typename = meets_requirements_t<RequiresClauseList>>
	struct requirements_c { /* not met */ };
	
	template<typename... RequiresClauses>
	struct requirements_c<requires_clause_list<RequiresClauses...>, std::true_type>
	{
		template<typename ReturnType> using met = ReturnType;
	};
	
	
	template<typename... RequiresClauses>
	using requirements = requirements_c<requires_clause_list<RequiresClauses...>>;
	
	template<typename... RequiresClauses>
	using requires_mf = typename requirements<requires_clause_list<RequiresClauses...>>::template met<void>;
}


#define REQUIRES_FWD(...) concepts_emulation::requires_mf<__VA_ARGS__>*
#define REQUIRES(...)     REQUIRES_FWD(__VA_ARGS__) = nullptr
#define REQUIRES_RET(...) typename concepts_emulation::requirements<__VA_ARGS__> :: template
#define RETURNS(TYPE)     met<TYPE>


namespace reflection
{
	// parsing helper for `Reflectable::requires_`:
	// unqualified lookup needs to determine that `Reflect` is a function
	// from the point of definition
	// Unfortunately, recent g++ rejects later code, claiming it would
	// refer to a deleted function (compiler bug?)
	//void Reflect(void) = delete;
	
	template<typename Key>
	struct Reflectable
	{
		template<typename T>
		auto requires_(T&& x) -> decltype( Reflect({xval<Key>()}, x) );
	};
	
	template<typename Key, typename T>
	using Reflection = decltype( Reflect({xval<Key>()}, lval<T>()) );
	
	template<typename T>
	using models = concepts_emulation::models<T>;
	
	template<typename T0, typename T1>
	struct is_different : std::integral_constant<bool, not std::is_same<T0, T1>{}> {};
	
	
	struct lock;
	
	class key_vault : noncopyable_nonmovable
	{
	private:
		struct key
		{
			explicit key() = default;
		};
		
		friend lock;
		
		template<typename T,
			REQUIRES( models<Reflectable<key_vault::key>(T)>,
			          models<concepts_emulation::EqualityComparable(Reflection<key_vault::key, T>)> )
		> friend constexpr bool operator== (T const& lhs, T const& rhs)
		{
			return Reflect({key_vault::key{}}, lhs) == Reflect({key_vault::key{}}, rhs);
		}
		
		template<typename T>
		friend constexpr auto operator< (T const& lhs, T const& rhs) ->
			REQUIRES_RET( models<Reflectable<key_vault::key>(T)>,
			              models<concepts_emulation::LessThanComparable(Reflection<key_vault::key, T>)> )
		RETURNS(bool);
	};
	
	struct lock : noncopyable_nonmovable
	{
		lock() = delete;
		template<typename T, REQUIRES(is_different<T, key_vault::key>)>
			lock(T) = delete;
		template<typename T, REQUIRES(std::is_same<T, key_vault::key>)>
			constexpr lock(T) noexcept {}
	};
	
	template<typename T,
		REQUIRES_FWD( models<Reflectable<key_vault::key>(T)>,
		              models<concepts_emulation::EqualityComparable(Reflection<key_vault::key, T>)> )
	> constexpr bool operator== (T const& lhs, T const& rhs);

	template<typename T>
	constexpr auto operator< (T const& lhs, T const& rhs) ->
		REQUIRES_RET( models<Reflectable<key_vault::key>(T)>,
		              models<concepts_emulation::LessThanComparable(Reflection<key_vault::key, T>)> )
	RETURNS(bool) {
		return Reflect({key_vault::key{}}, lhs) < Reflect({key_vault::key{}}, rhs);
	}
}


namespace user_namespace
{
	class MyRegularType
	{
	public:
		constexpr MyRegularType(int count, double amount)
			: count(count), amount(amount)
		{}
		
		constexpr friend auto Reflect(reflection::lock, MyRegularType const& o)
			-> std::tuple<int const&, double const&> // insufficient support for C++14 (g++)
		{
			return c_tie(o.count, o.amount);
		}
		
	private:
		int count;
		double amount;
	};
	
	
	class ReflectableIncomparable
	{
		class Incomparable {};
		
		friend Incomparable Reflect(reflection::lock, ReflectableIncomparable const&) {
			return {};
		}
	};
	
	class VampireType {};
	
	
	using namespace concepts_emulation;
	using reflection::Reflectable;
	using reflection::Reflection;
	
	// (A)
	static_assert(not models<EqualityComparable(MyRegularType)>{}, "");
	static_assert(not models<LessThanComparable(MyRegularType)>{}, "");
	
	
	using reflection::operator==;
	using reflection::operator<;
	
	// These two tests fail, probably due to memoization during the two tests above (A).
	//static_assert(models<EqualityComparable(MyRegularType)>{}, "");
	//static_assert(models<LessThanComparable(MyRegularType)>{}, "");
	

	constexpr auto cx = MyRegularType(1, 2.3);
	constexpr auto cy = cx;
	constexpr auto cz = MyRegularType(4, 5.6);

	static_assert(   cx == cy  , "" );
	static_assert( !(cx <  cx) , "" );
	static_assert( !(cx == cz) , "" );
	static_assert(   cx <  cz  , "" );
	
	
	static_assert(not models<EqualityComparable(ReflectableIncomparable)>{}, "");
	static_assert(not models<LessThanComparable(ReflectableIncomparable)>{}, "");
	
	static_assert(not models<EqualityComparable(VampireType)>{}, "");
	static_assert(not models<LessThanComparable(VampireType)>{}, "");
}

int main() {}