虚幻引擎中的数组---TArray: Arrays
概述
TArray是重要的指向性容器类。它是一个对类型相同的对象(称为元素)进行序列组织和管理的类。作为一个TArray的类,本身就是一个序列,其元素有很好的顺序性和它的方法用于准确的操作这些对象和他们的顺序。
TArray
TArray是虚幻引擎中最常见的容器类。它被定义为快速,安全和有效的内存处理类。TArray类型是由两个属性来定义的:主元素类型和可选的分配器。
元素的类型是指将要被存储在数组中的对象类型。TArray被称为同类型的容器:因为所有的元素类型必须是严格的同一类型。不允许存在混合类型的元素。
分配器是经常被忽略的,在大多数的使用时会自动缺省一个分配器。它定义了对象在内存中怎么放置和数组是怎么自动适应更多元素的情况。当你觉得缺省的分配器行为不符合你的要求,你可以使用其他很多不同的分配器,或者你可以自定义分配器。这个将在下面详细说明。
TArray是一个类型,就意味着它应该跟其他的内置类型,比如int32或float类型一样来对待。它的设计不是用来继承,并且在堆上创建/销毁数组被认为是一个不寻常的做法。容器拥有元素是值类型的,此类元素在数组销毁时候被销毁。从另外一个容器中创建一个TArray变量,将会拷贝容器中所有的元素到一个新的变量中;它们的状态是不共享。
创建和填充一个数组
创建一个数组,定义如下:
TArray<int32> IntArray;
这是定义了一个空的数组来存放整数变量的队列。元素的类型可以是任何可拷贝和可析构的符合常规C++值类型,比如:int32,FString,TSharedPtr等等……因为没有指定特殊的分配器,所以这个数组使用的就是常规的堆分配器。而此时,并没有内存被分配。
TArray类型可以被几种方式来填充。其中一种是通过单个数的多次拷贝来实现填充数组。
IntArray.Init(10, 5); // IntArray == [10,10,10,10,10] // 把10来拷贝5次填充到数组中。
通过Add和Emplace两种方式,在数组的最后来添加新的对象。
TArray<FString> StrArr; StrArr.Add (TEXT("Hello")); StrArr.Emplace(TEXT("World")); // StrArr == ["Hello","World"]
随着元素的添加,数组的内存通过分配器来分配。Add和Emplace做的事情基本类似,但是有些微小的差别:
l Add将会拷贝(或移动)一个元素类型的实例到数组中。
l Emplace将根据你给的参数创建一个新的元素实例。
因此,在我们的TArray中,Add将会从给出的字符串文字中创建一个临时的FString对象,然后把临时对象的内容移动到容器中一个新的FString对象里面;然而Emplace将会直接使用字符串文字来创建一个FString对象。结果是一样的,但是Emplace避免了创建临时对象,这个对于像FString这样有实际构造的类型来说是非常不受欢迎的。Push和Add的使用是一样的。
通常来说,Emplace是比Add更好一些的,对将要被容器拷贝或移动的对象,尽量的避免不必要的临时变量创建。根据以往经验,对于无实际构造的类型使用Add,否则使用Emplace。Emplace并不是总比Add的效率高,有时候Add也许读效率更好点。
Append允许你一次添加多个元素。不管你是从另外一个TArray、一个指针类型+字节数或常规的C数组,都是可以的。
FString Arr[] = { TEXT("of"), TEXT("Tomorrow") }; StrArr.Append(Arr, ARRAY_COUNT(Arr)); // StrArr == ["Hello","World","of","Tomorrow"]
AddUnique只允许添加一个元素,并且容器中没有与此元素相同的元素。相等的判定是使用元素类型的操作符==来实现的。
StrArr.AddUnique(TEXT("!")); // StrArr == ["Hello","World","of","Tomorrow","!"] StrArr.AddUnique(TEXT("!")); // StrArr is unchanged as "!" is already an element // 已经有了!,就不改变了。
Insert,跟Add、Emplace和Append类型,它允许你在给出的序列号位置上添加单个元素或拷贝一串元素。
StrArr.Insert(TEXT("Brave"), 1); // StrArr == ["Hello","Brave","World","of","Tomorrow","!"]
SetNum方法直接设置容器中元素个数。若设置的元素个数大于当前容器中元素个数,则新的元素就会通过元素类型的缺省构造函数来创建新元素。
StrArr.SetNum(8); // StrArr == ["Hello","Brave","World","of","Tomorrow","!","",""]
SetNum在新设置的元素个数小于容器中元素个数时,也可以用来删除元素。更多关于元素删除细节稍后说明。
StrArr.SetNum(6); // StrArr == ["Hello","Brave","World","of","Tomorrow","!"]
迭代
有几种关于数组元素迭代的方法,但是仍旧推荐使用C++的范围循环(ranged-for):
FString JoinedStr; for (auto& Str : StrArr) { JoinedStr += Str; JoinedStr += TEXT(" "); } // JoinedStr == "Hello Brave World of Tomorrow ! "
常规的基于顺序的迭代当然也是可以的:
for (int32 Index = 0; Index != StrArr.Num(); ++Index) { JoinedStr += StrArr[Index]; JoinedStr += TEXT(" "); }
最后,数组自身的迭代器可以来控制迭代。这里有两种方法为CreateIterator和CreateConstIterator,分别用于元素的读写和只读操作。
for (auto It = StrArr.CreateConstIterator(); It; ++It) { JoinedStr += *It; JoinedStr += TEXT(" "); }
排序
数组可以调用排序方法来进行简单的排序。
StrArr.Sort(); // StrArr == ["!","Brave","Hello","of","Tomorrow","World"]
这里,元素的值通过元素类型的的操作符“<”来进行比较。在FString中,是不区分大小写的字符顺序比较。一个二元匹配条件也可提供不同的比较方式。例如:
StrArr.Sort([](const FString& A, const FString& B) { return A.Len() < B.Len(); }); // StrArr == ["!","of","Hello","Brave","World","Tomorrow"]
现在,所有字符串按照其长度进行排序。注意到其中有三个字符串的长度是一样的-:“Hello”,“Brave”和“World”,只是改变了在数组中之前的相对位置。这是因为排序算法是不稳定的,相等的元素(这里这些字符串是相等的,因为他们有一样的长度)排列顺序是无保障的。排序算法比如:快速排序。
堆排序,无论是否带二元的匹配条件,都可以实现堆排序。是否使用堆排序取决于你的特定数据和相对其他排序算法堆排序的有效性。跟之前排序算法相似,堆排序是不稳定排序算法。如果你使用堆排序代替之前的排序,以下是排序结果(本例下,结果是一样的):
StrArr.HeapSort([](const FString& A, const FString& B) { return A.Len() < B.Len(); }); // StrArr == ["!","of","Hello","Brave","World","Tomorrow"]
总之,稳定排序算法在排序后可以保证相等元素的相对位置。然而,如果使用快排或堆排序代替稳定排序,结果如下:
StrArr.StableSort([](const FString& A, const FString& B) { return A.Len() < B.Len(); }); // StrArr == ["!","of","Brave","Hello","World","Tomorrow"]
“Hello”,“Brave”和“World”在根据字母顺序排序,排序后仍旧得到它们相同的相对位置。稳定排序算法比如归并排序。
查询
我们可以通过Num方法来知道数组中元素个数。
int32 Count = StrArr.Num(); // Count == 6
如果你需要直接访问数组内存,或许为了互操作c-类型的API,你可以使用GetData()方法来返回数组中的元素指针。指针有效性必须以数组存在和任何其他变异操作数组之前。StrPtr指向数组的指针就是指向Num()取得的第一个索引值的元素。
FString* StrPtr = StrArr.GetData(); // StrPtr[0] == "!" // StrPtr[1] == "of" // ... // StrPtr[5] == "Tomorrow" // StrPtr[6] - undefined behavior
若容器类型是const,那么返回的指针将也是const类型的。
你可以获得容器可包含元素的空间大小:
uint32 ElementSize = StrArr.GetTypeSize(); // ElementSize == sizeof(FString)
你可以使用索引的操作符 “[]”来检索元素,只需给它一个从零开始的你想得到的元素索引:
FString Elem1 = StrArr[1]; // Elem1 == "of"
给一个无效的索引值-比0小或比大于等于Num()值的索引-将会导致运行时错误。你可以通过IsValidIndex方法来请求容器某个索引否有有效:
bool bValidM1 = StrArr.IsValidIndex(-1); bool bValid0 = StrArr.IsValidIndex(0); bool bValid5 = StrArr.IsValidIndex(5); bool bValid6 = StrArr.IsValidIndex(6); // bValidM1 == false // bValid0 == true // bValid5 == true // bValid6 == false
操作符[]返回值是一个引用值,只要你的数组不是const类型的,你就可以改变数组中的元素。
StrArr[3] = StrArr[3].ToUpper(); // StrArr == ["!","of","Brave","HELLO","World","Tomorrow"]
跟GetData方法类型,若数组是const的,操作符[]将返回一个const的引用。你可以使用Last方法来从数组最后来获得序列元素。索引的缺省值为0。Top方法与Last作用相反,只是Top不带索引参数。
FString ElemEnd = StrArr.Last(); FString ElemEnd0 = StrArr.Last(0); FString ElemEnd1 = StrArr.Last(1); FString ElemTop = StrArr.Top(); // ElemEnd == "Tomorrow" // ElemEnd0 == "Tomorrow" // ElemEnd1 == "World" // ElemTop == "Tomorrow"
还可以检查数组中是否包含特定元素:
bool bHello = StrArr.Contains(TEXT("Hello")); bool bGoodbye = StrArr.Contains(TEXT("Goodbye")); // bHello == true // bGoodbye == false
或检查数组中是否匹配特定的匹配条件:
bool bLen5 = StrArr.ContainsByPredicate([](const FString& Str){ return Str.Len() == 5; }); bool bLen6 = StrArr.ContainsByPredicate([](const FString& Str){ return Str.Len() == 6; }); // bLen5 == true // bLen6 == false
我们可以通过Find家族函数来查找元素。检查元素是否存在并返回元素索引,可以用:
int32 Index; if (StrArr.Find(TEXT("Hello"), Index)) { // Index == 3 }
这种方法获得的是从容器中查找到第一个匹配元素索引。如果容器中存在多个复制元素,我们想找到从后倒数第一个匹配元素,我们使用FindLast方法来代替之前:
int32 IndexLast; if (StrArr.FindLast(TEXT("Hello"), IndexLast)) { // IndexLast == 3, because there aren’t any duplicates }
两种方法均返回一个布尔值来表示元素是否被找到,并且若找到元素,会将元素索引写入参数变量中。
Find和FindLast也可以直接返回元素索引。只要你不显式传递参数给函数,就会返回元素索引。这种方法比之前的更简洁,使用哪种方法取决于你的特定需求或风格。
若没有找到元素,则返回一个特殊值INDEX_NONE:
int32 Index2 = StrArr.Find(TEXT("Hello")); int32 IndexLast2 = StrArr.FindLast(TEXT("Hello")); int32 IndexNone = StrArr.Find(TEXT("None")); // Index2 == 3 // IndexLast2 == 3 // IndexNone == INDEX_NONE
IndexOfByKey的使用方法类似,但是它允许元素和任意对象进行比较。在Find方法中,参数实际上在搜素开始时被转化为元素类型(本例转为FString)。而在IndexOfByKey方法中,“键值”是直接比较的,甚至键值类型都不需要转化为元素类型。
IndexOfByKey可以为任何类型的键值工作,只要你存在操作符“==(ElementType,KeyType)”;这个将会被用于比较。IndexOfByKey将返回第一个被找到的元素索引,或元素没有找到返回INDEX_NONE。
int32 Index = StrArr.IndexOfByKey(TEXT("Hello")); // Index == 3
IndexOfByPredicate方法可以用于查找到与特定匹配条件第一个匹配的元素索引,若没有找到,依旧返回特定值INDEX_NONE。
int32 Index = StrArr.IndexOfByPredicate([](const FString& Str){ return Str.Contains(TEXT("r")); }); // Index == 2
除了返回索引,我们也可以返回找到元素的指针。FindByKey与IndexOfByKey也可用于元素和任意对象比较,但是返回是元素指针。没找元素返回nullptr。 copy
auto* OfPtr = StrArr.FindByKey(TEXT("of"))); auto* ThePtr = StrArr.FindByKey(TEXT("the"))); // OfPtr == &StrArr[1] // ThePtr == nullptr
同样,FindByPredicate也可以像IndexOfByPredicate使用,但它返回值是索引号。
auto* Len5Ptr = StrArr.FindByPredicate([](const FString& Str){ return Str.Len() == 5; }); auto* Len6Ptr = StrArr.FindByPredicate([](const FString& Str){ return Str.Len() == 6; }); // Len5Ptr == &StrArr[2] // Len6Ptr == nullptr
最后,当元素中数组匹配某个特殊匹配条件时候,可使用FilterByPredicate方法:
auto Filter = StrArray.FilterByPredicate([](const FString& Str){ return !Str.IsEmpty() && Str[0] < TEXT('M'); });
删除
你可以使用Remove家族的函数来进行删除元素的操作。Remove方法将删除所有与给出的元素相等的元素:
StrArr.Remove(TEXT("hello")); // StrArr == ["!","of","Brave","World","Tomorrow"] StrArr.Remove(TEXT("goodbye")); // StrArr is unchanged, as it doesn’t contain "goodbye"
注意到“HELLo”通过请求移“hello”来删除了。等于的操作测试是通过元素的操作符“==”来进行的。谨记,对FString而已,比较不区分大小写。
最后一个元素的删除可以通过 Pop方法来实现:
StrArr.Pop(); // StrArr == ["!", "of", "Brave", "World"]
Remove删除的是与条件相符的所有实例。例如:
TArray<int32> ValArr; int32 Temp[] = { 10, 20, 30, 5, 10, 15, 20, 25, 30 }; ValArr.Append(Temp, ARRAY_COUNT(Temp)); // ValArr == [10,20,30,5,10,15,20,25,30] ValArr.Remove(20); // ValArr == [10,30,5,10,15,25,30]
你也可以使用RemoveSingle来删除数组中从前面数到最近的元素。这个是很有用的,比如:你知道数组中包含多个复制对象,你只想删除一个的时候,或你的数组只能存在一个这样的元素作为对数组的优化时,因为当它找到并删除以后,就会停止搜索。
我们也可以使用RemoveAt方法来通过元素索引来删除元素。索引必须存在,否则会报运行时错误。谨记:索引是从0开始的:
我们可以使用RemoveAll来删除与匹配条件匹配的元素。例如:删除所有3的倍数的值:
在所有的删除操作中,当元素被删除后,此被删除元素后面的元素索引会调整到低索引,不可能删除元素后数组中留下一个“洞”。
这种索引调整过程是有开销的。若你不在乎剩下的元素顺序这种开销可以使用RemoveSwap、RemoveAtSwap和RemoveAllSwap来降低开销。这些方法的工作类似与非交换区变量,它们不需要保证剩下元素的顺序,只保证它们使用的高效性。
最后,所有元素的删除使用Empty方法:
操作符
数组作为一个常规值类型,可通过标准拷贝构造函数或赋值运算操作符来实现拷贝。作为数组完全拥有其元素,在拷贝数组时进行的是深度拷贝,新数组也将完全拥有拷贝的元素。
作为Append方法的替代,数据使用操作符“+=”来实现连接。
数组的比较使用的是操作符==和操作符!=。两个数组相等,必须是相同的索引有相同的元素值---元素的顺序是很重要的。元素的比较使用的是他们自己的操作符“==”。
堆
TArray有支持二叉堆数据结构的函数。堆是任意父节点等效或排序与所有子节点之前的二叉树。当作为数组使用时,树的根节点元素是0,左右字节点序号N的索引依次为2N+1和2N+2。子节点之间没有任何特殊排序。
一个已存在的数组通过调用Heapify可以转换到堆空间上。这个是可以根据是否匹配条件来重载函数,没有匹配条件的版本将使用元素类型的操作符“<”来决定顺序:
树的视图如下:
树上节点可从左到右,从上到下根据堆数组中元素顺序读取。要说明的是,数组转换到堆后排序并不是必须的。已排序数组是一个有效堆,其结构定义是足够松散的,并允许多个有效堆有相同元素集。
新元素通过使用HeapPush方法来添加到堆上,重新排序其他节点以更新堆。
HeapPop和HeapPopDiscard方法是用来删除堆的顶节点。不同之处在于前者传入参数引用,并返回最上面一个元素的拷贝,而后者简单的删除顶部节点,不返回任何值。两种方法结果对数组来说是一样的,堆通过自适应排序来更新堆。
HeapRemoveAt方法将删除指定索引号的元素对象,然后重新排序以更新堆。
值得注意的是,HeapPush、HeapPop、 HeapPopDiscard和HeapRemoveAt均只在堆结构为有效堆时可被调用,比如:在Heapify()调用之后、其他堆操作或手动把数组转换之后。
当然,这些操作,包括Heapify(),都可以通过二元匹配条件选项来决定节点在堆中顺序。当使用匹配条件时,同一匹配条件要使用到所有的堆操作中以维持正确的树结构。若无特殊匹配条件,堆操作使用的是元素的操作符“<”来决定顺序。
最后,堆中顶端节点可通过HeapTop来取得,但并不改变数组。
预留空间
由于数组是可调整的,它使用的是变长的内存。为避免每增加一个元素就开辟一次内存,分配器总是提供比请求多的内存,以便在将来添加时重新分配内存的造成性能消耗。同理,删除元素并不释放内存。不同的是在作为预留空间时,容器中多少个元素和有多个的元素能被添加进来,在下次内存分配之前是已知的。
数组的缺省构造并不分配内存,预留空间初始化为0。你可以使用GetSlack方法来获取数组中有多少个预留空间。另外,在容器中最多能容纳的元素个数可以通过Max方法来获得。GetSlack() 等于Max() - Num()。
在重新分配内存后有多少个预留空间取决于分配器,所以它不依赖于用户数组。
大多数情况,你不用关心预留空间。但是当你意识到它时,你可以使用它的优点来对数组进行优化。例如:若你知道,数组中将添加100个新元素,你可以保证你的预留空间至少有100个,这样当你添加元素时,就不需要再申请空间。上面提到的Empty方法,接受一个可选的预留空间参数。
Reset方法工作方式与Empty类似,稍有不同的是,当请求的预留空间已经由当前分配器提供时,它并不释放内存空间。然而,当需要更大的预留空间时,它将会分配更多内存空间。
最后,Shrink方法,它会删除任何浪费的预留空间,重新分配与当前元素序列需要求同样大小的空间,实际上不删除这些对象。
Raw内存
TArray只是对一些分配内存的包装。它可被当做一个可修改分配字节数和创建元素的类型。TArray总是尽其所能的提供它所有信息,但是有时你也需要降低标准。
需要注意的是,若你犯错误,这些操作会把容器变成了无效状态或引起无定义行为。在这些方法调用之后,其他常规方法被调用之前,你要保证容器处于有效状态。
AddUninitialized和InsertUninitialized方法允许你添加未初始化的空间到数组中。他们分别类似于Add和Insert的工作方式,但是不调用元素类型的构造函数。这对于有安全或方便构造函数的类型来说是很有用的,但是不管怎样这你都得完全重写状态(例如:调用Memcpy内存拷贝),最好不要自寻烦恼。
若你想或者需要控制构造过程,你可以使用保留一些你将要构造对象的内存空间。
AddZeroed和InsertZeroed 功能类似,还将通过添加/插入内存空间清空。当你有一个类型需要插入一些有效的0状态的字节位时,这个非常有用。
与SetNum类似,有SetNumUninitialized和SetNumZeroed两个方法,不同的是,当新的数字大于当前数字时,两函数对新元素空间分别进行不初始化或按位赋零。在你使用AddUninitialized和InsertUninitialized方法时,有必要保证,新元素在他们被需要时,被正确的构造在新的空间中。
使用任何Uninitialized或 Zeroed方法都需要谨慎对待。如果一个元素类型因添加一个成员而被修改,或它不具有有效的字节位为零的状态,都能导致无效的数组元素和未定义的行为。使用这些方法对于几乎不改变的数组类型大多数是很有用的,比如:FMatrix或FVector。
杂项
BulkSerialize方法是一个序列化函数,它可以用于替代数组的操作符“<<”序列化操作,用一块原生字节的序列化来替代逐个元素的序列化。当你元素类型是常见,比如内置类型或普通数据结构类型时,它的表现还是很棒的。
CountBytes和GetAllocatedSize用来估计数组中当前多少内存处于使用中。CountBytes使用的是可直接被调用的FArchive和GetAllocatedSize两个函数。他们常用于状态报告。
Swap和SwapMemory均需要两个索引号,将交换两个索引的元素值。他们两个作用是一样的,唯一区别在于Swap会做一些索引的错误检查,若索引不在范围内就引起断言。