先问大家一个很实际的问题如果你维护一个游戏实体列表需要在每一帧遍历所有存活单位同时频繁生成子弹、敌人还要在单位死亡时把它从列表里删掉。用std::vector的话删除中间元素代价太高用std::list的话增删倒是稳定但遍历起来缓存命中率很差。这种“既要稳定迭代器又要尽量快的遍历”的需求正是 C26 新容器std::hive想解决的核心问题。本文会把std::hive的来龙去脉、内部原理、性能表现和真实使用案例完整拆开并给出基于 Boost 实现的基准测试代码。即使你还没用上 C26 标准库也可以通过 Boost.Container 提前体验它的 API 和性能特征。1. 背景与核心概念1.1 std::hive 是什么std::hive是 C26 标准库候选容器之一前身是提案 P0447 中的std::colony。它与std::vector、std::list并列属于一种无序节点容器。所谓“无序”不是指元素自动排序而是指它不保证元素的遍历顺序与插入顺序一致也不支持随机访问。它最核心的三个卖点是插入、删除操作均摊 O(1) 复杂度插入或删除某个元素时其他元素的迭代器、指针和引用不会失效内部采用分块连续内存遍历时依然有比较好的缓存局部性。简单理解std::hive想要做到std::list那样的“稳定增删”同时尽量接近std::vector的“连续内存遍历速度”。1.2 为什么需要 std::hive先回顾一下现有主流容器的痛点。std::vector是连续内存数组遍历速度最快随机访问也是 O(1)。但它有两个问题在头部或中间插入/删除元素需要搬移后续所有元素复杂度 O(n)一旦触发扩容或删除元素已有元素的迭代器可能失效。std::list是双向链表每个节点单独分配所以插入和删除操作只需要修改指针复杂度 O(1)并且除了被删除元素其他元素的迭代器稳定。但它的问题也很明显每个节点包含两个指针额外内存开销大节点散落在堆内存中遍历时缓存命中率低尤其在元素规模较大时性能下降明显分配和释放节点的代价对高频操作来说并不低。而实际业务里很多场景并不是“只追加元素”的 vector 场景也不是“只遍历、偶尔删头部”的 list 场景而是“需要稳定持有某个实体引用、同时高频删除中间元素”的场景。这种场景下std::hive提供了一种新的平衡点块内接近连续内存块间通过指针/索引连接删除元素只标记空洞插入时优先复用空洞。1.3 std::hive 的适用场景从容器特性上看以下场景很适合使用std::hive游戏引擎中的实体管理例如子弹、敌人、粒子系统事件系统或任务调度器需要长时间持有任务迭代器图结构中的节点集合删除节点后不想让其他节点的引用失效对象池、实体池等需要频繁创建与销毁对象的场景。反过来如果业务主要依赖随机访问或者要求严格保持插入顺序std::hive并不是合适的选择继续使用std::vector或std::deque会更合理。2. 环境准备与版本说明2.1 C26 与标准库实现现状C26 是继 C23 之后的新标准版本目前还在草案阶段。虽然std::hive的提案已经持续维护了相当长时间但在主流编译器如 GCC、Clang、MSVC的标准库中std::hive还没有正式落地。因此在写本文的过程中我不会直接使用标准库里的std::hive而是使用Boost.Container 库中的boost::container::hive它的 API 设计与 C26 的std::hive提案保持一致。等到未来标准库实现落地迁移成本会很低。2.2 使用 boost::container::hive 体验 APIBoost.Container 在较新版本中加入了 hive 容器头文件是#include boost/container/hive.hpp请确认你的 Boost 版本不要过旧。如果编译时找不到hive.hpp说明当前 Boost 版本太低需要升级或者使用提案作者维护的单头文件库plf::colony作为替代体验。boost::container::hive的基本用法和std::list类似boost::container::hiveint h; h.insert(10); h.insert(20);更多操作会在后面的章节展开。2.3 编译环境与命令本文示例代码不再依赖 CMake所有测试可以直接用单个.cpp文件编译运行。推荐环境如下操作系统Linux 或 WindowsWSL、MSVC 均可编译器GCC 13 / Clang 16需要能编译 C17 或 C20Boost建议使用较新版本并且需要包含 Boost.Container编译选项建议开启-O2否则性能测试结果没有参考价值。编译命令示例g -stdc17 -O2 -Wall bench.cpp -o bench ./bench如果你的项目使用 CMake在CMakeLists.txt中只需要正常链接 Boost 库即可不需要额外find_package因为 hive 是 header-only 容器。3. std::hive 核心原理拆解3.1 分块存储与空洞复用std::hive内部由多个“块block”组成。每个块内部是一段连续的内存用于容纳元素。每个元素在块中占用一个“槽位slot”槽位除了保存元素本身还会保存一些控制状态例如“当前槽位是否被占用”。当删除一个元素时hive 不会像std::vector那样搬移后续元素而是将该槽位标记为空闲并把空槽的下标记录到该块的“空洞列表”中。当插入一个新元素时hive 会优先从空洞列表中找一个空闲槽位放入新元素从而避免频繁分配新内存。这种设计带来的直接好处是删除操作不会移动已有元素因此已有迭代器自然稳定插入操作优先复用旧内存分配次数比 list 少块内部依然连续遍历一个块时对 CPU 缓存更友好。3.2 迭代器稳定性的来源很多人第一次接触 hive 时会疑惑它内部不是会复用空洞吗复用空洞会不会导致其他迭代器失效答案是不会。因为 hive 的迭代器内部记录的是某个“块”和该块中的“槽位索引”而不是一块连续数组的固定偏移。删除一个元素后虽然槽位被标记为空但其他元素还在各自的槽位里内存地址没有变化。之后即使有新元素复用了这个空槽其他元素也不会移动。所以 hive 保证在插入或删除元素时除了指向被删除元素的迭代器、指针、引用之外其余所有迭代器、指针、引用都保持有效。这个保证比std::list更强吗其实std::list也有类似的迭代器稳定性但std::list每个节点是独立分配内存遍历时缓存局部性差。hive 用分块连续内存换取了接近 vector 的遍历速度同时保留了节点式容器的稳定性。3.3 插入、删除、遍历的复杂度分析从算法复杂度来看操作std::vectorstd::liststd::hive尾部插入均摊 O(1)O(1)均摊 O(1)头部/中间插入O(n)O(1)均摊 O(1)删除指定位置O(n)需搬移O(1)均摊 O(1)遍历O(n)缓存极好O(n)缓存较差O(n)缓存较好随机访问O(1)不支持不支持元素顺序插入顺序稳定插入顺序稳定不保证与插入顺序一致注意“均摊”二字。hive 在空洞耗尽时仍然需要分配新的 block因此单次插入可能触发 block 分配整体上均摊后仍是 O(1)。3.4 std::hive 与 vector / list 的取舍从上面表格可以看出hive 并不是全能的它不能做随机访问所以不能用它替代 vector 的下标访问场景它不保证顺序所以如果业务依赖“按插入顺序遍历”hive 不适合它的元素槽位包含额外控制信息因此内存占用比 vector 大但通常比 list 的双指针节点小。因此选型的核心逻辑是如果你需要频繁在容器“中间”删除或插入元素同时希望遍历尽量快并且不依赖元素顺序那么 hive 是很值得尝试的选项。如果只是尾部追加或者核心诉求是随机访问vector 依然是最优解。4. 性能实测编写基准测试程序4.1 测试目标与实验设计纸上谈兵没有说服力下面用实际代码测试三种容器的性能差异。测试环境并不过度重要重点是看相对趋势。测试包括插入性能插入 100 万个 int 元素比较耗时遍历性能对 100 万个 int 元素求和比较耗时删除性能删除一半元素比较耗时。由于std::vector删除中间元素是 O(n²) 级别为了让测试能在合理时间内跑完删除测试使用 10 万个元素。测试代码会分别使用std::vectorintstd::listintboost::container::hiveint4.2 插入性能测试首先测试尾部插入。std::vector和std::list使用push_backhive使用insert。#include boost/container/hive.hpp #include chrono #include iostream #include list #include vector using namespace std::chrono; const int INSERT_COUNT 1000000; void benchInsert() { // vector 尾部插入 { std::vectorint v; auto start steady_clock::now(); for (int i 0; i INSERT_COUNT; i) { v.push_back(i); } auto end steady_clock::now(); std::cout vector insert: duration_castmilliseconds(end - start).count() ms, size v.size() \n; } // list 尾部插入 { std::listint l; auto start steady_clock::now(); for (int i 0; i INSERT_COUNT; i) { l.push_back(i); } auto end steady_clock::now(); std::cout list insert: duration_castmilliseconds(end - start).count() ms, size l.size() \n; } // hive 插入 { boost::container::hiveint h; auto start steady_clock::now(); for (int i 0; i INSERT_COUNT; i) { h.insert(i); } auto end steady_clock::now(); std::cout hive insert: duration_castmilliseconds(end - start).count() ms, size h.size() \n; } }这里使用size()保证容器状态被使用者接收避免编译器整体优化掉循环。从通常经验看vector连续分配最快hive因为要维护 block 结构和空洞信息会慢一点但会比list快很多因为list每次插入都要单独分配/释放节点。4.3 遍历性能测试接下来测试遍历性能。为了不让求和结果被优化掉最后把sum打印出来。void benchTraverse() { // vector 遍历 { std::vectorint v; for (int i 0; i INSERT_COUNT; i) { v.push_back(i); } long long sum 0; auto start steady_clock::now(); for (int x : v) { sum x; } auto end steady_clock::now(); std::cout vector traverse: duration_castmilliseconds(end - start).count() ms, sum sum \n; } // list 遍历 { std::listint l; for (int i 0; i INSERT_COUNT; i) { l.push_back(i); } long long sum 0; auto start steady_clock::now(); for (int x : l) { sum x; } auto end steady_clock::now(); std::cout list traverse: duration_castmilliseconds(end - start).count() ms, sum sum \n; } // hive 遍历 { boost::container::hiveint h; for (int i 0; i INSERT_COUNT; i) { h.insert(i); } long long sum 0; auto start steady_clock::now(); for (int x : h) { sum x; } auto end steady_clock::now(); std::cout hive traverse: duration_castmilliseconds(end - start).count() ms, sum sum \n; } }在数据规模较大时list的遍历时间通常明显高于vectorhive会非常接近vector。这就是 hive 分块连续存储带来的优势。4.4 删除性能测试删除测试使用 10 万个元素删除策略是“从第一个元素开始每隔一个删除一个”最终容器里保留一半元素。const int ERASE_COUNT 100000; void benchEraseHalf() { // vector 删除中间元素 { std::vectorint v; for (int i 0; i ERASE_COUNT; i) { v.push_back(i); } auto start steady_clock::now(); auto it v.begin(); bool erase_this true; while (it ! v.end()) { if (erase_this) { it v.erase(it); } else { it; } erase_this !erase_this; } auto end steady_clock::now(); std::cout vector erase half: duration_castmilliseconds(end - start).count() ms, size v.size() \n; } // list 删除一半元素 { std::listint l; for (int i 0; i ERASE_COUNT; i) { l.push_back(i); } auto start steady_clock::now(); auto it l.begin(); bool erase_this true; while (it ! l.end()) { auto next std::next(it); if (erase_this) { l.erase(it); } erase_this !erase_this; it next; } auto end steady_clock::now(); std::cout list erase half: duration_castmilliseconds(end - start).count() ms, size l.size() \n; } // hive 删除一半元素 { boost::container::hiveint h; for (int i 0; i ERASE_COUNT; i) { h.insert(i); } auto start steady_clock::now(); auto it h.begin(); bool erase_this true; while (it ! h.end()) { auto next std::next(it); if (erase_this) { h.erase(it); } erase_this !erase_this; it next; } auto end steady_clock::now(); std::cout hive erase half: duration_castmilliseconds(end - start).count() ms, size h.size() \n; } }删除测试中std::list和boost::container::hive的删除代价都很低。std::vector则因为每次删除都要搬移大量元素耗时可能高出一个数量级以上。这也是 hive 最值得关注的场景之一。4.5 预期结果与分析测试项std::vectorstd::liststd::hive插入 100 万元素最快较慢中等遍历 100 万元素最快最慢接近 vector删除一半元素很慢快快迭代器稳定性不稳定稳定稳定注意不同机器、不同编译器、不同标准库实现得到的具体毫秒数会有很大差异。但如果代码正确、开启 O2 优化整体趋势通常是稳定的vector适合尾部追加和随机访问list适合稳定增删但遍历不频繁的场景hive在“需要稳定迭代器 频繁删除 遍历较多”的场景中综合表现最好。5. 真实场景实战游戏实体管理5.1 需求描述假设你在做一个简单的 2D 游戏框架。每个实体包含唯一 id坐标 x、y血量 hp。游戏运行过程中会不断生成新实体也会因为受到伤害而死亡。要求是能在任意时刻持有某个实体的迭代器能安全地在遍历过程中删除死亡实体新实体的加入不会让旧实体的迭代器失效。5.2 使用 hive 管理实体这里实现一个简单的EntityManager核心容器使用boost::container::hiveEntity。#include boost/container/hive.hpp #include cstdint #include iostream struct Entity { std::uint64_t id; float x; float y; int hp; bool alive() const { return hp 0; } }; class EntityManager { public: boost::container::hiveEntity entities; void spawn(float x, float y, int hp) { entities.insert(Entity{nextId_, x, y, hp}); } void update() { for (auto it entities.begin(); it ! entities.end();) { if (!it-alive()) { auto next std::next(it); entities.erase(it); it next; } else { it; } } } void print() const { std::cout alive entities: entities.size() \n; for (const auto e : entities) { std::cout id e.id hp e.hp ( e.x , e.y )\n; } } private: std::uint64_t nextId_ 0; };5.3 验证迭代器稳定性下面写一段演示代码验证“新增实体后已经保存的迭代器仍然可以访问”。int main() { EntityManager manager; manager.spawn(0.0f, 0.0f, 100); manager.spawn(1.0f, 1.0f, 50); manager.spawn(2.0f, 2.0f, 80); // 保存指向第一个实体的迭代器 auto first manager.entities.begin(); // 新增实体后first 仍然有效 manager.spawn(3.0f, 3.0f, 60); // 第一个实体受到 100 点伤害hp 变为 0 first-hp - 100; // 更新时清理死亡实体 manager.update(); manager.print(); return 0; }这段代码如果用std::vector实现manager.entities.begin()之后一旦spawn造成扩容first就失效了。而使用hive新增实体不影响已有实体的迭代器、指针和引用这是实体系统里非常实用的特性。5.4 与 list 实现的对比如果用std::listEntity也能实现类似效果因为 list 同样提供迭代器稳定。但两者在性能上存在差异list的每个节点独立分配实体数量达到十万以上时遍历会产生大量 cache misshive的元素按块连续存储遍历时对缓存友好得多高频spawn和死亡删除场景下hive的内存复用机制也优于 list 的频繁new/delete。因此在游戏这类对实时性要求较高的系统中hive是比list更合适的数据结构。6. 常见问题与排查思路6.1 标准还没出能直接用 std::hive 吗截至本文写作时C26 还在草案阶段主流标准库还没有实现std::hive。建议通过以下路径提前体验