Thư viện chuẩn STL cung cấp sẵn các cấu trúc dữ liệu hiệu quả. Đây là công cụ không thể thiếu khi thi lập trình và làm phần mềm C++.

55 phútTrung cấp
Bạn sẽ học được
  • pair, tuple
  • set, multiset
  • map, unordered_map
  • stack, queue, priority_queue

Cơ sở lý thuyết

STL (Standard Template Library) gồm bốn thành phần: container (lưu trữ), iterator (con trỏ tổng quát để duyệt), algorithm (thuật toán làm việc qua iterator) và function object. Nhờ template, mỗi container/thuật toán dùng được với mọi kiểu dữ liệu mà vẫn đạt hiệu năng như mã viết tay.

NhómContainerCấu trúc bên trong
Tuần tựvector, deque, listMảng động, mảng các khối, danh sách liên kết đôi
Liên kết có thứ tựset, map, multisetCây đỏ – đen, O(log n)
Liên kết không thứ tựunordered_set, unordered_mapBảng băm, O(1) trung bình
Bộ thích ứngstack, queue, priority_queueBọc container khác (deque, vector + heap)

Chọn container theo thao tác chính: truy cập theo chỉ số → vector; tìm kiếm theo khóa → unordered_map; cần thứ tự hoặc tìm phần tử gần nhất (lower_bound) → map/set; luôn lấy phần tử lớn nhất → priority_queue.

Ví dụ

#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#include <stack>

set<int> s = {5, 1, 5, 3};           // {1, 3, 5} tự sắp xếp, không trùng
map<string, int> dem;
for (string tu : {"a", "b", "a"}) dem[tu]++;
for (auto& [tu, sl] : dem) cout << tu << ":" << sl << " ";

unordered_map<int, int> bam;          // bảng băm, O(1) trung bình
pair<string, double> sv = {"Lan", 9};

priority_queue<int> pq;               // lấy lớn nhất trước
pq.push(3); pq.push(7); cout << pq.top();   // 7
stack<int> st; queue<int> q;
ContainerĐặc điểmĐộ phức tạp
vectorMảng độngTruy cập O(1)
set, mapCây cân bằng, có thứ tựO(log n)
unordered_mapBảng bămO(1) trung bình
priority_queueHeapO(log n)

Ứng dụng thực tế

Bài toán: hệ thống đặt phòng họp: kiểm tra một khoảng thời gian mới có trùng lịch đã đặt không. Dùng map (có thứ tự theo giờ bắt đầu) và lower_bound để chỉ kiểm tra hai lịch lân cận, O(log n):

#include <map>
map<int, int> lich;        // giờ bắt đầu (phút) → giờ kết thúc
bool datPhong(int bd, int kt) {
    auto sau = lich.lower_bound(bd);                       // lịch bắt đầu từ bd trở đi
    if (sau != lich.end() && sau->first < kt) return false;
    if (sau != lich.begin()) {
        auto truoc = prev(sau);
        if (truoc->second > bd) return false;
    }
    lich[bd] = kt;
    return true;
}
int main() {
    cout << datPhong(480, 540) << datPhong(530, 600) << datPhong(540, 600);   // 1 0 1
}
Thực hành
  1. Đếm tần suất từ bằng map.
  2. Loại bỏ phần tử trùng bằng set.
  3. Tìm k số lớn nhất bằng priority_queue.
Tóm tắt bài học
  • STL có sẵn cấu trúc dữ liệu hiệu quả.
  • map/set có thứ tự, unordered_map nhanh hơn.
  • Chọn container theo thao tác cần dùng.