in Unreal Engine |

Unreal Engine TArray Primer: Fundamentals

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 Fundamentals

TArray is a template class that represents a dynamically-sized array, similar to std::vector in standard C++. So it can automatically grow or shrink to accomodate the number of elements.

It allows to store collections of any type of data, whether primitive types (such as integers or floats), custom types or more complex UE classes (such as actors and components), with the costraint that all of its elements are strictly the same type.

TArray is an homogenous container, so it cannot store elements of different types.

The elements are managed as value types, and the TArray owns them. This means that when a TArray is destroyed, the elements will be destroiyed as well.

Remember: even pointers are value types, so the memory allocated to manage them within the container is destroyed, but obviously not the objects they pointed to.

Table of Contents:

Declaration

To use TArray you need to include Containers/Array.h header file from the Core module and have access to the class template TArray<typename ElementType, typename Allocator> where:

  • ElementType represent the type of the data we want to store in the container
  • Allocator represent the type of special classes responsible for the container memory management.

By now we will just play with ElementType argument and let TArray using a default implementation for the Allocator argument. An in depth discussion on this second template argument is demanded to the Memory Management topic of this series.

#include <Containers/Array.h>

TArray<int32>   IntArray;     // Array of ints (ElementType = int32)
TArray<FString> StringArray;  // Array of strings (ElementType = FString)
TArray<AActor*> ActorArray;   // Array of actor pointers (ElementType = AActor*)

Once a TArray is defined specifying the ElementType it can contains only element of that type.

Initialization

TArray can be constructed or initialized in different ways such as: Raw Array, Initialization List, an other TArray:

//initialization list
TArray<int32> Numbers1{1, 2};
TArray<int32> Numbers2 = {1, 2};
//Numbers1 = [1, 2]
//Numbers2 = [1, 2]

//Raw Array
int32 RawArray[] = {3, 4};
TArray<int32> Numbers3{RawArray, UE_ARRAY_COUNT(RawArray)};
//Numbers3 = [3, 4]

//Other TArray
TArray<int32> Numbers4{Numbers1};
TArray<int32> Numbers5 = Numbers1;
//Numbers4 = [1, 2]
//Numbers5 = [1, 2]

UE_ARRAY_COUNT is an Unreal Engine macro that help to retrive the number of elements in a raw array.

or using the Init(element, count) method which fill the array with a number of copies of the same element:

TArray<int32> Numbers;
Numbers.Init(1, 4);
//Numbers = [1, 1, 1, 1]

Destruction

When a TArray is destroyed performs those operations:

  • If element type is not trivially destructible, then the destructor for each element is invoked (this means that if element type is a pointer, destructor is not called)
  • Releasing all the memory allocated for the container.
class TrivialClass { };

class NoTrivialClass
{
    public:
        ~NoTrivialClass { }
};

{
    TArray<int32> Numbers = ...;               //only memory release
    TArray<TrivialClass> Trivials = ...;       //only memory release
    TArray<NoTrivialClass> NoTrivials = ...;   //destructor call + memory release
    TArray<int32*> Pointers = ...;             //only memory release
} //Suppose TArray are destroyed when exiting this scope

Insertion

Add an element

An element can be added a the end of the array using Add(element) or Emplace(args) method.

struct FMyClass
{
    FMyClass() { ... }
    FMyClass(int32 InValue) { ... }
};

TArray<FMyClass> MyArray;

MyArray.Add(1);               //ST01
MyArray.Add(FMyClass{2});     //ST02

MyArray.Emplace(3);           //ST03
MyArray.Emplace(FMyClass{4}); //ST04

//MyArray = [1, 2, 3, 4]

Both methods produce the same effect, the element will be appended at the end of the array, but with the following nuances:

  • Add will copy/move an instance of the element type into the array.
  • Emplace will use the arguments provided to construct a new instance of the element type in place.

This means that in case of ST01 a temporary is created and then moved to creating the new element, while for ST03 the value is passed directly to the constructor of the new element.

Instead ST02 and ST04 will have some behavior of moving instance (in this scenario, where a temporary is involved. Otherwise it could be a copy) to create the new element.

Under the hood:
Internally Add method forwards the element instance to Emplacemethod

Time complexity for adding an element with Add or Emplace is O(1), because of adding the element directly to the tail of the array.

Add multiple elements

Add multiple elements at once at the end of the array is possible using Append(elements).

This method allows to add elements from different sources such as: Raw Array, Initializer List, Ranged Types, TArray

int32 RawArray[] = {3, 4};
TArray<int32> OtherTArray = {5, 6};

TArray<int32> Numbers;
Numbers.Append({1, 2})
Numbers.Append(RawArray, UE_ARRAY_COUNT(RawArray));
Numbers.Append(OtherTArray);

//Numbers = [1, 2, 3, 4, 5, 6]

Under the hood

  • Append operation is optimized to allocate eventually enough memory for holding all the new elements.
  • Then, the new elements could be memory copyied at once (if specific condictions are meet. For instance when the element type is trivially copy constructible), or
  • the Copy Constructor with placement new is invoked for each new element.

Alternatively is possible to use operator+= with Initializer List or TArray:

TArray<int32> OtherTArray = {5, 6};

TArray<int32> Numbers;
Numbers += { 1, 2 };
Numbers += OtherTArray;

//Numbers = [1, 2, 5, 6]

Under the hood
TArray operator+= internally uses Append.

Considering Append optimization, time complexity depends on the elemens type and then if the new elements will be memory copied or not. In the first case complexity will be O(1), otherwise it will be O(N).

Insert an element

It is also possible insert elements at specific position of the array using Insert(element, index) or EmplaceAt(index, args):

TArray<int32> Numbers = { 10, 20 };

Numbers.Insert(30, 1);
Numbers.EmplaceAt(1, 40);

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

When an element is inserted at index, all the elements in the array are pushed down by 1, starting from that index.

In case of index is out of array range, will cause a runtime error.

A part the insertion aspect, Insert and EmplaceAt (in terms of element construction) behaves rispectively like Add and Emplace,

In terms of time complexity instead, those methods behave like Append. So it could be O(1) or O(N).

Insert multiple elements

Insert method has also an overload Insert(elements, index) that make possible to add multiple elements starting from a specific index from different sources such as: Raw Array, Initializer List, TArray:

TArray<int32> Numbers = { 10, 20 };

Numbers.Insert({ 30, 40 }, 1);

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

In terms of time complexity inserting multiple elements have the same behaviour described for inserting a single element. So it could be O(1) or O(N) depending on the element type.

Note that when adding new elements to the TArray, using any API described above, internally the container evaluates the need of expanding the memory allocated to hold the elements. In case it does, a bigger memory block is allocated and all the elements are moved from the old memory block, which is than freed.

Removal

Remove by instance

Removing elements providing an instance of the element using Remove(element) or RemoveSingle(element) methods. Those methods rely on element type operator==.
Remove removes all elements considered equal to the one provided, while RemoveSingle removes just the first occurrence starting from the beginning of the array.

TArray<int32> Numbers = {1, 2, 3, 3, 4, 4, 4};

int32 RemoveCount;

RemoveCount = Numbers.Remove(3);
//RemoveCount = 2
//Numbers = [1, 2, 4, 4, 4]

RemoveCount = Numbers.RemoveSingle(4);
//RemoveCount = 1
//Numbers = [1, 2, 4, 4]

Remove by index

Removing elements based on the position occuped in the array is possible using RemoveAt(index) or RemoveAt(index, count). The first remove just one element, while the second remove "count" elements starting from the index.

TArray<int32> Numbers = {10, 20, 30, 40, 50, 60};

Numbers.RemoveAt(3);
//Numbers = [10, 20, 30, 50, 60]

Numbers.RemoveAt(1, 3);
//Numbers = [10, 60]

Note that try to removing an element at invalid index will cause an "Array index of out of bounds" runtime error.

Remove by Predicate

Instead of iterating yourself the array and then evaluate if remove a specified elements, it is possible to use RemoveAll(predicate) that accepts a predicate.

TArray<int32> Numbers = {10, 20, 30, 40, 50, 60};

Numbers.RemoveAll([] (int32 InValue) { return InValue > 30; });
//Numbers = [10, 20, 30]

In this example, a Lambda has been used as Predicate. A predicate can also be implemented in different ways. Look at Appendix for more information.

To be noted that by default all remove operations will cause the TArray to shift properly the array elements to avoid gaps in between them preserving the order in which they were inserted. This makes remove operation O(N) in terms of time complexity. On top of that an array shrink operation could be performed (reducing memory size and reallocating the whole array).

Depending on the use case would be possible to improve remove operation performance using different apis. More on that will be discussed in the Best Practice topic of this series.

Iteration

Mainly there are three ways to iterate over a TArray: Index-based, Ranged-for and Iterator.

Index-based, classically iterating the array by index:

TArray<int32> Numbers = {10, 20, 30};
int32 Sum = 0;

for(int32 Index = 0; Index < Numbers.Num(); ++Index)
{
    int32 Each = Numbers[Index];
    Sum += Each;
}
//Sum = 60

Ranged-for, basically a compact iterator:

TArray<int32> Numbers = {10, 20, 30};
int32 Sum = 0;

for(auto Each : Numbers)
{
    Sum += Each;
}
//Sum = 60

Under the hood
As you may expect, Ranged-for is enabled on TArray class providing implementation for specific member functions - required by C++ standards - such as begin() and end().
Fun Fact: this is one of the few cases, where UE breaks its own coding convention standards where methods and functions should start with a capital letter 🙂

Iterator, that give explicit control over the accessibility of the elements. Using CreateIterator() it is possible to have read/write access, while using CreateConstInterator() provides read-only access to the elements, making clear the intent of the iteration:

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

for(auto It : Numbers.CreateIterator(); It; ++It)
{
    int32 Each = *It;  //read ok
    *It = Each + 1;    //write ok
}

//Numbers = [11, 21, 31]
TArray<int32> Numbers = {10, 20, 30};

for(auto It : Numbers.CreateConstIterator(); It; ++It)
{
    int32 Each = *It;  //read ok
    *It = Each + 1;    //write produces compilation error "expression must be a modifiable lvalue"
}

Sorting

Sort operation relies on a predicate that allow to compare pair of elements in terms of who has precedence over the other.

By default TArray use the element type operator<, but is also possible to pass a predicate as argument to the sorting method for more flexibility.

TArray offers 3 different algorithms (and related methods) to sort the elements:

  • Sort() and Sort(predicate): based on Quick Sort algorithm with unstable capability.
  • StableSort() and StableSort(predicate): based on Merge Sort algorithm with stable capability.
  • HeapSort() and HeapSort(predicate): based on Heap Sort algorithm with unstable capability.

Stable vs Unstable
Sorting algorithm are classified either "stable" or "unstable" based on how they handle equal elements (in terms of predicate used) during the sorting process
Stable algorithm preserves the relative order of the elements considered equal, while Unstable algorithm does not provide this guarantee so the relative order (of equal elements) may be changed after each sorting execution.

Example ofSort():

TArray<FString> Strings = { TEXT("Hello1"), TEXT("Hello2"), TEXT("A") };
Strings.Sort();

//Strings = ["A", "Hello1", "Hello2"]

Example of Sort(predicate) showing unstability property:

TArray<FString> Strings = { TEXT("Hello1"), TEXT("Hello2"), TEXT("A") };
Strings.Sort([] (const FString& Lhs, const Fstring& Rhs) {
    return Lhs.Len() < Rhs.Len();
});
//Strings = ["A", "Hello2", "Hello1"]

To be noted that "Hello1" and "Hello2" have same length, so considered equal by the sorting algorithm due to the predicate, and they may loose their relative order respect to the original array.

Example of StableSort(predicate) showing stability property:

TArray<FString> Strings = { TEXT("Hello1"), TEXT("Hello2"), TEXT("A") };
Strings.Sort([] (const FString& Lhs, const Fstring& Rhs) {
    return Lhs.Len() < Rhs.Len();
});
//Strings = ["A", "Hello1", "Hello2"]

To be noted that "Hello1" and "Hello2" have same length, so considered equal by the sorting algorithm due to the predicate, and they preserve their relative order respect to the original array.

In these example, a Lambda has been used as Predicate. A predicate can also be implemented in different ways. Look at Appendix for more information.

Querying

Array State

Check if array contains no elements with IsEmpty():

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

bool bIsEmpty = Numbers.IsEmpty();
// bIsEmpty = false

Retrieve the number of elements in the array with Num():

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

int32 Count = Numbers.Num();
// Count = 3

Check if an index is valid for the array with IsValidIndex(index):

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

bool bIsValid = Numbers.IsValidIndex(1);
// bIsValid = true

Direct Array access

Access elements by index with operator[]:

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

int32 Value = Numbers[1];
// Value = 20

Remember that operator[] returns a reference to the element.

Is is also possible to access raw array memory with GetData():

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

int32* RawData = Numbers.GetData();
// pointer to the beginning of the array memory

Usually useful when integrating with C like apis.

Searching Elements

Check if an element exists with bool Contains(CompareType) or bool ContainsByPredicate(predicate). The first one use the element type operator==(CompareType) or operator==(ElementType, CompareType) while the second a predicate.

TArray<int32> Numbers = { 10, 20, 30 };
bool bExists;

bExist = Numbers.Contains(20);
// bExists = true

bExist = Numbers.ContainsByPredicate([] (const int32& Value) {
    return Value < 10;
});
// bExists = false

In this example, a Lambda has been used as Predicate. A predicate can also be implemented in different ways. Look at Appendix for more information.

Contains is a templated method that provides the possibility of passing a different type from the ElementType of the TArray. Anyway, Contains is usually used with instance of the element type (so that CompareType is the ElementType), while doing more flexible check using ContainsByPredicate.

Finding element index using:

  • Find(element): given an element, find the related index (using element type operator==) starting from the beginning of the array. An overload exists that returns a bool and use output parameter for the index result.
  • FindLast(element): given an element, find the related index (using element type operator==) starting from the end of the array. An overload exists that returns a bool and use output parameter for the index result.
  • FindLastByPredicate(predicate): given a predicate, find the first element index that satisfy the predicate starting from the end of the array. An overload exists that allow to restric the search to a subrange of the array.
  • IndexOfByKey(key): allow to specify a KeyType where element type operator==(KeyType) or global operator==(ElementType, KeyType) should be defined, finding the first element index that correspond to the key starting from the beginning of the array (passing an element instance as key, this method behaves like Find).
  • IndexOfByPredicate(predicate): given a predicate, find the first element index that satisfy the predicate starting from the beginning of the array.

In case the search ends without result, an INDEX_NONE (which is a placeholder for the value -1) is returned as Index.

TArray<int32> Numbers = { 10, 20, 30, 20 };
bool bFound;
int32 Index;

Index  = Numbers.Find(20);                       // Index = 1
bFound = Numbers.Find(20, Index);                // bFound = true, Index = 1

Index  = Numbers.FindLast(20);                   // Index = 3
bFound = Numbers.FindLast(20, Index);            // bFound = true, Index = 3

auto Pred = [](const int32& Value){ return Value > 19; };
Index  = Numbers.FindLastByPredicate(Pred);      // Index = 3
Index  = Numbers.FindLastByPredicate(Pred, 3);   // Index = 1

Index  = Numbers.IndexOfByKey(20);               // Index = 1
Index  = Numbers.IndexOfByPredicate(Pred);       // Index = 1

In this example, a Lambda has been used as Predicate. A predicate can also be implemented in different ways. Look at Appendix for more information.

Retrieve element instances using:

  • FindByKey(key): allow to specify a KeyType where element type operator==(KeyType) or global operator==(ElementType, KeyType) should be defined, finding the first element that correspond to the key starting from the beginning of the array
  • FindByPredicate(predicate): given a predicate, find the first element that satisfy the predicate starting from the beginning of the array
  • FilterByPredicate(predicate): given a predicate, find all the elements that satisfy the predicate
TArray<int32> Numbers = { 10, 20, 30, 20 };
int32 Value;
TArray<int32> Values;

Value  = Numbers.FindByKey(20);                  // Value = 20

auto Pred = [](const int32& Value){ return Value > 19; };
Value  = Numbers.FindByPredicate(Pred);          // Value = 20

Values = Numbers.FilterByPredicate(Pred);        // Values = [20, 20]

In case the search ends without result, a nullptr is returned.

Appendix

Predicate Type

Some TArray apis (ContainsByPredicate, FindByPredicate, Sort, and others) accept a Predicate argument. A predicate is a template class that allow the following types:

  • Functor, type who define operator()
  • Lambda, basically a special case of Functor Object that is nameless
  • Non-Member Function

Here an example taking ContainsByPredicate as reference:

struct MyFunctorPredicate {
    int32 Value;
    bool operator()(const int32& InValue) const
    {
        return Value == InValue;
    }
};

bool NonMemberFuncPred(const int32& InValue)
{
    return InValue == 30;
}

TArray<int32> Numbers = { 10, 20, 30 };
bool Found;

//Functor
auto FunctorPred = MyFunctorPredicate{30};
Found  = Numbers.ContainsByPredicate(FunctorPred);          // Found = true

//Lambda
auto LamdaPred = [](const int32& InValue) { return InValue == 30; };
Found  = Numbers.ContainsByPredicate(LambaPred);            // Found = true

//Non-Member Function
Found  = Numbers.ContainsByPredicate(&NonMemberFuncPred);   // Found = true

NOTE: While it is not possible to use direcly a Member Function as a predicate, in case you need to, you could wrap it in a Lambda capturing properly the object reference who owns the function.

Conclusions

In this first article of the TArray Primer series, we explored the fundamental APIs of the TArray class for managing dynamic arrays in Unreal Engine. Insights also have been provided into its internals and performance by evaluating the time complexity of key operations. In the next article, we will dive deeper into how TArray handles container memory, taking a closer look at its allocation strategies and optimizations.

Published

Updated

Write a Comment

Comment