C++ Standard Template Library

🗂️ set, multiset, map và unordered_map

Bốn cấu trúc dữ liệu quan trọng để quản lý phần tử duy nhất, phần tử lặp, ánh xạ khóa–giá trị và tra cứu trung bình O(1). Bài học tập trung vào tư duy chọn đúng container, thao tác thường dùng, độ phức tạp và lỗi dễ gặp.

setDuy nhất + có thứ tự

multisetCho phép trùng + có thứ tự

mapkey → value, key có thứ tự

unordered_mapHash table, trung bình O(1)

Mục tiêu Đặt vấn đề Set Multiset Map Unordered Map So sánh Phân tích Code mẫu Giải thích code Lỗi thường gặp Quiz

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

Cần hiểu

Khác nhau giữa duy nhất và cho phép lặp.
Khác nhau giữa container có thứ tự và hash table.
Các thao tác insert, find, erase, count.
Cách dùng lower_bound, upper_bound với set/multiset.
Cách truy cập map bằng [], at(), find().

Ứng dụng

Loại phần tử trùng.
Đếm tần suất.
Quản lý tập động có thứ tự.
Tìm phần tử gần nhất theo giá trị.
Lưu thông tin theo khóa.
Tra cứu nhanh bằng hash.

1. Đặt vấn đề

Bài toán mở đầu.
Một chương trình nhận liên tục các giá trị hoặc cặp (khóa, dữ liệu). Ta cần:

lưu mỗi giá trị đúng một lần;
hoặc lưu cả các giá trị lặp;
đếm số lần xuất hiện;
tìm nhanh dữ liệu theo khóa;
đôi khi phải duyệt theo thứ tự tăng dần.

1.1. Vì sao vector chưa đủ?

Dùng vector, tìm kiếm hoặc kiểm tra trùng thường mất O(n). Chèn vào giữa để giữ thứ tự cũng mất O(n).

1.2. Mỗi yêu cầu cần một cấu trúc khác nhau

Nhu cầu	Container phù hợp	Lý do
Mỗi giá trị xuất hiện một lần, cần thứ tự	`set`	Duy nhất, tự sắp tăng.
Cho phép phần tử trùng, cần thứ tự	`multiset`	Lưu đầy đủ số lần xuất hiện.
Ánh xạ key → value, cần duyệt key tăng dần	`map`	Key duy nhất, có thứ tự.
Ánh xạ key → value, ưu tiên tra cứu nhanh	`unordered_map`	Hash table, trung bình O(1).

Kết luận: Không có container tốt nhất cho mọi bài. Hãy chọn theo: có cần thứ tự không, có cho phép trùng không, dữ liệu là giá trị hay key–value.

2. set – tập hợp duy nhất có thứ tự

Đặc điểm

Không lưu phần tử trùng.
Duyệt theo thứ tự tăng dần mặc định.
Thường cài bằng cây cân bằng.
insert/find/erase O(log n).

Thao tác

s.insert(x)
s.find(x)
s.count(x) chỉ trả 0 hoặc 1.
s.erase(x)
s.lower_bound(x)
s.upper_bound(x)

2.1. Mô phỏng set

Giá trị x

3. multiset – tập có thứ tự và cho phép trùng

Đặc điểm

Cho phép nhiều phần tử bằng nhau.
Tự giữ thứ tự tăng dần.
count(x) có thể lớn hơn 1.
Có thể xóa một bản sao hoặc xóa tất cả.

Hai kiểu erase

ms.erase(x): xóa tất cả phần tử bằng x.
auto it=ms.find(x); ms.erase(it);: xóa đúng một bản sao.

3.1. Mô phỏng multiset

Giá trị x

4. map – ánh xạ key → value có thứ tự

Đặc điểm

Mỗi key xuất hiện tối đa một lần.
Key được duyệt tăng dần.
find/insert/erase O(log n).
Phù hợp đếm tần suất cần thứ tự.

Truy cập

mp[key]: tạo key nếu chưa có.
mp.at(key): không tạo key, có thể ném ngoại lệ.
mp.find(key): kiểm tra an toàn.
mp.emplace(key,value).

4.1. Mô phỏng map đếm tần suất

Key Giá trị cộng thêm

5. unordered_map – hash table

Đặc điểm

Không đảm bảo thứ tự duyệt.
Tra cứu trung bình O(1).
Trường hợp xấu có thể O(n).
Key phải có hash phù hợp.

Khái niệm hash

Hash biến key thành chỉ số bucket.
Nhiều key có thể vào cùng bucket: collision.
reserve() và max_load_factor() giúp giảm rehash.

5.1. Mô phỏng bucket

Key số nguyên Value

Không dùng unordered_map nếu cần thứ tự key, lower_bound, phần tử nhỏ nhất/lớn nhất hoặc duyệt có thứ tự.

6. Bảng so sánh nhanh

Container	Trùng?	Có thứ tự?	Find/Insert/Erase	lower_bound?	Trường hợp dùng
`set`	Không	Có	O(log n)	Có	Tập duy nhất có thứ tự.
`multiset`	Có	Có	O(log n)	Có	Duy trì nhiều bản sao có thứ tự.
`map`	Key không trùng	Có	O(log n)	Có theo key	Key-value cần thứ tự.
`unordered_map`	Key không trùng	Không	O(1) trung bình	Không	Tra cứu nhanh, không cần thứ tự.

7. Phân tích và nguyên tắc chọn

Cần thứ tự?

Có → set/multiset/map. Không → cân nhắc unordered_map.

Có phần tử trùng?

Cần giữ trùng → multiset. Chỉ cần duy nhất → set.

Dữ liệu key–value?

Có → map hoặc unordered_map.

Cần lower_bound?

Dùng cấu trúc có thứ tự; unordered_map không hỗ trợ.

Cần tốc độ trung bình?

unordered_map thường nhanh hơn map nhưng không có bảo đảm O(log n).

Dữ liệu bị tấn công?

Hash xấu có thể làm unordered_map chậm. Trong một số bài, map ổn định hơn.

8. Code mẫu

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

int main() {
    set<int> s = {5, 2, 8, 2};

    s.insert(7);
    s.insert(5); // không tạo bản sao mới

    if (s.find(7) != s.end()) {
        cout << "Ton tai 7\n";
    }

    auto it = s.lower_bound(6);
    if (it != s.end()) {
        cout << "Phan tu dau tien >= 6: " << *it << '\n';
    }

    s.erase(2);

    for (int x : s) {
        cout << x << ' ';
    }
}

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

int main() {
    multiset<int> ms = {5, 2, 5, 7, 5};

    cout << ms.count(5) << '\n'; // 3

    auto it = ms.find(5);
    if (it != ms.end()) {
        ms.erase(it); // xóa đúng một số 5
    }

    // ms.erase(5); // xóa tất cả số 5

    for (int x : ms) {
        cout << x << ' ';
    }
}

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

int main() {
    vector<string> words = {
        "apple", "banana", "apple", "orange"
    };

    map<string,int> frequency;

    for (const string& word : words) {
        frequency[word]++;
    }

    for (const auto& [word, count] : frequency) {
        cout << word << ' ' << count << '\n';
    }

    if (frequency.find("pear") == frequency.end()) {
        cout << "Khong co pear\n";
    }
}

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

int main() {
    unordered_map<long long,int> frequency;

    frequency.reserve(200000);
    frequency.max_load_factor(0.7);

    int n;
    cin >> n;

    while (n--) {
        long long x;
        cin >> x;
        frequency[x]++;
    }

    long long value;
    cin >> value;

    auto it = frequency.find(value);
    if (it == frequency.end()) {
        cout << 0;
    } else {
        cout << it->second;
    }
}

9. Giải thích code

9.1. insert của set trả về gì?

s.insert(x) trả về pair<iterator,bool>. Giá trị bool cho biết phần tử có thực sự được chèn mới hay đã tồn tại.

9.2. lower_bound và upper_bound

lower_bound(x): phần tử đầu tiên ≥ x.
upper_bound(x): phần tử đầu tiên > x.

9.3. Vì sao multiset.erase(x) nguy hiểm?

ms.erase(x) xóa tất cả bản sao bằng x. Muốn xóa một bản sao, phải tìm iterator rồi gọi erase(it).

9.4. map[key] có tác dụng phụ gì?

Nếu key chưa tồn tại, map[key] sẽ tạo key mới với value mặc định. Vì thế, chỉ để kiểm tra tồn tại thì nên dùng find() hoặc contains() từ C++20.

9.5. Vì sao unordered_map chỉ O(1) trung bình?

Nhiều key có thể rơi vào cùng bucket. Nếu collision nhiều, thao tác có thể chậm. Trường hợp xấu lý thuyết là O(n).

9.6. reserve và max_load_factor

reserve(n) chuẩn bị đủ bucket cho khoảng n phần tử. max_load_factor(x) giới hạn mật độ trung bình trên mỗi bucket, giúp giảm rehash/collision.

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

Dùng set rồi mong giữ phần tử trùng.
Dùng multiset.erase(x) nhưng chỉ muốn xóa một phần tử.
Dereference iterator khi iterator bằng end().
Dùng map[key] chỉ để kiểm tra tồn tại và vô tình tạo key.
Cho rằng unordered_map luôn O(1).
Chờ đợi thứ tự tăng dần khi duyệt unordered_map.
Dùng unordered_map với key tự định nghĩa nhưng không viết hash.
Giữ iterator rồi erase phần tử đó và tiếp tục dùng iterator cũ.
Nhầm count() của set luôn có thể lớn hơn 1.

11. Quiz và bài tập

Câu 1. Container nào giữ phần tử duy nhất và có thứ tự?

Câu 2. Cách xóa đúng một bản sao x trong multiset?

Câu 3. unordered_map có đặc điểm nào?

📘 Cơ bản

Loại phần tử trùng bằng set.
Đếm tần suất bằng map.
In key theo thứ tự tăng dần.

📗 Trung bình

Tìm phần tử gần x bằng lower_bound.
Duy trì median bằng hai multiset.
Two Sum bằng unordered_map.

📙 Nâng cao

Sliding window dùng multiset.
Đếm đoạn tổng K bằng unordered_map.
Coordinate compression với set/map.

🐉 Định hướng CP

Custom comparator cho set.
Custom hash cho pair.
So sánh map, unordered_map và gp_hash_table.