`remove` on BTreeMap returns `false` although I know the value exists

help
1

The description of remove for a BTreeMap says "Returns whether the value was present in the set".

I have a BTreeMap that uses the following custom 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 {
        // I'm really confused about how this trait is supposed to work
        // Ideally, I'd just do `other.thing_to_compare.cmp(&self.thing_to_compare)`
        // But that seems to break `contains` because then `contains` will return
        // `true` if there's a value in the set with the same `thing_to_compare` but
        // different `a`
        if self.a == other.a {
            other.thing_to_compare.cmp(&self.thing_to_compare)
        } else if other.thing_to_compare > self.thing_to_compare {
            Ordering::Greater
        } else {
            Ordering::Less
        }
    }
}

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.

Two structs should only be equal if both of their fields are equal.

I'm noticing that if I have a BTreeSet with { a: 5, thing_to_compare: 1 }, then remove will not return that value, even if I pass in {a: 5, thing_to_compare: 1}. Instead the value will remain in the set, and remove will return false.

Am I mis-understanding how the traits for a BTreeSet should be implemented?

2

From the description of what you're trying to do, it sounds like this would work:

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

It will sort by thing_to_compare first, and break ties by looking at a.

EDIT: It appears that the code you posted works just fine, after renaming Foo to PriorityEntry. Can you post some code on the playground that demonstrates the problem you're seeing?

3

The problem with your code is that if self.a != other.a and other.thing_to_compare == self.thing_to_compare then it will always output Ordering::Less and this break the assumption that it's not possible to have both a < b and b < a

You have 2 solutions here:

  • Similar to @2e71828's answer, define your struct as:
#[derive(Debug, Eq,PartialEq,Ord,PartialOrd)]
pub struct PriorityEntry {
    pub thing_to_compare: std::cmp::Reverse<usize>,
    pub a: usize,
}

The difference with its code is that here I use Reverse to swap the order of comparison so that you'll get the same behaviour of other.thing_to_compare.cmp(&self.thing_to_compare)

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

impl Ord for PriorityEntry {
    fn cmp(&self, other: &Self) -> Ordering {
        other.thing_to_compare.cmp(&self.thing_to_compare).then(self.a.cmp(&other.a))
    }
}

// ...