Hi everyone

In this tutorial we will talk about Flat Set

So, What is Flat Set actually?

Flat Set is an associative container of C++ STL that stores only unique elements, just like set. Each element inside a flat set is a key — there are no associated values (that is the job of flat map). The elements are always kept sorted in ascending order automatically. From the outside, it looks and behaves almost exactly like set.

The difference shows up on the inside. Instead of a tree, flat set keeps its data in a single sorted array. Because the data sits in contiguous memory, flat set is much more cache-friendly than set.

Think of flat set as flat map without the values — just the keys, stored in one sorted vector.

Flat set is a container adaptor (like stack, queue, and priority queue). 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 of this layout —

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

💡 Note on availability — Flat set 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_set.

Header File Inclusion for flat_set

#include <flat_set>

Declaration & Initialization

Declaring an empty flat set —


flat_set <int> numbers;

The flat set is empty right now.

Declaring a flat set with values —

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


flat_set <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 set has sorted them in ascending order. That is the same behavior we see in set.

Declaring a flat set with duplicate values —

If we try to initialize a flat set with duplicate values, the duplicates are silently dropped —


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

After Initialization numbers will look like this —

The duplicate 10 and 20 were ignored. Just like set, deduplication is one of the most common uses of flat set.

Declaring flat sets of different types —

Element type can be anything that supports the < operator —


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

Declaring a flat set in descending order —

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


flat_set <int, greater<int> > reverseSet = { 10, 20, 30, 40, 50 };

After Initialization reverseSet will look like this —

Declaring a flat set with a different underlying container —

Since flat set 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_set <int, less<int>, deque<int> > dequeSet;

Insertion

Since flat set stores only unique keys, it does not have the [ ] subscript operator or the at() method. Flat set is not about looking up values by keys — it is about answering the question “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 set is the insert() method —


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

If we try to insert a value that already exists, the insertion is silently ignored —


numbers.insert(30);

numbers will still look like this —

💡 Quick tip on insert() return value — insert() actually returns a pair<iterator, bool>. The bool tells us whether the insertion actually happened (true) or the value was already there (false). This is useful when we want to check for duplicates during insertion.
auto result = numbers.insert(30);

if (result.second)
{
    cout << "Inserted successfully" << endl;
}
else
{
    cout << "Already exists" << endl;
}

Insertion using emplace() method

emplace() constructs the element in place, avoiding an extra copy —


numbers.emplace(60);
numbers.emplace(70);

Inserting a range of values

We can also insert a range of values from another container —


vector <int> extra = { 80, 90, 100 };

numbers.insert(extra.begin(), extra.end());

💡 Note on bulk insertion — Inserting one element at a time into a flat set 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 with no duplicates, we can use the sorted_unique tag to tell flat set to skip re-sorting — making bulk load O(n) total.
vector<int> sortedData = { 201, 202, 203, 204 };

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

Accessing the element

Flat set does not support [ ] or at(). Access happens through iterators returned by find(), or by iterating through the flat set directly.

find() method

find() returns an iterator to 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

Checking if an element exists

count() method

Since flat set elements are unique, count() returns either 0 (not present) or 1 (present) —


if (numbers.count(30))
{
    cout << "30 is in the flat set" << endl;
}

contains() method

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


if (numbers.contains(30))
{
    cout << "30 is in the flat set" << endl;
}

Iterating through a flat set

Range-based for loop

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


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

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

Using iterator

We can also iterate using iterators directly —


flat_set <int>::iterator it;

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

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

Deletion

Deletion using erase() with value

We can delete a specific element by passing the value directly to erase() —


numbers.erase(30);

After deletion, the element 30 will be removed from the flat set.

Deletion using erase() with iterator

We can also delete using an iterator —


auto it = numbers.find(40);

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

Deletion using erase() with range

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


// removing all elements from 60 onwards
numbers.erase(numbers.find(60), numbers.end());

clear() method

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


numbers.clear();

After clear(), numbers will be empty.

💡 Note on deletion cost — Each erase() in a flat set 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 set is empty" << endl;
}

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

Swapping

swap() method

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


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

setOne will look like this —

setTwo will look like this —

Now, let’s swap the elements of two flat sets —


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

After Swapping setOne will look like this —

After Swapping setTwo will look like this —

extract() and replace()

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


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

// data is a vector<int> of the elements
// numbers is now empty

replace() method

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


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

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

The vector must already be sorted and contain no duplicates. 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 set would otherwise apply on every access.

lower_bound() and upper_bound()

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

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_set <int> numbers = { 10, 20, 30, 40, 50 };

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

cout << *lb << endl;
cout << *ub << endl;

Output will be —


30
40

These are handy for range queries — for example, finding all values in the flat set between two bounds, with the bonus of fast contiguous iteration in between.

Accessing the smallest and largest element

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


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

// 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.

Flat Set vs Set vs Unordered Set

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

Property	flat_set	set	unordered_set
Underlying data structure	One sorted vector	Red-Black Tree	Hash Table
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
Memory usage	Lowest	Higher (tree nodes)	Highest (bucket overhead)
lower_bound() / upper_bound()	Available	Available	Not available
C++ version	C++23	C++98	C++11
Use when	Build once, read many — lookup-heavy work	Balanced insert/delete with sorted keys	Fastest lookup, order does not matter

Time Complexity

Operation	Description	Time Complexity
insert()	Insert an element	O(n)
insert(sorted_unique)	Bulk insert a pre-sorted, unique range	O(n)
emplace()	Construct and insert an element in place	O(n)
erase()	Remove an element by value or iterator	O(n)
erase_if()	Remove all elements matching a predicate	O(n)
find()	Find an element	O(log n)
count()	Check if an element exists (returns 0 or 1)	O(log n)
contains()	Check if an element exists	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)
equal_range()	Returns a pair of iterators covering the key	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 set is empty	O(1)
clear()	Removes all elements	O(n)
swap()	Swaps contents of two flat sets	O(1)

Applications

- - - Configuration or whitelist tables loaded once at program start and checked many times
    - Removing duplicates from a collection when we also want sorted, cache-friendly output
    - In-memory lookup tables for read-heavy workloads where order matters
    - Small-to-medium sets where cache performance matters more than asymptotic complexity
    - Embedded systems and memory-constrained environments (lower memory overhead than set)
    - Replacing a manually-maintained sorted vector<T> with a proper STL container
    - Range queries with lower_bound() and upper_bound() where iteration speed matters
    - Implementing set operations like union, intersection, and difference (with std::set_union, std::set_intersection, std::set_difference) over contiguous data

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

Until then
Happy Coding