Multisets are containers very similar to sets; the main difference in multisets is that they can have multiple elements with the same values, unlike in sets.
Multisets containers store the item in a particular specific order. In multisets, we can erase more than 1 element by giving start and end iterators.
Multiset in C++
A multiset in C++ is an associative container similar to a set, except that multiple elements can have the same values. Multisets containers are slower than unordered_sets containers when it comes to accessing individual elements by their key. Still, the advantage of sets is that they allow direct iteration on the subsets based on their order of elements in the container.
The storage needs are dynamically handled as multisets support insertion and deletion operations.
In the case of multisets, sorting is done using the key comparison function compare. Operations such as search, insert, and delete have logarithmic complexity.
The order of the items that compare equivalents is the insertion order, and it does not change from the introduction of C++11.
The main requirement of multisets is a container, aware allocator container, associative container, and reversible container.
The main application of multisets is in binary search trees.
The value of the elements in the multisets cannot be modified once inserted into the container, i.e. the items are always constant. But the insertion and removal operation can be performed.
Syntax of multiset
template<class X, class comp = less<X> class alloc = allocator<X>> > class multiset;
where X = multiset:: key_type/value type.
While using multisets, it is essential to include the header file of the set.
#include<set> to make all the functions of the multiset operational.
Multiset container properties
1 – Associative: Their key reference elements are present in the associative containers and not by their absolute position in the container.
2- Ordered: The items in the multiset container always follow an order. All the inserted elements are given a position in the container according to a specific order.
3- Multiple equivalent keys: This property states that multiple items in the multisets can have equal keys.
4- Allocator- aware: This container usually uses an allocator object to handle the storage needs dynamically.
Some important methods of multisets
begin()
It returns the iterator to the first element present in the multiset.
end()
It returns an iterator to the theoretical element that follows the last element in the multiset.
empty()
It returns whether the multiset is empty or not.
max_size()
It returns the maximum number of elements that the multiset can hold.
size()
It returns the number of elements in the multiset.
Program of Multiset in C++
Q1- Write a program to insert an element in a multiset.
#include <iostream>
#include <set>
using namespace std;
int main()
{
multiset<int, greater<int>> set_1;
set_1.insert(502);
set_1.insert(502);
set_1.insert(506);
set_1.insert(507);
set_1.insert(555);
multiset<int, greater<int>>::iterator iterator_1;
cout << "\nThe multiset elements are: ";
for (iterator_1 = set_1.begin(); iterator_1 != set_1.end(); ++iterator_1)
{
cout << "\t" << *iterator_1;
}
};
See the output.
Q2- Write a program to insert five elements in a set, delete two items, and print the set.
#include <iostream>
#include <set>
using namespace std;
int main()
{
multiset<int, greater<int>> set_1;
set_1.insert(502);
set_1.insert(502);
set_1.insert(506);
set_1.insert(507);
set_1.insert(555);
multiset<int, greater<int>>::iterator iterator_1;
cout << "\nThe multiset elements before deletion are: ";
for (iterator_1 = set_1.begin(); iterator_1 != set_1.end(); ++iterator_1)
{
cout << "\t" << *iterator_1;
}
set_1.erase(506);
set_1.erase(555); //deleting elements
cout << "\nThe multiset elements after deletion are: ";
for (iterator_1 = set_1.begin(); iterator_1 != set_1.end(); ++iterator_1)
{
cout << "\t" << *iterator_1;
}
};
See the output.
In the second example, observe the output, as the elements before deletion are also present in the second line. (You may miss this) after removal, only three items are there, including the repeating elements.
More Functions of Multisets in C++
- pair insert(const g): Adds a new element ‘g’ to the multiset.
- Iterator insert (iterator position, const g): Adds a new element ‘g’ at the position pointed by an iterator.
- erase(iterator position): Removes the element at the position the iterator points.
- erase(const g): Removes the value ‘g’ from the multiset.
- clear(): Removes all the elements from the multiset.
- key_comp() / value_comp(): Returns the object that determines how the elements in the multiset are ordered (‘<‘ by default).
- find(const g): Returns an iterator to the element ‘g’ in the multiset if found, else returns the iterator to end.
- count(const g): Returns several matches to element ‘g’ in the multiset.
- lower_bound(const g)– Returns the iterator to the first item that is equivalent to ‘g’ or will not go before the item ‘g’ in the multiset.
- upper_bound(const g): Returns the iterator to the first item that is equivalent to ‘g’ or definitely will go after the item ‘g’ in the multiset.
- multiset::swap(): The function is used to exchange the contents of two multisets, but the sets must be of the same type, although sizes may differ.
- multiset::operator(): This operator is used to assign new contents to the container by replacing the existing contents.
- multiset::emplace(): The function is used to insert a new element into the multiset container.
- multiset equal_range(): It returns the iterator of pairs. The pair refers to a range that includes all the items in the container with the key equivalent to k.
- multiset::emplace_hint(): Inserts a new element in the multiset.
- multiset::rbegin(): Returns a reverse iterator pointing to the last element in the multiset container.
- multiset::rend(): Returns a reverse iterator pointing to the theoretical element right before the first element in the multiset container.
- multiset::cbegin(): Returns a constant iterator pointing to the first element in the container.
- multiset::cend(): Returns a constant iterator pointing to the position past the last element in the container.
- multiset::crbegin(): Returns a constant reverse iterator pointing to the last element in the container.
- multiset::crend(): Returns a constant reverse iterator pointing to the position just before the first element in the container.
- multiset::get_allocator(): Returns the copy of the allocator object associated with the multiset.
Conclusion
Multisets are part of the C++ STL (Standard Template Library).
Multisets are associative containers like Set that store sorted values (the value is the key of type T), but unlike Set, which stores unique keys, multisets can have duplicate keys.
By default, it uses the < operator to compare the keys.
That’s it.
