Bài 19.2: Multimap và Unordered_map trong C++

Bài 19.2: Multimap và Unordered_multimap trong C++

Chào mừng các bạn quay trở lại với chuỗi bài viết về C++! Ở các bài trước, chúng ta đã tìm hiểu về map và unordered_map – những container mạnh mẽ giúp lưu trữ các cặp khóa-giá trị (key-value pairs). Tuy nhiên, một hạn chế cố hữu của map và unordered_map là mỗi khóa chỉ có thể liên kết với một giá trị duy nhất.

Trong thế giới thực, không phải lúc nào mối quan hệ khóa-giá trị cũng là 1-1. Ví dụ, một người có thể có nhiều số điện thoại, một học sinh có thể có nhiều điểm cho cùng một môn học, hoặc một từ có thể có nhiều nghĩa khác nhau. Lúc này, chúng ta cần đến những cấu trúc dữ liệu cho phép nhiều giá trị cùng tồn tại dưới một khóa duy nhất. Đó chính là lúc multimap và unordered_multimap tỏa sáng!

Bài viết này sẽ đi sâu vào hai container này, khám phá cách chúng hoạt động, khi nào nên sử dụng chúng, và làm thế nào để thao tác với dữ liệu bên trong.

multimap: Khi Khóa Lặp Lại Nhưng Cần Giữ Thứ Tự

multimap là một container kết hợp (associative container) giống như map ở chỗ nó lưu trữ các cặp khóa-giá trị và tự động sắp xếp các phần tử dựa trên khóa. Điểm khác biệt quan trọng nhất là multimap cho phép các khóa bị trùng lặp. Điều này có nghĩa là bạn có thể thêm nhiều cặp khóa-giá trị khác nhau với cùng một khóa.

Đặc điểm chính của multimap:
- Lưu trữ các cặp khóa-giá trị (pair<const Key, Value>).
- Cho phép khóa trùng lặp.
- Các phần tử được sắp xếp theo thứ tự tăng dần của khóa (mặc định, sử dụng less).
- Việc sắp xếp này giúp các thao tác tìm kiếm, chèn, và xóa có độ phức tạp thời gian là logarit (O(log n)).
- Thường được triển khai dưới dạng cây đỏ-đen (red-black tree).

Hãy xem xét một ví dụ: Lưu trữ danh sách các đầu sách được viết bởi cùng một tác giả. Một tác giả có thể viết nhiều sách.

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

using namespace std;

int main() {
    multimap<string, string> sachTacGia;

    sachTacGia.insert({"Nguyễn Nhật Ánh", "Mắt Biếc"});
    sachTacGia.insert({"Nguyễn Nhật Ánh", "Tôi Thấy Hoa Vàng Trên Cỏ Xanh"});
    sachTacGia.insert({"Harper Lee", "To Kill a Mockingbird"});
    sachTacGia.insert({"Nguyễn Nhật Ánh", "Cho Tôi Xin Một Vé Đi Tuổi Thơ"});
    sachTacGia.insert({"Gabriel Garcia Marquez", "One Hundred Years of Solitude"});
    sachTacGia.insert({"Harper Lee", "Go Set a Watchman"});

    cout << "Danh sach tac gia va sach (sap xep theo ten tac gia):\n";
    for (const auto& cap : sachTacGia) {
        cout << "- Tac gia: " << cap.first << ", Sach: " << cap.second << '\n';
    }

    return 0;
}

Danh sach tac gia va sach (sap xep theo ten tac gia):
- Tac gia: Gabriel Garcia Marquez, Sach: One Hundred Years of Solitude
- Tac gia: Harper Lee, Sach: To Kill a Mockingbird
- Tac gia: Harper Lee, Sach: Go Set a Watchman
- Tac gia: Nguyễn Nhật Ánh, Sach: Mắt Biếc
- Tac gia: Nguyễn Nhật Ánh, Sach: Tôi Thấy Hoa Vàng Trên Cỏ Xanh
- Tac gia: Nguyễn Nhật Ánh, Sach: Cho Tôi Xin Một Vé Đi Tuổi Thơ

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

Các thao tác cơ bản như chèn (insert, emplace), xóa (erase), tìm kiếm (find, count, lower_bound, upper_bound, equal_range) và duyệt (begin, end) đều có sẵn cho multimap. Tuy nhiên, cách chúng hoạt động khi có khóa trùng lặp là điểm cần lưu ý.

Chèn (Insertion): Sử dụng insert() hoặc emplace(). Mỗi lần chèn sẽ thêm một phần tử mới, ngay cả khi khóa đã tồn tại.

multimap<int, string> m;
m.insert({1, "Apple"});
m.insert({2, "Banana"});
m.insert({1, "Apricot"});
m.emplace(3, "Cherry");
m.emplace(2, "Blueberry");

Tìm kiếm (Searching):

count(key): Trả về số lượng phần tử có khóa bằng key. Đây là phương thức rất hữu ích với multimap.
find(key): Trả về một iterator trỏ đến phần tử đầu tiên có khóa bằng key. Nếu không tìm thấy, trả về end().
lower_bound(key): Trả về một iterator trỏ đến phần tử đầu tiên không nhỏ hơn key.
upper_bound(key): Trả về một iterator trỏ đến phần tử đầu tiên lớn hơn key.
equal_range(key): Trả về một pair gồm hai iterator: iterator đầu tiên là kết quả của lower_bound(key) và iterator thứ hai là kết quả của upper_bound(key). Cặp iterator này định nghĩa một phạm vi chứa tất cả các phần tử có khóa bằng key. Đây là phương thức quan trọng nhất để truy cập tất cả các giá trị liên kết với một khóa trùng lặp.

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

using namespace std;

int main() {
    multimap<string, string> sachTacGia;
    sachTacGia.insert({"Nguyễn Nhật Ánh", "Mắt Biếc"});
    sachTacGia.insert({"Nguyễn Nhật Ánh", "Tôi Thấy Hoa Vàng Trên Cỏ Xanh"});
    sachTacGia.insert({"Harper Lee", "To Kill a Mockingbird"});
    sachTacGia.insert({"Nguyễn Nhật Ánh", "Cho Tôi Xin Một Vé Đi Tuổi Thơ"});
    sachTacGia.insert({"Gabriel Garcia Marquez", "One Hundred Years of Solitude"});
    sachTacGia.insert({"Harper Lee", "Go Set a Watchman"});

    string tgTim = "Nguyễn Nhật Ánh";

    size_t soSach = sachTacGia.count(tgTim);
    cout << "\nTac gia '" << tgTim << "' co " << soSach << " cuon sach trong danh sach.\n";

    auto khoang = sachTacGia.equal_range(tgTim);

    cout << "Cac cuon sach cua '" << tgTim << "':\n";
    for (auto it = khoang.first; it != khoang.second; ++it) {
        cout << "- " << it->second << '\n';
    }

    string tgKoTonTai = "J.K. Rowling";
    if (sachTacGia.count(tgKoTonTai) == 0) {
         cout << "\nKhong tim thay tac gia '" << tgKoTonTai << "' trong danh sach.\n";
    }

    return 0;
}


Tac gia 'Nguyễn Nhật Ánh' co 3 cuon sach trong danh sach.
Cac cuon sach cua 'Nguyễn Nhật Ánh':
- Mắt Biếc
- Tôi Thấy Hoa Vàng Trên Cỏ Xanh
- Cho Tôi Xin Một Vé Đi Tuổi Thơ

Khong tim thay tac gia 'J.K. Rowling' trong danh sach.

Xóa (Deletion):

erase(iterator): Xóa phần tử được trỏ bởi iterator. Trả về iterator trỏ đến phần tử tiếp theo.
erase(key): Xóa tất cả các phần tử có khóa bằng key. Trả về số lượng phần tử đã xóa.

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

using namespace std;

int main() {
    multimap<string, string> sachTacGia;
    sachTacGia.insert({"Nguyễn Nhật Ánh", "Mắt Biếc"});
    sachTacGia.insert({"Nguyễn Nhật Ánh", "Tôi Thấy Hoa Vàng Trên Cỏ Xanh"});
    sachTacGia.insert({"Harper Lee", "To Kill a Mockingbird"});
    sachTacGia.insert({"Nguyễn Nhật Ánh", "Cho Tôi Xin Một Vé Đi Tuổi Thơ"});

    cout << "Truoc khi xoa:\n";
    for (const auto& cap : sachTacGia) {
        cout << "- " << cap.first << ": " << cap.second << '\n';
    }

    size_t soXoa = sachTacGia.erase("Harper Lee");
    cout << "\nDa xoa " << soXoa << " cuon sach cua Harper Lee.\n";

    cout << "\nSau khi xoa Harper Lee:\n";
    for (const auto& cap : sachTacGia) {
        cout << "- " << cap.first << ": " << cap.second << '\n';
    }

    auto khoangNNA = sachTacGia.equal_range("Nguyễn Nhật Ánh");
    for (auto it = khoangNNA.first; it != khoangNNA.second; ++it) {
        if (it->second == "Mắt Biếc") {
            sachTacGia.erase(it);
            cout << "\nDa xoa cuon 'Mắt Biếc'.\n";
            break;
        }
    }

    cout << "\nSau khi xoa Mat Biec:\n";
    for (const auto& cap : sachTacGia) {
        cout << "- " << cap.first << ": " << cap.second << '\n';
    }

    return 0;
}

Truoc khi xoa:
- Harper Lee: To Kill a Mockingbird
- Nguyễn Nhật Ánh: Mắt Biếc
- Nguyễn Nhật Ánh: Tôi Thấy Hoa Vàng Trên Cỏ Xanh
- Nguyễn Nhật Ánh: Cho Tôi Xin Một Vé Đi Tuổi Thơ

Da xoa 1 cuon sach cua Harper Lee.

Sau khi xoa Harper Lee:
- Nguyễn Nhật Ánh: Mắt Biếc
- Nguyễn Nhật Ánh: Tôi Thấy Hoa Vàng Trên Cỏ Xanh
- Nguyễn Nhật Ánh: Cho Tôi Xin Một Vé Đi Tuổi Thơ

Da xoa cuon 'Mắt Biếc'.

Sau khi xoa Mat Biec:
- Nguyễn Nhật Ánh: Tôi Thấy Hoa Vàng Trên Cỏ Xanh
- Nguyễn Nhật Ánh: Cho Tôi Xin Một Vé Đi Tuổi Thơ

unordered_multimap: Tốc Độ Là Ưu Tiên, Thứ Tự Không Quan Trọng

Giống như cách unordered_map là phiên bản "không có thứ tự" của map, unordered_multimap là phiên bản "không có thứ tự" của multimap. Nó cũng cho phép khóa trùng lặp nhưng lưu trữ các phần tử trong các "thùng" (buckets) dựa trên giá trị hash của khóa, thay vì sắp xếp chúng theo cây.

Đặc điểm chính của unordered_multimap:
- Lưu trữ các cặp khóa-giá trị (pair<const Key, Value>).
- Cho phép khóa trùng lặp.
- Các phần tử không có thứ tự cố định (thứ tự dựa vào hàm hash và cấu trúc bảng hash nội bộ).
- Các thao tác tìm kiếm, chèn, và xóa có độ phức tạp thời gian trung bình là hằng số (O(1)). Tuy nhiên, trong trường hợp xấu nhất (bad hash function hoặc quá nhiều va chạm), có thể suy biến thành tuyến tính (O(n)).
- Yêu cầu khóa (Key) phải có hàm hash (hash) và toán tử so sánh bằng (operator==) được định nghĩa. Các kiểu dữ liệu cơ bản và string đã có sẵn.

Ví dụ: Lưu trữ danh sách các tag cho một bài viết trên blog. Một bài viết có thể có nhiều tag, và nhiều bài viết có thể dùng cùng một tag.

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

using namespace std;

int main() {
    unordered_multimap<string, string> baiVietTag;

    baiVietTag.insert({"C++", "Gioi thieu ve STL"});
    baiVietTag.insert({"Data Structures", "Gioi thieu ve STL"});
    baiVietTag.insert({"C++", "Multimap va Unordered_multimap"});
    baiVietTag.insert({"Containers", "Multimap va Unordered_multimap"});
    baiVietTag.insert({"Algorithms", "Sap xep Merge Sort"});
    baiVietTag.insert({"Data Structures", "Cay B-Tree"});

    cout << "Danh sach tag va bai viet (khong theo thu tu cu the):\n";
    for (const auto& cap : baiVietTag) {
        cout << "- Tag: " << cap.first << ", Bai viet: " << cap.second << '\n';
    }

    return 0;
}

Danh sach tag va bai viet (khong theo thu tu cu the):
- Tag: Data Structures, Bai viet: Gioi thieu ve STL
- Tag: Data Structures, Bai viet: Cay B-Tree
- Tag: Algorithms, Bai viet: Sap xep Merge Sort
- Tag: C++, Bai viet: Gioi thieu ve STL
- Tag: C++, Bai viet: Multimap va Unordered_multimap
- Tag: Containers, Bai viet: Multimap va Unordered_multimap

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

Các thao tác tương tự multimap nhưng hiệu suất khác biệt do cấu trúc bên dưới.

Chèn (Insertion): Giống multimap, sử dụng insert() hoặc emplace(). Độ phức tạp trung bình O(1), xấu nhất O(n).

Tìm kiếm (Searching): Các phương thức giống multimap: count(), find(), equal_range().

count(key): Trả về số lượng phần tử có khóa bằng key. Trung bình O(1), xấu nhất O(n).
find(key): Trả về iterator đến phần tử đầu tiên có khóa key. Trung bình O(1), xấu nhất O(n).
equal_range(key): Trả về một pair của iterator định nghĩa phạm vi chứa tất cả phần tử có khóa key. Trung bình O(1) để tìm đầu phạm vi, sau đó duyệt qua phạm vi (phụ thuộc vào số lượng phần tử trùng lặp), xấu nhất O(n).

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

using namespace std;

int main() {
    unordered_multimap<string, string> baiVietTag;
    baiVietTag.insert({"C++", "Gioi thieu ve STL"});
    baiVietTag.insert({"Data Structures", "Gioi thieu ve STL"});
    baiVietTag.insert({"C++", "Multimap va Unordered_multimap"});
    baiVietTag.insert({"Containers", "Multimap va Unordered_multimap"});
    baiVietTag.insert({"Algorithms", "Sap xep Merge Sort"});
    baiVietTag.insert({"Data Structures", "Cay B-Tree"});

    string tagTim = "Data Structures";

    size_t soBaiViet = baiVietTag.count(tagTim);
    cout << "\nTag '" << tagTim << "' co " << soBaiViet << " bai viet.\n";

    auto khoang = baiVietTag.equal_range(tagTim);

    cout << "Cac bai viet voi tag '" << tagTim << "':\n";
    for (auto it = khoang.first; it != khoang.second; ++it) {
        cout << "- " << it->second << '\n';
    }

    return 0;
}


Tag 'Data Structures' co 2 bai viet.
Cac bai viet voi tag 'Data Structures':
- Gioi thieu ve STL
- Cay B-Tree

Xóa (Deletion):

erase(iterator): Xóa phần tử được trỏ bởi iterator.
erase(key): Xóa tất cả các phần tử có khóa bằng key. Trả về số lượng phần tử đã xóa.

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

using namespace std;

int main() {
    unordered_multimap<string, string> baiVietTag;
    baiVietTag.insert({"C++", "Gioi thieu ve STL"});
    baiVietTag.insert({"Data Structures", "Gioi thieu ve STL"});
    baiVietTag.insert({"C++", "Multimap va Unordered_multimap"});
    baiVietTag.insert({"Containers", "Multimap va Unordered_multimap"});
    baiVietTag.insert({"Algorithms", "Sap xep Merge Sort"});
    baiVietTag.insert({"Data Structures", "Cay B-Tree"});

    cout << "Truoc khi xoa:\n";
    for (const auto& cap : baiVietTag) {
        cout << "- " << cap.first << ": " << cap.second << '\n';
    }

    size_t soXoa = baiVietTag.erase("C++");
    cout << "\nDa xoa " << soXoa << " bai viet voi tag 'C++'.\n";

    cout << "\nSau khi xoa tag C++:\n";
    for (const auto& cap : baiVietTag) {
        cout << "- " << cap.first << ": " << cap.second << '\n';
    }

    return 0;
}

Truoc khi xoa:
- Tag: Data Structures, Bai viet: Gioi thieu ve STL
- Tag: Data Structures, Bai viet: Cay B-Tree
- Tag: Algorithms, Bai viet: Sap xep Merge Sort
- Tag: C++, Bai viet: Gioi thieu ve STL
- Tag: C++, Bai viet: Multimap va Unordered_multimap
- Tag: Containers, Bai viet: Multimap va Unordered_multimap

Da xoa 2 bai viet voi tag 'C++'.

Sau khi xoa tag C++:
- Tag: Data Structures, Bai viet: Gioi thieu ve STL
- Tag: Data Structures, Bai viet: Cay B-Tree
- Tag: Algorithms, Bai viet: Sap xep Merge Sort
- Tag: Containers, Bai viet: Multimap va Unordered_multimap

Multimap vs. Unordered_multimap: Chọn Lựa Thế Nào?

Quyết định sử dụng multimap hay unordered_multimap phụ thuộc vào yêu cầu cụ thể của bạn:

Sử dụng multimap khi:
- Bạn cần lưu trữ các cặp khóa-giá trị có thể trùng lặp.
- Bạn cần các phần tử được tự động sắp xếp theo thứ tự của khóa.
- Hiệu suất tìm kiếm, chèn, xóa logarit (O(log n)) là đủ nhanh cho ứng dụng của bạn, hoặc khi bạn làm việc với tập dữ liệu không quá lớn.
- Bạn cần sử dụng các thao tác dựa trên thứ tự như tìm kiếm trong một phạm vi khóa (range search).
Sử dụng unordered_multimap khi:
- Bạn cần lưu trữ các cặp khóa-giá trị có thể trùng lặp.
- Thứ tự của các phần tử không quan trọng.
- Bạn cần hiệu suất tìm kiếm, chèn, xóa trung bình rất nhanh (O(1)). Điều này đặc biệt quan trọng với tập dữ liệu lớn và khi các thao tác này là phổ biến nhất.
- Khóa của bạn là một kiểu dữ liệu có thể băm (hashable) và bạn có một hàm hash tốt để tránh va chạm (collisions).

Comments

There are no comments at the moment.