std::flat_map & flat_set (C++23)
Sorted containers with contiguous storage
The Problem
std::map uses tree structure (nodes scattered in memory). C++23 flat_map uses sorted vector for better cache locality.
#include <flat_map>
#include <flat_set>
// std::map: Tree structure, scattered memory
// std::flat_map: Sorted vector, contiguous memory
std::flat_map<int, std::string> map;
// Insert maintains sorted order
map[3] = "three";
map[1] = "one";
map[2] = "two";
// Memory layout: [1:"one", 2:"two", 3:"three"]
// Cache friendly for iteration!
for (const auto& [k, v] : map) {
std::cout << k << ": " << v << std::endl;
}Comparison: map vs flat_map
| Operation | std::map | std::flat_map |
|---|---|---|
| Lookup | O(log n) | O(log n) |
| Insert | O(log n) | O(n) - needs to shift elements |
| Iteration | Cache unfriendly | Cache friendly |
| Memory | Overhead per node | Contiguous, less overhead |
When to Use
Use flat_map when:
- • Few insertions, many lookups
- • Heavy iteration over elements
- • Memory locality matters
- • Container is mostly read-only after construction
Use map when:
- • Frequent insertions/deletions
- • Elements need stable addresses
- • Iterators must not invalidate
API Examples
std::flat_map<std::string, int> scores;
// Same interface as std::map
scores["Alice"] = 100;
scores.insert({"Bob", 95});
scores.emplace("Charlie", 87);
// Access
if (auto it = scores.find("Alice"); it != scores.end()) {
std::cout << it->second << std::endl;
}
// Lower/upper bound (vector binary search)
auto it = scores.lower_bound("Bob");
// Extract underlying containers (unique to flat_map!)
auto keys = scores.keys(); // View of keys
auto values = scores.values(); // View of values
// Reserve space (like vector)
scores.reserve(1000);
// Same for flat_set
std::flat_set<int> unique_numbers = {3, 1, 4, 1, 5};
// Stored as sorted vector: [1, 3, 4, 5]