C26 的 std::hive 是标准库容器家族里比较特殊的一员。它被设计来解决一个经典矛盾在需要频繁插入和删除元素时我们通常希望已有元素的迭代器和引用保持稳定但同时又希望遍历整个容器时仍然有接近数组的缓存效率。std::list 能满足前者但为每个元素分配独立内存遍历时缓存命中率低std::vector 能满足后者但中间插入和删除会移动元素并使迭代器失效。std::hive 在同一个容器里尝试同时解决这两个问题所以“它到底多快”并不是一句“比 vector 快”或“比 list 快”就能回答的。本文先解释它的内部结构和性能模型再给出可复现的基准测试工程最后分析常见误区和生产选型建议目标是让你能自己判断“这个容器是否适合我的场景”。需要说明的是截至撰写时C26 的标准化和编译器支持状态还会变化如果你的标准库还没有提供 std::hive可以使用参考实现完成同样的实验。1. 先理解 std::hive 的设计动机和性能取舍1.1 传统容器在“频繁插入删除 稳定引用”场景下的短板先看一个非常常见的需求游戏中的实体管理、事件监听器列表、网络连接对象池。这些场景的共同点是对象会被动态创建和销毁同时其他模块可能长期持有指向这些对象的指针或迭代器。如果在中间插入或删除时容器的内存布局发生变化已有指针和迭代器就会失效调用方就不得不重新查找对象或者维护开销很大的索引关系。std::vector在中间插入删除时需要搬移元素复杂度是O(n)而且会让插入位置之后的所有迭代器失效。std::list和std::forward_list可以做到插入删除只影响本节点迭代器稳定性很好但每个元素都要单独分配一块内存。元素本身很小的时候链表节点的堆分配开销甚至比数据本身还大遍历时缓存缺失也非常明显。std::deque是分段的连续内存两端的插入删除很高效但中间插入删除仍然要移动元素并且会触发迭代器失效规则。换句话说传统容器把“迭代器稳定性”和“遍历性能”当成两种互相冲突的能力。一个项目如果要同时满足两者往往只能自己造一个对象池再把外部引用改成索引。这个做法虽然可行但需要处理索引复用、空闲槽管理、内存增长、回收时机等一系列问题。std::hive的出现就是想把这个已经被反复手写的容器下沉到标准库中。1.2 认识 hive 的分块存储和标记删除std::hive的设计思路最初来自plf::colony所以很多讨论 hive 的文章都会拿它做参考实现。它的核心结构不是单一连续数组也不是每个元素一个节点而是由若干固定大小的内存块block组成。块内部仍然是一段连续内存存放实际元素。插入时先在已有 block 中寻找空闲槽位删除时不把后面的元素搬上来而是把当前槽位标记为空闲。迭代器遍历整个 hive 时遇到空闲槽位会跳过。因此已有元素的地址不会因为插入或删除其他元素而改变这是 hive 迭代器稳定性的关键。这种设计有两个直接后果。第一个后果是插入和删除的平均时间复杂度接近常数级别因为不需要大面积搬运数据。第二个后果是 hive 不是“有序容器”元素插入后落在哪个槽位取决于当时的空闲槽分布因此不能假设遍历顺序等于插入顺序。如果你需要严格按插入顺序遍历就需要额外保存顺序信息例如在元素内部记录自增序号。1.3 与 vector / list / deque 的核心差异在进入基准测试之前先用一张表把四个容器的能力差异说清楚。这张表不讨论具体毫秒数只看数据结构层面的复杂度特征。容器中间插入/删除随机访问迭代器稳定性遍历缓存友好度额外内存开销std::vectorO(n)会移动元素O(1)插入/删除后失效极好连续数组低std::listO(1)只改指针不支持其他元素不受影响较差节点分散每个节点一个堆分配std::deque中间 O(n)两端 O(1)O(1)中间插入/删除会失效较好分段连续中等std::hive平均 O(1)移动内部槽位状态不支持其他元素不受影响较好块内连续中等含空闲槽元数据这里要特别说明“平均 O(1)”的含义。hive 插入时需要找到一个空闲槽如果当前所有 block 都满了会分配新的 block。分配新 block 的频次远低于 list 的每元素一次分配但也不是完全不分配。删除只是标记空闲代价很低但如果删除后不整理内存空闲槽会越来越多遍历时跳过的次数也会增加。2. 准备可用的 hive 实验环境2.1 确认编译器与标准库支持情况std::hive是 C26 的候选容器但不同编译器、不同标准库实现的支持进度并不一致。在开始实验前先确认三件事。第一编译器是否支持 C26 或足够新的 C 模式。第二标准库是否提供了 hive 头文件以及它对应的命名空间和头文件名是什么。第三当前实现是否支持你计划用到的方法例如insert、erase、begin、end和size。有些实现会提供 feature-test 宏建议在代码里显式判断#include version #if defined(__cpp_lib_hive) #include hive #define HAVE_STD_HIVE 1 #else #define HAVE_STD_HIVE 0 #endif如果宏没有定义说明当前标准库还没有提供稳定的 std::hive 实现。不要硬写#include hive否则会在编译阶段直接报错。更好的做法是写一个类型别名在标准实现可用时切换到 std::hive不可用时落到参考实现。2.2 使用参考实现完成实验对于还没有内置 std::hive 的环境可以用 plf::colony 作为实验对象。它不是完全相同的实现但设计目标、内存结构和性能特征与 hive 同源。用它跑基准测试得到的是该实现的行为趋势而不是最新标准库的官方成绩。使用参考实现时下载一个头文件放到 include 目录即可。目录结构大致如下hive-bench/ CMakeLists.txt main.cpp include/plf/colony.h如果你的标准库已经支持 std::hive可以保留这套 CMake 结构只把代码里的类型和头文件替换掉。2.3 最小 CMake 工程创建一个新的 CMake 工程用来跑后续的验证程序和基准测试。下面的配置选择了 C20因为参考实现不依赖 C26而且主流编译器对 C20 的支持已经非常稳定。cmake_minimum_required(VERSION 3.20) project(hive_bench CXX) set(CMAKE_CXX_STANDARD 20) set(CMAKE_CXX_STANDARD_REQUIRED ON) add_executable(hive_bench main.cpp) target_include_directories(hive_bench PRIVATE include) if(MSVC) target_compile_options(hive_bench PRIVATE /O2 /DNDEBUG) else() target_compile_options(hive_bench PRIVATE -O2 -DNDEBUG) endif()编译选项中使用-O2或/O2是很重要的一步。基准测试如果不开优化容器内部的小函数和迭代器操作不会被内联结果会和真实生产环境偏差很大。2.4 验证环境是否就绪先写一个最小的验证程序确认可以正常编译、插入、迭代和删除。下面的代码以 plf::colony 为例#include plf/colony.h #include cassert #include iostream int main() { plf::colonyint c; auto it1 c.insert(10); auto it2 c.insert(20); auto it3 c.insert(30); int sum 0; for (auto value : c) { sum value; } assert(sum 60); c.erase(it2); sum 0; for (auto value : c) { sum value; } assert(sum 40); std::cout hive reference implementation works\n; return 0; }程序的重点不是计算结果而是确认三件事insert返回的迭代器可以继续使用删除it2之后it1和it3仍然有效遍历时被删除的元素不会出现。这三点是后续所有性能测试的基础。如果erase的返回值在参考实现中不被支持你可以先auto next std::next(it); c.erase(it); it next;来避开返回值问题。3. 设计并运行一个性能对照实验3.1 性能测试的维度回答“std::hive 多快”这个问题不能只测一种操作。不同的容器在不同的操作上有完全不同的表现真正的性能判断必须拆开来看。测试维度至少应该包含以下四项。第一连续插入大量元素。这一步能反映容器扩展内存、分配槽位和维护元数据的能力。第二删除一部分元素。删除时如果可以持有迭代器vector 需要移动大量元素而 hive 只需要标记槽位。第三删除后遍历剩余元素。这一步是很多人容易忽略的因为 hive 删除后留下的空洞会影响后续遍历速度。第四不同元素大小下复制和移动成本对容器性能的影响。实际项目中你需要根据自己的操作频率来分配测试权重。如果 90% 的操作是遍历那么遍历性能权重最高如果插入删除频繁但很少遍历那么就重点看插入删除。3.2 基准测试代码插入、删除、遍历下面的代码同时测试 vector、list、deque 和 hive 参考实现。为了简单使用 steady_clock 计时去掉输出干扰只记录耗时毫秒数。注意hive 的 insert 不需要指定位置因为它本身就不保证顺序。所以这里只比较“不断插入 N 个元素”的吞吐而不是 vector 的严格尾插。#include plf/colony.h #include chrono #include deque #include iostream #include list #include vector template typename F double time_ms(F f) { auto t0 std::chrono::steady_clock::now(); f(); auto t1 std::chrono::steady_clock::now(); return std::chrono::durationdouble, std::milli(t1 - t0).count(); } int main() { constexpr int N 1000000; std::vectorint v; v.reserve(N); auto v_insert time_ms([] { for (int i 0; i N; i) v.push_back(i); }); auto v_erase time_ms([] { for (auto it v.begin(); it ! v.end();) { if (*it % 2 0) { it v.erase(it); } else { it; } } }); auto v_iter time_ms([] { volatile long long sum 0; for (auto value : v) sum value; (void)sum; }); std::listint l; auto l_insert time_ms([] { for (int i 0; i N; i) l.push_back(i); }); auto l_erase time_ms([] { for (auto it l.begin(); it ! l.end();) { if (*it % 2 0) { it l.erase(it); } else { it; } } }); auto l_iter time_ms([] { volatile long long sum 0; for (auto value : l) sum value; (void)sum; }); std::dequeint d; auto d_insert time_ms([] { for (int i 0; i N; i) d.push_back(i); }); auto d_erase time_ms([] { for (auto it d.begin(); it ! d.end();) { if (*it % 2 0) { it d.erase(it); } else { it; } } }); auto d_iter time_ms([] { volatile long long sum 0; for (auto value : d) sum value; (void)sum; }); plf::colonyint h; auto h_insert time_ms([] { for (int i 0; i N; i) h.insert(i); }); auto h_erase time_ms([] { for (auto it h.begin(); it ! h.end();) { if (*it % 2 0) { it h.erase(it); } else { it; } } }); auto h_iter time_ms([] { volatile long long sum 0; for (auto value : h) sum value; (void)sum; }); std::cout container insert_ms erase_ms iterate_ms\n; std::cout vector v_insert v_erase v_iter \n; std::cout list l_insert l_erase l_iter \n; std::cout deque d_insert d_erase d_iter \n; std::cout hive h_insert h_erase h_iter \n; return 0; }这段代码有几个地方值得解释。volatile long long sum是为了防止编译器把循环优化掉因为 volatile 变量会迫使编译器真正执行加法操作。删除逻辑选择删除偶数元素也就是每隔一个删一个这样所有容器都会经历“删除约一半元素”的压力。对于 vector 和 deque这种删除模式会造成大量元素移动。在真实项目中不要直接照搬这个测试而应该把容器里的int替换成自己的业务结构体并把删除条件改成自己的业务规则。3.3 运行结果与性能趋势解读这里不给出具体毫秒数因为不同编译器和硬件差异很大。但可以总结出一组非常稳定的相对趋势。操作vectorlistdequehive 参考实现连续插入 N 个 int预留后很快较慢每次插入都有节点分配较快中到快块内连续加上空闲槽维护删除一半元素很慢反复搬移元素快只改指针较慢分段内搬移快只标记槽位删除后遍历剩余元素最快内存连续慢节点位置分散快分段连续中到快空洞越多越慢从趋势中可以明显看到vector 是“删除前性能最好删除时性能最差”的容器list 是“插入删除性能稳定但遍历性能一直垫底”的容器hive 则是在删除时接近 list在遍历时又远好于 list但无法达到 vector 的无空洞遍历水平。所以如果只运行插入测试你会觉得 hive 没有想象中快只运行删除测试你会觉得 hive 非常快只运行删除后的遍历测试你会觉得 hive 比 list 优势很大但比 vector 慢。这就是为什么答案必须绑定具体操作比例。3.4 引入分配器、元素大小等变量后会发生什么把元素从int换成一个大结构体结果会明显偏向 hive。因为 vector 在插入和删除时需要反复调用拷贝或移动构造函数而 hive 大部分情况下只是修改槽位状态不移动已有元素。自定义分配器也能揭示很多问题。可以在分配器中统计分配次数和释放次数。列表每个元素一次分配所以分配次数是O(n)vector 通常只有几次预留分配hive 的分配次数介于两者之间每新增一个 block 分配一次block 数量远小于元素数量。元素大小增大后hive 的块内连续内存优势仍然存在但单个 block 能容纳的元素数量会变少block 数量增加遍历时的跳转成本也会增加。元素大小为几十字节时hive 通常仍然有明显优势当元素大到超过一个缓存行时任何容器都会面临更严重的缓存压力这时最好先用实际结构体做基准而不是凭直觉选型。4. 拆解 std::hive 的性能来源4.1 插入为什么是平均 O(1) 且不需要移动元素hive 内部维护着空闲槽位信息。插入一个元素时不需要像 vector 那样把当前位置之后的所有元素后移也不需要像 list 那样新建一个独立节点。它只需要在空闲槽中找到一块位置把元素构造进去然后更新槽位状态。因为已有元素的地址和迭代器保持不变所以插入不会触发大范围拷贝。这就是 hive 在“频繁插入”场景下比 vector 快很多的核心原因。对比 vector即使已经预留了足够容量只要插入位置在中间后续元素仍然要被搬移如果没有预留插入还可能导致整块内存重新分配所有迭代器全部失效。hive 的插入也会遇到“当前块满了”的情况。这时需要分配新的 block。新 block 可能一次容纳几十个甚至上百个元素而不是每个元素分配一次因此分配频率远低于 list。这也解释了为什么 hive 插入通常比 list 快。4.2 删除为什么只改变迭代器而不是搬运数据删除一个元素时hive 不会把后面的元素向前移动。它只把目标槽位标记为空闲并把这个槽位加入空闲列表。因此删除操作的代价主要是一个标记和一个链表操作和元素数量无关。相比之下vector 在删除中间元素时需要把删除位置之后的所有元素全部前移最坏情况下是O(n)。即使只用erase删除一个元素也可能产生大量拷贝操作。元素越接近开头移动量越大。如果元素复制成本很高可能一次erase就比 hive 的几千次删除还慢。删除之后其他元素的迭代器为什么仍然有效因为 hive 的内存块没有发生移动其他元素仍然待在原来的地址上。只有被删除元素自己的迭代器会失效。这种语义对游戏实体列表、事件注册表这类需要外部持有引用的场景非常合适。4.3 遍历为什么比 std::list 快链表最大的问题不是插入删除慢而是遍历慢。因为每个节点在堆上独立分配相邻元素在内存中的地址可能相隔很远。CPU 加载一个节点之后下一个节点大概率不在同一个缓存行里于是每访问一个元素都可能在等内存。hive 遍历时会连续访问同一个 block 中的多个元素。block 内部是一段连续内存因此局部性比链表好很多。即使中间存在空闲槽需要跳过缓存预取仍然能覆盖到附近的存活元素。空洞越少遍历越接近连续数组。这里也有一个容易被忽略的性能上限如果大量删除之后没有整理hive 的遍历可能要跳过很多空洞。假设一个 block 原本有 64 个槽位删除后只剩 2 个存活元素遍历仍然会扫描整个 block。如果这样的 block 很多hive 的遍历速度会显著下降。这也是 hive 不适合“删除后不整理且高频遍历”场景的原因。4.4 它为什么无法替代随机访问容器hive 的设计目标是稳定迭代器和高效插入删除但它不提供operator[]也不保证随机访问是O(1)。即使某些参考实现提供了看起来像随机访问的迭代器定位第 N 个元素仍然需要跳过很多空洞本质上不是 vector 那种平坦数组访问。如果你的核心需求是按下标访问元素例如实现排序数组、二分查找、矩阵计算那么 vector 或 deque 仍然是正确选择。hive 适合的是“先持有迭代器再通过迭代器访问元素”的模型。在选型时把随机访问需求是否必需列出来比纠结基准数字更有价值。5. 性能测试中的常见误区和排查路径5.1 编译失败找不到 std::hive现象代码写了#include hive但编译时报“No such file or directory”。可能原因当前标准库还没有实现 std::hive或者头文件名不是hive而是其他名称。检查方式先查看编译器的功能特性宏再查实现文档中 hive 对应的头文件名和命名空间。解决方式使用参考实现或者等到当前标准库正式支持后再切换。预防措施在工程里定义一个类型别名例如#if HAVE_STD_HIVE using object_container std::hiveMyObject; #else using object_container plf::colonyMyObject; #endif这样业务代码不需要全部改写只需要调整容器实现。5.2 把 hive 当成 vector 用现象尝试调用hive_container[5]或者把hive_container.begin()传给一个要求随机访问迭代器的算法结果编译失败或运行错误。原因hive 不支持按下标访问也不是严格的有序容器。解决方式如果只是需要临时排序可以先把元素复制到 vector排序后再使用如果整个项目都需要随机访问那就应该使用 vector 或 deque。这个误区在性能测试中也会出现导致你拿一个错误的容器做不适合它的操作最终得出“hive 很慢”的结论。5.3 erase 后迭代器误用现象在遍历容器时直接删除当前迭代器然后继续使用这个迭代器导致崩溃或未定义行为。for (auto it h.begin(); it ! h.end(); it) { if (should_erase(*it)) { h.erase(it); // 错误it 已经失效 } }原因erase(it)之后it不再指向有效元素。解决方式使用it h.erase(it)或者在删除前先保存下一个迭代器for (auto it h.begin(); it ! h.end();) { auto next std::next(it); if (should_erase(*it)) { h.erase(it); } it next; }这个错误和 vector/list 的erase迭代器处理规则本质相同但 hive 给了你“迭代器稳定”的暗示反而容易让人放松警惕。要注意hive 保证的是“其他元素”的迭代器稳定不保证被删除元素的迭代器继续有效。5.4 删除多后遍历反而变慢现象删除大量元素后当前容器 size 很小但遍历耗时和删除前差不多甚至更慢。原因删除只是标记槽位为空并没有真正释放所有内存。容器中仍然有很多空闲 block 和空闲槽位遍历时每次都要跳过这些空洞。检查方式打印容器当前的大小、block 数量或空闲槽数量。如果你的参考实现提供了整理接口可以整理后再遍历。解决方式如果删除后需要长期高频遍历建议在删除动作结束后把存活元素复制到一个新容器中或者使用支持压缩内存的容器操作。预防措施不要只关注删除耗时要把“删除后接下来要做什么”纳入测试。5.5 小对象场景下 hive 没有明显优势现象元素类型是int或小结构体测试结果显示 vector 仍然最快甚至比 hive 快很多。原因vector 的连续内存和零元数据开销在小对象场景下优势明显而 hive 需要维护块信息、空闲槽和跳过逻辑。这不是 bug而是数据规模、元素大小和操作模式共同作用的结果。解决方式在真实负载下做基准而不是用 int 模拟所有业务对象。如果你的业务对象确实只是一个 8 字节字段并且能接受中间插入删除导致迭代器失效那 vector 仍然是合理的默认选择。5.6 hive 性能排查清单在实际项目中遇到“hive 没有想象中快”时按下面顺序排查。检查项检查方式建议编译器优化是否开启查看编译命令是否含-O2/-O3//O2优化关闭时容器性能会被低估迭代器稳定性是否真的需要检查删除插入后是否仍在引用旧迭代器不需要稳定迭代器时用 vector 更简单是否把 hive 当随机访问容器用搜索代码中的operator[]存在索引访问时改用 vector/deque删除后是否立即遍历在 erase 后统计遍历耗时高频遍历场景先压缩容器内存元素大小是否过小用小结构体和大型对象分别测试大对象场景 hive 优势更明显是否使用自定义分配器统计分配次数确认空闲槽和 block 的分配是否符合预期标准库实现是否成熟查看