03 - 3-way comparison

Rewritten candidates

C++20 has made overload resolution smarter for comparison operators with the feature of rewritten candidates - if x != y is not valid, compiler will try !(x == y) and analogically for other comparison operators. Rewritten candidates are considered for both member and non-member overloads.

Thus:

• The guideline to implement comparison operators as non-members is no longer needed.

• You no longer need to implement so many operator overloads. The boilerplate work is now done by the compiler.

• Some compiler errors have been improved.

Do rewritten candidates break existing special usages of operator overloading such as EDSL?

No. They are only considered if no implementation has been explicitly provided for remaining combinations.

Defaulted implementation

Another improvement is that you can now = default all comparison operators if they are member functions. They will compare class members in order of their appearance (identical to std::tie trick from previous lesson).

The spaceship operator

operator<=> represents 3-way comparison. It provides more information so a bool return type is not enough for it.

Before delving into what should be used instead of bool, you should first understand logical concepts that motivated multiple choices for the return type.

Can I call <=> a TIE Fighter?

No. I have been informed that:

• TIE Fighter is |=|

• <=> is Darth Vader's TIE Fighter

• <==> is TIE Bomber

• (=) is Inquisitor's TIE Advanced Prototype

Theory

Exercise

Which comparison categories are present in the following situations?

• points by the sum of their X, Y coordinates

• files by their size

• files by their paths

• users by their unique ID

• people by their birth date

• people by their ancestry tree

Practice

operator<=> can return one of 3 ordering types, defined in <compare>. The types themselves are not enumerations but classes (and values implemented as inline static constexpr members) which allows to specify implicit convertions by writing non-explicit converting constructors.

std::strong_ordering is implicity-convertible to std::weak_ordering which is implicity-convertible to std::partial_ordering.

All values:

• std::strong_ordering::less

• std::strong_ordering::equal

• std::strong_ordering::equivalent

• std::strong_ordering::greater

• std::weak_ordering::less

• std::weak_ordering::equivalent

• std::weak_ordering::greater

• std::partial_ordering::less

• std::partial_ordering::equivalent

• std::partial_ordering::greater

• std::partial_ordering::unordered

Equivalent elements are treated the same way for the purpose of comparison but are distinguishable. Equal elements are truly identical (thus this value is only present in std::strong_ordering).

If every member of the class has defined operator<=> and the operator<=> definition is defaulted, you can use auto as a return type and the compiler will pick the most powerful ordering category that is possible. Built-in types are considered to have the operator defined.

You can call operator<=> and its result (one of standard library ordering types) can be compared with one of the terms listed above and also directly with literal 0:

1
2
3
4
5
6
7

const auto cmp = x <=> y; // cmp will be std::*_ordering
if (cmp < 0)
	std::cout << "x < y";
else if (cmp > 0)
	std::cout << "x > y";
else
	std::cout << "x == y";

What's the reason behind special treatment of operator== and operator!=?

Optimization. Take strings as an example. Determining which of "abc" and "abCD" is greater requires a loop that goes through multiple characters (potentially expensive operation if strings are long and many first characters are equal). Determining whether they are equal is instant because equality can start by comparing length and only consider looping through characters if lengths are the same. In other words, for some types 2-way equivalence check can be much faster than 3-way comparison. Thus, if operator<=> is not = default, operator== should not be = default too.

Fraction class

• Weak ordering is used because two equal fractions can have different representation (e.g. 1/2 vs 2/4).

• No operator is defaulted because the implementation is more complex than mere memberwise comparison.

• operator== is defined because the 2-way equivalence check can be more optimal than 3-way comparison.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// (all inside class body)

bool operator==(fraction rhs) const
{
	if (denominator() == rhs.denominator())
		return numerator() == rhs.numerator();

	return numerator() * rhs.denominator() == rhs.numerator() * denominator();
}

std::weak_ordering operator<=>(fraction rhs) const
{
	if (denominator() == rhs.denominator())
	{
		if (denominator() > 0)
			return numerator() <=> rhs.numerator();
		else
			return rhs.numerator() <=> numerator();
	}

	const auto new_lhs_numerator = numerator() * rhs.denominator();
	const auto new_rhs_numerator = rhs.numerator() * denominator();

	if ((denominator() > 0) == (rhs.denominator() > 0))
		return new_lhs_numerator <=> new_rhs_numerator;
	else
		return new_rhs_numerator <=> new_lhs_numerator;
}

Mixed-type comparisons

Thanks to rewritten candidates, the example from previous lesson can be simplified to this code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class player
{
private:
	int id;
	// lots of other fields... (potentially expensive to construct)

public:
	// [...]

	bool operator==(const player& rhs) const
	{
		return id == rhs.id;
	}

	bool operator==(int other_id) const
	{
		return id == other_id;
	}
};

Lexicographical comparison

Just like in the previous lesson, you can use std::tie trick to avoid writing bug-prone code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <tuple>

struct package
{
	int rack;
	int shelf;
	int position;
	// [...] some other members that should not be used in comparison

	auto operator<=>(package rhs) const
	{
		return std::tie(rack, shelf, position)
		   <=> std::tie(rhs.rack, rhs.shelf, rhs.position);
	}
};

If there are no extra members and memberwise comparison is desired, the operator can be defined as = default.

Recommendations

Advanced features

The standard library contains niebloids that can be used to compare objects and produce a result of specific comparison category (as long as the comparison is possible).

When writing generic code, it is recommended not to use operator<=> as not every type may have it defined. Instead, it is recommended to use a template like the one presented below that will check for operator<=> existence and fall back to other operators.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <compare>
#include <type_traits>

struct synth_three_way_t
{
	template <typename T, std::totally_ordered_with<T> U>
	constexpr auto operator()(const T& lhs, const U& rhs) const
	{
		if constexpr (std::three_way_comparable_with<T, U>)
		{
			return lhs <=> rhs;
		}
		else
		{
			// Jonathan Müller used strong ordering here
			// I don't think we can assume that for arbitrary T and U
			if (lhs == rhs)
				return std::weak_ordering::equivalent;
			else if (lhs < rhs)
				return std::weak_ordering::less;
			else
				return std::weak_ordering::greater;
		}
	}
};
inline constexpr synth_three_way_t synth_three_way;

template <typename T, typename U = T>
using synth_three_way_category
	= decltype(synth_three_way(std::declval<const T&>(), std::declval<const U&>()));

Trivia

There was an idea to use the name <=> for the header <compare>[citation needed] but it was ultimately resigned from due to concern that = may not be in the set of supported characters for paths on some implementations.

This lesson has been based on:

• https://www.jonathanmueller.dev/talk/meetingcpp2019/

• https://youtube.com/watch?v=bysb-tzglqg