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

Unordered_map trong c++ là gì

Unordered_map trong C++ là một tập hợp các phần tử không có thứ tự, mà mỗi phần tử trong đó đượ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), với các khóa không được trùng nhau.

Trong unordered_map, các khóa (key) được sử dụng để xác định giá trị (value) tương ứng được liên kết với nó. Mỗi khóa trong unordered_map là duy nhất và không được phép trùng lặp. Các value trong unordered_map thì có thể trùng lặp, chúng có thể thay đổi giá trị, cũng như là được chèn hoặc xóa khỏi unordered_map.

Khác với map trong C++ với các phần tử được sắp xếp và lưu trữ theo thứ tự của các khóa, thì các phần tử trong unordered_map lại được lưu trữ dựa trên giá trị hash của khóa chứ không phải dựa trên thứ tự của các khóa.

Ở đây, giá trị hash của khóa là giá trị thu về sau khi tính toán khóa bằng một hàm hash. Còn hàm hash là giải thuật nhằm sinh ra các giá trị hash tương ứng với mỗi khối dữ liệu (có thể là một chuỗi ký tự, một đối tượng trong lập trình hướng đối tượng, v.v…) để phân biệt các khối dữ liệu với nhau.

Điều đó có nghĩa là giá trị chỉ định làm key trong unordered_map phải thuộc kiểu giá trị có thể được hash bằng hàm hash.

Về mặt tốc độ xử lý thì unordered_map có khả năng truy cập vào các phần tử riêng lẻ nhanh hơn so với map, tuy nhiên thì việc lặp trên một phạm vi trong đó thì lại chậm hơn map.

Tuy nhiên thì trong unordered_map các phần tử không được sắp xếp sẵn, nên để xử lý một số lượng phần tử không quá lớn thì chúng ta chỉ cần dùng tới map là đủ rồi.

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

Khác với map hay multimap vốn có cấu trúc dữ liệu unordered_map trong C++ thuộc dạng Red–black tree (cây đỏ đen), thì cấu trúc dữ liệu của unordered_map trong c++ lại hoàn toàn khác.

Nó dựa vào hash table- một bảng hash chứa các giá trị đã được hash để so sánh các key của phần tử, và quyết định thứ tự lưu giữ các phần tử này bên trong nó.

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

1. Khác với vector thì unordered_map không dựa vào index mà dựa vào key để truy cập phần tử.
2. Các phần tử trong unordered_map được lưu vào dựa vào giá trị sau khi đã hash của các key, chứ không phải là được sắp xếp theo giá trị của key.
3. Giống với map thì key trong unordered_map là duy nhất và một key chỉ có thể dùng để xác định một giá trị duy nhất mà thôi.

Và cũng nhờ việc phần tử trong unordered_map được lưu giữ theo giá trị hash của key mà chúng ta có thể truy cập vào phần tử riêng lẻ trong nó với tốc độ tức thì O(1).

std::unordered_map trong C++

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

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

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

Lại nữa, namespace của std::unordered_map 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::unordered_map trong chương trình như sau:

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

Khai báo unordered_map trong C++

Khai báo 1 unordered_map trong C++

Để khai báo unordered_map trong C++, chúng ta viết dòng std::unordered_map, 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 unordered_map như sau:

Trong đó mp là tên biến unordered_map 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.

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

Tuy nhiên đối với kiểu của key, chúng ta chỉ có thể chỉ định các kiểu dữ liệu có khả năng được hash bởi hash function mà thôi. Ví dụ như các kiểu dữ liệu nguyên thủy thuộc kiểu số, kiểu chữ, hoặc là con trỏ chẳng hạn.

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 thêm vào đối số thứ ba, là một hàm hash sử dụng để hash các dữ liệu này.

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 unordered_map như sau:

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 unordered_map ở trên thì phương pháp thứ 2 thường được sử dụng nhiều hơn.

Lưu ý unordered_map đượ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 unordered_map 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 unordered_map thuộc kiểu dữ liệu nguyên thủy như sau:

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

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

Còn khi khai báo 1 unordered_map 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 thêm vào đối số thú 3 là hash function như ví dụ sau:

class HashVI {  // Hàm hash object
public:
    size_t operator()(const vector<int> &x) const {
        const int C = 997;  
        size_t t = 0;
        for (int i = 0; i != x.size(); ++i) {
            t = t * C + x[i];
        }
        return t;
    }
};


std::unordered_map<vector<int>, int, HashVI> mp2;

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

Trong trường hợp cần khai báo đồng thời nhiều unordered_map 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::unordered_map với cú pháp sau đây:

Ví dụ cụ thể:

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

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

Gán giá trị cho unordered_map trong C++

Sau khi đã khai báo unordered_map, chúng ta có thể gán giá trị các phần tử vào nó bằng cách sử dụng toán tử [] với cú pháp sau đây:

Trong đó

• mp là tên biến unordered_map
• key và value là khóa và giá trị của phần tử cần gán vào unordered_map

Ví dụ:

std::unordered_map<std::string, int> mp; 
mp["Kiyoshi"] = 1; // {"Kiyoshi", 1}
mp["Honda"] = 2;   // {"Honda", 2}
mp["Suzuki"] = 3;  // {"Suzuki", 3}

Lại nữa, giá trị của phần tử có thể được ghi đè và thay thế bởi một giá trị mới nhiều lần như sau:

mp["Kiyoshi"] = 4; // {"Kiyoshi", 4}
mp["Kiyoshi"] = 8; // {"Kiyoshi", 8}
mp["Kiyoshi"] = 88;// {"Kiyoshi", 88}

Trong trường hợp thay đổi giá trị nhiều lần, thì giá trị trong lượt thay đổi giá trị cuối cùng sẽ được sử dụng làm giá trị phần tử.

Khởi tạo unordered_map trong C++

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

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

Trong đó

• mp là tên biến unordered_map
• 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 ý do mỗi khóa trong unordered_map là duy nhất, nên nếu chúng ta chỉ định các phần tử có cùng khóa thì dù giá trị của chúng có giống hay khác nhau thì chỉ có duy nhất phần tử viết đầu tiên sẽ được lưu vào trong unordered_map mà thôi.

Ví dụ:

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

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

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

Kết quả:

gamma: 30
beta: 20
alpha: 10

Trong trường hợp chỉ định các phần tử có khóa giống nhau, bất kể giá trị của chúng có giống hay khác nhau thì chỉ có duy nhất phần tử viết đầu tiên được lưu vào unordered_map như sau:

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

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

    for (auto x: mp) {
        cout << x.first << ": " << x.second << endl;
    }    
    
    return 0;
}
// beta: 20
// gamma: 30
// alpha: 20

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

Để truy cập phần tử trong unordered_map C++, chúng ta sử dụng toán tử [] hoặc hàm thành viên at() như sau:

Truy cập phần tử trong unordered_map C++ bằng toán tử []

Để truy cập phần tử trong unordered_map C++, chúng ta viết key của phần tử cần truy cập vào giữa cặp toán tử [] với cú pháp sau đây:

Trong đó

• mp là tên biến unordered_map
• key là khóa của phần tử cần truy cập trong unordered_map

Nếu như key tồn tại trong unordered_map, giá trị tương ứng của key sẽ được trả về. Tuy nhiên nếu không tồn tại, giá trị 0 sẽ được trả về

Ví dụ, chúng ta có thể truy cập và xuất giá trị của một phần tử trong unordered_map như sau:

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

int main ()
{
    /*Khai báo và gán giá trị*/
    unordered_map<string, int> mp; 
    mp["Kiyoshi"] = 1; // {"Kiyoshi", 1}
    mp["Honda"] = 2;   // {"Honda", 2}
    mp["Suzuki"] = 3;  // {"Suzuki", 3}

    /*Truy cập vào phần tử vừa gán bằng key*/
    cout << mp["Kiyoshi"] ;   //1
    
    /*Truy cập vào phần tử không tồn tại trong unordered_map*/
    cout << mp["Honda"];       //0
    
    return 0;
}

Ngoài việc xuất giá trị, chúng ta cũng có thể thay đổi giá trị của một phần tử trong unordered_map với cách này. Ví dụ:

/*Khai báo và gán giá trị*/
std::unordered_map<std::string, int> mp; 
mp["Kiyoshi"] = 1;

/*Truy cập và thay đổi giá trị*/
mp["Kiyoshi"] = 2;

Truy cập phần tử trong unordered_map C++ bằng hàm at()

Hàm at() trong C++ là một hàm thành viên trong class std:unordered_map, có tác dụng truy cập vào phần tử trong unordered_map thông qua key của nó.

Nếu như key tồn tại trong unordered_map, giá trị tương ứng của key sẽ được trả về. Tuy nhiên nếu không tồn tại, hàm at() sẽ trả về lỗi out_of_range.

Cú pháp truy cập phần tử trong unordered_map C++ bằng hàm at() trong C++ như sau:

Trong đó mp là tên unordered_map và key là khóa của phần tử cần truy cập.

Ví dụ cụ thể:

/*Khai báo và gán giá trị*/
std::unordered_map<std::string, int> mp; 
mp["Kiyoshi"] = 1;


/*Truy cập vào phần tử vừa gán bằng key*/
cout << mp.at("Kiyoshi"); //1

/*Truy cập vào phần tử không tồn tại trong unordered_map*/
cout << mp.at("Honda"); // throwing an instance of 'std::out_of_range

Có thể thấy rõ sự khác biệt giữa cách truy cập phần tử trong unordered_map bằng hàm at() và toán tử [] chính là ở kết quả khi chỉ định một key không tồn tại trong unordered_map.

Unordered_map vs map, multimap 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:

1. 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ự.
2. 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.
3. 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.
4. Key trong map và unordered_map là duy nhất, còn trong multimap thì có thể trùng nhau.

Đặc biệt nếu so sánh Unordered_map vs map thì chúng ta có thể xem xét thêm các khía cạnh khác như bảng sau đây:

Tổng kết

Trên đây Kiyoshi đã hướng dẫn bạn về unordered_map 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.

URL Link

https://laptrinhcanban.com/cpp/lap-trinh-cpp-co-ban/unordered-map-trong-cpp/unordered-map-trong-cpp-la-gi/