Hi everyone

In this tutorial we will talk about Flat Multimap

So, What is Flat Multimap actually?

Flat Multimap is an associative container of C++ STL that stores data in key–value pairs. It is basically a combination of two containers we already know —

• • • • From flat_map, it takes the cache-friendly layout — two parallel sorted vectors, one for keys and one for values
      • From multimap, it takes the ability to allow duplicate keys

Like multimap, it does not have the [ ] subscript operator or the at() method — with duplicate keys, it is not clear which value those should return. All lookups of “all values for a given key” go through equal_range().

Flat multimap is a container adaptor, just like flat_map. Its underlying data structure is a pair of sequence containers — by default two vectors, but it can also be configured to use deque. Because the data sits in contiguous memory —

• • • • Lookup is O(log n) — same as multimap, thanks to binary search on the sorted key array
      • Iteration is faster than multimap — 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 multimap is best when we build the container once and then read from it many times. If we need to insert and delete frequently, regular multimap is usually the better choice.

💡 Note on availability — Flat multimap 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_multimap.

Header File Inclusion for flat_multimap

#include <flat_map>

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

Declaration & Initialization

Declaring an empty flat multimap —

flat_multimap <int, string> studentMap;

Here, key type is int and value type is string. The flat multimap is empty right now.

Declaring a flat multimap with values —

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

flat_multimap <int, string> studentMap = {
    { 102, "Sakib" },
    { 101, "Imran" },
    { 102, "Linkon" },
    { 103, "Rafi" }
};

After Initialization studentMap will look like this —

 

key	value
101	Imran
102	Sakib
102	Linkon
103	Rafi

 

Notice two things here — even though we inserted 102 first, flat multimap has sorted the keys in ascending order. And the key 102 appears twice (once with “Sakib” and once with “Linkon”), which is perfectly valid in flat multimap.

Declaring a flat multimap with different data types —

Key and value can be of any type, even different from each other —

flat_multimap <string, int> scoreMap;
flat_multimap <char, vector<int> > charListMap;
flat_multimap <string, pair<int, int> > rangeMap;

Declaring a flat multimap in descending order of keys —

By default, flat multimap stores keys in ascending order. If we want keys in descending order, we can pass greater<> as the third template parameter —

flat_multimap <int, string, greater<int> > reverseMap;

Declaring a flat multimap with a different underlying container —

Since flat multimap is a container adaptor, we can tell it which sequence container to use for keys and values. By default both are vector, but we can switch to deque —

flat_multimap <int, string, less<int>, deque<int>, deque<string> > dequeMap;

Insertion

Insertion using insert() method with pair

Since flat multimap does not support the [ ] operator, all insertions go through the insert() method. We can insert using a pair —

flat_multimap <int, string> studentMap;

studentMap.insert(pair<int, string>(101, "Imran"));
studentMap.insert(pair<int, string>(102, "Linkon"));
studentMap.insert(pair<int, string>(102, "Sakib"));

Insertion using insert() method with make_pair

Same thing can be done with make_pair() for cleaner code —

studentMap.insert(make_pair(103, "Rafi"));

Insertion using insert() method with curly braces

We can also insert using curly braces directly —

studentMap.insert({ 104, "Tanvir" });
studentMap.insert({ 102, "Hasan" });

Insertion using emplace() method

emplace() constructs the pair in place, so it avoids an extra copy (since we are not using pair syntax explicitly) —

studentMap.emplace(105, "Shuvo");

💡 Note on bulk insertion — Inserting one element at a time into a flat multimap 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 multimap 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_map uses sorted_unique.

vector< pair<int, string> > sortedData = {
    {201, "A"}, {201, "B"}, {202, "C"}
};

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

Accessing the element

find() method

find() returns an iterator to the first occurrence of the given key, or end() if the key does not exist —

auto it = studentMap.find(102);

if (it != studentMap.end())
{
    cout << it->first << " " << it->second << endl;
}

Output will be – 102 Linkon

💡 Note on find() with duplicate keys — If the key appears multiple times, find() only returns the iterator to the first one. To get all the values for a given key, we need equal_range() (shown below).

equal_range() method

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

auto range = studentMap.equal_range(102);

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

Output will be —

102 - Linkon
102 - Sakib
102 - Hasan

This is the most common and reliable way to read all values of a given key in a flat multimap.

Accessing the underlying containers

Flat multimap lets us peek directly into the two vectors it uses internally. This is something we can only do with the flat family — multimap and unordered_multimap do not expose their internals this way.

keys() method

keys() returns a read-only reference to the underlying container that holds the keys —

const auto &keyList = studentMap.keys();

for (auto key : keyList)
{
    cout << key << " ";
}

values() method

values() returns a read-only reference to the underlying container that holds the values —

const auto &valueList = studentMap.values();

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

💡 Quick tip on keys() and values() — These are handy when we want to hand the keys or values to an algorithm that works on contiguous memory (like passing them to a C API, or feeding them into SIMD code). We get direct access to the internal vector without any copying.

Counting occurrences of a key

count() method

Since flat multimap allows duplicates, count() is actually useful — it returns the total number of elements that share the given key —

cout << studentMap.count(102) << endl;
cout << studentMap.count(101) << endl;
cout << studentMap.count(999) << endl;

Output will be —

3
1
0

contains() method

If we just want to check whether a key exists (without caring how many times), we can use contains() —

if (studentMap.contains(102))
{
    cout << "Key exists" << endl;
}

Iterating through a flat multimap

Range-based for loop

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

for (auto &element : studentMap)
{
    cout << element.first << " - " << element.second << endl;
}

Output will be —

101 - Imran
102 - Linkon
102 - Sakib
102 - Hasan
103 - Rafi
104 - Tanvir
105 - Shuvo

Using iterator

We can also iterate using iterators directly —

flat_multimap <int, string>::iterator it;

for (it = studentMap.begin(); it != studentMap.end(); it++)
{
    cout << it->first << " - " << it->second << endl;
}

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

Deletion

Deletion using erase() with key

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

int removed = studentMap.erase(102);
cout << removed << " entries removed" << endl;

Output will be – 3 entries removed

Deletion using erase() with iterator

If we only want to remove a single entry with a given key (not all of them), we need to pass an iterator —

// re-inserting some values for the next example
studentMap.insert({ 102, "Linkon" });
studentMap.insert({ 102, "Sakib" });
studentMap.insert({ 102, "Hasan" });

// now removing only the first "102" entry that find() returns
auto it = studentMap.find(102);

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

This removes only one entry for key 102, leaving the other two intact.

💡 Quick tip — erase all vs erase one — erase(key) removes every entry with that key. erase(iterator) removes only the one entry the iterator points to. Use the iterator version when you want surgical removal.

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 entries with a given key —

auto range = studentMap.equal_range(102);
studentMap.erase(range.first, range.second);

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

clear() method

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

studentMap.clear();

After clear(), studentMap will be empty.

💡 Note on deletion cost — Each erase() in a flat multimap 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 entries where key is greater than 102
erase_if(studentMap, [](const auto &e) {
    return e.first > 102;
});

Size and Empty

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

if (studentMap.empty())
{
    cout << "Flat multimap is empty" << endl;
}

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

Swapping

swap() method

STL flat multimap has a method named swap(), which swaps all the key–value pairs between two flat multimaps —

flat_multimap <int, string> mapOne = {
    { 1, "One" },
    { 1, "Uno" }
};

flat_multimap <int, string> mapTwo = {
    { 10, "Ten" },
    { 20, "Twenty" },
    { 20, "Bish" }
};

// swapping values between two flat multimaps
mapOne.swap(mapTwo);

After swapping, mapOne will have the elements of mapTwo, and mapTwo will have the elements of mapOne.

extract() and replace()

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

extract() method

extract() takes the underlying key and value containers out of the flat multimap, leaving the flat multimap empty —

auto internals = std::move(studentMap).extract();

// internals.keys is a vector<int> of keys
// internals.values is a vector<string> of values
// studentMap is now empty

replace() method

replace() does the reverse — it installs two vectors as the new underlying storage of the flat multimap —

vector<int> newKeys = { 1, 2, 2, 3 };
vector<string> newValues = { "A", "B", "B2", "C" };

studentMap.replace(std::move(newKeys), std::move(newValues));

The two vectors must have the same size, and the keys must already be sorted (but unlike flat_map, duplicates are allowed here). replace() does not re-sort or validate them.

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

lower_bound() and upper_bound()

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

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

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

flat_multimap <int, string> studentMap = {
    { 101, "Imran" },
    { 102, "Linkon" },
    { 102, "Sakib" },
    { 102, "Hasan" },
    { 103, "Rafi" }
};

auto lb = studentMap.lower_bound(102);
auto ub = studentMap.upper_bound(102);

for (auto it = lb; it != ub; it++)
{
    cout << it->first << " - " << it->second << endl;
}

Output will be —

102 - Linkon
102 - Sakib
102 - Hasan

Flat Multimap vs Multimap vs Unordered Multimap

This is the biggest question when picking between these three — so it is worth laying them side by side.

 

Property	flat_multimap	multimap	unordered_multimap
Underlying data structure	Two sorted vectors	Red-Black Tree	Hash Table
Duplicate keys	Allowed	Allowed	Allowed
Order of keys	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
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 workloads with duplicate keys	Balanced insert/delete/lookup with sorted, possibly duplicate keys	Fastest lookup with duplicate keys, order does not matter

 

Time Complexity

 

Operation	Description	Time Complexity
insert()	Insert a key–value pair	O(n)
insert(sorted_equivalent, …)	Bulk insert a pre-sorted range	O(n)
emplace()	Construct and insert a key–value pair in place	O(n)
erase(key)	Remove all elements matching the key	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 the first element with the given key	O(log n)
count()	Returns the number of elements matching the key	O(log n)
contains()	Check if a key exists	O(log n)
equal_range()	Returns a pair of iterators covering all elements with the key	O(log n)
lower_bound()	Iterator to first key not less than given key	O(log n)
upper_bound()	Iterator to first key greater than given key	O(log n)
keys() / values()	Direct access to underlying key/value containers	O(1)
extract()	Move out the underlying containers	O(1)
replace()	Install new underlying containers	O(1)
size()	Returns the number of elements	O(1)
empty()	Returns true if flat multimap is empty	O(1)
clear()	Removes all elements	O(n)
swap()	Swaps contents of two flat multimaps	O(1)
begin() / end()	Iterators to the beginning and end	O(1)

 

Applications

• • • • Read-only lookup tables where one key can map to multiple values (categories with multiple items, tags with multiple documents)
      • Timetables or schedules loaded once and queried many times (e.g., multiple events at the same time slot)
      • Dictionaries where a word can have multiple meanings, built once from a file
      • In-memory indexes in analytics workloads where multiple rows share a key
      • Embedded systems and memory-constrained environments (lower memory overhead than multimap)
      • Replacing a manually-maintained sorted vector<pair<K, V>> with duplicate keys with a proper STL container
      • Handing the underlying arrays to a C API or SIMD code using keys() and values()
      • Range queries with lower_bound() and upper_bound() where iteration speed matters

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

Until then
Happy Coding