Bài 15: Thư viện STL C++ (phần 3) - Ánh xạ (Map/Dictionary)
I. Giới thiệu chung
Ánh xạ là một cấu trúc dữ liệu có tính ứng dụng rất cao trong lập trình. Về bản chất, cấu trúc dữ liệu này được cài đặt thủ công (dựa trên cây nhị phân tự cân bằng hoặc bảng băm), tuy nhiên việc cài đặt thủ công rất dài dòng và phức tạp, lại dễ xảy ra nhầm lẫn. Vì thế, những ngôn ngữ lập trình hiện đại đã giải quyết việc này bằng cách cài đặt sẵn nó. Trong C++ và Python, chúng lần lượt có tên là map
và dictionary
.
Vậy cấu trúc dữ liệu này là gì? Trong toán học, "ánh xạ" có nghĩa là một quy tắc cho một phần tử trong tập hợp tương ứng với một phần tử trong tập hợp nói cách khác là một phép "mã hóa" thành . Vận dụng định nghĩa đó, ánh xạ trong lập trình là một cấu trúc dữ liệu cho phép tạo ra các phần tử ở dạng một cặp khóa - giá trị (key - value), mà giá trị chính là một ánh xạ của khóa do người dùng quy định, từ đó dễ dàng hơn trong việc kiểm soát dữ liệu.
Trong bài viết này, tôi sẽ giới thiệu tới các bạn cách sử dụng ánh xạ trong C++ và một số bài toán ứng dụng của nó.
II. Sử dụng ánh xạ trong C++
Trong C++, ánh xạ được cài đặt sẵn trong STL C++, đó là associative container map
. Giống như set
, các phần tử trong map
có khóa phân biệt, và chúng sẽ được tự động sắp xếp theo khóa (dựa trên phép so sánh mà người dùng quy định).
Trong map
, các phần tử được xác định bằng khóa. Tức là giả sử có một cặp phần tử là thì toàn bộ phần tử này sẽ được đại diện bằng khóa là . Kiểu của khóa và giá trị ánh xạ có thể khác nhau.
Mỗi phần tử của map
được cài đặt theo kiểu pair
, với khóa tương ứng với trường first
và giá trị ánh xạ tương ứng với trường second
.
1. Khai báo
Ta khai báo thư viện <map>
và không gian tên std
, sau đó tạo một map
theo cú pháp:
#include <map>
using namespace std;
map < {Kiểu_khóa}, {Kiểu_ánh_xạ} > {Tên_map};
Ví dụ:
#include <map>
using namespace std;
map < string, int > mymap;
2. Các thao tác với map
trong C++
Duyệt map
và truy cập phần tử
Các phần tử trong map
chỉ có thể duyệt qua bằng cách sử dụng vòng lặp và biến lặp giống như set
:
map < {Kiểu_khóa}, {Kiểu_ánh_xạ} > :: iterator {Tên_biến_lặp};
for ({Biến_lặp} = {Địa_chỉ_đầu}; {Biến_lặp} != {Địa_chỉ_cuối}; ++{Biến_lặp})
{
{Các_câu_lệnh};
}
Hoặc có thể sử dụng một cách ngắn gọn hơn là dùng biến auto
trong C++11. Nhưng cách này chỉ có thể duyệt qua toàn bộ phần tử trên map
chứ không thể duyệt một đoạn:
for (auto {Tên_biến_lặp}: {Tên_map})
{
{Các_câu_lệnh};
}
Giả sử ta có biến lặp là thì khi duyệt map
, ta có thể truy cập vào các trường của phần tử theo những cách sau:
(*it)
: Trả về phần tử mà biến lặp đang trỏ đến, kiểu làpair
.(*it).first
: Trả về khóa của phần tử mà biến lặp đang trỏ đến.(*it).second
: Trả về giá trị của phần tử mà biến lặp đang trỏ đến.it -> first
: Giống như(*it).first
.it -> second
: Giống như(*it).second
.
Để truy cập tới một phần tử thông qua khóa, ta sử dụng cú pháp:
{Tên_map}[{Khóa}];
Khi đó, nếu như khóa này đã tồn tại trong map
thì cú pháp sẽ trả về giá trị của khóa đó, ngược lại thì nó sẽ thêm khóa đó vào map
. Độ phức tạp của thao tác là với là kích thước của map
.
Đoạn chương trình dưới đây sẽ minh họa toàn bộ các thao tác trên:
#include <iostream>
#include <map>
using namespace std;
signed main()
{
map < char, int > mymap;
map < char, int > :: iterator it;
// Thêm các phần tử vào map.
mymap['a'] = 1;
mymap['b'] = 2;
mymap['c'] = 3;
for (it = mymap.begin(); it != mymap.end(); ++it)
cout << (*it).first << ' ' << (*it).second << endl;
// cout << it -> first << ' ' << it -> second << endl;
/* Hoặc có thể viết:
for (auto e: mymap)
cout << e.first << ' ' << e.second << endl;
*/
return 0;
}
Kết quả chạy sẽ là:
a 1
b 2
c 3
Viết lại hàm so sánh cho map
Phép so sánh mặc định của map
là less
, tức là các phần tử sẽ được sắp xếp tăng dần theo khóa. Các bạn cũng có thể viết lại hàm so sánh theo ý mình như sau:
struct cmp
{
bool operator() ({Khóa_đại_diện_1}, {Khóa_đại_diện_2})
{
{Quan_hệ_giữa_hai_khóa};
}
};
map < {Kiểu_khóa}, {Kiểu_ánh_xạ}, cmp > {Tên_map};
{Khóa_đại_diện_1}, {Khóa_đại_diện_2} lần lượt đại diện cho các phần tử đứng trước và đứng sau trong map
, quan hệ giữa chúng sẽ thể hiện cho thứ tự sắp xếp các phần tử trong map
. Ví dụ:
#include <iostream>
#include <map>
using namespace std;
// Quy định phép so sánh của map là khóa giảm dần.
struct cmp
{
bool operator() (char a, char b)
{
return a > b;
}
};
signed main()
{
map < char, int, cmp > mymap;
mymap.insert({'a', 1});
mymap.insert({'b', 2});
mymap.insert({'c', 3});
for (auto e: mymap)
cout << e.first << ' ' << e.second << endl;
return 0;
}
Kết quả chạy chương trình trên sẽ là:
c 3
b 2
a 1
Một số hàm dựng sẵn với map
Container map
đã xây dựng sẵn một số hàm để thao tác với set
, cụ thể tôi trình bày ở bảng dưới đây. Để sử dụng hàm, ta dùng cú pháp: {Tên_map}.{Tên_hàm}
. Coi rằng kích thước của một map
là .
Tên hàm | Tác dụng | Độ phức tạp |
---|---|---|
m.insert({key, value}) , m.insert(make_pair(key, value)) |
Thêm phần tử vào tập hợp, tự động sắp xếp lại | |
m.find(x) |
Trả về iterator trỏ tới phần tử trong map , nếu không tìm thấy thì trả về iterator end() |
|
m.clear() |
Xóa toàn bộ map |
|
m.erase() |
Xóa một phần tử trong map , có thể xóa theo khóa hoặc xóa theo iterator |
|
m.size() |
Trả về kích thước hiện tại của map |
|
m.empty() |
Trả về true nếu map rỗng, ngược lại trả về false |
|
m.lower_bound(key) |
Trả về iterator trỏ tới phần tử nhỏ nhất có khóa lớn hơn hoặc bằng khóa trong map (theo phép so sánh), nếu không tìm thấy thì trả về iterator end() |
|
m.upper_bound(key) |
Trả về iterator trỏ tới phần tử nhỏ nhất có khóa lớn hơn khóa trong tập hợp (theo phép so sánh), nếu không tìm thấy thì trả về iterator end() |
|
m.count(key) |
Trả về số lần xuất hiện của khóa trong tập hợp |
3. Các cấu trúc multimap
và unordered_map
Ngoài map
, trong STL C++ còn có thêm hai cấu trúc cũng tương tự như map
:
multimap
: Là một lớp nằm trong thư việnmap
. Giống nhưmap
, này cho phép chứa các phần tử có khóa giống nhau, vì thế nên không thể truy cập phần tử thông qua khóa bằng toán tử[]
. Các bạn đọc thêm về container này tại <i>đây.</i>unordered_map
: Cần khai báo thư viện<unordered_map>
khi sử dụng. Cũng giống nhưmap
, nhưng các phần tử khi thêm vào sẽ không có thứ tự, vì thế nên các thao tác gần như sẽ giảm độ phức tạp về . Tuy nhiên vì thế nên nó sẽ không có các hàm tìm kiếmlower_bound()
,upper_bound
. Các bạn đọc thêm về container này tại <i>đây.</i>
III. Một số bài toán minh họa
1. Bài toán 1
Đề bài
Trên xe ô tô đi tham quan, bạn Sơn Tùng được chơi trò chơi đập ếch trên máy tính bảng của cô bạn ngồi cùng xe. Màn hình trò chơi hiển thị một lưới ô vuông kích thước mỗi ô trên đó có in hình một chú ếch và một số nguyên là số hiệu của nó. Ở mỗi lượt chơi, khi người chơi dùng tay chạm vào bất kỳ ô nào đó trong bảng thì:
- Tất cả các chú ếch trong bảng có cùng số hiệu với chú ếch vừa chạm vào đều biến mất khỏi bảng.
- Người chơi dành được thêm số điểm bằng với số lượng chú ếch biến mất.
Yêu cầu: Sơn Tùng có lượt chơi, xác định số điểm lớn nhất cậu có thể đạt được?
Input:
- Dòng đầu tiên ghi ba số nguyên dương .
- Trên dòng tiếp theo, mỗi dòng chứa số nguyên là số hiệu của chú ếch trên từng hàng trong bảng, phân tách nhau bởi dấu cách.
Ràng buộc:
- .
- .
- .
Output:
- Số nguyên duy nhất là tổng điểm tối đa Sơn Tùng giành được.
Sample Input:
4 6 2
1 4 3 3 2 4
2 4 2 1 4 1
2 3 4 4 1 1
1 1 2 3 4 4
Sample Output:
15
Giải thích:
Bạn Sơn Tùng có thể chơi theo cách sau:
- Lượt chạm vào ô có số hiệu đạt điểm.
- Lượt chạm vào ô có số hiệu đạt điểm. Tổng hai lượt chơi đạt điểm.
Ý tưởng
Ý tưởng của bài toán này khá dễ, đơn giản là các bạn cần chọn ra số có số lần xuất hiện nhiều nhất trong ma trận, và cộng tất cả số lần xuất hiện của các số đó lại để thu được kết quả.
Ta sẽ sử dụng một map
hoặc dictionary
để lưu số lần xuất hiện của các số trong ma trận (bởi vì các số này nhỏ hơn hoặc bằng nên nếu dùng đếm phân phối bằng mảng sẽ không khả thi). Sau đó chỉ cần lưu lại số lần xuất hiện của từng số ra một mảng riêng rồi chọn số xuất hiện nhiều nhất là được.
Trong bài toán này, do không cần đến tính thứ tự của các khóa nên tôi sẽ sử dụng unordered_map
đối với C++ để đẩy nhanh tốc độ chương trình hơn.
Độ phức tạp: .
Cài đặt
#include <bits/stdc++.h>
using namespace std;
void enter(int& m, int& n, int& k, map < int, int >& cnt)
{
cin >> m >> n >> k;
// Nhập ma trận và đếm các số bằng unordered_map.
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
{
int x;
cin >> x;
if (cnt.find(x) != cnt.end())
cnt[x]++;
else
cnt[x] = 1;
}
}
void solution(int m, int n, int k, map < int, int >& cnt)
{
// Nếu ma trận không có đủ k giá trị phân biệt thì
// số điểm ghi được là m * n.
if (cnt.size() < k)
{
cout << m * n;
return;
}
// Lưu số lần xuất hiện của các giá trị phân biệt trong ma trận
// vào một vector riêng.
vector < int > frequency;
for (auto e: cnt)
frequency.push_back(e.second);
// Sắp xếp lại tần suất của các giá trị theo chiều giảm dần.
sort(frequency.begin(), frequency.end(), greater < int >());
// Tính tổng số điểm dành được với k lượt chơi.
cout << accumulate(frequency.begin(), frequency.begin() + k, 0);
}
signed main()
{
int m, n, k;
unordered_map < int, int > cnt;
enter(m, n, k, cnt);
solution(m, n, k, cnt);
return 0;
}
2. Bài toán 2
Đề bài
Tèo rất thích học hình học. Cậu ấy đã biết về phương trình tổng quát của đường thẳng là , trong đó và là các hệ số và và là các biến. Hôm nay, Tèo đã học về các đường thẳng song song. Các đường thẳng song song là các đường thẳng không bao giờ gặp nhau tại bất kỳ điểm nào.
Tèo có một tập hợp gồm đường thẳng theo dạng tổng quát, biết trước các hệ số của phương trình đường thẳng . Trong tập hợp này có thể tồn tại nhiều tập hợp con gồm các đường thẳng song song với nhau.
Yêu cầu: Hãy giúp Tèo tìm ra tập con có nhiều đường thẳng song song nhất?
Input:
- Dòng đầu tiên chứa số nguyên chỉ số lượng các đường thẳng.
- Trên dòng tiếp theo, mỗi dòng chứa ba số nguyên là hệ số của ,một đường thẳng.
Ràng buộc:
- .
- .
- Đối với một đường thẳng, ba hệ số và không đồng thời bằng .
Output:
- In ra kích thước của tập hợp gồm nhiều đường thẳng song song nhất trong các đường thẳng đã cho.
Sample Input:
5
1 0 0
1 2 3
3 4 5
30 40 0
30 40 50
Sample Output:
2
Giải thích:
Hai đường thẳng và tạo thành một tập con chứa nhiều đường thẳng song song nhất.
Ý tưởng
Ta có phương trình đường thẳng có dạng với và là các hệ số và và là các biến.
Phương trình của theo hệ số góc là với là hệ số góc của đường thẳng .
Từ và ta có:
Bây giờ, để hai đường thẳng song song thì chúng phải có cùng hệ số góc và khác nhau. Nếu bằng nhau thì chúng là hai đường thẳng trùng nhau. Vì vậy, chúng ta chỉ cần tạo các set
chứa các đường thẳng song song khác nhau theo hệ số góc của chúng và sau đó tìm độ dài của set
lớn nhất.
Để lưu tập hợp các đường thẳng theo từng hệ số góc, ta sử dụng một map
với key
là hệ số góc, còn value
là một set
chứa hệ số tự do của các đường thẳng có chung hệ số góc tương ứng đối với C++. Còn đối với Python, các bạn sẽ sử dụng dictionary
để lưu các đường thẳng phân biệt (tránh trường hợp các đường thẳng bị trùng nhau tính hai lần), còn một dictionary
để lưu số lần xuất hiện của các đường thẳng có hệ số góc giống nhau.
Tuy nhiên, các bạn cần lưu ý trường hợp đường thẳng có . Khi đó, đường thẳng này sẽ song song với trục tung, và dĩ nhiên mọi đường thẳng có đều sẽ song song với nhau. Ta sẽ coi và để phân biệt các đường thẳng đó với nhau, chứ không sử dụng hệ số góc để tránh chia cho .
Độ phức tạp tổng quát của giải thuật là .
Cài đặt
#include <bits/stdc++.h>
using namespace std;
// Cấu trúc lưu ba hệ số của một đường thẳng dạng tổng quát.
struct Line
{
int a, b, c;
};
void enter(int& n, vector < Line >& lines)
{
cin >> n;
lines.resize(n + 1);
for (int i = 1; i <= n; ++i)
cin >> lines[i].a >> lines[i].b >> lines[i].c;
}
void query(int n, vector < Line >& lines)
{
// Sử dụng map với key là các hệ số góc, value là set lưu tập hợp các đường thẳng
// phân biệt có chung hệ số góc (tức là song song).
map < double, set < double > > parallel_lines;
for (int i = 1; i <= n; ++i)
// Nếu b = 0 thì coi như hệ số góc là vô cùng và hệ số tự do là -c/a.
if (lines[i].b == 0)
{
double m = DBL_MIN;
double C = -lines[i].c / (double) lines[i].a;
parallel_lines[m].insert(C);
}
// Nếu b != 0 thì hệ số góc và hệ số tự do tính theo công thức bình thường.
else
{
double m = -lines[i].a / (double) lines[i].b;
double C = -lines[i].c / (double) lines[i].b;
parallel_lines[m].insert(C);
}
// Tìm tập hợp có số đường thẳng song song lớn nhất.
// Phải ép kiểu int cho hàm size() của map value, do tính chất ngôn ngữ C++.
int res = 0;
for (auto e: parallel_lines)
res = max(res, (int) e.second.size());
cout << res << endl;
}
signed main()
{
int ntest;
cin >> ntest;
while (ntest--)
{
int n;
vector < Line > lines;
enter(n, lines);
query(n, lines);
}
return 0;
}
IV. Tài liệu tham khảo
- https://www.cplusplus.com/reference/map/
- https://www.stdio.vn/modern-cpp/stl-map-trong-c-v12lmL
- https://vi.wikipedia.org/wiki/Ánh_xạ
©️ Tác giả: Vũ Quế Lâm từ Viblo
All rights reserved