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> // Cần để tách chuỗi thành từ

int main() {
    string text = "chuoi nay co chuoi va co chuoi";
    map<string, int> word_counts; // key: string (tu), value: int (so dem)

    stringstream ss(text); // Sử dụng stringstream để xử lý chuỗi như một luồng
    string word;

    while (ss >> word) { // Đọc từng từ
        // Nếu 'word' chưa có trong map, nó sẽ được thêm vào với giá trị mặc định là 0
        // Sau đó, giá trị này sẽ được tăng lên 1
        word_counts[word]++; 
    }

    cout << "Tan suat xuat hien cua cac tu:" << endl;
    // Duyệt qua map. Các phần tử sẽ được sắp xếp theo key (theo thứ tự bảng chữ cái)
    for (const auto& pair : word_counts) {
        cout << "'" << pair.first << "': " << pair.second << " lan" << endl;
    }

    return 0;
}

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() {
    map<string, string> country_names; // key: ma, value: ten day du

    // Thêm các cặp ma-ten
    country_names["VN"] = "Viet Nam";
    country_names["US"] = "United States";
    country_names["CA"] = "Canada";
    country_names["JP"] = "Japan";

    string search_code = "US";
    // Cách 1: Sử dụng [] - cẩn thận vì có thể thêm phần tử nếu khóa không tồn tại
    cout << "Ten day du cua " << search_code << " (dung []): ";
    if (country_names.count(search_code)) { // Kiểm tra sự tồn tại trước khi truy cập nếu không muốn thêm mới
         cout << country_names[search_code] << endl;
    } else {
         cout << "Khong tim thay!" << endl;
    }


    search_code = "DE"; // Mã không tồn tại
    // Cách 2: Sử dụng find() - an toàn hơn khi chỉ muốn tra cứu mà không thêm
    cout << "Ten day du cua " << search_code << " (dung find()): ";
    auto it = country_names.find(search_code);
    if (it != country_names.end()) {
        // it->first la key, it->second la value
        cout << it->second << endl;
    } else {
        cout << "Khong tim thay!" << endl;
    }

    return 0;
}

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() {
    vector<int> numbers = {10, 20, 10, 30, 20, 10, 40, 30};
    map<int, int> first_occurrence_index; // key: so, value: chi so dau tien

    // Duyệt qua vector
    for (int i = 0; i < numbers.size(); ++i) {
        int num = numbers[i];

        // Kiểm tra xem số này đã có trong map chưa
        if (first_occurrence_index.find(num) == first_occurrence_index.end()) {
            // Nếu chưa có, đây là lần đầu tiên ta thấy nó.
            // Thêm nó vào map với key là số và value là chỉ số hiện tại i.
            first_occurrence_index[num] = i;
        }
        // Nếu đã có rồi, ta không làm gì cả vì ta chỉ muốn lưu chỉ số ĐẦU TIÊN.
    }

    cout << "Chi so xuat hien dau tien cua cac so duy nhat:" << endl;
    // Duyệt qua map. Các số sẽ được in ra theo thứ tự tăng dần.
    for (const auto& pair : first_occurrence_index) {
        cout << "So " << pair.first << " xuat hien lan dau o chi so: " << pair.second << endl;
    }

    return 0;
}

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>

struct Person {
    string name;
    string city;
};

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

    map<string, vector<string>> people_by_city; // key: thanh pho, value: vector ten nguoi

    // Duyệt qua danh sách người
    for (const auto& person : people) {
        // people_by_city[person.city]: truy cập (hoặc thêm nếu chưa có) vector ứng với thành phố này.
        // push_back(person.name): thêm tên người hiện tại vào vector đó.
        people_by_city[person.city].push_back(person.name);
    }

    cout << "Danh sach nguoi theo thanh pho:" << endl;
    // Duyệt qua map. Các thành phố sẽ được in ra theo thứ tự bảng chữ cái.
    for (const auto& pair : people_by_city) {
        cout << "Thanh pho " << pair.first << ":" << endl;
        // Duyệt qua vector chứa tên người trong thành phố này
        for (const auto& name : pair.second) {
            cout << "  - " << name << endl;
        }
    }

    return 0;
}

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.