Pre-RFC: std::cmp::NoOrder

When working with some data structures like BinaryHeap with tuples, I might only wanted to sort by the first value, but no not care about the second (like sort by score with name as data BinaryHeap::<(u32,String)>). This means that the binheap have to sort on a potentially expensive cmp call when the ordering of the second parameter does not really matter. Right now you have to create a boilerplate struct for very simply tuples like this to implement a fast ordering on tree-like data structures.

However the std already have helper types for ordering, like the Reverse wrapper. I would like to extend this to also include some transparent wrapper like NoOrder that is always equals to any other NoOrder, as then the compiler can ignore that value when sorting. When testing I found it to be faster, even on primitive types.

So, a transparent wrapper with Deref/DerefMut that overrides PartialOrd to always return None?

Yes, that would be one implementation. However most data structures that benefit from this require Ord, like impl<T: Ord> BinaryHeap<T>. Therefore I am thinking Ord where it always returns std::cmp::Ordering::Equal even if the content is different.

Seems reasonable. I think the initial implementation should start out in a third-party crate, but it might make sense for the standard library if it proves to be widely used.

Makes sense, might publish a crate for it then, because I see more than a 25% speedup in graph traversal algorithms like Dijkstra's.

I think the obvious alternative to consider here is the long-lasting conversation about just adding a Comparer parameter to all these things. If you could just include a "compare by key" or "compare reversed" or similar in the type or instance then it'd also be easier to insert and extract things from the heap.

@VincentLagerros

PartialOrd and Ord need to be consisant, so this would need to be two wrappers, one that makes partial_cmp always return None, and one that makes cmp always return Equal.

Should Ord and Eq/PartialEq be consistent as well? if Ord is overriden to always be equal but Eq still does a comparison does it break any data structures?

Yes they should. It’s documented. On Ord:

Implementations must be consistent with the PartialOrd implementation

and on PartialEq:

The methods of this trait must be consistent with each other and with those of PartialEq.

(And the Eq trait doesn’t have methods.)

Yes, can break any current or future data structure inside or outside of std that relies on these stably established correctness properties; for anything but memory safety:

Violating these requirements is a logic error. The behavior resulting from a logic error is not specified, but users of the trait must ensure that such logic errors do not result in undefined behavior. This means that unsafe code must not rely on the correctness of these methods.

I just ran into this issue this week. Using BinaryHeap with an ordering index where the other data actually couldn't implement ordering meaningfully, so I just manually pretty arbitrarily implemented PartialEq, Eq, PartialOrd and Ord for the other data type since that was simplest. A wrapper type for that would have been helpful.

An alternative is to add an #[cmp(ignore)] attribute to the derive macros:

#[derive(PartialEq, PartialOrd)]
struct Foo {
    first: u32,
    #[cmp(ignore)]
    second: String,
}

Hash is also relevant. If all values of NoOrder<T> are considered equivalent, a no-op Hash-impl seems appropriate.

Spelled #[ignore(Ord)] (or skip would be my bikeshed color) because it’s a general tool that would be super handy with many other derives too, including third-party ones.

Helper attributes like #[serde(ignore)] are already in use, let's follow this convention. I don't see a need for a more "general" tool.

I proposed to name it #[cmp(ignore)] rather than #[ord(ignore)] because it affects both PartialOrd and PartialEq. The name cmp feels correct because both traits compare things.

I have now published the crate on crates.io: Rust Package Registry for what I believe the api should look like and behave. It is nothing fancy, and only like 40 loc, but works as a proof of concept.

to throw my bikeshed into the ring, if we're doing the wrapper type scheme, I think they should be named AlwaysEq and Incomparable.

Alternatively add a KeyValuePair<K, V> struct, which only compares the key but not the value using all the relevant traits (PartialEq, Eq, Hash, PartialOrd, Ord)

Is your deriving Debug, Default, Copy on NoOrder<T> imposing an unnecessary constraint on T and would a custom implementation expressing that constraint be better for a library?

Nice work.

This would be great for getting correct generic bounds from derive macros. RFC for derive-no-bounds didn't get approved, so that's another opportunity.

#[derive(PartialOrd, Ord)]
struct Kv<T> {
    k: u32,
    #[ignore(Ord)]
    v: T,
}

This can implement Ord for Kv<f32>.

A field wrapper like Uncomparable<T> couldn't be taken into account, and #[derive] would still add a T: Ord requirement, because macros can't understand types. ^[1]

1. 3rd party macros that seem to understand types cheat by matching exact names, and fail on use Type as SomeOtherName ↩︎

Actually no, this uses the same derives as std::cmp::Reverse and derives on generic structs only apply when T also has it. This means that it works on a struct that derives nothing, but allows for writing eg Default::default(); if T implements Default.

You can try it out here Rust Playground