BTreeSet contains value (with custom Ord implementation) and falsely returns true for `contains`

user_3847117 0
Viewed 190

I have a BTreeSet that stores values of type:

#[derive(Debug, Eq)]
pub struct Foo {
    pub a: usize,
    pub thing_to_compare: usize,
}

impl Ord for PriorityEntry {
    fn cmp(&self, other: &Self) -> Ordering {
        // Sort in reverse order
        other.thing_to_compare.cmp(&self.thing_to_compare)
    }
}

impl PartialOrd for PriorityEntry {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl PartialEq for PriorityEntry {
    fn eq(&self, other: &Self) -> bool {
        self.a == other.a && self.thing_to_compare == other.thing_to_compare
    }
}

The idea is that the structs in the BTreeSet should be sorted by thing_to_compare and the a field is just additional information.

I'm noticing that if I have a BTreeSet with

{ a: 0, thing_to_compare: 0 }

then contains will return true for

{ a: 1, thing_to_compare: 0 }

I'm guessing that it returns true because cmp will return Ordering::Equal for the two values since they have the same thing_to_compare. What I'm confused about is why the BTreeSet doesn't use the auto-generated Eq trait or PartialEq trait to check if the value exists inside of itself.

Afterall, I assume that the Ord trait should only be relevant to sorting and not whether two values are the same.

rust traits
2 Answers

The docs for Ord say:

Implementations of PartialEq, PartialOrd, and Ord must agree with each other. It's easy to accidentally make them disagree by deriving some of the traits and manually implementing others.

In other words, you need to ensure that (a == b) == (a.cmp(b) == Ordering::Equal) because other code (e.g. BTreeSet) is allowed to assume that this property holds; otherwise you can get incorrect (but not unsafe) behavior.

user_33988390

The idea is that the structs in the BTreeSet should be sorted by thing_to_compare

Sorting is how btrees are internally organised, as with Hash/Eq for HashSets. This means that thing_to_compare is your BTreeSet's "identity" information, it's not just a surface-level display or iteration order.

What I'm confused about is why the BTreeSet doesn't use the auto-generated Eq trait or PartialEq trait to check if the value exists inside of itself.

Because why would it? Ord is what it requires and what it uses to probe itself internally. If your Ord is broken then forget equality, the entire set will be internally inconsistent.

user_81821180
Related