This is the 2nd Part of Tutorial series on unordered_map. In C++, unordered_map and map are both associative containers that stores the data in a combination of key-value pairs. However, they have significant differences in their internal data structures, performance, and usage scenarios. In this tutorial, we will discuss these differences between unordered_map and map on these parameters.

Differences between Unordered_Map & Map in C++

1. Internal Data Structure

  • unordered_map:
    It uses a hash table where data is stored in an array of buckets. Each bucket contains zero or more entries. Keys are hashed to determine their bucket, and values are stored there. This structure offers quick access but does not maintain any order.
  • For Example:: Consider a phone book where you can quickly find a person’s number by their name, but the names are not in alphabetical order.

  • map: It uses a self-balancing binary search tree, like a Red-Black Tree, where each node contains a key-value pair. The tree maintains a sorted order based on the keys. This structure is great for traversing elements in sorted order but is less efficient for random access than a hash table.

  • For Example:: Think of a library catalog where books are sorted by their IDs. You can traverse through the books in ID order, but finding a book by its ID might take longer than in an unordered structure.

2. Order of Elements

  • unordered_map does not maintain any order. The order of elements depends on the internal hash function and can appear random.
  • For Example:: In a classroom, if students’ names are stored with their grades in an unordered_map, listing them will not produce any specific order.

  • map stores elements in a sorted order based on keys. This is useful for retrieving elements in a specific sequence.

  • For Example:: In a leaderboard, players’ scores stored in a map with their names as keys will list players in alphabetical order.

3. Performance

  • unordered_map offers average constant-time complexity (O(1)) for insertion, access, and deletion. This can degrade to linear time (O(n)) if there are many hash collisions.
  • For Example:: Finding a dish’s price in a fast-food restaurant menu using an unordered_map is very quick most of the time.

  • map provides logarithmic time complexity (O(log n)) for these operations, which is generally slower for large data sets.

  • For Example:: Finding a particular employee’s record in a large database of employees sorted by employee ID in a map will take longer, especially as the number of employees grows.

4. Usage Scenarios

  • Use unordered_map when the order of elements is not important, and you need faster access. It is ideal for scenarios where quick lookup, insertion, and deletion are crucial.
  • For Example:: Implementing a word frequency counter where you count how often each word appears in a document.

  • Use map when you need to maintain a sorted order of elements. It is ideal for scenarios where data needs to be traversed in a sorted manner.

  • For Example:: Storing and retrieving student records in order of their roll numbers for a report card generation system.

Code Example to explain the Difference

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

int main() 
{
    // unordered_map example
    std::unordered_map<std::string, int> wordFrequency = {
                                                {"Where", 20},
                                                {"How", 21},
                                                {"That", 19},
                                                {"What", 29} };

    std::cout << "nUnordered Map:" << std::endl;
    for (auto& pair : wordFrequency) 
    {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // map example
    std::map<std::string, int> sortedWordFrequency = {
                                                {"Where", 20},
                                                {"How", 21},
                                                {"That", 19},
                                                {"What", 29}  };

    std::cout << "n Map Contents:" << std::endl;
    for (auto& pair : sortedWordFrequency) 
    {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Output:

Unordered Map:
What: 29
That: 19
How: 21
Where: 20

 Map Contents:
How: 21
That: 19
What: 29
Where: 20

In the above example, a key difference between std::unordered_map and std::map in C++ is illustrated through their handling of order and sorting.

An unordered_map (i.e. wordFrequency) does not maintain any specific order of the elements. It uses a hash table for storage, meaning the order of elements is determined by the hash function and can appear random. This is evident in the output, where the order of the words (“Where”, “How”, “That”, “What”) does not correspond to the order in which they were inserted nor are they sorted alphabetically.

In contrast, in a std::map (i.e., sortedWordFrequency) automatically sorts its elements. It uses a self-balancing binary search tree, which maintains the elements in sorted order based on their keys. This characteristic is clearly demonstrated in the output, where the same set of words is sorted alphabetically (“How”, “That”, “What”, “Where”), regardless of the order in which they were added to the map. This sorting behavior is intrinsic to std::map and is a primary reason to choose it over unordered_map when a sorted order of elements is required.

Summary

Choosing between unordered_map and map depends on your specific needs in C++. If you prioritize speed and don’t care about the order, unordered_map is the way to go. But if you need ordered data, then map is the better choice.

Ritika Ohri

Hi, I am Ritika Ohri, founder of this blog. I craft comprehensive programming tutorials and also manage a YouTube channel. You can also connect with me on Linkedin.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.