Several implementations of same struct

help
#1

Hi Rustaceans,

I would like to have several implementations of Ord for the same struct, say:

#[derive(PartialEq, Eq)]
struct Person {
    id: u32,
    name: String,
    height: u32,
}

E.g. order by name vs order by height.
Each implementation will be relevant to a separate struct using Person.
Can I do that in the same compilation unit without the following error ?

error[E0119]: conflicting implementations of trait `std::cmp::Ord` for type Person

Thanks for your help!

#2

I wouldn't recommend doing this, as it makes it unclear what alice < bob means. It's fine just to compare the fields: alice.height < bob.height. Functions that use orderings typically take a by_key variant, e.g. people.sort_by_key(|p| p.height);.

5 Likes
#3

How would you choose which?

  • Either you use your own comparison methods (.cmp_height(), etc.),

  • or you define wrappers that do impl Ord, and it's the usage of the wrapper which can then be used to disambiguate:

    #[repr(transparent)]
pub struct OrderByHeight<T>(pub T);
impl Ord for OrderByHeight<Person> { … }

#[repr(transparent)]
struct OrderByName<T>(pub T);
impl Ord for OrderByName<Person> { … }

  • Or you use an extra type parameter (not recommended, albeit possible):

    use ::core::marker::PhantomData;

#[allow(nonstandard_style)]
mod OrderBy {
    pub enum Height {}
    pub enum Name {}
    pub enum Nothing {}
}

struct Person<OrderBy = OrderBy::Nothing> {
    name: …,
    …,
    _order_by: PhantomData<OrderBy>,
}

impl Ord for Person<OrderBy::Name> { … }
impl Ord for Person<OrderBy::Height> { … }

    • In the future, with const_generics, it will be possible to skip the whole PhantomData ordeal:

      #[derive(PartialEq, Eq)]
enum OrderBy { Height, Name, Nothing }

struct Person<const ORDER_BY: OrderBy> { … }

impl Ord for Person<{ OrderBy::Name }> { … }
impl Ord for Person<{ OrderBy::Height }> { … }
7 Likes
#4

What you can do is write several newtypes for Person, each with its own implementation of PartialOrd and Ord e.g.

struct NamePerson(Person);
// impl PartialOrd and Ord for NamePerson so `PartialOrd` and `Ord` order by name

struct HeightPerson(Person);
// impl PartialOrd and Ord for HeightPerson so `PartialOrd` and `Ord` order by height

@edit: ninja'd by @Yandros

3 Likes
#5

Thanks for your suggestions.
I am working with heaps.
So I would like to have one heap ordered by name and one heap ordered by height.
It seems to me overkill / immoral to define two different types of Persons to this end.
In Java, the problem is solved by passing a custom comparator to the PriorityQueue.

#6

As mentioned above, you don't have to repeat the same definition of Person twice, that's the very point of newtypes.

Rust is not Java, and in Rust, the problem is solved by newtypes. Cf. ordering in descending order – it's also solved by a newtype, Reverse.

2 Likes
#7

What about using slice::sort_by() to pass in your own comparator when re-ordering your heap?

#8

If OP is using std::collections::BinaryHeap then there's no opportunity to pass in a custom comparator; I think newtypes are the blessed solution here.

#9

And what about using tuples and lexicographic ordering? It looks so simpler.

#10

Once you get the grasp of using wrapper types, you can generalize over any kind of comparison function, if you so wish (granted, this would ideally be provided by some library, although as youc an see it can be written by hand):

use lib::BinaryHeapWithCustomComparator;

#[derive(Clone, Debug)]
struct Person {
    id: u32,
    name: String,
    height: u32,
}

fn main ()
{
    let p1 = Person {
        id: 1,
        name: "p1".into(),
        height: 42,
    };
    let p2 = Person {
        id: 2,
        name: "p2".into(),
        height: 27,
    };
    let p3 = Person {
        id: 3,
        name: "p3".into(),
        height: 0,
    };
    let mut heap = BinaryHeapWithCustomComparator::new(
        |p1: &'_ Person, p2: &'_ Person| {
            ::core::cmp::Ord::cmp(&p1.height, &p2.height)
        }
    );
    heap.push(p1.clone());
    heap.push(p2.clone());
    heap.push(p3.clone());
    eprintln!("Tallest person: {:?}", heap.peek().unwrap());
    
    let mut heap = BinaryHeapWithCustomComparator::<Person, _>::new(|p1, p2| {
        ::core::cmp::Ord::cmp(&p1.name, &p2.name)
    });
    heap.push(p1);
    heap.push(p2);
    heap.push(p3);
    eprintln!("By name, the last person is: {:?}", heap.peek().unwrap());
}
2 Likes