flat_map是一种基于有序vector的缓存友好关联容器，使用连续内存存储键值对，通过二分查找实现查询，具有高缓存命中率、低内存开销和快速迭代的优势，适用于数据量适中、查找频繁且修改较少的场景，但插入删除性能较差，C++23未正式引入，需手动实现或借助第三方库。
std::flat_map 并不是 C++23 标准中正式引入的容器。截至目前（C++23 最终草案），标准库中并未包含名为 std::flat_map 的容器。不过，这个名称经常出现在讨论中，指的是一个基于有序 std::vector 实现的缓存友好的关联容器设计模式，也被称为“平面映射”或“扁平映射”。
虽然它不在标准库中，但它的设计理念被广泛认可，并可能在未来版本（如 C++26）中被考虑标准化。目前，类似功能可通过组合现有容器手动实现，或使用第三方库（如 abseil 的 flat_hash_map 系列，尽管那是哈希变体）。
什么是 flat_map？
“Flat map” 是一种使用单个连续内存块（通常是 std::vector<std::pair<Key, Value>>）来存储键值对的关联容器。所有元素按键排序，查找通过二分搜索（如 std::lower_bound）完成。
与 std::map（通常为红黑树）相比，flat_map 优势在于：
立即学习“C++免费学习笔记（深入）”；
- 内存局部性好：数据连续存储，CPU 缓存命中率高。
- 迭代速度快：顺序访问性能接近原生数组。
- 内存开销小：无额外指针或节点管理成本。
如何模拟 std::flat_map？
你可以用 vector + 算法轻松实现一个简易版本：
#include <vector>
#include <algorithm>
#include <utility>
template<typename Key, typename Value, typename Compare = std::less<Key>>
class flat_map {
using value_type = std::pair<Key, Value>;
std::vector<value_type> data_;
Compare comp_;
auto key_comp() const { return [&](const value_type& a, const value_type& b) {
return comp_(a.first, b.first);
}; }
public:
// 插入：保持有序
std::pair<auto, bool> insert(const value_type& val) {
auto it = std::lower_bound(data_.begin(), data_.end(), val, key_comp());
if (it != data_.end() && !comp_(val.first, it->first) && !comp_(it->first, val.first)) {
return {it, false}; // 已存在
}
return {data_.emplace(it, val), true};
}
// 查找
auto find(const Key& k) {
auto it = std::lower_bound(data_.begin(), data_.end(), value_type{k, {}}, key_comp());
if (it != data_.end() && !comp_(k, it->first) && !comp_(it->first, k))
return it;
return data_.end();
}
// 其他接口如 size(), begin(), end() 等可直接转发
auto size() const { return data_.size(); }
auto begin() { return data_.begin(); }
auto end() { return data_.end(); }
};
适用场景与限制
flat_map 特别适合以下情况：
- 数据量较小到中等（几百到几千项）。
- 查找远多于插入/删除。
- 需要快速遍历所有元素。
- 对内存效率和缓存性能敏感。
但它也有缺点：
- 插入/删除慢：需移动大量元素（O(n)）。
- 频繁修改不适用：每次插入都要维持有序。
- 没有稳定的迭代器（插入可能导致重新分配）。
