[STL] So sánh giữa Map và Unordered Map trong C++

Trong ngôn ngữ lập trình C++, STL (Standard Template Library) cung cấp một loạt các cấu trúc dữ liệu và thuật toán tiêu chuẩn để giúp lập trình viên giải quyết các vấn đề phức tạp một cách dễ dàng và hiệu quả.

Trong phạm vi của STL, Map và Unordered Map là hai cấu trúc dữ liệu phổ biến được sử dụng để lưu trữ các cặp key-value. Tuy nhiên, mỗi loại lại có những ưu điểm và nhược điểm riêng. Trong bài viết này, mình sẽ đi vào sâu hơn để so sánh giữa chúng và hiểu rõ hơn về cách sử dụng và lựa chọn phù hợp cho từng tình huống cụ thể.

Map trong C++

Định nghĩa và tính chất của Map:

• Map trong C++ là một container được sử dụng để lưu trữ các cặp key-value, trong đó mỗi key là duy nhất và được sắp xếp theo thứ tự tăng dần.
• Dữ liệu trong Map được tổ chức dưới dạng cây nhị phân tìm kiếm (binary search tree), giúp cho việc tìm kiếm và truy cập các phần tử có hiệu suất cao.
• Map hỗ trợ các phương thức như insert, erase và find để thực hiện các thao tác thêm, xóa và truy vấn phần tử.

Ưu điểm của Map:

Bài viết này được đăng tại [free tuts .net]

• Dữ liệu được sắp xếp: Map duy trì thứ tự của các phần tử theo key, giúp cho việc tìm kiếm và duyệt dữ liệu một cách hiệu quả.
• Hiệu suất tìm kiếm cao: Do dữ liệu được tổ chức dưới dạng cây nhị phân tìm kiếm, nên việc tìm kiếm các phần tử trong Map có độ phức tạp thời gian là O(log n).
• Hỗ trợ các phương thức tiện ích: Map cung cấp các phương thức như insert, erase và find để thực hiện các thao tác với dữ liệu một cách dễ dàng.

Nhược điểm của Map:

• Chiếm dụng bộ nhớ lớn: Do Map duy trì thứ tự của các phần tử, nên yêu cầu một lượng bộ nhớ lớn hơn so với các cấu trúc dữ liệu không sắp xếp.
• Thời gian thực hiện các thao tác thêm và xóa không hiệu quả: Thời gian thực hiện các thao tác thêm và xóa phần tử trong Map có thể lâu hơn so với các cấu trúc dữ liệu khác, đặc biệt là khi cần phải di chuyển các phần tử.

Ví dụ Map trong C++

#include <iostream>
#include <map>

int main() {
    // Khai báo một map lưu trữ <int, char>
    std::map<int, char> myMap;

    // Thêm các cặp key-value vào map
    myMap[1] = 'a';
    myMap[2] = 'b';
    myMap[3] = 'c';
   //Bài được đăng tại freetuts.net

    // Truy cập các phần tử trong map
    std::cout << "Map: ";
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << "{" << it->first << ": " << it->second << "} ";
    }
    std::cout << std::endl;

    return 0;
}

Kết quả:

Unordered Map trong C++

Định nghĩa và tính chất của Unordered Map:

• Unordered Map trong C++ là một container được sử dụng để lưu trữ các cặp key-value, trong đó không đảm bảo thứ tự của các phần tử.
• Dữ liệu trong Unordered Map được tổ chức dưới dạng bảng băm (hash table), giúp cho việc tìm kiếm và truy cập các phần tử với độ phức tạp thời gian trung bình là O(1).
• Unordered Map hỗ trợ các phương thức như insert, erase và find để thực hiện các thao tác thêm, xóa và truy vấn phần tử.

Ưu điểm của Unordered Map:

• Tốc độ truy cập nhanh: Do dữ liệu được tổ chức dưới dạng bảng băm, nên việc truy cập các phần tử trong Unordered Map có độ phức tạp thời gian trung bình là O(1).
• Dữ liệu không cần sắp xếp: Unordered Map không duy trì thứ tự của các phần tử, giúp tiết kiệm bộ nhớ và tăng hiệu suất trong việc thêm và xóa phần tử.

Nhược điểm của Unordered Map:

• Không sắp xếp: Do Unordered Map không duy trì thứ tự của các phần tử, nên không thể sử dụng cho các tình huống cần dữ liệu được sắp xếp.
• Tốn bộ nhớ: Unordered Map cần một lượng bộ nhớ phụ để

Ví dụ Unordered Map trong C++

#include <iostream>
#include <unordered_map>

int main() {
    // Khai báo một unordered_map lưu trữ <int, char>
    std::unordered_map<int, char> myUnorderedMap;

    // Thêm các cặp key-value vào unordered_map
    myUnorderedMap[1] = 'a';
    myUnorderedMap[2] = 'b';
    myUnorderedMap[3] = 'c';
    //Bài được đăng tại freetuts.net

    // Truy cập các phần tử trong unordered_map
    std::cout << "Unordered Map: ";
    for (auto& pair : myUnorderedMap) {
        std::cout << "{" << pair.first << ": " << pair.second << "} ";
    }
    std::cout << std::endl;

    return 0;
}

Kết quả:

So sánh giữa Map và Unordered Map trong C++

Độ phức tạp thời gian và không gian

Map:

• Độ phức tạp thời gian: Thao tác tìm kiếm, thêm và xóa phần tử trong Map có độ phức tạp thời gian trung bình là O(log n), trong đó n là số lượng phần tử trong Map. Độ phức tạp không gian của Map là O(n).

Unordered Map:

• Độ phức tạp thời gian: Thao tác tìm kiếm, thêm và xóa phần tử trong Unordered Map có độ phức tạp thời gian trung bình là O(1) trong trường hợp trung bình, nhưng có thể là O(n) trong trường hợp xấu nhất. Độ phức tạp không gian của Unordered Map cũng là O(n), nhưng có thể cao hơn một chút so với Map do sử dụng bảng băm.

Ví dụ:

#include <iostream>
#include <map>
#include <unordered_map>

int main() {
    // Map
    std::map<int, int> myMap;
    for (int i = 0; i < 1000000; ++i) {
        myMap[i] = i;
    }
   //freetuts.net

    // Unordered Map
    std::unordered_map<int, int> myUnorderedMap;
    for (int i = 0; i < 1000000; ++i) {
        myUnorderedMap[i] = i;
    }

    return 0;
}

Tốc độ truy cập và tìm kiếm

Map:

• Tốc độ truy cập và tìm kiếm trong Map tốt, nhưng không bằng Unordered Map trong trường hợp trung bình.

Unordered Map:

• Tốc độ truy cập và tìm kiếm trong Unordered Map nhanh chóng, đặc biệt là trong trường hợp trung bình khi sử dụng bảng băm để tổ chức dữ liệu.

Ví dụ:

#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>

int main() {
    std::map<int, int> myMap;
    std::unordered_map<int, int> myUnorderedMap;

    // Đo thời gian truy cập phần tử trong Map
    auto startMap = std::chrono::steady_clock::now();
    for (int i = 0; i < 1000000; ++i) {
        myMap[i];
    }
    auto endMap = std::chrono::steady_clock::now();
    std::cout << "Time taken for Map: " << std::chrono::duration_cast<std::chrono::milliseconds>(endMap - startMap).count() << " ms" << std::endl;
    //Bài được đăng tại freetuts.net

    // Đo thời gian truy cập phần tử trong Unordered Map
    auto startUnorderedMap = std::chrono::steady_clock::now();
    for (int i = 0; i < 1000000; ++i) {
        myUnorderedMap[i];
    }
    auto endUnorderedMap = std::chrono::steady_clock::now();
    std::cout << "Time taken for Unordered Map: " << std::chrono::duration_cast<std::chrono::milliseconds>(endUnorderedMap - startUnorderedMap).count() << " ms" << std::endl;

    return 0;
}

Kết quả:

Thêm và xóa phần tử

Map:

• Thêm và xóa phần tử trong Map có thể mất thời gian hơn so với Unordered Map, đặc biệt là trong trường hợp cần di chuyển các phần tử khi thêm hoặc xóa.

Unordered Map:

• Thêm và xóa phần tử trong Unordered Map nhanh chóng và hiệu quả, đặc biệt là trong trường hợp trung bình khi sử dụng bảng băm.

Ví dụ:

#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>

int main() {
    // Map
    std::map<int, int> myMap;
    auto startMapInsert = std::chrono::steady_clock::now

Ví dụ thực hành Map và Unordered Map trong C++

Ví dụ về sử dụng Map trong C++:

#include <iostream>
#include <map>

int main() {
    // Khai báo và khởi tạo một map lưu trữ <int, std::string>
    std::map<int, std::string> myMap = {
        {1, "apple"},
        {2, "banana"},
        {3, "orange"}
    };

    // Truy cập và hiển thị giá trị của các phần tử trong map
    std::cout << "Map: ";
    for (const auto& pair : myMap) {
        std::cout << "{" << pair.first << ": " << pair.second << "} ";
    }
    std::cout << std::endl;
    //Bài được đăng tại freetuts.net

    // Tìm kiếm và hiển thị giá trị của phần tử có key = 2
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Value of key 2: " << it->second << std::endl;
    }

    return 0;
}

Kết quả:

Ví dụ về sử dụng Unordered Map trong C++:

#include <iostream>
#include <unordered_map>

int main() {
    // Khai báo và khởi tạo một unordered_map lưu trữ <int, std::string>
    std::unordered_map<int, std::string> myUnorderedMap = {
        {1, "apple"},
        {2, "banana"},
        {3, "orange"}
    };

    // Truy cập và hiển thị giá trị của các phần tử trong unordered_map
    std::cout << "Unordered Map: ";
    for (const auto& pair : myUnorderedMap) {
        std::cout << "{" << pair.first << ": " << pair.second << "} ";
    }
    std::cout << std::endl;

    // Tìm kiếm và hiển thị giá trị của phần tử có key = 2
    auto it = myUnorderedMap.find(2);
    if (it != myUnorderedMap.end()) {
        std::cout << "Value of key 2: " << it->second << std::endl;
    }
     //Bài được đăng tại freetuts.net

    return 0;
}

Kết quả:

Trong cả hai ví dụ trên, mình sử dụng Map và Unordered Map để lưu trữ các cặp key-value và thực hiện các thao tác như truy cập và tìm kiếm. Bằng cách này, mình có thể thấy cách sử dụng và tính linh hoạt của hai cấu trúc dữ liệu này trong STL của C++.

Kết bài

Tùy thuộc vào yêu cầu và đặc điểm của từng vấn đề cụ thể, việc lựa chọn giữa Map và Unordered Map sẽ có sự ảnh hưởng đáng kể đến hiệu suất và tiện ích của chương trình. Hi vọng rằng bài viết này đã cung cấp cho bạn cái nhìn tổng quan và chi tiết về sự khác biệt giữa hai cấu trúc dữ liệu quan trọng này trong STL của C++.