10.5K 783 122

Đã đăng vào thg 8 26, 2022 6:31 SA 13 phút đọc

4.7K

Bài 15: Thư viện STL C++ (phần 3) - Ánh xạ (Map/Dictionary)

I. Giới thiệu chung

Ánh xạ là một cấu trúc dữ liệu có tính ứng dụng rất cao trong lập trình. Về bản chất, cấu trúc dữ liệu này được cài đặt thủ công (dựa trên cây nhị phân tự cân bằng hoặc bảng băm), tuy nhiên việc cài đặt thủ công rất dài dòng và phức tạp, lại dễ xảy ra nhầm lẫn. Vì thế, những ngôn ngữ lập trình hiện đại đã giải quyết việc này bằng cách cài đặt sẵn nó. Trong C++ và Python, chúng lần lượt có tên là map và dictionary.

Vậy cấu trúc dữ liệu này là gì? Trong toán học, "ánh xạ" có nghĩa là một quy tắc cho một phần tử $x$ trong tập hợp $A$ tương ứng với một phần tử $y$ trong tập hợp $B,$ nói cách khác là một phép "mã hóa" $x$ thành $y$ . Vận dụng định nghĩa đó, ánh xạ trong lập trình là một cấu trúc dữ liệu cho phép tạo ra các phần tử ở dạng một cặp khóa - giá trị (key - value), mà giá trị chính là một ánh xạ của khóa do người dùng quy định, từ đó dễ dàng hơn trong việc kiểm soát dữ liệu.

Trong bài viết này, tôi sẽ giới thiệu tới các bạn cách sử dụng ánh xạ trong C++ và một số bài toán ứng dụng của nó.

II. Sử dụng ánh xạ trong C++

Trong C++, ánh xạ được cài đặt sẵn trong STL C++, đó là associative container map. Giống như set, các phần tử trong map có khóa phân biệt, và chúng sẽ được tự động sắp xếp theo khóa (dựa trên phép so sánh mà người dùng quy định).

Trong map, các phần tử được xác định bằng khóa. Tức là giả sử có một cặp phần tử là $1 - 0$ thì toàn bộ phần tử này sẽ được đại diện bằng khóa là $1$ . Kiểu của khóa và giá trị ánh xạ có thể khác nhau.

Mỗi phần tử của map được cài đặt theo kiểu pair, với khóa tương ứng với trường first và giá trị ánh xạ tương ứng với trường second.

1. Khai báo

Ta khai báo thư viện <map> và không gian tên std, sau đó tạo một map theo cú pháp:

#include <map>

using namespace std;

map < {Kiểu_khóa}, {Kiểu_ánh_xạ} > {Tên_map};

Ví dụ:

#include <map>

using namespace std;

map < string, int > mymap;

2. Các thao tác với `map` trong C++

Duyệt `map` và truy cập phần tử

Các phần tử trong map chỉ có thể duyệt qua bằng cách sử dụng vòng lặp và biến lặp giống như set:

map < {Kiểu_khóa}, {Kiểu_ánh_xạ} > :: iterator {Tên_biến_lặp};

for ({Biến_lặp} = {Địa_chỉ_đầu}; {Biến_lặp} != {Địa_chỉ_cuối}; ++{Biến_lặp})
{
    {Các_câu_lệnh};
}

Hoặc có thể sử dụng một cách ngắn gọn hơn là dùng biến auto trong C++11. Nhưng cách này chỉ có thể duyệt qua toàn bộ phần tử trên map chứ không thể duyệt một đoạn:

for (auto {Tên_biến_lặp}: {Tên_map})
{
    {Các_câu_lệnh};
}

Giả sử ta có biến lặp là $\text{it},$ thì khi duyệt map, ta có thể truy cập vào các trường của phần tử theo những cách sau:

(*it): Trả về phần tử mà biến lặp đang trỏ đến, kiểu là pair.
(*it).first: Trả về khóa của phần tử mà biến lặp đang trỏ đến.
(*it).second: Trả về giá trị của phần tử mà biến lặp đang trỏ đế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 khóa, ta sử dụng cú pháp:

{Tên_map}[{Khóa}];

Khi đó, nếu như khóa này đã tồn tại trong map thì cú pháp sẽ trả về giá trị của khóa đó, ngược lại thì nó sẽ thêm khóa đó vào map. Độ phức tạp của thao tác là $O\big(\log(n)\big)$ với $n$ là kích thước của map.

Đoạn chương trình dưới đây sẽ minh họa toàn bộ các thao tác trên:

#include <iostream>
#include <map>

using namespace std;

signed main()
{
    map < char, int > mymap;
    map < char, int > :: iterator it;

    // Thêm các phần tử và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 có thể viết:
        for (auto e: mymap)
            cout << e.first << ' ' << e.second << endl;
    */

    return 0;
}

Kết quả chạy sẽ là:

a 1
b 2
c 3

Viết lại hàm so sánh cho `map`

Phép so sánh mặc định của map là less, tức là các phần tử sẽ được sắp xếp tăng dần theo khóa. Các bạn cũng có thể viết lại hàm so sánh theo ý mình như sau:

struct cmp
{
    bool operator() ({Khóa_đại_diện_1}, {Khóa_đại_diện_2})
    {
        {Quan_hệ_giữa_hai_khóa};
    }
};

map < {Kiểu_khóa}, {Kiểu_ánh_xạ}, cmp > {Tên_map};

{Khóa_đại_diện_1}, {Khóa_đại_diện_2} lần lượt đại diện cho các phần tử đứng trước và đứng sau trong map, quan hệ giữa chúng sẽ thể hiện cho thứ tự sắp xếp các phần tử trong map. Ví dụ:

#include <iostream>
#include <map>

using namespace std;

// Quy định phép so sánh của map là khóa giả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 quả chạy chương trình trên sẽ là:

c 3
b 2
a 1

Một số hàm dựng sẵn với `map`

Container map đã xây dựng sẵn một số hàm để thao tác với set, cụ thể tôi trình bày ở bảng dưới đây. Để sử dụng hàm, ta dùng cú pháp: {Tên_map}.{Tên_hàm}. Coi rằng kích thước của một map $m$ là $n$ .

Tên hàm	Tác dụng	Độ phức tạp
`m.insert({key, value})`, `m.insert(make_pair(key, value))`	Thêm phần tử $x$ vào tập hợp, tự động sắp xếp lại	$O(\log n)$
`m.find(x)`	Trả về `iterator` trỏ tới phần tử $x$ trong `map`, nếu không tìm thấy thì trả về `iterator` `end()`	$O(\log n)$
`m.clear()`	Xóa toàn bộ `map`	$O(n)$
`m.erase()`	Xóa một phần tử trong `map`, có thể xóa theo khóa hoặc xóa theo `iterator`	$O\Big(\log\big(\\|s\\|\big)\Big)$
`m.size()`	Trả về kích thước hiện tại của `map`	$O(1)$
`m.empty()`	Trả về `true` nếu `map` rỗng, ngược lại trả về `false`	$O(1)$
`m.lower_bound(key)`	Trả về `iterator` trỏ tới phần tử nhỏ nhất có khóa lớn hơn hoặc bằng khóa $\text{key}$ trong `map` (theo phép so sánh), nếu không tìm thấy thì trả về `iterator` `end()`	$O(\log n)$
`m.upper_bound(key)`	Trả về `iterator` trỏ tới phần tử nhỏ nhất có khóa lớn hơn khóa $key$ trong tập hợp (theo phép so sánh), nếu không tìm thấy thì trả về `iterator` `end()`	$O(\log n)$
`m.count(key)`	Trả về số lần xuất hiện của khóa $\text{key}$ trong tập hợp	$O(\log n)$

3. Các cấu trúc `multimap` và `unordered_map`

Ngoài map, trong STL C++ còn có thêm hai cấu trúc cũng tương tự như map:

multimap: Là một lớp nằm trong thư viện map. Giống như map, này cho phép chứa các phần tử có khóa giống nhau, vì thế nên không thể truy cập phần tử thông qua khóa bằng toán tử []. Các bạn đọc thêm về container này tại <i>đây.</i>
unordered_map: Cần khai báo thư viện <unordered_map> khi sử dụng. Cũng giống như map, nhưng các phần tử khi thêm vào sẽ không có thứ tự, vì thế nên các thao tác gần như sẽ giảm độ phức tạp về $O(1)$ . Tuy nhiên vì thế nên nó sẽ không có các hàm tìm kiếm lower_bound(), upper_bound. Các bạn đọc thêm về container này tại <i>đây.</i>

III. Một số bài toán minh họa

1. Bài toán 1

Đề bà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 \times n,$ 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ó $k$ 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 $m, n, k$ .
Trên $m$ dòng tiếp theo, mỗi dòng chứa $n$ số nguyên là số hiệu của $n$ chú ếch trên từng hàng trong bảng, phân tách nhau bởi dấu cách.

Ràng buộc:

$1≤m, n≤1000$ .
$1≤k≤m \times n$ .
$|a_{i,j} |≤10^9;∀i,j:1≤i≤m,1≤j≤n$ .

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:

Giải thích:

Bạn Sơn Tùng có thể chơi theo cách sau:

Lượt $1$ chạm vào ô có số hiệu $1,$ đạt $7$ điểm.
Lượt $2$ chạm vào ô có số hiệu $4,$ đạt $8$ điểm. $→$ Tổng hai lượt chơi đạt $15$ điểm.

Ý tưởng

Ý tưởng của bài toán này khá dễ, đơn giản là các bạn cần chọn ra $k$ số có số lần xuất hiện nhiều nhất trong ma trận, và cộng tất cả số lần xuất hiện của các số đó lại để thu được kết quả.

Ta sẽ sử dụng một map hoặc dictionary để lưu số lần xuất hiện của các số trong ma trận (bởi vì các số này nhỏ hơn hoặc bằng $10^9$ nên nếu dùng đếm phân phối bằng mảng sẽ không khả thi). Sau đó chỉ cần lưu lại số lần xuất hiện của từng số ra một mảng riêng rồi chọn $k$ số xuất hiện nhiều nhất là được.

Trong bài toán này, do không cần đến tính thứ tự của các khóa nên tôi sẽ sử dụng unordered_map đối với C++ để đẩy nhanh tốc độ chương trình hơn.

Độ phức tạp: $O(m \times n)$ .

Cà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 và đếm cá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 có đủ k giá trị phân biệt thì 
    // số điểm ghi được là m * n.
    if (cnt.size() < k)
    {
        cout << m * n;
        return;
    }

    // Lưu số lần xuất hiện của các giá trị phân biệt trong ma trận
    // vào một vector riêng.
    vector < int > frequency;
    for (auto e: cnt)
        frequency.push_back(e.second);
    
    // Sắp xếp lại tần suất của các giá trị theo chiều giảm dần.
    sort(frequency.begin(), frequency.end(), greater < int >());

    // Tính tổng số điểm dà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. Bài toán 2

Đề bà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à $ax + by + c = 0$ , trong đó $a, b$ và $c$ là các hệ số và $x$ và $y$ 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 $n$ đường thẳng theo dạng tổng quát, biết trước các hệ số $a, b, c$ của phương trình đường thẳng $(ax + by + c = 0)$ . 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 $n$ chỉ số lượng các đường thẳng.
Trên $n$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a,b,c$ là hệ số của ,một đường thẳng.

Ràng buộc:

$1 \le n \le 10^5$ .
$|a|, |b|, |c| \le 10^9$ .
Đối với một đường thẳng, ba hệ số $a, b, c$ và $a, b$ không đồng thời bằng $0$ .

Output:

In ra kích thước của tập hợp gồm nhiều đường thẳng song song nhất trong các đường thẳng đã cho.

Sample Input:

Sample Output:

Giải thích:

Hai đường thẳng $3x + 4y + 5 = 0$ và $30x + 40y + 0 = 0$ tạo thành một tập con chứa nhiều đường thẳng song song nhất.

Ý tưởng

Ta có phương trình đường thẳng có dạng $ax + by + c = 0\; (1)$ với $a, b$ và $c$ là các hệ số và $x$ và $y$ là các biến.

Phương trình của $(1)$ theo hệ số góc là $y = mx + C \;(2)$ với $m$ là hệ số góc của đường thẳng $(1)$ .

Từ $(1)$ và $(2),$ ta có:

$\begin{cases} m = -\frac{a}{b} \\ C = -\frac{c}{b} \end{cases}$

Bây giờ, để hai đường thẳng song song thì chúng phải có cùng hệ số góc $m$ và $C$ khác nhau. Nếu $C$ 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 các đường thẳng theo từng hệ số góc, ta sử dụng một map với key là hệ số góc, còn value là một set chứa hệ số tự do $C$ của các đường thẳng có chung hệ số góc tương ứng đối với C++. Còn đối với Python, các bạn sẽ sử dụng $1$ dictionary để lưu các đường thẳng phân biệt (tránh trường hợp các đường thẳng bị trùng nhau tính hai lần), còn một dictionary để lưu số lần xuất hiện của các đường thẳng có hệ số góc giống nhau.

Tuy nhiên, các bạn cần lưu ý trường hợp đường thẳng có $b = 0$ . Khi đó, đường thẳng này sẽ song song với trục tung, và dĩ nhiên mọi đường thẳng có $b = 0$ đều sẽ song song với nhau. Ta sẽ coi $m = \infty$ và $C = -\frac{c}{a}$ để phân biệt các đường thẳng đó với nhau, chứ không sử dụng hệ số góc để tránh chia cho $0$ .

Độ phức tạp tổng quát của giải thuật là $O\big(n.\log(n)\big)$ .

Cài đặt

#include <bits/stdc++.h>

using namespace std;

// Cấu trúc lưu ba hệ số của một đường thẳng dạng tổng quá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ử dụng map với key là các hệ số góc, value là set lưu tập hợp các đường thẳng
    // phân biệt có chung hệ số góc (tức là song song).
    map < double, set < double > > parallel_lines;
    for (int i = 1; i <= n; ++i)
        // Nếu b = 0 thì coi như hệ số góc là vô cùng và hệ số tự do là -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 thì hệ số góc và hệ số tự do tính theo công thức bì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);
        }

    // Tìm tập hợp có số đường thẳng song song lớn nhất.
    // Phải ép kiểu int cho hàm size() của map value, do tí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. Tài liệu tham khảo

I. Giới thiệu chung

II. Sử dụng ánh xạ trong C++

1. Khai báo

2. Các thao tác với map trong C++

Duyệt map và truy cập phần tử

Viết lại hàm so sánh cho map

Một số hàm dựng sẵn với map

3. Các cấu trúc multimap và unordered_map

III. Một số bài toán minh họa

1. Bài toán 1

Đề bài

Ý tưởng

Cài đặt

2. Bài toán 2

Đề bài

Ý tưởng

Cài đặt

IV. Tài liệu tham khảo

Mục lục

2. Các thao tác với `map` trong C++

Duyệt `map` và truy cập phần tử

Viết lại hàm so sánh cho `map`

Một số hàm dựng sẵn với `map`

3. Các cấu trúc `multimap` và `unordered_map`