Deep dive into C++ STLs — unordered_map
Hey! Welcome to the first chapter in the C++ STLs series. Here we will explore in depth about different STLs provided by C++
But first, What is are STLs? 😯
STL stands for Standard Template Library. It is a set of template classes that have been provided to us for easy integration of standard data structures and algorithms like linked-lists, stacks, arrays, sorting, searching etc. Read more about them here.
In this article we are going to tackle the one data-structure that has proved immensely useful for me over the years of competitive coding — unordered_map.
It can be visualized as a list in which each element in-turn contains two sub-elements — key and value. Internally it uses something called a hash-function which takes in your key value, churns it through complex equations and computes a hash-value. This hash-value is used to internally store the value provided by the user.
It is because of this hash-value that locating individual items later in the data-structure’s life-cycle becomes much faster.
This is why the average cost of search, delete and insert is O(1).
NOTE: The worst case for searching an element go up-to O(n) depending on the Hash-function used and the probability of collisions but it is very unlikely to happen with modern compilers.
Show me the code 💻
Declaring an unordered_map
syntax: unordered_map<key-datatype, value-datatype> umap-name;unordered_map<int, int> intToInt;unordered_map<char, int> charToInt;
Inserting elements
syntax: umap-name[key] = value;
umap-name.insert(make_pair(key, value));intToInt[420] = 69;
charToInt['a'] = 2;
intToInt.insert(make_pair(1,1));
charToInt.insert(make_pair('a',2));
If the value data-type is Integer, then the default value will be set to ‘0’ which can let us do interesting things like
int nums[] = {2, 3, 4, 5, 2, 3};
for(auto num: nums){
intToInt[num]++;
}The code snippet above will let us count the number of occurrences of each element using the increment operator without having to initialize the unordered_map first.
Accessing all elements of umap
for(auto it: umap){
cout<<umap.first<<" "<<umap.second<<"\n";
}for(auto p = umap.begin(); p!=umap.end(); p++){
cout<<p->first<<" "<<p->second<<"\n";
}
It must be obvious but umap.first & p->first lets you access the first element or the key and umap.second & p->second lets you access the second element or the value.
Finding a key exists in unordered_map
if(umap.find(key)!=umap.end())
cout<<key<<" was found\n";
else
cout<<key<<" was not found\n";umap.find(key) returns an iterator to the position of the key in the unordered_map if it exists, or umap.end() if it does not exist.
Find key and access corresponding value
auto it = umap.find(key);if(it!=umap.end()){
cout<<"key is: "<<it->first<<" value is: "<<it->second<<endl;
}
Erase element from unordered_map
umap.erase(key);umap.erase(iterator);umap.erase(iterator_begin, iterator_end);
