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++.
- 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óm | Container | Cấu trúc bên trong |
|---|---|---|
| Tuần tự | vector, deque, list | Mả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, multiset | Cây đỏ – đen, O(log n) |
| Liên kết không thứ tự | unordered_set, unordered_map | Bảng băm, O(1) trung bình |
| Bộ thích ứng | stack, queue, priority_queue | Bọ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 |
|---|---|---|
| vector | Mảng động | Truy cập O(1) |
| set, map | Cây cân bằng, có thứ tự | O(log n) |
| unordered_map | Bảng băm | O(1) trung bình |
| priority_queue | Heap | O(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
}- Đếm tần suất từ bằng map.
- Loại bỏ phần tử trùng bằng set.
- Tìm k số lớn nhất bằng priority_queue.
- 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.

