map là một cấu trúc dữ liệu dùng để lưu các cặp khóa - giá trị (Key - Value). Mỗi khóa chỉ xuất hiện một lần và được dùng để truy cập giá trị tương ứng.
Các khóa trong map luôn được sắp xếp theo thứ tự tăng dần.
Ví dụ:
| Khóa (Key) | Giá trị (Value) |
|---|---|
| 101 | 8 |
| 102 | 9 |
| 103 | 10 |
Trong ví dụ trên:
Muốn lấy điểm của học sinh có mã 102, chỉ cần truy cập bằng khóa 102.
Ghi nhớ:
- map dùng để lưu dữ liệu theo dạng Khóa → Giá trị (Key → Value).
- Mỗi khóa chỉ có một giá trị tương ứng.
- Các khóa trong map luôn được sắp xếp theo thứ tự tăng dần.
- Để sử dụng map, cần khai báo thư viện:
#include <map>
- Có thể khai báo map theo cú pháp:
map<kiểu khóa, kiểu giá trị> tên_biến;
- Trong đó:
int, long long, char, string.int, long long, double, char, string,...Ví dụ:
map<int, int> mp;
Lưu các cặp khóa và giá trị đều có kiểu int.
map<long long, int> cnt;
Khóa có kiểu long long, giá trị có kiểu int.
map<char, int> dem;
Dùng để đếm số lần xuất hiện của từng ký tự.
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 |
|---|---|
map<int, int> |
Lưu các cặp số nguyên. |
map<long long, int> |
Đếm các số nguyên rất lớn. |
map<char, int> |
Đếm số lần xuất hiện của ký tự. |
map<string, int> |
Đếm số lần xuất hiện của từ hoặc chuỗi. |
Ghi nhớ:
- map luôn khai báo theo dạng 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, 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_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.
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 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ố).
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 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.
map* Các hàm/phương thức của 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}); // chỉ thêm nếu key chưa tồn tại
mp.insert(make_pair(key, value));// chỉ thêm nếu key chưa tồn tại
mp.emplace(key, value); // chỉ thêm nếu key chưa tồn tại
- 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 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.swap(mp2); // đổi dữ liệu của hai map
mp.key_comp(); // hàm so sánh khóa
mp.value_comp(); // hàm so sánh giá trị
- Duyệt toàn bộ map:
for(auto p : mp)
{
cout << p.first << " " << p.second << endl;
}
- Lưu ý:
- p.first: khóa (Key).
- p.second: giá trị (Value).
- Khi duyệt map, các khóa luôn được sắp xếp theo thứ tự tăng dần.
Ghi nhớ:
- 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 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);
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, các khóa trong map sẽ luôn được lưu theo thứ tự tăng dầ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.
- Các khóa trong map luôn được sắp xếp theo thứ tự tăng dần.
- 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 theo thứ tự tăng dần của các giá trị.
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
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 |
|---|---|
|
10 5 8 5 3 8 8 9 5 3 8 |
3 : 2 5 : 3 8 : 4 9 : 1 |
Do map tự động sắp xếp các khóa theo thứ tự tăng dần nên kết quả luôn được in theo đúng thứ tự của các giá trị.
Ghi nhớ:
- cnt[x]++ là cách sử dụng rất phổ biến của 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.
- Khi duyệt map, các khóa luôn được sắp xếp theo thứ tự tăng dần.
- map rất thích hợp cho các bài toán vừa cần đếm vừa cần in kết quả theo thứ tự.
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 |
|---|---|
|
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;
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;
}
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 map với vòng lặp để đếm số lần xuất hiện của các giá trị.
- Khi duyệt map, các khóa luôn được sắp xếp theo thứ tự tăng dần.
- map rất phù hợp với các bài toán vừa cần đếm vừa cần in kết quả theo thứ tự.
vector và map
Trong lập trình, vector và 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 |
|---|---|---|
| Kiểu lưu trữ | Dãy phần tử | Cặp (Key, Value) |
| Truy cập | Theo chỉ số | Theo khóa |
| Thứ tự lưu trữ | Theo chỉ số | Khóa được sắp xếp tăng dần |
| Khi nào nên dùng? | Khi dữ liệu có chỉ số liên tiếp. | Khi cần lưu dữ liệu theo khóa và 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
Bài tập luyện tập
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.
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.
| 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. |
Gợi ý mở rộng:
Nếu bài toán không yêu cầu in kết quả theo thứ tự bảng chữ cái thì có cách nào giải nhanh và phù hợp hơn map không?
Nội dung này sẽ được tìm hiểu trong Chủ đề 10 - unordered_map.
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.
- Nếu không cần sắp xếp các khóa, C++ còn cung cấp một cấu trúc dữ liệu khác là unordered_map, sẽ được tìm hiểu ở chủ đề tiếp theo.
- 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.