{"id":106674,"date":"2022-05-19T07:00:00","date_gmt":"2022-05-19T14:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=106674"},"modified":"2022-05-19T07:12:32","modified_gmt":"2022-05-19T14:12:32","slug":"20220519-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20220519-00\/?p=106674","title":{"rendered":"Writing a sort comparison function, part 3: spaceships"},"content":{"rendered":"

Last time, we wrote a multi-level sort with deferred calculation of secondary keys<\/a>. Having to compare everything twice got cumbersome. We can do better with the C++20 spaceship operator.<\/p>\n

\/\/ three-way comparison\r\nstd::weak_ordering\r\ncompare_3way_for_sorting(T const& a, T const& b)\r\n{\r\n    \/\/ First compare by name\r\n    std::weak_ordering cmp = a.name <=> b.name;\r\n    if (cmp != 0) return cmp;\r\n\r\n    \/\/ Names are equal, check connector names\r\n    cmp = a.GetConnector() <=> b.GetConnector();\r\n    if (cmp != 0) return cmp;\r\n\r\n    \/\/ Names and connector names are equal,\r\n    \/\/ manufacturing date is the last check.\r\n    cmp = LookupManufacturingDate(a.part_number) <=>\r\n          LookupManufacturingDate(b.part_number);\r\n    return cmp;\r\n}\r\n\r\n\/\/ less-than comparison\r\nbool compare_less_for_sorting(T const& a, T const& b)\r\n{\r\n    \/\/ First compare by name\r\n    std::weak_ordering cmp = a.name <=> b.name;\r\n    if (cmp != 0) return cmp < 0;\r\n\r\n    \/\/ Names are equal, check connector names\r\n    cmp = a.GetConnector() <=> b.GetConnector();\r\n    if (cmp != 0) return cmp < 0;\r\n\r\n    \/\/ Names and connector names are equal,\r\n    \/\/ manufacturing date is the last check.\r\n    cmp = LookupManufacturingDate(a.part_number) <=>\r\n          LookupManufacturingDate(b.part_number);\r\n    return cmp < 0;\r\n}\r\n<\/pre>\n
Another way of writing this is<\/p>\n
\/\/ three-way comparison\r\nstd::weak_ordering\r\ncompare_3way_for_sorting(T const& a, T const& b)\r\n{\r\n    std::weak_ordering cmp = a.name <=> b.name;\r\n    if (cmp == 0) cmp = a.GetConnector() <=> b.GetConnector();\r\n    if (cmp == 0) cmp = LookupManufacturingDate(a.part_number) <=>\r\n                        LookupManufacturingDate(b.part_number);\r\n    return cmp;\r\n}\r\n\r\n\/\/ less-than comparison\r\nbool compare_less_for_sorting(T const& a, T const& b)\r\n{\r\n    \/\/ First compare by name\r\n    std::weak_ordering cmp = a.name <=> b.name;\r\n    if (cmp == 0) cmp = a.GetConnector() <=> b.GetConnector();\r\n    if (cmp == 0) cmp = LookupManufacturingDate(a.part_number) <=>\r\n                        LookupManufacturingDate(b.part_number);\r\n    return cmp < 0;\r\n}\r\n<\/pre>\n
And then we can use the std::compare_weak_order_fallback<\/code> function to synthesize a missing three-way comparison:<\/p>\n
std::weak_ordering\r\ncompare_3way_for_sorting(T const& a, T const& b)\r\n{\r\n    auto cmp = std::compare_weak_order_fallback(a.name, b.name);\r\n    if (cmp == 0) cmp = std::compare_weak_order_fallback(a.GetConnector(), b.GetConnector());\r\n    if (cmp == 0) cmp = std::compare_weak_order_fallback(LookupManufacturingDate(a.part_number),\r\n                                                         LookupManufacturingDate(b.part_number));\r\n    return cmp;\r\n}\r\n\r\n\/\/ less-than comparison\r\nbool compare_less_for_sorting(T const& a, T const& b)\r\n{\r\n    auto cmp = std::compare_weak_order_fallback(a.name, b.name);\r\n    if (cmp == 0) cmp = std::compare_weak_order_fallback(a.GetConnector(), b.GetConnector());\r\n    if (cmp == 0) cmp = std::compare_weak_order_fallback(LookupManufacturingDate(a.part_number),\r\n                                                         LookupManufacturingDate(b.part_number));\r\n    return cmp < 0;\r\n}\r\n<\/pre>\n
Next time, we’ll look at descending sorts.<\/p>\n
Bonus chatter<\/b>: There is high copy\/pasta error risk because the left and right of the <=><\/code> operator differ only by the choice of a<\/code> or b<\/code>. Maybe we could use this helper:<\/p>\n
template<typename T, typename U = T>\r\nstruct successive_comparisons\r\n{\r\n    successive_comparisons(T&& left, U&& right) :\r\n        a(left), b(right) {}\r\n    T&& a;\r\n    U&& b;\r\n\r\n    template<typename Lambda>\r\n    auto compare(Lambda&& lambda)\r\n    { return lambda(a) <=> lambda(b); }\r\n};\r\n\r\n\/\/ I don't know why these deduction guides are necessary, but\r\n\/\/ it doesn't work if I omit them.\r\ntemplate<typename T, typename U = T>\r\nsuccessive_comparisons(T&, U&) -> successive_comparisons<T&, U&>;\r\n\r\ntemplate<typename T, typename U = T>\r\nsuccessive_comparisons(T&&, U&) -> successive_comparisons<T&, U>;\r\n\r\ntemplate<typename T, typename U = T>\r\nsuccessive_comparisons(T&, U&&) -> successive_comparisons<T, U&>;\r\n\r\ntemplate<typename T, typename U = T>\r\nsuccessive_comparisons(T&&, U&&) -> successive_comparisons<T, U>;\r\n\r\n\/\/ Avoid copy\/pasta risk.\r\nstd::weak_ordering\r\ncompare_3way_for_sorting(T const& a, T const& b)\r\n{\r\n    auto s = successive_comparisons(a, b);\r\n\r\n    std::weak_ordering\r\n        cmp = s.compare([](auto&& v) { return v.name; });\r\n    if (cmp == 0)\r\n        cmp = s.compare([](auto&& v) { return v.GetConnector(); });\r\n    if (cmp == 0)\r\n        cmp = s.compare([](auto&& v) { return LookupManufacturingDate(v.part_number); });\r\n    return cmp;\r\n}\r\n<\/pre>\n
Unfortunately, this copies the v.name<\/code> unnecessarily since the deduced lambda return type is as if by auto<\/code>, which is a copy, not a reference. To avoid the copy, you must ask for a reference return, which is either by naming the type explicitly or by using decltype(auto)<\/code> with a parenthesized return value.<\/p>\n
std::weak_ordering\r\ncompare_3way_for_sorting(T const& a, T const& b)\r\n{\r\n    auto s = successive_comparisons(a, b);\r\n\r\n    std::weak_ordering\r\n        cmp = s.compare([](auto&& v) -> decltype(auto)<\/span> { return (v.name)<\/span>; });\r\n    if (cmp == 0)\r\n        cmp = s.compare([](auto&& v) { return v.GetConnector(); });\r\n    if (cmp == 0)\r\n        cmp = s.compare([](auto&& v) { return LookupManufacturingDate(v.part_number); });\r\n    return cmp;\r\n}\r\n<\/pre>\n
I’m not sure this is an improvement. It just replaces one copy\/pasta risk for another.<\/p>\n
Also, this helper class prevents you from reusing intermediates from previous comparison steps.<\/p>\n
std::weak_ordering\r\ncompare_3way_for_sorting(T const& a, T const& b)\r\n{\r\n    auto s = successive_comparisons(a, b);\r\n\r\n    std::weak_ordering\r\n        cmp = s.compare([](auto&& v) -> decltype(auto) { return (v.name); });\r\n    if (cmp == 0)\r\n        cmp = s.compare([](auto&& v) { return v.GetConnector(); });\r\n    if (cmp == 0)\r\n        cmp = s.compare([](auto&& v) { return v.GetConnector().InstallDate(); });\r\n    return cmp;\r\n}\r\n<\/pre>\n
We have to call GetConnector()<\/code> a second time in order to look up its installation date, even though we had already done so earlier. With the explicit cascading version, we could reuse the results of the previous lookup:<\/p>\n
std::weak_ordering\r\ncompare_3way_for_sorting(T const& a, T const& b)\r\n{\r\n    std::weak_ordering cmp = a.name <=> b.name;\r\n    if (cmp != 0) return cmp;\r\n\r\n    auto connectorA = a.GetConnector();\r\n    auto connectorB = b.GetConnector();\r\n    cmp = connectorA <=> connectorB;\r\n    if (cmp != 0) return cmp;\r\n \r\n    return connectorA.InstallDate() <=> connectorB.InstallDate();\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Sprinkling some C++20 magic.<\/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-106674","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Sprinkling some C++20 magic.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106674","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=106674"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106674\/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=106674"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=106674"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=106674"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}