在 C 的容器选型里我经常面临一个两难用std::vector吧中间插入、删除要搬移大量元素迭代器还会失效用std::list吧插入和删除确实变成 O(1) 了但每个元素单独分配一块内存遍历时缓存命中率低到让人怀疑人生。C26 新增的std::hive早期提案名叫std::colony正是冲着这个空白来的。这篇文章不打算只念文档而是把它的性能来源、核心原理、最小可运行示例、四容器对比基准和常见坑一次讲清楚适合正在做 C26 特性调研或者正在为“高频增删对象集合”而烦恼的开发者。1. 从容器痛点认识 std::hive1.1 先看一个经典选型难题业务里有一个对象集合元素数量可能达到几十万每个对象内部会保存另一个对象的指针。程序运行过程中这个集合会频繁插入新对象、删除旧对象而且删除某个对象时其他对象持有的指针必须仍然有效。如果用std::vector一旦容量不够需要扩容所有元素都会被搬移之前拿到的指针、引用、迭代器全部失效。更麻烦的是中间插入和删除是 O(n) 的大量元素要跟着挪位置。如果用std::list指针稳定性问题解决了插入删除也变成 O(1)。但链表每个节点都要单独new节点之间在内存里散布遍历时 CPU 缓存基本帮不上忙。当集合里有几十万个元素时一次全量遍历的性能开销非常明显。std::deque介于两者之间两端操作很快但中间插入删除仍然是 O(n)而且中间操作会导致迭代器大面积失效并不适合“持有交叉引用”的场景。下面这张表能快速看出问题所在容器随机访问中间插入/删除迭代器稳定性遍历缓存友好度std::vectorO(1)O(n)插入、删除都会失效最好std::list不支持O(1)删除只影响被删元素较差std::dequeO(1)O(n)中间操作全部失效较好std::hive不支持摊销 O(1)插入、删除都不影响其他元素接近 vector你会发现std::hive基本上是在“迭代器稳定性”和“缓存友好度”之间找到了一个新的平衡点。1.2 std::hive 是什么先给一个通俗理解std::hive是一个“块式存储的无序容器”它把元素放进若干个连续内存块里而不是像list那样一个元素一个节点。每个块内部是连续数组所以遍历时对缓存比较友好块与块之间通过类似跳跃表的结构串联插入和删除只需要在块内操作不需要搬移其他元素。用术语表达就是std::hive是一个提供 O(1) 摊销插入与删除、并且保证除被操作元素外其他元素指针/引用/迭代器长期稳定的容器。它不提供随机访问也没有严格意义上的元素顺序承诺。它的典型场景包括对象池、实体组件系统ECS、游戏中的飞行子弹或粒子集合。需要大量短生命周期对象且对象之间互相持有指针/引用的系统。需要“一边遍历一边插入/删除”的复杂业务逻辑。1.3 从 colony 到 hive 的一段历史std::hive提案编号是 P0447最早的名字叫std::colony参考实现是plf::colony。这个提案经过多年的修订在 2024 年被标准委员会采纳进入 C26 工作草案名字也从容易产生歧义的colony改成了hive。需要注意的是std::hive和std::set、std::map这类有序容器没有任何关系它不会对元素排序也不要求元素可比较。它跟std::unordered_set也不同它不基于哈希表没有键值概念只是存一堆类型相同的对象。2. std::hive 的性能来自哪里核心原理拆解要回答“How fast is std::hive”这个问题必须先理解它的内部结构。下面三个概念是整个容器性能的关键。2.1 块式存储缓存友好度的来源std::hive内部把存储空间分成若干个“块”block每个块内部是一段连续内存可以存放多个元素。块与块之间通过指针连接遍历时先访问一个块内的连续元素再跳到下一个块。可以用一个简化的示意图来理解hive | -- block[0] : [ e0 | e1 | e2 | e3 | e4 | ... ] | | -- block[1] : [ e5 | e6 | e7 | e8 | ... ] | | -- block[2] : [ ... ]每个元素只占用块内一个槽位元素在块内是紧凑存放的。这意味着遍历一个块时CPU 可以像访问vector一样顺序加载内存预取器能正常工作。相比之下list的每个节点地址都可能相隔很远遍历时 CPU 几乎每次都要等待内存访问这就是list遍历慢的根本原因。当然块与块之间是跳转访问所以hive的遍历速度一般不会超过vector但会比list快很多。元素越小、块内能容纳的元素越多这个优势就越明显。2.2 墓碑标记与空间复用hive删除元素时并不一定立刻释放内存而是在块内把对应槽位标记为“已删除”可以理解为墓碑标记同时把槽位挂到空闲列表上。后续插入新元素时优先复用这些空闲槽位而不是每次重新分配内存。这种设计带来两个好处插入操作大多数时候只是“在已有块的空闲槽位上构造对象”省去了list那种每次malloc/free的开销。删除操作只是修改标记不需要搬移其他元素因此是 O(1) 摊销的。当整个块都变成空闲时hive会根据内部策略回收这个块避免内存无限增长。由于块的分配是成批的内存碎片化程度也会低于list的逐节点分配。2.3 为什么指针和迭代器如此稳定vector扩容时会申请更大的内存然后把旧元素搬过去所以所有旧迭代器都会失效。hive不会这么做它扩容量时是“新开一个块”已有块里的元素原地不动。插入新元素只是找一个空闲槽位删除元素只是打标记也不影响其他元素的位置。因此只要你不删除某个元素本身指向它的指针、引用和迭代器就一直有效。这是hive最核心的工程价值它让“对象之间互相持有裸指针”这种写法变得安全不需要退回到list也不需要引入复杂的shared_ptr循环引用方案。2.4 性能画像总结综合上述机制std::hive的性能特征可以概括为插入、删除均为摊销 O(1)并且分摊到每个元素上的堆分配次数远低于list。遍历速度明显优于list在元素尺寸较小时接近vector。不支持随机访问不能使用operator[]也不能直接std::sort。内存占用高于vector因为需要额外的块头、墓碑标记和空闲槽位但远低于list的“每节点两个指针加分配开销”。所以“How fast”这个问题没有统一答案关键看你和谁比、比哪个操作。后面第五章会给出可复现的基准框架。3. 环境准备与版本说明3.1 编译器与标准库支持情况std::hive是 C26 的新特性目前主流编译器的标准库实现还在陆续跟进。如果你用的是比较新的 GCC、Clang 或 MSVC 预览版可以尝试直接使用#include hive但要注意不同编译器对 C26 特性的支持程度不一样甚至同一个编译器不同小版本也有差异。比较稳妥的做法是先确认你的编译器支持 C26 模式例如 GCC 下使用-stdc2b或-stdc26具体取决于版本。如果你在官方标准库中还没找到std::hive并不代表思路有问题而是实现尚未落地。这时可以退回到参考实现plf::colony它几乎是std::hive的“前身”接口和性能特征高度一致。3.2 参考实现 plf::colonyplf::colony是提案作者维护的单头文件库只有一个plf_colony.h。把它放到项目目录里包含头文件后使用plf::colonyT即可不需要链接第三方库。两个名称的对应关系很简单标准名称参考实现std::hiveplf::colony#include hive#include plf_colony.hstd::hiveTplf::colonyT本文示例默认以plf::colony作为可运行基准因为它在当前大多数编译器上都能直接跑。如果你的编译器已经支持std::hive只需要修改头文件和类型名。3.3 示例项目结构我建议建一个干净的目录来实验hive-demo/ ├── hive_basic.cpp ├── hive_stable.cpp ├── hive_bench.cpp └── plf_colony.h其中hive_basic.cpp是最小入门示例hive_stable.cpp验证指针稳定性hive_bench.cpp是四容器性能对比基准。4. std::hive 快速上手4.1 最小示例插入、遍历、删除先看一个最简单的程序。为了兼容当前主流编译器这里使用plf::colony展示如果你的环境支持 C26把类型名换成std::hive即可。// 文件hive_basic.cpp // 如果编译器支持 C26 的 hive可以把下面两行替换为 // #include hive // using HiveStr std::hivestd::string; #include iostream #include string #include plf_colony.h using HiveStr plf::colonystd::string; int main() { HiveStr h; auto it1 h.insert(hello); auto it2 h.emplace(3, A); // 等价于构造 std::string(3, A)结果是 AAA auto it3 h.insert(world); std::cout size h.size() \n; // 遍历 for (const auto s : h) { std::cout s \n; } // 删除 it2 指向的元素 h.erase(it2); std::cout after erase: h.size() \n; // it1 仍然有效 std::cout it1 value: *it1 \n; return 0; }这里有几个关键点h.insert(value)和h.emplace(args...)都会返回指向新插入元素的迭代器。emplace直接使用参数构造元素避免不必要的临时对象。hive没有push_back统一用insert/emplace。erase返回下一个有效迭代器这一点和vector、list一致。预期输出size 3 hello AAA world after erase: 2 it1 value: hello4.2 验证指针稳定性下面这个例子是hive最吸引人的能力大量插入、删除其他元素都不会影响已经持有元素的指针和迭代器。// 文件hive_stable.cpp #include iostream #include plf_colony.h int main() { plf::colonyint h; // 保存第一个元素 auto keep_it h.insert(2024); int* keep_ptr *keep_it; // 再插入 10000 个元素 for (int i 0; i 10000; i) { h.insert(i); } // 删除 keep_it 之后的 5000 个元素 auto it keep_it; it; for (int i 0; i 5000 it ! h.end(); i) { it h.erase(it); } std::cout 指针解引用结果: *keep_ptr \n; std::cout 迭代器解引用结果: *keep_it \n; return 0; }在这个程序里keep_ptr指向的元素始终没有被删除所以在大量插入和删除之后解引用结果依然是2024。同样的代码如果换成vector在扩容后指针通常会失效程序行为就是未定义的。预期输出指针解引用结果: 2024 迭代器解引用结果: 20244.3 编译运行命令如果使用plf::colonyC17 甚至 C14 就能编译g -stdc17 -O2 -I. hive_basic.cpp -o hive_basic g -stdc17 -O2 -I. hive_stable.cpp -o hive_stable ./hive_basic ./hive_stable如果编译器已经支持 C26 的 hive