Bài 19.3: Các bài toán sử dụng Map trong C++

Chào mừng các bạn trở lại với chuỗi bài viết về C++! Hôm nay, chúng ta sẽ cùng đi sâu vào một cấu trúc dữ liệu cực kỳ mạnh mẽ và linh hoạt trong Thư viện Chuẩn (STL) của C++: map. Nếu bạn đã từng đối mặt với các bài toán cần lưu trữ và truy xuất dữ liệu dựa trên một khóa duy nhất, thì map chính là người bạn đồng hành tuyệt vời của bạn.

map là một kiểu container liên kết (associative container) lưu trữ các cặp khóa-giá trị (key-value pair). Điều đặc biệt và quan trọng nhất của map là nó luôn giữ cho các phần tử được sắp xếp theo thứ tự của khóa. Việc này giúp cho việc tìm kiếm, truy cập và duyệt qua các phần tử trở nên rất hiệu quả (với độ phức tạp thời gian là O(log n), trong đó n là số lượng phần tử).

Vậy, khi nào chúng ta nên nghĩ đến việc sử dụng map? Hãy cùng khám phá qua một số bài toán thực tế mà map có thể giúp chúng ta giải quyết một cách thanh lịch và hiệu quả nhé!

1. Đếm Tần Suất Xuất Hiện (Frequency Counting)

Đây là một trong những ứng dụng phổ biến nhất của map. Khi bạn cần đếm số lần xuất hiện của các phần tử duy nhất trong một tập dữ liệu (ví dụ: đếm số từ trong văn bản, đếm số lần một số xuất hiện trong mảng), map là lựa chọn hàng đầu.

Bài toán: Cho một danh sách các từ, đếm tần suất xuất hiện của mỗi từ.
Tại sao dùng Map: Mỗi từ duy nhất sẽ là khóa, và số lần nó xuất hiện sẽ là giá trị. map tự động xử lý việc chỉ lưu trữ các từ duy nhất và cho phép chúng ta dễ dàng tăng giá trị (số đếm) liên kết với mỗi từ.

Hãy xem ví dụ sau:

#include <iostream>
#include <string>
#include <map>
#include <sstream>

int main() {
    using namespace std;
    string vanBan = "chuoi nay co chuoi va co chuoi";
    map<string, int> demTu;

    stringstream ss(vanBan);
    string tu;

    while (ss >> tu) {
        demTu[tu]++;
    }

    cout << "Tan suat xuat hien cua cac tu:" << endl;
    for (const auto& p : demTu) {
        cout << "'" << p.first << "': " << p.second << " lan" << endl;
    }

    return 0;
}

Tan suat xuat hien cua cac tu:
'chuoi': 3 lan
'co': 2 lan
'nay': 1 lan
'va': 1 lan

Giải thích:
- Chúng ta khai báo map<string, int> word_counts;. Kiểu khóa là string (từ), kiểu giá trị là int (số lần đếm).
- stringstream giúp chúng ta dễ dàng tách chuỗi text thành từng từ.
- Vòng lặp while (ss >> word) đọc từng từ một.
- Dòng word_counts[word]++; là điểm mấu chốt:
  - Nếu word chưa tồn tại làm khóa trong word_counts, map sẽ tự động thêm word vào làm khóa và khởi tạo giá trị liên kết với nó bằng giá trị mặc định cho kiểu int, tức là 0.
  - Sau đó, toán tử ++ sẽ tăng giá trị đó lên 1.
  - Nếu word đã tồn tại, map sẽ truy cập đến giá trị hiện có liên kết với khóa word và tăng nó lên 1.
- Vòng lặp cuối cùng duyệt qua map. pair.first là khóa (từ), pair.second là giá trị (số đếm). Bạn sẽ thấy các từ được in ra theo thứ tự bảng chữ cái vì map duy trì thứ tự của khóa.

2. Bảng Tra Cứu (Lookup Tables)

Khi bạn cần ánh xạ một tập hợp các định danh (ID, code, tên viết tắt) với các thông tin chi tiết hơn (mô tả, tên đầy đủ), map hoạt động như một bảng tra cứu hiệu quả.

Bài toán: Lưu trữ và tra cứu tên đầy đủ của các quốc gia dựa trên mã quốc gia (ví dụ: "VN" -> "Viet Nam").
Tại sao dùng Map: Mã quốc gia là khóa duy nhất, tên đầy đủ là giá trị. Việc tra cứu theo khóa rất nhanh.

Ví dụ:

#include <iostream>
#include <string>
#include <map>

int main() {
    using namespace std;
    map<string, string> qg;

    qg["VN"] = "Viet Nam";
    qg["US"] = "United States";
    qg["CA"] = "Canada";
    qg["JP"] = "Japan";

    string ma = "US";
    cout << "Ten day du cua " << ma << " (dung []): ";
    if (qg.count(ma)) {
         cout << qg[ma] << endl;
    } else {
         cout << "Khong tim thay!" << endl;
    }

    ma = "DE";
    cout << "Ten day du cua " << ma << " (dung find()): ";
    auto it = qg.find(ma);
    if (it != qg.end()) {
        cout << it->second << endl;
    } else {
        cout << "Khong tim thay!" << endl;
    }

    return 0;
}

Ten day du cua US (dung []): United States
Ten day du cua DE (dung find()): Khong tim thay!

Giải thích:
- Chúng ta tạo map<string, string> country_names; để ánh xạ mã quốc gia (chuỗi) sang tên đầy đủ (chuỗi).
- Các phần tử được thêm vào bằng toán tử [].
- Để tra cứu, chúng ta có hai cách chính:
  - Sử dụng country_names[search_code]: Cách này tiện lợi nhưng cần cẩn thận. Nếu search_code chưa tồn tại trong map, nó sẽ được thêm vào với giá trị mặc định (chuỗi rỗng "" đối với string). Nếu bạn chỉ muốn tra cứu mà không muốn thêm phần tử mới, hãy kiểm tra sự tồn tại trước bằng count() hoặc find().
  - Sử dụng country_names.find(search_code): Phương thức find() trả về một iterator trỏ đến phần tử nếu tìm thấy, hoặc country_names.end() nếu không tìm thấy. Đây là cách an toàn hơn khi bạn chỉ muốn kiểm tra sự tồn tại hoặc truy xuất mà không làm thay đổi map. it->first sẽ truy cập khóa, it->second truy cập giá trị.

3. Duy Trì Tập Hợp Các Phần Tử Duy Nhất Kèm Dữ Liệu Liên Quan

Đôi khi bạn có một danh sách dài các mục, nhưng bạn chỉ quan tâm đến các mục duy nhất và cần lưu trữ một số thông tin bổ sung liên quan đến lần đầu tiên (hoặc lần cuối cùng) bạn thấy mục đó.

Bài toán: Cho một mảng các số, tìm chỉ số (index) đầu tiên mà mỗi số duy nhất xuất hiện.
Tại sao dùng Map: Số trong mảng là khóa (đảm bảo tính duy nhất), chỉ số đầu tiên của nó là giá trị.

Ví dụ:

#include <iostream>
#include <vector>
#include <map>

int main() {
    using namespace std;
    vector<int> a = {10, 20, 10, 30, 20, 10, 40, 30};
    map<int, int> viTriDau;

    for (int i = 0; i < a.size(); ++i) {
        int x = a[i];
        if (viTriDau.find(x) == viTriDau.end()) {
            viTriDau[x] = i;
        }
    }

    cout << "Chi so xuat hien dau tien cua cac so duy nhat:" << endl;
    for (const auto& p : viTriDau) {
        cout << "So " << p.first << " xuat hien lan dau o chi so: " << p.second << endl;
    }

    return 0;
}

Chi so xuat hien dau tien cua cac so duy nhat:
So 10 xuat hien lan dau o chi so: 0
So 20 xuat hien lan dau o chi so: 1
So 30 xuat hien lan dau o chi so: 3
So 40 xuat hien lan dau o chi so: 6

Giải thích:
- map<int, int> first_occurrence_index; lưu trữ số làm khóa (int) và chỉ số làm giá trị (int).
- Chúng ta lặp qua mảng numbers.
- Đối với mỗi số num tại chỉ số i, chúng ta dùng find() để kiểm tra xem num đã tồn tại làm khóa trong map chưa.
- first_occurrence_index.find(num) == first_occurrence_index.end() có nghĩa là số num chưa có trong map.
- Nếu đúng như vậy, chúng ta thêm num vào map với chỉ số hiện tại i bằng cách dùng first_occurrence_index[num] = i;. Lần sau gặp lại số num, điều kiện if sẽ sai và chúng ta bỏ qua, giữ lại chỉ số đầu tiên đã được lưu.
- Kết quả in ra sẽ liệt kê các số duy nhất cùng với chỉ số xuất hiện đầu tiên của chúng, được sắp xếp theo giá trị của số.

4. Nhóm Dữ Liệu Theo Khóa (Grouping Data by Key)

Khi bạn có một tập hợp các đối tượng và muốn nhóm chúng lại dựa trên một thuộc tính chung, map có thể được sử dụng hiệu quả bằng cách lưu trữ một container khác (như vector hoặc list) làm giá trị.

Bài toán: Cho một danh sách người, mỗi người có tên và thành phố, nhóm những người sống cùng một thành phố lại với nhau.
Tại sao dùng Map: Tên thành phố là khóa, danh sách (vector) các tên người sống ở thành phố đó là giá trị.

Ví dụ:

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

struct Nguoi {
    string ten;
    string tp;
};

int main() {
    vector<Nguoi> dsNguoi = {
        {"Alice", "Hanoi"},
        {"Bob", "HCM"},
        {"Charlie", "Hanoi"},
        {"David", "Da Nang"},
        {"Eve", "HCM"},
        {"Frank", "Hanoi"}
    };

    map<string, vector<string>> nhomTheoTp;

    for (const auto& ng : dsNguoi) {
        nhomTheoTp[ng.tp].push_back(ng.ten);
    }

    cout << "Danh sach nguoi theo thanh pho:" << endl;
    for (const auto& p : nhomTheoTp) {
        cout << "Thanh pho " << p.first << ":" << endl;
        for (const auto& tenNguoi : p.second) {
            cout << "  - " << tenNguoi << endl;
        }
    }

    return 0;
}

Danh sach nguoi theo thanh pho:
Thanh pho Da Nang:
  - David
Thanh pho HCM:
  - Bob
  - Eve
Thanh pho Hanoi:
  - Alice
  - Charlie
  - Frank

Giải thích:
- map<string, vector<string>> people_by_city; là map mà khóa là string (tên thành phố) và giá trị là vector<string> (một vector chứa tên của những người sống ở thành phố đó).
- Đối với mỗi person trong danh sách, people_by_city[person.city] sẽ truy cập vector liên kết với thành phố của người đó. Nếu thành phố chưa tồn tại trong map, map sẽ tự động thêm khóa mới là person.city và khởi tạo một vector<string> rỗng liên kết với khóa đó.
- Sau đó, .push_back(person.name); sẽ thêm tên của người đó vào vector.
- Kết quả in ra sẽ nhóm các tên người dưới tên thành phố tương ứng, và các thành phố sẽ được sắp xếp theo thứ tự bảng chữ cái.

Khi Nào Nên Chọn `map`? (So với `unordered_map`)

map không phải là lựa chọn duy nhất cho các bài toán ánh xạ khóa-giá trị. C++ còn cung cấp unordered_map, hoạt động dựa trên bảng băm (hash table).

map:
- Ưu điểm: Duy trì thứ tự của các khóa (luôn được sắp xếp), đảm bảo hiệu suất O(log n) cho hầu hết các thao tác (chèn, xóa, tìm kiếm).
- Nhược điểm: Thường chậm hơn unordered_map trên trung bình do overhead của cây nhị phân cân bằng.
- Nên dùng khi:
  - Bạn cần các phần tử được sắp xếp theo khóa.
  - Bạn cần hiệu suất đảm bảo logarit trong trường hợp xấu nhất.
  - Khóa của bạn không có hàm băm tốt hoặc không thể băm được.
unordered_map:
- Ưu điểm: Hiệu suất trung bình O(1) cho chèn, xóa, tìm kiếm (cực nhanh!).
- Nhược điểm: Không duy trì thứ tự của các phần tử. Hiệu suất trong trường hợp xấu nhất có thể là O(n) (khi có đụng độ băm lớn).
- Nên dùng khi:
  - Bạn không cần các phần tử được sắp xếp theo khóa.
  - Bạn muốn hiệu suất trung bình nhanh nhất có thể.
  - Khóa của bạn có thể băm được một cách hiệu quả.

Trong các ví dụ trên, nếu bạn không cần kết quả được sắp xếp theo khóa, bạn hoàn toàn có thể thay thế map bằng unordered_map để có thể đạt được hiệu suất tốt hơn trên hầu hết các trường hợp. Tuy nhiên, map mang lại sự đảm bảo về thứ tự và hiệu suất logarit ổn định.

Comments

There are no comments at the moment.