当我无法实现 Ord 时如何使用 BinaryHeap？

Question

我有以下 Rust 特征：

trait Task {
    fn time(&self) -> std::time::Duration;
    fn run(self);
}

我需要将 T: Task 的实例保存在某种排序列表中，我可以在其中弹出 time() 具有最低值的实例。我的计划是使用 BinaryHeap:

fn foo<T: Task>(task: T) {
    let heap = std::collections::BinaryHeap::new();
    heap.push(task);
}

可是，我运行在这里遇到了麻烦。要将某些内容放入 BinaryHeap，它必须实现 Ord:

error[E0277]: the trait bound `T: std::cmp::Ord` is not satisfied
 --> src/lib.rs:7:16
  |
7 |     let heap = std::collections::BinaryHeap::new();
  |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the trait `std::cmp::Ord` is not implemented for `T`
  |
  = help: consider adding a `where T: std::cmp::Ord` bound
  = note: required by `std::collections::BinaryHeap::<T>::new`

我无法为 Task 实现 Ord，因为 Ord 不是我的 crate。而且我也不想，因为 Task 的实现者可能想要 Ord.

的一些其他实现

那我该怎么办？我可以使用其他类型的排序列表吗？或者我可以欺骗 BinaryHeap 使用其他排序规则吗？

Answer 1

如果你想在同一个 BinaryHeap 中有多种类型的 Task（同时），你将需要使用盒装特征对象，或其他一些一种（智能）指针。所以你应该在类型 Box<dyn Task> 上实现 Ord。如果您确实一次只使用一种类型的任务，请参阅下文。

use std::cmp::Ordering;
use std::collections::BinaryHeap;

trait Task {
    fn time(&self) -> std::time::Duration;
    fn run(self);
}


impl PartialEq for Box<dyn Task> {
    fn eq(&self, other: &Self) -> bool {
        self.time() == other.time()
    }
}

impl Eq for Box<dyn Task> {}

impl PartialOrd for Box<dyn Task> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(&other)) // Delegate to the implementation in `Ord`.
    }
}

impl Ord for Box<dyn Task> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.time().cmp(&other.time())
    }
}

然后当您将 Task 插入 BinaryHeap 时，您需要用 Box::new 或类似的东西将其装箱。由于此 Box<dyn Task> 可能比 T 中的任何引用都长，您必须通过将 'static 添加到T.

fn foo<T: Task + 'static>(task: T) {
    let mut heap = BinaryHeap::new();

    let boxed_task: Box<dyn Task> = Box::new(task);
    heap.push(boxed_task);
}

附带说明：您还可以在 dyn Task 上实施 Ord（以及其他）。然后，您将免费获得 Box<dyn Task> 的 Ord 的实现，因为如果 T 实现，Box<T> 实现 Ord。如果您在 Task 中使用 Box<T> 以外的多个指针类型，例如 Rc<dyn Task> 或 &dyn Task.

，这可能很有用

如果您真的一次只使用一种类型，那么您可以使用实现 Ord 的包装器类型。这看起来就像您现在正在做的，因为您只有在手头有特定任务后才创建 BinaryHeap。我不认为这是你想要的，但无论如何它就在这里。

use std::cmp::Ordering;
use std::collections::BinaryHeap;

trait Task {
    fn time(&self) -> std::time::Duration;
    fn run(self);
}

struct TaskWrapper<T: Task>(T);

impl<T: Task> PartialEq for TaskWrapper<T> {
    fn eq(&self, other: &Self) -> bool {
        self.0.time() == other.0.time()
    }
}

impl<T: Task> Eq for TaskWrapper<T> {}

impl<T: Task> Ord for TaskWrapper<T> {
    fn cmp(&self, other: &Self) -> Ordering {
        self.0.time().cmp(&other.0.time())
    }
}

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

使用这种方法，如果 task: T 和 T 实现了 Task，您可以将 task 插入 BinaryHeap，像 [=45] 一样包装它=].

fn foo<T: Task>(task: T) {
    let mut heap = BinaryHeap::new();
    heap.push(TaskWrapper(task));
}

还有一件事。 BinaryHeap 的成员的相对顺序改变是逻辑错误。由于我们这里的排序完全基于方法 time，因此每次调用 time 时排序可能会发生变化。所以即使在这种情况下，我们也必须依赖 time 的正确性外部实现。正是出于这个原因，您想避免使用特征绑定 T: Ord，所以请牢记这一点。

当我无法实现 Ord 时如何使用 BinaryHeap？

How to use a BinaryHeap when I can't implement Ord?

traits

binary-heap

sortedlist

rust