C++26 新容器 std::hive：稳定指针与缓存局部性兼得

C++ 博客作者 Sandor Dargo 发表文章，介绍了 C++26 标准中新引入的容器 std::hive。文章指出，C++26 在新容器方面非常慷慨——除了之前介绍的 std::inplace_vector，另一个重要的新容器是 std::hive。它解决了一个长期存在的工程难题：在需要稳定指针/迭代器的同时，保持良好的缓存局部性。

问题背景：游戏引擎的实体管理

文章以一个典型的游戏引擎场景开场：

• 数千个实体：游戏引擎管理着数千个实体（Entity）
• 外部指针：其他子系统持有指向这些实体的指针
• 实体销毁：当一个实体被销毁时，需要从容器中删除
• 问题：
  • 用 std::vector：删除元素后，后面的所有元素都会移动，导致所有指针失效
  • 用 std::list：指针不会失效，但缓存性能很差（节点分散在内存中）

这是一个经典的权衡：稳定指针 vs 缓存局部性。

std::hive 的目标是同时获得两者的优势：稳定的指针和迭代器、O(1) 摊销的插入和删除、良好的缓存局部性。

什么是 std::hive

基本定义

std::hive 是 C++26 引入的新容器，定义在新的 <hive> 头文件中，由提案 P0447R28 引入。

• 名字来源：如果这个名字听起来不熟悉但概念熟悉，你可能知道它的前身 plf::colony——一个经过 28 次修订、八年委员会工作后进入标准的库
• 核心特性：
  • 稳定的指针和迭代器（插入和删除后仍然有效）
  • O(1) 摊销的插入和删除
  • 良好的缓存局部性（得益于连续内存块）
• 适用场景：游戏引擎实体管理、粒子系统、对象池、需要频繁插入删除且持有外部指针的场景

三个核心方面

提案（§V）定义了 std::hive 的三个核心方面：

1. 基于块的内存布局（Block-based Memory Layout）

std::hive 将元素存储在多个固定大小的内存块中：

• 每个块：包含固定数量的元素槽（Slot），内存是连续的
• 块之间：通过指针链接，形成块的链表
• 插入：在当前块的空闲槽中插入，块满后分配新块
• 删除：将槽标记为空闲，不需要移动其他元素

std::hive 内存布局：

块 1 (容量 64)          块 2 (容量 64)          块 3 (容量 64)
┌──────────────┐      ┌──────────────┐      ┌──────────────┐
│ 元素 0  ✓    │      │ 元素 64 ✓    │      │ 元素 128 ✓   │
│ 元素 1  ✓    │      │ 元素 65 空闲  │      │ 元素 129 ✓   │
│ 元素 2 空闲  │      │ 元素 66 ✓    │      │ 元素 130 空闲 │
│ 元素 3  ✓    │      │ ...          │      │ ...          │
│ ...          │      │ 元素 127 ✓   │      │ 元素 191 空闲 │
└──────────────┘      └──────────────┘      └──────────────┘
     │                      │                      │
     └──────────────────────┴──────────────────────┘
                    块链表指针

优势：

• 缓存局部性：每个块内的元素是连续的，遍历时缓存命中率高
• 无移动：删除元素不需要移动其他元素，指针保持稳定
• 可扩展：块的数量可以动态增长，没有容量上限

2. 空闲槽管理（Free Slot Management）

为了高效管理空闲槽，std::hive 使用了一个巧妙的技术：

• 空闲链表：空闲槽被组织成一个链表，每个空闲槽存储下一个空闲槽的索引
• 复用空闲槽：插入时优先使用空闲槽，而不是总是在块末尾添加
• O(1) 插入：从空闲链表中取一个槽，O(1) 时间
• O(1) 删除：将槽加入空闲链表，O(1) 时间

空闲槽管理：

块 1：
┌──────────────┐
│ 元素 0  ✓    │ ← 已使用
│ 元素 1  →2   │ ← 空闲，指向下一个空闲槽（索引 2）
│ 元素 2  →5   │ ← 空闲，指向下一个空闲槽（索引 5）
│ 元素 3  ✓    │ ← 已使用
│ 元素 4  ✓    │ ← 已使用
│ 元素 5  →-1  │ ← 空闲，链表末尾（-1 表示结束）
└──────────────┘

空闲链表头 → 索引 1 → 索引 2 → 索引 5 → 结束

这个技术的巧妙之处在于：空闲槽不需要额外的内存来存储链表指针，因为空闲槽本身的内存可以被复用（存储下一个空闲槽的索引）。

3. 跳过空闲元素的迭代（Skip-field Iteration）

遍历 std::hive 时需要跳过空闲槽。为了高效地做到这一点：

• 跳过字段（Skip-field）：每个块有一个跳过字段，记录块内空闲槽的位置信息
• 快速跳过：遍历时可以快速跳过整个空闲区域，不需要逐个检查每个槽
• 迭代器稳定性：迭代器指向块+槽索引，插入和删除不影响其他元素的迭代器

与其他容器的对比

std::hive vs std::vector

std::hive vs std::list

std::hive vs std::deque

使用示例

基本用法

#include <hive>
#include <iostream>

struct Entity {
    int id;
    float x, y;
    // ...
};

int main() {
    std::hive<Entity> entities;

    // 插入元素
    auto it1 = entities.insert({1, 0.0f, 0.0f});
    auto it2 = entities.insert({2, 10.0f, 20.0f});
    auto it3 = entities.insert({3, 30.0f, 40.0f});

    // 指针稳定：持有指针
    Entity* ptr1 = &(*it1);

    // 删除中间元素
    entities.erase(it2);

    // ptr1 仍然有效！
    std::cout << "Entity 1: " << ptr1->id << std::endl;

    // 遍历（自动跳过空闲槽）
    for (const auto& e : entities) {
        std::cout << "Entity: " << e.id << std::endl;
    }

    return 0;
}

游戏引擎实体管理

#include <hive>
#include <vector>

struct GameObject {
    int id;
    bool active;
    float position[3];
    // ... 其他组件
};

class GameEngine {
    std::hive<GameObject> objects;
    std::vector<GameObject*> render_list;  // 持有指针

public:
    GameObject* spawn_object() {
        auto it = objects.insert(GameObject{});
        GameObject* ptr = &(*it);
        render_list.push_back(ptr);
        return ptr;
    }

    void destroy_object(GameObject* obj) {
        // 从 hive 中删除，指针失效但其他指针不受影响
        // 注意：需要先从 render_list 中移除
        // ...
        objects.erase(obj);  // 需要找到对应的迭代器
    }

    void update() {
        // 遍历所有对象，缓存友好
        for (auto& obj : objects) {
            if (obj.active) {
                // 更新逻辑
            }
        }
    }

    void render() {
        // 使用持有指针的渲染列表
        for (auto* obj : render_list) {
            // 渲染逻辑
        }
    }
};

粒子系统

#include <hive>
#include <cmath>

struct Particle {
    float x, y, vx, vy;
    float life;
    int color;
};

class ParticleSystem {
    std::hive<Particle> particles;
    static constexpr int MAX_PARTICLES = 100000;

public:
    void emit(int count, float origin_x, float origin_y) {
        for (int i = 0; i < count; ++i) {
            particles.insert({
                origin_x, origin_y,
                random_direction(), random_direction(),
                1.0f, random_color()
            });
        }
    }

    void update(float dt) {
        for (auto it = particles.begin(); it != particles.end(); ) {
            it->x += it->vx * dt;
            it->y += it->vy * dt;
            it->life -= dt;

            if (it->life <= 0.0f) {
                it = particles.erase(it);  // O(1) 删除
            } else {
                ++it;
            }
        }
    }

    size_t count() const { return particles.size(); }
};

性能特点

插入性能

• O(1) 摊销：大多数插入是 O(1)（使用空闲槽或当前块的末尾）
• 块分配：当所有块都满时，需要分配新块，这是 O(块大小)，但摊销后是 O(1)
• 比 vector 好：在中间插入比 vector 快得多（不需要移动元素）
• 比 list 好：缓存友好，分配开销小

删除性能

• O(1) 摊销：删除只需要将槽标记为空闲，加入空闲链表
• 比 vector 好：不需要移动元素
• 比 list 相当：都是 O(1)，但 hive 的缓存更好

遍历性能

• 缓存友好：块内元素连续，遍历时缓存命中率高
• 跳过空闲槽：使用跳过字段快速跳过空闲区域
• 比 list 好：list 的节点分散，缓存命中率低
• 比 vector 略差：vector 是完全连续的，但差距不大

内存开销

• 块开销：每个块有少量元数据（块指针、跳过字段、空闲链表头）
• 空闲槽：空闲槽占用内存，但可以被复用
• 比 list 低：list 每个节点有两个指针，hive 只有块级别的指针
• 比 vector 高：vector 没有块开销，但可能有容量浪费

注意事项和限制

1. 迭代器稳定性的细节

• 插入：插入不会使任何现有迭代器失效
• 删除：删除只会使指向被删除元素的迭代器失效，其他迭代器不受影响
• 引用和指针：与迭代器相同，只有被删除元素的引用/指针失效

2. 迭代器的特殊性

• 不是随机访问迭代器：std::hive 的迭代器是前向迭代器（Forward Iterator），不是随机访问迭代器
• 不支持 it + n：不能直接做算术运算
• std::next(it, n) 是 O(n)：需要逐个遍历
• 但 operator[] 是 O(1)：通过块+索引直接访问

3. 元素顺序

• 不保证插入顺序：由于插入会复用空闲槽，元素的物理顺序可能与插入顺序不同
• 遍历顺序：遍历顺序是块的顺序 + 块内槽的顺序，不一定是插入顺序
• 如果需要顺序：使用 std::vector 或 std::list

4. 异常安全

• 强异常安全：插入时如果构造函数抛出异常，容器状态不变
• 删除不抛出：删除操作不会抛出异常（假设析构函数不抛出）

5. 与标准算法的兼容性

• 大多数算法可用：由于迭代器是前向迭代器，大多数标准算法可以使用
• 不支持需要随机访问的算法：如 std::sort、std::binary_search 等
• 排序：如果需要排序，可以将元素复制到 vector，排序后再复制回来

总结

std::hive 是 C++26 引入的重要新容器，解决了稳定指针和缓存局部性之间的长期权衡。

核心要点：

1. 问题背景：游戏引擎等场景需要频繁插入删除，同时持有外部指针，vector 指针失效，list 缓存差
2. 核心特性：稳定的指针和迭代器、O(1) 摊销插入删除、良好的缓存局部性
3. 三个核心方面：基于块的内存布局、空闲槽管理（空闲链表复用槽内存）、跳过空闲元素的迭代
4. 与其他容器对比：比 vector 指针稳定、比 list 缓存好、比 deque 中间操作快
5. 适用场景：游戏引擎实体管理、粒子系统、对象池、需要频繁插入删除且持有外部指针的场景
6. 注意事项：迭代器是前向迭代器、不保证插入顺序、不支持需要随机访问的算法

对于 C++ 开发者来说，std::hive 提供了一个新的工具，在特定场景下可以同时获得稳定性和性能。它不是要取代 vector 或 list，而是填补了它们之间的空白。对于游戏引擎、物理模拟、粒子系统等需要管理大量动态对象的场景，std::hive 可能是最佳选择。

正如文章所指出的，std::hive 的前身 plf::colony 经过了八年的委员会工作和 28 次修订才进入标准。这反映了 C++ 标准化过程的严谨性，也说明这个容器确实解决了一个重要的工程问题。

原文链接：https://www.sandordargo.com/blog/2026/09/02/cpp26-hive