稀疏集合是一个灵活、高效的数据结构，适合在需要频繁插入、删除和查找的场景中使用，通过紧凑存储和简单的操作，它提供了优越的性能和良好的缓存利用率，但是使用它可能仍然存在一些顾虑
内存占用
稀疏数组的大小通常等于可能的实体总数，哪怕实际使用的实体数量很少
- 极端情况：假如有 20 万个实体，但只有一个实体拥有一个组件，这种情况下，稀疏数组的内存开销可能显得不划算
不过，真实场景中这种情况极为少见，稀疏集合通常用于存储大批量的组件，而不是仅为个别组件分配一个巨大的稀疏数组，在大多数现代应用中，内存已不再是主要瓶颈，但了解如何优化稀疏数组仍然有意义
为了解决稀疏数组内存问题，EnTT 实现了一种内存 分页机制
分页 Pagination
分页将稀疏数组分为多个较小的页面，每个页面仅在需要时分配，这样可以有效减少稀疏数组的内存占用，分页的代价是引入了一层间接访问，需要先定位页面再访问具体数据
- 直接访问稀疏数组：
sparse[element] - 分页访问稀疏数组：通过计算页码和页内偏移量定位数据
虽然多了一步间接访问，但实践中其性能开销几乎可以忽略
- 迭代操作：迭代过程中通常直接访问密集数组，而稀疏数组基本不参与，因此分页对性能无影响
- 插入和删除：这些操作依赖稀疏数组，因此分页会有轻微的性能开销
分页并不能完全解决所有问题，如果每页只添加一个元素，总体内存使用量仍可能接近未分页的情况，这种模式在实际应用中非常罕见，因为实体通常是批量创建或操作的
分页的效果很大程度上取决于页面大小的选择，但如果内存不是瓶颈，大可不必过于关注这一点，对于极端稀疏的场景，可以考虑其他数据结构（如哈希表）
查找
在稀疏集合中，有效查找操作需要访问两个数组（稀疏数组和密集数组），这一点可能引起一些开发者的顾虑，尽管访问两个数组的性能开销并不高，但仍有优化的空间
空实体 Null Entity
为优化查找性能，可以在 稀疏数组 中引入一个特殊的 空实体，用于标识无效位置，EnTT 使用了 entt::null 作为 空实体 的 标识符 值，并通过以下方式应用该机制
- 初始化：稀疏数组的所有元素初始化为空实体
- 删除元素：在移除元素时，将对应的稀疏数组位置设置为空实体
引入空实体后，查找逻辑变得更加简单和高效
-
原始查找逻辑（需要访问两个数组）
dense[sparse[element]] == element需要先访问稀疏数组找到位置，再访问密集数组验证元素是否存在
-
空实体查找逻辑（仅访问一个数组）
sparse[element] != entt::null只需检查稀疏数组的值是否为空实体即可，无需再访问密集数组
在设计 空实体 的 标识符值 时，需要避免浪费资源或增加额外的复杂性
- 避免浪费密集数组的第一个位置
不建议使用0作为空实体标识符值，因为这会导致位置0的实体无法使用，从而浪费密集数组的第一个元素或增加操作复杂性 - 推荐使用最后一个位置
假设支持最多1M个实体，可以使用(1M-1)作为空实体的标识符值，这样避免了浪费密集数组的任何有效位置
迭代
在密集数组的迭代过程中，添加或删除元素会导致以下问题
- 添加元素：通常意味着向密集数组末尾追加新元素，这可能导致正在进行的迭代访问无关的新增元素
- 删除元素：从密集数组中移除某个元素需要与末尾元素交换位置以保持数组紧凑，可能导致迭代器失效或访问重复的元素
反向迭代
通过从 末尾到头部 进行反向迭代，可以有效避免上述问题
- 添加元素：新增的元素被追加到密集数组末尾，而迭代从末尾向头部进行。由于新增元素在未被迭代的范围之外，它们不会影响当前迭代
- 删除当前元素：删除当前元素时，它与密集数组末尾的元素交换位置。由于末尾元素已经被访问过，这种交换不会导致重复访问
反向迭代不仅使得迭代器的行为更稳定，还完全避免了因添加或删除元素导致的迭代器失效