Error with simple sort implementation


#1

I’m learning Rust, and I think I’m missing a piece of the puzzle when it comes to implementing traits.

In particular, I do not understand why my implementation of Ord fails in the following example. Why is defining cmp insufficient?

Thank you very much!

https://play.rust-lang.org/?gist=db67d664bab20543fa4c&version=stable


#2

"the trait core::cmp::Eq is not implemented for the type Item "… "required by core::cmp::Ord"

Basically, you can’t implement Ord for a type unless it implements both Eq and PartialOrd. See https://doc.rust-lang.org/std/cmp/trait.Ord.html.

Do you have any suggestions for making the error message more clear?


#3

Okay, I implemented the Eq, PartialEq, and PartialOrd traits as well as Ord. Then it compiled. Source code is at https://play.rust-lang.org/?gist=e4c5e58609ef4ff2e3ad&version=stable

The way I understand it is this:
Vec::sort() depends on Ord.
Ord depends on Eq and PartialOrd.
Eq and PartialOrd both depend on PartialEq.

I thought I could just implement Ord for my type, and that would satisfy Vec::sort(). Certainly the other traits are implemented for the type of key, which is u64.

It seems weird to me that there’s so much boilerplate required for this.

Is there a better way to do it?

@eefriedman I’ll suggest a clearer error message once I understand what I’m doing wrong :slight_smile:


#4

Why isn’t implementing Ord enough to sort? I agree it’s too much boilerplate required.


#5

I can’t help but feel this is just approaching the issue in the wrong way. The Eq and Ords you’ve defined for Item don’t seem right. Really, seems like you should be using <[_]>::sort_by:

use std::cmp::Ordering;

struct Item {
    key: u64,
    value: u64,
}

impl Item {
    fn cmp_key(&self, other: &Self) -> Ordering {
        self.key.cmp(&other.key)
    }
}

fn main() {
    let mut v: Vec<Item> = Vec::new();
    v.sort_by(Item::cmp_key);
}

I mean, if it weren’t for the somewhat weird situation of comparing the keys but not the values, you could’ve just #[derive(...)]'d all of those traits.

Beyond that, it doesn’t really make any sense to have something that’s orderable but not comparable for equality, or something that’s totally ordered whilst somehow not being partially ordered.


#6

One of the things I don’t understand is why implementing Ord wouldn’t provide Eq, too. Why is that? Ordering::Equal says just that, after all. Is that just an implementation detail?


#7

At this point, it’d be backwards incompatible, so it doesn’t really matter what the original reason is/was, if there even was one. It ain’t happening.

Personally, I’d find it a bit weird that implementing Ord, which depends on Eq, causes an implementation of Eq to suddenly appear.


#8

There’s Ordering::Equal, it’s enough for equality. Shouldn’t the implementation of Eq be just an optional performance optimization?
If some data can be totally ordered, shouldn’t the compiler be able to derive a partial ordering?

Rust V.1.0 is quite young, so I think it needs invent some ways to manage breaking changes. Success should be delayed :wink:


#9

Maybe it doesn’t really solve the issue, but there has been suggested meta-deriving attributes (derive multiple traits with one directive).

A meta deriving attribute with an optional argument like #[derive(Comparable="key")] that derives all the comparison traits (and Hash) based upon the specified struct field(s) would be very useful.


#10

This has already been discussed to death and back again. Short version: it ain’t happening. There are a lot of people that care very much about Rust being stable. The whole point of 1.0 was to promise backward compatibility. Going back on that now would be, in my opinion, catastrophically damaging to Rust’s reputation.

I still remember being bitten by the empty promise of backward compatibility with D 1.0. It meant I never really trusted the language ever again.

Either way, this isn’t even an issue in 99% of cases. Most of the time, you just derive all the comparison traits and you’re done. If you need something more complicated, you can just implement Ord, then write the others in terms of that. Heck, you could pretty trivially write a macro to do it.

Could totally do that right now with custom_derive! :stuck_out_tongue:


#11

:stuck_out_tongue:
:droplet:
:droplet:


#12

The single key field case is very simple with custom_derive, subject to its limitations (no type parameters). Still very cool.