std::flat_map(C++23)
什么是 std::flat_map
std::flat_map 是 C++23 引入的容器适配器,提供与 std::map 相同的有序关联容器功能(键值对,键唯一,按键排序),但底层使用两个排序的连续容器(默认是 std::vector)分别存储键和值,而不是红黑树。
这种设计让查找操作更加缓存友好——键紧密排列在连续内存中,二分查找时减少了缓存缺失。
#include <flat_map>
std::flat_map<std::string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 82;flat_map vs map vs unordered_map
| 特性 | std::flat_map | std::map | std::unordered_map |
|---|---|---|---|
| 底层结构 | 排序的 vector 对 | 红黑树 | 哈希表 |
| 查找复杂度 | O(log n) | O(log n) | O(1) 平均 |
| 插入复杂度 | O(n)(需要移动元素) | O(log n) | O(1) 平均 |
| 删除复杂度 | O(n) | O(log n) | O(1) 平均 |
| 内存连续性 | 键和值分别连续 | 节点分散 | 桶+链表/探测 |
| 缓存友好 | 非常好 | 差 | 一般 |
| 迭代器稳定性 | 插入/删除后失效 | 稳定 | 重哈希后失效 |
| 内存开销 | 低(无节点指针) | 高(每个节点有指针) | 中等 |
| 有序遍历 | 天然有序 | 天然有序 | 无序 |
基本示例
#include <iostream>
#include <flat_map>
#include <string>
#include <vector>
// ============================
// 示例1:基本用法
// ============================
void basic_demo() {
std::flat_map<std::string, int> ages;
// 插入元素
ages["Alice"] = 25;
ages["Bob"] = 30;
ages["Charlie"] = 28;
ages.insert({"Diana", 22});
// 遍历(按键排序)
std::cout << "按姓名排序:" << std::endl;
for (const auto& [name, age] : ages) {
std::cout << " " << name << ": " << age << std::endl;
}
// Alice: 25, Bob: 30, Charlie: 28, Diana: 22
// 查找
if (auto it = ages.find("Bob"); it != ages.end()) {
std::cout << "Bob 的年龄: " << it->second << std::endl;
}
// contains(和 map 一样)
std::cout << "有 Eve: " << std::boolalpha << ages.contains("Eve") << std::endl;
}
// ============================
// 示例2:从已排序数据高效构造
// ============================
void sorted_construction_demo() {
// 如果数据已经排序,可以用 sorted_unique 标签避免重新排序
std::flat_map<int, std::string> fm(std::sorted_unique,
std::vector<int>{1, 2, 3, 4, 5},
std::vector<std::string>{"one", "two", "three", "four", "five"}
);
for (const auto& [k, v] : fm) {
std::cout << k << " -> " << v << std::endl;
}
}
// ============================
// 示例3:访问底层容器
// ============================
void underlying_demo() {
std::flat_map<std::string, int> scores = {
{"Alice", 95}, {"Bob", 82}, {"Charlie", 78}
};
// 直接访问键容器和值容器
const auto& keys = scores.keys();
const auto& values = scores.values();
std::cout << "键: ";
for (const auto& k : keys) std::cout << k << " ";
std::cout << std::endl;
std::cout << "值: ";
for (int v : values) std::cout << v << " ";
std::cout << std::endl;
// 值容器是连续内存,可以直接获取指针
const int* data_ptr = values.data();
std::cout << "第一个值的地址: " << data_ptr << std::endl;
}
// ============================
// 示例4:批量插入
// ============================
void batch_insert_demo() {
std::flat_map<int, std::string> fm;
// 批量插入比逐个插入更高效
std::vector<std::pair<int, std::string>> data = {
{5, "five"}, {1, "one"}, {3, "three"}, {2, "two"}, {4, "four"}
};
fm.insert(data.begin(), data.end());
for (const auto& [k, v] : fm) {
std::cout << k << ": " << v << std::endl;
}
}
// ============================
// 示例5:自定义比较器
// ============================
void custom_compare_demo() {
// 按降序排列
std::flat_map<int, std::string, std::greater<>> fm = {
{1, "one"}, {3, "three"}, {2, "two"}
};
std::cout << "降序:" << std::endl;
for (const auto& [k, v] : fm) {
std::cout << " " << k << ": " << v << std::endl;
}
// 3: three, 2: two, 1: one
}
// ============================
// 示例6:extract 和 replace
// ============================
void extract_demo() {
std::flat_map<std::string, int> fm = {
{"Alice", 95}, {"Bob", 82}, {"Charlie", 78}
};
// extract 取出底层容器
auto containers = std::move(fm).extract();
// containers.keys 和 containers.values 现在可以直接操作
auto& keys = containers.keys;
auto& vals = containers.values;
std::cout << "提取后的键: ";
for (const auto& k : keys) std::cout << k << " ";
std::cout << std::endl;
// replace 放回
// fm.replace(std::move(keys), std::move(vals));
}
// ============================
// 示例7:与 map 的接口兼容
// ============================
void compatibility_demo() {
std::flat_map<std::string, int> fm;
// 和 std::map 几乎相同的接口
fm.emplace("Alice", 95);
fm.try_emplace("Bob", 82);
fm.insert_or_assign("Alice", 100); // 更新已有的键
std::cout << "Alice: " << fm.at("Alice") << std::endl; // 100
// erase
fm.erase("Bob");
std::cout << "大小: " << fm.size() << std::endl;
// lower_bound / upper_bound
fm.insert({{"C", 1}, {"D", 2}, {"E", 3}});
auto lb = fm.lower_bound("D");
if (lb != fm.end()) {
std::cout << "lower_bound(D): " << lb->first << std::endl;
}
}
int main() {
std::cout << "=== 基本用法 ===" << std::endl;
basic_demo();
std::cout << "\n=== 已排序构造 ===" << std::endl;
sorted_construction_demo();
std::cout << "\n=== 底层容器 ===" << std::endl;
underlying_demo();
std::cout << "\n=== 批量插入 ===" << std::endl;
batch_insert_demo();
std::cout << "\n=== 自定义比较 ===" << std::endl;
custom_compare_demo();
std::cout << "\n=== 接口兼容 ===" << std::endl;
compatibility_demo();
return 0;
}何时选择 flat_map
| 场景 | 推荐 | 原因 |
|---|---|---|
| 构建后主要查找,很少修改 | flat_map | 查找缓存友好 |
| 频繁插入删除 | map | 插入删除 O(log n) |
| 需要迭代器稳定性 | map | flat_map 插入后迭代器失效 |
| 内存受限 | flat_map | 无节点指针开销 |
| 需要连续内存访问 | flat_map | keys()/values() 返回 vector |
| 元素数量小(< 几百) | flat_map | 小数据集缓存效果好 |
| 大量数据频繁修改 | map 或 unordered_map | flat_map 插入 O(n) |
适用场景
- 配置数据(构建一次,频繁查找)
- 小型查找表
- 需要有序遍历且查找性能优先
- 需要直接访问底层连续内存
- 从已排序数据构建映射
常见问题
flat_map 的插入为什么是 O(n)?
因为底层是排序的 vector,插入新元素需要移动后面所有元素来保持排序。对于大量随机插入的场景,这比 map 的 O(log n) 慢得多。
flat_map 的查找真的比 map 快吗?
对于中小规模数据,通常是的。虽然两者都是 O(log n) 二分查找,但 flat_map 的键存储在连续内存中,CPU 缓存预取可以大幅减少访问延迟。
flat_map 可以用 deque 作为底层容器吗?
可以。标准允许用 std::vector 或 std::deque 作为底层容器。用 deque 可以避免 vector 在扩容时的大块内存重新分配。
flat_map 支持 node 操作吗?
不支持。flat_map 没有 extract(node) 和 merge 等节点操作。它有自己的 extract() 和 replace() 来操作底层容器。
注意事项
- 插入和删除是 O(n) 的——不适合频繁修改的场景
- 插入和删除后所有迭代器都失效
- 底层默认使用两个 vector(键和值分开存储)
- 从已排序数据构造时用
sorted_unique标签可以跳过排序 - 不支持节点操作(extract node / merge)
- 需要
<flat_map>头文件
编译器支持情况
| 编译器 | std::flat_map | 最低版本 |
|---|---|---|
| GCC | 支持 | 15.0 |
| Clang | 部分支持 | 18.0 |
| MSVC | 支持 | 19.34 (VS 2022 17.4) |
总结
std::flat_map 是 C++23 引入的有序关联容器适配器,提供与 std::map 相同的接口,但底层使用排序的连续容器(默认 vector)存储键和值。这让查找操作更加缓存友好,内存开销更低。代价是插入和删除变成了 O(n)。flat_map 最适合"构建一次、查找多次"的场景——配置数据、小型查找表、需要有序遍历的映射等。对于频繁修改的场景,传统的 std::map 仍然是更好的选择。