Bài 121: push, pop, insert, remove

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

• Dùng được .push(x) để append phần tử vào cuối Vec và hiểu vì sao chi phí là O(1) amortized — đôi khi gặp re-alloc khi len == capacity, mặt khác nhiều lần push liên tiếp được phân bổ chi phí xuống mức không đổi trung bình.
• Dùng được .pop() để lấy phần tử cuối, hiểu signature trả Option<T>: Some(v) nếu có, None nếu Vec rỗng — Rust ép bạn xử lý case rỗng ngay, không gặp lỗi run-time như nhiều ngôn ngữ khác.
• Hiểu .insert(i, x) và .remove(i) đều là thao tác O(n) vì phải shift mọi phần tử phía sau — không dùng khi vòng lặp lớn, dùng .swap_remove(i) khi không cần preserve thứ tự.
• Phân biệt .remove(i) (giữ order, O(n)) vs .swap_remove(i) (không giữ order, O(1)) — chọn đúng theo workload thực tế.
• Biết .clear() đưa len về 0 nhưng giữ nguyên capacity — tái sử dụng Vec mà không phải re-alloc.
• Dùng .retain(|x| predicate) để filter in-place — giữ lại phần tử thoả predicate, drop phần khác, không cần tạo Vec mới.
• Dùng .append(other) để move tất cả phần tử từ Vec khác sang self — nhanh hơn push từng phần tử, đồng thời consume other về Vec rỗng nhưng vẫn còn capacity.
• Nhớ điều kiện chung: mọi method sửa Vec đều yêu cầu Vec khai báo mut — quên mut là compile error ngay.

Bài này thuần phương thức cốt lõi sửa nội dung Vec. Bài 122 sẽ đi vào đọc phần tử (v[i] vs v.get(i)); Bài 123 đi vào iterate.

Method dùng nhiều nhất khi xây Vec. Signature: pub fn push(&mut self, value: T). Thêm value vào cuối Vec, tăng len lên một, không trả gì.

fn main() {
    let mut v: Vec<i32> = Vec::new();

    v.push(10);
    v.push(20);
    v.push(30);

    println!("v = {:?}", v);                // [10, 20, 30]
    println!("len = {}", v.len());          // 3
    println!("capacity = {}", v.capacity()); // 4 (Vec grow exponential)

    // Push trong vòng lặp
    let mut squares: Vec<u32> = Vec::with_capacity(10);
    for i in 1..=10 {
        squares.push(i * i);
    }
    println!("{:?}", squares);              // [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
}

Chi phí: O(1) amortized. Khi len < capacity, push chỉ ghi memory rồi tăng len — đúng O(1). Khi len == capacity, Vec phải re-alloc: cấp buffer mới (thường gấp đôi), copy toàn bộ phần tử cũ sang, free buffer cũ. Lần đó chi phí O(n), nhưng phân bổ qua nhiều lần push thì trung bình vẫn O(1) — đó là ý nghĩa của "amortized". Muốn tránh re-alloc, dùng Vec::with_capacity như Bài 120.

Yêu cầu: Vec phải mut. Quên là compile error cannot borrow as mutable. Đồng thời value bị move vào Vec — sau push, không còn dùng được biến cũ trừ khi T: Copy.

Đối nghịch với push. Signature: pub fn pop(&mut self) -> Option<T>. Lấy phần tử cuối ra (move-out), giảm len xuống một, trả về Some(v) hoặc None nếu Vec rỗng.

fn main() {
    let mut stack: Vec<i32> = vec![1, 2, 3];

    // Vòng lặp pop tới khi rỗng - dùng while let
    while let Some(top) = stack.pop() {
        println!("Lấy ra: {}", top);
    }
    // In: 3, 2, 1 (LIFO order - đúng tính chất stack)

    // Pop trên Vec rỗng trả None
    let mut empty: Vec<i32> = Vec::new();
    match empty.pop() {
        Some(v) => println!("Có: {}", v),
        None    => println!("Vec rỗng, không có gì để pop"),
    }
}

Chi phí: O(1) tuyệt đối — không re-alloc, không shift, chỉ giảm len và move phần tử cuối ra. Capacity giữ nguyên — buffer cấp phát không bị giải phóng, để lần push sau dùng lại (muốn giảm thì gọi .shrink_to_fit()).

Idiom: while let Some(x) = v.pop() { ... } để drain Vec từ cuối về đầu, theo thứ tự LIFO. Đây là cách triển khai stack đơn giản nhất trong Rust — Vec đã sẵn là stack.

Vì trả Option<T>, compiler ép bạn xử lý case rỗng. Không có phiên bản nào panic kiểu "pop khi rỗng" — Rust thiết kế an toàn ngay từ API.

Khi cần chèn vào giữa Vec, dùng .insert(index, value). Signature: pub fn insert(&mut self, index: usize, element: T). Chèn element vào vị trí index, shift mọi phần tử từ index về sau lùi xuống một ô.

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

    v.insert(0, 99);            // Chèn vào đầu
    println!("{:?}", v);        // [99, 10, 20, 30, 40]

    v.insert(2, 50);            // Chèn vào giữa
    println!("{:?}", v);        // [99, 10, 50, 20, 30, 40]

    let len = v.len();
    v.insert(len, 100);         // Chèn vào cuối (tương đương push)
    println!("{:?}", v);        // [99, 10, 50, 20, 30, 40, 100]

    // PANIC nếu index > len
    // v.insert(100, 0);  // thread 'main' panicked: insertion index (is 100) should be <= len (is 7)
}

Chi phí O(n): insert vào vị trí i phải dịch len - i phần tử lùi xuống. Insert vào đầu Vec rất tốn — toàn bộ phần tử phải shift. Nếu cần nhiều thao tác insert đầu, cân nhắc VecDeque (double-ended queue, Bài cuối Group 16 sẽ giới thiệu).

Điều kiện: index <= len. Nếu index == len thì tương đương push — chèn vào sau phần tử cuối. Nếu index > len, Vec panic với message rõ ràng. Khác với một số ngôn ngữ tự động pad — Rust thiên về fail fast.

Đối nghịch với insert. Signature: pub fn remove(&mut self, index: usize) -> T. Xoá phần tử ở index và trả về nó. Mọi phần tử phía sau shift lên một ô để lấp chỗ — preserve thứ tự gốc.

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

    let removed = v.remove(2);          // Xoá phần tử thứ 3 (index 2)
    println!("Đã xoá: {}", removed);    // 30
    println!("{:?}", v);                // [10, 20, 40, 50]  - order giữ nguyên

    let first = v.remove(0);            // Xoá phần tử đầu
    println!("Đã xoá: {}", first);      // 10
    println!("{:?}", v);                // [20, 40, 50]

    // PANIC nếu index >= len
    // v.remove(100);  // thread 'main' panicked: removal index (is 100) should be < len (is 3)
}

Chi phí: O(n) vì shift len - i - 1 phần tử. Tốn như insert theo cùng lý do. Khi xoá nhiều phần tử trong vòng lặp, không nên gọi .remove() lặp — nên dùng .retain() ở Bước 8 (O(n) tổng thể) hoặc .swap_remove() nếu không cần preserve order.

Bẫy thường gặp: vòng lặp for i in 0..v.len() { if cond { v.remove(i); } } — sai vì sau khi remove thì len giảm, index cũ trỏ sang phần tử khác, dẫn đến skip. Hoặc lỗi concurrent modification nếu lặp qua reference cùng Vec. Cách đúng: dùng .retain() hoặc clone index list trước rồi xoá theo thứ tự ngược.

Điều kiện: index < len. Nếu vượt, panic ngay với thông báo rõ — không trả Option. Muốn safe version, dùng if i < v.len() { v.remove(i) }.

Phiên bản nhanh của .remove(i): .swap_remove(i) swap phần tử ở i với phần tử cuối, sau đó pop. Kết quả: O(1) — không shift, nhưng thứ tự thay đổi.

fn main() {
    let mut v = vec!["a", "b", "c", "d", "e"];

    // Xoá index 1 ("b") bằng swap_remove
    let removed = v.swap_remove(1);
    println!("Đã xoá: {}", removed);   // "b"
    println!("{:?}", v);               // ["a", "e", "c", "d"]
    //                                     ^^^ phần tử cuối "e" nhảy lên vị trí 1

    // So sánh với .remove() preserve order:
    let mut w = vec!["a", "b", "c", "d", "e"];
    w.remove(1);
    println!("{:?}", w);               // ["a", "c", "d", "e"]  - thứ tự giữ
}

Cơ chế: thay vì shift O(n), Rust swap phần tử cuối vào vị trí i rồi gọi pop() nội bộ. Hai thao tác O(1) — tổng O(1).

Khi nào dùng: khi Vec là set không quan tâm thứ tự (vd unordered ID list, particle pool trong game, slot trong cache không sort). Khi nào tránh: khi Vec đại diện sequence có ý nghĩa (timeline, sorted list, UI list user nhìn thấy).

Ứng dụng kinh điển: game / ECS xoá entity theo id không cần giữ order. Thay vì O(n) cho từng .remove() trong loop 1000 entity, dùng .swap_remove() O(1) — giảm chi phí cả vòng từ O(n²) xuống O(n).

Điều kiện: index < len, panic nếu vượt — giống .remove().

Đưa Vec về rỗng: pub fn clear(&mut self). Drop mọi phần tử, đưa len về 0, nhưng giữ nguyên capacity.

fn main() {
    let mut v: Vec<i32> = Vec::with_capacity(100);
    for i in 0..50 {
        v.push(i);
    }

    println!("Trước clear: len = {}, capacity = {}", v.len(), v.capacity());
    // len = 50, capacity = 100

    v.clear();

    println!("Sau clear:   len = {}, capacity = {}", v.len(), v.capacity());
    // len = 0,  capacity = 100  -- buffer vẫn còn

    // Tái sử dụng Vec mà không re-alloc
    for i in 0..50 {
        v.push(i * 2);
    }
    println!("Sau push lại: len = {}, capacity = {}", v.len(), v.capacity());
    // len = 50, capacity = 100  -- vẫn không re-alloc
}

Lợi ích chính của giữ capacity: pattern reuse. Ví dụ buffer dùng đi dùng lại trong loop (parser, network frame, batch processor) — gọi clear() đầu mỗi vòng, không trả buffer về OS, không re-alloc khi push lại. Đặc biệt hữu ích trong code hot path.

Muốn vừa clear vừa giải phóng memory: gọi .clear() rồi .shrink_to_fit(), hoặc đơn giản gán v = Vec::new(). Khác nhau: shrink_to_fit giữ Vec cũ, = Vec::new() drop Vec cũ và tạo mới.

Cách an toàn và hiệu quả để xoá nhiều phần tử thoả điều kiện: pub fn retain<F>(&mut self, mut f: F) where F: FnMut(&T) -> bool. Đi qua Vec một lần, giữ phần tử mà f trả true, drop phần tử trả false, không tạo Vec mới.

fn main() {
    let mut nums = vec![-3, -1, 0, 2, 4, -5, 7, 8];

    // Giữ phần tử dương
    nums.retain(|&x| x > 0);
    println!("{:?}", nums);            // [2, 4, 7, 8]

    // Giữ số chẵn
    let mut more = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    more.retain(|&x| x % 2 == 0);
    println!("{:?}", more);            // [2, 4, 6, 8, 10]

    // Với String - closure nhận &String, không phải &str
    let mut words = vec![String::from("apple"), String::from("hi"), String::from("rust")];
    words.retain(|w| w.len() >= 4);
    println!("{:?}", words);           // ["apple", "rust"]
}

Chi phí: O(n) — đi qua Vec một lần. So với loop for + remove O(n²), retain nhanh hơn nhiều và tránh hoàn toàn bug index khi vừa lặp vừa xoá. Đây là cách đúng để filter một Vec đang có trong tay.

Preserve thứ tự: phần tử giữ lại vẫn giữ vị trí tương đối ban đầu — Rust shift in-place các phần tử thoả predicate xuống đầu.

Closure nhận reference &T, không phải T — nên |&x| x > 0 destructure ngay từ pattern. Có biến thể retain_mut cho phép mutate phần tử bên trong closure — bài sau Group 16 sẽ đề cập.

Gộp toàn bộ phần tử từ Vec khác sang Vec hiện tại: pub fn append(&mut self, other: &mut Vec<T>). Move data từ other sang self, để other rỗng (nhưng capacity được giữ lại).

fn main() {
    let mut a = vec![1, 2, 3];
    let mut b = vec![4, 5, 6];

    a.append(&mut b);

    println!("a = {:?}", a);             // [1, 2, 3, 4, 5, 6]
    println!("b = {:?}", b);             // []  - đã rỗng
    println!("b cap = {}", b.capacity()); // capacity còn nguyên

    // So sánh với push từng phần tử (chậm hơn, phải copy/clone)
    // for x in &b { a.push(*x); }       -- O(n) copy, không consume b
}

Chi phí: O(other.len()), nhưng nhanh hơn loop push từng phần tử vì append dùng memcpy-style bulk move khi T là POD, không phải gọi từng method push riêng.

Tham số là &mut Vec<T>, không phải Vec<T> — other vẫn sống sau khi append, chỉ rỗng nội dung. Cho phép tái sử dụng buffer other mà không phải khai báo lại.

Biến thể liên quan: .extend(iter) nhận bất kỳ iterator nào (Vec, array, HashSet...), copy/move phần tử vào self. .append dành riêng cho &mut Vec<T> và move bulk; .extend linh hoạt hơn nhưng chậm hơn một chút cho trường hợp Vec → Vec. Group adapter ở Bài 162 sẽ đào sâu .extend.

• .push(x): append cuối, O(1) amortized, có thể re-alloc khi len == capacity.
• .pop(): lấy phần tử cuối, trả Option<T>, O(1), không re-alloc. Idiom: while let Some(x) = v.pop().
• .insert(i, x): chèn vào vị trí i, shift phần tử phía sau, O(n), panic nếu i > len.
• .remove(i): xoá vị trí i, preserve order, O(n) shift, panic nếu i >= len.
• .swap_remove(i): xoá O(1) bằng swap với phần tử cuối, KHÔNG preserve order, panic nếu i >= len.
• .clear(): len = 0, giữ capacity — pattern reuse buffer.
• .retain(|x| pred): filter in-place, O(n), preserve order — cách đúng để xoá nhiều phần tử theo điều kiện.
• .append(&mut other): move bulk từ Vec khác, để other rỗng nhưng còn capacity.
• Mọi method trên đều yêu cầu Vec khai báo mut — quên là compile error.

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

1. Viết hàm fn build_stack(n: u32) -> Vec<u32> nhận n, dùng .push() trong vòng lặp để build Vec [0, 1, ..., n-1]. Sau đó dùng while let Some(x) = ... .pop() in ngược về 0.
2. Cho let mut v = vec![10, 20, 30, 40];. Viết code: chèn 99 vào đầu, chèn 100 vào sau index 2, xoá phần tử index 1 (preserve order). Vec cuối cùng phải là [99, 30, 100, 20, 40].
3. Cho Vec vec!["a", "b", "c", "d", "e"]. Gọi .remove(1) trên Vec sao chép thứ nhất, và .swap_remove(1) trên Vec sao chép thứ hai. So sánh kết quả — chú thích sự khác biệt về order.
4. Viết hàm fn keep_positive(v: &mut Vec<i32>) dùng .retain() để giữ chỉ số dương. Test với vec![-5, 3, 0, -1, 7, 2, -8].
5. Cho hai Vec let mut a = vec![1, 2, 3]; và let mut b = vec![4, 5, 6];. Dùng .append() gộp b vào a. Sau đó in a, b, và b.capacity() — quan sát b rỗng nhưng capacity vẫn còn.

Bài 122: Indexing vs .get() — Panic vs Option — so sánh hai cách đọc phần tử Vec: v[i] panic khi out-of-bound vs v.get(i) trả Option<&T> an toàn. Idiom khi nào nên dùng cách nào, vì sao panic không phải lúc nào cũng xấu, và pattern dùng .get() trong code production nơi index có thể đến từ user input.