Introduction

TArray is a powerful and flexible container class that offers dynamic array functionality, commonly used throughout Unreal Engine sources and projects for managing collections of objects. While this series will not cover all the TArray APIs (since the official Unreal Engine documentation and Api documentation provides an exhaustive reference) we will focus on its key features, internals, memory management, and best practices for optimal usage and performance. Understanding these core concepts will help in using TArray effectively, avoiding common pitfalls, and writing more efficient, robust code in UE.

Based on this premise, the series is organized as follow:

• TArray Fundamentals. An introduction to TArray, its main features and related insights.
• TArray Versatility. Highlights how TArray can mimic different types of data structure and related pros and cons.
• TArray Memory Managament. Describes internals on how memory is handled using Allocators. [ON-GOING]
• TArray Best Practices. A summary of use cases and considerations to take the most out from TArray. [ON-GOING]

TArray Versatility

TArray dynamic nature and robust functionality extend far beyond its simple array-like appearance, allowing developers to adapt it to mimic the behavior of numerous classic data structures such as lists, sets, stacks, heaps, and maps.

In this article, we will delve into practical examples that illustrate how TArray can be used to emulate those data structure, discussing possible use cases and evaluating pros and cons.

Table of Contents:

• As List
• As Set
• As Stack
• As Heap
• As Map
• Conclusions

As List

Using TArray as a List is one of its most common use case. In this role, TArray excels at managing a contiguous collection of elements, providing a comprehensive set of APIs for inserting, removing, iterating, sorting, and querying data. It combines the advantages of both sequential and random access, making it well-suited for a variety of tasks that involve dynamic arrays.

Anywhow some operations that involve array index such as InsertAt() or RemoveAt() can be critical, depending on the application and the frequency, due to elements shifting.

APis and example related to this use case has been discussed in the first post of the series TArray Fundamentals, so refer to it for more insights.

As Set

It is possible to use TArray as a collections of elements without duplicates with a dedicated api for adding unique element AddUnique(ElementType).

This api will add the element only if it is not already exists in the container:

TArray<int32> NumbersSet;

NumbersSet.AddUnique(10);
NumbersSet.AddUnique(10);

//Numbers = [10]

Under the hood
Internally, AddUnique checks the existence of the element using Find api (so ElementType operator== is used) and in case use Add api for appending the new element.

In terms of Time Complexity this means that AddUnique is O(N), due to the brute-force scan for checking element existence. For this reason if you need to handle a huge set of elements is better using a dedicated container such as TSet.

As Stack

Using TArray as a LIFO data structure is supported by the Push(ElementType) and Pop(ElementType) apis. These two methods provide the stack semantic to respectively insert and extract (reading + removal) an element:

TArray<int32> NumbersStack;

NumbersStack.Push(10);
NumbersStack.Push(20);
NumbersStack.Push(30);

// NumbersStack = [10, 20, 30]

int32 Value = NumbersStack.Pop();
// Value = 30
// NumbersStack = [10, 20]

Under the hood
As can be seen from the example, the stack semantic is granted using the tail of the array for better performance. Infact Push use internally Add api to append the element at end of the container and Pop access the element at the last index (array size - 1), copy the element and remove it from the container.

In terms of Time Complexity both operations are O(1), even if Pop method due to the removal operation could trigger a shrink operation.

As Heap

TArray also offers heap data structure feature, in the form of a binary tree implemented as an array where:

• a parent node should be always greather than or equal to its children (Max-Heap property) or lower than or equal to its children (Min-Heap property)
• for every node at index i, its left child is at 2i + 1 and the right child is at 2i + 2

By default Heap operations assumes that operator<(ElementType) is defined of the element type declared as template argument. Anyhow overloads are availables which accept a predicate.

Add Element using HeapPush(ElementType):

TArray<int32> NumbersHeap;

NumbersHeap.HeapPush(30);
NumbersHeap.HeapPush(10);
NumbersHeap.HeapPush(40);
NumbersHeap.HeapPush(20);

// NumbersStack = [10, 20, 40, 30]

/*
            10
          /    \
        20     40
       /
     30
*/

Remove Element using HeapRemoveAt(index) or HeapPopDiscard(). The first one allow to remove any element by index, while the second is an explicit removal operation for removing the the root item. Remove operation will cause the Heap to be recomputed to keep the binary tree balanced.

NOTE:
Basically HeapPopDiscard() is equivalent to HeapRemoveAt(0)

TArray<int32> NumbersHeap = {10, 20, 40, 30};

NumbersHeap.HeapRemoveAt(1);

// NumbersStack = [10, 30, 40]

/*
            10
          /    \
        30     40
*/

NumbersHeap.HeapPopDiscard();

// NumbersStack = [30, 40]

/*
            30
          /
        40
*/

Retrive the root element using HeapTop() or HeapPop(output). The first is just a read operation, while the second other than returning the root element as a copy, removes it causing the Heap to be recomputed to keep the binary tree balanced:

TArray<int32> NumbersHeap = {10, 20, 40, 30};
int32 Value;

NumbersHeap.HeapTop(Value);
// Value = 10
// NumbersStack = [10, 20, 30, 40]

NumbersHeap.HeapPop(Value);
// Value = 10
// NumbersStack = [20, 30, 40]

/*
            20
          /    \
        30     40
*/

Convert TArray to Heap using Heapify(). With this method you can transform an existing TArray to an heap data structure.

TArray<int32> NumbersHeap = {20, 10, 40, 30};

NumbersHeap.Heapify();
// NumbersStack = [10, 20, 40, 30]

/*
            10
          /    \
        20     40
       /
     30
*/

Final notes:

• All heap operations (except for Heapify) must be called on a valid heap data structure obtained manually handling the array or as an outcome of the Heapfy method.
• All heap operations accepts a predicate (as method overloads) to provide custom ordering between pair of elements such as (const ElementType& First, const ElementType& Second) -> bool.

Refer to the Appendix in TArray Fundamentals on how implement predicates which satisfy TArray apis.

As Map

Benefecting from the index-based access, it is possible to use TArray as a basic map implementation, where the key is represented by the element index, while the element itself is the value.

TArray<int32> NumbersMap;

int32 Key10 = NumbersMap.Add(10);
int32 Key20 = NumbersMap.Add(20);

// Key10 = 0
// Key20 = 1
// NumbersStack = [10, 20]

int32 Value10 = NumbersMap[Key10];
// Value10 = 10

Obviously this can work under the condition to avoid any operation on the container that have an impact on the indexing of the elements already present. Then:

• Add, Emplace, Append methods are "index-friendly" because elements will be added at new indexes at the end of the array
• Insert, EmplaceAt are not, as far all the Removal Operation that can cause element shifting and Sorting Operation that cause element swapping.

So, possible usage scenario could be:

• It is fine to have integer keys
• Needs of O(1) time complexity for index-friendly insertion operation and element access
• Needs of often iterating/querying all the elements
• No needs to do Removal operation (or eventually not often, with the drawback to update the collection of keys)
• No needs to do Sorting operation

For any other scenario a real map container such as TMap or TMultiMap should be preferred.

Conclusions

Throughout this article, we have explored the versatility of Unreal Engine TArray, demonstrating how it can be adapted to replicate the behavior of various data structures, including lists, sets, stacks, heaps, and maps. However, when using TArray to mimic a specific data structure, it is important to closely follow the conventions of that structure and avoid utilizing unrelated APIs. For instance, if you are emulating a stack, it is best to limit operations to pushing and popping elements, steering clear of arbitrary insertions or deletions that could compromise the stack intended behavior. By restricting the use of TArray additional features, you can prevent unintended side effects and ensure the integrity of the emulated data structure.

Moreover, while TArray offers considerable flexibility, it is crucial to choose the appropriate container for the specific use case. Depending on the requirements, opting for the actual data structure such as TSet for maintaining unique elements or TMap for efficient key-value pair management can provide performance advantages, built-in optimizations, and clearer code intent that TArray might not achieve as effectively. Understanding when to leverage TArray versatility versus when to select a specialized container is key to writing efficient, maintainable, and robust code in Unreal Engine.