排序
通过从 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
必须彼此一致。