高级数据结构_flat结构

发表于2025-09-10更新于2025-09-10阅读次数

author: Chenggong Xing

date: 2025/9/10

内容

  1. 分析了已经在C++23引入标准库的flat_map结构
  2. 分析了尚未引入标准库的优秀的unordered_flat_map实现

flat_map

C++23 中引入的 std::flat_map、std::flat_set 等平坦容器，其核心在于​​底层使用有序的连续内存结构（如 std::vector）来存储元素​​，并通过​​二分查找​​来定位元素，从而维护其有序性。这使得它们在查找和遍历性能上通常优于传统的基于节点的容器（如 std::map），但在插入和删除操作上成本较高。

下面是一个对比表格，帮助你快速了解 std::flat_map 与 std::map 在底层实现上的关键差异：

特性维度 std::map (传统关联容器) std::flat_map (C++23 平坦容器)
​​底层数据结构​​ 通常为红黑树（节点式，非连续内存） ​​排序的连续内存​​（如 std::vector<std::pair<Key, Value>> 或​​两个分离的 std::vector​​ ）
​​查找机制​​ 遍历树结构（O(log n)） ​​二分查找​​（O(log n)，​​常数项更优​​，缓存友好）
​​插入/删除机制​​ 调整树节点指针（O(log n)） ​​可能移动大量元素​​以维持有序（O(n)）
​​迭代器稳定性​​ ​​稳定​​（插入删除通常不会使其他迭代器失效） ​​不稳定​​（插入删除可能使所有迭代器失效）
​​内存布局​​ 元素分散在堆内存中，额外开销包括节点指针等 ​​元素紧凑排列​​，内存开销更小

维护有序性的细节

平坦容器所有元素都存储在一个或多个始终保持​​严格排序​​状态的底层容器（如 std::vector）中。这是其高效查找的基础。

  1. ​插入操作​​：
    • 当插入新元素时，容器首先使用​​二分查找​​（复杂度 O(log n)）在底层有序序列中快速定位到正确的插入位置，以确保排序不变性。
    • 找到位置后，如果底层容器是 std::vector，​​插入点之后的所有元素可能需要向后移动​​一位以腾出空间（复杂度 O(n)）。这个过程类似于向有序数组中间插入数据。
    • 因此，​​插入操作的总体复杂度是 O(n)​​。
  2. ​删除操作​​：
    • 类似地，删除元素时，首先使用二分查找定位目标元素（O(log n)）。
    • 移除该元素后，​​其后所有元素可能需要向前移动​​一位以填补空隙（O(n)）。
    • 因此，​​删除操作的总体复杂度也是 O(n)​​。
  3. ​查找操作​​：
    • 由于元素有序，查找操作直接使用​​二分查找​​（O(log n)），且得益于​​连续内存存储带来的极佳缓存局部性​​，实际效率通常远高于传统的 std::map/std::set。
  4. ​底层容器与内存管理​​：
    • 平坦容器是​​容器适配器​​，可以指定底层使用的容器类型（例如 std::vector 或 std::deque），默认为 std::vector。
    • std::flat_map 的一个特殊之处在于其底层通常由​​两个单独的数组​​构成：一个用于存储键（Key），另一个用于存储值（Value）。键数组始终保持有序，值数组中元素的索引与键数组一一对应。这种设计使得键的比较更加高效，但在插入和删除时需要同时维护两个数组的同步和有序性。

核心特点与设计考量

  • ​性能权衡​​：平坦容器通过​​牺牲插入和删除的效率​​，换取了​​极佳的查找性能、遍历速度和更低的内存占用​​。这是一种典型的以空间换时间（缓存友好性）的设计思路。
  • ​异常安全​​：由于插入和删除操作可能涉及大量元素的移动，如果在移动过程中（例如元素的移动构造函数）抛出异常，容器的状态可能会变得复杂，其异常安全性通常弱于节点式容器。
  • ​元素类型要求​​：因为涉及元素的移动，键和值类型必须是​​可移动构造（Movable）和可复制构造（Copyable）​​ 的。

适用场景

  1. ​频繁查找和遍历，少量插入删除​​：例如配置表、初始化后很少变化的参考数据、游戏中的静态资源表等。
  2. ​对内存占用和缓存友好性极其敏感的场景​​：嵌入式系统或需要处理海量数据且希望减少缓存未命中的应用。
  3. ​需要频繁对容器进行批量操作或排序的场景​​：由于数据在内存中连续，可以非常高效地与标准库算法结合使用。

注意事项

  1. ​迭代器失效​​：​​任何可能修改容器内容的操作（如插入、删除）都可能导致所有现有的迭代器和引用失效​​。这是因为底层存储可能需要重新分配内存或移动大量元素。
  2. ​性能波动​​：虽然查找速度稳定且快，但插入和删除操作的时间成本取决于插入点的位置。在容器尾部操作比在头部操作更快。

两个分离的数组和单一数组存pair的对比

C++23 中 std::flat_map 使用两个分离的数组分别存储键（Key）和值（Value），与使用单一数组存储 std::pair<Key, Value> 的设计相比，确实各有优劣。下面这个表格汇总了它们的主要区别：

特性维度 双数组设计 (键值分离) 单数组设计 (存储 pair)
​​缓存局部性​​ ​​键的局部性极佳​​，查找时仅键数组入缓存，命中率高 每次比较需加载整个 pair，可能包含不必要的数据，缓存效率相对较低
​​查找性能​​ ​​通常更高​​（二分查找时比较操作更高效） 相对较低（需传递整个 pair 进行比较）
​​插入/删除性能​​ 需移动​​两个数组​​中的元素，​​开销可能更大​​ 只需移动​​一个数组​​中的元素，开销相对较小
​​内存布局​​ 键和值分别连续存储 键值对连续存储
​​内存管理​​ 更灵活，可为键和值选择不同的分配器或容器 相对统一，管理简单
​​迭代器类型​​ 提供随机访问迭代器 提供随机访问迭代器
​​迭代器稳定性​​ ​​极不稳定​​，任何修改操作均使所有迭代器失效 ​​极不稳定​​，任何修改操作均使所有迭代器失效
​​代码复杂性​​ 内部实现需维护两个序列的同步，更复杂 实现相对简单直接

双数组设计优缺点分析

优点：

  1. ​卓越的查找性能与缓存效率​​：这是​​最显著的优点​​。进行二分查找时，算法只需在​​连续紧凑的键数组​​中进行比较操作。这大大提高了 CPU 缓存命中率，因为缓存线可以被纯粹用于键的比较数据填满，避免了将值数据（可能很大且无关）加载到缓存中。对于键类型较小且比较操作昂贵的场景，性能提升尤为明显。
  2. ​潜在的内存灵活性​​：理论上，可以为键容器和值容器指定不同的类型（例如，键用 std::vector，值用 std::deque），甚至不同的分配器。这提供了更精细的内存管理控制。

缺点：

  1. ​插入和删除开销更大​​：维护有序性需要向底层容器插入或删除元素。在双数组设计中，​​需要在两个数组的对应位置进行相同的移动操作​​。这意味着一次插入可能引发两次元素移动（键数组一次，值数组一次），理论上开销比单数组移动 pair 更大。
  2. ​实现复杂度更高​​：容器需要小心翼翼地维护键和值两个序列的同步，确保对应索引的键值始终匹配。这增加了内部实现的复杂性。

单数组设计（存储 pair）优缺点分析

优点：

  1. ​插入删除操作稍快​​：只需在单个 pair 数组中进行元素的移动，操作次数更少。对于频繁需要修改的场景，这可能是一个优势。
  2. ​实现更简单直观​​：只需要管理一个容器，逻辑相对简单，不易出错。
  3. ​与传统习惯兼容​​：许多现有算法和代码习惯于处理 std::pair，单数组设计在交互上可能更自然。

缺点：

  1. ​缓存局部性相对较差​​：进行二分查找时，每次比较都需要把整个 std::pair 加载到缓存中。如果值数据很大（例如包含字符串），但比较时根本用不到，就会​​浪费宝贵的缓存空间​​，导致缓存效率降低，从而影响查找速度。
  2. ​内存使用可能不经济​​：同上，如果键很小而值很大，每次比较操作却要加载整个大 pair，内存带宽的利用效率不高。

设计选择与考量

C++23 标准委员会最终为 std::flat_map 选择了​​双数组设计​​，这主要基于其核心应用场景的考量：

  • ​std::flat_map 的首要目标是提供极致的查找性能​​。在大多数关联容器的使用场景中，​​查找​​是最频繁的操作，而插入和删除则相对较少。双数组设计完美地优化了查找性能，通过牺牲一些修改操作的效率，换取了更重要的查找速度和缓存效率。
  • ​缓存局部性在现代计算机体系结构中至关重要​​。处理器速度远快于内存速度，因此减少缓存未命中、提高缓存命中率是提升性能的关键。双数组设计在这方面表现优异。
  • 虽然插入/删除更耗时，但其复杂度仍然是 ​​O(n)​​，与单数组设计相同。 Big-O 记号相同，但常数因子可能不同。标准委员会认为查找性能的收益超过了修改操作的开销。

如何选择

  • 如果你的使用场景是​​频繁查找、遍历，而插入和删除操作很少​​（例如配置表、初始化后很少变化的数据、只读或重加载不频繁的参考数据），那么 std::flat_map 的双数组设计是非常理想的选择，能为你带来显著的性能提升。
  • 如果你的场景需要​​频繁的插入和删除​​，那么基于节点的容器（如 std::map）可能仍然是更好的选择，因为它们能提供稳定的 O(log n) 插入删除和迭代器稳定性。
  • 需要注意的是，无论哪种底层存储设计，​​std::flat_map 的迭代器在插入和删除操作后都会失效​​，这是由其底层线性结构决定的。

unordered_flat_map

高性能哈希表。核心特点是：开放寻址、平坦内存布局。

截止2025年9月10日，unordered_flat_map还未引入标准库。

Abseil 库实现

Abseil 库的实现是absl::flat_hash_map。采用了一种称为瑞士表格（Swiss Table）的设计。

底层策略

底层策略是基于开放寻址和线性探测。所有元素直接存储在一个数组中，而不是像std::unordered_map那样使用链地址法（每个桶挂载一个链表）

核心机制

核心机制是控制字节：每个键值对（槽位）都有一个对应的控制字节，用于编码该槽位的状态（空、已删除、满）以及哈系值的一部分信息（通常取哈系值的高 7 位），这使得它可以快速判断一个槽位是否可以匹配目标键，从而加速查找。

内存布局

内存布局：数据（键值对）和元数据（控制字节）是分离存储的。数据数组和控制字节数组并存。这种布局有利于使用SIMD指令（如 SSE 或 AVX）一次性比较多个控制字节，极大提升扫描速度。

哈系探测

哈希探测：使用模运算或按位与（桶大小为 2 的幂时）来确定初始索引。发生冲突时，进行线性探测（顺序检查下一个槽位）。探测过程中，首先检查控制字节组，可以快速跳过大量不匹配的槽位。

性能优化

  1. SIMD 加速​​：利用 SIMD 指令并行比对多个控制字节，这是其性能卓越的关键之一
  2. 缓存友好​​：连续的数组存储使得 CPU 缓存利用率更高，减少了缓存未命中
  3. 惰性删除​​：删除元素时并不立即压缩数组，而是将其标记为“已删除”，后续插入操作可以复用这些槽位

Boost 库实现

Boost 1.81 版本引入了boost::unordered_flat_map，它也是一个基于开放寻址的高性能哈希容器。

底层策略

底层策略同样基于开放寻址和线性探测。所有元素也是存储在单个数组中。

核心机制

核心机制也是控制字节：也使用了类似于控制字节的​​元数据​​来管理槽位状态。其快速路径（fast path）在每次查找时只需​​一次条件判断​​和​​一次指针解引用​​，效率极高。

内存布局

内存布局：倾向于将​​键值对直接存储​​在主数组中（与 absl 可能分离存储元数据的策略略有不同），但同样保证了数据的连续性。

哈系探测

哈希探测：与 absl 类似，通过哈希函数映射到初始索引，然后进行线性探测。

性能优化

官方基准测试显示，其性能与 absl::flat_hash_map和 google::dense_hash_map处于同一梯队，甚至在许多场景下更具优势。其设计目标之一就是提供异常出色的查找速度。

对比总结：absl::flat_hash_map vs. boost::unordered_flat_map

特性 Abseil (absl::flat_hash_map) Boost (boost::unordered_flat_map)
​​核心策略​​ 开放寻址 + 线性探测 开放寻址 + 线性探测
​​元数据​​ ​​控制字节​​（单独数组），存储状态和部分哈希值 类似的​​元数据​​（具体实现未完全公开），集成或与数据交错
​​关键优化​​ ​​SIMD 指令​​批量处理控制字节 极简的​​快速路径​​（一次条件判断+一次指针解引用）
​​内存布局​​ ​​数据与元数据分离​​，利于 SIMD 数据连续存储，优化缓存 locality
​​删除操作​​ ​​惰性删除​​（标记为已删除） 类似惰性删除机制
​​性能表现​​ 极高性能，尤其在查找和迭代方面 极高性能，基准测试中常名列前茅

思考：不如直接说是vector？

“直接用vector实现一个flat_map不就好了？” 这确实是 flat_map的核心思想之一：​​利用排序的 vector或类似连续容器，通过二分查找进行高效的查询​​。

了解 map、flat_map、unordered_flat_map 和 vector 的区别非常重要，它们各自有不同的设计目的和性能特性。下面解释它们的核心区别，并分析为什么“直接用 vector 实现一个 flat_map”的想法在实践中并不简单。

四个容器核心区别一览

特性 std::vector std::flat_map (C++23) std::unordered_flat_map (或类似实现) std::map (参考)
​​底层数据结构​​ 连续内存数组 ​​两个排序的数组​​ (键数组+值数组 或 pair 数组) ​​开放寻址哈希表​​ (连续内存块) 红黑树 (节点式)
​​元素顺序​​ 插入顺序 ​​按键排序​​ ​​无序​​ 按键排序
​​查找复杂度​​ O(n) (线性) O(log n) (二分查找) ​​O(1) 平均​​ (哈希) O(log n)
​​插入/删除复杂度​​ 尾部 O(1)*, 中间 O(n) O(n) (需移动元素) O(1) 平均 (摊销) O(log n)
​​缓存友好性​​ ​​极佳​​ (连续内存) ​​极佳​​ (连续内存) ​​佳​​ (主要数据连续) 差 (内存碎片)
​​内存开销​​ 很低 低 中 高 (每个节点含指针)
​​迭代器稳定性​​ 插入/删除可能失效 ​​任何操作都可能失效​​ 插入/删除可能失效 ​​稳定​​ (除删除元素)
​​核心优势​​ 顺序访问、遍历、随机访问 ​​有序且缓存友好​​的查找 ​​极速查找​​，不关心顺序 有序且迭代器稳定
​​典型场景​​ 动态数组、需频繁遍历 ​​需有序且查找频繁​​的场景 ​​纯键值查询​​、缓存、字典 需​​有序且频繁插入删除​​

注：vector 尾部插入为摊销常数复杂度，可能触发重新分配。

为何不直接用 Vector 实现 Flat Map？

然而，标准库（或 Boost/Abseil 等库）提供的 flat_map 相比自己用 vector 手动实现，有以下​​关键优势和考量​​：

  1. ​封装与易用性​​：
    • 它​​封装了所有复杂逻辑​​：维护排序状态、二分查找、处理插入和删除时的元素移动、迭代器失效管理等。
    • 提供了一套​​完整且标准的关联容器接口​​（如 insert, erase, find, lower_bound），让你可以像使用 std::map 一样使用它，无需重复造轮子。
  2. ​性能优化​​：
    • ​精心设计的底层结构​​：例如，std::flat_map 可能采用​​两个分离的数组​​分别存储键和值，而不仅仅是 std::vector<std::pair<Key, T>>。这种设计可以​​进一步提升缓存效率​​，因为在二分查找比较键时，加载到缓存中的都是键，避免了无关值数据的干扰。
    • ​算法优化​​：库实现会使用最合适的二分查找算法，并处理所有边界情况。
  3. ​内存管理​​：
    • 它会​​智能地处理内存分配和重新分配​​，比如在插入元素前预留空间以避免频繁扩容，就像一个好的 vector 用法一样。
  4. ​异常安全​​：
    • 库实现会提供​​更强的异常安全保证​​，正确处理在插入、移动元素过程中可能发生的异常，确保容器状态不被破坏。
  5. ​与现有生态的兼容性​​：
    • 使用标准或广泛认可的库实现，可以​​更容易地与他人协作​​，并且能保证未来的维护性。

​简单来说​​：你自己当然可以基于 vector 和 std::lower_bound 等算法实现一个类似的功能，但要把它做得像标准库那样健壮、高效和易用，需要大量的工作和测试。flat_map 本质上就是为你提供了这个“轮子”。

四个容器如何选择？

map、flat_map、unordered_flat_map 和 vector 如何选择：
选择哪个容器取决于你的具体需求：

  • ​需要极致的查找速度且不关心顺序​​：选择 unordered_flat_map (或 absl::flat_hash_map, boost::unordered_flat_map)。它是字典、缓存等场景的最佳选择。
  • ​需要元素有序，且查询频繁但插入删除较少​​：选择 std::flat_map。它在提供有序性的同时，拥有了接近 vector 的遍历速度和缓存友好性，非常适合配置表、初始化后几乎不变的数据。
  • ​需要频繁在任意位置插入和删除，且要求迭代器稳定​​：选择 std::map (或 std::unordered_map)。虽然查找稍慢，但插入和删除效率更高（对于 map 是 O(log n)），且迭代器在插入后通常不会失效（unordered_map 在 rehash 时除外）。
  • ​只需要一个简单的动态数组，频繁遍历或随机访问​​：选择 std::vector。它是序列容器的首选。