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.

FAQ

1. What is the primary difference between std::map and std::unordered_map in C++?

Answer:

The primary difference lies in the order and retrieval performance. `std::map` maintains ordered key-value pairs and offers O(log N) time complexity for retrieval. `std::unordered_map` (HashMap) does not guarantee order and provides faster O(1) average retrieval times due to hashing.

2. When should I use std::map in C++?

Answer:

Use `std::map` when you require ordered key-value storage, and the specific order of elements matters for your application. It is suitable for situations where you need to iterate through key-value pairs in ascending order.

3. When is std::unordered_map (HashMap) a better choice in C++?

Answer:

Choose `std::unordered_map` when order is not essential, and you prioritize fast key retrieval. It is an excellent choice for situations where you need quick access to values based on their keys but dont require a specific order.

4. Does the choice between std::map and std::unordered_map affect memory usage?

Answer:

Yes, the choice can impact memory usage. `std::map` may consume more memory due to its ordered structure, while `std::unordered_map` may use less memory but could have slightly higher overhead due to hashing. Consider your memory constraints when selecting the container.

5. Why does std::unordered_map provide an equal_range member function?

Answer:

`std::unordered_map` provides an `equal_range` member function for several reasons:

  1. Efficiency: `std::unordered_map` is implemented as a hash table, which allows for fast constant-time average complexity for various operations. The `equal_range` function can be implemented efficiently for hash-based containers to locate all elements with the same key. It is faster than iterating over the entire container manually.
  2. Consistency: C++ Standard Library containers, including `std::unordered_map`, strive to provide a consistent and familiar interface. Other associative containers like `std::multimap` and `std::map` also have an `equal_range` member function. This consistency simplifies code migration and usage for developers.
  3. Simplifying Code: The `equal_range` function can simplify code that needs to work with a range of elements associated with a specific key. It allows developers to find all elements with the same key in a more concise and readable manner.
  4. Performance Benefits: For scenarios where you need to find all elements with the same key, using `equal_range` can be more efficient than separate `find` and iteration operations. It can help avoid multiple lookups and achieve better performance.
  5. Range Semantics: The `equal_range` function returns a pair of iterators pointing to the range of elements associated with a specific key. This is particularly useful when you want to perform operations on all such elements as a group.
In summary, `std::unordered_map` provides the `equal_range` member function to offer efficient, consistent, and simplified access to elements with the same key in the container. This feature is valuable for developers working with hash-based containers to ensure optimal performance and code clarity.

Discover My FlutterFlow Courses and Template Apps

Launch Your Dating App with FlutterFlow: Course + Template
Master FlutterFlow and Build Your Dating App with Our Step-by-Step Course and Ready-Made Template.
Launch Your Grocery Delivery App with FlutterFlow: Course + Template
Master FlutterFlow and Build Your Grocery Delivery App with Our Step-by-Step Course and Ready-Made Template.
Launch Your Courses App with FlutterFlow: Course + Template
Master FlutterFlow and Build Your Courses App with Our Step-by-Step Course and Ready-Made Template.
Codzify Logo

Terms and Conditions    Cookie Policy   Refund Policy   Adsense Disclaimer

Contact: teamcodzify@gmail.com