What is an unordered_multiset?

At its core, std::unordered_multiset is an unordered associative container that allows the storage of multiple occurrences of elements, known as duplicates, in no particular order. It is similar to std::unordered_set, but unlike a set, it permits multiple elements with equivalent values. Each element in an unordered multiset is stored based on its hash value, enabling efficient storage and retrieval.

Understanding

Imagine you have a big box where you can put different types of toys. However, unlike your typical toy box, this one doesn't keep things organized in any particular order. You can throw in multiple toys of the same type, and they just get mixed up inside the box.

That's essentially what an unordered_multiset is like in C++. It's a special kind of container that can many items of the same kind, but doesn't care about the order in which they are put in or stored. It's like having a box where you can throw in as many toys as you want, and they all just get jumbled together.

Here's simple breakdown:

1. Unordered: Items aren't arranged in any particular order. You don't know which item comes first, second, and so on. It's like having a messy room where things are just scattered around.
2. Multiset: It's like having a container where you can put multiple instances of the same item. For example, if you have a multiset of fruits, you can put in many apples, many oranges, and so on. It doesn't restrict you to having only one of each kind.

Syntax

In order to use unordered_multiset, one must need to include the unordered_multiset library:

#include <unordered_set>

std::unordered_multiset<type> multiset_name;

Here, type refers to the data type of elements to be stored within the multiset and multi_set is the identifier chosen for the particular instance of the multiset.

Functions

1 insert()

This function is used to insert elements into the unordered_multiset. If the element already exists, it is inserted again, allowing duplicates.

std::unordered_multiset<int> mySet;
mySet.insert(10);
mySet.insert(20);
mySet.insert(10); // Inserting duplicate element

Complexity Analysis

Time Complexity -

• Average Case: O(1)
• Worst Case: O(n)

2 erase()

This function is used to remove elements from the unordered_multiset by their value.

mySet.erase(10); // Removes all occurrences of 10

Complexity Analysis:

Time Complexity -

• Average Case: O(1)
• Worst Case: O(n)

3 count()

This function retrieves the number of occurrences of a specific value within the unordered_multiset.

int occurrences = mySet.count(10); // Returns the number of occurrences of 10

Complexity Analysis:

Time Complexity -

• Average Case: O(1)
• Worst Case: O(n)