You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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.
The text was updated successfully, but these errors were encountered:
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.
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 ofthree_way_compare
from the library's internals:three_way_compare
had no extension mechanism for user-defined types whileoperator<=>
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 fromstd::string::compare
, so getting rid of it should lead to some compile-time benefits too.Frankly
three_way_compare
is only used intim_sort
andgrail_sort
today. That said,tim_sort
doesn't benefit from a three-way comparison, and I need to check forgrail_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:
operator<=>
if needed but might have been specialized to be more efficient?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
anda > 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:quick_sort
for a basic three-way partitioningham
grail_sort
in some placesstable_compare
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 conceptThreeWayComparable
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.The text was updated successfully, but these errors were encountered: