It will return Some(Less)
if partial_cmp
return None
.
So, no NaN
in this case.
First, get rid of some bound checks. Second, instead of comparing by ternary …
It will return Some(Less)
if partial_cmp
return None
.
So, no NaN
in this case.
And what should sort()
do when it asks "is this item before that one?" and gets None
instead of a yes/no answer?
Your only options are:
Result
to indicate that sorting was unsuccessfulsort()
All three options are equally terrible, so instead of making sort()
do the wrong thing out of the box the standard library force developers to handle the fact that their type can't be properly ordered. Hence the T: Ord
requirement instead of T: PartialOrd
.
In these situations, you can use the slice::sort_by()
method to provide your own comparison logic (e.g. my_floats.sort_by(|left, right| left.partial_cmp(right).unwrap_or(Ordering::Less))
).
impl PartialOrd for S {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
if self.a == other.a {
return other.b.partial_cmp(&self.b);
}
self.a.partial_cmp(&other.a)
}
}
impl Ord for S {
fn cmp(&self, other: &Self) -> Ordering {
if self.a == other.a {
return self.b.cmp(&other.b);
}
self.a.cmp(&other.a)
}
}
The partial_cmp(PartialOrd)
is the right one that I want. cmp(Ord)
's order is reversed.
But sort
works as expected.
This is so confusing. sort
didn't depend on Ord
's implementation.
the standard library force developers to handle the fact that their type can't be properly ordered
So I don't think this is a good idea.
This isn't a mathematically sound implementation of Ord
given the implementation of PartialOrd
. Rust, though, has no way of preventing you from doing it.
I don't think it's a good idea for your PartialOrd
and Ord
implementations to behave differently. In particular, you are actually violating Ord
's invariants:
Implementations must be consistent with the
PartialOrd
implementation, and ensuremax
,min
, andclamp
are consistent withcmp
:
partial_cmp(a, b) == Some(cmp(a, b))
.max(a, b) == max_by(a, b, cmp)
(ensured by the default implementation).min(a, b) == min_by(a, b, cmp)
(ensured by the default implementation).- For
a.clamp(min, max)
, see the method docs (ensured by the default implementation).
Normally if your type implements both, you'll implement one in terms of the other.
struct Foo { ... }
impl Ord for Foo {
fn cmp(&self, other: &Self) -> Ordering { ... }
}
impl PartialOrd for Foo {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) }
}
If you want your sorting to be reversed, then provide your own comparison which explicitly reverses the ordering - slice.sort_by(|a, b| b.cmp(a))
.
Decades of industrial experience and probably hundreds or thousands of CVEs disagree with you.
Yes, there is a bug in my Ord
's implementation. But sort()
works well and I didn't find this bug before.
So, I think sort()
require PartialOrd
would be better.
This one persuades me.
Yep, also some historical reasons. That makes sense.
https://stackoverflow.com/questions/70588237/why-sort-need-t-to-be-ord/70588789#70588789
That is very surprising. While technically fine because requirements say this is equivalent to using cmp
when Ord
is implemented, I think it should be nevertheless changed to use Ord::cmp
.
Let's look at this from a mathematical p.o.v.
There are partial orders and weak orders (in form of a "strict weak order", or a "non-strict weak order", of which the latter is also called "total preorder", see linked Wikipedia article).
IMHO sorting a slice based on a partial order usually makes no sense because there could be two subsets which each can be sorted, but there is no relation between two elements when each of these elements is in a different of the two subsets.
For example:
We could define a partial order where equal currencies can be compared, while different currencies don't compare. Possible sorting results could be:
I would claim that it is semantically wrong to call this "sorting" the list. I would say you could "partially" sort it (which is something different than an "unstable" sort).
However, if we have a weak order, e.g. ordering rectangles based on their area, then we could easily sort these. But there is no trait for a weak order in Rust!
I mean, you totally can do the sort though:
rects.sort_by_key(|rect| rect.area());
OK I see what the reason for this is:
First, get rid of some bound checks. Second, instead of comparing by ternary …
It's faster when lt()
can do less work than cmp
when it's specialized.
I'm not sure why it's actually (very slightly) faster for built-in types, according to that ticket, since the compiler should be able to see the two ways to compare built-in types are equivalent.
Yes, but you can't do this with .sort
(which uses Ord
) unless you make two rectangles with the same area equal.
Thus there is no trait to represent the weak ordering. It's represented through the closure |rect| rect.area()
instead.
P.S.: My screaming smiley was an exaggeration. I guess there isn't really a need to introduce a trait for weak orders, as these can always be achieved easily through a sorting key like you suggested. I just wanted to point out that PartialOrd
shouldn't be confused with WeakOrd
(which doesn't exist).
Could you expand on there is no trait for a weak order in Rust? If there are partial orders and those are PartialOrd
, and there are weak orders but those are not Ord
, then what is Ord
?
However, if we have a weak order , e.g. ordering rectangles based on their area, then we could easily sort these. But there is no trait for a weak order in Rust!
IMO, Ord
is definitely a trait for weak orders. It's just incorrectly documented (it should say "total preorder", yet it does say "total order" im the docs). Look at Eq
which is correctly documented as a trait for equivalence relations, not for equality. The distinction between stable and unstable sorting algorithms only really makes sense for weak orders, too. (The German version of the Wikipedia article also does point that out.)
(The use of "total order" in the docs makes some sense if the equivalence by the Eq
implementation is (mis-)interpreted as equality. After all, a total preorder is the same as an actual total order on the equivalence classes.)
I'm not sure why it's actually (very slightly) faster for built-in types, according to that ticket, since the compiler should be able to see the two ways to compare built-in types are equivalent.
Because that was before C++20. I'm not joking.
GCC got the appropriate optimization only very recently, I wouldn't be surprised that LLVM was also missing it at the time when bug was created.
If there are partial orders and those are
PartialOrd
, and there are weak orders but those are notOrd
, then what isOrd
?
According to the documentation, Ord
is a total order. That also makes sense to me, because it will always compare an element to another element as either being smaller or greater, unless it is equal.
IMO,
Ord
is definitely a trait for weak orders. It's just incorrectly documented (it should say "total pre-order", yet it does say "total order" im the docs).
Isn't a weak order the same as a total order if we simply put all non-comparable items in the same equivalence class? Maybe these two are actually the same and it's just a semantic difference?
Now I'm confused
But I just noticed that a "total order" indeed depends on how equality is defined (or a used equivalence relation). And the Ord
trait does require that equality (or a certain equivalence relation defined through Eq
) does behave in a certain way.
Look at
Eq
which is correctly documented as a trait for equivalence relations, not for equality.
Yes, Eq
could be any equivalence relation.
(The use of "total order" in the docs makes some sense if the equivalence by the
Eq
implementation is (mis-)interpreted as equality. After all, a total preorder is the same as an actual total order on the equivalence classes.)
Now the question is… Is the equality / non-equality operator here an arbitrary equivalence relation? I would say yes, because we're not operating with numbers or any particular objects here in the mathematical definition. If yes, then I'd say Ord
can be seen as "total order".
My point is: Ord
interacts with Eq
, and thus I'd say it's correct to describe it as total order.
Could you expand on there is no trait for a weak order in Rust?
I would say:
Ord
unambiguously sorts all elements (unless some elements are equal to one another according to Eq
, in which case their sorting can vary).WeakOrd
(which doesn't exist) could treat some elements as "equal in regard to the sorting", independently on how Eq
(==
operator) is defined for that type.PartialOrd
can treat some elements as "could appear anywhere in the list". Floating point numbers have a partial order, because NaN could appear anywhere in a sorted list.Is the equality / non-equality operator here an arbitrary equivalence relation?
No, it's not an arbitrary equivalence relation.
I would say yes, because we're not operating with numbers or any particular objects here in the mathematical definition.
Mathematical notion of equality is defined for all mathematical objects. On a fundamental level in first-order logic you already have a notion of equality. It asserts basic properties like the ability to always being able to substitute equal things with equal things in statements or expressions. This it related to the notion of equality by Leibniz which basically says that things are equal if and only if they have the same properties. Or if you take a set theoretic foundation, that comes with a more concrete notion of equality by means of sets having the same elements.