C++26 的 std::hive 有多快？

# C++26 的 std::hive 有多快？ Source: https://lemire.me/blog/2026/08/02/how-fast-is-c26s-stdhive/ C++26 在标准库中新增了一个容器：`std::hive`。它意在填补 `std::vector` 和 `std::list` 之间的空白。与 vector 类似，它将元素保存在连续的内存块中，因此遍历时你不需要为每个元素追索指针。与 list 类似，一旦元素被插入，它就永远不会移动：你的指针、引用和迭代器始终保持有效，并且你可以在常数时间内删除任意元素，而不影响其他元素。 在内部，hive 是一个由块组成的链表。每个块携带一个 *skipfield*（跳过字段）：每个槽位有一个小整数，它告诉迭代器需要跳过多已删除的槽位。 据我所知，目前还没有标准库提供 `std::hive`。幸运的是，有一个实现（plf::hive (https://github.com/mattreecebentley/plf_hive)，作者 Matt Bentley）以单个头文件的形式提供，你今天就可以使用。 我使用的元素类型是 `uint64_t`，编译器为 GCC 16.1，并启用了 `-O3 -march=native`，运行在 Intel Xeon Gold 6548N（Emerald Rapids）上，并固定在一个核心上。数字是每元素的纳秒数，以及每元素退役的周期数和指令数。 我们从空容器开始，追加一百万个值，然后销毁容器。 | container | ns/element | instructions/element | |---|---|---| | `std::vector` (`reserve`) | 0.29 | 8.0 | | `std::vector` | 0.81 | 8.0 | | `std::hive` | 1.57 | 16.2 | | `std::hive` (`reserve`) | 1.76 | 17.0 | | `std::list` | 14.22 | 220.0 | `std::list` 每个元素需要一次分配，而 glibc 的 malloc 和 free 加起来，每个元素要花费超过 200 条指令。它落后于其他所有容器一个数量级。这并不新鲜。 有趣的对比是 vector 与 hive。hive 的成本大约是 vector 的两倍，所需指令数也是两倍。这是 skipfield 的代价：每次插入都要写入一个元素 *和* 一个 skipfield 条目，并维护块的记账信息。注意，在我的实验中，对 hive 调用 `reserve` 并无帮助。 接下来，我们遍历容器并对值求和。 | container | ns/element | cycles/element | instructions/element | |---|---|---|---| | `std::vector` | 0.22 | 0.78 | 1.0 | | `std::list` | 1.51 | 5.27 | 4.0 | | `std::hive` | 1.77 | 6.18 | 9.0 | 在这里，hive 的迭代速度并不比链表快，实际上还要稍慢一些，并且比 vector 慢约八倍。 vector 的循环每元素只退休一条指令，并在 0.78 个周期内完成：处理器同时执行多个元素。这之所以可能，是因为 `std::vector` 的实现受益于