C++ STL: multiset (Complete Guide)

Multisets in C++ are containers that are very similar to sets. Unlike sets, multisets can store duplicate elements in a sorted manner. The elements inside the multiset cannot be changed, once they are added to the multiset, they can only be inserted or deleted. A multiset is present in #include<set> header file. The elements inside the multiset can be accessed using iterators. 

Multiset Declaration

Syntax:

multiset <data_type> name = { initial_values };

data_type: data type of the elements to be stored inside the multiset

initial_values: optional parameter which initializes the multiset with the given values

Note: By default the multiset stores values in non-decreasing order. To store the values in non-increasing order, we use an inbuilt comparator function

multiset <data_type, greater <data_type>> name;

Example:

multiset <int> s; //initializes a multiset of size 0 which stores integer values arranged in non-decreasing order
multiset <int> s = { 10, 20, 30 }; //initializes a multiset having initial values as 10,20,30
multiset <int, greater <int>> s; //initializes a multiset of size 0 which stores integer values arranged in non-increasing order

Functions on multisets

• begin(): Returns an iterator to the first element of the multiset.
  Parameters: None
  Return type: iterator
   
• end(): Returns an iterator to the element past the last element of the multiset.
  Parameters: None
  Return type: iterator
   
• size(): It tells us the size of the multiset.
  Parameters: None
  Return type: integer - total number of elements in the multiset
   
• insert(element): Inserts an element in the multiset.
  Time Complexity: O(logN) where N is the size of the multiset
  Parameters: the element to be inserted
  Return type: void
   
• erase(value) or erase(start_iterator,end_iterator): Delete elements from the multiset.
  Time Complexity: O(logN) where N is the size of the multiset
  Parameters: the value to be removed or iterators pointing to the position between which the value needs to be deleted
  Return type: void
   
• find(element): Returns an iterator pointing to the element, if the element is found else returns an iterator pointing to the end of the multiset.
  Parameters: the element which needs to be found
  Return type: iterator
   
• clear(): It deletes all the elements from the multiset
  Parameters: None
  Return type: void
   
• empty(): It tells us whether the multiset is empty or not.
  Parameters: None
  Return type: Boolean, true if a multiset is empty else false

#include<iostream>
#include<set>
using namespace std;

int main() {
  multiset <int> s1;
  multiset <int, greater <int>> s2;
  for (int i = 0; i < 5; i++) {
    s1.insert(i + 1);
  }
  for (int i = 0; i < 5; i++) {
    s1.insert(i + 1);
  }
  for (int i = 0; i < 5; i++) {
    s2.insert((i + 1) * 10);
  }
  for (int i = 0; i < 5; i++) {
    s2.insert((i + 1) * 10);
  }
  set <int> ::iterator it;
  for (it = s1.begin(); it != s1.end(); it++)
    cout << * it << " ";
  cout << '\n';
  for (it = s2.begin(); it != s2.end(); it++)
    cout << * it << " ";
  cout << '\n';

  s1.erase(1);
  s2.erase(s2.begin(), s2.find(10));
  cout << "After erasing element, size of set1 is " << s1.size() << '\n';
  int val = 4;
  if (s1.find(val) != s1.end())
    cout << "The set1 contains " << val << endl;
  else
    cout << "The set1 does not contains " << val << endl;
  cout << "New elements of set1 are ";
  for (it = s1.begin(); it != s1.end(); it++)
    cout << * it << " ";
  cout << '\n';

  s1.clear();
  if (s1.empty() == true) {
    cout << "set1 is empty!";
  }
  return 0;
}

Output

1 1 2 2 3 3 4 4 5 5 
50 50 40 40 30 30 20 20 10 10 
After erasing element, size of set1 is 8
The set1 contains 4
New elements of set1 are 2 2 3 3 4 4 5 5 
set1 is empty!