Khóa học CTDL và GT

Bài 8.3. Multimap và các ứng dụng đơn giản

Chào mừng các bạn quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật của FullhouseDev!

Trong các bài trước, chúng ta đã khám phá sức mạnh của các cấu trúc dữ liệu liên kết (associative containers) như std::map, nơi mỗi khóa là duy nhất và được dùng để tra cứu giá trị tương ứng. std::map cực kỳ hữu ích cho các tình huống cần ánh xạ 1-1 (one-to-one).

Tuy nhiên, trong thế giới lập trình thực tế, đôi khi chúng ta gặp phải những tình huống mà một khóa lại cần liên kết với nhiều giá trị. Ví dụ: một tên sinh viên có thể có nhiều điểm kiểm tra, một từ trong văn bản có thể xuất hiện ở nhiều dòng khác nhau, hoặc một sân bay có nhiều chuyến bay khởi hành. Nếu chỉ dùng std::map, chúng ta sẽ phải tìm cách lưu trữ tập hợp các giá trị (như dùng std::vector làm kiểu dữ liệu cho value: std::map<KeyType, std::vector<ValueType>>), điều này có thể trở nên rườm rà.

May mắn thay, C++ STL cung cấp một giải pháp thanh lịch hơn cho vấn đề này: std::multimap.

std::multimap là gì?

std::multimap là một container liên kết (associative container) tương tự như std::map, nhưng có một điểm khác biệt quan trọng: nó cho phép lưu trữ nhiều phần tử có cùng một khóa (duplicate keys).

Giống như std::map, std::multimap cũng lưu trữ các cặp khóa-giá trị (key-value pairs). Các phần tử trong multimap được tự động sắp xếp theo thứ tự tăng dần của khóa (mặc định sử dụng toán tử < hoặc một comparator tùy chỉnh).

Hãy hình dung std::map là một cuốn từ điển Anh-Việt đơn giản, mỗi từ tiếng Anh (khóa) chỉ có một nghĩa tiếng Việt duy nhất (giá trị). Còn std::multimap giống một cuốn từ điển Anh-Việt đầy đủ hơn, nơi một từ tiếng Anh (khóa) có thể có nhiều nghĩa khác nhau (nhiều giá trị).

Các đặc điểm chính của std::multimap

• Liên kết (Associative): Các phần tử được truy cập bằng khóa, không phải theo vị trí chỉ mục.
• Có thứ tự (Ordered): Các phần tử được sắp xếp dựa trên khóa. Thứ tự này được duy trì tự động khi thêm hoặc xóa phần tử.
• Cho phép khóa trùng lặp (Duplicate Keys Allowed): Đây là điểm khác biệt cốt lõi so với std::map.
• Cặp Khóa-Giá trị (Key-Value Pairs): Mỗi phần tử là một cặp (key, value). Giá trị liên kết với khóa có thể không duy nhất.
• Cây nhị phân tìm kiếm cân bằng (Balanced Binary Search Tree): multimap thường được triển khai dựa trên cấu trúc cây (ví dụ: cây đỏ-đen), đảm bảo các thao tác cơ bản như chèn, xóa và 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 container.

Sử dụng std::multimap: Các thao tác cơ bản và ví dụ

Để sử dụng std::multimap, bạn cần include header <map>.

#include <iostream>
#include <map> // Bao gồm cả map và multimap
#include <string>

Khai báo

Cú pháp khai báo multimap tương tự như map:

std::multimap<KieuKhóa, KieuGiaTri> ten_multimap;

Ví dụ:

std::multimap<std::string, int> student_scores; // Lưu tên sinh viên (khóa) và điểm (giá trị)
std::multimap<char, std::string> char_to_words; // Lưu ký tự (khóa) và các từ bắt đầu bằng ký tự đó (giá trị)

Chèn phần tử (insert)

Bạn có thể chèn các cặp khóa-giá trị bằng hàm insert. Vì multimap cho phép khóa trùng lặp, mọi lệnh insert sẽ thêm một phần tử mới vào container (trừ khi có lỗi bộ nhớ, v.v.).

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

int main() {
    std::multimap<std::string, int> student_scores;

    // Chèn các điểm cho các sinh viên
    student_scores.insert({"Alice", 95});
    student_scores.insert({"Bob", 80});
    student_scores.insert({"Alice", 88}); // Alice có thêm một điểm khác
    student_scores.insert({"Charlie", 75});
    student_scores.insert({"Bob", 92});   // Bob cũng có thêm điểm

    std::cout << "Multimap sau khi insert:\n";
    // Duyệt qua multimap (sẽ được sắp xếp theo tên)
    for (const auto& pair : student_scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Giải thích:

• Chúng ta khai báo student_scores với khóa là std::string (tên) và giá trị là int (điểm).
• Hàm insert được gọi với cặp {tên, điểm}.
• Lưu ý cách "Alice" và "Bob" xuất hiện nhiều lần trong multimap.
• Khi duyệt qua multimap, các phần tử được trình bày theo thứ tự tăng dần của khóa ("Alice", "Bob", "Charlie"). Các giá trị cho cùng một khóa sẽ xuất hiện liền kề nhau theo thứ tự chèn (hoặc theo thứ tự được duy trì nội bộ bởi cấu trúc cây).

Truy cập và tìm kiếm

Đây là phần thú vị và khác biệt nhất khi làm việc với multimap so với map. Vì có nhiều phần tử với cùng một khóa, bạn không thể chỉ truy cập bằng [] (toán tử [] chỉ dùng cho map với khóa duy nhất). Thay vào đó, bạn sử dụng các hàm tìm kiếm trả về iterator.

• count(key): Trả về số lượng phần tử có khóa key. Rất hữu ích để kiểm tra xem một khóa có tồn tại (và bao nhiêu lần) hay không.
• find(key): Trả về một iterator trỏ đến phần tử đầu tiên có khóa key. Nếu không tìm thấy, nó trả về multimap.end().
• lower_bound(key): Trả về một iterator trỏ đến phần tử đầu tiên có khóa không nhỏ hơn key. Trong trường hợp khóa tồn tại, đây là iterator đến phần tử đầu tiên của nhóm các phần tử có khóa đó.
• upper_bound(key): Trả về một iterator trỏ đến phần tử đầu tiên có khóa lớn hơn key. Trong trường hợp khóa tồn tại, đây là iterator đến phần tử ngay sau nhóm các phần tử có khóa đó.
• equal_range(key): Đây là hàm mạnh mẽ nhất cho multimap. Nó trả về một cặp (pair) iterator xác định phạm vi (range) của tất cả các phần tử có khóa key. Cặp này là {lower_bound(key), upper_bound(key)}. Bạn có thể lặp qua phạm vi này để truy cập tất cả các giá trị cho khóa đó.

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

int main() {
    std::multimap<std::string, int> student_scores;

    student_scores.insert({"Alice", 95});
    student_scores.insert({"Bob", 80});
    student_scores.insert({"Alice", 88});
    student_scores.insert({"Charlie", 75});
    student_scores.insert({"Bob", 92});

    // Sử dụng count
    std::string search_key = "Alice";
    size_t num_alice = student_scores.count(search_key);
    std::cout << "\nSo luong diem cua " << search_key << ": " << num_alice << std::endl;

    std::string search_key_non_existent = "David";
    size_t num_david = student_scores.count(search_key_non_existent);
    std::cout << "So luong diem cua " << search_key_non_existent << ": " << num_david << std::endl;

    // Sử dụng find (chỉ tìm thấy phần tử đầu tiên)
    auto it_first_alice = student_scores.find(search_key);
    if (it_first_alice != student_scores.end()) {
        std::cout << "Diem dau tien cua " << search_key << ": " << it_first_alice->second << std::endl;
    } else {
        std::cout << "Khong tim thay diem nao cho " << search_key << std::endl;
    }

    // Sử dụng equal_range để tìm TẤT CẢ các giá trị cho một khóa
    std::cout << "\nTat ca diem cua " << search_key << " (su dung equal_range):\n";
    auto range = student_scores.equal_range(search_key);

    // range.first là iterator đến phần tử đầu tiên có khóa là search_key
    // range.second là iterator đến phần tử đầu tiên có khóa LỚN HƠN search_key (hoặc end())

    if (range.first == range.second) {
        std::cout << "Khong tim thay diem nao cho " << search_key << ".\n";
    } else {
        for (auto it = range.first; it != range.second; ++it) {
            std::cout << "- " << it->first << ": " << it->second << std::endl;
        }
    }

    // Ví dụ với khóa không tồn tại
    std::string search_key_non_existent_range = "David";
    std::cout << "\nTat ca diem cua " << search_key_non_existent_range << " (su dung equal_range):\n";
    auto range_david = student_scores.equal_range(search_key_non_existent_range);
     if (range_david.first == range_david.second) {
        std::cout << "Khong tim thay diem nao cho " << search_key_non_existent_range << ".\n";
    } else {
         // Vòng lặp này sẽ không chạy
        for (auto it = range_david.first; it != range_david.second; ++it) {
             std::cout << "- " << it->first << ": " << it->second << std::endl;
        }
    }


    return 0;
}

Giải thích:

• count("Alice") trả về 2 vì có hai phần tử có khóa "Alice".
• find("Alice") chỉ trả về iterator đến phần tử đầu tiên là {"Alice", 95}.
• equal_range("Alice") trả về một cặp iterator. range.first trỏ đến {"Alice", 95} và range.second trỏ đến {"Bob", 80} (phần tử đầu tiên có khóa lớn hơn "Alice"). Vòng lặp từ range.first đến range.second sẽ đi qua tất cả các phần tử có khóa "Alice".
• Khi tìm kiếm một khóa không tồn tại ("David"), count trả về 0 và equal_range trả về một cặp iterator mà cả hai đều là multimap.end(), dẫn đến range.first == range.second.

Xóa phần tử (erase)

Bạn có thể xóa phần tử theo iterator hoặc theo khóa.

• 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 key. Trả về số lượng phần tử đã xóa.

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

int main() {
    std::multimap<std::string, int> student_scores;

    student_scores.insert({"Alice", 95});
    student_scores.insert({"Bob", 80});
    student_scores.insert({"Alice", 88});
    student_scores.insert({"Charlie", 75});
    student_scores.insert({"Bob", 92});

    std::cout << "Multimap truoc khi xoa:\n";
    for (const auto& pair : student_scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // Xóa TẤT CẢ các phần tử có khóa "Bob"
    std::string key_to_erase = "Bob";
    size_t num_removed = student_scores.erase(key_to_erase);
    std::cout << "\nDa xoa " << num_removed << " phan tu voi khoa \"" << key_to_erase << "\".\n";

    std::cout << "Multimap sau khi xoa " << key_to_erase << ":\n";
    for (const auto& pair : student_scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // Xóa một phần tử cụ thể bằng iterator (ví dụ xóa điểm 88 của Alice)
    // Đầu tiên tìm phần tử đó (cẩn thận với các khóa trùng lặp)
    auto range_alice = student_scores.equal_range("Alice");
    auto it_to_remove = student_scores.end(); // Iterator mặc định không hợp lệ

    for(auto it = range_alice.first; it != range_alice.second; ++it) {
        if (it->second == 88) {
            it_to_remove = it; // Tìm thấy phần tử cần xóa
            break; // Chỉ xóa 1 phần tử khớp đầu tiên
        }
    }

    if (it_to_remove != student_scores.end()) {
        std::cout << "\nXoa diem 88 cua Alice...\n";
        student_scores.erase(it_to_remove);
    }


    std::cout << "Multimap sau khi xoa diem 88 cua Alice:\n";
    for (const auto& pair : student_scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }


    return 0;
}

Giải thích:

• erase("Bob") tìm và xóa cả hai phần tử {"Bob", 80} và {"Bob", 92}. Hàm trả về 2, là số lượng phần tử đã xóa.
• Để xóa một phần tử cụ thể khi có khóa trùng lặp, bạn cần tìm đúng iterator đến phần tử đó (ví dụ bằng cách duyệt qua phạm vi trả về bởi equal_range) và sau đó dùng erase(iterator).

Các thao tác khác

• size(): Trả về số lượng phần tử hiện có trong multimap.
• empty(): Trả về true nếu multimap rỗng, ngược lại trả về false.
• clear(): Xóa tất cả phần tử khỏi multimap.

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

int main() {
    std::multimap<std::string, int> student_scores;

    student_scores.insert({"Alice", 95});
    student_scores.insert({"Bob", 80});
    student_scores.insert({"Alice", 88});

    std::cout << "Kich thuoc hien tai cua multimap: " << student_scores.size() << std::endl;

    if (!student_scores.empty()) {
        std::cout << "Multimap khong rong.\n";
    }

    student_scores.clear();
    std::cout << "Kich thuoc sau khi clear: " << student_scores.size() << std::endl;

     if (student_scores.empty()) {
        std::cout << "Multimap da rong.\n";
    }

    return 0;
}

Ứng dụng đơn giản của std::multimap

std::multimap là lựa chọn tự nhiên cho các kịch bản cần ánh xạ một khóa đến nhiều giá trị, nơi thứ tự của khóa là quan trọng.

Ví dụ 1: Xây dựng chỉ mục từ (Word Index)

Giả sử bạn muốn tạo một chỉ mục cho một văn bản, liệt kê mỗi từ và các dòng mà nó xuất hiện. Một từ có thể xuất hiện ở nhiều dòng. std::multimap là cấu trúc dữ liệu lý tưởng: Khóa là từ (std::string), giá trị là số dòng (int).

#include <iostream>
#include <map>
#include <string>
#include <sstream> // Để xử lý dòng văn bản
#include <cctype>  // Để kiểm tra ký tự

// Hàm đơn giản để làm sạch từ (chuyển thành chữ thường, loại bỏ dấu câu)
std::string clean_word(const std::string& word) {
    std::string cleaned;
    for (char c : word) {
        if (std::isalpha(c)) { // Chỉ giữ lại chữ cái
            cleaned += std::tolower(c); // Chuyển thành chữ thường
        }
    }
    return cleaned;
}

int main() {
    std::multimap<std::string, int> word_index; // Khóa: tu, Gia tri: so dong

    std::string text =
        "This is a sample text.\n"
        "This text has sample words.\n"
        "Sample text again.";

    std::stringstream ss(text);
    std::string line;
    int line_num = 0;

    while (std::getline(ss, line)) {
        line_num++;
        std::stringstream line_stream(line);
        std::string word;
        while (line_stream >> word) {
            std::string cleaned = clean_word(word);
            if (!cleaned.empty()) {
                word_index.insert({cleaned, line_num});
            }
        }
    }

    // Hiển thị chỉ mục
    std::cout << "Chi muc tu:\n";
    // Duyệt và in ra từng từ và các dòng xuất hiện
    // Cần xử lý để không in lại từ nhiều lần, chỉ in các dòng liên quan
    auto it = word_index.begin();
    while(it != word_index.end()) {
        std::string current_word = it->first;
        std::cout << current_word << ": ";

        // Sử dụng equal_range để lấy tất cả các dòng cho từ hiện tại
        auto range = word_index.equal_range(current_word);
        bool first_line = true;
        for(auto range_it = range.first; range_it != range.second; ++range_it) {
            if (!first_line) {
                std::cout << ", ";
            }
            std::cout << range_it->second;
            first_line = false;
        }
        std::cout << std::endl;

        // Di chuyển iterator chính đến sau phạm vi của từ hiện tại
        it = range.second;
    }


    return 0;
}

Giải thích:

• Chúng ta đọc từng dòng của văn bản.
• Trên mỗi dòng, chúng ta trích xuất từng từ, làm sạch nó (loại bỏ dấu câu, chuyển về chữ thường).
• Mỗi lần tìm thấy một từ trên một dòng, chúng ta chèn cặp {từ_đã_làm_sạch, số_dòng} vào word_index. Vì cùng một từ có thể xuất hiện trên nhiều dòng hoặc nhiều lần trên cùng một dòng, chúng ta cần multimap.
• Để in chỉ mục một cách gọn gàng (mỗi từ chỉ in một lần, theo sau là danh sách các dòng), chúng ta sử dụng equal_range để lấy toàn bộ các dòng cho từ hiện tại, in chúng ra, và sau đó nhảy iterator chính đến cuối phạm vi đó để tiếp tục với từ tiếp theo.

Ví dụ 2: Lưu trữ thông tin các chuyến bay theo sân bay

Giả sử bạn cần lưu trữ danh sách các chuyến bay khởi hành từ các sân bay khác nhau. Mỗi sân bay (mã sân bay - khóa) có thể có nhiều chuyến bay (thông tin chuyến bay - giá trị).

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

int main() {
    std::multimap<std::string, std::string> airport_departures; // Khóa: Ma san bay, Gia tri: Thong tin chuyen bay

    // Them mot so chuyen bay
    airport_departures.insert({"SGN", "VN780 - 08:00"});
    airport_departures.insert({"HAN", "VJ123 - 09:30"});
    airport_departures.insert({"SGN", "BL590 - 10:15"}); // Chuyen bay khac tu SGN
    airport_departures.insert({"DAD", "QH456 - 11:00"});
    airport_departures.insert({"SGN", "VN246 - 12:00"}); // Them mot chuyen bay nua tu SGN
    airport_departures.insert({"HAN", "VN250 - 13:00"}); // Chuyen bay khac tu HAN

    std::cout << "Lich khoi hanh chuyen bay:\n";
    // In tat ca cac chuyen bay, nhom theo san bay (da duoc multimap sap xep)
     auto it = airport_departures.begin();
    while(it != airport_departures.end()) {
        std::string current_airport = it->first;
        std::cout << "San bay " << current_airport << ":\n";

        auto range = airport_departures.equal_range(current_airport);
        for(auto range_it = range.first; range_it != range.second; ++range_it) {
            std::cout << "- " << range_it->second << std::endl;
        }

        it = range.second;
    }

    std::cout << "\nTim cac chuyen bay tu SGN:\n";
    std::string search_airport = "SGN";
    auto sgn_range = airport_departures.equal_range(search_airport);
     if (sgn_range.first == sgn_range.second) {
        std::cout << "Khong co chuyen bay nao tu " << search_airport << " hom nay.\n";
    } else {
        for (auto it_sgn = sgn_range.first; it_sgn != sgn_range.second; ++it_sgn) {
            std::cout << "- " << it_sgn->second << std::endl;
        }
    }


     std::cout << "\nTim cac chuyen bay tu HPH (khong co):\n";
    std::string search_airport_non = "HPH";
    auto hph_range = airport_departures.equal_range(search_airport_non);
     if (hph_range.first == hph_range.second) {
        std::cout << "Khong co chuyen bay nao tu " << search_airport_non << " hom nay.\n";
    } else {
         // Vong lap nay se khong chay
        for (auto it_hph = hph_range.first; it_hph != hph_range.second; ++it_hph) {
            std::cout << "- " << it_hph->second << std::endl;
        }
    }


    return 0;
}

Giải thích:

• airport_departures lưu trữ mã sân bay làm khóa và chuỗi thông tin chuyến bay làm giá trị.
• Nhiều chuyến bay từ cùng một sân bay được lưu trữ dễ dàng nhờ tính năng khóa trùng lặp của multimap.
• Khi in ra lịch, chúng ta lại sử dụng kỹ thuật duyệt qua các phạm vi được trả về bởi equal_range để nhóm các chuyến bay theo sân bay.
• Khi tìm kiếm các chuyến bay từ một sân bay cụ thể, equal_range cung cấp ngay một cặp iterator chỉ đến toàn bộ các chuyến bay đó.

Khi nào nên dùng std::multimap?

Hãy cân nhắc sử dụng std::multimap khi:

1. Bạn cần lưu trữ các cặp khóa-giá trị.
2. Một khóa có thể liên kết với nhiều giá trị.
3. Bạn cần các phần tử được sắp xếp tự động theo thứ tự của khóa.
4. Hiệu suất tìm kiếm, chèn, xóa O(log n) là chấp nhận được.

Nếu bạn không cần khóa trùng lặp, hãy dùng std::map. Nếu bạn không cần thứ tự và cần hiệu suất trung bình O(1) cho các thao tác cơ bản, hãy cân nhắc std::unordered_multimap (trong header <unordered_map>).

Bài tập ví dụ:

Ngăn xếp Socola

Trong một buổi thực tập tại cửa hàng bánh kẹo, FullHouse Dev được giao nhiệm vụ quản lý một ngăn xếp các hộp socola. Với sự yêu thích bánh kẹo và lập trình, họ quyết định viết một chương trình để theo dõi việc bán và nhập hàng của cửa hàng.

Bài toán

FullHouse Dev có một ngăn xếp các hộp socola ban đầu rỗng. Trong \(N\) phút tiếp theo, một trong hai sự kiện sau có thể xảy ra:

• Hộp socola ở đỉnh ngăn xếp được bán
• Nhận một hộp socola mới từ kho và đặt lên đỉnh ngăn xếp

Nhiệm vụ của họ là xác định số lượng socola trong mỗi hộp được bán.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(N\) - số phút.
• Dòng thứ hai chứa mảng \(C\) mô tả các sự kiện:
  • Nếu \(C[i] = 0\), hộp socola được bán
  • Nếu \(C[i] > 0\), nhận hộp mới chứa \(C[i]\) socola

OUTPUT FORMAT:

• In ra một mảng chứa số lượng socola trong mỗi hộp được bán, theo thứ tự bán ra.

Ràng buộc:

• \(1 \leq N \leq 10^5\)
• \(0 \leq C[i] \leq 10^9\)

Ví dụ

INPUT

4
2 1 0 0

OUTPUT

1 2

Giải thích

• Sau hai phút đầu, ngăn xếp có hai hộp [1, 2] (từ đỉnh xuống đáy)
• Phút thứ ba, hộp chứa 1 socola được bán
• Phút thứ tư, hộp chứa 2 socola được bán

Ví dụ khác

INPUT

3
5 0 5

OUTPUT

5

Giải thích

• Sau phút đầu tiên, ngăn xếp có một hộp [5]
• Phút thứ hai, hộp chứa 5 socola được bán
• Phút thứ ba, nhận thêm một hộp mới chứa 5 socola Đây là hướng dẫn giải bài "Ngăn xếp Socola" bằng C++ một cách ngắn gọn:

1. Cấu trúc dữ liệu: Bài toán mô phỏng hoạt động bán và nhập hàng theo nguyên tắc "vào sau ra trước" (Last-In, First-Out - LIFO). Đây chính là đặc điểm của ngăn xếp (stack).

2. Cách triển khai trong C++: Sử dụng std::stack trong thư viện <stack>. Kiểu dữ liệu cho các phần tử trong stack nên là int hoặc long long để chứa số lượng socola (C[i]).

3. Lưu trữ kết quả: Cần một nơi để lưu trữ số lượng socola của các hộp được bán. Sử dụng std::vector trong thư viện <vector> để làm điều này, vì chúng ta cần lưu trữ các giá trị theo thứ tự bán ra.

4. Xử lý các sự kiện:

   • Duyệt qua mảng sự kiện C từ trái sang phải.
   • Nếu C[i] > 0: Đây là sự kiện nhập hàng. Đẩy (push) giá trị C[i] vào ngăn xếp.
   • Nếu C[i] = 0: Đây là sự kiện bán hàng.
     • Lấy giá trị ở đỉnh ngăn xếp (sử dụng stack.top()).
     • Thêm giá trị này vào cuối vector kết quả.
     • Loại bỏ phần tử đỉnh khỏi ngăn xếp (sử dụng stack.pop()). (Giả định rằng thao tác bán chỉ xảy ra khi ngăn xếp không rỗng, theo logic của bài toán).

5. Xuất kết quả: Sau khi xử lý hết tất cả N sự kiện, in ra các phần tử trong vector kết quả theo thứ tự, cách nhau bởi dấu cách.

Làm thêm nhiều bài tập miễn phí tại đây