Использует ли BinaryHeap PartialEq только для порядка сортировки или для подлинной эквивалентности?

Question

Я хочу сохранить MyStruct в BinaryHeap, используя мои собственные критерии заказа. Мне нужно реализовать Ord и PartialEq, но будет ли куча использовать PartialEq только для заказа или также будет использовать его, чтобы решить, что MyStruct экземпляр 1 и MyStruct экземпляр 2 логически являются одним и тем же объектом и следовательно, я могу покачивать вещи за моей спиной?

Например, может ли он решить: «Ну, следующий inst2, но у меня уже есть inst1 здесь, в каком-то кеше, и я просто верну его снова»?

Мои экземпляры - очень разные объекты - у них просто одинаковый ключ сортировки.

У меня есть этот код. Это плохо, потому что моя реализация Eq сравнивает только то, что я хочу отсортировать? Я хочу поместить эти объекты в BinaryHeap. В моем текущем коде я помещаю их в Vec и сортирую после каждой вставки, которая является неоптимальной.

type TQIFunc = fn() -> ();

struct TimerQueueItem {
    when: Instant, // when it should run
    name: String,  // for trace only
    what: TQIFunc, // what to run
}

impl Ord for TimerQueueItem {
    fn cmp(&self, other: &TimerQueueItem) -> Ordering {
        other.when.cmp(&self.when)
    }
}

// `PartialOrd` needs to be implemented as well.
impl PartialOrd for TimerQueueItem {
    fn partial_cmp(&self, other: &TimerQueueItem) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

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

impl Eq for TimerQueueItem {}

TQI1 равно TQI2, если они имеют одинаковое значение when - когда на самом деле я просто хочу отсортировать по значению when.

Будет ли BinaryHeap делать другие предположения о равенстве двух вещей, или он просто используется для сортировки? Я согласен с тем, что то, что делает код сегодня, не является хорошим основанием для ответа; Меня больше всего беспокоит то, что BinaryHeap не думает, что TQI1 является логическим клоном TQI2, потому что я утверждаю, что они равны.

Answer 1

В документах для BinaryHeap указано, что это: « очередь с приоритетом, реализованная с помощью двоичной кучи ». Весь смысл очереди с приоритетами состоит в том, что вы можете вставлять разные элементы с одинаковым приоритетом и получать те же элементы обратно. Таким образом, в вашем случае у вас может быть несколько элементов с одинаковым значением when, и они все равно будут разными элементами в очереди. Вы также можете дважды поставить один и тот же элемент в очередь, и вы получите его столько раз, сколько вы его поместили.

Единственное, чего вы не можете гарантировать: если вы вставите несколько сравниваемых элементов равны, то нет гарантии, что вы вернете их обратно.

Answer 2

Rust будет использовать только черту Ord для BinaryHeap (а черта Ord требует черты PartialEq). Вы можете увидеть это в исходном коде , где они просеивают кучу:

fn sift_up(&mut self, start: usize, pos: usize) -> usize {
    unsafe {
        // Take out the value at `pos` and create a hole.
        let mut hole = Hole::new(&mut self.data, pos);

        while hole.pos() > start {
            let parent = (hole.pos() - 1) / 2;
            if hole.element() <= hole.get(parent) {
                break;
            }
            hole.move_to(parent);
        }
        hole.pos()
    }
}

Сравнение выполняется с <=, который использует Ord.