This is the 1st Part of Tutorial series on unordered_map. In this tutorial, we will learn about the STL Container unordered_map in C++. We will discuss its internal data storage mechanisms in C++.

What is an Unordered_Map in C++?

An unordered_map is an associative container provided by Standard Template Library in C++. It stores the elements in a combination of a key-value pairs. Unlike standard maps, which are ordered sequences, unordered_maps follows Hashing and uses Hash Tables to store elements, which helps in faster access to individual elements based on their keys.

What is Hashing, Hash Table & Hash Function?

A Hash Table is a type of table where every item has a numeric index position. You can consider that indexing begins from zero. With each index position, there is an associated bucket. This bucket can store one or multiple elements. A Hash Table will look like this,

Hashing is a way to store elements in a Hash Table so that lookup, insertion, and deletion can be done with O(1) complexity most of the time.

The core of this Hashing process is a Hash Function, which transforms a given key into a numeric Hash value, correlating to an index in the hash table where the data is stored or retrieved.

For instance, a string like “Delhi” is passed through the hash function, which assigns an index where it’s stored in the hash table. This method enables quick operations such as insertion, lookup, and deletion, typically with O(1) time complexity.

Hashing rely on two fundamental functions: the hash function for determining the storage index and the equality operator for data verification, both of which are essential for the data types stored in the hash table.

How Unordered_Map stores the Data Internally?

Internally, an unordered_map in C++ uses a hash table to store its elements. When an element is inserted, the key is hashed using a hash function, and this hash value determines where in the table the element is stored. This mechanism allows the container to find and access elements quickly based on their keys.

The hash table consists of an array of ‘buckets’, where each bucket contains zero or more elements that have the same hash value. A good hash function minimizes collisions (where multiple keys have the same hash value), but when collisions do occur, the elements are stored in a linked list within the same bucket.

As unordered_map uses Hashing internally, so we can control the behaviour by providing the custom Hash Function and equality operator. We will discuss that latter in this series.

Why do we need unordered_map in C++

The unordered_map container is highly efficient for certain types of operations. When we need to access, insert, or delete elements frequently and the order of elements is not important, unordered_map becomes a more suitable choice than a regular map in C++. It offers average constant time complexity (O(1)) for these operations, making it best for scenarios where performance is a critical factor.

Example of unordered_map

To use an unordered_map, first we need to include the <unordered_map> header file. Then we can create an object of unordered_map by specifying the types of the key and value while creating its object. The syntax is as follows:

std::unordered_map<KeyType, ValueType> mapName;

Here, KeyType is the type of the keys and ValueType is the type of the values that the map will store. Here’s an example of using an unordered_map: We can initialize the unordered_map with an Initializer List of predefined key-value pairs. Like this,

#include <iostream>
#include <unordered_map>

int main() 
{
    // Creating an unordered_map to store words as keys
    // and their frequency as values
    std::unordered_map<std::string, int> wordFrequency = {
                                              {"Where", 20}, 
                                              {"How",    21}, 
                                              {"That",   19}
                                          };

    // Accessing elements from unordered_map
    std::cout << "Frequency of Word 'How' is: " << wordFrequency["How"] << std::endl;

    return 0;
}

Output:

Frequency of Word 'How' is: 21

We created an unordered_map of strings and integers, where keys are of string type and values are of integer type. Then we accessed the value associated with the key “How” from the unordered_map using the [] operator. We will see more about creating unordered_map objects and accessing values later in this series.

Summary

Today we have explored the concept of unordered_map in C++, its internal data storage mechanism. Unordered_maps are ideal for scenarios where fast access to elements is crucial, and the order of elements is not a concern.

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.