Hi everyone

In this tutorial we will talk about Multiset

So, What is Multiset actually?

Multiset is an associative container of C++ STL that stores elements in sorted order, just like set. Each element is a key — there are no associated values (that is the job of map and multimap).

The one big difference from set is that multiset allows duplicate values. The same element can appear multiple times, and all of them are kept.

Think of multiset as set that does not drop duplicates. Or think of it as multimap without the values — just the keys, and duplicates are welcome.

Just like set, multiset does not have the [ ] subscript operator or the at() method. Multiset is not about looking up values by keys — it is about answering the question “how many times does this element appear?” or iterating through the elements in sorted order.

Multiset’s underlying data structure is a Self-Balancing Binary Search Tree (usually a Red-Black Tree). That is why all its major operations — insertion, deletion, search — take O(log n) time, and that is also why the elements stay sorted automatically.

Header File Inclusion for multiset

#include <set>

Multiset comes from the same header as set, so we include <set> for it.

Declaration & Initialization

Declaring an empty multiset —


multiset <int> numbers;

The multiset is empty right now.

Declaring a multiset with values —

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


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

After Initialization numbers will look like this —

Notice that even though we inserted the values in the order 50, 20, 40, 10, 30, multiset has sorted them in ascending order.

Declaring a multiset with duplicate values —

Unlike set, multiset keeps the duplicates —


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

After Initialization numbers will look like this —

All 7 values are kept, and they are sorted. This is the main reason to reach for multiset over set.

Declaring multisets of different types —

Element type can be anything that supports the < operator —


multiset <double> scores;
multiset <string> nameList;
multiset <char> letters;
multiset <pair<int, int> > points;

Declaring a multiset in descending order —

By default, multiset stores elements in ascending order. If we want elements in descending order, we can pass greater<> as the second template parameter —


multiset <int, greater<int> > reverseMultiset = { 10, 20, 30, 20, 10 };

After Initialization reverseMultiset will look like this —

Insertion

Insertion using insert() method

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


multiset <int> numbers;

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

After Insertion numbers will look like this —

Inserting a duplicate value

Unlike set, multiset keeps duplicates happily —


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

After Insertion numbers will look like this —

All three 30s stay, and they sit next to each other because multiset is sorted.

💡 Quick tip on insert() return value — Unlike set, 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 — a suggestion for where the new element should go —


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

auto it = numbers.find(40);     // points to 40

numbers.insert(it, 30);         // hint: 30 belongs just before 40
numbers.emplace_hint(it, 45);   // same idea, constructed in place

After this, numbers will look like this —

💡 Note on hints in ordered containers — Unlike unordered_multiset (where the hint is ignored, because placement is decided by the hash function), in multiset the hint actually matters. If the hint points to the element just after where the new one belongs, the insertion drops from O(log n) to amortized O(1). This is genuinely useful when inserting many already-sorted elements one by one — passing the previous iterator as the hint each time keeps every insert cheap.

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 — multiset does not filter anything out.

Accessing the element

Multiset does not support [ ] or at(). Access happens through iterators returned by find(), or by iterating through the 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 (not necessarily the first inserted). 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.


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 a multiset.

Counting occurrences of a value

count() method

Since 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 a multiset

Range-based for loop

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


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

Output will be – 10 20 30 30 30 40 50

Using iterator

We can also iterate using iterators directly —


multiset <int>::iterator it;

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

💡 Note on iteration order — Multiset always iterates elements in sorted order (ascending by default). Duplicates come out in the order they were inserted, grouped together.

Deletion

Deletion using erase() with value

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


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

After deletion numbers will look like this —

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.

erase_if() method (C++20)

From C++20 onwards, erase_if() is a non-member helper that removes all elements satisfying a predicate in a single pass, and returns how many were removed —


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

// remove all elements greater than 25
int removed = erase_if(numbers, [](int value) {
    return value > 25;
});

cout << removed << " entries removed" << endl;

Output will be – 4 entries removed

After this, numbers will look like this —

clear() method

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


numbers.clear();

After clear(), numbers will be empty.

Size and Empty


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

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

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

Swapping

swap() method

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


multiset <int> multisetOne = { 1, 2, 2, 3 };
multiset <int> multisetTwo = { 10, 20, 30, 30, 40, 50 };

multisetOne will look like this —

multisetTwo will look like this —

Now, let’s swap the elements of two multisets —


// swapping values between two multisets
multisetOne.swap(multisetTwo);

After Swapping multisetOne will look like this —

After Swapping multisetTwo will look like this —

Node Handle Operations (C++17)

From C++17 onwards, 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 multiset and returns its node handle — a small object that owns the underlying node. The node can later be inserted into another compatible container.


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). We can confirm it —


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

Output will be – 1

💡 Note on node handles in set vs map — For set and multiset, the node handle exposes the element through node.value(). For map and multimap it is split into node.key() and node.mapped() instead, since those store key-value pairs. Either way, the node can be re-inserted into another container, which is the real point of extract().

merge() method

merge() takes another multiset (or even a set, as long as it has the same comparator) and moves all of its elements into the calling multiset. The source becomes empty afterwards.


multiset <int> multisetOne = { 10, 20, 30 };
multiset <int> multisetTwo = { 30, 40, 50 };

multisetOne.merge(multisetTwo);

After merge(), multisetOne will look like this —

And multisetTwo is now empty. Note that the duplicate 30 from multisetTwo 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 multisets stays cheap. This is especially useful when reorganizing data between containers in performance-sensitive code.

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. With multiset, this works right out of the box —


multiset < pair<int, int> > points;

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

No extra setup is needed. After insertion, points is sorted and will look like this —

(1, 2)

(1, 5)

(3, 4)

The pairs are sorted lexicographically — first by the .first value, and when those tie, by the .second value. That is why (1, 2) comes before (1, 5), which comes before (3, 4). And the duplicate (1, 2) is kept, sitting right next to its twin.

Counting how many times a point appears —


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

Output will be – 2

💡 Why no custom comparator is needed (unlike unordered_multiset’s hash) — This is the key difference between the ordered and unordered containers. An ordered container like multiset only needs a way to compare two elements with <, and pair (as well as tuple and string) already provides a built-in < operator. So pair just works. An unordered container like unordered_multiset instead needs a hash function, and STL does not provide a default hash for pair — which is exactly why the unordered version forces us to write our own. If we ever want a different ordering for our pairs, we can still pass a custom comparator as the second template parameter, just like with int.

lower_bound() and upper_bound()

Since multiset elements are stored in sorted order, we can use lower_bound() and upper_bound() just like we do for set. These two together actually give us what equal_range() gives — they are used internally by equal_range() anyway.

lower_bound(value) — returns an iterator to the first element that is not less than the given value.

upper_bound(value) — returns an iterator to the first element that is strictly greater than the given value.


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

auto lb = numbers.lower_bound(30);
auto ub = numbers.upper_bound(30);

for (auto it = lb; it != ub; it++)
{
    cout << *it << " ";
}

Output will be – 30 30 30

These are also handy for range queries — for example, finding all values in the multiset between two bounds.

Accessing the smallest and largest element

Since multiset is always sorted, the smallest element is at begin() and the largest element is at rbegin() —


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

// smallest element
cout << *numbers.begin() << endl;

// largest element
cout << *numbers.rbegin() << endl;

Output will be —


10
50

💡 Quick tip on min/max access — Unlike priority_queue (which only gives us the top element), multiset gives us O(log n) access to both the smallest and largest elements, and we can remove them in O(log n) too. This makes multiset a great choice when we need to repeatedly query and remove from both extremes of a collection — even when duplicates are involved.

Observers

key_comp() and value_comp()

These return the comparison object that the multiset uses to order its elements —


auto cmp = numbers.key_comp();

cout << cmp(10, 20) << endl;   // is 10 ordered before 20?

Output will be – 1

For multiset, key_comp() and value_comp() return the same comparator, because the element is the key — there is no separate value the way there is in a map. By default this comparator is less<T>, which is exactly why elements come out in ascending order, and it is this same object we replace when we pass greater<> for a descending multiset.

💡 When do we actually use these? — Rarely in everyday code. key_comp() and value_comp() are mostly useful when writing generic code that should work with any ordered container, or when we want to reuse the container’s own ordering rule elsewhere instead of hard-coding it. They are the ordered-container counterpart to unordered_multiset’s hash_function() and key_eq().

Multiset vs Set

This is a common confusion, so it is worth a quick note —

Property	multiset	set
Underlying data structure	Red-Black Tree	Red-Black Tree
Duplicate values	Allowed	Not allowed
Order of elements	Sorted	Sorted
insert() return type	iterator	pair<iterator, bool>
count() returns	0, 1, 2, 3, … (total matches)	0 or 1 only
Use when	We need sorted elements and duplicates matter	We need sorted elements and each one must be unique

Time Complexity

Operation	Description	Time Complexity
insert()	Insert an element	O(log n)
emplace()	Construct and insert an element in place	O(log n)
insert() with hint	Insert an element with a position hint	O(log n), amortized O(1) with a good hint
emplace_hint()	Construct and insert with a position hint	O(log n), amortized O(1) with a good hint
erase(value)	Remove all elements equal to the value	O(log n + k) where k is the number of matches
erase(iterator)	Remove a single element at the iterator	O(1) amortized
erase_if()	Remove all elements matching a predicate (C++20)	O(n)
extract(value)	Remove and return a node handle for a single occurrence	O(log n)
extract(iterator)	Remove and return a node handle at the iterator	O(1) amortized
merge()	Move all elements from another multiset	O(n log n)
find()	Find one occurrence of the element	O(log n)
count()	Returns the number of elements equal to the value	O(log n + k)
contains()	Check if a value exists (C++20)	O(log n)
equal_range()	Returns a pair of iterators covering all matches	O(log n)
lower_bound()	Iterator to first value not less than given value	O(log n)
upper_bound()	Iterator to first value greater than given value	O(log n)
begin() / end()	Iterators to the beginning and end	O(1)
rbegin() / rend()	Reverse iterators (access largest, smallest)	O(1)
size()	Returns the number of elements	O(1)
empty()	Returns true if multiset is empty	O(1)
clear()	Removes all elements	O(n)
swap()	Swaps contents of two multisets	O(1)
key_comp() / value_comp()	Returns the comparison object	O(1)

Applications

- - - Maintaining a sorted collection that keeps duplicates (unlike set)
    - Counting frequency of elements while keeping them in sorted order
    - Sliding window problems where we need both min and max of the current window and duplicates matter
    - Scheduling problems where multiple events can share the same priority or timestamp
    - Storing scores of students or match results where the same score can repeat
    - Finding the k-th smallest or largest element via iterator advance, with duplicates counted
    - Range queries with lower_bound() and upper_bound() over a collection that has duplicates
    - Implementing a sorted “bag” of items where insertions, deletions, and searches all need to be fast

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

Until then
Happy Coding