排序

通过从 Vec 转换到 HashMap,我们提升了工单管理系统的性能,并在此过程中简化了代码。然而,并非一切都完美无瑕。当遍历基于 Vec 的存储时,我们可以确保工单按照添加的顺序返回。而对于 HashMap 来说则并非如此:你能够遍历工单,但是顺序是随机的。

我们可以通过将 HashMap 替换为 BTreeMap 来恢复一致的排序。

BTreeMap

BTreeMap 保证了条目按其键的顺序排列。当你需要按照特定顺序遍历条目,或者需要执行范围查询(例如,“给我所有ID在10到20之间的工单”)时,这一点非常有用。

HashMap 一样,在 BTreeMap 的定义上你找不到特征界限,但是在其方法上可以找到。我们来看一看 insert 方法:

#![allow(unused)]
fn main() {
// `K` 和 `V` 分别代表键和值的类型,和在 `HashMap` 中一样。
impl<K, V> BTreeMap<K, V> {
    pub fn insert(&mut self, key: K, value: V) -> Option<V>
    where
        K: Ord,
    {
        // 实现细节
    }
}
}

不再需要 Hash,取而代之的是键的类型必须实现 Ord 特征。

Ord

Ord 特征用于比较值。当 PartialEq 用于判断相等时,Ord 则用于比较大小顺序。

它定义在 std::cmp 中:

#![allow(unused)]
fn main() {
pub trait Ord: Eq + PartialOrd {
    fn cmp(&self, other: &Self) -> Ordering;
}
}

cmp 方法返回一个 Ordering 枚举,可以是 LessEqualGreater 中的一个。Ord 还要求实现另外两个特征:EqPartialOrd

PartialOrd

PartialOrdOrd 的弱化版本,就像 PartialEqEq 的弱化版本一样。通过查看其定义可以理解这一点:

#![allow(unused)]
fn main() {
pub trait PartialOrd: PartialEq {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering>;
}
}

PartialOrd::partial_cmp 返回一个 Option —— 并不保证两个值可以被比较。例如,f32 不实现 Ord 因为 NaN 值不可比较,这也是 f32 不实现 Eq 的原因。

实现 OrdPartialOrd

OrdPartialOrd 都可以为你的类型自动生成:

#![allow(unused)]
fn main() {
// 需要同时添加 `Eq` 和 `PartialEq`,因为 `Ord` 要求它们。
#[derive(Eq, PartialEq, Ord, PartialOrd)]
struct TicketId(u64);
}

如果你选择(或需要)手动实现它们,请务必小心:

  • OrdPartialOrd 必须与 EqPartialEq 保持一致。
  • OrdPartialOrd 必须彼此一致。