44、C++23 前瞻：std::flat_map与std::flat_set，连续存储的关联容器。

说实话，C++ 标准库里的关联容器，我们用了这么多年，心里都清楚它们的脾气。std::map 和 std::set 底层是红黑树，查找快，插入删除也稳定。但代价是什么？内存碎片化，缓存不友好。你想想看，一个红黑树的节点在堆上东一个西一个，遍历的时候 CPU 缓存命中率能高到哪去？

C++23 引入的 std::flat_map 和 std::flat_set，说白了就是换了个思路——用连续存储的数组来组织关联数据。我最初看到这个提案的时候，第一反应是：这不就是 sorted vector 吗？嗯，还真差不多，但标准库把它做成了适配器，用起来更顺手。

它们到底是什么？

std::flat_map 和 std::flat_set 是关联容器的适配器。它们内部维护一个或多个连续存储的容器（默认是 std::vector），并保证元素按键有序。说白了，就是把 map 和 set 的语义，套在了 vector 的存储上。

我个人的习惯是，把 flat_map 理解成「排序后的 vector of pairs」。它不像红黑树那样每个节点单独分配内存，而是所有数据挤在一块连续的内存区域里。

为什么需要它们？

我在项目中遇到过好几次这样的场景：一个配置表，启动时加载进去，之后几乎只读，偶尔查一查。用 std::map 当然可以，但每次性能分析都发现，遍历配置表的时候，缓存 miss 高得吓人。换成 sorted vector 之后，性能直接翻倍。

flat_map 和 flat_set 就是为这种场景量身定做的。它们适合：

• 元素数量相对固定：一次性构建，之后很少插入删除
• 查找操作频繁：连续内存让二分查找的缓存效率极高
• 遍历操作多：顺序访问连续内存，CPU 预取友好
• 内存敏感的环境：没有节点指针开销，内存占用更低

性能对比一览

操作	std::map (红黑树)	std::flat_map (连续存储)
查找	O(log n)，节点分散	O(log n)，缓存友好
插入（单次）	O(log n)，节点分配	O(n)，可能移动大量元素
批量插入（已排序）	O(n log n)	O(n)，可优化为原地合并
遍历	O(n)，缓存不友好	O(n)，顺序访问
内存占用	高（节点指针 + 颜色位）	低（只有数据本身）

你看这个表就明白了。查找和遍历，flat_map 几乎完胜。但插入操作，它要付出代价。所以选哪个，取决于你的使用模式。

基本用法示例

先看一段简单的代码，感受一下 flat_map 的用法：

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

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

    // 插入元素
    fm.insert({3, "three"});
    fm.insert({1, "one"});
    fm.insert({2, "two"});

    // 查找
    auto it = fm.find(2);
    if (it != fm.end()) {
        std::cout << it->second << '\n';  // 输出 "two"
    }

    // 遍历
    for (const auto& [key, value] : fm) {
        std::cout << key << ": " << value << '\n';
    }

    return 0;
}

嗯，接口和 std::map 几乎一样。你甚至可以直接把代码里的 std::map 换成 std::flat_map，大部分情况下能直接编译通过。但性能表现就完全不一样了。

自定义底层容器

flat_map 是一个适配器，你可以指定底层容器。默认是 std::vector，但你可以换成 std::deque 甚至你自己的容器，只要满足序列容器的要求。

// 使用 std::deque 作为底层存储
std::flat_map<int, std::string, std::less<int>, std::deque<std::pair<int, std::string>>> fm_deque;

我个人建议，除非你有特殊理由，否则就用默认的 vector。它在绝大多数场景下表现最好。

flat_set 的用法

flat_set 和 flat_map 类似，只不过它只存储键，没有值。用法和 std::set 几乎一样：

#include <flat_set>
#include <iostream>

int main() {
    std::flat_set<int> fs;

    fs.insert(5);
    fs.insert(1);
    fs.insert(3);

    // 查找
    if (fs.contains(3)) {
        std::cout << "found 3\n";
    }

    // 遍历
    for (int x : fs) {
        std::cout << x << ' ';
    }
    // 输出: 1 3 5

    return 0;
}

批量构建：最擅长的场景

flat_map 最拿手的，其实是批量构建。如果你有一堆数据要一次性放进去，而且数据本身已经排好序，那 flat_map 的构建速度比 std::map 快一个数量级。

#include <flat_map>
#include <vector>
#include <utility>

int main() {
    // 假设数据已经按 key 排好序
    std::vector<std::pair<int, std::string>> data = {
        {1, "one"},
        {2, "two"},
        {3, "three"},
        {4, "four"}
    };

    // 使用 sorted_unique 标签，告诉 flat_map 数据已经有序且无重复
    std::flat_map<int, std::string> fm(
        std::sorted_unique,
        data.begin(),
        data.end()
    );

    // 直接使用，无需排序
    return 0;
}

这里的关键是 std::sorted_unique 标签。它告诉 flat_map：相信我，数据已经排好序了，没有重复。这样 flat_map 就省去了排序和去重的开销，直接拿过来用。我在项目中处理百万级配置数据时，用这个方式构建 flat_map，比 std::map 快了将近 10 倍。

内部结构示意图

下面这张图展示了 flat_map 和 std::map 在内存布局上的本质区别。你可以直观地看到，为什么 flat_map 对缓存更友好。

你看，std::map 的节点在内存里东一个西一个，遍历的时候 CPU 得不停地从不同地址加载数据。而 flat_map 的数据整整齐齐排在一起，遍历时 CPU 可以预取后面的数据，缓存命中率自然高。

避坑指南

我曾经在一个项目中，把 std::map 直接替换成 std::flat_map，结果程序崩溃了。排查了半天，发现是因为迭代器失效的问题。flat_map 的迭代器在插入操作后可能全部失效（因为 vector 可能重新分配内存），而 std::map 的迭代器在插入后只有指向被删除元素的迭代器会失效。这个差异，如果你不注意，很容易踩坑。

什么时候不该用 flat_map？

嗯，这里要诚实。flat_map 不是万能的。以下几种情况，我建议你还是老老实实用 std::map：

• 频繁插入删除：每次插入都可能 O(n) 移动元素，性能会很难看
• 元素类型很大：如果 key 或 value 的拷贝成本很高，移动元素的代价会非常大
• 需要稳定迭代器：如果你依赖迭代器在插入后仍然有效，flat_map 会让你失望
• 元素数量极少：少于 10 个元素时，红黑树和连续数组的性能差异可以忽略不计

说白了，flat_map 是为「构建一次，查询多次」的场景设计的。如果你需要频繁修改容器内容，还是用传统的关联容器更稳妥。

总结

std::flat_map 和 std::flat_set 是 C++23 给我们的一个有力工具。它们不是要取代 std::map 和 std::set，而是在特定场景下提供更好的选择。我个人觉得，这个设计思路很务实——承认不同场景需要不同的数据结构，而不是试图用一个方案解决所有问题。

记住一句话：选择数据结构，先看你的使用模式。读多写少，用 flat_map；写多读少，用 map。就这么简单。

---

公众号:蓝海资料掘金营，微信deep3321