flat_map / flat_set

std::flat_map 和 std::flat_set 是 C++23 引入的有序关联容器，底层用有序 vector 存储元素。相比基于平衡树的 map/set，它们内存更紧凑、缓存更友好，适合"构建后大量查询，偶尔修改"的场景。

头文件与基本特征

#include <flat_map>
#include <flat_set>

特征	map/set	flat_map/flat_set (C++23)
底层	平衡二叉树	有序 vector
内存	每节点额外指针开销	紧凑连续存储
遍历速度	跳跃指针，缓存不友好	线性扫描，缓存友好
查找	O(log n)	O(log n)（二分查找）
插入/删除	O(log n)	O(n)（需搬移元素）
迭代器失效	删除时单个失效	插入/删除全部失效

基本用法

#include <flat_map>
#include <iostream>
#include <string>

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

    scores["Alice"] = 95;
    scores["Bob"] = 88;
    scores["Cathy"] = 91;

    for (const auto& [name, score] : scores) {
        std::cout << name << " = " << score << '\n';
    }
    // 按键顺序输出：Alice → Bob → Cathy

    return 0;
}

接口几乎完全兼容 map/set，迁移成本很低。

选择指南

场景	推荐
数据量较小（~几百）且查多改少	flat_map / flat_set
频繁插入/删除	map / set
需要稳定迭代器	map / set
追求遍历速度	flat_map / flat_set
需要内存紧凑	flat_map / flat_set

使用注意

1. flat_map 插入和删除是 O(n)，频繁修改不适用。
2. 所有插入/删除操作都会使迭代器失效。
3. 键类型必须可移动——插入时会重新排序整个底层 vector。
4. 接口基本兼容 map，但有细微差别（如 extract 等特殊操作）。

小结

std::flat_map / std::flat_set 是缓存友好的有序容器。在数据量适中、查询远多於修改的场景下，它们通常比红黑树实现的 map/set 快得多。核心权衡：用 O(n) 的插入代价换 O(1) 的遍历/缓存性能。