9 UE5 TSparseArray介绍

TSparseArray 稀疏数组

• 他是TMap和TSet内存放元素的容器
• 动态数组，可以认为和TArray差不多
• 下标不一定是连续的
• 删除元素消耗为 O(1)
• 用TBitArray来存储每个元素索引是否使用
• 用TArray来存储元素

template<typename InElementType,typename Allocator /*= FDefaultSparseArrayAllocator */>
class TSparseArray
{
    using ElementType = InElementType;

    template <typename, typename>
    friend class TScriptSparseArray;
....
....

private:
    typedef TSparseArrayElementOrFreeListLink<
        TAlignedBytes<sizeof(ElementType), alignof(ElementType)>> 
FElementOrFreeListLink;

        // 数据的存储
    typedef TArray<FElementOrFreeListLink,typename Allocator::ElementAllocator> DataType;
    DataType Data;
      
        // // 索引标记存储
    typedef TBitArray<typename Allocator::BitArrayAllocator> AllocationBitArrayType;
    AllocationBitArrayType AllocationFlags;

    int32 FirstFreeIndex;

    int32 NumFreeIndices;

链表结构 TSparseArrayElementOrFreeListLink

• 在有元素时，这个ElementData就是元素本身，
• 没有元素时，是前一个和后一个空索引/指针。
• 当删除某个元素时，这个元素的内存不动，而是将这个元素插入空闲元素链表，通过索引将他们链起来，
• 在下次插入时，如果链表里有空闲元素，只要找空闲元素，并把这个元素从链表中删除即可。
• 如下代码

/** Allocated elements are overlapped with free element info in the element list. */
template<typename ElementType>
union TSparseArrayElementOrFreeListLink
{
    /** If the element is allocated, its value is stored here. */
    ElementType ElementData;

    struct
    {
        /** If the element isn't allocated, this is a link to the previous element in the array's free list. */
        int32 PrevFreeIndex;

        /** If the element isn't allocated, this is a link to the next element in the array's free list. */
        int32 NextFreeIndex;
    };
};

删除图解，参考知乎

image.png

代码实操

• Add 和 RemoveAt

image.png image.png