Solved: map vs unordered_map in


Map and unordered_map are both associative containers present in the C++ Standard Template Library (STL) that store elements formed by the combination of a key value and a mapped value. The main difference between the two is that while map (like a set) implements a self-balancing Binary Search Tree (BST) and stores keys in sorted order, unordered_map (like unordered_set) uses a Hash table for internal implementation and keys are not ordered.

Solution to the Problem:

When programming in C++, deciding when to use a map versus an unordered map can significantly impact efficiency. This decision largely depends on the specifications of your application. If the ordering of elements is important, opt for a map. However, if you’re aiming for faster access times, unordered_map is the way to go.

The code discussed here will demonstrate the difference in performance between map and unordered_map in C++:

using namespace std;

void perf_test()
map Map;
unordered_map Unordered_Map;

auto start = high_resolution_clock::now();
for (int i = 0; i < 1e6; i++) Map[i] += i; auto stop = high_resolution_clock::now(); auto duration = duration_cast(stop – start);
cout << "Time taken by Map: "<< duration.count() << " microseconds" << endl; start = high_resolution_clock::now(); for (int i = 0; i < 1e6; i++) Unordered_Map[i] += i; stop = high_resolution_clock::now(); duration = duration_cast(stop – start);
cout << "Time taken by Unordered_Map: "<< duration.count() << " microseconds" << endl; } int main() { perf_test(); return 0; } [/code] This performance test would typically reveal that unordered_map is faster than map.

Understanding Map in C++

A map in C++ STL is an associative container that stores elements formed by a combination of a key value and a mapped value. The key values are sorted, which allows for easy lookup, addition and removal of items from the map. However, because the elements in a map are ordered, the time complexity for lookup, insert and delete operations is logarithmic in the size of the map.

In the aforementioned code, we create a map named “Map” and we add elements using a loop and time the operation using the high_resolution_clock utility from the library.

Unordered_map in C++

Unlike a map, an unordered_map performs average case constant-time lookups, insertions and deletions, regardless of the size of the map. It achieves this impressive performance by using a hash table for its underlying implementation.

In our example code, we create an unordered_map named “Unordered_Map” and just like for the map, we add elements using a loop and time the operation. In most cases, the time taken by unordered_map operations is significantly less than those performed by a map.

Understanding the differences and characteristics of map and unordered_map in C++ will allow developers to leverage their strengths and create efficient applications tailored to the problem at hand.


In both, map and unordered_map sections of the provided code, we’ve used library. This library in C++ STL provides us with functions and classes to calculate time. C++ program to calculate duration of a program using Chrono library gives a clear explanation of high_resolution_clock, which is used to measure time in microseconds, and duration_cast(), which converts the units of a calculated duration to its desired type.

Related posts:

Leave a Comment