c++ 稀疏集ecs c++ entt的sparse set是如何实现的-C++-PHP中文网

entt的sparse_set本质是“稀疏数组+m_dense映射”：m_sparse以entity为下标存其在m_dense中的位置，m_dense按插入顺序存储entity，保证o(1)遍历局部性；entity id必须是小整数，否则m_sparse内存爆炸；erase通过末尾填充维持m_dense紧凑，遍历安全需避免正向遍历时删除后续元素。

c++ 稀疏集ecs c++ entt的sparse set是如何实现的

ENTT 的 `sparse_set` 本质是“稀疏数组 + 密集索引映射”

它不是哈希表，也不是链表，更不是 std::set；而是一对紧密耦合的数组：m_sparse（稀疏数组）和 m_dense（密集数组）。前者用实体 ID（通常为 entt::entity）作下标，存的是该实体在 m_dense 中的位置；后者按插入顺序存实体 ID，保证遍历 O(1) 局部性。

关键点在于：实体 ID 必须是小整数（ENTT 默认从 0 开始递增），否则 m_sparse 会浪费大量内存。ENTT 不做越界检查，越大的 ID 直接导致 m_sparse 分配巨大 vector —— 这是第一个容易崩的点。

m_sparse[entity] 如果为 entt::null（即 -1），说明该实体未存储
m_dense[index] 存的是真实 entity，index 是“逻辑顺序”，不等于 entity 值
插入时：往 m_dense 尾部 push，再把 index 写进 m_sparse[entity]
删除时：把 m_dense 末尾元素移到被删位置，更新其 m_sparse 映射，再 pop_back

为什么 `erase` 后遍历不会跳过或重复？

因为 begin()/end() 遍历的是 m_dense，而 erase 总是用末尾元素填补空洞 —— 所以 m_dense 始终紧凑、无空隙。你拿到的迭代器始终指向有效 entity，且顺序就是插入/保留顺序（除非中间删过）。

但注意：如果你在遍历 m_dense 时调用 erase(entity)，且该 entity 在当前迭代器之后，那么被挪过来的末尾元素可能被重复访问（如果它没被删过）；ENTT 不禁止这种操作，但结果不可靠。安全做法是收集待删 ID 后批量删，或反向遍历。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

正向遍历时 erase 当前元素：安全，内部已处理好迭代器偏移
正向遍历时 erase 后续某个元素：可能导致那个被挪来的 entity 被再次命中
erase 返回值是下一个有效迭代器，但仅当传入的是迭代器而非 entity 时才可用

`sparse_set` 和 `basic_storage` 的区别在哪？

sparse_set 只存 entity ID，不存组件数据；basic_storage（如 storage<t></t>）才是存组件值的容器，它内部也用类似 sparse-dense 结构，但额外维护一个 m_values 数组存 T 实例，并保持与 m_dense 索引对齐。

也就是说：sparse_set 是“谁有这个组件”的轻量判定层；storage<t></t> 是“这个组件值是多少”的数据层。两者共享同一套索引逻辑，所以 view<t></t> 能 O(1) 关联 entity 和 T&。

sparse_set::size() = 当前有多少 entity 拥有该组件（即 m_dense.size()）
storage<t>::size()</t> 必然等于 sparse_set::size()，否则 ENT 行为未定义
直接 new 一个 sparse_set 没意义 —— 它被设计为 registry 内部管理，不暴露构造接口

常见误用：以为 `sparse_set` 支持任意 entity ID 或需要手动扩容

ENTT 的 entity ID 默认是 32 位整数，高位用作版本号，低位才是索引。当你调用 create()，它返回的 ID 并非单纯递增整数 —— 但 sparse_set 会自动提取低位作为 m_sparse 下标。只要你没手动构造非法 ID（比如高位版本乱填、低位溢出），就不用管。

真正要小心的是：如果长期运行中 entity 频繁创建销毁，版本号会涨，但低位重复使用，m_sparse 大小基本稳定；可一旦你用 entity{4294967295} 这种超大值去调 contains，m_sparse 会尝试 resize 到 4GB+ —— 程序当场 OOM。