Bài 124: Methods Phổ Biến: sort, dedup, contains, reverse

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

• Sắp xếp Vec ascending bằng .sort(), hiểu yêu cầu T: Ord và Vec phải mut.
• Viết comparator tuỳ ý qua .sort_by(|a, b| ...) trả Ordering::Less / Equal / Greater — sort theo field của struct hoặc theo thứ tự ngược.
• Dùng .sort_by_key(|x| ...) để extract key một lần — gọn hơn sort_by khi key chỉ phụ thuộc một field.
• Hiểu .dedup() chỉ xoá consecutive duplicate và biết phải .sort() trước nếu muốn xoá hết duplicate.
• Dùng .contains(&x) để kiểm tra membership O(n), nhớ T: PartialEq.
• Dùng .reverse() đảo ngược in-place; .iter().position() tìm index match predicate; .binary_search() trả Result<usize, usize> trên Vec đã sort.

Method đơn giản nhất là .sort(). Nó sắp xếp tăng dần, in-place (không tạo Vec mới), trên một Vec phải khai báo mut vì sửa trực tiếp buffer ở heap. Yêu cầu: T: Ord — type của phần tử phải implement trait Ord để có thể so sánh tổng thể (total ordering).

fn main() {
    let mut v: Vec<i32> = vec![5, 1, 4, 2, 3];
    v.sort();
    println!("{:?}", v); // [1, 2, 3, 4, 5]
}

Tất cả integer, String, &str, char, bool đều impl Ord — gọi .sort() luôn được. Riêng f32 / f64 không impl Ord (vì NaN phá total ordering) — phải dùng .sort_by(|a, b| a.partial_cmp(b).unwrap()) hoặc .sort_by(|a, b| a.total_cmp(b)) (Rust 1.62+).

Độ phức tạp: O(n log n) trong cả average và worst case. Internally Rust dùng thuật toán adaptive (driftsort từ 1.81, trước đó là TimSort) — ổn định và nhanh trên dữ liệu gần-sorted. Không cần lo về quicksort worst-case O(n²) như trong nhiều ngôn ngữ khác.

Khi muốn sort theo logic riêng — giảm dần, theo field của struct, hay theo nhiều tiêu chí — dùng .sort_by(|a, b| ...). Closure nhận hai phần tử và trả std::cmp::Ordering: Less nếu a đứng trước b, Greater nếu sau, Equal nếu bằng.

use std::cmp::Ordering;

#[derive(Debug)]
struct Product {
    name: String,
    price: u32,
}

fn main() {
    let mut items = vec![
        Product { name: "Coffee".into(), price: 45 },
        Product { name: "Tea".into(),    price: 30 },
        Product { name: "Cake".into(),   price: 60 },
    ];

    // Sort giảm dần theo price
    items.sort_by(|a, b| b.price.cmp(&a.price));

    for p in &items {
        println!("{:?}", p);
    }
}

Mẹo: viết a.cmp(&b) sort tăng dần, đảo b.cmp(&a) sort giảm dần. Cần sort theo nhiều tiêu chí thì .cmp() field thứ nhất, nếu bằng .then() field thứ hai: a.price.cmp(&b.price).then(a.name.cmp(&b.name)) — tiện và rõ ý đồ.

Nếu tiêu chí sort chỉ là "extract một key rồi so sánh", .sort_by_key(|x| key) ngắn gọn hơn nhiều so với sort_by. Closure nhận một phần tử và trả về key — key phải impl Ord.

#[derive(Debug)]
struct Product { name: String, price: u32 }

fn main() {
    let mut items = vec![
        Product { name: "Coffee".into(), price: 45 },
        Product { name: "Tea".into(),    price: 30 },
        Product { name: "Cake".into(),   price: 60 },
    ];

    items.sort_by_key(|p| p.price); // tăng dần theo price
    println!("{:?}", items);
}

Đằng sau, sort_by_key gọi closure nhiều lần trong quá trình so sánh — nếu việc extract key đắt (ví dụ tính hash), nên cân nhắc sort_by_cached_key(|p| ...) để cache key một lần cho mỗi phần tử. Để sort giảm dần theo key, đảo dấu cho số (|p| std::cmp::Reverse(p.price)) — hoặc fallback về sort_by.

.dedup() xoá các phần tử kề nhau mà bằng nhau — chỉ duplicate liền kề, không phải toàn bộ duplicate trong Vec. Yêu cầu T: PartialEq và Vec phải mut. Method giữ lại phần tử đầu tiên của mỗi run.

fn main() {
    let mut v = vec![1, 1, 2, 3, 3, 3, 4, 1];
    v.dedup();
    println!("{:?}", v); // [1, 2, 3, 4, 1]
}

Chú ý 1 ở cuối không bị xoá vì nó không liền kề với 1 ở đầu. Idiom để xoá toàn bộ duplicate là: sort trước, sau đó dedup. Sau khi sort, mọi phần tử bằng nhau đều liền kề nên dedup xoá hết.

fn main() {
    let mut v = vec![3, 1, 2, 1, 3, 2, 4];
    v.sort();    // [1, 1, 2, 2, 3, 3, 4]
    v.dedup();   // [1, 2, 3, 4]
    println!("{:?}", v);
}

Biến thể: .dedup_by(|a, b| ...) nhận closure return bool chỉ định "có coi là duplicate hay không"; .dedup_by_key(|x| key) dedup theo key extract — tiện khi muốn dedup struct theo một field, ví dụ users.dedup_by_key(|u| u.id).

.contains(&x) trả bool, kiểm tra xem Vec có chứa giá trị x hay không. Đây là linear search O(n) — quét tuần tự, không yêu cầu Vec đã sort. Yêu cầu duy nhất là T: PartialEq. Tham số nhận tham chiếu tới giá trị cần tìm (signature là &T).

fn main() {
    let v = vec![10, 20, 30, 40, 50];
    println!("{}", v.contains(&30));  // true
    println!("{}", v.contains(&99));  // false

    let names = vec![String::from("Alice"), String::from("Bob")];
    // Truyền &&str cũng OK nhờ deref coercion? KHÔNG — phải &String,
    // hoặc dùng .iter().any(|n| n == "Alice").
    println!("{}", names.contains(&String::from("Alice"))); // true
}

Bẫy thường gặp: với Vec<String> bạn không thể viết v.contains(&"Alice") (kiểu là &&str) — phải tạo String tạm hoặc dùng v.iter().any(|s| s == "Alice"). Với Vec lớn cần search nhiều lần, thay vì gọi contains O(n) lặp lại, nên chuyển sang HashSet hoặc sort + binary_search.

.reverse() đảo ngược thứ tự phần tử in-place, không tạo Vec mới. Yêu cầu Vec phải mut. Độ phức tạp O(n/2) swap — swap phần tử đầu với cuối, thứ hai với gần cuối, cứ thế tới giữa.

fn main() {
    let mut v = vec![1, 2, 3, 4, 5];
    v.reverse();
    println!("{:?}", v); // [5, 4, 3, 2, 1]
}

Khác biệt với .iter().rev(): rev() trả về một iterator duyệt ngược nhưng không thay đổi Vec gốc. Khi chỉ cần iterate ngược một lần, dùng for x in v.iter().rev() sẽ tiết kiệm hơn. Khi cần Vec thực sự ngược (vì sẽ truyền cho hàm khác, hoặc sẽ index nhiều lần), gọi .reverse(). Một idiom phổ biến là "sort giảm dần": v.sort(); v.reverse(); — tương đương v.sort_by(|a, b| b.cmp(a)) nhưng đôi khi dễ đọc hơn.

.contains() chỉ trả bool; khi cần index của phần tử match, dùng .iter().position(|&x| predicate). Method trả Option<usize> — Some(i) với index của match đầu tiên, None nếu không tìm thấy. Đây cũng là linear search O(n).

fn main() {
    let v = vec![10, 20, 30, 40, 50];

    match v.iter().position(|&x| x == 30) {
        Some(i) => println!("Tìm thấy ở index {}", i),
        None    => println!("Không có"),
    }

    // Tìm phần tử lẻ đầu tiên
    let odd_idx = v.iter().position(|&x| x % 2 != 0);
    println!("{:?}", odd_idx); // None vì tất cả chẵn
}

Closure nhận &T (vì iter() trả tham chiếu) — viết |&x| để destructure ra giá trị cho type Copy. Khi muốn tìm match cuối cùng, dùng .iter().rposition(|&x| ...). Khi muốn cả giá trị + index, dùng .iter().enumerate().find(|(_, &x)| ...) trả Option<(usize, &T)>.

Khi Vec đã sort, có thể dùng .binary_search(&x) tìm phần tử với độ phức tạp O(log n) — nhanh hơn nhiều so với linear search trên Vec lớn. Yêu cầu cứng: Vec phải sort tăng dần (theo Ord của T); nếu chưa sort, kết quả không xác định.

Signature trả về Result<usize, usize> — đây là chi tiết quan trọng làm binary_search khác mọi API "find" thông thường:

• Ok(i): tìm thấy phần tử ở index i.
• Err(i): không tìm thấy, nhưng i là index nên chèn x vào để Vec vẫn sort. Cực kỳ tiện khi cần insert sorted.

fn main() {
    let v = vec![1, 3, 5, 7, 9, 11];

    match v.binary_search(&7) {
        Ok(i)  => println!("Có 7 ở index {}", i),       // Ok(3)
        Err(i) => println!("Không có, chèn vào {}", i),
    }

    // Insert sorted: tìm vị trí rồi insert
    let mut v = v.clone();
    let x = 6;
    match v.binary_search(&x) {
        Ok(_)  => { /* đã có, không insert */ }
        Err(i) => v.insert(i, x),
    }
    println!("{:?}", v); // [1, 3, 5, 6, 7, 9, 11]
}

Nếu Vec có duplicate, binary_search không cam kết trả về index nào cụ thể trong nhóm bằng nhau — chỉ một trong số đó. Biến thể: binary_search_by(|x| ...) với comparator tự viết (giống sort_by), và binary_search_by_key(&k, |x| key(x)) tìm theo key extract — đối ứng với sort_by_key mà bạn đã dùng để sort Vec.

• .sort() — in-place ascending, yêu cầu T: Ord và mut Vec, O(n log n).
• .sort_by(|a, b| ...) — comparator trả Ordering::Less/Equal/Greater; dùng để sort giảm dần, theo field, theo nhiều tiêu chí với .then().
• .sort_by_key(|x| ...) — extract key một lần, ngắn gọn cho trường hợp key đơn giản.
• .dedup() — chỉ xoá consecutive duplicate; sort trước rồi dedup để xoá hết.
• .contains(&x) — bool, O(n) linear, T: PartialEq.
• .reverse() — in-place, O(n/2) swap; khác .iter().rev() không sửa Vec.
• .iter().position(|&x| ...) — Option<usize>, match đầu tiên.
• .binary_search(&x) — O(log n) trên Vec đã sort, trả Result<usize, usize>: Err(i) chính là vị trí nên chèn để giữ sort.

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

1. Cho let v = vec![3.1, 1.4, 1.5, 9.2, 6.5]: Vec<f64>. Vì sao v.sort() không compile? Viết một dòng sort tăng dần đúng.
2. Có Vec<Product { name, price }>. Viết code sort giảm dần theo price, nếu trùng price thì sort tăng dần theo name (alphabet).
3. Cho let mut v = vec![1, 2, 1, 2, 1]. Gọi v.dedup() rồi in ra kết quả. Bạn mong đợi gì? Nếu muốn kết quả là [1, 2] thì làm thế nào?
4. So sánh .contains(&x) và .iter().any(|y| *y == x) — hai cách có khác gì không? Khi nào nên dùng any?
5. Trên Vec đã sort tăng dần [10, 20, 30, 40], gọi v.binary_search(&25) trả gì? Dùng kết quả đó để chèn 25 vào Vec giữ sort.
6. Bạn có Vec 1 triệu phần tử cần check membership 10000 lần. Giải thuật nào tốt hơn: lặp .contains() hay .sort() rồi .binary_search()? Tính sơ qua chi phí.

Bài 125: Vec Với Generic Struct — bài này bạn đã quen với các method "đại trà". Bài tiếp theo nhìn vào Vec<User> (Vec chứa struct của bạn), những gì xảy ra khi push một User (ownership move), idiom builder return Vec<T>, và so sánh ngắn với LinkedList để hiểu vì sao Vec gần như luôn là lựa chọn mặc định.