C++23的std::flat_map是什么_C++基于有序向量的高速缓存友好型关联容器

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++23的std::flat_map是什么_C++基于有序向量的高速缓存友好型关联容器

2025-11-24

浏览次数：次

返回列表

flat_map是一种基于有序vector的缓存友好关联容器，使用连续内存存储键值对，通过二分查找实现查询，具有高缓存命中率、低内存开销和快速迭代的优势，适用于数据量适中、查找频繁且修改较少的场景，但插入删除性能较差，C++23未正式引入，需手动实现或借助第三方库。

c++23的std::flat_map是什么_c++基于有序向量的高速缓存友好型关联容器

std::flat_map 并不是 C++23 标准中正式引入的容器。截至目前（C++23 最终草案），标准库中并未包含名为 std::flat_map 的容器。不过，这个名称经常出现在讨论中，指的是一个基于有序 std::vector 实现的缓存友好的关联容器设计模式，也被称为“平面映射”或“扁平映射”。

虽然它不在标准库中，但它的设计理念被广泛认可，并可能在未来版本（如 C++26）中被考虑标准化。目前，类似功能可通过组合现有容器手动实现，或使用第三方库（如 abseil 的 flat_hash_map 系列，尽管那是哈希变体）。

什么是 flat_map？

“Flat map” 是一种使用单个连续内存块（通常是 std::vector<:p style="color:#f60; text-decoration:underline;" title="ai" href="https://www.php.cn/zt/17539.html" target="_blank">air>）来存储键值对的关联容器。所有元素按键排序，查找通过二分搜索（如 std::lower_bound）完成。

与 std::map（通常为红黑树）相比，flat_map 优势在于：

PictoGraphic

AI驱动的矢量插图库和插图生成平台

133 查看详情 PictoGraphic

内存局部性好：数据连续存储，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(); }
};