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.
Frequently Asked:
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,
Best Resources to Learn C++:
- 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.
Leave a Reply
You must be logged in to post a comment.