HOME › lập trình c++ cơ bản dành cho người mới học lập trình>>25. multimap trong c++

Multimap trong C++ là gì

20 tháng 1 ,2022

Cùng tìm hiểu về kiểu multimap trong C++. Bạn sẽ biết khái niệm multimap trong c++ là gì, cách khai báo multimap trong C++, cách khởi tạo multimap trong C++, cách truy cập phần tử của multimap, cũng như sự khác biệt giữa list và multimap trong C++ sau bài học này.

Multimap trong c++ là gì

Multimap trong C++ là một tập hợp các phần tử được sắp xếp theo thứ tự cụ thể, với mỗi phần tử được hình thành bởi sự kết hợp của một cặp khóa và giá trị (key & value), trong đó nhiều phần tử có thể có các khóa giống nhau.

Trong multimap, các khóa (key) được sử dụng để sắp xếp và xác định các giá trị (value) tương ứng được liên kết với nó. Mỗi khóa trong multimap được phép trùng lặp khiến nhiều phần tử có thể có các khóa tương đương. Do vậy, một khóa trong multimap có thể dùng để xác định nhiều giá trị được liên kết với nó.

Về mặt nội bộ, các phần tử trong multimap luôn được sắp xếp theo khóa của nó theo thứ tự cụ thể một cách nghiêm ngặt, được chỉ ra bởi đối tượng so sánh nội bộ của multimap. Nếu bạn thêm các phần tử mới không theo thứ tự cụ thể vào một multimap, chúng sẽ tự động sắp xếp lại theo khóa trước khi được lưu trữ nội bộ.

Trong C++ cũng có một loại dữ liệu khá giống với multimap là map khi các phần tử cũng được hình thành bởi các cặp khóa và giá trị. Tuy nhiên thì khác với map không cho phép các khóa trùng lặp thì trong một multimap nhiều phần tử có thể có các khóa giống nhau.

Về mặt tốc độ xử lý thì multimap được cho là chậm hơn unordered_map khi cần truy cập vào một phần tử ngẫu nhiên, nhưng lại nhanh hơn unordered_map trong việc thực thi các trình lặp trỏ tới chúng.

Cấu trúc dữ liệu multimap trong c++

Tương tự như kiểu map thì cấu trúc dữ liệu multimap trong C++ thuộc dạng Red–black tree (cây đỏ đen) - một cây nhị phân, là một cấu trúc dữ liệu trong khoa học máy tính để tổ chức các thành phần dữ liệu có thể so sánh.

Cụ thể thì cấu trúc dữ liệu multimap trong C++ có được thể hiện như ví dụ dưới đây. Lưu ý là cấu trúc này có thể khác một chút so với thực tế cấu trúc trong môi trường máy của bạn.

Chúng ta cần đặc biệt lưu ý 3 điểm sau đây về Cấu trúc dữ liệu multimap trong c++:

Trong các Node sẽ lưu giữ cặp khóa:giá trị (key & value) cũng như con trỏ của các Node con (trái, phải) của nó.
Các giá trị trong Node thỏa mãn điều kiện giá trị của Node con bên trái <= Giá trị Node cha <= Giá trị của Node con bên phải. Do trong multimap cho phép khóa trùng nhau nên dấu <= được sử dụng.
Độ sâu của các Node bằng nhau và cây Node thì cân bằng.

Nhờ vào cấu trúc dữ liệu kiểu này mà chúng ta có thể tìm kiếm nhị phân trong multimap, qua đó có thể tìm kiếm trong multimap với tốc độ cao O(Log N).

std::multimap trong C++

std::multimap trong C++ là một thư viện chuẩn được sử dụng để xử lý multimap trong C++.

Giống như std::map thì std::multimap được cài sẵn trong header file map và để sử dụng được chức năng này, chúng ta cần thêm dòng #include <map> vào đầu chương trình.

Cần đặc biệt lưu ý ở đây là #include <map> chứ không phải là #include <map> .Khác với các container khác vốn có header file riêng biệt để quản lý thì multimap lại dùng chung header file với map.

#include <map>   
int main()
{
    std::multimap<std::string, int> mp; 
    std::multimap<char, double> mp2;   
}

Lại nữa, namespace của std::multimap là std, do đó bằng cách khai báo sử dụng namespace này vào đầu chương trình mà chúng ta có thể viết gọn std::multimap trong chương trình như sau:

#include <map>   
using namespace std;
int main()
{
    multimap<string, int> mp; 
    multimap<char, double> mp2; 
}

Khai báo multimap trong C++

Khai báo 1 multimap trong C++

Để khai báo multimap trong C++, chúng ta viết dòng std::multimap, sau đó viết kiểu dữ liệu của key và value cách nhau bởi dấu phẩy ở giữa cặp dấu <>, và cuối cùng là tên biến multimap như sau:

std::multimap<k_type, v_type> mp;

Trong đó mp là tên biến multimap và k_type, v_type lần lượt là kiểu dữ liệu của key và value. Cách viết sử dụng cặp dấu <> như trên được viết theo cú pháp khi sử dụng chức năng template của C++ mà chúng ta sẽ cùng học trong các chuyên đề sau.

Chúng ta có thể dùng bất cứ kiểu dữ liệu nào có trong C++ để khai báo type, ví dụ như char, int, double, hay cấu trúc hoặc class tự tạo chẳng hạn.

Lưu ý, mặc dù chúng ta có thể dùng bất cứ kiểu dữ liệu nào có trong C++ để khai báo type, tuy nhiên do trong multimap các phần tử cần phải được sắp xếp, nên kiểu của chúng cũng phải là kiểu dữ liệu có thể được so sánh.

Đối với các kiểu dữ liệu nguyên thủy như char, int, double chẳng hạn thì chúng vốn có thể tự so sánh được, nhưng nếu chúng ta sử dụng các kiểu dữ liệu không phải là kiểu dữ liệu nguyên thủy, ví dụ như cấu trúc hoặc class tự tạo chẳng hạn, thì bắt buộc phải tự định nghĩa toán tử so sánh nội bộ operator<() để làm rõ quan hệ lớn nhỏ giữa chúng.

Lại nữa, trong trường hợp đã khai báo namespace std vào đầu chương trình, chúng ta cũng có thể lược bỏ dòng std:: và dùng cú pháp khai báo multimap như sau:

using namespace std;
multimap<k_type, v_type> mp;

Thông thường chúng ta hay khai báo namespace std vào đầu chương trình để sử dụng tới các chức năng thông dụng khác như nhập xuất chẳng hạn, nên trong 2 phương pháp khai báo multimap ở trên thì phương pháp thứ 2 thường được sử dụng nhiều hơn.

Lưu ý multimap được khai báo với cú pháp này sẽ có 0 phần tử bên trong nó. Sau khi khai báo multimap kiểu này, chúng ta có thể sử dụng các hàm thành viên để có thể thêm phần tử vào nó sau này.

Ví dụ cụ thể, chúng ta khai báo 1 multimap thuộc kiểu dữ liệu nguyên thủy như sau:

#include <iostream>
#include <map>   
using namespace std;

int main()
{
    multimap<double, string> user; 
    multimap<int, char> info;    
}

Còn khi khai báo 1 multimap không thuộc kiểu dữ liệu nguyên thủy, ví dụ như struct chẳng hạn thì chúng ta phải tự tạo ra toán tử so sánh nội bộ operator<() để làm rõ quan hệ lớn nhỏ giữa các phần tử như ví dụ sau:

struct Person {
    string m_name;
    int    m_height;
};
// Định nghĩa toán tử so sánh nội bộ của struct
bool operator<(const Person &lhs, const Person &rhs)
{
    return lhs.m_name < rhs.m_name;
}

/*Khai báo multimap thuộc kiểu struct*/
std::multimap<Person, int> mp;

Khai báo đồng thời nhiều multimap trong C++

Trong trường hợp cần khai báo đồng thời nhiều multimap trong C++, chúng ta viết các tên các biến cách nhau bởi dấu phẩy vào đằng sau std::multimap với cú pháp sau đây:

using namespace std;
multimap<k_type, v_type> name1, name2, name3, ... ;

Ví dụ cụ thể:

#include <iostream>
#include <map>   
using namespace std;

int main()
{
    multimap<string, int> name, job, sex;
    multimap<int, char> age;
}

Khởi tạo multimap trong C++

Ngoài cách khai báo rồi thêm giá trị cho multimap sau đó thì chúng ta cũng có thể khởi tạo multimap và gán luôn giá trị ban đầu cho multimap.

Chúng ta khởi tạo multimap trong C++ cách sử dụng cặp dấu ngoặc {} với cú pháp sau đây:

std::multimap<k_type, v_type> mp = { {k1, v1}, {k2, v2}, {k3, v3}, ...};

Trong đó

mp là tên biến multimap
k_type, v_type là kiểu dữ liệu của key và value
k,v là các cặp key và value

Lưu ý khác với map thì khóa trong multimap có thể trùng lặp, nên nếu chúng ta chỉ định các phần tử có cùng khóa thì tất cả chúng cũng sẽ được lưu vào map.

Ví dụ:

#include <iostream>
#include <map>
using namespace std;

int main ()
{
    multimap<string,int> mp = {
                { "alpha", 10 },
                { "alpha", 20 },
                { "beta", 20 },
                { "alpha", 10 },
                { "gamma", 30 } 
            };

    for (auto& x: mp) {
        cout << x.first << ": " << x.second << '\n';
    }
    return 0;
}

Kết quả:

alpha: 10
alpha: 20
alpha: 10
beta: 20
gamma: 30

Truy cập phần tử trong multimap C++

Khác với map thì trong multimap không tồn tại toán tử [] hoặc hàm thành viên at() giúp truy cập vào phần tử thông qua key, do đó để truy cập phần tử trong multimap C++, chúng ta cần phải sử dụng vòng lặp tuần tự bằng một trong các cách mà Kiyoshi đã hướng dẫn trong bài Duyệt multimap trong C++.

Ví dụ, chúng ta sử dụng vòng lặp dựa trên phạm vi để truy cập vào phần tử theo key trong multimap C++ như sau:

#include <iostream>
#include <map>
using namespace std;

int main ()
{
    multimap<string,int> mp = {
                { "alpha", 10 },
                { "alpha", 20 },
                { "beta", 20 },
                { "alpha", 10 },
                { "gamma", 30 } 
            };

    for (auto& x: mp) {
        if(x.first == "alpha") cout << x.first <<": " << x.second << '\n';
    }
    return 0;
}

multimap vs map, unordered_map trong c++

Trong C++ tồn tại 3 loại map gồm map, unordered_map và multimap. Ba loại map này đều có phần tử được tạo thành bởi một cặp khóa và giá trị (key & value), tuy nhiên giữa chúng có những điểm hoàn toàn khác nhau như sau:

Phần tử trong map và multimap được sắp xếp theo thứ tự, còn unordered_map thì không có thứ tự.
Phần tử trong map và multimap được lưu theo thứ tự của khóa, còn trong unordered_map thì theo thứ tự giá trị hash của khóa.
map và multimap tuân theo cấu trúc cây nhị phân Red–black tree, còn unordered_map thì theo giá trị trong bảng hash.
Key trong map và unordered_map là duy nhất, còn trong multimap thì có thể trùng nhau.

Về tốc độ xử lý thì unordered_map có tốc độ truy cập phần tử ngẫu nhiên nhanh hơn map và multimap, tuy nhiên tốc độ xử lý vòng lặp lại kém hơn so với 2 anh em của nó.

Tổng kết

Trên đây Kiyoshi đã hướng dẫn bạn về multimap trong C++ rồi. Để nắm rõ nội dung bài học hơn, bạn hãy thực hành viết lại các ví dụ của ngày hôm nay nhé.

Và hãy cùng tìm hiểu những kiến thức sâu hơn về C++ trong các bài học tiếp theo.