std::flat_map(C++23) ​

什么是 std::flat_map ​

std::flat_map 是 C++23 引入的容器适配器,提供与 std::map 相同的有序关联容器功能(键值对,键唯一,按键排序),但底层使用两个排序的连续容器(默认是 std::vector)分别存储键和值,而不是红黑树。

这种设计让查找操作更加缓存友好——键紧密排列在连续内存中,二分查找时减少了缓存缺失。

cpp
#include <flat_map>
std::flat_map<std::string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 82;

flat_map vs map vs unordered_map ​

特性std::flat_mapstd::mapstd::unordered_map
底层结构排序的 vector 对红黑树哈希表
查找复杂度O(log n)O(log n)O(1) 平均
插入复杂度O(n)(需要移动元素)O(log n)O(1) 平均
删除复杂度O(n)O(log n)O(1) 平均
内存连续性键和值分别连续节点分散桶+链表/探测
缓存友好非常好差一般
迭代器稳定性插入/删除后失效稳定重哈希后失效
内存开销低(无节点指针)高(每个节点有指针)中等
有序遍历天然有序天然有序无序

基本示例 ​

cpp
#include <iostream>
#include <flat_map>
#include <string>
#include <vector>

// ============================
// 示例1:基本用法
// ============================

void basic_demo() {
    std::flat_map<std::string, int> ages;

    // 插入元素
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    ages["Charlie"] = 28;
    ages.insert({"Diana", 22});

    // 遍历(按键排序)
    std::cout << "按姓名排序:" << std::endl;
    for (const auto& [name, age] : ages) {
        std::cout << "  " << name << ": " << age << std::endl;
    }
    // Alice: 25, Bob: 30, Charlie: 28, Diana: 22

    // 查找
    if (auto it = ages.find("Bob"); it != ages.end()) {
        std::cout << "Bob 的年龄: " << it->second << std::endl;
    }

    // contains(和 map 一样)
    std::cout << "有 Eve: " << std::boolalpha << ages.contains("Eve") << std::endl;
}

// ============================
// 示例2:从已排序数据高效构造
// ============================

void sorted_construction_demo() {
    // 如果数据已经排序,可以用 sorted_unique 标签避免重新排序
    std::flat_map<int, std::string> fm(std::sorted_unique,
        std::vector<int>{1, 2, 3, 4, 5},
        std::vector<std::string>{"one", "two", "three", "four", "five"}
    );

    for (const auto& [k, v] : fm) {
        std::cout << k << " -> " << v << std::endl;
    }
}

// ============================
// 示例3:访问底层容器
// ============================

void underlying_demo() {
    std::flat_map<std::string, int> scores = {
        {"Alice", 95}, {"Bob", 82}, {"Charlie", 78}
    };

    // 直接访问键容器和值容器
    const auto& keys = scores.keys();
    const auto& values = scores.values();

    std::cout << "键: ";
    for (const auto& k : keys) std::cout << k << " ";
    std::cout << std::endl;

    std::cout << "值: ";
    for (int v : values) std::cout << v << " ";
    std::cout << std::endl;

    // 值容器是连续内存,可以直接获取指针
    const int* data_ptr = values.data();
    std::cout << "第一个值的地址: " << data_ptr << std::endl;
}

// ============================
// 示例4:批量插入
// ============================

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

    // 批量插入比逐个插入更高效
    std::vector<std::pair<int, std::string>> data = {
        {5, "five"}, {1, "one"}, {3, "three"}, {2, "two"}, {4, "four"}
    };

    fm.insert(data.begin(), data.end());

    for (const auto& [k, v] : fm) {
        std::cout << k << ": " << v << std::endl;
    }
}

// ============================
// 示例5:自定义比较器
// ============================

void custom_compare_demo() {
    // 按降序排列
    std::flat_map<int, std::string, std::greater<>> fm = {
        {1, "one"}, {3, "three"}, {2, "two"}
    };

    std::cout << "降序:" << std::endl;
    for (const auto& [k, v] : fm) {
        std::cout << "  " << k << ": " << v << std::endl;
    }
    // 3: three, 2: two, 1: one
}

// ============================
// 示例6:extract 和 replace
// ============================

void extract_demo() {
    std::flat_map<std::string, int> fm = {
        {"Alice", 95}, {"Bob", 82}, {"Charlie", 78}
    };

    // extract 取出底层容器
    auto containers = std::move(fm).extract();
    // containers.keys 和 containers.values 现在可以直接操作

    auto& keys = containers.keys;
    auto& vals = containers.values;

    std::cout << "提取后的键: ";
    for (const auto& k : keys) std::cout << k << " ";
    std::cout << std::endl;

    // replace 放回
    // fm.replace(std::move(keys), std::move(vals));
}

// ============================
// 示例7:与 map 的接口兼容
// ============================

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

    // 和 std::map 几乎相同的接口
    fm.emplace("Alice", 95);
    fm.try_emplace("Bob", 82);
    fm.insert_or_assign("Alice", 100);  // 更新已有的键

    std::cout << "Alice: " << fm.at("Alice") << std::endl;  // 100

    // erase
    fm.erase("Bob");
    std::cout << "大小: " << fm.size() << std::endl;

    // lower_bound / upper_bound
    fm.insert({{"C", 1}, {"D", 2}, {"E", 3}});
    auto lb = fm.lower_bound("D");
    if (lb != fm.end()) {
        std::cout << "lower_bound(D): " << lb->first << std::endl;
    }
}

int main() {
    std::cout << "=== 基本用法 ===" << std::endl;
    basic_demo();

    std::cout << "\n=== 已排序构造 ===" << std::endl;
    sorted_construction_demo();

    std::cout << "\n=== 底层容器 ===" << std::endl;
    underlying_demo();

    std::cout << "\n=== 批量插入 ===" << std::endl;
    batch_insert_demo();

    std::cout << "\n=== 自定义比较 ===" << std::endl;
    custom_compare_demo();

    std::cout << "\n=== 接口兼容 ===" << std::endl;
    compatibility_demo();

    return 0;
}

何时选择 flat_map ​

场景推荐原因
构建后主要查找,很少修改flat_map查找缓存友好
频繁插入删除map插入删除 O(log n)
需要迭代器稳定性mapflat_map 插入后迭代器失效
内存受限flat_map无节点指针开销
需要连续内存访问flat_mapkeys()/values() 返回 vector
元素数量小(< 几百)flat_map小数据集缓存效果好
大量数据频繁修改map 或 unordered_mapflat_map 插入 O(n)

适用场景 ​

  • 配置数据(构建一次,频繁查找)
  • 小型查找表
  • 需要有序遍历且查找性能优先
  • 需要直接访问底层连续内存
  • 从已排序数据构建映射

常见问题 ​

flat_map 的插入为什么是 O(n)?

因为底层是排序的 vector,插入新元素需要移动后面所有元素来保持排序。对于大量随机插入的场景,这比 map 的 O(log n) 慢得多。

flat_map 的查找真的比 map 快吗?

对于中小规模数据,通常是的。虽然两者都是 O(log n) 二分查找,但 flat_map 的键存储在连续内存中,CPU 缓存预取可以大幅减少访问延迟。

flat_map 可以用 deque 作为底层容器吗?

可以。标准允许用 std::vector 或 std::deque 作为底层容器。用 deque 可以避免 vector 在扩容时的大块内存重新分配。

flat_map 支持 node 操作吗?

不支持。flat_map 没有 extract(node) 和 merge 等节点操作。它有自己的 extract() 和 replace() 来操作底层容器。

注意事项 ​

  • 插入和删除是 O(n) 的——不适合频繁修改的场景
  • 插入和删除后所有迭代器都失效
  • 底层默认使用两个 vector(键和值分开存储)
  • 从已排序数据构造时用 sorted_unique 标签可以跳过排序
  • 不支持节点操作(extract node / merge)
  • 需要 <flat_map> 头文件

编译器支持情况 ​

编译器std::flat_map最低版本
GCC支持15.0
Clang部分支持18.0
MSVC支持19.34 (VS 2022 17.4)

总结 ​

std::flat_map 是 C++23 引入的有序关联容器适配器,提供与 std::map 相同的接口,但底层使用排序的连续容器(默认 vector)存储键和值。这让查找操作更加缓存友好,内存开销更低。代价是插入和删除变成了 O(n)。flat_map 最适合"构建一次、查找多次"的场景——配置数据、小型查找表、需要有序遍历的映射等。对于频繁修改的场景,传统的 std::map 仍然是更好的选择。