unordered_map là một cấu trúc dữ liệu dùng để lưu trữ các cặp khóa (key) và giá trị (value).
Mỗi khóa chỉ xuất hiện duy nhất một lần và được dùng để truy cập đến giá trị tương ứng.
Khác với vector hay mảng, unordered_map không truy cập phần tử bằng chỉ số (0, 1, 2, ...) mà truy cập bằng khóa (key).
Khóa có thể là nhiều kiểu dữ liệu khác nhau như int, long long, char, string,...
Ví dụ:
| Khóa (Key) | Giá trị (Value) |
|---|---|
| 3 | 15 |
| 8 | 7 |
| 100 | 25 |
Ta có thể truy cập các giá trị trên bằng khóa:
mp[3] = 15;
mp[8] = 7;
mp[100] = 25;
Khi nào nên sử dụng unordered_map?
Ghi nhớ:
- unordered_map lưu dữ liệu theo cặp (key, value).
- Truy cập dữ liệu bằng khóa, không phải bằng chỉ số.
- Mỗi khóa chỉ xuất hiện một lần.
- Rất thích hợp để đếm tần suất và tra cứu dữ liệu nhanh.
- Để sử dụng unordered_map, cần khai báo thư viện:
#include <unordered_map>
- Có thể khai báo unordered_map theo cú pháp:
unordered_map<kiểu khóa, kiểu giá trị> tên_biến;
- Trong đó:
Ví dụ:
unordered_map<int, int> mp;
Lưu các cặp khóa và giá trị đều có kiểu int.
unordered_map<long long, int> cnt;
Khóa có kiểu long long, giá trị có kiểu int.
unordered_map<char, int> dem;
Dùng để đếm số lần xuất hiện của từng ký tự.
unordered_map<string, int> word;
Dùng để đếm số lần xuất hiện của từng từ.
Một số kiểu khai báo thường gặp
| Khai báo | Mục đích sử dụng |
|---|---|
unordered_map<int, int> |
Lưu các cặp số nguyên. |
unordered_map<long long, int> |
Đếm các số nguyên rất lớn. |
unordered_map<char, int> |
Đếm số lần xuất hiện của ký tự. |
unordered_map<string, int> |
Đếm số lần xuất hiện của từ hoặc chuỗi. |
Ghi nhớ:
- unordered_map luôn khai báo theo dạng unordered_map<Key, Value>.
- Khóa (Key) dùng để truy cập dữ liệu.
- Giá trị (Value) là dữ liệu được lưu tương ứng với khóa.
- Có thể sử dụng nhiều kiểu dữ liệu khác nhau cho khóa và giá trị.
Khác với vector, unordered_map không truy cập phần tử bằng chỉ số mà truy cập bằng khóa (key).
Cú pháp:
tên_unordered_map[khóa]
Có thể dùng để gán giá trị, lấy giá trị hoặc cập nhật giá trị của một khóa.
* Gán giá trị
mp[5] = 100;
mp[8] = 200;
mp[15] = 300;
Kết quả:
| Khóa (Key) | Giá trị (Value) |
|---|---|
| 5 | 100 |
| 8 | 200 |
| 15 | 300 |
* Lấy giá trị
cout << mp[8];
Kết quả:
200
* Truy cập bằng phương thức at()
Ngoài cú pháp mp[key], có thể truy cập giá trị bằng phương thức at().
cout << mp.at(8);
Kết quả:
200
Nếu khóa chưa tồn tại, phương thức at() sẽ phát sinh lỗi trong khi thực thi chương trình.
unordered_map<int, int> mp;
cout << mp.at(100);
Chương trình sẽ báo lỗi vì khóa 100 chưa tồn tại.
* Cập nhật giá trị
mp[8] = 500;
Giá trị của khóa 8 được thay đổi từ 200 thành 500.
* Tăng hoặc giảm giá trị
mp[5]++;
mp[5] += 10;
mp[5]--;
Đây là cách sử dụng rất phổ biến khi đếm số lần xuất hiện của các giá trị.
* Nếu khóa chưa tồn tại
Khi truy cập một khóa chưa có trong unordered_map bằng cú pháp mp[key], khóa đó sẽ được tự động tạo và giá trị mặc định bằng 0 (đối với kiểu số).
unordered_map<int, int> mp;
cout << mp[100];
Kết quả:
0
Sau câu lệnh trên, khóa 100 đã được thêm vào unordered_map với giá trị bằng 0.
Ghi nhớ:
- Truy cập phần tử bằng cú pháp mp[key] hoặc mp.at(key).
- mp[key] có thể dùng để gán, lấy hoặc cập nhật giá trị.
- Nếu khóa chưa tồn tại, mp[key] sẽ tự tạo khóa mới với giá trị mặc định.
- mp.at(key) chỉ truy cập được khóa đã tồn tại, nếu khóa chưa có chương trình sẽ phát sinh lỗi.
- Cú pháp mp[key]++ thường được dùng để đếm số lần xuất hiện của dữ liệu.
unordered_map* Các hàm/phương thức của unordered_map
- Thêm hoặc cập nhật phần tử:
mp[key] = value; // thêm mới hoặc cập nhật giá trị
mp[key]++; // tăng giá trị lên 1
mp[key] += x; // cộng thêm x vào giá trị
mp.insert({key, value}); // thêm cặp (key, value)
mp.insert(make_pair(key, value));// thêm cặp (key, value)
mp.emplace(key, value); // thêm cặp (key, value)
- Kiểm tra khóa:
mp.count(key); // trả về 1 nếu tồn tại, ngược lại trả về 0
mp.find(key); // tìm khóa, trả về iterator
mp.contains(key); // kiểm tra khóa (C++20)
- Xóa phần tử:
mp.erase(key); // xóa khóa key
mp.erase(iterator); // xóa phần tử tại iterator
- Các thao tác khác:
mp.size(); // số lượng cặp (key, value)
mp.clear(); // xóa toàn bộ dữ liệu
mp.empty(); // kiểm tra unordered_map có rỗng hay không
mp.begin(); // iterator tới phần tử đầu tiên
mp.end(); // iterator sau phần tử cuối cùng
mp[key]; // truy cập hoặc tạo khóa mới
mp.at(key); // truy cập khóa đã tồn tại
mp.max_size(); // số phần tử tối đa có thể lưu
mp.bucket_count(); // số bucket hiện có
mp.bucket(key); // bucket chứa khóa key
mp.bucket_size(i); // số phần tử trong bucket i
mp.load_factor(); // hệ số tải hiện tại
mp.max_load_factor(); // hệ số tải tối đa
mp.reserve(n); // cấp phát trước cho khoảng n phần tử
mp.rehash(n); // thay đổi số bucket
mp.swap(mp2); // đổi dữ liệu của hai unordered_map
mp.hash_function(); // hàm băm đang sử dụng
mp.key_eq(); // hàm so sánh khóa
- Duyệt toàn bộ unordered_map:
for(auto p : mp)
{
cout << p.first << " " << p.second << endl;
}
- Lưu ý:
- p.first: khóa (Key).
- p.second: giá trị (Value).
- Thứ tự các phần tử khi duyệt không được đảm bảo và có thể khác nhau giữa các lần chạy chương trình.
Ghi nhớ:
- unordered_map không có các phương thức như push_back(), pop_back(), insert(pos,...) giống vector vì dữ liệu được lưu theo khóa (key), không theo vị trí.
- Các phương thức được sử dụng nhiều nhất là [], at(), count(), find(), erase(), clear(), size(), empty(), begin() và end().
- Các phương thức còn lại được giới thiệu để tham khảo và sẽ được sử dụng trong các chương trình hoặc bài toán nâng cao.
* Ví dụ: Lưu điểm của học sinh theo mã số
Cho nhập vào số lượng học sinh n. Với mỗi học sinh nhập vào:
Lưu dữ liệu vào unordered_map và tra cứu điểm của một học sinh theo mã số.
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
unordered_map<int, int> diem;
int n;
cout << "Nhap so hoc sinh: ";
cin >> n;
for(int i = 1; i <= n; i++)
{
int ma, d;
cout << "Nhap ma hoc sinh: ";
cin >> ma;
cout << "Nhap diem: ";
cin >> d;
diem[ma] = d;
}
int tim;
cout << "Nhap ma hoc sinh can tim: ";
cin >> tim;
if(diem.count(tim))
cout << "Diem: " << diem[tim];
else
cout << "Khong tim thay hoc sinh!";
}
Ví dụ
| Input | Output |
|---|---|
|
3 101 8 102 10 103 9 102 |
Diem: 10 |
Trong ví dụ trên:
| Khóa (Key) | Giá trị (Value) |
|---|---|
| 101 | 8 |
| 102 | 10 |
| 103 | 9 |
Khi nhập mã học sinh 102, chương trình sẽ tra cứu và lấy giá trị tương ứng là 10.
Ghi nhớ:
- Mỗi khóa (Key) chỉ lưu một giá trị (Value) tương ứng.
- Có thể truy cập dữ liệu rất nhanh bằng cú pháp mp[key].
- Có thể dùng count() để kiểm tra khóa có tồn tại trước khi truy cập.
- unordered_map rất phù hợp để lưu các dữ liệu có dạng mã → thông tin, chẳng hạn như: mã học sinh → điểm, mã sản phẩm → giá bán, mã nhân viên → lương,...
* Ví dụ: Đếm số lần xuất hiện của mỗi số nguyên
Cho nhập vào số nguyên dương n, tiếp theo là n số nguyên.
Hãy đếm số lần xuất hiện của từng giá trị và in kết quả ra màn hình.
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
unordered_map<int, int> cnt;
for(int i = 0; i < n; i++)
{
int x;
cin >> x;
cnt[x]++;
}
cout << "So lan xuat hien cua tung gia tri:\n";
for(auto p : cnt)
{
cout << p.first << " : " << p.second << '\n';
}
return 0;
}
Ví dụ
| Input | Output (có thể) |
|---|---|
|
10 5 8 5 3 8 8 9 5 3 8 |
3 : 2 5 : 3 8 : 4 9 : 1 |
Lưu ý: Do unordered_map không lưu dữ liệu theo thứ tự nên kết quả có thể được in theo thứ tự khác, nhưng số lần xuất hiện của mỗi giá trị vẫn chính xác.
Ghi nhớ:
- cnt[x]++ là cách sử dụng phổ biến nhất của unordered_map.
- Nếu khóa x chưa tồn tại, cnt[x] sẽ tự động được tạo với giá trị ban đầu bằng 0, sau đó tăng lên thành 1.
- unordered_map rất thích hợp để đếm số lần xuất hiện của các số, ký tự hoặc chuỗi.
unordered_mapCho dữ liệu trong tệp DEMO.INP gồm hai dòng:
Hãy đếm số lần xuất hiện của từng giá trị và ghi kết quả ra tệp DEMO.OUT.
| DEMO.INP | DEMO.OUT (có thể) |
|---|---|
|
10 5 8 5 3 8 8 9 5 3 8 |
3 : 2 5 : 3 8 : 4 9 : 1 |
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen("DEMO.INP", "r", stdin);
freopen("DEMO.OUT", "w", stdout);
int n;
cin >> n;
unordered_map<int, int> cnt;
for(int i = 0; i < n; i++)
{
int x;
cin >> x;
cnt[x]++;
}
for(auto p : cnt)
{
cout << p.first << " : " << p.second << '\n';
}
return 0;
}
Lưu ý:
Do unordered_map không lưu dữ liệu theo thứ tự nên kết quả ghi ra tệp có thể khác thứ tự trong ví dụ, nhưng số lần xuất hiện của từng giá trị luôn chính xác.
Ghi nhớ:
- Dùng freopen() để đọc dữ liệu từ tệp và ghi kết quả ra tệp.
- Có thể kết hợp unordered_map với vòng lặp để đếm số lần xuất hiện của các giá trị.
- Thứ tự các phần tử khi duyệt unordered_map không được đảm bảo.
- Đây là một trong những ứng dụng phổ biến nhất của unordered_map trong lập trình thi đấu.
vector, map và unordered_map
Trong lập trình, vector, map và unordered_map đều là các cấu trúc dữ liệu rất hữu ích. Tuy nhiên, mỗi cấu trúc dữ liệu sẽ phù hợp với từng bài toán khác nhau.
| Đặc điểm | vector | map | unordered_map |
|---|---|---|---|
| Kiểu lưu trữ | Dãy phần tử | Cặp (Key, Value) | Cặp (Key, Value) |
| Truy cập | Theo chỉ số | Theo khóa | Theo khóa |
| Thứ tự lưu trữ | Theo chỉ số | Khóa được sắp xếp tăng dần | Khóa không được sắp xếp theo thứ tự |
| Khi nào nên dùng? | Dữ liệu có chỉ số liên tiếp. | Cần lưu dữ liệu theo khóa và cần sắp xếp khóa. | Cần lưu dữ liệu theo khóa nhưng không cần sắp xếp khóa. |
Ví dụ 1: Dùng vector
Lưu điểm của học sinh theo thứ tự nhập:
vector<int> diem(3);
diem[0] = 8;
diem[1] = 9;
diem[2] = 10;
cout << diem[1];
Kết quả:
9
Ví dụ 2: Dùng map
Lưu điểm theo mã học sinh và muốn các mã học sinh luôn được sắp xếp tăng dần.
map<int, int> diem;
diem[101] = 8;
diem[102] = 9;
diem[103] = 10;
cout << diem[102];
Kết quả:
9
Ví dụ 3: Dùng unordered_map
Lưu điểm theo mã học sinh nhưng không cần sắp xếp các mã học sinh.
unordered_map<int, int> diem;
diem[101] = 8;
diem[102] = 9;
diem[103] = 10;
cout << diem[102];
Kết quả:
9
Một số ứng dụng của unordered_map
unordered_map (sẽ học ở chương sau).Ghi nhớ:
- Dùng vector khi dữ liệu được lưu theo chỉ số (0, 1, 2, ...).
- Dùng map khi cần lưu dữ liệu theo khóa và muốn các khóa luôn được sắp xếp tăng dần. Chẳng hạn bài yêu cầu: In theo thứ tự khóa tăng dần, duyệt dữ liệu theo thứ tự khóa, lấy khóa nhỏ nhất, lớn nhất,...
- Dùng unordered_map khi cần lưu dữ liệu theo khóa nhưng không cần sắp xếp các khóa.
- Hãy lựa chọn cấu trúc dữ liệu phù hợp với yêu cầu của từng bài toán.
Cho một xâu ký tự S chỉ gồm các chữ cái tiếng Anh in thường từ 'a' đến 'z'.
Yêu cầu: Đếm số lần xuất hiện của từng chữ cái trong xâu. Không yêu cầu in theo thứ tự chữ cái.
Dữ liệu vào: Gồm một dòng duy nhất chứa xâu S (1 ≤ |S| ≤ 105).
Dữ liệu ra: Mỗi dòng ghi một chữ cái và số lần xuất hiện của chữ cái đó. Thứ tự các dòng có thể khác nhau.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra (có thể) | Giải thích |
|---|---|---|
| banana |
n 2 a 3 b 1 |
Chữ a xuất hiện 3 lần, b xuất hiện 1 lần và n xuất hiện 2 lần. |
Giới hạn:
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
unordered_map<char, int> cnt;
for(char c : s)
{
cnt[c]++;
}
for(auto p : cnt)
{
cout << p.first << " " << p.second << '\n';
}
return 0;
}
Cho một xâu ký tự S chỉ gồm các chữ cái tiếng Anh in thường từ 'a' đến 'z'.
Yêu cầu: Đếm số lần xuất hiện của từng chữ cái trong xâu và in kết quả theo thứ tự bảng chữ cái ('a' đến 'z').
Dữ liệu vào: Gồm một dòng duy nhất chứa xâu S (1 ≤ |S| ≤ 105).
Dữ liệu ra: Mỗi dòng ghi một chữ cái và số lần xuất hiện của chữ cái đó theo thứ tự bảng chữ cái.
Ví dụ:
| Dữ liệu vào | Dữ liệu ra | Giải thích |
|---|---|---|
| banana | a 3 b 1 n 2 | Kết quả phải được in theo thứ tự bảng chữ cái. |
Giới hạn:
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
map<char, int> cnt;
for(char c : s)
{
cnt[c]++;
}
for(auto p : cnt)
{
cout << p.first << " " << p.second << '\n';
}
return 0;
}