5.2.3. 结构体 Vector 排序
问题:
你想对结构体类型的动态数组 vector 进行排序。
解决方案:
依据自然顺序(按名称和年龄),对具有 name
和 age
属性的 Person 结构体 Vector 排序。为了使 Person 可排序,你需要四个 traits:Eq
、PartialEq
、Ord
,以及 PartialOrd
。这些 traits 可以被简单地派生。你也可以使用 vec:sort_by
方法自定义比较函数,仅按照年龄排序。
以下实例代码引用自开源书籍项目《Cookin’ with Rust》,笔者在其基础上稍作修改。
#[derive(Debug, Eq, Ord, PartialEq, PartialOrd)] struct Person { name: String, age: u32 } impl Person { pub fn new(name: &str, age: u32) -> Self { Person { name: name.to_string(), age } } } fn main() { let mut people = vec![ Person::new("Zhang", 25), Person::new("Liu", 60), Person::new("Wang", 1), ]; println!(" 排序前: {:?}", people); // 根据获得的自然顺序(name 和 age)对 people 进行排序 people.sort(); println!(" 排序后(name 和 age): {:?}", people); assert_eq!( people, vec![ Person::new("Liu", 60), Person::new("Wang", 1), Person::new("Zhang", 25), ]); // 根据 age 值对 people 进行排序 people.sort_by(|a, b| b.age.cmp(&a.age)); println!(" 排序后(age): {:?}", people); assert_eq!( people, vec![ Person::new("Liu", 60), Person::new("Zhang", 25), Person::new("Wang", 1), ]); }
代码第 1-5 行,创建结构体类型 Person
,并为其派生一系列宏 Debug, Eq, Ord, PartialEq, PartialOrd
。
代码第 14 行,为结构体类型 Person
实现 new
方法。并且在代码第 17-21 行,使用 new
方法绑定值到结构体 people
。
代码第 25 行,根据自然顺序,即为全部值 name 和 age,对结构体 people
进行排序。
代码第 37 行,仅根据 age 值对结构体 people
进行排序,在 sort_by
方法中通过闭包,指定排序依据 age 值。
构建并运行后,结果大抵如下所示。
排序前: [Person { name: "Zhang", age: 25 }, Person { name: "Liu", age: 60 }, Person { name: "Wang", age: 1 }]
排序后(name 和 age): [Person { name: "Liu", age: 60 }, Person { name: "Wang", age: 1 }, Person { name: "Zhang", age: 25 }]
排序后(age): [Person { name: "Liu", age: 60 }, Person { name: "Zhang", age: 25 }, Person { name: "Wang", age: 1 }]
断言的使用和整型 vector 排序类似,不再赘述。
讨论:
Eq
是对等式进行等价关系比较的 trait。这意味着,除了 a == b
和 a != b
严格可逆比较外,等式必须为(对于所有 a
、b
和 c
而言):
- 自反:
a == a
; - 对称:
a == b
意味着b == a
;以及 - 等量代换:
a == b
和b == c
意味着a == c
。
PartialEq
是对等式部分进行等价关系比较的 trait。对于没有完全等价关系的类型,实现此 trait 允许部分相等。例如,在浮点数中,NaN != NaN
,所以浮点类型实现 PartialEq
而不是 Eq
。从形式上讲,等式必须为(对于所有 a
、b
和 c
而言):
- 对称:
a == b
意味着b == a
;以及 - 等量代换:
a == b
和b == c
意味着a == c
。
Ord
是用于构成全序关系类型的 trait。如果是全序关系的排序(对于所有 a
、b
和 c
而言):
- 完全非对称:
a < b
,a == b
或a > b
中的一个为真;以及 - 等量代换:
a < b
和b < c
意味着a < c
。对于==
和>
,同样具有等量代换关系。
PartialOrd
是可比较排序规则的 trait。对于所有 a
、b
和 c
而言,比较关系必须满足:
- 非对称:如果
a < b
,那么!(a > b)
,以及a > b
意味着!(a < b)
;以及 - 等量代换:
a < b
和b < c
意味着a < c
。对于==
和>
,同样具有等量代换关系。
还有 vec::sort
,其对切片进行排序,这种排序是稳定的(即不重新排序相等的元素)。在合适的场景,不稳定排序是首选的,因为它通常比稳定排序快,并且不分配辅助内存。