C++ STL: unordered_multiset (Complete Guide)

Unordered_multisets in C++ are containers that are the same as unordered_sets except for the fact that they can store duplicate values. They store elements in any order but duplicated elements come together. The elements inside the unordered_multiset cannot be changed, once they are added to the set, they can only be inserted or deleted. 

They are implemented as a hash table in memory. The elements inside the unordered_multisets are organized into buckets. The elements inside these buckets are inserted using hashing. Also, the count of each value is stored, thus taking extra space. When a duplicate key is added to the set, the count of the key is incremented in the hash table. All operations take O(1) time on average and O(N) time in the worst case. 

Unordered_multiset is present in #include<unordered_set> header file. The elements inside the unordered_multiset can be accessed using iterators. 

Unordered_multiset Declaration

Syntax:

unordered_multiset <data_type> name = {initial_values};

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

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

Example:

unordered_multiset <int> s; //initializes a unordered_multiset of size 0 which stores integer values
unordered_multiset <int> s = {10, 20, 20, 30}; //initializes a unordered_multiset having initial values as 10,20,20,30

Functions on unordered_multisets

• begin(): Returns an iterator to the first element of the unordered_multiset.
  Parameters: None
  Return type: iterator
   
• end(): Returns an iterator to the element past the last element of the unordered_multiset.
  Parameters: None
  Return type: iterator
   
• size(): It tells us the size of the unordered_multiset.
  Parameters: None
  Return type: integer - total number of elements in the unordered_multiset
   
• bucket_count(): It tells us the total number of buckets in the unordered_multimap.
  Parameters: None
  Return type: integer - total number of buckets in the unordered_multimap
   
• count(element): It tells us the total number of occurrences of the element in the unordered_multiset.
  Parameters: element whose occurrences needs to be found
  Return type: integer - total number of occurrences of key in the unordered_multiset
   
• insert(element): Inserts an element in the unordered_multiset.
  Time Complexity: O(1) in the average case and O(N) in the worst case where N is the size of the unordered_multiset
  Parameters: the element to be inserted
  Return type: void
   
• erase(value) or erase(start_iterator,end_iterator): Delete elements from the unordered_multiset.
  Time Complexity: O(1) in the average case and O(N) in the worst case where N is the size of the unordered_multiset
  Parameters: the value whose occurrences has to be removed or iterators pointing to the position between which the value needs to be deleted
  Return type: The first one returns the number of elements erased and the second one returns an iterator immediately following the last element erased. 
   
• find(element): Returns an iterator pointing to the element, if the element is found else returns an iterator pointing to the end of the unordered_multiset.
  Parameters: the element which needs to be found
  Return type: iterator
   
• clear(): It deletes all the elements from the unordered_multiset.
  Parameters: None
  Return type: void
   
• empty(): It tells us whether the unordered_multiset is empty or not.
  Parameters: None
  Return type: Boolean, true if a unordered_multiset is empty else false

#include<iostream>
#include<unordered_set>

using namespace std;

int main() {
  unordered_multiset <int> s;
  for (int i = 0; i < 5; i++) {
    s.insert(i + 1);
  }
  s.insert(4);
  s.insert(5);
  s.insert(0);
  unordered_multiset <int> ::iterator it;
  cout << "Unordered_multiset contains ";
  for (it = s.begin(); it != s.end(); it++)
    cout << * it << " ";
  cout << '\n';

  s.erase(4);
  s.erase(s.find(2));
  cout << "After erasing the element, the size of unordered_multiset is " << s.size() << '\n';
  int val = 4;
  if (s.find(val) != s.end())
    cout << "The unordered_multiset contains " << val << endl;
  else
    cout << "The unordered_multiset does not contain " << val << endl;
  cout << "Elements of unordered_multiset ";
  for (it = s.begin(); it != s.end(); it++)
    cout << * it << " ";
  cout << '\n';
  cout << "No of occurrences of 5 in unordered_multiset is " << s.count(5) << "\n";
  int n = s.bucket_count();

  cout << "set has " << n << " buckets.\n";

  for (int i = 0; i < n; ++i) {
    cout << "bucket " << i << " contains:";
    for (auto it = s.begin(i); it != s.end(i); ++it)
      cout << " " << * it;
    cout << "\n";
  }

  s.clear();
  if (s.empty() == true) {
    cout << "set is empty now!";
  }
  return 0;
}

Output

Unordered_multiset contains 0 2 1 3 4 4 5 5 
After erasing the element, the size of unordered_multiset is 5
The unordered_multiset does not contain 4
Elements of unordered_multiset 0 1 3 5 5 
No of occurrences of 5 in unordered_multiset is 2
set has 11 buckets.
bucket 0 contains: 0
bucket 1 contains: 1
bucket 2 contains:
bucket 3 contains: 3
bucket 4 contains:
bucket 5 contains: 5 5
bucket 6 contains:
bucket 7 contains:
bucket 8 contains:
bucket 9 contains:
bucket 10 contains:
set is empty now!