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

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

穿越時空

发布： 2025-11-24 14:01:02

原创

174人浏览过

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<std::pair<Key, Value>>）来存储键值对的关联容器。所有元素按键排序，查找通过二分搜索（如 std::lower_bound）完成。

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

立即学习“C++免费学习笔记（深入）”；

AI TransPDF

高效准确地将PDF文档翻译成多种语言的AI智能PDF文档翻译工具

231

查看详情

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

登录后复制