C++ - The Difference Between Map and HashMap in STL

Written by: Manish Methani

September 8, 2021 at 8:04am IST. 7 min 28 sec

Table of Contents:

In C++, the Standard Template Library (STL) provides two common data structures for associative containers: std::map and std::unordered_map (often referred to as HashMap). These containers allow you to store key-value pairs and efficiently retrieve values based on their keys. In this article, we will explore the differences between std::map and std::unordered_map and provide example code to illustrate their usage.

Step 1: Include the Necessary Headers

Before we delve into the code examples, make sure to include the required headers:

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

Step 2: Use std::map for Ordered Key-Value Storage

std::map is an ordered associative container. It stores key-value pairs where the keys are unique, and they are sorted in ascending order. Here's how you can declare and use a std::map:

std::map myMap;

// Insert key-value pairs
myMap[1] = "One";
myMap[3] = "Three";
myMap[2] = "Two";

// Access values using keys
std::cout << myMap[2] << std::endl;  // Output: "Two"

Step 3: Use std::unordered_map (HashMap) for Fast Retrieval

std::unordered_map, often referred to as HashMap, is an unordered associative container. It also stores unique key-value pairs, but it does not maintain any specific order. Instead, it uses hashing for fast retrieval. Here's an example of using std::unordered_map:

std::unordered_map myHashMap;

// Insert key-value pairs
myHashMap["One"] = 1;
myHashMap["Three"] = 3;
myHashMap["Two"] = 2;

// Access values using keys
std::cout << myHashMap["Two"] << std::endl;  // Output: 2

Step 4: Key Differences

Now, let's discuss the key differences between std::map and std::unordered_map:

• Order: std::map maintains the order of key-value pairs based on the keys, while std::unordered_map does not guarantee any specific order.

• Performance: std::map has O(log N) time complexity for key retrieval, making it suitable for situations where you need ordered access. std::unordered_map has O(1) average time complexity for key retrieval, making it faster for unordered access.

• Storage: std::map may consume more memory due to the order it maintains. std::unordered_map may use less memory but could have slightly higher overhead due to hashing.

Full Example Code

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

int main() {
    // Creating a std::map
    std::map mapContainer;
    
    // Inserting key-value pairs into the map
    mapContainer[1] = "Apple";
    mapContainer[3] = "Banana";
    mapContainer[2] = "Orange";
    mapContainer[4] = "Grapes";
    
    // Iterating and printing the std::map
    std::cout << "std::map (Ordered):" << std::endl;
    for (const auto& pair : mapContainer) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    // Creating a std::unordered_map (HashMap)
    std::unordered_map unorderedMapContainer;

    // Inserting key-value pairs into the unordered_map
    unorderedMapContainer[1] = "Apple";
    unorderedMapContainer[3] = "Banana";
    unorderedMapContainer[2] = "Orange";
    unorderedMapContainer[4] = "Grapes";

    // Iterating and printing the std::unordered_map (HashMap)
    std::cout << "
std::unordered_map (HashMap):" << std::endl;
    for (const auto& pair : unorderedMapContainer) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    return 0;
}

Output

std::map (Ordered):
Key: 1, Value: Apple
Key: 2, Value: Orange
Key: 3, Value: Banana
Key: 4, Value: Grapes

std::unordered_map (HashMap):
Key: 4, Value: Grapes
Key: 2, Value: Orange
Key: 3, Value: Banana
Key: 1, Value: Apple

In this code, we first create a std::map and a std::unordered_map (HashMap) and insert key-value pairs into both containers. Then, we iterate through each container and print the key-value pairs. The std::map preserves the order of insertion, while the std::unordered_map (HashMap) does not guarantee any specific order.

This example demonstrates the difference in ordering between the two containers, showcasing the primary distinction between std::map and std::unordered_map in C++.

Conclusion

In C++, std::map and std::unordered_map (HashMap) serve as valuable tools for associative containers, each with its unique characteristics. The choice between them depends on the specific requirements of your program, whether you prioritize order or fast retrieval. Understanding these differences allows you to make an informed decision when selecting the appropriate container for your task.

By using std::map or std::unordered_map, you can efficiently manage key-value data and enhance the performance of your C++ applications.