Bài 20.4: Bài tập thực hành Unordered_set và Unordered_map trong C++

Chào mừng trở lại với series bài viết về C++! Hôm nay, chúng ta sẽ đi sâu vào thực hành với hai container cực kỳ mạnh mẽ và hiệu quả trong Thư viện Chuẩn C++ (STL): unordered_set và unordered_map. Nếu bạn đang tìm kiếm tốc độ xử lý dữ liệu chớp nhoáng cho các thao tác tìm kiếm, chèn và xóa, thì đây chính là lúc bạn cần chú ý!

Khác với set và map truyền thống dựa trên cây nhị phân tìm kiếm cân bằng (thường là cây Đỏ-Đen), unordered_set và unordered_map sử dụng bảng băm (hash table). Điều này mang lại độ phức tạp thời gian trung bình là O(1) cho các thao tác cơ bản (chèn, xóa, tìm kiếm), biến chúng thành lựa chọn lý tưởng cho nhiều bài toán thực tế đòi hỏi hiệu suất cao.

Chúng ta sẽ không chỉ lý thuyết suông, mà sẽ cùng nhau thực hành qua các ví dụ code C++ cụ thể để thấy rõ sức mạnh của chúng!

1. Sức Mạnh Của `unordered_set`: Lưu Trữ Các Phần Tử Duy Nhất Tốc Độ Cao

unordered_set là một container lưu trữ tập hợp các phần tử duy nhất. Điểm khác biệt lớn nhất so với set là các phần tử không được lưu trữ theo một thứ tự cụ thể nào, nhưng bù lại, tốc độ truy cập, chèn, xóa trung bình cực kỳ nhanh.

Các Thao Tác Cơ Bản Với `unordered_set`

Hãy xem qua các thao tác phổ biến nhất:

Khởi tạo: Tạo một unordered_set rỗng.
Chèn phần tử: Thêm một phần tử vào tập hợp. Nếu phần tử đã tồn tại, thao tác sẽ không có tác dụng.
Kiểm tra sự tồn tại: Tìm xem một phần tử có trong tập hợp hay không.
Xóa phần tử: Loại bỏ một phần tử khỏi tập hợp.
Lặp qua các phần tử: Duyệt qua tất cả các phần tử trong tập hợp (lưu ý: thứ tự không được đảm bảo).

Dưới đây là ví dụ minh họa:

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    // Khởi tạo một unordered_set lưu trữ string
    unordered_set<string> uniqueWords;

    // Chèn các từ
    uniqueWords.insert("apple");
    uniqueWords.insert("banana");
    uniqueWords.insert("apple"); // 'apple' đã tồn tại, sẽ không được thêm lại
    uniqueWords.insert("orange");

    cout << "Kich thuoc cua unordered_set: " << uniqueWords.size() << endl; // Output: 3

    // Kiem tra su ton tai cua phan tu
    if (uniqueWords.count("banana")) {
        cout << "'banana' co ton tai trong tap hop." << endl;
    } else {
        cout << "'banana' khong ton tai trong tap hop." << endl;
    }

    if (uniqueWords.find("grape") == uniqueWords.end()) {
         cout << "'grape' khong ton tai trong tap hop." << endl;
    }

    // Xoa phan tu
    uniqueWords.erase("apple");
    cout << "Kich thuoc sau khi xoa 'apple': " << uniqueWords.size() << endl; // Output: 2

    // Lap qua cac phan tu (thu tu khong dam bao)
    cout << "Cac phan tu trong unordered_set:" << endl;
    for (const string& word : uniqueWords) {
        cout << word << endl;
    }

    return 0;
}

Giải thích:

Chúng ta khai báo unordered_set<string> uniqueWords;.
insert() được dùng để thêm phần tử. Khi bạn chèn "apple" lần thứ hai, kích thước của set vẫn là 3 vì nó chỉ chứa các phần tử duy nhất.
count("banana") trả về 1 nếu "banana" có trong set, 0 nếu không. Đây là cách nhanh chóng để kiểm tra sự tồn tại.
find("grape") trả về một iterator. Nếu phần tử không tồn tại, nó trả về uniqueWords.end(). Đây cũng là một cách phổ biến để kiểm tra sự tồn tại và lấy vị trí nếu cần (dù vị trí không có ý nghĩa thứ tự ở đây).
erase("apple") xóa phần tử có giá trị "apple".
Vòng lặp for (const string& word : uniqueWords) duyệt qua các phần tử. Quan trọng: Bạn không thể dựa vào thứ tự xuất hiện của các từ khi lặp.

Bài Tập Thực Hành Nhỏ Với `unordered_set`: Đếm Số Lượng Số Phân Biệt

Hãy áp dụng unordered_set để giải bài toán kinh điển: cho một danh sách các số nguyên, hãy đếm xem có bao nhiêu số phân biệt.

#include <iostream>
#include <vector>
#include <unordered_set>

int main() {
    vector<int> numbers = {10, 20, 10, 30, 40, 20, 50, 10};
    unordered_set<int> distinctNumbers;

    // Duyet qua vector va chen vao unordered_set
    for (int num : numbers) {
        distinctNumbers.insert(num);
    }

    // Kich thuoc cua unordered_set chinh la so luong so phan biet
    cout << "Danh sach cac so: ";
    for(int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    cout << "So luong so phan biet: " << distinctNumbers.size() << endl; // Output: 4 (10, 20, 30, 40, 50)

    cout << "Cac so phan biet la: ";
    for (int num : distinctNumbers) {
        cout << num << " "; // Luu y thu tu khong dam bao
    }
    cout << endl;

    return 0;
}

Giải thích: Chúng ta đơn giản là duyệt qua vector gốc và chèn từng số vào unordered_set. Nhờ tính chất chỉ lưu trữ phần tử duy nhất của unordered_set, mọi số trùng lặp sẽ tự động bị bỏ qua. Kích thước cuối cùng của unordered_set chính là số lượng các số phân biệt.

2. Sức Mạnh Của `unordered_map`: Bản Đồ Key-Value Siêu Tốc

unordered_map lưu trữ các cặp khóa-giá trị (key-value pairs), trong đó các khóa là duy nhất. Giống như unordered_set, nó dựa trên bảng băm để cung cấp tốc độ truy cập, chèn, xóa trung bình O(1) dựa trên khóa.

Các Thao Tác Cơ Bản Với `unordered_map`

Khởi tạo: Tạo một unordered_map rỗng.
Chèn/Cập nhật: Thêm một cặp khóa-giá trị mới hoặc cập nhật giá trị cho một khóa đã tồn tại.
Truy cập giá trị: Lấy giá trị tương ứng với một khóa.
Kiểm tra sự tồn tại của khóa: Xem một khóa có trong map hay không.
Xóa phần tử: Loại bỏ cặp khóa-giá trị dựa trên khóa.
Lặp qua các phần tử: Duyệt qua tất cả các cặp khóa-giá trị (thứ tự không được đảm bảo).

Dưới đây là ví dụ minh họa:

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // Khởi tạo một unordered_map lưu trữ ten (string) va tuoi (int)
    unordered_map<string, int> ages;

    // Chen hoac cap nhat gia tri
    ages["Alice"] = 30;      // Chen Alice voi tuoi 30
    ages["Bob"] = 25;        // Chen Bob voi tuoi 25
    ages["Alice"] = 31;      // Cap nhat tuoi cua Alice thanh 31
    ages.insert({"Charlie", 22}); // Mot cach chen khac

    cout << "So luong nguoi trong map: " << ages.size() << endl; // Output: 3

    // Truy cap gia tri bang key
    cout << "Tuoi cua Bob: " << ages["Bob"] << endl; // Output: 25
    // cout << "Tuoi cua David: " << ages.at("David") << endl; // Dong nay se gay ra exception vi David khong ton tai

    // Kiem tra su ton tai cua key
    if (ages.count("Charlie")) {
        cout << "Charlie co trong map voi tuoi: " << ages["Charlie"] << endl; // Output: 22
    }

    // Xoa phan tu bang key
    ages.erase("Bob");
    cout << "So luong nguoi sau khi xoa Bob: " << ages.size() << endl; // Output: 2

    // Lap qua cac cap key-value (thu tu khong dam bao)
    cout << "Cac cap key-value trong map:" << endl;
    for (const auto& pair : ages) { // pair la mot pair<const string, int>
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

Giải thích:

Chúng ta khai báo unordered_map<string, int> ages;. Kiểu dữ liệu đầu tiên (string) là kiểu của khóa, kiểu thứ hai (int) là kiểu của giá trị.
Sử dụng toán tử [] (ages["Alice"] = 30;) là cách phổ biến nhất để chèn hoặc cập nhật. Nếu khóa chưa tồn tại, nó sẽ được chèn cùng với giá trị được gán. Nếu khóa đã tồn tại, giá trị cũ sẽ bị ghi đè.
ages.insert({"Charlie", 22}); cũng dùng để chèn. Nếu khóa đã tồn tại, thao tác này sẽ không có tác dụng (khác với [] ghi đè).
Truy cập giá trị có thể dùng [] (ages["Bob"]) hoặc at() (ages.at("Bob")). Điểm khác biệt quan trọng: at() sẽ ném ra một exception nếu khóa không tồn tại, trong khi [] sẽ tự động chèn khóa đó với giá trị mặc định (0 cho int, chuỗi rỗng cho string, v.v.) và trả về tham chiếu đến giá trị đó. Hãy cẩn thận khi dùng [] nếu bạn chỉ muốn truy cập và không muốn chèn ngầm.
count("Charlie") hoặc find("Charlie") tương tự như unordered_set để kiểm tra sự tồn tại của khóa.
erase("Bob") xóa cặp khóa-giá trị có khóa là "Bob".
Vòng lặp duyệt qua các cặp pair<const Key, Value>. pair.first là khóa (const), pair.second là giá trị.

Bài Tập Thực Hành Nhỏ Với `unordered_map`: Đếm Tần Suất Từ

unordered_map cực kỳ hữu ích cho việc đếm tần suất. Hãy viết code đếm số lần xuất hiện của mỗi từ trong một câu.

#include <iostream>
#include <string>
#include <unordered_map>
#include <sstream> // Thu vien xu ly chuoi nhu stream

int main() {
    string sentence = "day la mot cau lap lai tu lap day la";
    unordered_map<string, int> wordFrequencies;

    // Su dung stringstream de tach cac tu
    stringstream ss(sentence);
    string word;

    // Doc tung tu va dem tan suat
    while (ss >> word) {
        // Neu tu chua co trong map, no se duoc them vao voi gia tri mac dinh la 0
        // Sau do, gia tri se duoc tang len 1
        wordFrequencies[word]++;
    }

    // In ket qua
    cout << "Tan suat xuat hien cua cac tu:" << endl;
    for (const auto& pair : wordFrequencies) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

Giải thích:

Chúng ta dùng stringstream để dễ dàng tách câu thành từng từ.
Vòng lặp while (ss >> word) đọc từng từ.
Dòng ma thuật wordFrequencies[word]++; thực hiện cả hai việc:
- Nếu word chưa tồn tại làm khóa trong map, nó sẽ được chèn vào với giá trị mặc định là 0.
- Sau đó, giá trị tương ứng với khóa word sẽ được tăng lên 1.
Cuối cùng, chúng ta lặp qua map để in ra từng từ và số lần xuất hiện của nó.

3. `unordered_set` vs `set`, `unordered_map` vs `map`: Khi Nào Sử Dụng Cái Nào?

Sự khác biệt chính nằm ở cấu trúc dữ liệu nền tảng và do đó là hiệu suất và tính năng:

set / map:
- Dựa trên cây nhị phân tìm kiếm cân bằng (thường là cây Đỏ-Đen).
- Lưu trữ các phần tử/khóa theo thứ tự đã sắp xếp.
- Độ phức tạp thời gian cho hầu hết các thao tác là O(log N), đảm bảo hiệu suất ổn định ngay cả trong trường hợp xấu nhất.
- Sử dụng khi bạn cần dữ liệu được sắp xếp hoặc khi cần đảm bảo hiệu suất O(log N) trong mọi trường hợp.
unordered_set / unordered_map:
- Dựa trên bảng băm.
- Không lưu trữ các phần tử/khóa theo thứ tự nào cả. Thứ tự khi lặp qua có thể thay đổi giữa các lần chạy hoặc giữa các môi trường.
- Độ phức tạp thời gian cho hầu hết các thao tác là O(1) trung bình. Điều này làm cho chúng cực kỳ nhanh trong phần lớn các trường hợp.
- Độ phức tạp thời gian trong trường hợp xấu nhất có thể là O(N) (xảy ra khi có quá nhiều va chạm băm - hash collisions), nhưng điều này hiếm khi xảy ra với các hàm băm tốt và phân phối dữ liệu hợp lý.
- Sử dụng khi tốc độ là ưu tiên hàng đầu và bạn không cần dữ liệu phải được sắp xếp. Đây là lựa chọn mặc định tốt cho nhiều tác vụ tìm kiếm nhanh.

Tóm lại: Nếu bạn cần dữ liệu có thứ tự, hãy dùng set hoặc map. Nếu bạn chỉ cần tìm kiếm, chèn, xóa nhanh nhất có thể và không quan tâm đến thứ tự, hãy dùng unordered_set hoặc unordered_map. Trong nhiều ứng dụng thực tế, unordered containers thường mang lại hiệu suất cao hơn.

Comments

There are no comments at the moment.