Three-way comparison

[Morwenn]

WIP issue, still drafting

This issue is meant to explore once again the work started in #18 in light of the recent additions to the C++20 standard, most notably everything that has to do with operator<=> and the new comparison utilities. The old design was inspired by the tools we had back then, but those tools have changed and I believe we can do better now.

operator<=>

The first big change is the addition of operator<=> itself, which has a few interesting properties: most notably it allows to get rid of three_way_compare from the library's internals: three_way_compare had no extension mechanism for user-defined types while operator<=> is meant to be implemented by users for their own types, so we get the extension mechanism for free. Moreover, three_way_compare included <string> to benefit from std::string::compare, so getting rid of it should lead to some compile-time benefits too.

Frankly three_way_compare is only used in tim_sort and grail_sort today. That said, tim_sort doesn't benefit from a three-way comparison, and I need to check for grail_sort but it's not guaranteed. We can probably get rid of before starting the work on the C++20 branch.

Three-way comparison support for algorithms

If seem to recall that there was a standard proposal mentioning that standard algorithms should accept three-way comparison operators, but I'm unable to find the proposal again. If standard algorithms do end up gaining first-class support for three-way comparisons, we will adopt an equivalent design.

It seems tricky for a variety of reasons:

• Do we use the three-way comparison operators directly?
• Do we use the usual operators knowing that they will hook into operator<=> if needed but might have been specialized to be more efficient?
• Do we accept any function/function object returning one of the standard orders?
• Should we accept partial orders or reject them? Floating point sorting comes to my mind....

There are many questions to be solved before we can provide proper first-class support in the library's algorithms.

Another questions is which algorithms would benefit from three-way comparisons. Basically it's mostly algorithms for which we need to check both a < b and a > b at some point, and there is a specific behaviour (or lack thereof) when the elements compare equivalent. Here is a likely incomplete list of algorithms in the library that might benefit from this:

• [ ] Probably quick_sort for a basic three-way partitioning
• [ ] The measure of presortedness ham
• [ ] grail_sort in some places
• [ ] stable_compare
• [ ] Other candidates? I need to audit the library

New comparison functions

I'm not sure what to do yet with the comparison functions borrowed from P0100: they seem to have equivalent utilities in the standard library itself, but AFAIK those comparisons aren't proper customization point objects, so the ones in cpp-sort are still somewhat better (to be checked). However, if such functions exist in the standard, we can't really expect users to use them. Maybe we can take advantage of the full switch to C++20 to remove them altogether from the library.

EDIT: in Kona 2019, std::strong_order and friends were made customization point objects, so we can safely get rid of our own equivalent functions in cpp-sort 2.0.0.

Related utilities

P1154 (Type traits for structural comparison) proposes a set of type traits to detect structural comparison (equality & ordering). has_weak_structural_ordering looks like a tool that would allow to resuscitate #32 and to provide elements of answers for #88 (EDIT: apparently that sepcific trait was killed in Kona 2019, so RIP me I guess, I'll never have nice toys ç_ç).

P1188 (Library utilities for <=>) proposes among other things the concept ThreeWayComparable which looks like a nice building block to adapt algorithms to three-way comparison.

All the dance around std::compare_3way sounds like a can of worms and we will have to analyze its behaviour in details before taking action on anything involving it.

[Morwenn]

P2022 mentions a future std::ranges::sort_three_way that would accept three-way comparators. Having a separate sort of overloads might allow us to avoid making sorter_facade::operator() overloads even more ridiculous by having an equivalent for three-way sorters.

This kind of implies duplicating a bunch of the library nomenclature though, so I want to wait for the standard solution to align. To keep regular sorters close to their three-way equivalents, I could see something like cppsort::foo_sort.three_way returning a function object whose operator() is overloaded in such a way that it accepts three-way comparators.

This solution would still require to find a way to implement algorithms by reusing the most code though without making them needlessly inefficient for two-way or three-way predicates. Fortunately the number of functions where it makes a difference should be rather small, so in the worst case it should still be possible to special-case small parts of the code.