Multiset

Author Gaurav Joshi

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

Before we go ahead with multiset implementation, let us first understand what a multiset is and how it's different from a set.

Sets are containers to store unique elements in the C++ STL. Elements in sets are present in sorted order. We can insert the element in the set using the set.insert() method and can delete elements using set.erase() method. If the same elements are present multiple times, the set will only store the element once, deleting all duplicates.

Like sets, multisets also work as associative containers used to store elements in sorted order (sorted according to the internal comparison object by default, it's sorted in ascending order) in the C++ STL library. Unlike sets, multisets can store duplicate elements. Both in sets and multisets underlying Data Structure is a BST.

Implementation

Code:-


// Include header files 
#include <iostream>  
#include <set>  
#include <iterator>  
  
using namespace std;  
  
int main()  
{  
    // Create an empty multiset container Multiset 01, which stores elements in Decreasing order.
    multiset <int, greater <int> > Multiset_1;   
      
    // Inserting elements with help of .insert() method in Multiset 01  
    Multiset_1.insert(40);  
    Multiset_1.insert(30);  
    Multiset_1.insert(60);  
    Multiset_1.insert(20);  
    Multiset_1.insert(50);
    
    // Adding some common elements i.e. 50 and 40
    Multiset_1.insert(50); 
    Multiset_1.insert(40); 
    
    // Unlike Set Both the common element 50 and 40 will get added in the Multiset 
      
    // Printing Multiset 01 with the help of iterator itr
    multiset <int> :: iterator itr;  
      
    cout << "\nElements of Multiset 01 are :- "<<endl;  
    
    // .begin() methods return iterator to the start of Multiset
    // .end() methods return iterator to the element following end element of the Multiset
    for (itr = Multiset_1.begin(); itr != Multiset_1.end(); ++itr)  
    {  
        cout << "  " << *itr;  
    }  
    cout << endl;  
      
    // Assigning all the elements from Multiset 01 to Multiset 02
    // Multiset 02 store elements in default Sorted Order
    multiset <int> Multiset_2(Multiset_1.begin(), Multiset_1.end());  
      
    // Printing all the elements of the Multiset 02  
    cout << "\nElements of Multiset 02 are :- "<<endl;  
    for (itr = Multiset_2.begin(); itr != Multiset_2.end(); ++itr)  
    {  
        cout << "  " << *itr;  
    }  
    cout << endl;  
      
    // Finding the Highest and Smallest element in Multiset 01  
    multiset<int>::iterator Multiset_It1, Multiset_It2;  
    Multiset_It1 =  Multiset_1.begin();  
    cout<< "\nHighest element in Multiset 01 is :- "<<*Multiset_It1;  
    
    // .end() returns iterator to the element following last element so using -- to place at last 
    Multiset_It1 = --Multiset_1.end();
    cout<< "\nSmallest element in Multiset 01 is :- "<<*Multiset_It1;
     
    // Finding the Highest and Smallest element in Multiset 02  
    Multiset_It2 =  --Multiset_2.end();  
    
    // .end() returns iterator to the element following last element so using -- to place at last 
    cout<< "\nHighest element in Multiset 02 is :-  "<<*Multiset_It2;  
    Multiset_It2 = Multiset_2.begin();
    cout<< "\nSmallest element in Multiset 01 is :- "<<*Multiset_It2;
          
    // Removing all elements up to value 30 in Multiset 2 
    cout << "\n\nElements in Multiset 02 more than or equal to 30 :-\n ";  
    
    // Using .find() method to get iterator to a particular element
    Multiset_2.erase(Multiset_2.begin(), Multiset_2.find(30));  
    for (itr = Multiset_2.begin(); itr != Multiset_2.end(); ++itr)  
    {  
      cout << "  " << *itr;  
    }  
      
    // Removing all instances of element 50 in Multiset 02  
    int num;  
    
    // .erase(50) method will remove all instances of Element 50 present in the multiset
    num = Multiset_2.erase(50);  
    cout << "\nElement in Multiset 02 after removing element 50 :-\n" ;  
    for (itr = Multiset_2.begin(); itr != Multiset_2.end(); ++itr)  
    {  
        cout << "  " << *itr;  
    }  
    
    // To insert new line     
    cout << endl<<endl;  
    
    // Printing lower bound and upper bound for Multiset 01  
    cout << "Multiset_1.lower_bound(40) :- " << *Multiset_1.lower_bound(40) << endl;  
    cout << "Multiset_2.upper_bound(40) :- " << *Multiset_1.upper_bound(40) << endl; 
    
    // Printing lower bound and upper bound for Multiset 02  
    cout << "Multiset_1.lower_bound(40) :- " << *Multiset_2.lower_bound(40) << endl;  
    cout << "Multiset_2.upper_bound(40) :- " << *Multiset_2.upper_bound(40) << endl;  
      
return 0;  
}

You can also try this code with Online C++ Compiler

Run Code

Output :-

Elements of Multiset 01 are :- 
  60  50  50  40  40  30  20
Elements of Multiset 02 are :- 
  20  30  40  40  50  50  60


Highest element in Multiset 01 is :- 60
Smallest element in Multiset 01 is :- 20
Highest element in Multiset 02 is :-  60
Smallest element in Multiset 01 is :- 20


Elements in Multiset 02 more than or equal to 30 :-
   30  40  40  50  50  60
Element in Multiset 02 after removing element 50 :-
   30  40  40  60


Multiset_1.lower_bound(40) :- 40
Multiset_2.upper_bound(40) :- 30
Multiset_1.lower_bound(40) :- 40
Multiset_2.upper_bound(40) :- 60

You can also try this code with Online C++ Compiler

Run Code

Function List

Functions	Description
insert(data)	.insert(data) helps us to add constant data in the multiset.
begin()	.begin() method returns the iterator to the first element in the multiset.
end()	It returns the iterator to the Hypothetical element that follows the last element in the Multiset.
size()	It returns the number of elements in the multiset.
max size()	.maxsize() method returns the max number of element multiset can hold.
clear()	.clear() method removes all elements present in the multiset.
lower_bound(const)	.lower_bound(const) method returns element that is most equivalent to the const .It will not go before the element const if found. Else it returns the iterator to the end
upper_bound(const)	.upper_bound(const) method returns the first element that is most equivalent to the const. It will definitely go after the element in the multiset if found. Else it returns the iterator to the end
erase()	.erase(const) method helps us to remove all the instances of the element const.
empty()	.empty() method helps to check if the multiset is empty or not. Return true if multiset is empty and false if not.
find(const)	.find() method returns the iterator to the element const if found. Else return an iterator to the end.

Must Read Lower Bound in C++

FAQs

What is a multiset?
A multiset is an associative container used to store elements in sorted order (sorted according to the internal comparison object by default, sorted in ascending order )in the C++ STL library. Unlike sets, multisets can store duplicate elements. The underlying data structure in a multiset is a BST.
How to insert data in the Multiset?
To insert an element in the Multiset, we use the .insert() method; it helps us add data in the Multiset.
What is the basic difference between a set and a multiset?
Both set and Multiset are associative containers that store data in sorted order. Set doesn't store duplicate elements. On the other hand, Multiset can store duplicate elements.

Key Takeaway

In the article, we have extensively discussed the sets and multisets in C++ STL. We have also discussed the implementation of Multiset and some of its essential functions.

We hope that this blog has helped you enhance your understanding of data structure. Suppose you would like to learn more about such content and practice some quality questions that require you to excel your preparations a notch higher. In that case, you can visit our Guided Path in Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Till then, All the best for your future endeavours, and Keep Coding.