Hi everyone

In this tutorial we will talk about Flat Multiset

So, What is Flat Multiset actually?

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

- - - From flat_set, it takes the cache-friendly layout — a single sorted vector that keeps the elements in contiguous memory
    - From multiset, it takes the ability to allow duplicate values

Like multiset, every duplicate is kept happily — nothing is silently dropped. And just like set, multiset, and flat_set, flat multiset does not have the [ ] subscript operator or the at() method — there are no values to look up, only keys.

Think of flat multiset as flat multimap without the values — just the keys, stored in one sorted vector, with duplicates allowed.

Flat multiset is a container adaptor, just like flat_set. Its underlying data structure is a sequence container — by default a vector, but it can also be configured to use deque. That single container stores the elements in sorted order. Because the data sits in contiguous memory —

- - - Lookup is O(log n) — same as multiset, thanks to binary search on the sorted array
    - Iteration is faster than multiset — contiguous memory gives us cache locality
    - Insertion and deletion are O(n) — because inserting in the middle of a vector means shifting all elements after it

So flat multiset is best when we build the container once and then read from it many times. If we need to insert and delete frequently, regular multiset is usually the better choice.

💡 Note on availability — Flat multiset is a C++23 feature. We need a modern compiler with C++23 support (GCC 15+, Clang 20+, or MSVC 19.40+) and the -std=c++23 flag. Before C++23, we can get very similar behavior from boost::container::flat_multiset.

Header File Inclusion for flat_multiset

#include <flat_set>

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

Declaration & Initialization

Declaring an empty flat multiset —


flat_multiset <int> numbers;

The flat multiset is empty right now.

Declaring a flat multiset with values —

We can initialize a flat multiset with values using curly braces —


flat_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, flat multiset has sorted them in ascending order. That is the same behavior we see in multiset.

Declaring a flat multiset with duplicate values —

Unlike flat_set, flat multiset keeps the duplicates —


flat_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 — so the two 10s and the two 20s sit right next to each other. This is the main reason to reach for flat multiset over flat_set — when duplicates matter and we still want sorted, cache-friendly storage.

Declaring flat multisets of different types —

Element type can be anything that supports the < operator —


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

Declaring a flat multiset in descending order —

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


flat_multiset <int, greater<int> > reverseSet = { 10, 20, 20, 30 };

Declaring a flat multiset with a different underlying container —

Since flat multiset is a container adaptor, we can tell it which sequence container to use. By default it is vector, but we can switch to deque —


flat_multiset <int, less<int>, deque<int> > dequeSet;

Insertion

Since flat multiset stores only keys (no values), it does not have the [ ] subscript operator or the at() method. Flat multiset is not about looking up values by keys — it is about answering “how many times is this element present?” or iterating through the elements in sorted order.

Insertion using insert() method

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


flat_multiset <int> numbers;

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

Inserting a duplicate value

Unlike flat_set, flat multiset keeps duplicates happily —


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

Now there are three 30s in numbers, all sitting next to each other in sorted order.

💡 Quick tip on insert() return value — Unlike flat_set, flat 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 — flat multiset does not filter anything out.

💡 Note on bulk insertion — Inserting one element at a time into a flat multiset is O(n) per insert (because of the shift), which means bulk loading one-by-one is O(n²). If we already have a sorted batch of values, we can use the sorted_equivalent tag to tell flat multiset to skip re-sorting — making bulk load O(n) total. Note that this is the multi-version’s bulk-insert tag (allowing duplicates), while flat_set uses sorted_unique.
vector<int> sortedData = { 201, 201, 202, 203 };

numbers.insert(sorted_equivalent, sortedData.begin(), sortedData.end());

Accessing the element

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


flat_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 flat multiset.

Counting occurrences of a value

count() method

Since flat 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

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 flat multiset

Range-based for loop

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


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

Output will be – 10 20 30 30 30 40 50 60 60 70 70 80 90

Using iterator

We can also iterate using iterators directly —


flat_multiset <int>::iterator it;

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

💡 Note on iteration speed — Iterating a flat multiset is typically faster than iterating a multiset of the same size, even though both are O(n). The reason is memory layout — flat multiset’s elements sit in one contiguous array, which means the CPU cache can pre-load the next few entries. Multiset stores each element in a separate tree node scattered across the heap.

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 —


flat_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 flat multiset, we can use clear() —


numbers.clear();

After clear(), numbers will be empty.

💡 Note on deletion cost — Each erase() in a flat multiset is O(n) because the elements after the deleted one must shift left to close the gap. For bulk deletion, erase_if() processes the whole container in a single O(n) pass instead of O(n) per element.

erase_if() method

erase_if() is a non-member helper that removes all elements matching a predicate in one pass —


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

Size and Empty


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

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

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

Swapping

swap() method

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


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

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

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

extract() and replace()

Flat multiset gives us two unique methods — extract() and replace() — that let us rip out its underlying vector, work on it directly, and then hand it back.

extract() method

extract() takes the underlying container out of the flat multiset, leaving the flat multiset empty —


auto data = std::move(numbers).extract();

// data is a vector<int> of the elements (duplicates included)
// numbers is now empty

replace() method

replace() does the reverse — it installs a vector as the new underlying storage of the flat multiset —


vector<int> newData = { 1, 2, 2, 3, 3 };

numbers.replace(std::move(newData));

The vector must already be sorted, but unlike flat_set, duplicates are allowed here. replace() does not re-sort or validate it.

💡 Quick tip on extract/replace — This pair is useful when we want to apply some heavy transformation on the elements (for example, bulk-update or filter the whole collection). We extract, modify the raw vector directly (fast, contiguous memory), then replace — skipping the O(log n) lookup overhead that flat multiset would otherwise apply on every access.

lower_bound() and upper_bound()

Since flat multiset elements are stored in sorted order, we can use lower_bound() and upper_bound() just like we do for multiset. 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.


flat_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

Accessing the smallest and largest element

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


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

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

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

Output will be —


10
50

💡 Quick tip on min/max access — Because the elements live in one sorted array, the smallest element sits at the very front of the vector and the largest at the very back. So both extremes are right where the cache wants them — even when duplicates are present.

Flat Multiset vs Multiset vs Unordered Multiset

This is the biggest question when picking between these three — so it is worth laying them side by side. Flat multiset sits at the intersection of two containers we already know — it borrows the cache-friendly layout from flat_set and duplicates from multiset.

Property	flat_multiset	multiset	unordered_multiset
Underlying data structure	One sorted vector	Red-Black Tree	Hash Table
Duplicate values	Allowed	Allowed	Allowed
Order of elements	Sorted	Sorted	No specific order
Lookup	O(log n) with cache locality	O(log n)	O(1) average
Insertion / Deletion	O(n)	O(log n)	O(1) average
Iteration speed	Fastest (contiguous memory)	Slow (pointer chasing)	Medium
lower_bound() / upper_bound()	Available	Available	Not available
Memory usage	Lowest	Higher (tree nodes)	Highest (bucket overhead)
C++ version	C++23	C++98	C++11
Use when	Build once, read many — lookup-heavy work with duplicates	Sorted elements with duplicates, frequent insert/delete	Fastest lookup with duplicates, order does not matter

Time Complexity

Operation	Description	Time Complexity
insert()	Insert an element	O(n)
insert(sorted_equivalent)	Bulk insert a pre-sorted range	O(n)
emplace()	Construct and insert an element in place	O(n)
erase(value)	Remove all elements equal to the value	O(n)
erase(iterator)	Remove a single element at the iterator	O(n)
erase_if()	Remove all elements matching a predicate	O(n)
find()	Find one occurrence of the element	O(log n)
count()	Returns the number of elements equal to the value	O(log n)
contains()	Check if a value exists	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 value	O(log n)
upper_bound()	Iterator to first value greater than value	O(log n)
extract()	Move out the underlying container	O(1)
replace()	Install a new underlying container	O(1)
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 flat multiset is empty	O(1)
clear()	Removes all elements	O(n)
swap()	Swaps contents of two flat multisets	O(1)

Applications

- - - Read-only frequency tables built once and queried many times, where order matters and duplicates carry meaning
    - Counting occurrences of values while keeping them sorted and cache-friendly
    - A sorted “bag” of items loaded once, where the same value can appear multiple times
    - Histogram-style data where we need both the counts (via count()) and fast in-order iteration
    - Embedded systems and memory-constrained environments (lower memory overhead than multiset)
    - Replacing a manually-maintained sorted vector<T> that allows duplicates with a proper STL container
    - Range queries with lower_bound() and upper_bound() where iteration speed matters and duplicates are expected
    - Any situation where multiset’s functionality is needed but the workload is read-heavy after an initial build

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

Until then
Happy Coding