Introduction:
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++:
#include
using namespace std;
void perf_test()
{
map
unordered_map
auto start = high_resolution_clock::now(); 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 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
for (int i = 0; i < 1e6; i++)
Map[i] += i;
auto stop = high_resolution_clock::now();
auto duration = duration_cast
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
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++
Unordered_map in C++
