Khóa học C++ từ cơ bản đến nâng cao

Bài 18.2: Multiset và Unordered_set trong C++

Chào mừng trở lại với chuỗi bài blog về C++! Hôm nay, chúng ta sẽ "lặn sâu" vào thế giới của hai cấu trúc dữ liệu cực kỳ hữu ích trong Thư viện Chuẩn C++ (STL): multiset và unordered_set. Nếu bạn đã quen thuộc với set, thì multiset và unordered_set là những "anh em" của nó, mỗi loại mang một đặc tính riêng biệt để giải quyết các bài toán cụ thể.

Chúng ta sẽ tìm hiểu xem chúng là gì, cách sử dụng chúng, và quan trọng nhất là sự khác biệt cốt lõi giúp bạn đưa ra lựa chọn phù hợp cho từng tình huống lập trình.

multiset: Khi thứ tự quan trọng và trùng lặp được chấp nhận

multiset là một container (vùng chứa) trong STL, lưu trữ các phần tử theo một thứ tự được sắp xếp. Điểm đặc biệt làm nên tên tuổi của nó (multi) chính là khả năng cho phép các phần tử trùng lặp.

Nghĩ về nó như một tập hợp các số mà bạn luôn muốn giữ chúng theo thứ tự từ nhỏ đến lớn, và nếu có nhiều số giống nhau, bạn muốn giữ lại tất cả chúng.

Về mặt kỹ thuật, multiset thường được triển khai dựa trên cấu trúc cây cân bằng (như Red-Black Tree), đảm bảo các thao tác cơ bản như thêm, xóa, tìm kiếm có độ phức tạp thời gian là O(log N), trong đó N là số lượng phần tử trong multiset.

Các thao tác cơ bản với multiset

Hãy cùng xem một số ví dụ minh họa cách sử dụng multiset.

1. Khởi tạo và thêm phần tử (insert)

#include <iostream>
#include <multiset>

int main() {
    multiset<int> ms;

    ms.insert(10);
    ms.insert(5);
    ms.insert(15);
    ms.insert(5);
    ms.insert(10);

    cout << "Kich thuoc ms: " << ms.size() << endl;

    cout << "Cac phan tu trong ms: ";
    for (int x : ms) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Kich thuoc ms: 5
Cac phan tu trong ms: 5 5 10 10 15

Giải thích: Đoạn code này tạo một multiset<int>, chèn các số vào. Bạn có thể thấy rằng các giá trị 5 và 10 được thêm nhiều lần và đều được lưu giữ. Khi duyệt qua myMultiset, các phần tử được in ra theo thứ tự tăng dần, bất kể thứ tự chèn vào ban đầu.

2. Tìm kiếm phần tử (find, count)

Bạn có thể tìm kiếm một phần tử cụ thể và đếm số lần xuất hiện của nó.

#include <iostream>
#include <multiset>

int main() {
    multiset<int> ms = {10, 5, 15, 5, 20, 10};

    auto it = ms.find(10);
    if (it != ms.end()) {
        cout << "Tim thay so 10 trong multiset." << endl;
        cout << "Gia tri tai iterator find: " << *it << endl;
    } else {
        cout << "Khong tim thay so 10." << endl;
    }

    it = ms.find(100);
    if (it != ms.end()) {
        cout << "Tim thay so 100 trong multiset." << endl;
    } else {
        cout << "Khong tim thay so 100." << endl;
    }

    cout << "So lan xuat hien cua 5: " << ms.count(5) << endl;
    cout << "So lan xuat hien cua 10: " << ms.count(10) << endl;
    cout << "So lan xuat hien cua 20: " << ms.count(20) << endl;
    cout << "So lan xuat hien cua 100: " << ms.count(100) << endl;

    return 0;
}

Tim thay so 10 trong multiset.
Gia tri tai iterator find: 10
Khong tim thay so 100.
So lan xuat hien cua 5: 2
So lan xuat hien cua 10: 2
So lan xuat hien cua 20: 1
So lan xuat hien cua 100: 0

Giải thích: Phương thức find(value) trả về một iterator trỏ đến lần xuất hiện đầu tiên của value trong multiset (theo thứ tự đã sắp xếp). Nếu không tìm thấy, nó trả về numbers.end(). Phương thức count(value) thì cực kỳ tiện lợi, nó trả về tổng số lần value xuất hiện trong multiset.

3. Xóa phần tử (erase)

Xóa phần tử trong multiset có thể hơi phức tạp hơn so với set vì có thể có trùng lặp.

#include <iostream>
#include <multiset>

int main() {
    multiset<int> ms = {10, 5, 15, 5, 20, 10};

    cout << "Multiset ban dau: ";
    for (int x : ms) cout << x << " ";
    cout << endl;

    auto it = ms.find(5);
    if (it != ms.end()) {
        ms.erase(it);
    }

    cout << "Sau khi xoa mot so 5: ";
    for (int x : ms) cout << x << " ";
    cout << endl;

    size_t sl = ms.erase(10);
    cout << "So phan tu bi xoa (gia tri 10): " << sl << endl;

    cout << "Sau khi xoa tat ca so 10: ";
    for (int x : ms) cout << x << " ";
    cout << endl;

    ms.erase(ms.upper_bound(15), ms.end());

    cout << "Sau khi xoa phan tu > 15: ";
    for (int x : ms) cout << x << " ";
    cout << endl;

    return 0;
}

Multiset ban dau: 5 5 10 10 15 20 
Sau khi xoa mot so 5: 5 10 10 15 20 
So phan tu bi xoa (gia tri 10): 2
Sau khi xoa tat ca so 10: 5 15 20 
Sau khi xoa phan tu > 15: 5 15

Giải thích:

• erase(iterator): Xóa phần tử mà iterator đó đang trỏ tới. Nếu bạn chỉ muốn xóa một trong số các phần tử trùng lặp, bạn cần tìm đúng iterator của phần tử đó (thường là dùng find hoặc duyệt).
• erase(value): Xóa tất cả các lần xuất hiện của value trong multiset và trả về số lượng phần tử đã bị xóa.
• erase(first_iterator, last_iterator): Xóa tất cả các phần tử trong phạm vi từ first_iterator đến last_iterator (không bao gồm last_iterator). Kết hợp với lower_bound và upper_bound rất hữu ích.

unordered_set: Khi tốc độ là ưu tiên và chỉ cần duy nhất

Trái ngược với multiset (và set), unordered_set là một container lưu trữ các phần tử theo một thứ tự không được đảm bảo (unordered). Nó dựa trên cấu trúc bảng băm (hash table).

Điểm mấu chốt của unordered_set là:

1. Nó không cho phép các phần tử trùng lặp.
2. Các thao tác cơ bản như thêm, xóa, tìm kiếm có độ phức tạp thời gian trung bình là O(1) (thời gian hằng số). Trong trường hợp xấu nhất (xảy ra va chạm băm nhiều), độ phức tạp có thể lên tới O(N), nhưng điều này khá hiếm với hàm băm tốt.

Nghĩ về nó như một cái "túi" chứa các vật duy nhất. Bạn bỏ vật vào, chúng nằm lộn xộn trong túi, nhưng bạn có thể nhanh chóng kiểm tra xem một vật cụ thể có trong túi hay không.

Các thao tác cơ bản với unordered_set

Hãy xem unordered_set hoạt động như thế nào.

1. Khởi tạo và thêm phần tử (insert)

#include <iostream>
#include <unordered_set>

int main() {
    unordered_set<int> us;

    us.insert(10);
    us.insert(5);
    us.insert(15);
    auto kq5 = us.insert(5);
    auto kq10 = us.insert(10);

    cout << "Insert 5 lan 2 " << (kq5.second ? "thanh cong" : "that bai") << endl;
    cout << "Insert 10 lan 2 " << (kq10.second ? "thanh cong" : "that bai") << endl;

    cout << "Kich thuoc us: " << us.size() << endl;

    cout << "Cac phan tu trong us: ";
    for (int x : us) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Insert 5 lan 2 that bai
Insert 10 lan 2 that bai
Kich thuoc us: 3
Cac phan tu trong us: 15 5 10

Giải thích: Khi bạn cố gắng chèn một phần tử đã tồn tại vào unordered_set, thao tác insert sẽ trả về một pair với phần tử second là false, và phần tử đó sẽ không được thêm vào lại. Kích thước của tập hợp vẫn là 3 (5, 10, 15). Khi duyệt, thứ tự in ra có thể khác nhau mỗi lần chạy.

2. Tìm kiếm phần tử (find, count)

Tìm kiếm trong unordered_set rất nhanh, trung bình là O(1).

#include <iostream>
#include <unordered_set>

int main() {
    unordered_set<int> us = {10, 5, 15, 20};

    auto it = us.find(10);
    if (it != us.end()) {
        cout << "Tim thay so 10 trong unordered_set." << endl;
    } else {
        cout << "Khong tim thay so 10." << endl;
    }

    it = us.find(100);
    if (it != us.end()) {
        cout << "Tim thay so 100 trong unordered_set." << endl;
    } else {
        cout << "Khong tim thay so 100." << endl;
    }

    cout << "So lan xuat hien cua 5: " << us.count(5) << endl;
    cout << "So lan xuat hien cua 100: " << us.count(100) << endl;

    return 0;
}

Tim thay so 10 trong unordered_set.
Khong tim thay so 100.
So lan xuat hien cua 5: 1
So lan xuat hien cua 100: 0

Giải thích: Phương thức find(value) hoạt động tương tự như trong multiset và set, trả về iterator trỏ đến phần tử nếu tìm thấy, hoặc end() nếu không. Phương thức count(value) trả về số lần xuất hiện. Tuy nhiên, vì unordered_set không cho phép trùng lặp, count luôn chỉ trả về 0 (nếu không tìm thấy) hoặc 1 (nếu tìm thấy).

3. Xóa phần tử (erase)

Xóa phần tử trong unordered_set cũng rất nhanh.

#include <iostream>
#include <unordered_set>

int main() {
    unordered_set<int> us = {10, 5, 15, 20};

    cout << "Unordered_set ban dau: ";
    for (int x : us) cout << x << " ";
    cout << endl;

    size_t sl = us.erase(15);
    cout << "So phan tu bi xoa (gia tri 15): " << sl << endl;

    cout << "Sau khi xoa 15: ";
    for (int x : us) cout << x << " ";
    cout << endl;

    sl = us.erase(100);
    cout << "So phan tu bi xoa (gia tri 100): " << sl << endl;

    auto it = us.find(10);
    if(it != us.end()) {
        us.erase(it);
    }

    cout << "Sau khi xoa 10: ";
    for (int x : us) cout << x << " ";
    cout << endl;

    return 0;
}

Unordered_set ban dau: 20 15 5 10 
So phan tu bi xoa (gia tri 15): 1
Sau khi xoa 15: 20 5 10 
So phan tu bi xoa (gia tri 100): 0
Sau khi xoa 10: 20 5

Giải thích: Phương thức erase(value) sẽ tìm và xóa phần tử có giá trị đó (nếu tồn tại) và trả về 1 nếu xóa thành công, 0 nếu không tìm thấy. Phương thức erase(iterator) xóa phần tử mà iterator đó trỏ tới. Cả hai đều có độ phức tạp trung bình O(1).

Multiset vs. Unordered_set: Lựa chọn nào cho bài toán của bạn?

Sau khi tìm hiểu về cả hai, đây là bảng tóm tắt sự khác biệt chính để giúp bạn quyết định nên dùng container nào:

Khi nào nên sử dụng multiset?

• Khi bạn cần lưu trữ một tập hợp mà thứ tự của các phần tử là quan trọng.
• Khi bạn cần lưu trữ các phần tử có thể trùng lặp.
• Khi bạn cần thực hiện các thao tác như tìm kiếm phạm vi (lower_bound, upper_bound).
• Khi độ phức tạp O(log N) là chấp nhận được.

Ví dụ: Theo dõi danh sách điểm thi của học sinh (có thể có điểm trùng nhau) và muốn xem danh sách điểm theo thứ tự tăng dần.

Khi nào nên sử dụng unordered_set?

• Khi bạn chỉ cần lưu trữ các phần tử duy nhất.
• Khi thứ tự của các phần tử không quan trọng.
• Khi bạn ưu tiên tốc độ truy cập trung bình O(1) cho các thao tác thêm, xóa, tìm kiếm.

Ví dụ: Lưu trữ danh sách các từ duy nhất xuất hiện trong một văn bản, hoặc kiểm tra sự tồn tại nhanh chóng của một phần tử trong một tập lớn.