UE-TSparseArray

思考

如果一个数组只用关心插入和删除, 不用关心其位置. 即使中间位置的元素删除后也不用将后续元素前移. 构建一个这样的数组需要解决的问题:

  1. 如何找到空闲位置?
  2. 某个元素删除之后如何再次被使用?

我们将数组分成两部分: 已使用部分+空闲部分. 这样可以在每次添加元素后将它放入已使用部分, 在每次将数据删除后将其放入空闲部分. 将空闲部分串联起来, 每次取头部元素使用, 归还时放入空闲列表的头部. 并使用一个索引记录第一个空闲元素的索引.

UE具体实现

UE具体实现方式:

  1. 将Item定义为union类型, 当期被使用时存储原本元素. 当期空闲时存储下一个空闲元素的索引.

  1. 记录第一个空闲元素的索引TSparseArray.FirstFreeIndex.

  1. 除此之外, UE还记录了空闲元素数量TSparseArray.NumFreeIndices用于计算当前元素数量和扩容等操作.

  1. 使用BitArray存储每个元素是否空闲的状态. 用于加速遍历. 遍历过程中可以\(O(1)\)定位到下一个被使用的元素. 其实不是\(O(1)\). 是通过关键函数FMath::CountLeadingZeros计算前导0的个数.

​ 对于TStaticBitArray类型, 会使用GCC内置函数__builtin_ctzll计算前导0的数量. 具体参考函数:TStaticBitArray.FindFirstClearBit

​ 对于TConstSetBitIterator.FindFirstSetBit, 经过一系列计算将其变成计算前导0的方式计算对应Index.

​ 对于TConstDualSetBitIterator.FindFirstSetBit, 最终是以计算前导0的方式找到下一个有效位.

TSparseArray.Add

  1. 提取第一个空闲元素.
  2. 重新设置FirstFreeIndex.
  3. 放入已使用列表, 即设置具体的值.

TSparseArray.RemoveAt

  1. 将元素归还到空闲链表头部
  2. 重新设置FirstFreeIndex.

TSparseArray.Reserve

总结

快的原因:

  1. 删除元素不需要将该元素后边元素前移.
  2. 遍历会加速, 跳过空闲元素.