Thư Viện STL C++ Nâng Cao

1. Khái niệm & bản chất của các cấu trúc dữ liệu STL nâng cao

Thư viện mẫu chuẩn C++ (Standard Template Library - STL) cung cấp các cấu trúc dữ liệu trừu tượng hiệu năng cao được xây dựng trên nền tảng Cây đỏ-đen (Red-Black Tree) và Bảng băm (Hash Table):

• set / multiset / map: Cấu trúc cây tự cân bằng (Balanced BST), duy trì các phần tử luôn được sắp xếp có thứ tự, hỗ trợ thêm, xóa, tìm kiếm, tìm kiếm nhị phân (lower_bound, upper_bound) trong thời gian logarit $\mathcal{O}(\log N)$.
• unordered_set / unordered_map: Cấu trúc bảng băm (Hash Table), đạt độ phức tạp trung bình $\mathcal{O}(1)$ cho các thao tác tìm kiếm và thêm xóa (nhưng có thể suy biến về $\mathcal{O}(N)$ khi bị đụng độ băm).
• priority_queue (Hàng đợi ưu tiên): Cấu trúc đống nhị phân (Binary Heap), luôn duy trì phần tử lớn nhất (Max-Heap) hoặc nhỏ nhất (Min-Heap) ở đỉnh trong $\mathcal{O}(1)$, thêm và xóa trong $\mathcal{O}(\log N)$.
• Tùy biến hàm so sánh (Custom Struct Comparator / Functor): Tùy chỉnh trật tự sắp xếp phức tạp cho các cấu trúc dữ liệu STL.

2. Bảng so sánh cấu trúc & hiệu năng của các Container STL

3. Tử huyệt lập trình: Bẫy xóa phần tử trong multiset & Bẫy unordered_map

Cảnh báo bẫy lỗi 1: BẪY XÓA TẤT CẢ PHẦN TỬ TRÙNG NHAU TRONG MULTISET

Trong multiset<int> ms, nếu viết ms.erase(val), C++ sẽ xóa sạch toàn bộ mọi phần tử có giá trị bằng val!
Cách xóa đúng duy nhất 1 phần tử: Truyền vào iterator trỏ tới phần tử đó: cpp auto it = ms.find(val); if (it != ms.end()) { ms.erase(it); // Chỉ xóa đúng 1 phần tử tại vị trí it }

Cảnh báo bẫy lỗi 2: BẪY TẤN CÔNG BẢNG BĂM (ANTI-HASH TEST / HASH COLLISION)

unordered_map mặc định trong libstdc++ dùng hàm băm chia dư đơn giản, dễ bị các bộ test sinh đối kháng (Anti-hash tests) làm đụng độ băm khiến thời gian chạy tụt từ $\mathcal{O}(1)$ xuống $\mathcal{O}(N) \implies \text{TLE}$.
Giải pháp: Sử dụng Custom Hash kết hợp thời gian hệ thống (Chrono): cpp struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; unordered_map<long long, int, custom_hash> safe_map;

4. Mẫu cài đặt chuẩn thi đấu: Duy trì trung vị

Bài toán: Cho một luồng số liên tục, sau mỗi số được thêm vào, hãy in ra trung vị của toàn bộ các số đã nhập.

• Chiến lược 2 Heap:
• Max-Heap left_heap chứa nửa nhỏ hơn của dãy số.
• Min-Heap right_heap chứa nửa lớn hơn của dãy số.
• Duy trì kích thước: left_heap.size() luôn bằng right_heap.size() hoặc hơn đúng $1$ phần tử.
• Trung vị luôn là left_heap.top().

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    priority_queue<int> left_heap; // Max-heap
    priority_queue<int, vector<int>, greater<int>> right_heap; // Min-heap

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;

        if (left_heap.empty() || x <= left_heap.top()) left_heap.push(x);
        else right_heap.push(x);

        // Cân bằng kích thước
        if (left_heap.size() > right_heap.size() + 1) {
            right_heap.push(left_heap.top());
            left_heap.pop();
        } else if (right_heap.size() > left_heap.size()) {
            left_heap.push(right_heap.top());
            right_heap.pop();
        }

        cout << left_heap.top() << " ";
    }
    cout << "\n";
    return 0;
}

5. Ranh giới áp dụng