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);

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.

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 —

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.

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)
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
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)

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