+8

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ử xx trong tập hợp AA tương ứng với một phần tử yy trong tập hợp B,B, nói cách khác là một phép "mã hóa" xx thành yy. 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à 101 - 0 thì toàn bộ phần tử này sẽ được đại diện bằng khóa là 11. 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à it,\text{it}, 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à O(log(n))O\big(\log(n)\big) với nn 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 mm là nn.

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ử xx vào tập hợp, tự động sắp xếp lại O(logn)O(\log n)
m.find(x) Trả về iterator trỏ tới phần tử xx trong map, nếu không tìm thấy thì trả về iterator end() O(logn)O(\log n)
m.clear() Xóa toàn bộ map O(n)O(n)
m.erase() Xóa một phần tử trong map, có thể xóa theo khóa hoặc xóa theo iterator O(log(s))O\Big(\log\big(\|s\|\big)\Big)
m.size() Trả về kích thước hiện tại của map O(1)O(1)
m.empty() Trả về true nếu map rỗng, ngược lại trả về false O(1)O(1)
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 key\text{key} trong map (theo phép so sánh), nếu không tìm thấy thì trả về iterator end() O(logn)O(\log n)
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 keykey trong tập hợp (theo phép so sánh), nếu không tìm thấy thì trả về iterator end() O(logn)O(\log n)
m.count(key) Trả về số lần xuất hiện của khóa key\text{key} trong tập hợp O(logn)O(\log n)

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ện map. 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ề O(1)O(1). Tuy nhiên vì thế nên nó sẽ không có các hàm tìm kiếm lower_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×n,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ó kk 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,km, n, k.
  • Trên mm dòng tiếp theo, mỗi dòng chứa nn số nguyên là số hiệu của nn 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:

  • 1m,n10001≤m, n≤1000.
  • 1km×n1≤k≤m \times n.
  • ai,j109;i,j:1im,1jn|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:

15

Giải thích:

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

  • Lượt 11 chạm vào ô có số hiệu 1,1, đạt 77 điểm.
  • Lượt 22 chạm vào ô có số hiệu 4,4, đạt 88 điểm. Tổng hai lượt chơi đạt 1515 đ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 kk 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 10910^9 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 kk 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: O(m×n)O(m \times n).

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à ax+by+c=0ax + by + c = 0, trong đó a,ba, bcc là các hệ số và xxyy 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 nn đường thẳng theo dạng tổng quát, biết trước các hệ số a,b,ca, b, c của phương trình đường thẳng (ax+by+c=0)(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 nn chỉ số lượng các đường thẳng.
  • Trên nn dòng tiếp theo, mỗi dòng chứa ba số nguyên a,b,ca,b,c là hệ số của ,một đường thẳng.

Ràng buộc:

  • 1n1051 \le n \le 10^5.
  • a,b,c109|a|, |b|, |c| \le 10^9.
  • Đối với một đường thẳng, ba hệ số a,b,ca, b, ca,ba, b không đồng thời bằng 00.

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 3x+4y+5=03x + 4y + 5 = 030x+40y+0=030x + 40y + 0 = 0 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 ax+by+c=0  (1)ax + by + c = 0\; (1) với a,ba, bcc là các hệ số và xxyy là các biến.

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

Từ (1)(1)(2),(2), ta có:

{m=abC=cb\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 mmCC khác nhau. Nếu CC 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 CC 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 11 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ó b=0b = 0. Khi đó, đường thẳng này sẽ song song với trục tung, và dĩ nhiên mọi đường thẳng có b=0b = 0 đều sẽ song song với nhau. Ta sẽ coi m=m = \inftyC=caC = -\frac{c}{a} để 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 00.

Độ phức tạp tổng quát của giải thuật là O(n.log(n))O\big(n.\log(n)\big).

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


©️ Tác giả: Vũ Quế Lâm từ Viblo


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí