How is multiset implemented in C++
Similar to sets, multisets are an associative container type where several items may share the same values.
Associative containers implement instantly searchable sorted data structures with O(log n) complexity.
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).
A multiset's internal comparison object always indicates the strict weak ordering criterion that must be followed while sorting the elements internally (of type Compare).
Multiset containers provide direct iteration on subsets depending on their order but are typically slower than unordered multiset containers to access individual pieces by their key.
The most common way to implement multisets is via binary search trees.
Associated multiset functions:
- end() - This function is used to return a theoretical element that follows the last element, which is present in the Multiset through an iterator in O(1)
- begin() - This function is used to return the first element in the Multiset through an iterator -> O(1)
- size() - Returns how many elements are in the multiset -> O(1)
- max size() - Returns how many elements the multiset can hold -> O(1)
- empty () - Checks to see if the multiset is empty and inserts in O(1) time (x) Removes all elements from the multiset -> O(n)
- erase(x); - Inserts element x into the multiset -> O(log n)
- clear (); - Removes all instances of x -> O (log n)
Implementation of Multi set
Example 1:
#include <iostream>
#include <set>
#include <string>
#include <cstdlib>
using namespace std;
int main()
{
multiset<int> mse;
multiset<int>::iterator it, it1;
int ch, item;
while (1)
{
cout<<"\n*************"<<endl;
cout<<"Implementation of Multiset in STL"<<endl;
cout<<"\n*************"<<endl;
cout<<"1.Insert an Element into the Multiset"<<endl;
cout<<"2.Delete an Element from the Multiset"<<endl;
cout<<"3.Find out the Element in a Multiset"<<endl;
cout<<"4.Count the Elements with a particular key"<<endl;
cout<<"5.Size of the Multiset"<<endl;
cout<<"6.Display Multiset"<<endl;
cout<<"7.Exit"<<endl;
cout<<"Enter your Choice: ";
cin>>ch;
switch(ch)
{
case 1:
cout<<"Enter value to be inserted: ";
cin>>item;
if (mse.empty())
it1 = mse.insert(item);
else
it1 = mse.insert(it1, item);
break;
case 2:
cout<<"Enter value to be deleted: ";
cin>>item;
mse.erase(item);
break;
case 3:
cout<<"Enter element to find ";
cin>>item;
it = mse.find(item);
if (it != mse.end())
cout<<"Element found"<<endl;
else
cout<<"Element not found"<<endl;
break;
case 4:
cout<<"Enter element to be counted: ";
cin>>item;
cout<<item<<" appears "<<mse.count(item)<<" times."<<endl;
break;
case 5:
cout<<"Size of the Multiset: "<<mse.size()<<endl;
break;
case 6:
cout<<"Elements of the Multiset: ";
for (it = mse.begin(); it != mse.end(); it++)
cout<<*it<<" ";
cout<<endl;
break;
case 7:
exit(1);
break;
default:
cout<<"Wrong Choice Entered"<<endl;
}
}
return 0;
}
Output:
Example 2:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void show(multiset<int> s)
{
multiset<int>::iterator i;
for (i = s.begin(); i != s.end(); i++)
{
cout << *i << " ";
}
cout << endl;
}
int main()
{
cout << " Program to illustrate the working of a Multiset, in CPP \n";
cout << "*** Multisets are similar to set, with an exception that multiple elements can have same values. *** \n\n";
//Set declaration (Set of integers)
multiset<int> s;
//Filling the elements by using the insert() method.
cout << "\n\nFilling the Multiset with integers in random order."; //Multiset automatically stores them in order
s.insert(5);
s.insert(39);
s.insert(5);
s.insert(82);
s.insert(39);
s.insert(54);
cout << "\n\nThe number of elements in the Multiset are: " << s.size();
cout << "\n\nThe elements of the Multiset are: ";
show(s);
multiset<int>::iterator it;
s.erase(s.begin(), s.find(54));
cout << "\n\nAfter deleting all the elements which are less than 54, the Multiset become as : ";
for (it = s.begin(); it != s.end(); it++)
{
cout << " " << *it;
}
cout << "\n\n\n";
return 0;
}
Output:
Example 3:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
multiset<int, greater<int> > g1;
// insert elements in random order
g1.insert(40);
g1.insert(30);
g1.insert(60);
g1.insert(20);
g1.insert(50);
// 50 will be added again to
// the multiset unlike set
g1.insert(50);
g1.insert(10);
// printing multiset g1
multiset<int, greater<int> >::iterator itr;
cout << "\nThe multiset g1 is : \n";
for (itr = g1.begin(); itr != g1.end(); ++itr) {
cout << *itr << " ";
}
cout << endl;
// assigning the elements from g1 to g2
multiset<int> g2(g1.begin(), g1.end());
cout << "\nThe multiset g2 \n"
"after assign from g1 is : \n";
for (itr = g2.begin(); itr != g2.end(); ++itr) {
cout << *itr << " ";
}
cout << endl;
// remove all elements up to element
// with value 30 in g2
cout << "\ng2 after removal \n"
"of elements less than 30 : \n";
g2.erase(g2.begin(), g2.find(30));
for (itr = g2.begin(); itr != g2.end(); ++itr) {
cout << *itr << " ";
}
// remove all elements with value 50 in gquiz2
int num;
num = g2.erase(50);
cout << "\ng2.erase(50) : \n";
cout << num << " removed \n";
for (itr = g2.begin(); itr != g2.end(); ++itr) {
cout << *itr << " ";
}
cout << endl;
// lower bound and upper bound for multiset g1
cout << "\ng1.lower_bound(40) : \n"
<< *g1.lower_bound(40) << endl;
cout << "g1.upper_bound(40) : \n"
<< *g1.upper_bound(40) << endl;
// lower bound and upper bound for multiset g2
cout << "g2.lower_bound(40) : \n"
<< *g2.lower_bound(40) << endl;
cout << "g2.upper_bound(40) : \n"
<< *g2.upper_bound(40) << endl;
return 0;
}
Output:
The multiset g1 is :
60 50 50 40 30 20 10
The multiset g2
after assign from g1 is :
10 20 30 40 50 50 60
g2 after removal
of elements less than 30 :
30 40 50 50 60
g2.erase(50) :
2 removed
30 40 60
g1.lower_bound(40) :
40
g1.upper_bound(40) :
30
g2.lower_bound(40) :
40
g2.upper_bound(40) :
60