Data Structures: MULTI_SET vs SET vs UNORDERED_SET
Are you confused about the differences between these data structures?
Let’s get you on track then!
In today’s tiny post, I’ll list out most of their differences and their implementations. I’ll also include an image containing the time complexities of different data structures at the end of the post.
First of all, let me make it clear that I’ll be following the C++ programming language. So the names and some of the properties, methods, and time complexities may differ due to differences in their implementations.
So let’s get started without further ado!
To put things in a simple way :
Set is a container that stores sorted and unique elements.
Unordered_set does not sort and stores unique elements.
Multi_set can have duplicate elements but is sorted.
We also have Unordered_multiset, which can have duplicates but is not sorted.
So, All of these have something or the other in common within themselves.
1) set
Stores the values in sorted order.
Stores only unique values.
Elements can only be inserted or deleted but cannot be modified.
Implemented as Binary Search Tree.
2) unordered_set
Elements are not stored in an order.
Stores unique values.
Implemented as Hash-table, to store elements.
All other properties similar to set.
3) multi_set
Stores elements in sorted order.
It allows storage of duplicate elements.
C++ standard doesnot secify the implentation of multi_set but GCC implements it as a red-black tree which allows for faster lookup, insertion and deletion.
All other properties similar to set.
4) unordered_multiset
Elements are not sorted in an order.
Duplicate elements can be stored.
Implemented as Hash-table, to store elements.
All other properties similar to set.
Now you might be thinking “What’s the difference between vector and unordered_multiset ??” Read this answer on stack overflow to get a clear view on the same.
Cutting to the chase: All these associative data structures provide faster lookup, delete, and insertion in most of the cases, due to the reason that they are implemented based on hashtables and binary search trees.
Now It’s time for the time complexities, which we are most concerned about when coding. This image consists of most of them :
I hope you learned something from today’s post. Let me know if you want me to write on other data structures as well. Let me know in the comments section. Also, feel free to share if I wrote something wrong or missed it.
If you are pleased too much, you can always buy me a coffee 😉
You can read some of my other posts :
I coded a script to download the “download restricted” files of Google Drive
Play YouTube Videos on VLC with Just 1 Click
Convert Your ‘.py’ to a ‘.exe’ File with Just 2 Commands
All You Need to Know About the “Fetch API” in JavaScript
Share your thoughts in the comments section. For further doubts or anything else, you can ping me at mohithgupta@gmail.com or find me on Twitter.
That’s it for today, Arigato for reading :) Sayonara! See you in the next one!
