Hi everyone

In this tutorial we will talk about Unordered Map

So, What is Unordered Map actually?

Unordered Map is an associative container of C++ STL that stores data in key–value pairs, just like map. Each key inside an unordered map is unique, and we access values using their keys.

The big difference from map is that unordered map does not keep the keys in any sorted order. Instead, it uses a hash function to decide where to put each key. That’s why it is called “unordered”.

Unordered Map’s underlying data structure is a Hash Table. Because of hashing, all its major operations — insertion, deletion, search — take O(1) time on average. In the worst case (when many keys hash to the same bucket) the operations can go up to O(n), but in practice this is very rare.

Header File Inclusion for unordered_map

#include <unordered_map>

Declaration & Initialization

Declaring an empty unordered map —


unordered_map <int, string> studentMap;

Here, key type is int and value type is string. The unordered map is empty right now.

Declaring an unordered map with values —

From C++11 onwards, we can initialize an unordered map with values using curly braces —


unordered_map <int, string> studentMap = {
    { 101, "Imran" },
    { 102, "Linkon" },
    { 103, "Sakib" }
};

After Initialization studentMap may look like this —

key	value
103	Sakib
101	Imran
102	Linkon

Notice that the order of keys is not 101, 102, 103. Since unordered map does not keep keys sorted, the actual order depends on the hash function and can be different on different machines or compilers.

Declaring an unordered map with different data types —

Key and value can be of any hashable type —


unordered_map <string, int> ageMap;
unordered_map <char, vector<int> > charListMap;
unordered_map <int, pair<int, int> > rangeMap;

💡 Quick tip on key types — Since unordered map relies on hashing, the key type must have a valid hash function. All built-in types (int, string, char, double, etc.) work out of the box. But for custom types or pair, we need to provide our own hash function. We will see this in a bit.

Insertion

Insertion using [ ] subscript operator

The easiest way to insert a key–value pair is by using the [ ] operator —


unordered_map <int, string> studentMap;

studentMap[101] = "Imran";
studentMap[102] = "Linkon";
studentMap[103] = "Sakib";

Insertion using insert() method with pair

We can also insert values using the insert() method with a pair —


studentMap.insert(pair<int, string>(104, "Rafi"));

Insertion using insert() method with make_pair

Same thing can be done with make_pair() for cleaner code —


studentMap.insert(make_pair(105, "Tanvir"));

Insertion using insert() method with curly braces

From C++11 onwards, we can insert using curly braces directly —


studentMap.insert({ 106, "Shuvo" });

Insertion using emplace() method

emplace() constructs the pair in place, so it avoids an extra copy —


studentMap.emplace(107, "Hasan");

💡 Quick tip on duplicate keys — Since unordered map keys are unique, if we try to insert a key that already exists using insert() or emplace(), the insertion will be ignored (old value stays). But if we use the [ ] operator, the old value will be overwritten. Choose carefully based on what we want.

Insertion using insert_or_assign() method (C++17)

If we want the behavior of “insert if new, update if exists” explicitly, we can use insert_or_assign() —


studentMap.insert_or_assign(101, "Imran Hossain");

Now the value of key 101 will be updated to “Imran Hossain”.

Accessing the element

[ ] subscript operator

We can access the value of a given key using the [ ] operator —


cout << studentMap[102] << endl;

Output will be – Linkon

💡 Quick tip on [ ] operator — If the key does not exist, the [ ] operator will create a new entry with that key and a default value (empty string, 0, etc.). This can silently add unwanted entries to our unordered map. If we just want to read, prefer at() or find() instead.

at() method

at() method also returns the value of a given key. But unlike [ ], it does not create a new entry if the key is missing — it throws an out_of_range exception instead —


cout << studentMap.at(103) << endl;

Output will be – Sakib

find() method

find() returns an iterator to the element if the key exists, otherwise it returns end() —


auto it = studentMap.find(104);

if (it != studentMap.end())
{
    cout << it->first << " " << it->second << endl;
}
else
{
    cout << "Key not found" << endl;
}

Output will be – 104 Rafi

Checking if a key exists

count() method

Since keys are unique, count() returns either 0 (not present) or 1 (present) —


if (studentMap.count(105))
{
    cout << "Key exists" << endl;
}

contains() method (C++20)

From C++20 onwards, we have a cleaner way —


if (studentMap.contains(105))
{
    cout << "Key exists" << endl;
}

Iterating through an unordered map

Range-based for loop

The cleanest way to iterate through an unordered map is using a range-based for loop —


for (auto &element : studentMap)
{
    cout << element.first << " - " << element.second << endl;
}

Output may be something like —

107 - Hasan
103 - Sakib
101 - Imran Hossain
106 - Shuvo
104 - Rafi
102 - Linkon
105 - Tanvir

Using iterator

We can also iterate using iterators directly —


unordered_map <int, string>::iterator it;

for (it = studentMap.begin(); it != studentMap.end(); it++)
{
    cout << it->first << " - " << it->second << endl;
}

💡 Note on iteration order — Unlike map, unordered map does not iterate keys in sorted order. The order depends on the hash values and the bucket layout, so it can feel random. If we need the keys sorted, we should use map instead.

Deletion

Deletion using erase() with key

We can delete a specific key–value pair by passing the key directly to erase() —


studentMap.erase(102);

After deletion, the entry with key 102 will be removed from the unordered map.

Deletion using erase() with iterator

We can also delete using an iterator —


auto it = studentMap.find(104);

if (it != studentMap.end())
{
    studentMap.erase(it);
}

clear() method

If we want to remove all elements of the unordered map, we can use clear() —


studentMap.clear();

After clear(), studentMap will be empty.

Size and Empty


cout << studentMap.size() << endl;

if (studentMap.empty())
{
    cout << "Unordered map is empty" << endl;
}

size() returns the number of elements, and empty() returns true if the unordered map has no elements.

Swapping

swap() method

STL unordered map has a method named swap(), which swaps all the key–value pairs between two unordered maps —


unordered_map <int, string> mapOne = {
    { 1, "One" },
    { 2, "Two" }
};

unordered_map <int, string> mapTwo = {
    { 10, "Ten" },
    { 20, "Twenty" },
    { 30, "Thirty" }
};

// swapping values between two unordered maps
mapOne.swap(mapTwo);

After swapping, mapOne will have the elements of mapTwo, and mapTwo will have the elements of mapOne.

Unordered Map with pair as key

Sometimes we want to use a pair as the key — for example, to store the weight of an edge between two nodes. But if we try this directly —


// this will give a compile error
unordered_map < pair<int, int>, int > edgeWeight;

We will get a compile error. The reason is that STL does not provide a default hash function for pair. We need to provide our own.

Writing a custom hash function —


struct pairHash
{
    size_t operator()(const pair<int, int> &p) const
    {
        // combine hashes of the two elements
        return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
    }
};

unordered_map < pair<int, int>, int, pairHash > edgeWeight;

edgeWeight[{1, 2}] = 50;
edgeWeight[{1, 3}] = 20;
edgeWeight[{2, 3}] = 70;

Accessing values —


cout << edgeWeight[{1, 3}] << endl;

Output will be – 20

💡 Note on custom hash — The hash function must be deterministic (same input always gives same output) and should spread the keys as evenly as possible across buckets. A poor hash function can push the performance from O(1) down to O(n).

Bucket Interface

Unordered map stores its elements in buckets. Each bucket holds keys that hash to the same index. STL gives us a few methods to peek into this bucket structure.

bucket_count() method

Returns the total number of buckets currently in the unordered map —


cout << studentMap.bucket_count() << endl;

bucket() method

Returns the bucket number where a given key is stored —


cout << studentMap.bucket(101) << endl;

load_factor() method

Returns the average number of elements per bucket, calculated as size() / bucket_count(). A higher load factor means more collisions —


cout << studentMap.load_factor() << endl;

max_load_factor() method

Returns (or sets) the maximum load factor that unordered map allows. When the actual load factor crosses this value, the unordered map automatically rehashes —


cout << studentMap.max_load_factor() << endl;

// setting a new max load factor
studentMap.max_load_factor(0.75);

rehash() method

Forces the unordered map to rebuild its internal bucket structure with at least the given number of buckets —


studentMap.rehash(100);

reserve() method

Reserves enough buckets to hold at least the given number of elements without rehashing. This is very useful when we know how many elements we are about to insert —


// if we know we will insert around 10000 elements
studentMap.reserve(10000);

💡 Quick tip on reserve() — Calling reserve() before a big batch of insertions prevents multiple rehashes during insertion and can give a noticeable speed boost.

Unordered Map vs Map

This is a common confusion, so it is worth a quick note —

Property	unordered_map	map
Underlying data structure	Hash Table	Red-Black Tree
Order of keys	No specific order	Sorted
Insertion / Deletion / Search	O(1) average, O(n) worst	O(log n)
lower_bound() / upper_bound()	Not available	Available
Memory usage	Higher (due to buckets)	Lower
Use when	We just need fast lookup, order does not matter	We need sorted keys or ordered traversal

Time Complexity

Operation	Description	Time Complexity
operator[ ]	Access or insert a value by key	O(1) average, O(n) worst
at()	Access value by key (throws if missing)	O(1) average, O(n) worst
insert()	Insert a key–value pair	O(1) average, O(n) worst
emplace()	Construct and insert a key–value pair in place	O(1) average, O(n) worst
insert_or_assign()	Insert new or update existing value	O(1) average, O(n) worst
erase()	Remove an element by key or iterator	O(1) average, O(n) worst
find()	Find an element by key	O(1) average, O(n) worst
count()	Check if a key exists (returns 0 or 1)	O(1) average, O(n) worst
contains()	Check if a key exists (C++20)	O(1) average, O(n) worst
size()	Returns the number of elements	O(1)
empty()	Returns true if unordered map is empty	O(1)
clear()	Removes all elements	O(n)
swap()	Swaps contents of two unordered maps	O(1)
bucket_count()	Returns the number of buckets	O(1)
load_factor()	Returns average elements per bucket	O(1)
rehash()	Rebuilds the bucket structure	O(n) average, O(n²) worst
reserve()	Reserves buckets for expected element count	O(n) average, O(n²) worst
begin() / end()	Iterators to the beginning and end	O(1)

Applications

- - - Fast frequency counting of words, characters, or numbers
    - Caching and memoization in dynamic programming
    - Checking duplicates in large datasets
    - Two-sum and subarray-sum style problems
    - Hash-based database indexing
    - Symbol tables in compilers and interpreters
    - Counting distinct elements when order does not matter
    - Associating IDs with objects when fast lookup is the main concern

In the next tutorial we will talk about another useful STL container.

Until then
Happy Coding