UE-TSparseArray
思考
如果一个数组只用关心插入和删除, 不用关心其位置. 即使中间位置的元素删除后也不用将后续元素前移. 构建一个这样的数组需要解决的问题:
- 如何找到空闲位置?
- 某个元素删除之后如何再次被使用?
我们将数组分成两部分: 已使用
部分+空闲
部分.
这样可以在每次添加元素后将它放入已使用
部分,
在每次将数据删除后将其放入空闲
部分. 将空闲部分串联起来,
每次取头部元素使用, 归还时放入空闲列表的头部.
并使用一个索引记录第一个空闲元素的索引.
UE具体实现
UE具体实现方式:
- 将Item定义为
union
类型, 当期被使用时存储原本元素. 当期空闲时存储下一个空闲元素的索引.
- 记录第一个空闲元素的索引
TSparseArray.FirstFreeIndex
.
- 除此之外,
UE还记录了空闲元素数量
TSparseArray.NumFreeIndices
用于计算当前元素数量和扩容等操作.
- 使用BitArray存储每个元素是否空闲的状态. 用于加速遍历.
遍历过程中可以\(O(1)\)定位到下一个被使用的元素.
其实不是\(O(1)\).
是通过关键函数
FMath::CountLeadingZeros
计算前导0的个数.
对于TStaticBitArray
类型,
会使用GCC内置函数__builtin_ctzll
计算前导0的数量.
具体参考函数:TStaticBitArray.FindFirstClearBit
对于TConstSetBitIterator.FindFirstSetBit
,
经过一系列计算将其变成计算前导0的方式计算对应Index.
对于TConstDualSetBitIterator.FindFirstSetBit
,
最终是以计算前导0的方式找到下一个有效位.
TSparseArray.Add
- 提取第一个空闲元素.
- 重新设置FirstFreeIndex.
- 放入已使用列表, 即设置具体的值.
TSparseArray.RemoveAt
- 将元素归还到空闲链表头部
- 重新设置FirstFreeIndex.
TSparseArray.Reserve
总结
快的原因:
- 删除元素不需要将该元素后边元素前移.
- 遍历会加速, 跳过空闲元素.