Bài 164: PartialOrd, Ord — Ordering Traits

Sau bài học, bạn sẽ:

• Phân biệt PartialOrd (partial order, cho phép cặp không comparable) và Ord (total order, mọi cặp đều xếp được).
• Hiểu method partial_cmp(&self, other) -> Option<Ordering> vì sao bọc Option — chính là chỗ trả None khi không có thứ tự (NaN).
• Hiểu method cmp(&self, other) -> Ordering không có Option — total order cam kết luôn có kết quả, và vì sao Ord require Eq + PartialOrd.
• Nắm enum Ordering { Less, Equal, Greater } — return type của cmp và partial_cmp, có chain then / then_with để so sánh nhiều field.
• Hiểu vì sao f32, f64 chỉ impl PartialOrd, không impl Ord — và workaround total_cmp hoặc crate ordered-float.
• Dùng #[derive(PartialOrd, Ord, PartialEq, Eq)] gộp 4 trait — sort lexicographic theo thứ tự field khai báo.
• Tự viết impl Ord để sort theo một field cụ thể (ví dụ priority) mà không bị ràng buộc bởi field order.
• Phân biệt Vec::sort() (cần T: Ord), sort_by (closure trả Ordering), sort_by_key (extract key có Ord).

PartialOrd là trait nền cho các operator so sánh <, >, <=, >=. Định nghĩa (rút gọn) trong std::cmp:

pub trait PartialOrd: PartialEq {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering>;

    fn lt(&self, other: &Self) -> bool { /* dùng partial_cmp */ }
    fn le(&self, other: &Self) -> bool { /* dùng partial_cmp */ }
    fn gt(&self, other: &Self) -> bool { /* dùng partial_cmp */ }
    fn ge(&self, other: &Self) -> bool { /* dùng partial_cmp */ }
}

Method cốt lõi là partial_cmp, trả Option<Ordering> — bọc Option vì có thể không tồn tại thứ tự giữa self và other. Khi nào không tồn tại? Khi hai giá trị thuộc một "partial order" — một số cặp xếp được, một số cặp thì không. Ví dụ kinh điển là f64::NAN: không nhỏ hơn ai, không lớn hơn ai, không bằng ai, kể cả chính mình. So sánh NaN < 1.0 không trả true cũng không trả false theo nghĩa "Less" — kết quả là None tại tầng partial_cmp, và operator < trả false cho tất cả các quan hệ với NaN.

Một type chỉ impl PartialOrd là cách Rust mô hình hoá khái niệm "phép so sánh có thể fail" ngay trong type system. Khi bạn viết a < b, compiler chỉ cần PartialOrd; không cần biết quan hệ là total hay partial.

Ord là tầng mạnh hơn: total order — mọi cặp giá trị đều xếp được thứ tự, không tồn tại "không comparable":

pub trait Ord: Eq + PartialOrd {
    fn cmp(&self, other: &Self) -> Ordering;

    fn max(self, other: Self) -> Self { /* ... */ }
    fn min(self, other: Self) -> Self { /* ... */ }
    fn clamp(self, min: Self, max: Self) -> Self { /* ... */ }
}

Khác biệt then chốt với PartialOrd: method cmp trả thẳng Ordering, không có Option. Vì Ord cam kết total order — luôn so sánh được — không cần variant None để biểu diễn "không xếp được". Đây là sự khác biệt quan trọng nhất giữa hai trait.

Ord require Eq + PartialOrd: total order kéo theo equality reflexive (x == x luôn đúng — Eq) và kéo theo partial order (PartialOrd) như một trường hợp đặc biệt. Bạn không thể impl Ord cho type chưa impl Eq và PartialOrd. Đây là lý do float không impl Ord — vì NaN phá vỡ cả Eq lẫn total order.

Method max, min, clamp trên Ord tận dụng total order: lấy giá trị lớn/nhỏ hơn, hoặc kẹp giá trị vào khoảng — không cần Option vì luôn có kết quả.

Cả partial_cmp lẫn cmp đều xoay quanh enum Ordering:

pub enum Ordering {
    Less,
    Equal,
    Greater,
}

Đây là return type chuẩn cho mọi phép so sánh trong Rust. Match Ordering để rẽ nhánh:

use std::cmp::Ordering;

fn describe(a: i32, b: i32) -> &'static str {
    match a.cmp(&b) {
        Ordering::Less => "nhỏ hơn",
        Ordering::Equal => "bằng",
        Ordering::Greater => "lớn hơn",
    }
}

Ordering có method tiện ích then và then_with để chain nhiều phép so sánh — dùng khi cần sort theo nhiều field (so sánh field 1 trước, nếu bằng thì so sánh field 2). Đây là pattern khi viết custom cmp cho struct nhiều field.

f32 và f64 chỉ impl PartialOrd — không impl Ord, cũng không impl Eq. Lý do duy nhất là NaN:

fn main() {
    let nan = f64::NAN;
    println!("{}", nan < 1.0);          // false
    println!("{}", nan > 1.0);          // false
    println!("{}", nan == 1.0);         // false
    println!("{}", nan == nan);         // false — NaN không bằng chính nó!

    println!("{:?}", nan.partial_cmp(&1.0)); // None
}

NaN phá vỡ total order và reflexivity, nên float không đủ điều kiện làm Ord. Hệ quả: vec![3.1, 1.4, 2.5].sort() không compile — sort() yêu cầu T: Ord.

Hai workaround:

• f64::total_cmp (stable từ Rust 1.62) — total order do IEEE 754 định nghĩa, sắp xếp NaN vào cuối: v.sort_by(|a, b| a.total_cmp(b)).
• Crate ordered-float với wrapper OrderedFloat<f64> impl Ord đầy đủ, panic khi gặp NaN hoặc xếp NaN theo policy của crate.

Khi muốn struct/enum tự nhiên có thứ tự lexicographic theo field, gộp 4 derive trong một dòng:

#[derive(PartialOrd, Ord, PartialEq, Eq, Debug)]
struct Version {
    major: u32,
    minor: u32,
    patch: u32,
}

fn main() {
    let v1 = Version { major: 1, minor: 2, patch: 5 };
    let v2 = Version { major: 1, minor: 3, patch: 0 };
    assert!(v1 < v2);

    let mut versions = vec![
        Version { major: 0, minor: 9, patch: 0 },
        Version { major: 1, minor: 2, patch: 5 },
        Version { major: 1, minor: 1, patch: 9 },
    ];
    versions.sort();
    println!("{:?}", versions);
}

Derive sinh ra cmp so sánh major trước; nếu bằng thì so minor; nếu vẫn bằng thì so patch — đúng thứ tự field khai báo trong struct. Đây là lexicographic order, hành vi mặc định của derive. Đổi thứ tự field trong struct sẽ đổi thứ tự sort — cần cẩn thận khi refactor.

Yêu cầu: mọi field cũng phải impl các trait tương ứng. Field f64 chặn không cho derive Ord/Eq (vì float không có); chỉ derive được PartialOrd/PartialEq.

Khi muốn sort theo một field cụ thể (ví dụ priority chứ không phải field đầu), tự viết impl Ord:

use std::cmp::Ordering;

#[derive(Eq, PartialEq, Debug)]
struct Task {
    id: u32,
    priority: u8,
    title: String,
}

impl Ord for Task {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority.cmp(&other.priority)
    }
}

impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn main() {
    let mut tasks = vec![
        Task { id: 1, priority: 3, title: "Deploy".into() },
        Task { id: 2, priority: 1, title: "Doc".into() },
        Task { id: 3, priority: 5, title: "Hotfix".into() },
    ];
    tasks.sort();  // sort theo priority tăng dần
}

Pattern chuẩn: viết impl Ord trả về kết quả so sánh field cần quan tâm (delegate cmp lên field đó). Sau đó impl PartialOrd chỉ wrap kết quả cmp trong Some — vì đã cam kết total order, partial_cmp luôn trả Some. Cuối cùng cần Eq + PartialEq để thoả Ord's supertrait — có thể derive nếu equality cũng tự nhiên theo field, hoặc impl tay khi cần định nghĩa "bằng" riêng.

Muốn sort theo nhiều field — primary priority, secondary id — dùng then_with: self.priority.cmp(&other.priority).then_with(|| self.id.cmp(&other.id)).

Vec (chính xác là slice [T]) cung cấp 3 method sort, mỗi cái yêu cầu/giao diện khác nhau:

fn main() {
    // 1. sort() — cần T: Ord
    let mut nums = vec![3, 1, 4, 1, 5, 9, 2, 6];
    nums.sort();
    // → [1, 1, 2, 3, 4, 5, 6, 9]

    // 2. sort_by — closure tự định nghĩa Ordering, không cần T: Ord
    let mut floats = vec![3.1, 1.4, 2.5, f64::NAN];
    floats.sort_by(|a, b| a.total_cmp(b));

    // 3. sort_by_key — extract key, key phải Ord
    let mut words = vec!["banana", "fig", "apple", "kiwi"];
    words.sort_by_key(|w| w.len());
    // → sort theo độ dài chuỗi
}

Phân biệt:

• sort(): chữ ký fn sort(&mut self) where T: Ord. Không cần closure — dùng Ord::cmp sẵn có. Chỉ chạy được khi T đã impl Ord; với f64 sẽ báo lỗi compile.
• sort_by(|a, b| -> Ordering): closure trả Ordering trực tiếp. Không yêu cầu T: Ord — closure tự định nghĩa thứ tự. Đây là cách sort f64 qua total_cmp hoặc sort ngược (b.cmp(&a)).
• sort_by_key(|x| -> K): trích xuất "key" K từ mỗi phần tử; key phải impl Ord. Gọn nhất khi sort theo một thuộc tính dẫn xuất (độ dài, một field). Lưu ý closure được gọi nhiều lần nên tránh tính toán đắt; cần đắt thì dùng sort_by_cached_key.

Ngoài ra còn sort_unstable, sort_unstable_by, sort_unstable_by_key — nhanh hơn nhưng không đảm bảo giữ thứ tự tương đối của phần tử bằng nhau. Khi không cần stability (sort số/key đơn), unstable thường được khuyến nghị.

• PartialOrd cấp operator <, >, <=, >= và method partial_cmp(&self, other) -> Option<Ordering> — bọc Option vì có cặp không comparable (NaN của float).
• Ord là total order: method cmp(&self, other) -> Ordering không có Option vì luôn so sánh được; require Eq + PartialOrd (supertrait chain).
• Ordering là enum 3 variant { Less, Equal, Greater }, là return type chuẩn; chain bằng then / then_with khi sort theo nhiều field.
• f32, f64 chỉ impl PartialOrd — không impl Ord, không impl Eq vì NaN phá vỡ total order và reflexivity. Workaround: f64::total_cmp hoặc crate ordered-float.
• #[derive(PartialOrd, Ord, PartialEq, Eq)] thường gộp 1 nhóm — sort lexicographic theo thứ tự field khai báo; mọi field cũng phải impl trait tương ứng.
• Custom impl Ord khi muốn sort theo 1 field cụ thể (như priority); pattern là delegate cmp lên field đó; impl PartialOrd wrap cmp trong Some.
• Vec::sort() cần T: Ord; sort_by(|a, b| ...) nhận closure trả Ordering tự định nghĩa; sort_by_key(|x| ...) extract key có Ord.
• sort_unstable* nhanh hơn nhưng không giữ thứ tự tương đối của phần tử bằng nhau — chọn khi không cần stability.

Tự trả lời, đáp án ở cuối:

1. Vì sao partial_cmp trả Option<Ordering> mà cmp chỉ trả Ordering? Cho ví dụ giá trị làm partial_cmp trả None.
2. Đoạn vec![3.1f64, 1.4, 2.5].sort() báo lỗi gì khi compile? Sửa lại để chạy được, dùng total_cmp.
3. Cho struct struct Point { x: i32, y: i32 } với #[derive(PartialOrd, Ord, PartialEq, Eq)]. Hai điểm Point { x: 1, y: 5 } và Point { x: 2, y: 0 }, derive sẽ xếp cái nào trước? Vì sao?
4. Viết impl Ord cho struct Event { time: u64, name: String } để sort theo time giảm dần (mới nhất trước). Gợi ý: đảo self và other trong cmp.
5. So sánh khi nào dùng sort(), sort_by, sort_by_key: bạn có Vec<User> với User { name: String, age: u32 } và muốn sort theo age. Cách nào ngắn nhất?

Bài 165: Default Trait — Giá Trị Mặc Định — đã đi qua equality (PartialEq/Eq/Hash) và ordering (PartialOrd/Ord), bài 165 chuyển sang Default — trait cấp method Default::default() trả giá trị "rỗng/zero" của type: 0 cho số, "" cho String, vec![] cho Vec, None cho Option; derive cho struct khi mọi field đều Default; custom impl khi muốn giá trị mặc định khác zero (ví dụ port: 8080); cú pháp ..Default::default() trong struct update để chỉ override vài field — pattern config/builder rất phổ biến.