Multimap dùng để lưu nhiều cặp key → value, trong đó một key có thể xuất hiện nhiều lần. Trang này tổng hợp lý thuyết, ví dụ, lỗi thường gặp và 5 bài tập kèm bộ test.
multimap<Key, Value> là container liên kết trong C++ STL, lưu các phần tử dạng pair<const Key, Value>. Khác với map, nhiều phần tử trong multimap có thể có cùng key.
#include <bits/stdc++.h> using namespace std; multimap<string, int> diem; // key: tên, value: điểm multimap<int, string> hocSinh; // key: điểm, value: tên multimap<int, string, greater<int>> giam; // key giảm dần
| Thao tác | Cú pháp | Ý nghĩa |
|---|---|---|
| Thêm phần tử | mp.insert({'}key, value{'}) | Thêm một cặp key-value, kể cả khi key đã tồn tại. |
| Đếm theo key | mp.count(key) | Trả về số phần tử có key đang xét. |
| Tìm một phần tử | mp.find(key) | Trả về iterator đến một phần tử có key đó, hoặc end(). |
| Lấy cả nhóm | mp.equal_range(key) | Trả về cặp iterator bao phủ tất cả phần tử có cùng key. |
| Cận dưới | mp.lower_bound(key) | Iterator đầu tiên có key không nhỏ hơn key đang xét. |
| Cận trên | mp.upper_bound(key) | Iterator đầu tiên có key lớn hơn key đang xét. |
| Xóa theo key | mp.erase(key) | Xóa tất cả phần tử có key đó. |
multimap<string, int> mp;
mp.insert({"An", 8});
mp.insert({"Binh", 7});
mp.insert({"An", 9});
auto range = mp.equal_range("An");
for (auto it = range.first; it != range.second; ++it) {
cout << it->second << " ";
}
// Kết quả: 8 9multimap<int, string> mp;
mp.insert({8, "An"});
mp.insert({9, "Binh"});
mp.insert({8, "Chi"});
int L = 8, R = 9;
for (auto it = mp.lower_bound(L); it != mp.upper_bound(R); ++it) {
cout << it->second << " ";
}
// In các value có key trong [L, R]| Tiêu chí | map | multimap |
|---|---|---|
| Key trùng nhau | Không cho phép | Cho phép |
| Truy cập bằng [] | Có thể dùng mp[key] | Không dùng được [] như map |
| Thêm phần tử cùng key | Ghi đè hoặc giữ một value tùy cách thêm | Thêm thêm một phần tử mới |
| Dùng khi | Mỗi key chỉ có một value | Mỗi key có thể có nhiều value |
Một từ khóa có thể có nhiều nghĩa khác nhau.
Một điểm số có thể có nhiều học sinh cùng đạt.
Một thời điểm có thể có nhiều sự kiện.
Một mã người dùng có nhiều lần truy cập hoặc nhiều giao dịch.
Gom nhiều value theo cùng một key để xử lý nhanh.
Dùng lower_bound và upper_bound để lấy dữ liệu theo khoảng key.
| Bài | Tên bài | Kỹ năng chính | Test |
|---|---|---|---|
| 1 | Từ điển nhiều nghĩa | insert, equal_range | 20 test / 4 sub |
| 2 | Liệt kê học sinh theo khoảng điểm | lower_bound, upper_bound | 20 test / 4 sub |
| 3 | Thêm, xóa, thống kê bản ghi | erase, count, equal_range | 20 test / 4 sub |
| 4 | Lịch sự kiện | truy vấn khoảng động | 20 test / 4 sub |
| 5 | Tra cứu sản phẩm theo giá | key trùng + query | 20 test / 4 sub |
Cho n cặp từ khóa - nghĩa. Một từ khóa có thể xuất hiện nhiều lần với nhiều nghĩa khác nhau. Với mỗi truy vấn, hãy in tất cả nghĩa của từ đó theo thứ tự xuất hiện trong dữ liệu vào.
5 3 code ma_lenh map anh_xa code lap_trinh key khoa code chuong_trinh code map stack
ma_lenh lap_trinh chuong_trinh anh_xa NONE
Cho danh sách học sinh và điểm. Có q truy vấn [L, R]. Với mỗi truy vấn, in tên các học sinh có điểm nằm trong đoạn [L, R], theo thứ tự điểm tăng dần.
5 2 An 8 Binh 7 Chi 8 Dung 10 Hoa 6 7 8 9 10
Binh An Chi Dung
Ban đầu có n bản ghi dạng key value. Sau đó có q thao tác: 1 k v thêm bản ghi, 2 k xóa tất cả bản ghi có key k, 3 k in số lượng và tổng value của key k.
4 5 1 10 2 5 1 7 3 8 3 1 1 1 4 3 1 2 1 3 1
2 17 3 21 0 0
Có n sự kiện ban đầu, mỗi sự kiện có thời điểm t và tên. Có q thao tác: 1 L R in các sự kiện có thời điểm trong [L, R]; 2 t name thêm sự kiện mới.
3 4 5 hoc 10 thi 10 nop 1 1 10 2 7 on 1 6 9 1 11 20
hoc thi nop on NONE
Quản lý danh sách sản phẩm theo giá. Có q thao tác: 1 p in các mã sản phẩm có giá p; 2 L R in số sản phẩm có giá trong [L, R]; 3 p code thêm sản phẩm mới.
4 5 10 A 20 B 10 C 30 D 1 10 2 10 20 3 10 E 1 10 2 25 40
A C 3 A C E 1