Structure with sorted elements, get first and remove in the middle

Hello!
I need a special data structures that contains structures like

pub struct __ {
    pub ___: usize,
    pub ___: f64,
}

I need it to be sorted by f64.
Also I need to get lowest element of it and be able to remove and find elements by usize.

I can't use BTreeSet as first_entry is still experimental
Also I can't use BinaryHeap because it cannot remove elements from middle.

Can you suggest me any solution for this?

You can have btreeset.first() by calling btreeset.iter().next().

To have your struct sorted by the f64 field you will have to manually implement Ord and PartialOrd traits on it.

3 Likes

To expand on @kornel's answer, note that correctly implementing Ord for an f64 field can be difficult, since NaNs cannot be normally compared with any other value. One option would to be adopt ordered-float's convention, where all NaNs are equal to each other and greater than all numbers:

use std::cmp::Ordering;

pub struct MyData {
    pub key: usize,
    pub value: f64,
}

impl PartialEq for MyData {
    fn eq(&self, other: &Self) -> bool {
        if self.value.is_nan() {
            other.value.is_nan()
        } else {
            self.value == other.value
        }
    }
}

impl Eq for MyData {}

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

impl Ord for MyData {
    fn cmp(&self, other: &Self) -> Ordering {
        if let Some(ordering) = self.value.partial_cmp(&other.value) {
            ordering
        } else if !self.value.is_nan() {
            Ordering::Less
        } else if !other.value.is_nan() {
            Ordering::Greater
        } else {
            Ordering::Equal
        }
    }
}
2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.