unordered_map vs unordered_set
Unordered_map |
Unordered_set |
---|---|
Unordered_map contains elements only in the form of (key-value) pairs. | Unordered_set does not necessarily contain elements in the form of key-value pairs, these are mainly used to see the presence/absence of a set. |
Operator ‘[]’ to extract the corresponding value of a key that is present in the map. | The searching for an element is done using a find() function. So no need for an operator[]. |
Note: For example, consider the problem of counting the frequencies of individual words. We can’t use unordered_set (or set) as we can’t store counts while we can use unordered_map.
unordered_map in C++ STL
unordered_map is an associated container that stores elements formed by the combination of a key value and a mapped value. The key value is used to uniquely identify the element and the mapped value is the content associated with the key. Both key and value can be of any type predefined or user-defined. In simple terms, an unordered_map is like a data structure of dictionary type that stores elements in itself. It contains successive pairs (key, value), which allows fast retrieval of an individual element based on its unique key.
Internally unordered_map is implemented using Hash Table, the key provided to map is hashed into indices of a hash table which is why the performance of data structure depends on the hash function a lot but on average, the cost of search, insert, and delete from the hash table is O(1).
Note: In the worst case, its time complexity can go from O(1) to O(n), especially for big prime numbers. In this situation, it is highly advisable to use a map instead to avoid getting a TLE(Time Limit Exceeded) error.
Syntax:
Below is the C++ program to demonstrate an unordered map:
C++
// C++ program to demonstrate // functionality of unordered_map #include <iostream> #include <unordered_map> using namespace std; // Driver code int main() { // Declaring umap to be of // <string, int> type key // will be of STRING type // and mapped VALUE will // be of int type unordered_map<string, int > umap; // inserting values by using [] operator umap[ "w3wiki" ] = 10; umap[ "Practice" ] = 20; umap[ "Contribute" ] = 30; // Traversing an unordered map for ( auto x : umap) cout << x.first << " " << x.second << endl; } |
Contribute 30 Practice 20 w3wiki 10
Explanation: The specific thing that this output justifies is that the value of the outcome of unordered_map is produced in a random key-to-value manner whereas the map displays value and key in an ordered manner.