Unordered Multiset

Leave a Comment / C++ STL / By

Hi everyone ✋

In this tutorial we will talk about Unordered Multiset

So, What is Unordered Multiset actually?

Unordered Multiset is an associative container of C++ STL that stores elements as keys — there are no associated values (that is the job of map and multimap). It is basically a combination of two containers we already know —

        • From unordered_set, it takes the hash table backing and the fast O(1) average lookup (no sorting, no specific order)
        • From multiset, it takes the ability to allow duplicate values

Just like unordered_set, it does not keep elements in any sorted order. And just like multiset, it keeps every duplicate happily — nothing is silently dropped.

Just like set and multiset, unordered multiset does not have the [ ] subscript operator or the at() method — there are no values to look up, only keys.

Unordered Multiset’s underlying data structure is a Hash Table. Because of hashing, all its major operations — insertion, deletion, search — take O(1) time on average. In the worst case (when many keys hash to the same bucket) the operations can go up to O(n), but in practice this is very rare.

Header File Inclusion for unordered_multiset

#include <unordered_set>

Unordered multiset comes from the same header as unordered_set, so we include <unordered_set> for it.

Declaration & Initialization

Declaring an empty unordered multiset —


unordered_multiset <int> numbers;

The unordered multiset is empty right now.

Declaring an unordered multiset with values —

From C++11 onwards, we can initialize an unordered multiset with values using curly braces —


unordered_multiset <int> numbers = { 10, 20, 30, 40, 50 };

After Initialization numbers may look like this —

 

30 50 10 40 20

 

Notice that the elements are not in the order we inserted them (10, 20, 30, 40, 50). Since unordered multiset does not keep elements sorted, the actual order depends on the hash function and can be different on different machines or compilers.

Declaring an unordered multiset with duplicate values —

Unlike unordered_set, unordered multiset keeps the duplicates —


unordered_multiset <int> numbers = { 10, 20, 30, 20, 40, 10, 50 };

All 7 values are kept. The order of keys is hash-dependent, but elements that share the same value will land in the same bucket and appear next to each other during iteration. So numbers may look something like this —

 

30 50 10 10 40 20 20

 

This is the main reason to reach for unordered multiset over unordered_set — when duplicates matter and we still want O(1) average lookup.

Declaring unordered multisets of different types —

Element type can be anything that has a valid hash function —


unordered_multiset <double> scores;
unordered_multiset <string> nameList;
unordered_multiset <char> letters;

💡 Quick tip on element types — Since unordered multiset relies on hashing, the element type must have a valid hash function. All built-in types (int, string, char, double, etc.) work out of the box. But for custom types or pair, we need to provide our own hash function. We will see this in a bit.

Insertion

Insertion using insert() method

The main way to add elements to an unordered multiset is the insert() method —


unordered_multiset <int> numbers;

numbers.insert(20);
numbers.insert(50);
numbers.insert(10);
numbers.insert(40);
numbers.insert(30);

Inserting a duplicate value

Unlike unordered_set, unordered multiset keeps duplicates happily —


numbers.insert(30);
numbers.insert(30);

Now there are three 30s in numbers, and they all live in the same bucket.

💡 Quick tip on insert() return value — Unlike unordered_set, unordered multiset’s insert() always succeeds. So it returns a single iterator pointing to the inserted element — not a pair<iterator, bool>. There is nothing to fail, since duplicates are allowed.


auto it = numbers.insert(30);
cout << *it << endl;

Insertion using emplace() method

emplace() constructs the element in place, avoiding an extra copy —


numbers.emplace(60);
numbers.emplace(60);

Insertion using insert() and emplace_hint() with a position hint

Both insert() and emplace() have overloads that take an iterator as a position hint, suggesting where the new element should go —


auto it = numbers.begin();

numbers.insert(it, 80);
numbers.emplace_hint(it, 90);

💡 Note on hints in unordered containers — Unlike tree-based containers (set, multiset, map, multimap) where a good hint can speed up insertion, unordered containers decide placement using the hash function — the hint is mostly ignored. It is there for API compatibility, not for performance. Use the regular insert() / emplace() unless you are writing generic code that should work for both ordered and unordered containers.

Inserting a range of values

We can also insert a range of values from another container —


vector <int> extra = { 70, 80, 70, 90 };

numbers.insert(extra.begin(), extra.end());

Notice that even the duplicate 70 inside extra is kept — unordered multiset does not filter anything out.

Accessing the element

Unordered multiset does not support [ ] or at(). Access happens through iterators returned by find(), or by iterating through the unordered multiset directly.

find() method

find() returns an iterator to one occurrence of the element if it exists, otherwise it returns end() —


auto it = numbers.find(30);

if (it != numbers.end())
{
    cout << "Found " << *it << endl;
}
else
{
    cout << "Not found" << endl;
}

Output will be – Found 30

💡 Note on find() with duplicates — If the value appears multiple times, find() only returns an iterator to one of them. To walk through all occurrences of a value, we need equal_range().

equal_range() method

equal_range() returns a pair of iterators — the first one points to the start of the range of elements equal to the given value, and the second one points just past the end of that range.


unordered_multiset <int> numbers = { 10, 20, 30, 30, 30, 40, 50 };

auto range = numbers.equal_range(30);

for (auto it = range.first; it != range.second; it++)
{
    cout << *it << " ";
}

Output will be – 30 30 30

This is the most common and reliable way to read all occurrences of a value in an unordered multiset.

Counting occurrences of a value

count() method

Since unordered multiset allows duplicates, count() is actually useful — it returns the total number of elements equal to the given value —


cout << numbers.count(30) << endl;
cout << numbers.count(10) << endl;
cout << numbers.count(999) << endl;

Output will be —


3
1
0

contains() method (C++20)

From C++20 onwards, if we just want to check whether a value exists (without caring how many times), we can use contains() —


if (numbers.contains(30))
{
    cout << "30 exists" << endl;
}

Iterating through an unordered multiset

Range-based for loop

The cleanest way to iterate through an unordered multiset is using a range-based for loop —


for (auto &value : numbers)
{
    cout << value << " ";
}

Output may be something like —


50 10 30 30 30 40 20

Using iterator

We can also iterate using iterators directly —


unordered_multiset <int>::iterator it;

for (it = numbers.begin(); it != numbers.end(); it++)
{
    cout << *it << " ";
}

💡 Note on iteration order — The overall order of elements is unpredictable (depends on the hash function), but elements sharing the same value always appear together in the iteration. If we need the elements sorted, we should use multiset instead.

Deletion

Deletion using erase() with value

If we pass a value directly to erase(), it removes all occurrences of that value, and returns how many were removed —


unordered_multiset <int> numbers = { 10, 20, 30, 30, 30, 40, 50 };

int removed = numbers.erase(30);
cout << removed << " entries removed" << endl;

Output will be – 3 entries removed

Deletion using erase() with iterator

If we only want to remove a single occurrence of a value (not all of them), we need to pass an iterator —


// re-inserting some 30s for this example
numbers.insert(30);
numbers.insert(30);
numbers.insert(30);

// now removing only one 30
auto it = numbers.find(30);

if (it != numbers.end())
{
    numbers.erase(it);
}

This removes only one 30, leaving the other two 30s intact.

💡 Quick tip — erase all vs erase one — erase(value) removes every occurrence of that value. erase(iterator) removes only the one element the iterator points to. Use the iterator version when you want surgical removal of a single duplicate.

Deletion using erase() with range

We can also delete a range of elements. A very common pattern is to combine this with equal_range() to remove all occurrences of a value —


auto range = numbers.equal_range(30);
numbers.erase(range.first, range.second);

This does the same thing as erase(30), just expressed with iterators.

clear() method

If we want to remove all elements of the unordered multiset, we can use clear() —


numbers.clear();

After clear(), numbers will be empty.

Size and Empty


cout << numbers.size() << endl;

if (numbers.empty())
{
    cout << "Unordered multiset is empty" << endl;
}

size() returns the total number of elements (counting duplicates), and empty() returns true if the unordered multiset has no elements.

max_size() method

Returns the maximum number of elements the unordered multiset can theoretically hold —


cout << numbers.max_size() << endl;

This is bounded by the system and the allocator, and is usually a very large number — rarely the actual limit we will hit in practice.

Swapping

swap() method

STL unordered multiset has a method named swap(), which swaps all the elements between two unordered multisets —


unordered_multiset <int> setOne = { 1, 2, 2, 3 };
unordered_multiset <int> setTwo = { 10, 20, 30, 30, 40, 50 };

// swapping values between two unordered multisets
setOne.swap(setTwo);

After swapping, setOne will have the elements of setTwo, and setTwo will have the elements of setOne.

Node Handle Operations (C++17)

From C++17 onwards, unordered multiset supports node handle operations — extract() and merge(). These let us move elements between containers without copying them, and without allocating memory for them again.

extract() method

extract() removes an element from the unordered multiset and returns its node handle — a small object that owns the underlying node. The node can later be inserted into another compatible container.


unordered_multiset <int> numbers = { 10, 20, 30, 30, 40 };

auto node = numbers.extract(30);

if (!node.empty())
{
    cout << "Extracted " << node.value() << endl;
}

Output will be – Extracted 30

extract() comes in two flavors — pass a value to extract one occurrence of that value, or pass an iterator to extract that exact element. After extract(), numbers has only one 30 left (since extract by value removes a single occurrence, not all of them).

merge() method

merge() takes another unordered multiset (with the same key type, hash, and key equality) and moves all of its elements into the calling unordered multiset. The source becomes empty afterwards.


unordered_multiset <int> setOne = { 10, 20, 30 };
unordered_multiset <int> setTwo = { 30, 40, 50 };

setOne.merge(setTwo);

After merge(), setOne contains { 10, 20, 30, 30, 40, 50 } in some hash-dependent order, and setTwo is empty. Note that the duplicate 30 from setTwo is kept — that is the multiset behavior.

💡 Why use extract() and merge()? — Both operations move nodes instead of copying them. So even if the element type is expensive to copy (like a long string or a heavy struct), moving thousands of elements between two unordered multisets stays cheap. This is especially useful when reorganizing data between containers in performance-sensitive code.

Unordered Multiset with pair as element

Sometimes we want to use a pair as the element — for example, to store (x, y) coordinates where the same point can repeat. But if we try this directly —


// this will give a compile error
unordered_multiset < pair<int, int> > points;

We will get a compile error. The reason is that STL does not provide a default hash function for pair. We need to provide our own.

Writing a custom hash function —


struct pairHash
{
    size_t operator()(const pair<int, int> &p) const
    {
        // combine hashes of the two elements
        return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
    }
};

unordered_multiset < pair<int, int>, pairHash > points;

points.insert({ 1, 2 });
points.insert({ 3, 4 });
points.insert({ 1, 2 }); // duplicate is kept this time

Counting how many times a point appears —


cout << points.count({ 1, 2 }) << endl;

Output will be – 2

💡 Note on custom hash — The hash function must be deterministic (same input always gives same output) and should spread the elements as evenly as possible across buckets. A poor hash function can push the performance from O(1) down to O(n).

Bucket Interface

Unordered multiset stores its elements in buckets. Each bucket holds elements that hash to the same index. All copies of the same value naturally land in the same bucket — that is why equal_range() is so fast. STL gives us a few methods to peek into this bucket structure.

bucket_count() method

Returns the total number of buckets currently in the unordered multiset —


cout << numbers.bucket_count() << endl;

max_bucket_count() method

Returns the maximum number of buckets the unordered multiset can theoretically hold —


cout << numbers.max_bucket_count() << endl;

This is mostly an upper bound exposed by the implementation — usually not a number we hit in practice.

bucket() method

Returns the bucket number where a given element is stored —


cout << numbers.bucket(30) << endl;

bucket_size() method

Returns the number of elements in a given bucket. This is especially useful in unordered multiset since duplicates pile up in the same bucket —


size_t b = numbers.bucket(30);
cout << numbers.bucket_size(b) << endl;

Local iterators — begin(n) / end(n)

Apart from the regular begin() / end() that walk through every element, unordered multiset also gives us local iterators that walk through elements of a single bucket. We pass the bucket number to begin() and end() —


unordered_multiset <int> numbers = { 10, 20, 30, 30, 30, 40, 50 };

size_t b = numbers.bucket(30);

for (auto it = numbers.begin(b); it != numbers.end(b); it++)
{
    cout << *it << " ";
}

Output will be something like – 30 30 30

Since all duplicates of a value land in the same bucket, walking just that bucket is essentially the same as walking equal_range() for that value (in the common case where no other key collides into the same bucket). This is a very specific tool, but it is a natural fit for unordered multiset because of how duplicates pile up.

💡 Local iterators vs equal_range() — equal_range() gives us exactly the elements equal to a given value, even if other keys hash to the same bucket. begin(n) / end(n) gives us everything in bucket n, which may include keys that are different but happen to hash there. For most use cases, equal_range() is what we want — local iterators are mainly handy for diagnostics or for writing our own bucket-level logic.

load_factor() method

Returns the average number of elements per bucket, calculated as size() / bucket_count(). A higher load factor means more collisions —


cout << numbers.load_factor() << endl;

max_load_factor() method

Returns (or sets) the maximum load factor that unordered multiset allows. When the actual load factor crosses this value, the unordered multiset automatically rehashes —


cout << numbers.max_load_factor() << endl;

// setting a new max load factor
numbers.max_load_factor(0.75);

rehash() method

Forces the unordered multiset to rebuild its internal bucket structure with at least the given number of buckets —


numbers.rehash(100);

reserve() method

Reserves enough buckets to hold at least the given number of elements without rehashing. This is very useful when we know how many elements we are about to insert —


// if we know we will insert around 10000 elements
numbers.reserve(10000);

💡 Quick tip on reserve() — Calling reserve() before a big batch of insertions prevents multiple rehashes during insertion and can give a noticeable speed boost.

Observers

hash_function() method

Returns the hash function object that the unordered multiset is using —


auto h = numbers.hash_function();
cout << h(30) << endl;

This prints the hash value of 30 as the unordered multiset would compute it.

key_eq() method

Returns the key equality function object — the one used to decide whether two elements are considered equal —


auto eq = numbers.key_eq();
cout << eq(30, 30) << endl;

Output will be – 1

These two observers are mostly useful when we are writing generic code that needs to work with any unordered container, or when we are debugging a custom hash and want to inspect what is happening under the hood.

Unordered Multiset vs Multiset vs Unordered Set

This is a common confusion, so it is worth a quick note. Unordered multiset sits at the intersection of two other containers we already know — it borrows hashing from unordered_set and duplicates from multiset. Looking at all three side-by-side makes the tradeoffs clear —

 

Property unordered_multiset multiset unordered_set
Underlying data structure Hash Table Red-Black Tree Hash Table
Duplicate values Allowed Allowed Not allowed
Order of elements No specific order Sorted No specific order
Insertion / Deletion / Search O(1) average, O(n) worst O(log n) O(1) average, O(n) worst
insert() return type iterator iterator pair<iterator, bool>
count() returns 0, 1, 2, 3, … (total matches) 0, 1, 2, 3, … (total matches) 0 or 1 only
lower_bound() / upper_bound() Not available Available Not available
Access to smallest / largest Not directly available O(1) via begin() / rbegin() Not directly available
Memory usage Higher (due to buckets) Lower Higher (due to buckets)
Use when We need fast lookup with duplicates, order does not matter We need sorted elements with duplicates allowed We need fast lookup, each element must be unique

 

Time Complexity

 

Operation Description Time Complexity
insert() Insert an element O(1) average, O(n) worst
insert() with hint Insert an element with a position hint O(1) average, O(n) worst
emplace() Construct and insert an element in place O(1) average, O(n) worst
emplace_hint() Construct and insert with a position hint O(1) average, O(n) worst
erase(value) Remove all elements equal to the value O(k) average, O(n) worst (k = number of matches)
erase(iterator) Remove a single element at the iterator O(1) average
extract(value) Remove and return a node handle for a single occurrence O(1) average, O(n) worst
extract(iterator) Remove and return a node handle at the iterator O(1) average
merge() Move all elements from another unordered multiset O(n) average, O(n × m) worst (n = source size)
find() Find one occurrence of the element O(1) average, O(n) worst
count() Returns the number of elements equal to the value O(k) average, O(n) worst
contains() Check if a value exists (C++20) O(1) average, O(n) worst
equal_range() Returns a pair of iterators covering all matches O(1) average, O(n) worst
size() Returns the number of elements O(1)
max_size() Returns the maximum possible number of elements O(1)
empty() Returns true if unordered multiset is empty O(1)
clear() Removes all elements O(n)
swap() Swaps contents of two unordered multisets O(1)
bucket_count() Returns the number of buckets O(1)
max_bucket_count() Returns the maximum possible number of buckets O(1)
bucket_size() Returns the number of elements in a given bucket O(1)
begin(n) / end(n) Local iterators to a single bucket O(1)
load_factor() Returns average elements per bucket O(1)
rehash() Rebuilds the bucket structure O(n) average, O(n²) worst
reserve() Reserves buckets for expected element count O(n) average, O(n²) worst
hash_function() Returns the hash function object O(1)
key_eq() Returns the key equality function object O(1)
begin() / end() Iterators to the beginning and end O(1)

 

Applications

        • Counting frequency of elements when we don’t need them sorted (frequency map without values)
        • Fast “bag” of items where duplicates matter and we want O(1) average insertion and lookup
        • Tracking how many times a tag, label, or category has been seen in a stream of events
        • Sliding window problems with duplicates where order does not matter — adding and removing elements as the window slides, while keeping count() of any value at O(1) average
        • Maintaining a multiset of seen items in graph or grid problems where duplicates carry meaning
        • Storing repeated (x, y) coordinates in 2D problems using pair as element with a custom hash
        • Counting word occurrences in text processing when alphabetical order is not needed
        • Anagram and permutation checks where character multiplicities matter and order does not
        • Any situation where multiset’s functionality is needed but sorted order is not

In the next tutorial we will talk about another useful STL container.

Until then
Happy Coding 💻 🎵

Leave a Comment

Your email address will not be published. Required fields are marked *