C++ 11 introduced another kind of containers in STL : Unordered Containers.
Just as you can guess from its name, the order of elements is not defined and it may change over the time.
There are four unordered containers in C++ STL :
1. unordered_set
2. unordered_multiset
3. unordered_map
4. unordered_multimap
Unordered containers are implemented using Hashtable.
Hashtable can be implemented as an array of buckets, where each bucket is implemented as a linked list, to handle multiple values which map to this index(handling collision).
The key to be stored is given to the hash function which gives us the index of hashtable, where this key is stored.
The biggest advantage of this kind of structure is that if we have an effective hash function(which provides very less collisions), then it only takes constant time to find the correct position for an element in the container.
Unordered containers are used for hashing, i.e when we want to store certain values in the container for later use. This is because they provide very fast lookup.
Hash collision :
When multiple elements are stored in the same bucket(linked list), this may degrade the performance of the container. Some buckets will be empty while some will have many elements. Worst case occurs when all the elements are stored in the same bucket causing a linear time complexity for most operations. Therefore selecting an efficient hash function is very important but unordered containers are very efficiently designed in STL and perform really well.
=> All operations on unordered containers take constant time O(1) on an average which can go up to linear time O(n) in worst case which depends on the internally used hash function.
Let's discuss unordered_set to understand unordered containers.
unordered_set is a container which stores unique values(set) without any particular order between elements(unordered).
=> Declaring an unordered set of type string
unordered_set<string> us = {"coding","singing","playing"};
=> Inserting an element
us.insert("codingwithart"); // O(1) on average, but worst case : O(n)
=> Inserting from a vector
vector<string> vec = {"str1","str2"};
us.insert(vec.begin(), vec.end());
This inserts all the elements from the provided vector between the iterators provided.
=> Searching an element
We know unordered containers provide very fast lookup function
auto itr = us.find("coding"); // O(1) on average(Amortized constant time)
It returns an iterator which points to the item if found otherwise it points to the end of the container.
if(itr != us.end()) // important check as value may not be present which may lead to undefined behavior
cout<<*itr<<" ";
=>Erasing an element
a. Using iterator :
auto it=us.find("coding");
us.erase(it); O(1);
b. Using value :
us.erase("coding"); // O(1) on average
Other unordered containers :
unordered_multiset : unordered_set which allows duplicate elements
unordered_map : map in which the keys are unordered
unordered_multimap : unordered_map which allows duplicate keys
=> Properties of unordered containers :
1. Fastest search, insert and erase (O(1) on average).
Associative containers take O(log n), sequence containers take O(n).
2. They are read-only, i.e
unordered set/multiset : element value cannot be changed
unordered map/multimap : element key cannot be changed
3. unordered_map also provides random access by key just like map.
unordered_map<char, int> mp = {{'a',4},{'b',10}};
cout<<mp['a']; // prints 4
mp['d']=25; // inserts pair {'d',25} in mp
mp['a']=1; // update pair {'a',4} to {'a',1}
But remember multimap and unordered_multimap do not provide random access.
This completes our discussion of Unordered containers. If you have any doubts. please mention in the comments section.
Also check out other types of C++ STL containers if you missed them out :
1. Sequence Containers
2. Associative Containers
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.