Intro to Unreal Engine containers (TArray, TSet, TMap)

This article may be helpful for those who are familiar with standard containers and would like to learn Unreal-specific ones, or for those who already have a knowledge of the containers but would like to explore them a little deeper.

Here is information about the following containers: TArray, TSet, TMap, and a basic overview of the TMultiMap and TSortedMap.

TArray

Let’s start with TArray. TArray is a dynamically sized array, similar to std::vector in the standard library.

The primary use of TArray is to provide an easy way to iterate over its elements using both traditional and range-based for loops, with good memory and performance.

TArray<int32> IntArray{5, 10, 15, 20, 25};

for (int32 Index = 0; Index < IntArray.Num(); ++Index)
{
    UE_LOG(LogTemp, Log, TEXT("Traditional for loop iteration. Element value: %d"), IntArray[Index]);
}

TArray<int32> IntArray{5, 10, 15, 20, 25};

for (int32 Element : IntArray)
{
    UE_LOG(LogTemp, Log, TEXT("Range-based for loop iteration. Element value: %d"), Element);
}

From a time complexity perspective, all TArray operations except for indexing have linear O(n) time complexity.

TSet

TSet is a dynamic collection of unique elements stored as keys, similar to the std::set container in the standard library. It uses a hash table implementation to efficiently store and retrieve the elements, where the actual key is passed through a hash function to generate a numerical representation.

Technically, TSet encapsulates a TSparseArray, allowing hashed keys to be optimally stored as indexes.

As a result, this container is designed for instant (in constant time O(1)) element search.

However, the elements in this container are likely to have an inconsistent order in memory. And accessing an element using a hash function each time makes it not the preferred option for iterating over all elements.

TSet<FString> StringSet{TEXT("First element"), TEXT("Second element"), TEXT("Third element")};

// The value will be true since there is a "Second element" element
bool bFound = StringSet.Contains(TEXT("Second element"));

TMap

TMap is a dynamically sized associative array, similar to TSet, that stores elements as key-value pairs. It is implemented in a similar manner as std::unordered_map and has a structure similar to a hash table, but the main difference is that not keys are hashed, but key-value pairs.

Technically, TMap encapsulates a TSet containing a TPair<KeyType, ValueType>.

Thus, all operations, except searching for an element by value, occur in constant time O(1).

Since this container works similarly to TSet, it is not recommended to use it when iterating over all elements for the same reasons

Diving even deeper: to find the keys inside TPair<KeyType, ValueType>, TMap uses key functions called TDefaultMapHashableKeyFuncs, which handles the matching and calling the hashing function (GetKeyHash) based on the input key. Internally, it has its own implementation of KeyInitType with replacement of the element type for search from TPair<KeyType, ValueType> to KeyType, which allows you to specify only the key instead of the full pair when searching in TMap. Essentially, you can think of TMap<KeyType, ValueType> as TSet<TPair<KeyType, ValueType>, TDefaultMapHashableKeyFuncs<KeyType, ValueType, false>>, with the final “false” indicating to disallow duplicate keys, which are not allowed in TMap by design.

TMap<FString, float> StringFloatMap
{
	{TEXT("First element"), 0.1f},
	{TEXT("Second element"), 0.2f},
	{TEXT("Third element"), 0.3f}
};

// The value found will be 0.2
float FoundValue = *StringFloatMap.Find(TEXT("Second element"));

TMap<FString, float> StringFloatMap
{
	{TEXT("First element"), 0.1f},
	{TEXT("Second element"), 0.2f},
	{TEXT("Third element"), 0.3f}
};

// The key found will be "Third element"
FString FoundKey = *StringFloatMap.FindKey(0.3f);

Similar containers to TMap

TMultiMap operates similarly to TMap, but is closer to the standard std::unordered_multimap, as it allows multiple values to be assigned for each key. To some extent, you can think of TMultiMap<KeyType, ValueType> as TSet<TPair<KeyType, ValueType>, TDefaultMapHashableKeyFuncs<KeyType, ValueType, true>>, where the “true” argument in TDefaultMapHashableKeyFuncs specifies that duplicate keys are allowed.

There is an even more TMap-like container called TSortedMap, which is more efficient than TMap when the number of elements is small. It is similar to std::map in that finding has logarithmic complexity O(log n), since the algorithm uses a binary search, although it is not implemented as a red-black tree , but simply as an array of key-value pairs (TArray<TPair<KeyType, ValueType>>), so adding and removing takes linear time O(n).