Unordered Map in C++ (STL)

In this article we will discuss what is unordered_map and how it use it.

What is an unordered_map

Unordered_map provides a functionality of map i.e. it store the elements in key value pair and with unique key only.

Unordered_map internally uses the hashing to achieve this. It internally uses a hash table to implement this hashing feature. If you want to know more about hashing check following article,
What is Hashing and Hash Table

In an unordered_map elements are stored in a key value pair combination. But elements are stored in arbitrary order unlike associative containers where elements were stored in sorted order of keys.

Let’s see an example by creating an unordered_map of string and int, to maintain the repeated count of a word i.e.

#include <iostream>
#include <unordered_map>
#include <string>

int main()
{
	// Create an empty unordered_map
	std::unordered_map<std::string, int> wordMap;

	// Insert Few elements in map
	wordMap.insert( { "First", 1 });
	wordMap.insert(	{ "Second", 2 });
	wordMap.insert(	{ "Third", 3 });

	// Overwrite value of an element
	wordMap["Third"] = 8;

	// Iterate Over the unordered_map and display elements
	for (std::pair<std::string, int> element : wordMap)
		std::cout << element.first << " :: " << element.second << std::endl;

	return 0;
}

Output:



    Third :: 8
    Second :: 2
    First :: 1
    

    As we can see above, elements are stored in arbitrary order.

    How unordered_map store elements?

    The reason because unordered_map does the hashing i.e. whenever we try to insert an element in a unordered_map, it internally does the following steps,

    • First hash of key is calculated using Hasher function and then on the basis of that hash an appropriate bucket is choose.
    • Once bucket is identified then it compares the key with key of each element inside the bucket using Comparator function to identify if given element is a duplicate or not.
    • If its not a duplicate then only it stores the element in that bucket

    Therefore, there is no specific order in which elements are stored internally.

    Advantage of Unordered_map

    The basic advantage of using unordered_map instead of associative map is the searching efficiency. In an unordered_map complexity to search for an element is O(1) if hash code are chosen efficiently.

    Scroll to Top