Why do all sorted Data Structures only allows types that implement `Ord`

I'm writing an informed search algorithm and need to organize nodes based on distances from A to B. These distances are float point values. Started looking into sorted Data Structures in the standard library and found out that all of them (BinaryHeap, BTreeSet/Map, PriorityQueue) require the score to implement Ord while float point values in Rust only implement PartialOrd so those DS can't be used with float values.

Please correct me if I misunderstood something. Can someone explain to me how come so?

Also, Is there a standard solution to this, or I should look for external crates or implement my version of it?

If you want to sort your data, you need to be able to say "does a go before b?" For types like integers this is well defined and you will always get an answer (represented with the Ord trait).

However, because floats may include NaNs, sometimes you will ask that question and it'll say "I dunno", at which point you are in a bit of a pickle and can't continue. Hence the Partial bit in PartialOrd... Floats are mostly ordered, except when they aren't.

The typical solution is to provide your own definition for float ordering.

One way to do achieve this is by passing in your own comparison function. For example, if you just want your program to blow up when its floats aren't ordered (e.g. because the presence of NaN indicates a programming error), you might do something like vec_of_floats.sort_by(|left, right| left.partial_cmp(right).expect("Unable to sort floats")). You can choose to handle NaNs any other way you choose, but making sure your code works correctly for both NaN < x and x < NaN may be tricky.

There are newtype wrappers around floats that will do something similar for you, defining an Ord implementation which is useful for sorting purposes even if it doesn't follow the IEE 754 floating point spec. One example is the ordered_float crate which implements Ord by saying all NaNs are equal to each other and greater than any other float value.

The difference between a newtype wrapper and a custom comparison is that the newtype will force you to change what your datastructure holds. Instead of having a Vec<f32> you would have a Vec<OrderedFloat<f32>>, which may impact your public API or be annoying.

11 Likes

Another option is Noisy_float — Rust math library // Lib.rs, if you're confident you don't actually have any NANs in your data.

6 Likes

To be clear, that's only possible in sort_by functions and your own home-cooked sorted vector. None of the sorted data structures in Rust's standard library allow that, right?

Yeah, datastructures like BTreeMap will use the type's Ord implementation for keeping things ordered.

Well, you "pass in" your comparison function by using a newtype. So, for example, BinaryHeap<T> is a max-heap, but if you want a min-heap you use BinaryHeap<Reverse<T>>.

3 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.