深入学习 std::flat_map

头文件：<flat_map> 命名空间：std 编译器要求：C++23 起（GCC 15+ / Clang 18+ / MSVC 19.38+）

一、设计动机：std::map 的性能痛点

1.1 红黑树的缓存问题

std::map 底层是红黑树——每个节点独立分配在堆上：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
std::map 内存布局（红黑树）：

         ┌──────┐
         │ Node │ ← 堆上随机位置
         │ k=5  │
         └──┬───┘
        ┌───┴───┐
   ┌────▼──┐  ┌─▼─────┐
   │ Node  │  │ Node   │ ← 另一个堆上随机位置
   │ k=3   │  │ k=8    │
   └───────┘  └────────┘

每次查找跳转 O(log n) 个节点，每个节点可能在不同的缓存行
→ 大量 cache miss
→ 对于只读查找密集的场景，性能远不如连续内存

1.2 flat_map 的解法：排序 vector

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
std::flat_map 内存布局（两个排序 vector）：

Keys vector（连续内存）：
┌───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 3 │ 5 │ 7 │ 9 │ 12│ 15│  ← 有序排列
└───┴───┴───┴───┴───┴───┴───┘

Values vector（连续内存）：
┌───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │ F │ G │  ← 与 keys 一一对应
└───┴───┴───┴───┴───┴───┴───┘

查找 key=7：
  二分查找 keys vector → 命中索引 3 → 返回 values[3] = D
  二分查找在连续内存上进行 → CPU 预取高效 → 极少 cache miss

1.3 性能对比

操作	std::map	std::flat_map	原因
查找	O(log n)，多次 cache miss	O(log n)，极少 cache miss	连续内存二分 vs 树节点跳转
有序遍历	O(n)，频繁指针追逐	O(n)，顺序内存访问	vector 遍历 vs 树 in-order 遍历
插入/删除	O(log n)	O(n)（需移动元素）	vector 中间插入需后移所有元素
内存占用	每节点 ≥ 32 bytes 开销	几乎零开销	无节点指针/颜色位
迭代器稳定性	插入/删除不影响其他	全部失效	vector reallocation

一句话总结：flat_map 用插入性能换取查找和遍历性能——适合"少写多读"的场景。

二、核心 API

2.1 基本用法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <flat_map>
#include <string>
#include <cstdio>

int main()
{
    // 构造——与 std::map 几乎相同的接口
    std::flat_map<int, std::string> fm = {
        {3, "three"},
        {1, "one"},
        {4, "four"},
        {1, "duplicate"},  // 重复 key 被忽略
        {5, "five"}
    };

    // 自动排序——遍历时按 key 有序
    for (const auto& [key, val] : fm) {
        printf("%d -> %s\n", key, val.c_str());
    }
    // 输出：
    // 1 -> one
    // 3 -> three
    // 4 -> four
    // 5 -> five

    // 查找——二分查找，O(log n) 但 cache 友好
    auto it = fm.find(3);
    if (it != fm.end()) {
        printf("Found: %s\n", it->second.c_str());
    }

    // operator[]——不存在则插入默认值
    fm[2] = "two";

    // 删除
    fm.erase(4);

    // 大小
    printf("size: %zu\n", fm.size());
}

2.2 与 std::map 的 API 差异

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <flat_map>
#include <vector>
#include <string>

int main()
{
    std::flat_map<std::string, int> fm;

    // ✅ 相同的 API（flat_map 是 map 的近似替换）
    fm.insert({"apple", 1});
    fm.emplace("banana", 2);
    fm.try_emplace("cherry", 3);
    fm.insert_or_assign("apple", 10);
    auto it = fm.find("banana");
    auto lb = fm.lower_bound("b");
    auto ub = fm.upper_bound("c");
    bool has = fm.contains("cherry");  // C++20 风格

    // ❌ flat_map 没有的（因为底层是 vector 不是节点）：
    // fm.extract(...)    // 不支持节点操作
    // fm.merge(...)      // 不支持节点 merge

    // ✅ flat_map 独有的——直接访问底层容器
    const auto& keys = fm.keys();      // 返回 keys vector 的 const 引用
    const auto& vals = fm.values();    // 返回 values vector 的 const 引用

    printf("Keys container size: %zu\n", keys.size());
}

2.3 sorted_unique 优化构造

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <flat_map>
#include <string>

int main()
{
    // 如果数据已经排序且无重复，传入 sorted_unique 标签
    // 跳过排序步骤——O(1) 而非 O(n log n) 构造
    std::flat_map<int, std::string> fm(
        std::sorted_unique,  // 告诉 flat_map："我保证数据已排序且无重复"
        {
            std::pair{1, std::string("one")},
            std::pair{2, std::string("two")},
            std::pair{3, std::string("three")},
            std::pair{5, std::string("five")}
        }
    );

    // ⚠️ 如果实际未排序或有重复，行为未定义！
    // 只在你 100% 确定数据已排序时使用

    // 典型场景：从已排序的数据库结果集构造
    // 或从另一个有序容器转换时
}

2.4 自定义底层容器

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <flat_map>
#include <vector>
#include <deque>
#include <string>
#include <memory_resource>

// flat_map 模板参数：
// template <class Key, class T,
//           class Compare = less<Key>,
//           class KeyContainer = vector<Key>,
//           class MappedContainer = vector<T>>

// 使用 deque 作为底层容器（不需要连续内存保证时，减少大块 realloc）
std::flat_map<int, std::string,
              std::less<int>,
              std::deque<int>,           // key 用 deque 存
              std::deque<std::string>>   // value 用 deque 存
dequeMap;

// 使用 PMR vector（自定义内存分配）
void withPmr()
{
    char buffer[4096];
    std::pmr::monotonic_buffer_resource pool(buffer, sizeof(buffer));

    std::flat_map<int, std::string,
                  std::less<int>,
                  std::pmr::vector<int>,
                  std::pmr::vector<std::string>>
        pmrMap(std::less<int>{},
               std::pmr::vector<int>(&pool),
               std::pmr::vector<std::string>(&pool));

    // 所有数据都从 pool 分配——零堆分配，请求结束后统一回收
    pmrMap[1] = "hello";
    pmrMap[2] = "world";
}

三、性能特征深入分析

3.1 查找性能：为什么比 map 快

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <flat_map>
#include <map>
#include <chrono>
#include <cstdio>
#include <random>

void benchmarkLookup()
{
    constexpr int N = 100'000;

    // 准备数据
    std::vector<int> keys(N);
    std::iota(keys.begin(), keys.end(), 0);
    std::mt19937 rng(42);
    std::shuffle(keys.begin(), keys.end(), rng);

    // 构造 map
    std::map<int, int> m;
    for (int k : keys) m[k] = k * 2;

    // 构造 flat_map
    std::flat_map<int, int> fm;
    for (int k : keys) fm[k] = k * 2;

    // 查找基准测试
    auto lookupKeys = keys;  // 随机顺序查找
    std::shuffle(lookupKeys.begin(), lookupKeys.end(), rng);

    auto start = std::chrono::high_resolution_clock::now();
    long long sum = 0;
    for (int k : lookupKeys) {
        sum += m.find(k)->second;  // map：树节点跳转，cache miss
    }
    auto mapTime = std::chrono::high_resolution_clock::now() - start;

    start = std::chrono::high_resolution_clock::now();
    sum = 0;
    for (int k : lookupKeys) {
        sum += fm.find(k)->second;  // flat_map：连续内存二分，cache 友好
    }
    auto fmTime = std::chrono::high_resolution_clock::now() - start;

    printf("map lookup:      %lld us\n",
           std::chrono::duration_cast<std::chrono::microseconds>(mapTime).count());
    printf("flat_map lookup: %lld us\n",
           std::chrono::duration_cast<std::chrono::microseconds>(fmTime).count());
    // 典型结果：flat_map 比 map 快 2~5 倍（取决于数据量和 key 大小）
}

3.2 插入性能：flat_map 的弱点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// flat_map 的插入是 O(n)——需要在 sorted vector 中间插入并后移元素
// 对比 map 的 O(log n) 插入

// ❌ 逐个插入 N 个元素：O(N²) 总复杂度
void slowBuild()
{
    std::flat_map<int, int> fm;
    for (int i = 0; i < 100000; ++i) {
        fm[i] = i;  // 每次插入可能后移大量元素
    }
}

// ✅ 批量构造：O(N log N)（排序一次）
void fastBuild()
{
    // 方法1：先准备好数据，一次构造
    std::vector<std::pair<int, int>> data;
    data.reserve(100000);
    for (int i = 0; i < 100000; ++i) {
        data.emplace_back(i, i);
    }
    // 从已有范围构造——内部排序一次
    std::flat_map<int, int> fm(data.begin(), data.end());

    // 方法2：如果数据已排序
    std::flat_map<int, int> fm2(std::sorted_unique, data.begin(), data.end());
}

3.3 内存优势

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <flat_map>
#include <map>
#include <cstdio>

void memoryComparison()
{
    // std::map<int, int> 每个节点：
    // - key: 4 bytes
    // - value: 4 bytes
    // - left/right/parent 指针: 24 bytes
    // - 颜色位 + padding: ~8 bytes
    // 总计每节点 ≈ 40~48 bytes
    // 100K 元素 ≈ 4~5 MB

    // std::flat_map<int, int>：
    // - keys vector: 100K × 4 = 400 KB
    // - values vector: 100K × 4 = 400 KB
    // 总计 ≈ 800 KB（+ 少量 vector 元数据）

    // flat_map 内存占用约为 map 的 1/5 ~ 1/6
    printf("map node overhead: ~%zu bytes per element\n", sizeof(void*) * 3 + 8);
    printf("flat_map overhead: ~0 bytes per element (just the data)\n");
}

四、适用场景与不适用场景

4.1 适用（flat_map 优于 map）

场景	原因
启动时加载，运行时只读查找	查找 O(log n) 但 cache 友好，遍历连续
配置表、枚举映射	一次构造，频繁查找
小数据集（<1000）	常数项小，连续内存优势明显
需要紧凑内存	无节点开销
频繁有序遍历	连续内存顺序访问
需要范围查询（lower_bound）	二分查找在连续内存上更快

4.2 不适用（应选 map 或 unordered_map）

场景	原因	替代
频繁插入/删除	flat_map 插入 O(n)	std::map
需要迭代器稳定性	flat_map 插入后迭代器全失效	std::map
海量数据 + 频繁修改	realloc 成本高	std::map
不需要有序	哈希表更快	std::unordered_map
key/value 类型大且移动昂贵	插入时移动成本 O(n)	std::map

4.3 决策流程图

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
需要关联容器？
├── 不需要有序 → std::unordered_map
└── 需要有序
    ├── 频繁插入/删除 → std::map
    └── 少写多读
        ├── 数据量 < 10K → std::flat_map ✅
        ├── 数据量 10K~100K
        │   ├── 查找频率 >> 插入频率 → std::flat_map ✅
        │   └── 插入频率高 → std::map
        └── 数据量 > 100K
            ├── 一次构造只读 → std::flat_map ✅
            └── 需要动态修改 → std::map

五、与手写 sorted vector 的对比

在 C++23 之前，很多项目手动实现"排序 vector 模拟 map"：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// C++23 之前的手动实现（flat_map 的前身）
template <typename K, typename V>
class SortedVectorMap {
    std::vector<std::pair<K, V>> data_;

public:
    auto find(const K& key) {
        auto it = std::lower_bound(data_.begin(), data_.end(), key,
            [](const auto& p, const K& k) { return p.first < k; });
        if (it != data_.end() && it->first == key) return it;
        return data_.end();
    }
    // ... 大量模板代码
};

flat_map 的优势：

标准化——跨团队代码一致
Key 和 Value 分开存储——二分查找时只遍历 keys vector，cache 更友好
完整的 map 兼容 API——几乎可直接替换 std::map
支持自定义底层容器（deque、pmr::vector 等）
异常安全保证

六、实战场景

6.1 只读配置表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <flat_map>
#include <string>
#include <string_view>
#include <cstdio>

struct ItemConfig {
    uint32_t id;
    std::string name;
    int basePrice;
    float dropRate;
};

class ItemConfigTable {
    // flat_map 非常适合配置表：
    // 1. 启动时一次加载（O(n log n) 排序）
    // 2. 运行时只读查找（O(log n)，cache 友好）
    // 3. 内存紧凑（无树节点开销）
    std::flat_map<uint32_t, ItemConfig> items_;

public:
    void loadFromDatabase(/* db connection */)
    {
        // 从数据库批量加载，构造有序数据
        std::vector<std::pair<uint32_t, ItemConfig>> rawData;
        rawData.reserve(10000);  // 预估配置条数

        // ... 从 DB 读取所有条目到 rawData ...
        // 假设 DB 返回按 id 排序的结果
        // rawData.emplace_back(id, ItemConfig{id, name, price, rate});

        // 排序后构造——跳过内部排序
        std::sort(rawData.begin(), rawData.end(),
                  [](const auto& a, const auto& b) { return a.first < b.first; });

        // 去重
        rawData.erase(std::unique(rawData.begin(), rawData.end(),
                      [](const auto& a, const auto& b) { return a.first == b.first; }),
                      rawData.end());

        items_ = std::flat_map<uint32_t, ItemConfig>(
            std::sorted_unique,
            std::move(rawData)  // 零拷贝转移所有权
        );

        printf("Loaded %zu items\n", items_.size());
    }

    const ItemConfig* getItem(uint32_t id) const
    {
        auto it = items_.find(id);  // O(log n)，连续内存二分
        if (it != items_.end()) return &it->second;
        return nullptr;
    }

    // 范围查询：获取 ID 在 [low, high] 范围内的所有道具
    void getItemsInRange(uint32_t low, uint32_t high) const
    {
        auto begin = items_.lower_bound(low);
        auto end = items_.upper_bound(high);
        // 遍历是连续内存顺序访问——极快
        for (auto it = begin; it != end; ++it) {
            printf("  [%u] %s\n", it->first, it->second.name.c_str());
        }
    }
};

6.2 枚举到字符串的双向映射

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <flat_map>
#include <string_view>
#include <algorithm>

enum class ErrorCode : uint16_t {
    Ok = 0,
    NotFound = 404,
    Forbidden = 403,
    Internal = 500,
    Timeout = 504
};

// 编译期初始化的 flat_map（小数据集）
// 枚举值 → 字符串名
const std::flat_map<ErrorCode, std::string_view> errorNames = {
    {ErrorCode::Ok, "OK"},
    {ErrorCode::NotFound, "Not Found"},
    {ErrorCode::Forbidden, "Forbidden"},
    {ErrorCode::Internal, "Internal Server Error"},
    {ErrorCode::Timeout, "Gateway Timeout"}
};

// 字符串 → 枚举值（反向映射）
const std::flat_map<std::string_view, ErrorCode> errorByName = {
    {"Forbidden", ErrorCode::Forbidden},
    {"Gateway Timeout", ErrorCode::Timeout},
    {"Internal Server Error", ErrorCode::Internal},
    {"Not Found", ErrorCode::NotFound},
    {"OK", ErrorCode::Ok}
};

std::string_view getErrorName(ErrorCode code)
{
    auto it = errorNames.find(code);
    return it != errorNames.end() ? it->second : "Unknown";
}

ErrorCode parseErrorCode(std::string_view name)
{
    auto it = errorByName.find(name);
    return it != errorByName.end() ? it->second : ErrorCode::Internal;
}

6.3 时间线事件序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <flat_map>
#include <string>
#include <chrono>
#include <cstdio>

using Timestamp = std::chrono::steady_clock::time_point;

struct GameEvent {
    std::string description;
    uint32_t playerId;
    // ... 其他字段
};

class EventTimeline {
    // flat_map 按时间戳排序——适合时间序列数据
    // 特点：按时间顺序插入（尾部追加），按时间范围查询
    std::flat_map<Timestamp, GameEvent> events_;

public:
    void addEvent(Timestamp ts, GameEvent event)
    {
        // 如果事件按时间顺序到达（通常如此），
        // 尾部插入是 O(1)（hint 版本）
        events_.emplace(ts, std::move(event));
    }

    // 查询时间范围内的事件——flat_map 的强项
    void queryRange(Timestamp from, Timestamp to) const
    {
        auto begin = events_.lower_bound(from);
        auto end = events_.upper_bound(to);

        // 连续内存顺序遍历——极快
        for (auto it = begin; it != end; ++it) {
            printf("  Player %u: %s\n",
                   it->second.playerId,
                   it->second.description.c_str());
        }
    }

    // 删除旧事件（清理前 N 秒的数据）
    void pruneOlderThan(Timestamp cutoff)
    {
        auto it = events_.lower_bound(cutoff);
        // 批量删除头部——比 map 逐节点释放高效
        events_.erase(events_.begin(), it);
    }
};

七、C++23 之前的替代方案

如果编译器不支持 C++23，可以用以下替代：

替代方案	来源	特点
`boost::container::flat_map`	Boost.Container	最成熟，API 接近标准
`absl::flat_hash_map`	Abseil	无序版本，开放寻址
手写排序 vector + 二分	自实现	零依赖，但需维护
`folly::sorted_vector_map`	Meta/Folly	生产验证

1
2
3
4
5
6
7
// Boost 替代（C++23 之前）
#include <boost/container/flat_map.hpp>

boost::container::flat_map<int, std::string> bfm;
bfm[1] = "one";
bfm[2] = "two";
// API 几乎与 std::flat_map 一致

八、最佳实践总结

“少写多读"场景首选 flat_map——配置表、映射表、只读字典
批量构造优于逐个插入——先收集数据再一次性构造
数据已排序时用 sorted_unique——跳过排序，O(n) → O(1) 构造
替换 std::map 前评估写入频率——频繁插入删除时 map 更优
小数据集（<1000）flat_map 几乎总是最快——常数项优势压倒算法复杂度
与 PMR 结合实现请求级零分配——自定义底层容器用 pmr::vector
不要依赖迭代器稳定性——任何修改操作都可能失效
利用 keys()/values() 访问底层容器——需要批量操作时直接操作 vector
范围查询（lower_bound/upper_bound）是 flat_map 的强项——优于 unordered_map

深入学习 std::flat_map#

一、设计动机：std::map 的性能痛点#

1.1 红黑树的缓存问题#

1.2 flat_map 的解法：排序 vector#

1.3 性能对比#

二、核心 API#

2.1 基本用法#

2.2 与 std::map 的 API 差异#

2.3 sorted_unique 优化构造#

2.4 自定义底层容器#

三、性能特征深入分析#

3.1 查找性能：为什么比 map 快#

3.2 插入性能：flat_map 的弱点#

3.3 内存优势#

四、适用场景与不适用场景#

4.1 适用（flat_map 优于 map）#

4.2 不适用（应选 map 或 unordered_map）#

4.3 决策流程图#

五、与手写 sorted vector 的对比#

六、实战场景#

6.1 只读配置表#

6.2 枚举到字符串的双向映射#

6.3 时间线事件序列#

七、C++23 之前的替代方案#

八、最佳实践总结#

深入学习 std::flat_map

一、设计动机：std::map 的性能痛点

1.1 红黑树的缓存问题

1.2 flat_map 的解法：排序 vector

1.3 性能对比

二、核心 API

2.1 基本用法

2.2 与 std::map 的 API 差异

2.3 sorted_unique 优化构造

2.4 自定义底层容器

三、性能特征深入分析

3.1 查找性能：为什么比 map 快

3.2 插入性能：flat_map 的弱点

3.3 内存优势

四、适用场景与不适用场景

4.1 适用（flat_map 优于 map）

4.2 不适用（应选 map 或 unordered_map）

4.3 决策流程图

五、与手写 sorted vector 的对比

六、实战场景

6.1 只读配置表

6.2 枚举到字符串的双向映射

6.3 时间线事件序列

七、C++23 之前的替代方案

八、最佳实践总结