Multiset
Multisets are containers that store elements in a specified order and where multiple elements can have equivalent values.
In a multiset, an element is also identified by its value (the value is itself the key, of type T). A multiset's elements can be added to or deleted from the container, but their values cannot be changed once they are inside the container (they are always const).
-
It also stores the elements in a sorted manner.
-
Multiset can store duplicate values.
-
All other properties of a multiset are the same as that of the set.
Syntax:
multiset <data_type> set_name
Implementation of Multi Set in C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
multiset<int> demo_multiset;
demo_multiset.insert(20);
demo_multiset.insert(30);
demo_multiset.insert(10);
demo_multiset.insert(90);
demo_multiset.insert(80);
demo_multiset.insert(12);
//duplicates
demo_multiset.insert(20);
demo_multiset.insert(90);
cout << "Duplicates are allowed:" << endl;
// traversing the set using iterators
for (auto it = demo_multiset.begin(); it != demo_multiset.end(); it++)
{
cout << *it << " ";
}
cout << endl;
auto it2 = demo_multiset.find(12);
auto it3 = demo_multiset.find(80);
demo_multiset.erase(it2, it3);
cout << "Elements in the multiset after erasing:" << endl;
for (auto it = demo_multiset.begin(); it != demo_multiset.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
You can also try this code with Online C++ Compiler
Output:
Duplicates are allowed:
10 12 20 20 30 80 90 90
Elements in the multiset after erasing:
10 80 90 90
Time Complexity Analysis
A multiset makes use of red-black trees. For a multiset in C++, the time complexity for insertion, deletion, and retrieving information is O(log(n)) as they follow the balanced binary tree to structure the data.
Unordered Set
Unordered sets are containers that store unique elements in no particular order, and which allow fast retrieval of individual elements based on their value.
The value of an element in an unordered set acts as both its key and its unique identifier. Since keys are immutable, elements in an unordered set cannot be changed after they have been added to the container; however, they can be added and removed.
-
It stores the elements in any order, with no specified order for storing elements. It generally depends upon the machine that we are using.
-
It stores unique elements.
-
It uses the hash table for storing the element.
- All other properties are the same as that of the set.
Cost Of Hash Map
An unordered set is implemented with a hash table, where keys are hashed into hash table indices so that insertion is always randomized. All operations on the unordered set take constant time O(1) on average, which can go up to linear time O(n) in the worst case depending on the internal implementation of hash function, but they perform extremely well in practice and generally provide a constant time lookup operation.
Syntax:
unordered_set <data_type> set_name
Implementation of unordered set in C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
unordered_set<int> demo_us;
demo_us.insert(20);
demo_us.insert(30);
demo_us.insert(10);
demo_us.insert(90);
demo_us.insert(80);
demo_us.insert(12);
//duplicates
demo_us.insert(20);
demo_us.insert(90);
cout << "Elements are unique and in any order:" << endl;
// traversing the set using iterators
for (auto it = demo_us.begin(); it != demo_us.end(); it++)
{
cout << *it << " ";
}
cout << endl;
auto it2 = demo_us.find(20);
demo_us.erase(it2);
cout << "After erasing:" << endl;
for (auto it = demo_us.begin(); it != demo_us.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
You can also try this code with Online C++ Compiler
Output:
Elements are unique and in any order:
12 80 20 30 10 90
After erasing:
12 80 30 10 90
Time Complexity Analysis
All operations on the unordered_set take constant time O(1) on average which can go up to linear time O(n) in the worst case.
Check out this problem - First And Last Occurrences Of X
Unordered Multiset
Unordered multiset is an associative container that holds a collection of Key objects that may not all be unique. The complexity of search, insertion, and removal is often constant-time. Internally, the components are arranged into buckets rather than being sorted in any specific sequence.
-
It stores the elements in any order, with no specified order for storing elements. It generally depends upon the machine that we are using.
-
Duplicates are allowed.
-
It uses the hash table for storing the element.
-
All other properties are the same as that of the set.
Syntax:
unordered_multiset <data_type> set_name
Implementation of unordered multiset in C++
#include<bits/stdc++.h>
using namespace std;
int main()
{
unordered_multiset<int> demo_ums;
demo_ums.insert(20);
demo_ums.insert(30);
demo_ums.insert(10);
demo_ums.insert(90);
demo_ums.insert(80);
demo_ums.insert(12);
//duplicates
demo_ums.insert(20);
demo_ums.insert(90);
cout << "Duplicates are allowed:" << endl;
// traversing the set using iterators
for (auto it = demo_ums.begin(); it != demo_ums.end(); it++)
{
cout << *it << " ";
}
cout << endl;
auto it2 = demo_ums.find(20);
demo_ums.erase(it2);
cout << "After erasing:" << endl;
for (auto it = demo_ums.begin(); it != demo_ums.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
You can also try this code with Online C++ Compiler
Output:
Duplicates are allowed:
12 80 20 20 30 10 90 90
After erasing:
12 80 20 30 10 90 90
Time Complexity Analysis
Frequently Asked Questions
Is multiset ordered?
Internally, the elements of a multiset are always sorted according to a strict weak ordering criterion specified by its internal comparison object (of type Compare).
Is it possible to have duplicates in an unordered set?
Unordered sets do not allow duplicates and are initialized with comma-separated values surrounded by curly braces.
How do you find the set's last element?
To find the last element of a set, we can use an iterator that points to the element beyond the last element i.e. set.end(), and then move the iterator one position back by decrementing the iterator once.
Key Takeaways
In this article, we discussed the different containers of C++ STL (standard template library): Set, Multiset, Unordered set, Unordered multiset, their features and how they differ from each other. If you would like to learn more, check out our articles Introduction to C++, STL containers in C++, and many more in our Library.
Also read, Difference Between C and Python
Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! You can check out the mock exam series and take part in the contests held on Coding Ninjas Studio to test your coding proficiency. But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.
Do upvote our blogs if you find them helpful and engaging!
Happy Learning!
84+ registered