How do I select different std::cmp::Ord (or other trait) implementations for a given type?

Question

I'm trying to use std::collections::BinaryHeap with a custom struct. In order to do so, I have to have my struct implement the std::cmp::Ord trait, but what I need is 2 BinaryHeaps of the same structs but ordered differently.

Is there a way to define 2 Ord implementations & pick which Ord gets used, or some other way to specify an alternate ordering?

I think I could define 2 different wrapping structs which keep a reference to the original custom struct and have an implementation of Ord for each of them, but it seems quite wasteful to have to construct potentially a lot of instances of such wrapping structs.

In Pyhton/Java I'd provide a sorting function/Comparator, but there seems no facility like that. In Scala, I can define a compile-time only type to select the right implicit Ordering implementation; it feels like Rust supports something similar, but I haven't been able to work it out.

If you're going to have two binary heaps, you would need two binary heaps in any language, and need to fill both with their own (references) to the structs/objects. What's the problem? — user395760
@delnan The problem was not having 2 heaps, but that each heap needs to use different orderings for the same type. Since afaik Rust enforces a 1:1 mapping between types and traits (including between my struct and Ord), it wasn't clear to me how I should handle that. — Caspar

huon huon · Accepted Answer · 2015-02-28T13:08:13

There's no way to have two different implementations of the same trait for a single type, e.g. this hypothetical scheme doesn't work

struct MyType { ... }
mod foo {
    impl Ord for MyType { ... } // A

    // everything in here uses the A implementation
}
mod bar {
    impl Ord for MyType { ... } // B

    // everything in here uses the B implementation
}

If you want different behaviours with BinaryHeap you do have to just use wrapper types, however, wrapper types are not wasteful, since there is no additional indirection or memory use, struct Foo { data: T } and T are same, other than the nominal type name (no matter what type T is).

How do I select different std::cmp::Ord (or other trait) implementations for a given type?

1 Answers