引言

这是个系列文章，会通过分析源码，从数据结构层面来分析UE4/UE5中的几种数据结构基本容器：TArray、TSparseArray、TBitArray、TSet、TMap、TMultiMap，并与传统实现方案进行比较。

本文基于的源码版本是UE5 release 5.0.0。不过源码与UE4对比过基本一致，可通用。

本文作为系列文章的第一篇，会分析TArray、TSparseArray、TBitArray的实现。

数据结构是程序员的基本功，因此本文不会赘述教科书上人尽皆知的概念，只会从UE4/UE5的数据结构基本容器的特色机制出发来分析其具体实现。

TArray

TArray就是动态数组，类似stl中的std::vector。其功能也与传统的动态数组类似，支持元素增删查改、遍历等常见操作。

TArray的结构

这是一个模板类，需要外部指定使用的内存分配器。我们也可以在ContainerFwd.h里面找到其默认分配器是TSizedHeapAllocator：

1
2
3
4
5
6
7
8
9
// ContainerAllocationPolicies.h
template <int IndexSize> class TSizedDefaultAllocator : public TSizedHeapAllocator<IndexSize> { public: typedef TSizedHeapAllocator<IndexSize> Typedef; };

// ContainerFwd.h
template<int IndexSize> class TSizedDefaultAllocator;
using FDefaultAllocator = TSizedDefaultAllocator<32>;
using FDefaultAllocator64 = TSizedDefaultAllocator<64>;

template<typename T, typename Allocator = FDefaultAllocator> class TArray;

每个TArray内部都会维护一个分配器对象，用于管理其动态分配的内存。

1
2
3
4
5
6
7
8
9
10
11
12
template<typename InElementType, typename InAllocatorType>
class TArray
{
    // ...
protected:
    // 内存分配器实例，用于管理当前TArray申请的内存
    ElementAllocatorType AllocatorInstance;
    // 当前数组长度，相当于vector的size
    SizeType             ArrayNum;
    // 当前数组容量，相当于vector的capacity
    SizeType             ArrayMax;
}

这样，当传入不同的分配器类型后，即可使用不同的分配策略，而TArray自己不用关心内存相关的逻辑。

动态分配策略

我们都还记得，vector内部扩容策略是两倍扩容，当容量不足时，会扩容至原来的两倍。而java的ArrayList扩容则是1.5倍。那么UE是怎样的策略呢？

UE的TArray的扩容策略与分配器相关，在使用默认分配器TSizedHeapAllocator的情况下，其扩容策略没有vector那么激进。先说结论：每次会扩容到比1.375倍略多的数量。实际扩容公式为：

NewArrayMax=ArrayNum×(1+38)+4NewArrayMax = ArrayNum \times (1 + \frac{3}{8}) + 4

具体代码分析：每次向数组中添加元素时，最终都会调用到AddUninitialized()函数中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
FORCEINLINE SizeType AddUninitialized(SizeType Count = 1)
{
    CheckInvariants();
    checkSlow(Count >= 0);

    const SizeType OldNum = ArrayNum;
    // 注意！！！这里是+=，在这之后ArrayNum就是需要的数量，已经比ArrayMax要大了。
    if ((ArrayNum += Count) > ArrayMax)
    {
        // 容量不足时，使用ResizeGrow函数来实际进行扩容
        ResizeGrow(OldNum);
    }
    return OldNum;
}

FORCENOINLINE void ResizeGrow(SizeType OldNum)
{
    // 计算出需要扩容到的大小
    ArrayMax = AllocatorCalculateSlackGrow(ArrayNum, ArrayMax);
    // 直接调用Malloc进行内存分配扩容操作
    AllocatorResizeAllocation(OldNum, ArrayMax);
}

具体的扩容逻辑在DefaultCalculateSlackGrow函数中。核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// NumElements是当前的ArrayNum，表示需要的大小，NumAllocatedElements是当前的ArrayMax
template <typename SizeType>
FORCEINLINE SizeType DefaultCalculateSlackGrow(SizeType NumElements, SizeType NumAllocatedElements, SIZE_T BytesPerElement, bool bAllowQuantize, uint32 Alignment = DEFAULT_ALIGNMENT)
{
    const SIZE_T FirstGrow = 4;
    const SIZE_T ConstantGrow = 16;
    
    SIZE_T Grow = FirstGrow; // this is the amount for the first alloc

    // ...
    if (NumAllocatedElements)
    {
        // 当前的ArrayMax有值，表示已经分配过内存，将容量扩展为原始容量的1.375倍加上固定大小。
        // Allocate slack for the array proportional to its size.
        Grow = SIZE_T(NumElements) + 3 * SIZE_T(NumElements) / 8 + ConstantGrow;
    }
    else if (SIZE_T(NumElements) > Grow)
    {
        // 如果未分配过内存，那么容量设为需要的数量。
        Grow = SIZE_T(NumElements);
    }

    // ...

    return RetVal;
}

实际添加元素的代码在函数Emplace中。使用了C++11的几个新特性：万能引用、变长参数模板、placement new。

1
2
3
4
5
6
7
8
9
// 参数使用了万能饮用和变长参数模板，完美支持了左值引用、右值引用、普通形参等多种情况
template <typename... ArgsType>
FORCEINLINE SizeType Emplace(ArgsType&amp;&amp;... Args)
{
    const SizeType Index = AddUninitialized(1);
    // 这里使用了placement new，直接在已经分配的空间上构造对象
    new(GetData() + Index) ElementType(Forward<ArgsType>(Args)...);
    return Index;
}

优化 Remove

传统的动态数组，Remove 元素的复杂度都是 O(n)O(n) ，因为需要将删除元素之后的部分依次往前挪。即使使用 Memmove 也无法改变其时间复杂度。

但是对于一个无序，且不关心元素顺序的数组，有一种很巧妙的方法，移除元素之后，将数组最后一个位置上的元素填充到被删除的部分，并且ArrayNum减一即可。

由于数组在需求上便不关心顺序，因此也不会影响原有逻辑。这样可以将Remove的时间复杂度由 O(n)O(n) 降低为 &O(1)& 。

在TArray的实现中，也实现了这种删除方式，使用RemoveAtSwap即可实现这种方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void RemoveAtSwapImpl(SizeType Index, SizeType Count = 1, bool bAllowShrinking = true)
{
    if (Count)
    {
        CheckInvariants();
        checkSlow((Count >= 0) &amp; (Index >= 0) &amp; (Index + Count <= ArrayNum));

        // 调用析构函数
        DestructItems(GetData() + Index, Count);

        // 将数组末尾的部分memcpy到已删除的部分。
        // Replace the elements in the hole created by the removal with elements from the end of the array, so the range of indices used by the array is contiguous.
        const SizeType NumElementsInHole = Count;
        const SizeType NumElementsAfterHole = ArrayNum - (Index + Count);
        const SizeType NumElementsToMoveIntoHole = FPlatformMath::Min(NumElementsInHole, NumElementsAfterHole);
        if (NumElementsToMoveIntoHole)
        {
            FMemory::Memcpy(
                (uint8*)AllocatorInstance.GetAllocation() + (Index)* sizeof(ElementType),
                (uint8*)AllocatorInstance.GetAllocation() + (ArrayNum - NumElementsToMoveIntoHole) * sizeof(ElementType),
                NumElementsToMoveIntoHole * sizeof(ElementType)
                );
        }
        // 数组长度直接减去Count
        ArrayNum -= Count;

        if (bAllowShrinking)
        {
            ResizeShrink();
        }
    }
}

作为栈使用

一个动态数组的结构与栈非常类似。TArray更是直接提供了Push、Pop、Top等栈专有的函数，可以直接作为栈使用。

作为二叉堆使用

传统的二叉堆也是使用数组实现的，TArray也直接实现了二叉堆的功能。其内部提供了Heapify、HeapPush、HeapPop、HeapRemoveAt等二叉堆专用函数，具体实现与传统二叉堆实现是一致的，则不再赘述。

TSparseArray

TArray是连续数组，但是如果要用来存储稀疏元素的话，会存在较大的空间和时间浪费。因此，UE5专门提供了一种稀疏数组容器，用于承载稀疏数组的功能。

另外，这里专门介绍稀疏数组，还有一个非常重要的原因，是因为TSet和TMap的功能的实现，底层数据结构也使用到了TSparseArray。

有一点需要注意的是，UE5提供的TSparseArray，并不会节约内存，其最大的目的是优化TArray插入删除的速度，以及提升遍历的效率。

TSparseArray的结构

我们先来看一下TSparseArray的内部成员变量。其内部只有这四个变量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 使用TArray来实际存储数据，数据类型是FElementOrFreeListLink
typedef TArray<FElementOrFreeListLink,typename Allocator::ElementAllocator> DataType;
DataType Data;

// 使用bit数组来记录当前已分配的数据的索引。其长度与Data数组保持一致
typedef TBitArray<typename Allocator::BitArrayAllocator> AllocationBitArrayType;
AllocationBitArrayType AllocationFlags;

// 记录稀疏数组中的空闲索引。
/** The index of an unallocated element in the array that currently contains the head of the linked list of free elements. */
int32 FirstFreeIndex;

/** The number of elements in the free list. */
int32 NumFreeIndices;

我们再来看一下关键的FElementOrFreeListLink类型的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 为了这里为了避免在申请空间时直接运行数组元素的构造函数，使用了一个包装类，只用来分配空间
/**
 * The element type stored is only indirectly related to the element type requested, to avoid instantiating TArray redundantly for
 * compatible types.
 */
typedef TSparseArrayElementOrFreeListLink<
    TAlignedBytes<sizeof(ElementType), alignof(ElementType)>
    > FElementOrFreeListLink;

// 实际分配空间所使用的对象，注意是一个union！！
/** 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;
    };
};

这个空闲链表非常关键，理解了它就理解了整个TSparseArray的工作方式。

对于稀疏数组而言，主要有三种操作。

  1. 添加元素

  2. 指定位置插入元素

  3. 删除元素

这三种操作都是需要操作空闲链表。由于都是一些基本的链表操作，笔者不再帖源码赘述，只是简单描述其策略，并结合实例来具体说明。

空闲链表操作

假设我们自定义一个类型：

1
2
3
4
struct MyData
{
    // 任意数据
}

现用一个稀疏数组来存储，并依次执行以下操作：

  1. 预分配大小：Reserve(6)

  2. 在指定位置插入元素：EmplaceAt(3, MyData1)

  3. 添加元素：Add(MyData2)

  4. 指定位置移除元素：RemoveAt(3)

预分配大小

预分配大小或许是最复杂的步骤。需要将所有新位置加入空闲链表，并正确设置每个空闲位置的PrevFreeIndex和NextFreeIndex。

在调用Reserve(6)之后，其FirstFreeIndex为0，其内存分布表示为：

0(当前头结点) 1 2 3 4 5
Prev -1 0 1 2 3 4
Next 1 2 3 4 5 -1

指定位置插入元素

指定位置插入元素相当于空闲链表的节点删除操作。当然也需要判断当前位置是否是头结点或者尾结点。

在调用EmplaceAt(3, MyData1)之后，其FirstFreeIndex依然为0，其内存分布表示为：

0 1 2 3(设置新数据) 4 5
Prev -1 0 1 2 4 -
Next 1 2 4 MyData1 5 -1

添加元素

添加元素非常简单，从空闲链表中删除头结点，并将头结点后移，在已删除的空闲节点地址上进行构造及返回。

在调用Add(MyData2)之后，其FirstFreeIndex变为1，其内存分布表示为：

0(设置新数据) 1(变为头结点) 2 3 4 5
Prev MyData2 -1 1 2 4 -
Next 2 4 MyData1 5 -1 -

指定位置删除元素

删除元素的逻辑与插入元素相反，是将元素析构之后，将对应位置重新添加至空闲链表即可。这一步也会改变空闲链表的头结点。

在调用RemoveAt(3)之后，其FirstFreeIndex变为3， 内存分布表示为：

0 1 2 3(变为头结点) 4 5
Prev MyData2 3 1 -1 2 4
Next 2 4 1 MyData1 5 -1

TBitArray

TSparseArray内部包含了一个BitArray，而BitArray在TSparseArray内部承载了非常多的功能，尤其是遍历。分析其遍历之前，我们先看一下TBitArray的结构。

TBitArray的结构

TBitArray的结构与TArray类似，同样包含了数量、容量、分配器。如下所示：

1
2
3
4
5
6
7
8
9
template<typename Allocator /*= FDefaultBitArrayAllocator*/>
class TBitArray
{
    // ...
private:
    AllocatorType AllocatorInstance;
    int32         NumBits;
    int32         MaxBits;
}

区别是添加元素、删除元素的时候，需要使用位运算来辅助计算。

以添加元素为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int32 AddUninitialized(int32 NumBitsToAdd)
{
    check(NumBitsToAdd >= 0);
    int32 AddedIndex = NumBits;
    if (NumBitsToAdd > 0)
    {
        // 计算当前word是否足够添加。是否需要新的word
        int32 OldLastWordIndex = NumBits == 0 ? -1 : (NumBits - 1) / NumBitsPerDWORD;
        int32 NewLastWordIndex = (NumBits + NumBitsToAdd - 1) / NumBitsPerDWORD;
        if (NewLastWordIndex == OldLastWordIndex)
        {
            // 当前word已经足够添加新的bits
            // We're not extending into a new word, so we don't need to reserve more memory and we don't need to clear the unused bits on the final word
            NumBits += NumBitsToAdd;
        }
        else
        {
            // 当前word空间不足，需要申请新的word空间
            Reserve(NumBits + NumBitsToAdd);
            NumBits += NumBitsToAdd;
            // 将最后一个word的未使用到的高位清零
            ClearPartialSlackBits();
        }
    }
    return AddedIndex;
}

TBitArray的遍历（TSparseArray的遍历）

普通的Array，在遍历的时候一般是从低下标向高下标进行遍历。稀疏数组会有一些特殊，因为其中会有不少空元素，这些空元素肯定是不应该遍历到的。

实现这种迭代器，有一种简单的实现，在迭代器的自增函数中，使用循环来判断当前是否有元素，没有元素的话继续自增下标，直到有元素为止才返回。然而，这种实现对于稀疏数组可以说是比较浪费的，因为稀疏数组大概率会存在较多的空元素，会有较多无效遍历。

TSparseArray利用它的位结构字段AllocationFlags，完美解决了这个问题。

我们知道，AllocationFlags是一个TBitArray。要如何高效遍历TBitArray呢？

TBitArray实现了许多不同场合下的迭代器类。这里我们直接看TSparseArray使用到的迭代器类：TConstSetBitIterator。

TConstSetBitIterator核心思想是将BitArray以DWORD(32bit)为单位划分为不同小块，记录当前遍历到的WordIndex，这样处理遍历时就可以利用位运算函数只处理当前WORD内部的遍历操作。

TConstSetBitIterator的成员变量结构

我们首先来看TConstSetBitIterator有哪些成员变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template<typename Allocator>
class TConstSetBitIterator : public FRelativeBitReference
{
    // ...

private:
    // 引用，用于引用外部传入的需要遍历的BitArray
    const TBitArray<Allocator>&amp; Array;
    
    // 当前Word内还未访问过的bit，例如当前BitIndex=100，那么Mask就是0xffff<<(100%32) = 0xffff<<4
    uint32 UnvisitedBitMask;
    // 记录当前遍历到的BitIndex
    int32 CurrentBitIndex;
    // 记录当前BitIndex除了当前WORD之外的值，用于迭代器自增最后计算CurrentBitIndex，例如当前BitIndex=100，那么BaseBitIndex=32*(floor(100/32))=96
    int32 BaseBitIndex;
}

// 以下为基类FRelativeBitReference的成员
class FRelativeBitReference
{
public:
    // 记录当前的WordIndex，例如如果当前遍历到了100，那么WordIndex就是floor(100/32) = 3
    int32  WordIndex;
    // 当前Word处理时内部的mask。例如当前的BitIndex=100，那么Mask就是1<<(100%32) = 1<<4
    uint32 Mask;
};

TConstSetBitIterator自增函数

在迭代器的自增函数中，用了若干巧妙的位运算，使得同一WORD内的bit遍历达到O(1)的复杂度。

其自增函数实现为：

1
2
3
4
5
6
7
8
9
10
11
12
/** Forwards iteration operator. */
FORCEINLINE TConstSetBitIterator&amp; operator++()
{
    // 通过与取反位运算（可以看做直接相减），将当前Mask的有效位标记为已访问。实质就是将UnvisitedBitMask最低有效位置为0
    // Mark the current bit as visited.
    UnvisitedBitMask &amp;= ~this->Mask;
    
    // Find the first set bit that hasn't been visited yet.
    FindFirstSetBit();
    
    return *this;
}

这里的核心函数在FindFirstSetBit()，通过巧妙的位运算直接在复杂度O(1)内实现了同一Word下的bit遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/** Find the first set bit starting with the current bit, inclusive. */
void FindFirstSetBit()
{
    const uint32* ArrayData      = Array.GetData();
    const int32   ArrayNum       = Array.Num();
    const int32   LastWordIndex = (ArrayNum - 1) / NumBitsPerDWORD;
    
    // 为方便描述和想象，将低位称为右侧，高位称为左侧
    
    // 表示当前Word左侧是否还有未访问的值为1的数据。如果有，那么RemainingBitMask必不为1
    // Advance to the next non-zero uint32.
    uint32 RemainingBitMask = ArrayData[this->WordIndex] &amp; UnvisitedBitMask;
    while (!RemainingBitMask)
    {
        // 如果当前Word左侧已没有数据，通过遍历来找到下一个有数据的Word
        ++this->WordIndex;
        BaseBitIndex += NumBitsPerDWORD;
        if (this->WordIndex > LastWordIndex)
        {
            // We've advanced past the end of the array.
            CurrentBitIndex = ArrayNum;
            return;
        }
        
        // 如果新的Word内没有1，那么其全部为0，继续循环查找
        RemainingBitMask = ArrayData[this->WordIndex];
        UnvisitedBitMask = ~0;
    }
    
    // RemainingBitMask &amp; (RemainingBitMask - 1)是一个常用的消除最低有效位的1的方法，可以将最低有效位的1变为0
    // 如果当前Word存在还未访问的为1的数据，将RemainingBitMask最右侧的1变为0
    // This operation has the effect of unsetting the lowest set bit of BitMask
    const uint32 NewRemainingBitMask = RemainingBitMask &amp; (RemainingBitMask - 1);
    
    // 异或即可快速提取出当前RemainingBitMask的最低有效位的1
    // This operation XORs the above mask with the original mask, which has the effect
    // of returning only the bits which differ; specifically, the lowest bit
    this->Mask = NewRemainingBitMask ^ RemainingBitMask;
    
    // FMath::CountLeadingZeros(this->Mask)计算当前有效位的左侧有多少个0。这是一个指令级别的函数，由硬件支持计算。
    // NumBitsPerDWORD - 1 - FMath::CountLeadingZeros(this->Mask)即表示当前有效位的右侧有多少个0，也即当前WORD遍历过程中内部的index
    // CurrentBitIndex = BaseBitIndex + 当前WORD内部index
    // If the Nth bit was the lowest set bit of BitMask, then this gives us N
    CurrentBitIndex = BaseBitIndex + NumBitsPerDWORD - 1 - FMath::CountLeadingZeros(this->Mask);
    
    // If we've accidentally iterated off the end of an array but still within the same Word
    // then set the index to the last index of the array
    if (CurrentBitIndex > ArrayNum)
    {
        CurrentBitIndex = ArrayNum;
    }
}

我们通过一个实例来演示一下遍历的过程。

实例分析遍历过程

假设有一个BitArray，其长度为50，其中0~9为1，10~19为0，20~29为1，30~39为，40~49为1，如下所示：

11111111 11000000 00001111 11111100 00000000 11111111 11

我们目前已经遍历到30，那么当前迭代器内各成员变量数据为：

成员变量字段 数据 备注
当前Word数据 11111111 11000000 00001111 11111100
UnvisitedBitMask 11000000 00000000 00000000 00000000 迭代器自增之后，会将其与Mask相减
Mask 01000000 00000000 00000000 00000000
CurrentBitIndex 30
BaseBitIndex 0
WordIndex 0

迭代器通过operator*()函数返回出去的值为0。

执行一次迭代器的自增之后：

成员变量字段 数据 备注
当前Word数据 11111111 11000000 00001111 11111100
UnvisitedBitMask 10000000 00000000 00000000 00000000 旧值与Mask相减所得 (实际是执行&= ~Mask)
Mask 10000000 00000000 00000000 00000000 提取出的UnvisitiedBitMask的最低有效位
CurrentBitIndex 31
BaseBitIndex 0
WordIndex 0

再执行一次自增之后，将遍历下一个Word。此时迭代器数据变为：

成员变量字段 数据 备注
当前Word数据 00000000 00000000 00000011 11111111 当前数量已不足，从高位开始补0
UnvisitedBitMask 11111111 11111111 11111111 11111111 切换Word时，UnvisitedBitMask会置为全1
Mask 00000000 00000000 00000000 00000001 提取出的UnvisitiedBitMask的最低有效位
CurrentBitIndex 32
BaseBitIndex 32 直接在原基础上加32
WordIndex 1

继续执行自增的话：

成员变量字段 数据 备注
当前Word数据 00000000 00000000 00000011 11111111
UnvisitedBitMask 11111111 11111111 11111111 11111110
Mask 00000000 00000000 00000000 00000010 提取出的UnvisitiedBitMask的最低有效位
CurrentBitIndex 33
BaseBitIndex 32
WordIndex 1

以此类推，不再赘述。

从上面的分析可以看出：

TSparseArray遍历依然是从Elements的起始下标开始，快速找到已分配元素的下标，到最大下标为止。

总结

本文通过分析源码，简单介绍了TArray、TSparseArray、TBitArray几种UE常用容器的关键技术和实现原理。其实现既融合了传统数据结构的思想，并进行了优化，又融合了C++模板元编程的若干技巧。

下一篇文章，会基于TSparseArray的机制，详细分析TSet、TMap和TMultiMap的实现。