C++23在标准库中引入了一组新的容器适配器，其中就包括std::flat_multiset。它是一个基于有序数组的关联容器，允许存储重复元素，并始终保持元素有序。与基于红黑树实现的std::multiset不同，flat_multiset内部采用连续内存的vector作为底层结构，这一设计变化带来了完全不同的性能特征。本文将深入剖析它的实现原理、性能表现和使用场景。
一、底层实现原理：有序数组如何支撑关联容器
std::flat_multiset实际上是一个容器适配器，它并不自己管理内存，而是包装了一个底层序列容器（默认是std::vector）。所有元素在这个vector中按照比较规则（默认是std::less）保持有序排列。当你插入一个元素时，容器通过二分搜索找到合适的插入位置，然后将该位置之后的元素整体后移一位，腾出空间放入新元素；删除元素时则将后续元素整体前移一位。
这种实现的直接代价是插入和删除的时间复杂度为O(n)，因为移动元素需要线性时间。但换来的是几个显著的优势：第一，查找操作可以退化为纯二分搜索，不需要像红黑树那样沿着指针层层跳转；第二，连续内存布局对CPU缓存极其友好，现代CPU的缓存行预取机制可以充分发挥作用；第三，没有每个节点额外的指针开销，内存占用大幅降低。
标准库还允许你通过模板参数指定底层容器类型，例如使用std::deque代替std::vector，定义形式如下：
#include <flat_set> // 默认使用std::vector作为底层容器 std::flat_multiset<int> fm1; // 显式指定底层容器为deque std::flat_multiset<int, std::less<int>, std::deque<int>> fm2;
二、性能对比：flat_multiset与multiset谁更快
性能是这个容器存在的核心意义。我们先从理论复杂度层面做一个对比：std::multiset的插入、删除、查找都是O(log n)；flat_multiset的查找是O(log n)，但插入和删除是O(n)。单看复杂度，flat_multiset似乎全面处于劣势，但实际运行中的表现往往相反。
原因在于常数因子和缓存行为。红黑树的每个节点在堆上独立分配，节点之间通过指针连接，查找时CPU需要在内存中不断跳跃，缓存命中率很低。而flat_multiset的元素紧密排列在连续内存中，二分搜索虽然逻辑上跳跃访问，但当数据量在几万到几十万级别时，大部分数据都能装进CPU的L2、L3缓存，实际查找速度通常能达到multiset的2到5倍。
内存占用差距同样明显。存储一百万个int类型元素，multiset每个节点除了4字节数据外还要存储颜色标记、三个指针以及内存分配器的开销，实际内存占用可能是vector版本的5到10倍。以下是两种容器的对比表格：
| 特性 | std::multiset | std::flat_multiset |
|---|---|---|
| 底层结构 | 红黑树 | 有序数组（vector） |
| 插入复杂度 | O(log n) | O(n) |
| 删除复杂度 | O(log n) | O(n) |
| 查找复杂度 | O(log n) | O(log n) |
| 迭代器稳定性 | 插入删除不失效 | 插入删除可能失效 |
| 内存占用 | 高（含指针开销） | 低（紧凑连续） |
| 缓存友好性 | 差 | 优秀 |
需要注意的一个关键点是迭代器失效规则。flat_multiset本质上依赖vector，任何可能导致vector重新分配内存的操作都会使所有迭代器失效，这一点和multiset形成鲜明对比，写代码时务必小心悬空迭代器问题。
三、与flat_set的区别以及典型使用场景
flat系列容器一共有四个：flat_set、flat_map、flat_multiset、flat_multimap。flat_multiset与flat_set的区别在于是否允许重复键值。当你调用flat_set的insert插入已存在的元素时，插入会被忽略并返回已有元素的位置；而flat_multiset会正常插入，重复元素会相邻存放。
基于这些特性，flat_multiset最适合的场景是读多写少的数据集合。典型例子包括：配置数据的加载与查询（启动时构建一次，运行期间只读）、排行榜系统（周期性批量重建，期间高频查询名次）、词典或索引表（预排序后大量查找）、以及需要频繁进行范围查询的统计场景。这些场景的共同点是查找和遍历操作远多于插入删除。
反过来，如果你的程序需要频繁地随机插入和删除元素，例如实时消息队列的去重管理，那么flat_multiset的O(n)插入会成为性能瓶颈，此时坚持使用传统的multiset才是正确选择。选型的核心判断依据就是读写比例：读操作占比超过九成的场景，flat容器几乎总是更优解。
四、基本用法示例
flat_multiset的接口与multiset几乎完全一致，学习成本几乎为零。下面的示例展示了插入、重复元素处理、查找和范围查询的基本操作：
#include <iostream>
#include <flat_set>
int main() {
std::flat_multiset<int> fm;
// 插入元素，允许重复
fm.insert(5);
fm.insert(3);
fm.insert(8);
fm.insert(3); // 重复元素也会被插入
// 元素始终保持有序，重复元素相邻
for (int v : fm) {
std::cout << v << " "; // 输出: 3 3 5 8
}
std::cout << "\n";
// 统计某个值出现的次数
std::cout << "count(3) = " << fm.count(3) << "\n"; // 输出2
// 范围查询：查找所有不小于4的元素
auto it = fm.lower_bound(4);
while (it != fm.end()) {
std::cout << *it << " "; // 输出: 5 8
++it;
}
return 0;
}
除了逐个插入，flat_multiset还提供了一个针对批量构建的优化技巧：当你已经有一批数据需要全部放入容器时，可以先调用insert_range或使用构造函数直接传入迭代器范围，标准库实现会在内部先排序再去重处理，效率远高于逐个调用insert。
此外，flat_multiset支持通过replace方法直接替换底层容器对象，这在需要从外部已排序数据快速构建容器时非常有用，可以完全跳过逐个插入的O(n log n)开销，实现O(n)的整体构建。
总结
std::flat_multiset代表了C++标准库设计思路的一次务实转变：不再执着于单一结构的理论最优复杂度，而是承认缓存友好的连续内存在真实硬件上的巨大价值。在读多写少的场景下，它用更低的内存占用和更快的查找速度提供了明显优于std::multiset的表现。如果你的编译器已经支持C++23（GCC 13以上、MSVC 19.37以上），不妨在实际项目中尝试这个新容器，相信它会给你带来惊喜。
std::flat_multisetC++23有序容器修改时间：2026-09-02 08:52:34