Stdlib has many `Ord` implementations on things that aren't totally ordered

[apoelstra]

A quick glance at the implementors of Ord

http://doc.rust-lang.org/master/std/cmp/trait.Ord.html

shows that most collections implement it. From discussion on IRC I’ve been told that most of these orderings are probably “lexicographical ordering of all elements in sorted order”, which is not the expected ordering (set inclusion) for most collections. In particular for the -Set types this is wrong.

Apparently Ord is required to use these types as keys in many collections. This also seems wrong to me. Why isn’t PartialOrd sufficient for keying?

Should these implementations be dropped?

[apoelstra]

I see, a partial ordering is not enough to reliably search for keys. Imagine doing a binary search on a set with the trivial partial ordering (nothing compares to anything).

[ A, B, C, D, E, F, G ]

To find A: check is A <= D (no), so restrict the search to [ E, F, G ] and you can see that we’ve already failed.

So in the case of keying it makes sense to have an “arbitrary total ordering” just for the sake of having a total ordering; on the other hand, the exact ordering will not make sense for objects that don’t have a natural total ordering. This is an unfortunate state of affairs and it’s not clear to me what should be done about it.

[Gankro]

Whoops, made an issue for this before I saw this thread pop up.

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.