UE4的TSparseArray

TSparseArray，翻译过来就是稀疏数组，如果写过android程序应该会对这个名字很熟悉，谷歌给android单独做了一个SparseArray容器，其实对用户来说，就是对int类型单独实现的一种特化版本HashMap原因是Java的泛型是假泛型，单独搞一个这样的容器，可以去掉key的装箱和拆箱操作，这样就可以显著提升性能。他的内部直接通过两个数组来存intkey和value，在删除之后会出现空位，所以android上这个容器就叫做了稀疏数组。UE4里也有一个这样的容器，但是内部实现却跟安卓的版本完全不同，我个人觉得UE4版本的实现，才是名副其实的SparseArray，而谷歌的版本从功能上来说叫SparseMap可能更合适。

为什么要介绍TSparseArray这个容器呢？你可能觉得这个容器你平时都没有用到，看名字又很冷门，即使不知道对写程序能有什么影响？其实并不是这样的，只要你在写UE4程序，那么这个容器你就基本上一直在用，因为他是TMap和TSet内元素的容器，你使用TSet和TMap时数据实际就存在内部的TSparseArray中，UE4的TMap和TSet比STL的容器性能好的精髓就在于这个容器，所以了解这个容器对提升游戏性能非常重要。下面具体来说说UE4版本的TSparseArray是怎样实现的，可以重点关注内部是怎样管理已经删除的元素的，这点实现的非常巧妙。

先看顶部注释，基本已经说清楚了这个容器实现，是一个动态数组，可以认为和TArray差不多，所以把他当TArray来用也完全可以，唯一区别就是索引不是必须连续的，因此不省内存，但是他带来的好处就是O(1)的删除开销，对比TArray或STL的vector，删除某个位置的元素之后，需要把后面的元素向前移，虽然TArray有RemoveAtSwap，但这个容器连Swap都不需要，同时额外存了一个TBitArray，用来标记某个元素是否已分配。

看他的内部成员变量，也确实如上面注释所说，就是一个TArray和一个TBitArray两个容器组成，同时还有两个变量FirstFreeIndex和NumFreeIndices，分别记录了第一个空位的Index在哪，一共有多少个空Index。

对于前面的TArray，FElementOrFreeListLink是TArray中元素的类型，可以看到这里和TArray本身不太一样，元素并没有使用ElementType本身，下面转到这个类型的定义。

这里中转定义了一遍，具体原因是TSparseArray本身并不关心实际元素是什么，只需要大小和对齐值就可以了，这样蓝图定义的类型，或运行时定义的类型，在C++编译期即使不知道定义，只要清楚了元素内存和对齐值就能使用这个容器，具体细节可以看FScriptSparseArray，等以后说蓝图容器实现时再填坑，暂时可以先不关心这里。

FElementOrFreeListLink可以看到内部实际是TElementOrFreeListLink类型，这是一个union，可以看到注释，在分配的时候，这个元素就是元素本身，而没有分配的时候，这个元素就变成了一个结构体，结构体是前一个和后一个空索引，这不就是一个链表结构吗？我想看到这里，你应该差不多已经清楚了这个容器内部是怎样实现的：在有元素时，这个容器就是数组，当删除某个元素时，这个元素的内存并不收紧，而是将这个元素插入空闲元素链表，通过索引将他们链起来，在下次插入时，如果链表里有空闲元素，只要找空闲元素，并把这个元素从链表中删除即可。因为这里是union的原因，下面的结构大小是8字节，所以我们可以想到，无论我们设定的元素有多小（比如int32是4字节），每个元素实际也都至少占用8字节

这里简单用一个例子来说明内部具体实现。

下面看删除操作的具体代码实现：

下面看插入操作的具体代码实现：

返回结果是Add的具体位置Index

可以看到，返回了一个这样的结构FSparseArrayAllocationInfo，这是个临时变量，只用来返回结果，有两个元素Index和Pointer，分别表示这个元素的位置和内存地址，这样外面就可以在Pointer上调用placement new来调用构造函数了（C++的placement new只调用构造函数，不会分配内存）

为什么能直接在这个结构上，而不是在内部Pointer上调用呢，是因为专门实现了这个运算符，如下图所示，返回的就是Pointer，所以实际就是在Pointer上调用的

当然也支持Insert，Sort等数组常见的操作，TArray的操作基本都有。需要注意的是Num得到的是元素的个数，而GetMaxIndex得到的是内部数组的Num，如果有空位时，这两个值是不相等的。

再说说遍历操作，因为中间有空位，所以不能简单的用索引遍历，要用迭代器。非要用索引遍历也可以，只是要判断是否为空位。下面是具体写法：

我们可以自然的想到，只想简单的存储大量变化的数据，在不担心内存，且不关心顺序的情况下，用这个容器比TArray能获得更多的性能提升（因为删除操作是O(1)的）。而且可以把这个容器当作一个特殊的TMap，每个元素可以理解为是一个不可指定具体值的int32的Key到实际Value的映射。因为他本身具有数组的高性能，又同时具有Map的特性，所以这也是TSet和TMap把他作为内部存储实现的原因。