Bài 20.2: Bài tập thực hành Map cơ bản trong C++

Chào mừng trở lại với chuỗi bài học C++! Hôm nay, chúng ta sẽ đi sâu vào một trong những cấu trúc dữ liệu mạnh mẽlinh hoạt nhất trong Thư viện Template Chuẩn (STL) của C++: map. Nếu bạn đã từng nghĩ về việc lưu trữ dữ liệu dưới dạng các cặp khóa-giá trị (key-value) một cách có tổ chức và dễ dàng truy xuất, thì map chính là người bạn đồng hành mà bạn cần!

Hãy tưởng tượng bạn muốn lưu trữ thông tin cá nhân, nơi tên của mỗi người (ví dụ: "Alice") là khóa duy nhất và số điện thoại của họ (ví dụ: "0912345678") là giá trị tương ứng. Hoặc đơn giản hơn, bạn muốn đếm số lần xuất hiện của mỗi từ trong một đoạn văn. map được thiết kế hoàn hảo cho những tình huống như vậy.

map là gì và tại sao lại cần nó?

Trong C++, map là một container thuộc STL, lưu trữ các phần tử dưới dạng cặp khóa-giá trị, trong đó:

  1. Khóa (Key): Phải là duy nhất trong toàn bộ map. Map sử dụng khóa để sắp xếp và truy xuất các phần tử một cách hiệu quả.
  2. Giá trị (Value): Là dữ liệu liên kết với khóa.

Điểm đặc trưng quan trọng của map là các phần tử được tự động sắp xếp theo thứ tự của khóa (mặc định là tăng dần). Điều này được thực hiện bằng cách sử dụng một cấu trúc dữ liệu cây cân bằng (thường là cây đỏ-đen - red-black tree) bên dưới, mang lại hiệu quả truy xuất, thêm, và xóa với độ phức tạp là O(log n), trong đó 'n' là số lượng phần tử trong map.

So sánh nhanh:

  • Khác với vector hay list, bạn không truy xuất phần tử bằng chỉ số (index) mà bằng khóa.
  • Khác với unordered_map, các phần tử trong map luôn được sắp xếp theo khóa.

Bắt Đầu: Khai Báo một map

Để sử dụng map, bạn cần bao gồm header <map>. Khi khai báo, bạn cần chỉ rõ kiểu dữ liệu cho khóagiá trị.

#include <map>
#include <string> // Để sử dụng string
#include <iostream> // Để in ra console

int main() {
    // Khai báo một map lưu tên (string) và tuổi (int)
    map<string, int> age_map;
    cout << "Da khai bao age_map." << endl;

    // Khai báo một map lưu mã sản phẩm (int) và tên sản phẩm (string)
    map<int, string> product_catalog;
    cout << "Da khai bao product_catalog." << endl;

    // Khai báo một map lưu chữ cái (char) và tần suất xuất hiện (int)
    map<char, int> frequency_counter;
    cout << "Da khai bao frequency_counter." << endl;

    return 0;
}

Giải thích: Cú pháp cơ bản là map<KieuKhoa, KieuGiaTri> ten_map;. Bạn có thể sử dụng bất kỳ kiểu dữ liệu hợp lệ nào của C++ làm khóa và giá trị, miễn là kiểu khóa hỗ trợ phép toán so sánh (<) để map có thể sắp xếp được.

Thêm Phần Tử vào map

Có nhiều cách để thêm các cặp khóa-giá trị vào map:

1. Sử dụng toán tử []

Đây là cách phổ biến và tiện lợi nhất cho hầu hết các trường hợp. Nếu khóa đã tồn tại, toán tử [] sẽ trả về tham chiếu đến giá trị hiện có để bạn có thể thay đổi nó. Nếu khóa chưa tồn tại, nó sẽ tự động thêm một cặp khóa-giá trị mới vào map với khóa được cung cấp và giá trị được khởi tạo mặc định cho kiểu dữ liệu đó (ví dụ: 0 cho int, chuỗi rỗng cho string, false cho bool).

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

int main() {
    map<string, int> age_map;

    // Them moi
    age_map["Alice"] = 30; // Alice chua ton tai, them moi {Alice, 30}
    age_map["Bob"] = 25;   // Bob chua ton tai, them moi {Bob, 25}

    // Cap nhat gia tri cho khoa da ton tai
    age_map["Alice"] = 31; // Alice da ton tai, cap nhat gia tri tu 30 thanh 31

    // Luu y: Truyen khoa chua ton tai vao [] de doc co the gay ra viec them moi ngam!
    // int chieu_cao_david = age_map["David"]; // David chua ton tai, map se them {David, 0}
    // cout << "Tuoi cua David (co the bi them moi): " << age_map["David"] << endl; // David co gia tri mac dinh 0

    return 0;
}

Giải thích: Toán tử [] là cực kỳ tiện lợi, nhưng hãy cẩn thận khi sử dụng nó để đọc một khóa mà bạn không chắc chắn có tồn tại hay không, vì nó có thể vô tình thêm một phần tử mới vào map.

2. Sử dụng hàm insert()

Hàm insert() cung cấp nhiều tùy chọn để thêm phần tử. Cách phổ biến nhất là chèn một pair hoặc sử dụng danh sách khởi tạo (initializer list). Hàm insert trả về một pair chứa một iterator trỏ đến phần tử (đã được chèn hoặc đã tồn tại) và một bool cho biết việc chèn có thực sự xảy ra hay không (true nếu là mới, false nếu khóa đã tồn tại). Quan trọng: insert sẽ không ghi đè lên giá trị nếu khóa đã tồn tại.

#include <map>
#include <string>
#include <iostream>
#include <utility> // De su dung pair

int main() {
    map<string, string> phone_book;

    // Them moi su dung insert voi pair
    pair<string, string> entry1("Alice", "0912345678");
    auto result1 = phone_book.insert(entry1);
    if (result1.second) {
        cout << "Da them Alice vao danh ba." << endl;
    } else {
        cout << "Alice da co trong danh ba." << endl;
    }

    // Them moi su dung insert voi initializer list (C++11 tro len)
    auto result2 = phone_book.insert({"Bob", "0987654321"});
    if (result2.second) {
        cout << "Da them Bob vao danh ba." << endl;
    } else {
        cout << "Bob da co trong danh ba." << endl;
    }

    // Thu them lai Alice (da co trong map)
    auto result3 = phone_book.insert({"Alice", "0900000000"}); // So dien thoai moi
    if (result3.second) {
        cout << "Da them Alice lan 2 (se khong xay ra)." << endl;
    } else {
        // second == false vi Alice da ton tai.
        // first la iterator tro den phan tu {Alice, "0912345678"}
        cout << "Alice da co trong danh ba. Khong cap nhat so dien thoai moi." << endl;
        cout << "So hien tai cua Alice: " << result3.first->second << endl;
    }

    return 0;
}

Giải thích: insert là cách an toàn để thêm phần tử nếu bạn muốn tránh ghi đè hoặc cần kiểm tra xem việc thêm có thành công hay không. Nó đặc biệt hữu ích khi bạn muốn thêm một loạt các cặp mà không muốn vô tình ghi đè lên dữ liệu hiện có.

3. Sử dụng hàm emplace()

emplace() tương tự như insert, nhưng nó hiệu quả hơn một chút đối với các kiểu dữ liệu phức tạp vì nó xây dựng đối tượng giá trị tại chỗ trong map thay vì sao chép hoặc di chuyển một đối tượng đã tồn tại.

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

int main() {
    map<string, double> item_prices;

    // Su dung emplace de them cap khoa-gia tri
    auto result1 = item_prices.emplace("Apple", 1.2);
    if (result1.second) {
        cout << "Da them gia Apple." << endl;
    }

    auto result2 = item_prices.emplace("Banana", 0.75);
    if (result2.second) {
        cout << "Da them gia Banana." << endl;
    }

    // Thu emplace lai Apple
    auto result3 = item_prices.emplace("Apple", 1.5); // Gia moi
     if (!result3.second) {
        cout << "Apple da co trong map. Khong cap nhat gia moi." << endl;
        cout << "Gia hien tai cua Apple: " << result3.first->second << endl;
    }

    return 0;
}

Giải thích: emplace cũng trả về kết quả tương tự như insert. Chọn emplace khi bạn muốn hiệu suất tốt nhất, đặc biệt với các kiểu giá trị lớn hoặc phức tạp.

Truy Cập Phần Tử trong map

Có hai cách chính để truy cập giá trị dựa trên khóa:

1. Sử dụng toán tử []

Như đã đề cập ở phần thêm, toán tử [] trả về tham chiếu đến giá trị. Nếu khóa tồn tại, bạn sẽ nhận được tham chiếu đến giá trị đó. Nếu khóa không tồn tại, nó sẽ thêm khóa đó vào map với giá trị mặc định và trả về tham chiếu đến giá trị mặc định đó.

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

int main() {
    map<string, int> age_map;
    age_map["Alice"] = 30;
    age_map["Bob"] = 25;

    // Truy cap gia tri bang khoa ton tai
    int alice_age = age_map["Alice"];
    cout << "Tuoi cua Alice: " << alice_age << endl; // Output: 30

    // Truy cap gia tri bang khoa KHONG ton tai (CAN THAN!)
    // int charlie_age = age_map["Charlie"]; // Charlie chua ton tai, map se them {Charlie, 0}
    // cout << "Tuoi cua Charlie (sau khi truy cap bang []): " << age_map["Charlie"] << endl; // Output: 0

    // Kich thuoc map truoc va sau khi truy cap khoa khong ton tai
    // cout << "Kich thuoc map truoc: 2" << endl;
    // age_map["Charlie"]; // Them Charlie
    // cout << "Kich thuoc map sau: " << age_map.size() << endl; // Output: 3

    return 0;
}

Giải thích: Toán tử [] là cách tiện lợi để đọc hoặc sửa đổi giá trị cho một khóa mà bạn biết chắc chắn là đã hoặc sẽ có trong map.

2. Sử dụng hàm at()

Hàm at() cũng trả về tham chiếu đến giá trị cho khóa được cung cấp. Tuy nhiên, điểm khác biệt quan trọng là nếu khóa không tồn tại, at() sẽ ném ra một ngoại lệ kiểu out_of_range. Điều này giúp bạn phát hiện lỗi khi cố gắng truy cập một khóa không hợp lệ.

#include <map>
#include <string>
#include <iostream>
#include <stdexcept> // De su dung out_of_range

int main() {
    map<string, int> age_map;
    age_map["Alice"] = 30;
    age_map["Bob"] = 25;

    // Truy cap gia tri bang khoa ton tai (an toan)
    try {
        int bob_age = age_map.at("Bob");
        cout << "Tuoi cua Bob: " << bob_age << endl; // Output: 25
    } catch (const out_of_range& e) {
        cerr << "Loi: " << e.what() << endl; // Khong xay ra trong truong hop nay
    }

    // Truy cap gia tri bang khoa KHONG ton tai (se nem ngoai le)
    try {
        int charlie_age = age_map.at("Charlie"); // Charlie chua ton tai
        cout << "Tuoi cua Charlie: " << charlie_age << endl; // Dong nay se khong chay
    } catch (const out_of_range& e) {
        cerr << "Loi: Khong tim thay Charlie trong map! Thong bao: " << e.what() << endl;
        // Output: Loi: Khong tim thay Charlie trong map! Thong bao: map::at
    }

    // Kich thuoc map sau khi dung at() voi khoa khong ton tai
    cout << "Kich thuoc map sau khi dung at() voi Charlie: " << age_map.size() << endl; // Output: 2 (Charlie khong bi them vao)

    return 0;
}

Giải thích: Sử dụng at() khi bạn cần đảm bảo an toàn và muốn biết liệu khóa có tồn tại hay không. Nó không thêm phần tử mới nếu khóa không tìm thấy.

Duyệt (Iterate) qua map

Bạn có thể duyệt qua tất cả các cặp khóa-giá trị trong map bằng cách sử dụng vòng lặp dựa trên phạm vi (range-based for loop) hoặc iterator. Các phần tử sẽ được duyệt theo thứ tự tăng dần của khóa.

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

int main() {
    map<string, int> age_map;
    age_map["Charlie"] = 35;
    age_map["Alice"] = 30;
    age_map["Bob"] = 25;

    cout << "Duyet map su dung range-based for loop:" << endl;
    // Moi phan tu trong map la mot pair<const KeyType, ValueType>
    for (const auto& pair : age_map) {
        // pair.first la khoa (string)
        // pair.second la gia tri (int)
        cout << pair.first << " is " << pair.second << " years old." << endl;
    }
    // Output thu tu:
    // Alice is 30 years old.
    // Bob is 25 years old.
    // Charlie is 35 years old.

    cout << "\nDuyet map su dung iterator:" << endl;
    for (auto it = age_map.begin(); it != age_map.end(); ++it) {
        // it la mot iterator tro toi pair<const KeyType, ValueType>
        // it->first la khoa
        // it->second la gia tri
        cout << it->first << ": " << it->second << endl;
    }
    // Output thu tu:
    // Alice: 30
    // Bob: 25
    // Charlie: 35

    return 0;
}

Giải thích: Vòng lặp dựa trên phạm vi rất tiện lợi. Mỗi lần lặp, bạn nhận được một pair (const cho khóa, có thể sửa đổi cho giá trị). Iterator cung cấp quyền kiểm soát chi tiết hơn, đặc biệt cần thiết nếu bạn muốn xóa phần tử trong khi đang duyệt.

Kiểm Tra Sự Tồn Tại của Khóa

Trước khi truy cập một khóa bằng [] hoặc at(), bạn thường cần kiểm tra xem khóa đó có tồn tại trong map hay không. Có hai cách chính:

1. Sử dụng hàm count()

Hàm count(key) trả về số lượng phần tử có khóa bằng key. Vì khóa trong map là duy nhất, count() sẽ trả về 1 nếu khóa tồn tại và 0 nếu không.

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

int main() {
    map<string, int> age_map;
    age_map["Alice"] = 30;
    age_map["Bob"] = 25;

    // Kiem tra su ton tai cua Alice
    if (age_map.count("Alice")) {
        cout << "Alice is in the map." << endl;
    } else {
        cout << "Alice is not in the map." << endl; // Khong chay
    }

    // Kiem tra su ton tai cua Charlie
    if (age_map.count("Charlie")) {
        cout << "Charlie is in the map." << endl; // Khong chay
    } else {
        cout << "Charlie is not in the map." << endl;
    }

    return 0;
}

Giải thích: count() là cách đơn giản nhất để kiểm tra sự tồn tại.

2. Sử dụng hàm find()

Hàm find(key) trả về một iterator trỏ đến phần tử có khóa bằng key nếu tìm thấy. Nếu không tìm thấy, nó trả về iterator map.end(). Đây là cách hiệu quả hơn nếu bạn có ý định truy cập hoặc xóa phần tử ngay sau khi tìm thấy nó, vì bạn đã có sẵn iterator.

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

int main() {
    map<string, int> age_map;
    age_map["Alice"] = 30;
    age_map["Bob"] = 25;

    // Tim Alice
    auto it_alice = age_map.find("Alice");
    if (it_alice != age_map.end()) {
        cout << "Found Alice! Age: " << it_alice->second << endl; // Output: Found Alice! Age: 30
    } else {
        cout << "Alice not found." << endl; // Khong chay
    }

    // Tim Charlie
    auto it_charlie = age_map.find("Charlie");
    if (it_charlie != age_map.end()) {
        cout << "Found Charlie! Age: " << it_charlie->second << endl; // Khong chay
    } else {
        cout << "Charlie not found." << endl;
    }

    return 0;
}

Giải thích: find() là lựa chọn tốt khi bạn cần cả thông tin về việc tìm thấy hay không và một cách hiệu quả để làm việc với phần tử đã tìm thấy.

Xóa Phần Tử khỏi map

Bạn có thể xóa phần tử khỏi map bằng khóa, iterator, hoặc một phạm vi iterator.

1. Xóa bằng khóa

Hàm erase(key) xóa phần tử có khóa bằng key. Nó trả về số lượng phần tử đã xóa (sẽ là 0 hoặc 1).

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

int main() {
    map<string, int> age_map;
    age_map["Alice"] = 30;
    age_map["Bob"] = 25;
    age_map["Charlie"] = 35;

    cout << "Map ban dau co " << age_map.size() << " phan tu." << endl; // Output: 3

    // Xoa Bob bang khoa
    size_t removed_count = age_map.erase("Bob");
    if (removed_count > 0) {
        cout << "Da xoa Bob. Con " << age_map.size() << " phan tu." << endl; // Output: Da xoa Bob. Con 2 phan tu.
    }

    // Thu xoa David (khong ton tai)
    size_t removed_david = age_map.erase("David");
    if (removed_david == 0) {
        cout << "David khong co trong map, khong xoa duoc." << endl; // Output: David khong co trong map, khong xoa duoc.
    }

    return 0;
}

Giải thích: Xóa bằng khóa là cách đơn giản nhất khi bạn chỉ có khóa cần xóa.

2. Xóa bằng Iterator

Hàm erase(iterator) xóa phần tử mà iterator trỏ tới. Nó trả về một iterator trỏ đến phần tử tiếp theo sau phần tử bị xóa (điều này rất hữu ích khi xóa trong vòng lặp).

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

int main() {
    map<string, int> age_map;
    age_map["Alice"] = 30;
    age_map["Bob"] = 25;
    age_map["Charlie"] = 35;

    // Tim Bob
    auto it_bob = age_map.find("Bob");

    // Xoa Bob bang iterator
    if (it_bob != age_map.end()) {
        // Luu y: erase(iterator) tra ve iterator den phan tu tiep theo
        auto it_next = age_map.erase(it_bob);
        cout << "Da xoa Bob bang iterator." << endl;
        if (it_next != age_map.end()) {
             cout << "Phan tu tiep theo la: " << it_next->first << endl; // Output: Phan tu tiep theo la: Charlie
        }
    }

    cout << "Map hien tai co " << age_map.size() << " phan tu." << endl; // Output: 2

    return 0;
}

Giải thích: Xóa bằng iterator thường được sử dụng sau khi bạn đã dùng find() để định vị phần tử hoặc khi bạn đang duyệt map và muốn xóa các phần tử dựa trên một điều kiện nào đó trong quá trình duyệt.

Các Thao Tác Cơ Bản Khác

Map cũng hỗ trợ các thao tác cơ bản khác:

  • size(): Trả về số lượng phần tử trong map.
  • empty(): Trả về true nếu map rỗng, false nếu ngược lại.
  • clear(): Xóa tất cả các phần tử khỏi map.
#include <map>
#include <string>
#include <iostream>

int main() {
    map<string, int> age_map;
    age_map["Alice"] = 30;
    age_map["Bob"] = 25;

    cout << "Kich thuoc ban dau: " << age_map.size() << endl; // Output: 2
    cout << "Map co rong khong? " << (age_map.empty() ? "Co" : "Khong") << endl; // Output: Khong

    age_map.clear(); // Xoa het cac phan tu

    cout << "Kich thuoc sau khi clear: " << age_map.size() << endl; // Output: 0
    cout << "Map co rong khong sau clear? " << (age_map.empty() ? "Co" : "Khong") << endl; // Output: Co

    return 0;
}

Giải thích: Các hàm này cung cấp thông tin cơ bản về trạng thái và kích thước của map.

Khi nào thì dùng map?

Bạn nên cân nhắc sử dụng map khi:

  • Bạn cần lưu trữ dữ liệu dưới dạng cặp khóa-giá trị.
  • Các khóa cần phải duy nhất.
  • Bạn cần các phần tử được sắp xếp tự động theo khóa.
  • Hiệu suất truy xuất, thêm, xóa logarithmic (O(log n)) là chấp nhận được cho ứng dụng của bạn.

Nếu bạn không cần các phần tử được sắp xếp và muốn hiệu suất trung bình O(1) cho các thao tác cơ bản, unordered_map là lựa chọn tốt hơn (sẽ được tìm hiểu trong các bài sau).

Một Ví Dụ Thực Tế Nhỏ: Đếm Tần Suất Từ

Đây là một ví dụ kinh điển thể hiện sức mạnh của map: đếm số lần xuất hiện của mỗi từ trong một chuỗi văn bản.

#include <iostream>
#include <map>
#include <string>
#include <sstream> // De tach chuoi thanh tu
#include <cctype> // De xu ly ky tu (chuyen thanh chu thuong)
#include <algorithm> // De su dung transform

int main() {
    string text = "This is a sample text. This text is a sample.";
    map<string, int> word_counts;

    // Tao mot stringstream tu chuoi van ban
    stringstream ss(text);
    string word;

    // Doc tung tu tu stringstream
    while (ss >> word) {
        // Don gian hoa tu: chuyen thanh chu thuong va loai bo dau cham, phay
        transform(word.begin(), word.end(), word.begin(),
                       [](unsigned char c){ return tolower(c); });

        // Loai bo cac ky tu dac biet o cuoi tu (vi du: dau cham)
        while (!word.empty() && ispunct(word.back())) {
            word.pop_back();
        }

        // Neu tu khong rong, tang bien dem trong map
        if (!word.empty()) {
            word_counts[word]++; // Day la dieu ky dieu cua map!
        }
    }

    // In ket qua (map tu dong sap xep theo tu)
    cout << "Tan suat xuat hien cua cac tu:" << endl;
    for (const auto& pair : word_counts) {
        cout << pair.first << ": " << pair.second << endl;
    }
    /* Output (co the khac tuy vao cach xu ly chuan hoa tu):
    a: 2
    is: 2
    sample: 2
    text: 2
    this: 2
    */

    return 0;
}

Giải thích: Trong ví dụ này, chúng ta sử dụng stringstream để dễ dàng tách chuỗi thành từng từ. Sau đó, với mỗi từ, chúng ta chuẩn hóa nó (chuyển thành chữ thường, loại bỏ dấu câu). Dòng word_counts[word]++; là trung tâm: nếu từ đó đã là khóa trong map, giá trị (số đếm) của nó sẽ được tăng lên. Nếu chưa, nó sẽ được thêm vào map với giá trị mặc định là 0, sau đó được tăng lên 1. Kết quả là map tự động lưu trữ và đếm số lần xuất hiện của mỗi từ, được sắp xếp theo thứ tự chữ cái của từ.

Comments

There are no comments at the moment.