C++ multisets are STL containers that store elements of the same type in sorted order, where multiple elements can have equivalent values. In other words, duplicate values are allowed.
Like C++ sets, the value of each element acts as its own key.
Multiset Properties
- Elements are referenced by their key and not by their absolute position in the container.
- Elements are stored in a sorted manner.
- Multiple elements in the container can have equivalent keys.
Syntax :
#include <set>
// declare a multiset default ascending order
std::multiset<data_type> multiset_name = {key1, key2, key3, ...};
// declare a multiset in descending order
std::multiset<data_type, greater<data_type>> multiset_name = {key1, key2, key3, ...};Example :
// initialize multiset with elements
std::multiset<int> my_multiset1 = {5, 3, 8, 1, 3};
// initialize multiset with elements
multiset<int, greater<int>> my_multiset = {5, 3, 8, 1, 3};C++ Multiset Methods
In C++, we have various methods to perform various operations in a multiset.
| Operation | Description | Time complexity |
|---|---|---|
| begin() | Returns an iterator to the first element in the multiset | O(1) |
| end() | Returns an iterator to the theoretical element that follows the last element in the multiset | O(1) |
insert() | Insert elements into a multiset. | O(log n) |
erase() | Erase all instances of an element. | O(log n) |
clear() | Remove all the elements from a multiset. | O(n) |
empty() | Check if the multiset is empty. | O(1) |
size() | Returns the size of the multiset. | O(1) |
| max_size() | Returns the maximum number of elements that the multiset can hold | O(1) |
#include <iostream>
#include <set>
using namespace std;
int main() {
multiset<int> my_multiset = {5, 3, 8, 1, 3};
cout << "multiset ascending order:" << "\n"
for(int val : my_multiset) {
cout << val << " ";
}
multiset<int, greater<int>> my_multiset = {5, 3, 8, 1, 3};
cout << "multiset descending order:" << "\n"
for(int val : my_multiset) {
cout << val << " ";
}
return 0;
}
/*
Output :
multiset ascending order:
1 3 3 5 8
multiset ascending order:
8 5 3 3 1
*/Add Elements to a Multiset :
#include <iostream>
#include <set>
using namespace std;
int main () {
multiset<int> my_multiset;
// add values to the multiset
my_multiset.insert(10);
my_multiset.insert(30);
my_multiset.insert(20);
my_multiset.insert(50);
my_multiset.insert(40);
my_multiset.insert(50);
// print multiset after insertion
for (int i : my_multiset) {
cout << i << " ";
}
return 0;
}
/*
Output :
10 20 30 40 50 50
*/Remove Elements From a Multiset :
#include <iostream>
#include <set>
using namespace std;
int main () {
multiset<int> my_multiset = {10, 30, 20, 50, 40, 50};
// delete all occurences of 50 from the multiset
my_multiset.erase(50);
// print multiset after erase
cout << "\nThe multiset after erase: ";
for (int i : my_multiset) {
cout << i << " ";
}
// delete all values from the multiset
my_multiset.clear();
// print multiset after clear
cout << "\nThe multiset after clear: ";
for (int i : my_multiset) {
cout << i << " ";
}
return 0;
}
/*
Output :
The multiset after erase: 10 20 30 40
The multiset after clear:
*/Multiset empty() and size() Methods
#include <iostream>
#include <set>
using namespace std;
int main () {
multiset<int> my_multiset = {10, 20, 20, 20 ,30 , 40};
// print multiset before clearing all values
cout << "The multiset before clear: ";
for (int i : my_multiset) {
cout << i << " ";
}
// check if the multiset is empty
cout << "\nEmpty: " << my_multiset.empty() << endl;
// check the size of the multiset
cout << "Size: " << my_multiset.size() << endl;
// delete all values from the multiset
my_multiset.clear();
// multiset after clear
cout << "\nThe multiset after clear: ";
for (int i : my_multiset) {
cout << i << " ";
}
// use the capacity methods again
cout << "\nEmpty: " << my_multiset.empty() << endl;
cout << "Size: " << my_multiset.size() << endl;
return 0;
}
/*
Output :
The multiset before clear: 10 20 20 20 30 40
Empty: 0
Size: 6
The multiset after clear:
Empty: 1
Size: 0
*/
/*
Explanation :
Here, we have used the empty() and size() methods before and after clearing the contents of the multiset.
Before clearing the contents:
empty() returns 0, indicating that the multiset isn't empty.
size() returns 6, indicating that there are six elements in the multiset.
After clearing the contents:
empty() returns 1, indicating that the multiset is empty.
size() returns 0, indicating that there are no elements in the multiset.
*/Removing Element From Multiset Which Have Same Value:
- a.erase() – Remove all instances of element from multiset having the same value
- a.erase(a.find()) – Remove only one instance of element from multiset having same value
// CPP Code to remove an element from multiset which have
// same value
#include <bits/stdc++.h>
using namespace std;
int main()
{
multiset<int> a;
a.insert(10);
a.insert(10);
a.insert(10);
// it will give output 3
cout << a.count(10) << endl;
// removing single instance from multiset
// it will remove only one value of
// 10 from multiset
a.erase(a.find(10));
// it will give output 2
cout << a.count(10) << endl;
// removing all instance of element from multiset
// it will remove all instance of value 10
a.erase(10);
// it will give output 0 because all
// instance of value is removed from
// multiset
cout << a.count(10) << endl;
return 0;
}
/*
Output :
3
2
0
*/The time complexities for doing various operations on Multisets are –
- Insertion of Elements- O(log N)
- Accessing Elements – O(log N)
- Deleting Elements- O(log N)
List of all other functions of multiset :
Iterators
begin
cbegin (C++11)returns an iterator to the beginning (public member function)
end
cend (C++11)returns an iterator to the end (public member function)
rbegin
crbegin(C++11)returns a reverse iterator to the beginning (public member function)
rend
crend(C++11)returns a reverse iterator to the end (public member function)
Capacity
empty checks whether the container is empty (public member function)
size returns the number of elements (public member function)
max_size returns the maximum possible number of elements (public member function)
Modifiers
clear clears the contents (public member function)
insert inserts elements or nodes(since C++17) (public member function)
insert_range(C++23)inserts a range of elements (public member function)
emplace(C++11)constructs element in-place (public member function)
emplace_hint(C++11)constructs elements in-place using a hint (public member function)
erase erases elements (public member function)
swap swaps the contents (public member function)
extract(C++17)extracts nodes from the container (public member function)
merge(C++17)splices nodes from another container (public member function)
Lookup
count returns the number of elements matching specific key (public member function)
find finds element with specific key (public member function)
contains( C++20)checks if the container contains element with specific key (public member function)
equal_range returns range of elements matching a specific key (public member function)
lower_bound returns an iterator to the first element not less than the given key (public member function)
upper_bound returns an iterator to the first element greater than the given key (public member function)
Observers
key_comp returns the function that compares keys (public member function)
value_comp returns the function that compares keys in objects of type value_type (public member function)