Differences :
| set | unordered_set
---------------------------------------------------------
Ordering | increasing order | no ordering
| (by default) |
Implementation | Self balancing BST | Hash Table
| like Red-Black Tree |
search time | log(n) | O(1) -> Average
| | O(n) -> Worst Case
Insertion time | log(n) + Rebalance | Same as search
Deletion time | log(n) + Rebalance | Same as search
Use set when
- We need ordered data.
- We would have to print/access the data (in sorted order).
- We need predecessor/successor of elements.
- Since set is ordered, we can use functions like binary_search(), lower_bound() and upper_bound() on set elements. These functions cannot be used on unordered_set().
- See advantages of BST over Hash Table for more cases.
Use unordered_set when
- We need to keep a set of distinct elements and no ordering is required.
- We need single element access i.e. no traversal.
Examples:
set: Input : 1, 8, 2, 5, 3, 9 Output : 1, 2, 3, 5, 8, 9 Unordered_set: Input : 1, 8, 2, 5, 3, 9 Output : 9 3 1 8 2 5
If you want to look at implementation details of set and unordered_set in c++ STL, see Set Vs Map. Set allows to traverse elements in sorted order whereas Unordered_set doesn’t allow to traverse elements in sorted order.
Implementation:
CPP
// Program to print elements of set#include <bits/stdc++.h>using namespace std;int main(){ set<int> s; s.insert(5); s.insert(1); s.insert(6); s.insert(3); s.insert(7); s.insert(2); cout << "Elements of set in sorted order: \n"; for (auto it : s) cout << it << " "; return 0;} |
Output
Elements of set in sorted order: 1 2 3 5 6 7
Implementation:
CPP
// Program to print elements of set#include <bits/stdc++.h>using namespace std;int main(){ unordered_set<int> s; s.insert(5); s.insert(1); s.insert(6); s.insert(3); s.insert(7); s.insert(2); cout << "Elements of unordered_set: \n"; for (auto it : s) cout << it << " "; return 0;} |
Output
Elements of unordered_set: 2 7 3 6 5 1
Predecessor/Successor in Set: Set can be modified to find predecessor or successor whereas Unordered_set doesn’t allow to find predecessor/Successor.
Implementation:
CPP
// Program to print inorder predecessor and inorder successor#include <bits/stdc++.h>using namespace std;set<int> s;void inorderPredecessor(int key){ if (s.find(key) == s.end()) { cout << "Key doesn't exist\n"; return; } set<int>::iterator it; it = s.find(key); // get iterator of key // If iterator is at first position // Then, it doesn't have predecessor if (it == s.begin()) { cout << "No predecessor\n"; return; } --it; // get previous element cout << "predecessor of " << key << " is="; cout << *(it) << "\n";}void inorderSuccessor(int key){ if (s.find(key) == s.end()) { cout << "Key doesn't exist\n"; return; } set<int>::iterator it; it = s.find(key); // get iterator of key ++it; // get next element // Iterator points to NULL (Element does // not exist) if (it == s.end()) { cout << "No successor\n"; return; } cout << "successor of " << key << " is="; cout << *(it) << "\n";}int main(){ s.insert(1); s.insert(5); s.insert(2); s.insert(9); s.insert(8); inorderPredecessor(5); inorderPredecessor(1); inorderPredecessor(8); inorderSuccessor(5); inorderSuccessor(2); inorderSuccessor(9); return 0;} |
Output
predecessor of 5 is=2 No predecessor predecessor of 8 is=5 successor of 5 is=8 successor of 2 is=5 No successor
Let us see the differences in a tabular form -:
| set | unordered_set | |
| 1. | It is used to store the unique elements. | It is used to store the unique elements. |
| 2. | Sets are implemented using Binary search trees. | It is implemented using hash table |
| 3. | It stores the elements in increasing order. | It stores the element with no order. |
| 4. | We can traverse sets using iterators. | We can traverse unordered_set using iterators. |
| 5. | It is included in #include <set> header file. | It is included in #include <unordered_set> header file. |
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
