排序

通过从 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 枚举，可以是 Less、Equal 或 Greater 中的一个。Ord 还要求实现另外两个特征：Eq 和 PartialOrd。

PartialOrd

PartialOrd 是 Ord 的弱化版本，就像 PartialEq 是 Eq 的弱化版本一样。通过查看其定义可以理解这一点：

#![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 的原因。

实现 Ord 和 PartialOrd

Ord 和 PartialOrd 都可以为你的类型自动生成：

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

如果你选择（或需要）手动实现它们，请务必小心：

• Ord 和 PartialOrd 必须与 Eq 和 PartialEq 保持一致。
• Ord 和 PartialOrd 必须彼此一致。