🧰 STL cơ bản: vector, pair và tuple

🎯 Mục tiêu bài học

1. Đặt vấn đề

1.1. Hạn chế của mảng thường

Mảng như int a[1000] cần biết trước giới hạn. Khi dữ liệu thay đổi, ta phải tự quản lý số phần tử và dễ vượt kích thước.

1.2. Hạn chế của nhiều mảng song song

Nếu một bản ghi có nhiều trường, dùng nhiều mảng riêng dễ làm dữ liệu lệch nhau khi sắp xếp.

2. vector – mảng động

2.1. Mô phỏng vector

3. Các hàm thường dùng với vector

3.1. Mô phỏng insert, erase, resize, reverse và find

3.2. Ví dụ xóa theo giá trị

vector<int> a = {2, 5, 2, 7, 2, 9};
int x = 2;

a.erase(
    remove(a.begin(), a.end(), x),
    a.end()
);

// a = {5, 7, 9}

4. pair – gom hai giá trị

4.1. Sắp xếp vector<pair>

5. tuple – gom nhiều giá trị

5.1. Sắp xếp tuple

6. Chọn vector, pair, tuple hay struct?

7. Code mẫu

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a;
    a.reserve(100);

    a.push_back(5);
    a.push_back(2);
    a.emplace_back(8);

    sort(a.begin(), a.end());

    for (int x : a) cout << x << ' ';

    if (!a.empty()) a.pop_back();
}

#include <bits/stdc++.h>
using namespace std;

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

    a.insert(a.begin() + 2, 99);
    // {10, 20, 99, 30, 40, 50}

    a.erase(a.begin() + 3);
    // {10, 20, 99, 40, 50}

    a.erase(a.begin() + 1, a.begin() + 3);
    // Xóa đoạn [1,3): {10, 40, 50}

    a.erase(
        remove(a.begin(), a.end(), 40),
        a.end()
    );
    // {10, 50}

    auto it = find(a.begin(), a.end(), 50);

    if (it != a.end()) {
        int position = it - a.begin();
        cout << position;
    }
}

vector<pair<int,string>> students;
students.push_back({9, "An"});
students.emplace_back(7, "Binh");
students.emplace_back(9, "Chi");

sort(students.begin(), students.end());

for (const auto& [score, name] : students) {
    cout << score << ' ' << name << '\n';
}

tuple<int,int,int> getMinMaxSum(const vector<int>& a) {
    int mn = *min_element(a.begin(), a.end());
    int mx = *max_element(a.begin(), a.end());
    int sum = accumulate(a.begin(), a.end(), 0);
    return {mn, mx, sum};
}

auto [mn, mx, sum] = getMinMaxSum(a);

sort(students.begin(), students.end(),
    [](const Student& a, const Student& b) {
        if (a.score != b.score) return a.score > b.score;
        if (a.name != b.name) return a.name < b.name;
        return a.id < b.id;
    }
);

8. Giải thích code

8.1. Vì sao push_back là O(1) trung bình?

Phần lớn lần thêm chỉ ghi vào ô tiếp theo. Khi hết capacity, vector cấp phát vùng mới và chuyển các phần tử, nên có lần O(n). Tính trung bình nhiều lần là O(1) khấu hao.

8.2. reserve khác resize

8.3. Vì sao dùng const auto&?

Tránh sao chép phần tử và không cho phép sửa dữ liệu gốc.

8.4. Structured binding có sao chép không?

auto [x,y]=p tạo bản sao. Muốn tham chiếu, dùng auto& [x,y]=p hoặc const auto& [x,y]=p.

8.5. emplace_back có luôn nhanh hơn?

Không. Nó hữu ích khi dựng đối tượng trực tiếp từ đối số. Với kiểu đơn giản như int, khác biệt không đáng kể.

8.6. insert và erase ảnh hưởng đến phần tử phía sau thế nào?

Vector lưu dữ liệu liên tiếp. Khi chèn hoặc xóa ở giữa, các phần tử phía sau phải dịch chuyển, nên thao tác thường là O(n).

8.7. Vì sao erase nhận iterator?

Muốn xóa vị trí pos, chuyển chỉ số thành iterator bằng a.begin()+pos.

8.8. erase trả về gì?

erase trả về iterator tới phần tử đứng ngay sau phần tử hoặc đoạn vừa bị xóa. Điều này hữu ích khi vừa duyệt vừa xóa.

8.9. Khi nào dùng lower_bound?

Đoạn dữ liệu phải được sắp xếp theo cùng thứ tự so sánh. Nếu vector chưa sắp xếp, kết quả không có ý nghĩa như tìm kiếm nhị phân.

9. Lỗi thường gặp

• Truy cập a[0] hoặc pop_back khi vector rỗng.
• Duyệt i <= a.size().
• Nhầm reserve với resize.
• Giữ pointer/reference rồi push_back làm vector tái cấp phát.
• Dùng auto [x,y] rồi tưởng sửa được pair gốc.
• Nhớ sai thứ tự trường trong tuple.
• Dùng tuple quá dài thay vì struct.
• Gọi insert hoặc erase với vị trí vượt biên.
• Nhầm đoạn xóa [L,R) thành [L,R].
• Dùng remove nhưng quên gọi erase.
• Tiếp tục dùng iterator/reference cũ sau khi insert hoặc erase làm chúng mất hiệu lực.

10. Quiz và bài tập