std::flat_map和std::flat_set是C++23引入的基于有序动态数组的关联容器，以连续内存存储实现O(log n)查找，相比传统红黑树更缓存友好、内存紧凑，适用于中小规模、读多写少的场景。

在C++23中，std::flat_map 和 std::flat_set 正式成为标准库的一部分。它们是基于连续内存容器（如 std::vector）实现的高性能关联容器，提供类似 std::map 和 std::set 的接口，但在某些场景下性能更优。

什么是 flat_map 和 flat_set？

与传统的红黑树实现不同，std::flat_map 和 std::flat_set 使用一个有序的动态数组（通常是封装了 std::vector 的结构）来存储元素。内部通过保持元素有序，并使用二分查找进行访问，从而实现 O(log n) 的查找复杂度。

它们的本质是一个“排序的 vector + 二分搜索”，牺牲了插入和删除的最差性能（O(n)），换取更好的缓存局部性和更低的内存开销。

相比 map/set 的优势

• 缓存友好：数据连续存储，遍历和查找时 CPU 缓存命中率高，实际性能常优于指针离散的树结构。
• 内存占用更小：没有额外的左右子节点指针和平衡标记，每个元素的开销接近原生类型。
• 迭代效率高：连续内存支持快速遍历，适合只读或低频修改的场景。
• 可预测的性能：避免了树结构可能的不平衡或重新平衡开销。

适用场景与使用建议

flat 容器最适合以下情况：

• 容器大小适中（几百到几千个元素）
• 查找远多于插入/删除
• 数据可以批量构建后只读使用
• 对性能和内存敏感，尤其是嵌入式或高频计算场景

例如，在配置查找表、静态索引、编译时常量映射等场景中，std::flat_map 可显著提升性能。

注意：频繁插入删除会导致大量内存移动，此时传统 std::map 更合适。

基本用法示例

使用方式与标准容器类似：

#include 
#include 

int main() {
    std::flat_map fm;
    fm.insert({1, "one"});
    fm.insert({3, "three"});
    fm.insert({2, "two"}); // 自动排序

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

基本上就这些。std::flat_map 和 std::flat_set 是 C++23 对性能导向编程的重要补充，合理使用能有效提升程序效率。