Vùng chứa liên kết: map & set
vector đánh số phần tử bằng chỉ số nguyên chạy từ 0. Nhưng rất nhiều bài toán
lại cần đánh số bằng thứ khác: đếm số lần mỗi từ xuất hiện, tra điểm theo mã
sinh viên, đếm tần suất mỗi ký tự. Đó là việc của std::map.
Đổi lại, map mang theo một cái bẫy mà không ai đoán ra nếu chưa từng bị: m[k]
với khoá chưa có không báo lỗi, không trả về giá trị rỗng, mà lặng lẽ chèn một
phần tử mới rồi trả về tham chiếu tới nó. Nghĩa là một câu lệnh trông như phép
đọc lại làm đổi vùng chứa. Bài này gỡ đúng chỗ đó, và ba chỗ liên quan.
Thử ngay: gọi một thao tác, xem size đổi theo
Chọn thao tác, đổi khoá, rồi nhìn cặp số size ở góc phải chứ đừng chỉ nhìn
giá trị trả về. Cặp số ấy mới phân biệt được bốn cách tra cứu.
m[k]
| vị trí | khoá | giá trị |
|---|---|---|
| 0 | lan | 3 |
| 1 | binh | 1 |
| 2 | an | 2 |
| end() · vị trí 3, không trỏ vào phần tử nào | ||
| vị trí | khoá | giá trị |
|---|---|---|
| 0 | an | 2 |
| 1 | binh | 1 |
| 2 | cuong | 0 |
| 3 | lan | 3 |
| end() · vị trí 4, không trỏ vào phần tử nào | ||
Khoá `cuong` CHƯA có, nên `m["cuong"]` chèn một phần tử mới với giá trị khởi tạo bằng 0 rồi trả về tham chiếu tới nó. Kích thước đi từ 3 lên 4. Một phép ĐỌC vừa làm đổi map, và không có cảnh báo nào.
Bảng bên phải là map sau thao tác. Hàng end() ở cuối không phải một phần tử: nó
là vị trí ngay sau phần tử cuối, chỗ mà find trả về khi không tìm thấy. Khoá
luôn nằm theo thứ tự tăng dần vì map tự sắp, nên thứ tự chèn không đổi được
thứ tự duyệt.
Khai báo, thêm, và duyệt
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<string, int> diem;
diem["lan"] = 3;
diem["binh"] = 1;
diem["an"] = 2;
for (const auto& [ten, so] : diem) { // C++17
cout << ten << " = " << so << endl;
}
return 0;
}
Kết quả in ra an = 2, binh = 1, lan = 3. Chú ý thứ tự: không phải thứ tự
bạn gán, mà là thứ tự tăng dần của khoá. map giữ dữ liệu trong một cây tìm
kiếm cân bằng, nên duyệt nó luôn cho ra dãy đã sắp mà không cần gọi sort.
Cú pháp const auto& [ten, so] là structured binding của C++17: nó tách cặp
khoá giá trị thành hai tên riêng. Trước C++17 bạn viết dài hơn và dễ quên hơn:
for (map<string, int>::const_iterator it = diem.begin(); it != diem.end(); ++it) {
cout << it->first << " = " << it->second << endl;
}
it->first là khoá, it->second là giá trị. Hai tên ấy đáng nhớ vì mọi thông báo
lỗi của trình biên dịch đều gọi chúng như vậy.
Bốn cách tra cứu, và chỉ một cách chèn ngầm
Đây là bảng cần thuộc:
| viết | khoá đã có | khoá chưa có | có làm size đổi không |
|---|---|---|---|
m[k] | trả tham chiếu tới giá trị | chèn phần tử giá trị 0 rồi trả tham chiếu | có, khi khoá chưa có |
m.at(k) | trả tham chiếu tới giá trị | ném std::out_of_range | không bao giờ |
m.find(k) | trả iterator tới phần tử | trả m.end() | không bao giờ |
m.count(k) | trả 1 | trả 0 | không bao giờ |
Trên sim ở đầu bài, bấm nút [] khoá thiếu: size đi từ 3 lên 4 và một
khoá cuong với giá trị 0 xuất hiện. Bấm at khoá thiếu: cùng khoá ấy, cùng
map ấy, nhưng lần này chương trình ném std::out_of_range và map không đổi.
:::caution Câu lệnh kiểm tra lại tạo ra thứ nó đi tìm
if (diem["cuong"] > 0) { ... } // SAI: dòng này vừa TẠO ra khoá "cuong"
if (diem.count("cuong")) { ... } // đúng
if (diem.contains("cuong")) { } // đúng, C++20, đọc rõ nghĩa nhất
Cái hiểm là chương trình vẫn chạy và vẫn cho kết quả trông hợp lý: diem["cuong"]
trả về 0, điều kiện sai, nhánh không chạy. Chỉ có diem.size() là lớn lên, và
nếu về sau bạn duyệt map để in bảng điểm thì cuong hiện ra với 0 điểm.
:::
1#include <iostream>2#include <map>3#include <string>4using namespace std;56int main() {7 map<string, int> diem = {{"an", 2}, {"binh", 1}, {"lan", 3}};8 string can_tra[] = {"cuong", "dung", "lan", "cuong"};910 for (const string& ten : can_tra) {11 cout << ten << ": " << diem[ten] << endl;12 }13 cout << "size = " << diem.size() << endl;14 return 0;15}
Cách viết chỉ đọc, không chèn:
for (const string& ten : can_tra) {
auto it = diem.find(ten);
if (it != diem.end()) cout << ten << ": " << it->second << endl;
else cout << ten << ": chua co" << endl;
}
Với dãy tra cứu trên, lối [] để lại map 5 khoá còn lối find giữ nguyên 3.
Chênh lệch đúng bằng số khoá lạ đã tra.
:::note Chèn ngầm không phải lúc nào cũng sai
Ở bài toán đếm từ, dem[tu]++ dựa hẳn vào chèn ngầm: từ mới được tạo ra với giá
trị 0 rồi tăng lên 1, đúng ý ta và ngắn hơn hẳn. Vấn đề không nằm ở [], mà
nằm ở chỗ dùng [] khi ta chỉ muốn đọc.
:::
insert không ghi đè, [] = v thì có
map<string, int> diem = {{"lan", 3}};
diem.insert({"lan", 99}); // lan VẪN là 3
diem["lan"] = 99; // lan thành 99
diem.insert_or_assign("lan", 99); // C++17, thành 99, và nói rõ ý định
insert trả về một cặp: first là iterator tới phần tử mang khoá đó, second là
bool cho biết có chèn thật hay không. Bỏ qua giá trị bool ấy là cách phổ
biến nhất để một bản cập nhật im lặng không xảy ra:
auto kq = diem.insert({"lan", 99});
if (!kq.second) cout << "da co san, gia tri hien tai la " << kq.first->second;
Trên sim, bấm insert khoá đã có rồi bấm [] = v khoá đã có để thấy hai
hành vi nằm cạnh nhau trên cùng một map.
Xoá, và cái bẫy iterator trong vòng lặp
diem.erase("lan"); // trả về 1 nếu có xoá, 0 nếu khoá không tồn tại
Xoá một khoá không tồn tại là hợp lệ, không ném gì, chỉ trả về 0. Nhưng xoá
trong lúc đang duyệt thì phải cẩn thận:
for (auto it = diem.begin(); it != diem.end(); ) {
if (it->second == 0) it = diem.erase(it); // erase trả về iterator KẾ TIẾP
else ++it;
}
Hai chi tiết. Thứ nhất, phần thứ ba của for để trống, vì việc tăng iterator do
thân vòng lặp lo. Thứ hai, erase(it) làm it cũ vô hiệu, nên phải nhận lại
iterator kế tiếp mà chính erase trả về. Viết diem.erase(it); ++it; là dùng một
iterator đã chết, và đó là hành vi không xác định, đúng loại bẫy mà bài
Chuỗi ký tự đã gặp với c_str().
Với map, xoá một phần tử chỉ vô hiệu iterator trỏ vào đúng phần tử ấy; các
iterator khác vẫn dùng được. vector thì không được như vậy: xoá giữa mảng làm
mọi iterator từ chỗ đó trở đi vô hiệu, và push_back có thể làm vô hiệu tất cả.
map hay unordered_map
#include <unordered_map>
unordered_map<string, int> nhanh;
map | unordered_map | |
|---|---|---|
| cấu trúc bên trong | cây cân bằng | bảng băm |
| thứ tự duyệt | tăng dần theo khoá | không hứa gì |
| tra cứu | O(log n) | O(1) trung bình |
| cần gì ở kiểu khoá | có < | có hàm băm và == |
Chọn unordered_map khi bạn chỉ tra cứu và không quan tâm thứ tự. Chọn map khi
bạn cần duyệt theo thứ tự, cần khoá nhỏ nhất hay lớn nhất, hoặc cần tìm theo
khoảng. Điểm quan trọng: operator[] của unordered_map cũng chèn ngầm y hệt,
nên đổi kiểu vùng chứa không cứu bạn khỏi cái bẫy ở trên.
set: khi chỉ cần biết có hay không
set là map bỏ đi phần giá trị. Nó giữ các phần tử duy nhất và đã sắp.
#include <set>
set<string> da_gap;
da_gap.insert("lan");
da_gap.insert("lan"); // không thêm gì, set giữ khoá duy nhất
cout << da_gap.size() << endl; // 1
if (da_gap.count("lan")) cout << "da gap roi" << endl;
set không có operator[], và đó là một điều may: cái bẫy chèn ngầm không tồn
tại ở đây. Muốn hỏi thì dùng count, find, hoặc contains của C++20.
Bài tập thực hành
Bài tập 1: đếm tần suất từ rồi in theo thứ tự chữ cái
#include <iostream>
#include <map>
#include <sstream>
#include <string>
using namespace std;
int main() {
string dong;
getline(cin, dong);
map<string, int> dem;
istringstream luong(dong);
string tu;
while (luong >> tu) dem[tu]++; // chèn ngầm ở đây là ĐÚNG ý
for (const auto& [t, n] : dem) cout << t << " " << n << endl;
return 0;
}
istringstream biến một chuỗi thành luồng để dùng >> tách theo khoảng trắng, y
hệt cách cin >> tách dữ liệu nhập. Kết quả in ra đã sắp sẵn theo chữ cái vì
map giữ như vậy, không cần gọi sort.
Bài tập 2: đảo map thành giá trị sang khoá
map<int, vector<string>> dao(const map<string, int>& g) {
map<int, vector<string>> r;
for (const auto& [ten, so] : g) r[so].push_back(ten);
return r;
}
Ở đây r[so] chèn ngầm một vector rỗng khi so xuất hiện lần đầu, rồi
push_back thêm tên vào. Đó chính là kiểu dùng mà chèn ngầm giúp ta viết ngắn.
Giá trị phải là vector chứ không phải string, vì hai người có thể cùng điểm và
map thì không cho hai khoá trùng.
Bài tập 3: giao của hai tập
set<string> giao(const set<string>& a, const set<string>& b) {
set<string> r;
for (const string& x : a) if (b.count(x)) r.insert(x);
return r;
}
Duyệt tập nhỏ hơn và tra tập lớn hơn thì nhanh hơn, vì số lần tra bằng kích thước
tập được duyệt. Thư viện chuẩn có sẵn std::set_intersection trong <algorithm>,
và nó chạy tuyến tính vì khai thác được việc cả hai tập đã sắp.
Bài tập 4: tìm khoá có giá trị lớn nhất
string cao_nhat(const map<string, int>& g) {
if (g.empty()) return "";
auto it = max_element(g.begin(), g.end(),
[](const auto& x, const auto& y) { return x.second < y.second; });
return it->first;
}
Việc phải viết một hàm so sánh riêng nhắc lại một điều: map sắp theo khoá,
nên nó không giúp gì cho câu hỏi về giá trị. Muốn truy vấn theo giá trị nhiều
lần thì hãy giữ thêm một cấu trúc thứ hai, đừng quét lại mỗi lần.
Câu hỏi tự kiểm
- 1map<string,int> m có 3 khoá và không có khoá "x". Sau khi chạy cout << m["x"]; thì m.size() bằng bao nhiêu?
- 2map<string,int> m = {{"lan", 3}}; rồi m.insert({"lan", 99}); thì giá trị của "lan" là bao nhiêu?
- 3Đoạn for (auto it = m.begin(); it != m.end(); ) { if (it->second == 0) m.erase(it); else ++it; } sai ở đâu?
- 4Khác biệt nào giữa map và unordered_map là thật?
- 5Vì sao viết dem[tu]++ để đếm tần suất từ lại được coi là dùng đúng, dù nó dựa vào chèn ngầm?
Tóm tắt
map đánh số phần tử bằng khoá bất kỳ thay vì chỉ số nguyên, và giữ chúng
đã sắp theo khoá, nên duyệt nó không cần gọi sort.
m[k] với khoá chưa có chèn một phần tử giá trị 0 rồi trả tham chiếu tới
nó. Đây là phép đọc duy nhất làm đổi vùng chứa, và nó không cảnh báo gì. Trên sim
ở đầu bài, size đi từ 3 lên 4 chỉ vì một lần đọc.
Ba cách tra cứu còn lại đều an toàn: at ném std::out_of_range, find trả
end(), count trả 0. Tra bốn khoá trong đó hai khoá lạ: lối [] để lại map
5 phần tử, lối find giữ nguyên 3.
insert không ghi đè khi khoá đã có, và nó báo bằng false ở phần thứ hai
của cặp trả về. Muốn ghi đè thì dùng m[k] = v hoặc insert_or_assign.
erase(it) làm it vô hiệu, nên trong vòng lặp phải viết it = m.erase(it).
unordered_map nhanh hơn nhưng không hứa thứ tự, và operator[] của nó cũng chèn
ngầm y hệt. set là map không có phần giá trị, và vì nó không có operator[]
nên cái bẫy chèn ngầm không tồn tại ở đó.