Multiset in C++

Hi there. Today we will see how multiset works in C++. They are containers that always store elements in a specific manner. And there can be multiple elements of the same value. Also, once a value is stored in multiset, it cannot be changed. But we can either remove them or insert another element instead. The most common application of multiset is to implement binary search trees(BST). Because the elements are in order, so it becomes easy to parse them.

Now let’s look at a sample program. We will see basic functions like erase, find, insert, etc. These are helpful when you are doing competitive programming or when you are preparing for interviews.

Also read: C++ multiset swap() function

C++: program to implement multiset

As with any C++ container, multiset is also parsed using iterators. We will use iterators for printing the elements, finding lower and upper bound elements, for erasing an element, or for searching. Now let’s see the program itself.

#include<bits/stdc++.h>
using namespace std;

int main()
{
   int n,temp;
   cout<<"enter number of elements:"<<endl;
   cin>>n;
   multiset<int,less<int>> ms;
   //input demonstration
   for(int o=0;o<n;o++)
   {
    cout<<"enter "<<"element "<<(o+1)<<":"<<endl;
    cin>>temp;
    ms.insert(temp);
   }
   //iterator for printing elements
   multiset<int,less<int>>::iterator it;
   for(it=ms.begin();it!=ms.end();it++)
   {
    cout<<*it<<" ";
   }
   cout<<endl;
    
  //removing elements from multiset
  cout<<"enter the element you want to erase:"<<endl;
  int erase_num;
  cin>>erase_num;
  int op=ms.erase(erase_num);
  cout<<"The multiset after removal of specified element becomes:"<<endl;
  multiset<int,less<int>>::iterator it2;
  for(it2=ms.begin();it2!=ms.end();it2++)
  {
    cout<<*it2<<" ";
  }
  cout<<endl;
  //lower bound,upper bound for multiset
  int lower_bound_element,upper_bound_element;
  cout<<"Enter the element for which you want to calculate the lower_bound:";
  cin>>lower_bound_element;
  cout<<*ms.lower_bound(lower_bound_element)<<endl;
  cout<<"Enter the element for which you want to calculate the upper_bound:";
  cin>>upper_bound_element;
  cout<<*ms.upper_bound(upper_bound_element)<<endl;

  //searching for elements using find and then erasing it
  int find_element;
  multiset<int,less<int>>::iterator it3;
  cout<<"enter the element you want to find:"<<endl;
  cin>>find_element;
  it3=ms.find(find_element);
  ms.erase(it3);
  multiset<int,less<int>>::iterator it4;
  cout<<"Multiset after the searched element is erased:"<<endl;
  for(it4=ms.begin();it4!=ms.end();it4++)
  {
    cout<<*it4<<" ";
  }
  return 0;
}

As you can see, first we saw how input works. The insert method is used to enter elements. Then we delete elements using the erase method. This method also deletes the duplicates of the element you want to remove. Then we print the lower bound and upper of any element you enter. Lower bound might print the same value you enter, but it never prints lower than that value. Finally, we see how the find method works for searching a value. In our case, we delete the search value.

Let’s see the output now.

enter number of elements:
7
enter element 1:
10
enter element 2:
20
enter element 3:
30
enter element 4:
40
enter element 5:
50
enter element 6:
50
enter element 7:
60
10 20 30 40 50 50 60
enter the element you want to erase:
50
The multiset after removal of specified element becomes:
10 20 30 40 60
Enter the element for which you want to calculate the lower_bound:30
30
Enter the element for which you want to calculate the upper_bound:30
40
enter the element you want to find:
20
Multiset after the searched element is erased:
10 30 40 60

I hope you found this article useful. For further practice, you can see the other methods for multiset, like swap, clear, etc. That will enhance your grasp on multiset.

Also read: C++ program for best fit algorithm

Leave a Reply