{"id":106661,"date":"2022-05-16T07:06:52","date_gmt":"2022-05-16T14:06:52","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=106661"},"modified":"2022-05-16T07:06:52","modified_gmt":"2022-05-16T14:06:52","slug":"20220516-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20220516-52\/?p=106661","title":{"rendered":"How can I synthesize a C++20 three-way comparison from two-way comparisons?"},"content":{"rendered":"

The C++20 three-way comparison operator <=><\/tt> (commonly nicknamed the spaceship operator<\/i> due to its appearance<\/a>) compares two items and describes the result. It’s called the three-way comparison because there are five possible results: less<\/i>, equal<\/i>, equivalent<\/i>, greater<\/i>, and unordered<\/i>.<\/p>\n

Yeah, the name is kind of weird.<\/p>\n

It’s called the three-way comparison because in other languages, the equivalent operator has three possible results: less<\/i>, equal<\/i>, and greater<\/i>. C++20 expands the set of possible results but kept the old name. (Sound familiar<\/a>?)<\/p>\n\n\n\n\n\n\n
Ordering<\/th>\nResults<\/th>\n<\/tr>\n
strong ordering<\/td>\nless<\/td>\nequal<\/td>\nequivalent<\/td>\ngreater<\/td>\n <\/td>\n<\/tr>\n
weak ordering<\/td>\nless<\/td>\nequivalent<\/td>\ngreater<\/td>\n <\/td>\n<\/tr>\n
partial ordering<\/td>\nless<\/td>\nequivalent<\/td>\ngreater<\/td>\nunordered<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Each of the orderings can convert to the one below it, using the conversions given by the chart.<\/p>\n

The strong ordering distinguishes between items being equal<\/i> (identical and interchangeable) and equivalent<\/i> (not interchangeable but close enough for some purpose). For example, two instances of the same string \"hello\"<\/code> are equal, in that they represent the same string and are fully interchangeable. On the other hand, two people with the same security clearance are equivalent<\/i> from a security perspective (they have access to the same things), but they are not equal<\/i> (they are nevertheless different people).<\/p>\n

When sorting, you are usually interested in equivalence, but when searching you might be interested in equality. (I’m looking for Bob, not just anybody with the same security clearance as Bob.)<\/p>\n

Suppose you have an object from a class library that predates C++20 and doesn’t support three-way comparison. You want your code to be able to take advantage of the three-way comparison should the library be updated but fall back to two-way comparison in the meantime. In other words, you want to take advantage of three-way comparison if available.<\/p>\n

Fortunately, you don’t have to write all that SFINAE nonsense, because somebody else has done it for you: std::tuple<\/code>.<\/p>\n

Tuples have the bonus property of supporting the three-way comparison operator, even if the underlying types do not. In the case where they do not, they will synthesize a three-way comparison from the two-way comparisons.<\/p>\n\n\n\n\n\n
if a < b<\/code><\/td>\nreturn less<\/code><\/td>\n<\/tr>\n
else if a > b<\/code><\/td>\nreturn greater<\/code><\/td>\n<\/tr>\n
otherwise<\/td>\nreturn equivalent<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

So we can just wrap the objects inside a std::tuple<\/code> and compare the tuples. To avoid unnecessary copies, we can wrap them as references, or use forward_as_tuple<\/code> which always uses references.<\/p>\n

std::weak_ordering\r\ncompare_3way_via_tuple(T const& a, T const& b)\r\n{\r\n    return std::forward_as_tuple(a) <=>\r\n           std::forward_as_tuple(b);\r\n}\r\n<\/pre>\n
It turns out that there’s already a pre-made function that does something very similar: std::compare_weak_order_fallback<\/code> also synthesize a missing three-way comparison, but it uses a different algorithm from tuples:<\/p>\n\n\n\n\n\n
if a == b<\/code><\/td>\nreturn equivalent<\/code><\/td>\n<\/tr>\n
else if a < b<\/code><\/td>\nreturn less<\/code><\/td>\n<\/tr>\n
otherwise<\/td>\nreturn greater<\/code><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
Tuples use a different algorithm from std::compare_weak_order_fallback<\/code>. Which one is better? Why are they different?<\/p>\n
I suspect that tuples use a different algorithm because tuple ordering comes from C++11, which predates three-way comparison. Back in those days, the comparison operators was used mostly for sorting and other ordered-sequence type algorithms. And those algorithms require only that the objects support the <<\/code> operator. Therefore, tuples have to make do with only the <<\/code> operator.<\/p>\n
On the other hand, std::compare_weak_order_fallback<\/code> was born into the world of three-way comparisons, so it has more liberty to take dependencies on things beyond just the <<\/code> operator.<\/p>\n
If you know that the underlying object supports ==<\/code>, then my guess is that std::compare_weak_order_fallback<\/code> is better, because ==<\/code> testing tends to be faster than <<\/code> testing. For example, comparing two strings for equality can short-circuit if the strings are different lengths. This shortcut is not available for less-than comparison.<\/p>\n","protected":false},"excerpt":{"rendered":"
Multiple ways of synthesizing a comparison.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-106661","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Multiple ways of synthesizing a comparison.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106661","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=106661"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106661\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=106661"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=106661"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=106661"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}