std::flat_multiset是C++23中基于vector的有序容器，查找快（O(log n)且常数小）但插入/删除慢（O(n)移动），适合读多写少、中等规模、高局部性场景。
std::flat_multiset 在 C++23 中正式落地，它不是红黑树的变体，而是一个基于 std::vector 的有序容器适配器——本质是“排序后的动态数组”。这意味着：插入/删除可能触发内存重分配和大量元素移动，但遍历、缓存命中率、内存紧凑性远优于 std::multiset；它适合读多写少、数据量中等、对局部性敏感的场景，而非高频增删的流式处理。
为什么 std::flat_multiset 查找快但插入慢？
根本原因在于底层存储模型切换：从指针跳转的红黑树节点，变成连续内存块中的二分查找。
-
find()、lower_bound()、upper_bound()都走std::lower_bound调用，时间复杂度仍是 O(log n)，但常数极小——CPU 可预取、缓存行一次性加载多个相邻元素 -
insert()必须先二分定位，再在 vector 中间插入，导致 O(n) 元素后移；若触发扩容，还要重新分配 + 复制全部元素 -
erase(iterator)同理：删除后需将后续所有元素前移，O(n)；且不支持按值批量删除（erase(const key_type&)在flat_multiset中被禁用，避免歧义） - 没有“迭代器失效”的模糊地带：只要没触发 realloc，所有迭代器都有效；一旦扩容，全部失效——这点比
multiset更明确，也更危险
std::flat_multiset 与 std::multiset 的接口差异
两者语义接近，但关键操作签名和行为有硬性区别，混用会编译失败或逻辑出错。
-
insert()返回值不同：std::multiset::insert返回iterator；std::flat_multiset::insert返回std::pair<iterator bool></iterator>（因为底层 vector 插入总成功，但“是否新增了新位置”需靠返回迭代器是否指向已有等值元素判断） - 不支持
emplace_hint()：flat 容器无“提示位置”概念，hint 参数被忽略 - 缺少
key_comp()和value_comp()的 const 版本重载（部分标准库实现尚未补全，使用时需查文档） -
merge()接口存在但语义不同：它把另一个flat_multiset的所有元素归并进当前容器并保持有序，不是原地 inplace 合并，而是清空源容器 + 移动插入，实际开销接近一次重建
什么时候该用 flat_multiset？看这三点
别只盯着“C++23 新特性”就上，它的优势有明确边界。
立即学习“C++免费学习笔记（深入）”；
- 数据静态或半静态：初始化后仅少量插入/删除（比如配置项列表、白名单集合、离线分析中间结果），且总量在几千到几万级——超过 10⁵ 元素时，vector 移动成本开始显著拖累
- 频繁范围查询：如统计 [L, R) 区间内重复值个数，用
lower_bound(L)和upper_bound(R)得到两个迭代器，直接std::distance即可，无需遍历红黑树子树 - 内存受限或追求确定性：flat 容器无指针、无额外树节点元数据，内存占用≈
sizeof(T) * size()；且无动态树旋转，行为更可预测，适合嵌入式或实时系统（前提是写操作可控）
容易踩的坑：erase 和迭代器生命周期
这是最易忽视的实操雷区。
- 调用
erase(it)后，it立即失效，且it + 1也不再安全——因为内部是 vector，删除后所有后续迭代器都偏移了 - 错误写法：
for (auto it = fm.begin(); it != fm.end(); ++it) { if (*it == x) fm.erase(it); }→ 崩溃或跳过元素 - 正确做法：用返回值推进，
it = fm.erase(it)（erase返回下一个有效迭代器）；或改用索引循环、或收集待删位置后倒序删除 - 注意：
clear()后所有迭代器失效；shrink_to_fit()可能触发 realloc，同样令所有迭代器失效
flat_multiset 的“扁平”不是免费的——它把红黑树的指针开销换成了移动开销，把不确定性平衡操作换成了确定性但昂贵的内存复制。是否值得，取决于你手上的数据模式和性能瓶颈点在哪里。别让它成为你 profile 报告里那个突然暴涨的 memmove 调用源。
