🏗️ Bài giảng: Vector trong C++ (Standard Template Library)

1. Vector là gì?

Khác với mảng tĩnh (array), Vector là một "mảng động". Nó có khả năng tự động thay đổi kích thước khi ta thêm hoặc xóa phần tử. Trong lập trình thi đấu, Vector cực kỳ mạnh mẽ vì linh hoạt và có nhiều hàm hỗ trợ sẵn.

2. Các thao tác cơ bản cần nhớ

• Khai báo: vector<int> v; hoặc vector<int> v(n, 0); (khởi tạo n phần tử bằng 0).
• Thêm phần tử vào cuối: v.push_back(x); — Độ phức tạp O(1).
• Lấy kích thước: v.size();
• Truy cập phần tử: v[i] tương tự mảng.
• Xóa phần tử cuối: v.pop_back();
• Làm rỗng vector: v.clear();
• Duyệt vector bằng Range-based loop: for (int x : v) { ... }

Dưới đây là 4 cách duyệt Vector phổ biến nhất trong C++, từ kiểu truyền thống đến hiện đại:

1. Duyệt bằng chỉ số (Index-based)

Đây là cách phổ biến nhất, giống hệt như cách bạn duyệt mảng tĩnh.

• Ưu điểm: Dễ hiểu, có thể truy cập chỉ số i để tính toán hoặc so sánh với các phần tử lân cận ().
• Cú pháp:

for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << " ";
}

2. Duyệt bằng Iterator (Trình lặp)

Iterator được coi là một "con trỏ" thông minh trỏ vào các phần tử của Vector.

• Ưu điểm: Đây là cách tiếp cận chuẩn của STL, giúp bạn dễ dàng làm việc với các hàm như std::sort, std::reverse, hoặc khi cần xóa phần tử bằng v.erase().
• Cú pháp:

for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    cout << *it << " "; // Dùng dấu * để lấy giá trị tại vị trí con trỏ
}
// Có thể dùng 'auto it' để code ngắn gọn hơn (C++11)

3. Duyệt bằng Range-based for loop (C++11)

Đây là cách hiện đại và được khuyến khích sử dụng nhất nếu bạn chỉ cần lấy giá trị để tính toán mà không quan tâm đến chỉ số.

• Ưu điểm: Cực kỳ ngắn gọn, tránh các lỗi "off-by-one" (truy cập quá giới hạn mảng).
• Lưu ý: * Sử dụng for (int x : v) nếu chỉ muốn đọc giá trị (tạo bản sao).

• Sử dụng for (int &x : v) nếu muốn thay đổi giá trị trực tiếp trong Vector.

• Cú pháp:

for (int x : v) {
    cout << x << " ";
}

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {10, 20, 30, 40, 50};

    // Dùng auto để trình biên dịch tự hiểu it là std::vector<int>::iterator
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " "; // Giải tham chiếu để lấy giá trị
    }

    return 0;
}

• Các biến thể của Range-based for loop Tùy vào mục đích sử dụng, bạn có thể viết theo 3 cách chính sau:
  for(auto x : v) (Duyệt giá trị - Copy): C++ sẽ tạo ra một bản sao của từng phần tử trong v và gán vào x. Nếu bạn thay đổi x, giá trị trong vector v không thay đổi. Cách này phù hợp với các kiểu dữ liệu nhỏ (int, char, bool).
  for(auto &x : v) (Duyệt tham chiếu): x lúc này là một tham chiếu (reference) đến phần tử trong v. Nếu bạn thay đổi x, giá trị trong v sẽ thay đổi theo. Cách này hiệu quả về bộ nhớ vì không phải tạo bản sao.
  for(const auto &x : v) (Duyệt tham chiếu hằng): Dùng khi bạn chỉ muốn đọc dữ liệu, không muốn thay đổi giá trị và muốn tối ưu hiệu năng (không copy), đặc biệt là khi vector chứa các kiểu dữ liệu lớn như string hoặc struct/class.

// Ví dụ Gấp đôi giá trị mỗi phần tử

for(auto &x : v) {
    x *= 2;
}

// In ra giá trị
for(auto x : v) {
    cout << x << " "; // Output: 2 4 6 8 10
}

4. Duyệt ngược (Reverse Iterators)

Trong một số bài toán yêu cầu xử lý từ cuối dãy lên đầu, thay vì dùng i-- dễ gây lỗi với kiểu số nguyên không dấu, em có thể dùng reverse_iterator.

• Cú pháp:

for (auto it = v.rbegin(); it != v.rend(); ++it) {
    cout << *it << " ";
}

📊 Bảng so sánh nhanh

Lời khuyên cho đội tuyển: Khi bồi dưỡng học sinh giỏi, các em dùng Range-based for loop cho các bài toán đơn giản để tiết kiệm thời gian gõ code, và dùng Index-based khi bài toán liên quan đến quy hoạch động hoặc các bài cần so sánh với v[i] với v[i-1]

Gợi ý: Với các em mới bắt đầu, việc sử dụng v.reserve(n) nếu đã biết trước số lượng phần tử để tối ưu tốc độ, tránh việc Vector phải cấp phát lại bộ nhớ quá nhiều lần.

TRẮC NGHIỆM VỀ VECTOR SAU KHI LÀM BÀI TẬP