Hi everyone

In this tutorial we will talk about Flat Map

So, What is Flat Map actually?

Flat Map is an associative container of C++ STL that stores data in key–value pairs, just like map. Each key inside a flat map is unique, and the elements are kept sorted by key automatically. From the outside, it looks and behaves almost exactly like map.

The difference shows up on the inside. Instead of a tree, flat map keeps its data in two parallel arrays — one holding the sorted keys and another holding the corresponding values at the same index. Because the data sits in contiguous memory, flat map is much more cache-friendly than map.

Flat map is a container adaptor (like stack, queue, and priority queue). Its underlying data structure is a pair of sequence containers — by default two vectors, but it can also be configured to use deque. The first vector stores keys in sorted order, the second stores values.

Because of this layout —

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

💡 Note on availability — Flat map 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_map.

Header File Inclusion for flat_map

#include <flat_map>

Declaration & Initialization

Declaring an empty flat map —


flat_map <int, string> studentMap;

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

Declaring a flat map with values —

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


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

After Initialization studentMap will look like this —

key	value
101	Imran
102	Linkon
103	Sakib

Notice that even though we inserted the values in the order 103, 101, 102, flat map has sorted them in ascending order by key. That is the same behavior we see in map.

Declaring a flat map with different data types —

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


flat_map <string, int> ageMap;
flat_map <char, vector<int> > charListMap;
flat_map <string, pair<int, int> > rangeMap;

Declaring a flat map in descending order of keys —

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


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

Declaring a flat map with a different underlying container —

Since flat map 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_map <int, string, less<int>, deque<int>, deque<string> > dequeMap;

Insertion

Insertion using [ ] subscript operator

The easiest way to insert a key–value pair is by using the [ ] operator —


flat_map <int, string> studentMap;

studentMap[101] = "Imran";
studentMap[102] = "Linkon";
studentMap[103] = "Sakib";

Insertion using insert() method with pair

We can also insert values using the insert() method with a pair —


studentMap.insert(pair<int, string>(104, "Rafi"));

Insertion using insert() method with make_pair

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


studentMap.insert(make_pair(105, "Tanvir"));

Insertion using insert() method with curly braces

We can also insert using curly braces directly —


studentMap.insert({ 106, "Shuvo" });

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(107, "Hasan");

💡 Quick tip on duplicate keys — Since flat map keys are unique, if we try to insert a key that already exists using insert() or emplace(), the insertion will be ignored (old value stays). But if we use the [ ] operator, the old value will be overwritten. Choose carefully based on what we want.

Insertion using insert_or_assign() method

If we want the behavior of “insert if new, update if exists” explicitly, we can use insert_or_assign() —


studentMap.insert_or_assign(101, "Imran Hossain");

Now the value of key 101 will be updated to “Imran Hossain”.

Insertion using try_emplace() method

try_emplace() constructs the value in place, but only if the key does not already exist. If the key is already there, nothing happens —


studentMap.try_emplace(108, "Fahim");
studentMap.try_emplace(101, "Someone Else"); // ignored, 101 already exists

💡 Note on bulk insertion — Inserting one element at a time into a flat map 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_unique tag to tell flat map to skip re-sorting — making bulk load O(n) total.
vector< pair<int, string> > sortedData = {
    {201, "A"}, {202, "B"}, {203, "C"}
};

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

Accessing the element

[ ] subscript operator

We can access the value of a given key using the [ ] operator —


cout << studentMap[102] << endl;

Output will be – Linkon

💡 Quick tip on [ ] operator — If the key does not exist, the [ ] operator will create a new entry with that key and a default value (empty string, 0, etc.). This can silently add unwanted entries to our flat map. If we just want to read, prefer at() or find() instead.

at() method

at() method also returns the value of a given key. But unlike [ ], it does not create a new entry if the key is missing — it throws an out_of_range exception instead —


cout << studentMap.at(103) << endl;

Output will be – Sakib

find() method

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


auto it = studentMap.find(104);

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

Output will be – 104 Rafi

Accessing the underlying containers

Flat map lets us peek directly into the two vectors it uses internally. This is something we can only do with flat map — map and unordered_map 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.

Checking if a key exists

count() method

Since keys are unique, count() returns either 0 (not present) or 1 (present) —


if (studentMap.count(105))
{
    cout << "Key exists" << endl;
}

contains() method

We can also use contains() for a cleaner check —


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

Iterating through a flat map

Range-based for loop

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


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

Output will be —


101 - Imran Hossain
102 - Linkon
103 - Sakib
104 - Rafi
105 - Tanvir
106 - Shuvo
107 - Hasan
108 - Fahim

Using iterator

We can also iterate using iterators directly —


flat_map <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 map is typically faster than iterating a map of the same size, even though both are O(n). The reason is memory layout — flat map’s keys and values sit in contiguous arrays, which means the CPU cache can pre-load the next few entries. Map stores each entry in a separate tree node scattered across the heap.

Deletion

Deletion using erase() with key

We can delete a specific key–value pair by passing the key directly to erase() —


studentMap.erase(102);

After deletion, the entry with key 102 will be removed from the flat map.

Deletion using erase() with iterator

We can also delete using an iterator —


auto it = studentMap.find(104);

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

Deletion using erase() with range

We can delete a range of elements by passing the start and end iterators —


studentMap.erase(studentMap.find(105), studentMap.end());

clear() method

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


studentMap.clear();

After clear(), studentMap will be empty.

💡 Note on deletion cost — Each erase() in a flat map 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 105
erase_if(studentMap, [](const auto &e) {
    return e.first > 105;
});

Size and Empty


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

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

size() returns the number of elements, and empty() returns true if the flat map has no elements.

Swapping

swap() method

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


flat_map <int, string> mapOne = {
    { 1, "One" },
    { 2, "Two" }
};

flat_map <int, string> mapTwo = {
    { 10, "Ten" },
    { 20, "Twenty" },
    { 30, "Thirty" }
};

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

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

extract() and replace()

Flat map 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 map, leaving the flat map 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 map —


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

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

The two vectors must have the same size, and the keys must already be sorted and unique. 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 map would otherwise apply on every access.

lower_bound() and upper_bound()

Since flat map keys are stored in sorted order, we can use lower_bound() and upper_bound() just like we do for map.

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_map <int, string> studentMap = {
    { 101, "Imran" },
    { 103, "Sakib" },
    { 105, "Tanvir" },
    { 107, "Hasan" }
};

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

cout << lb->first << " " << lb->second << endl;
cout << ub->first << " " << ub->second << endl;