5.2.3. 结构体 Vector 排序

std-badge cat-science-badge

问题:

你想对结构体类型的动态数组 vector 进行排序。

解决方案:

依据自然顺序(按名称和年龄),对具有 nameage 属性的 Person 结构体 Vector 排序。为了使 Person 可排序,你需要四个 traits:EqPartialEqOrd,以及 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: String, age: u32) -> Self {
        Person {
            name,
            age
        }
    }
}

fn main() {
    let mut people = vec![
        Person::new("Zhang".to_string(), 25),
        Person::new("Liu".to_string(), 60),
        Person::new("Wang".to_string(), 1),
    ];
    println!("  排序前: {:?}", people);

    // 根据获得的自然顺序(name 和 age)对 people 进行排序
    people.sort();
    println!("  排序后(name 和 age): {:?}", people);

    assert_eq!(
        people,
        vec![
            Person::new("Liu".to_string(), 60),
            Person::new("Wang".to_string(), 1),
            Person::new("Zhang".to_string(), 25),
        ]);

    // 根据 age 值对 people 进行排序
    people.sort_by(|a, b| b.age.cmp(&a.age));
    println!("  排序后(age): {:?}", people);

    assert_eq!(
        people,
        vec![
            Person::new("Liu".to_string(), 60),
            Person::new("Zhang".to_string(), 25),
            Person::new("Wang".to_string(), 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 == ba != b 严格可逆比较外,等式必须为(对于所有 abc 而言):

  • 自反:a == a
  • 对称:a == b 意味着 b == a;以及
  • 等量代换:a == bb == c 意味着 a == c

PartialEq 是对等式部分进行等价关系比较的 trait。对于没有完全等价关系的类型,实现此 trait 允许部分相等。例如,在浮点数中,NaN != NaN,所以浮点类型实现 PartialEq 而不是 Eq。从形式上讲,等式必须为(对于所有 abc 而言):

  • 对称:a == b 意味着 b == a;以及
  • 等量代换:a == bb == c 意味着 a == c

Ord 是用于构成全序关系类型的 trait。如果是全序关系的排序(对于所有 abc 而言):

  • 完全非对称:a < ba == ba > b 中的一个为真;以及
  • 等量代换:a < bb < c 意味着 a < c。对于 ==>,同样具有等量代换关系。

PartialOrd 是可比较排序规则的 trait。对于所有 abc 而言,比较关系必须满足:

  • 非对称:如果 a < b,那么 !(a > b),以及 a > b 意味着 !(a < b);以及
  • 等量代换:a < bb < c 意味着 a < c。对于 ==>,同样具有等量代换关系。

还有 vec::sort,其对切片进行排序,这种排序是稳定的(即不重新排序相等的元素)。在合适的场景,不稳定排序是首选的,因为它通常比稳定排序快,并且不分配辅助内存。