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> // multimap được định nghĩa trong header <map>
#include <string>

int main() {
    // Khai báo một multimap lưu tên tác giả và tên sách
    multimap<string, string> author_books;

    // Thêm các cặp tác giả - sách. Chú ý tác giả "Nguyễn Nhật Ánh" xuất hiện nhiều lần
    author_books.insert({"Nguyễn Nhật Ánh", "Mắt Biếc"});
    author_books.insert({"Nguyễn Nhật Ánh", "Tôi Thấy Hoa Vàng Trên Cỏ Xanh"});
    author_books.insert({"Harper Lee", "To Kill a Mockingbird"});
    author_books.insert({"Nguyễn Nhật Ánh", "Cho Tôi Xin Một Vé Đi Tuổi Thơ"});
    author_books.insert({"Gabriel Garcia Marquez", "One Hundred Years of Solitude"});
    author_books.insert({"Harper Lee", "Go Set a Watchman"});

    cout << "Danh sach tac gia va sach (sap xep theo ten tac gia):\n";
    // Duyệt qua toàn bộ multimap
    for (const auto& pair : author_books) {
        cout << "- Tac gia: " << pair.first << ", Sach: " << pair.second << '\n';
    }
    // Output sẽ được sắp xếp theo tên tác giả

    return 0;
}

Giải thích code:

Chúng ta include header <map> để sử dụng multimap.
Khai báo multimap<string, string> với khóa là tên tác giả (kiểu string) và giá trị là tên sách (kiểu string).
Sử dụng phương thức insert() để thêm các cặp khóa-giá trị. Lưu ý rằng "Nguyễn Nhật Ánh" được thêm vào ba lần với ba cuốn sách khác nhau.
Duyệt qua multimap bằng vòng lặp range-based for. Các cặp pair.first (khóa) và pair.second (giá trị) được in ra. Quan sát output, bạn sẽ thấy các sách của cùng một tác giả được gom nhóm lại và các tác giả được sắp xếp theo thứ tự alphabet.

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> my_multi;
my_multi.insert({1, "Apple"});
my_multi.insert({2, "Banana"});
my_multi.insert({1, "Apricot"}); // Khóa 1 bị trùng, vẫn được chèn
my_multi.emplace(3, "Cherry");
my_multi.emplace(2, "Blueberry"); // Khóa 2 bị trùng, vẫn được chèn

// Multimap lúc này sẽ chứa: {1, "Apple"}, {1, "Apricot"}, {2, "Banana"}, {2, "Blueberry"}, {3, "Cherry"}
// (Thứ tự của "Apple" và "Apricot" khi có cùng khóa 1 có thể phụ thuộc vào thứ tự chèn, nhưng chúng sẽ nằm cạnh nhau)

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>

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

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

    // 1. Sử dụng count để biết số lượng sách
    size_t num_books = author_books.count(search_author);
    cout << "\nTac gia '" << search_author << "' co " << num_books << " cuon sach trong danh sach.\n";

    // 2. Sử dụng equal_range để liệt kê tất cả sách
    auto range = author_books.equal_range(search_author);

    cout << "Cac cuon sach cua '" << search_author << "':\n";
    for (auto it = range.first; it != range.second; ++it) {
        // it->first là khóa (tên tác giả), it->second là giá trị (tên sách)
        cout << "- " << it->second << '\n';
    }

    // 3. Tìm kiếm một tác giả không tồn tại
    string non_existent_author = "J.K. Rowling";
    if (author_books.count(non_existent_author) == 0) {
         cout << "\nKhong tim thay tac gia '" << non_existent_author << "' trong danh sach.\n";
    }

    return 0;
}

Giải thích code:

Chúng ta sử dụng count("Nguyễn Nhật Ánh") để biết có bao nhiêu cuốn sách của tác giả này trong multimap.
Phương thức equal_range("Nguyễn Nhật Ánh") trả về một cặp iterator. range.first trỏ đến cuốn sách đầu tiên của "Nguyễn Nhật Ánh", và range.second trỏ đến vị trí ngay sau cuốn sách cuối cùng của ông.
Vòng lặp for (auto it = range.first; it != range.second; ++it) duyệt qua chính xác phạm vi các phần tử có khóa là "Nguyễn Nhật Ánh". it->second truy cập vào tên sách.
Kiểm tra sự tồn tại của một khóa có thể dùng count(key) > 0.

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.

```cpp #include <iostream> #include <map> #include <string>

int main() {

multimap<string, string> author_books;
author_books.insert({"Nguyễn Nhật Ánh", "Mắt Biếc"});
author_books.insert({"Nguyễn Nhật Ánh", "Tôi Thấy Hoa Vàng Trên Cỏ Xanh"});
author_books.insert({"Harper Lee", "To Kill a Mockingbird"});
author_books.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& pair : author_books) {
    cout << "- " << pair.first << ": " << pair.second << '\n';
}

// Xóa tất cả sách của tác giả "Harper Lee"
size_t num_erased = author_books.erase("Harper Lee");
cout << "\nDa xoa " << num_erased << " cuon sach cua Harper Lee.\n";

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

// Ví dụ xóa một phần tử cụ thể bằng iterator (phức tạp hơn)
// Tìm và xóa cuốn "Mắt Biếc" của Nguyễn Nhật Ánh
auto range_nna = author_books.equal_range("Nguyễn Nhật Ánh");
for (auto it = range_nna.first; it != range_nna.second; ++it) {
    if (it->second == "Mắt Biếc") {
        // Sử dụng it = author_books.erase(it); nếu muốn tiếp tục vòng lặp sau khi xóa
        author_books.erase(it);
        cout << "\nDa xoa cuon 'Mat Biec'.\n";
        break; // Chỉ xóa cuốn đầu tiên tìm thấy
    }
}

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

    return 0;
}
```
*Giải thích code:*
*   `author_books.erase("Harper Lee")` tìm tất cả các phần tử có khóa "Harper Lee" và xóa chúng. Nó trả về số lượng phần tử đã xóa.
*   Xóa bằng iterator yêu cầu bạn tìm iterator của phần tử muốn xóa trước. Trong ví dụ, chúng ta dùng `equal_range` để tìm các sách của Nguyễn Nhật Ánh, sau đó duyệt qua phạm vi đó để tìm cuốn "Mắt Biếc" và xóa nó bằng `erase(it)`.

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> // unordered_multimap được định nghĩa trong header <unordered_map>
#include <string>

int main() {
    // Khai báo một unordered_multimap lưu tag và tiêu đề bài viết
    unordered_multimap<string, string> tag_articles;

    // Thêm các cặp tag - tiêu đề bài viết
    tag_articles.insert({"C++", "Gioi thieu ve STL"});
    tag_articles.insert({"Data Structures", "Gioi thieu ve STL"}); // Cùng bài viết, khác tag
    tag_articles.insert({"C++", "Multimap va Unordered_multimap"}); // Cùng tag, khác bài viết
    tag_articles.insert({"Containers", "Multimap va Unordered_multimap"}); // Cùng bài viết, khác tag
    tag_articles.insert({"Algorithms", "Sap xep Merge Sort"});
    tag_articles.insert({"Data Structures", "Cay B-Tree"});

    cout << "Danh sach tag va bai viet (khong theo thu tu cu the):\n";
    // Duyệt qua toàn bộ unordered_multimap
    for (const auto& pair : tag_articles) {
        cout << "- Tag: " << pair.first << ", Bai viet: " << pair.second << '\n';
    }
    // Output sẽ không được sắp xếp

    return 0;
}

Giải thích code:

Chúng ta include header <unordered_map> để sử dụng unordered_multimap.
Khai báo unordered_multimap<string, string>.
Sử dụng insert() để thêm các cặp tag-bài viết. Một tag có thể liên kết với nhiều bài, và một bài có thể liên kết với nhiều tag.
Duyệt và in ra các cặp. Thứ tự in ra sẽ không có quy tắc rõ ràng như multimap, vì nó phụ thuộc vào cấu trúc bảng hash.

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>

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

    string search_tag = "Data Structures";

    // 1. Sử dụng count để biết số lượng bài viết với tag này
    size_t num_articles = tag_articles.count(search_tag);
    cout << "\nTag '" << search_tag << "' co " << num_articles << " bai viet.\n";

    // 2. Sử dụng equal_range để liệt kê tất cả bài viết
    auto range = tag_articles.equal_range(search_tag);

    cout << "Cac bai viet voi tag '" << search_tag << "':\n";
    for (auto it = range.first; it != range.second; ++it) {
        cout << "- " << it->second << '\n';
    }
    // Lưu ý: Thứ tự các bài viết trong phạm vi này không được đảm bảo

    return 0;
}

Giải thích code:

Tương tự multimap, chúng ta dùng count() để đếm và equal_range() để lấy phạm vi các phần tử có cùng khóa.
Vòng lặp duyệt qua phạm vi này để in tên các bài viết. Điểm khác biệt chính so với multimap là thứ tự các bài viết cùng tag không được sắp xếp.

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>

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

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

    // Xóa tất cả bài viết có tag "C++"
    size_t num_erased = tag_articles.erase("C++");
    cout << "\nDa xoa " << num_erased << " bai viet voi tag 'C++'.\n";

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

    return 0;
}

Giải thích code:

tag_articles.erase("C++") tìm và xóa tất cả các cặp có khóa là "C++". Trả về số lượng phần tử đã xóa.
Tương tự multimap, bạn cũng có thể xóa bằng iterator sau khi tìm thấy phần tử mong muốn.

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.