1. Epic GamesDeveloper
  3. TCompactSet

TCompactSet

A set with an optional KeyFuncs parameters for customizing how the elements are compared and searched.

API > API/Runtime > API/Runtime/Core

A set with an optional KeyFuncs parameters for customizing how the elements are compared and searched. E.g. You can specify a mapping from elements to keys if you want to find elements by specifying a subset of the element type. It uses a TSparseArray of the elements, and also links the elements into a hash with a number of buckets proportional to the number of elements. Addition, removal, and finding are O(1).

The ByHash() functions are somewhat dangerous but particularly useful in two scenarios: Heterogeneous lookup to avoid creating expensive keys like FString when looking up by const TCHAR*. You must ensure the hash is calculated in the same way as ElementType is hashed. If possible put both ComparableKey and ElementType hash functions next to each other in the same header to avoid bugs when the ElementType hash function is changed. Reducing contention around hash tables protected by a lock. It is often important to incur the cache misses of reading key data and doing the hashing before acquiring the lock.

Here's a visual example of the data layout for the compact set

          Data Array Hash Size Collision List Hash Table   ____ _______ ______ ____

Data Array - Payload of the set. This is a just a regular array of items without any empty spots Hash Size - 4 byte integer to reference how big the hash table is. Storing this is significantly faster than trying to recalculate it Collision List - For each entry in the Data Array there is an entry in this list that may contain a valid index to the next item to consider for hash table collisions Hash Table - Power of 2 table to lookup the first index of a given hash value

   
Name TCompactSet
Type class
Header File /Engine/Source/Runtime/Core/Public/Containers/CompactSet.h.inl
Include Path #include "Containers/CompactSet.h.inl"

Syntax

template<typename InElementType, typename KeyFuncs, typename Allocator>  
class TCompactSet : public TCompactSetBase< Allocator::template ElementAllocator< sizeof> >

Inheritance Hierarchy

Constructors

Name Remarks Include Path Unreal Specifiers

constexpr TCompactSet ()

      

consteval TCompactSet ( EConstEval
)

      

TCompactSet ( const TCompactSet& Copy
)

      

TCompactSet ( TArrayView< const ElementType > InArrayView
)

      

TCompactSet ( TArray< ElementType >&& InArray
)

      

TCompactSet ( std::initializer_list< ElementType > InitList
)

      

TCompactSet ( TCompactSet&& Other
)

      

TCompactSet ( TCompactSet< ElementType, KeyFuncs, OtherAllocator >&& Other
)

 Constructor for moving elements from a UE_TCOMPACT_SET with a different SetAllocator    

TCompactSet ( const TCompactSet< ElementType, KeyFuncs, OtherAllocator >& Other
)

 Constructor for copying elements from a UE_TCOMPACT_SET with a different SetAllocator    
     

Destructors

Name Remarks Include Path Unreal Specifiers

~TCompactSet()

      

Classes

Name Remarks
TBaseIterator The base type of whole set iterators.
TBaseKeyIterator The base type of whole set iterators.
TIterator Used to iterate over the elements of a UE_TCOMPACT_SET.
TKeyIterator Used to iterate over the elements of a UE_TCOMPACT_SET.

Typedefs

| Name | Type | Remarks | Include Path | | --- | --- | --- | --- |

Constants

| Name | Type | Remarks | Include Path | | --- | --- | --- | --- |

Functions

Public

Name Remarks Include Path Unreal Specifiers

FSetElementId Add ( ElementType&& InElement,
bool* bIsAlreadyInSetPtr
)

      

FSetElementId Add ( const ElementType& InElement,
bool* bIsAlreadyInSetPtr
)

 Adds an element to the set.    

FSetElementId AddByHash ( uint32 KeyHash,
ElementType&& InElement,
bool* bIsAlreadyInSetPtr
)

      

FSetElementId AddByHash ( uint32 KeyHash,
const ElementType& InElement,
bool* bIsAlreadyInSetPtr
)

 Adds an element to the set.    

void Append ( TArray< ElementType, ArrayAllocator >&& InElements
)

      

void Append ( TCompactSet< typename TContainerElementTypeCompatibility< ElementType >::CopyFromOtherType, OtherKey...
)

 Add all items from another set to our set (union without creating a new set) Compatible element type version.    

void Append ( const TCompactSet< typename TContainerElementTypeCompatibility< ElementType >::CopyFromOtherType, Ot...
)

 Add all items from another set to our set (union without creating a new set) Compatible element type version.    

void Append ( std::initializer_list< ElementType > InitList
)

      

void Append ( TCompactSet< ElementType, KeyFuncs, OtherAllocator >&& OtherSet
)

      

void Append ( const TCompactSet< ElementType, KeyFuncs, OtherAllocator >& OtherSet
)

 Add all items from another set to our set (union without creating a new set)    

void Append ( TArrayView< const ElementType > InElements
)

      

TArray< ElementType > Array()

      

TArrayView< const ElementType > ArrayView()

      

TRangedForConstIterator begin ()

      

TRangedForIterator begin ()

      

void CheckInvariants()

 Checks array invariants: if array size is greater than or equal to zero and less than or equal to the maximum.    

void Compact()

 Deprecated - default behavior now, keeping this here so UE_TCOMPACT_SET can be swapped with TSet without changing code    

void CompactStable()

 Deprecated - use sparse array if this behavior is required, keeping this here so UE_TCOMPACT_SET can be swapped with TSet without changing code    

bool Contains ( KeyInitType Key
) const

 Checks if the element contains an element with the given key.    

bool ContainsByHash ( uint32 KeyHash,
const ComparableKey& Key
) const

 Checks if the element contains an element with the given key.    

void CopyUnfrozen ( const FMemoryUnfreezeContent& Context,
void* Dst
) const

      

void CountBytes ( FArchive& Ar
) const

 Tracks the container's memory use through an archive.    

TConstIterator CreateConstIterator()

 Creates a const iterator for the contents of this set    

TIterator CreateIterator()

 Creates an iterator for the contents of this set    

TCompactSet Difference ( const TCompactSet& OtherSet
) const

      

void Dump ( FOutputDevice& Ar
) const

 Describes the set's contents through an output device.    

TPair< FSetElementId, bool > Emplace ( EInPlace,
ArgTypes&&... InArgs
)

 Adds an element to the set by constructing the ElementType in-place with multiple args.    

FSetElementId Emplace ( ArgType&& Arg,
bool* bIsAlreadyInSetPtr
)

 Adds an element to the set.    

TPair< FSetElementId, bool > EmplaceByHash ( EInPlace,
uint32 KeyHash,
ArgTypes&&... InArgs
)

 Adds an element to the set by constructing in-place with multiple args, using a precomputed hash.    

FSetElementId EmplaceByHash ( uint32 KeyHash,
ArgType&& Arg,
bool* bIsAlreadyInSetPtr
)

 Adds an element to the set.    

void Empty ( int32 ExpectedNumElements
)

 Removes all elements from the set, potentially leaving space allocated for an expected number of elements about to be added.    

TRangedForIterator end ()

      

TRangedForConstIterator end ()

      

ElementType * Find ( KeyInitType Key
)

 Finds an element with the given key in the set.    

const ElementType * Find ( KeyInitType Key
) const

 Finds an element with the given key in the set.    

ElementType * FindArbitraryElement ()

 Finds any element in the set and returns a pointer to it.    

const ElementType * FindArbitraryElement ()

      

ElementType * FindByHash ( uint32 KeyHash,
const ComparableKey& Key
)

 Finds an element with a pre-calculated hash and a key that can be compared to KeyType.    

const ElementType * FindByHash ( uint32 KeyHash,
const ComparableKey& Key
) const

      

FSetElementId FindId ( KeyInitType Key
) const

 Finds an element with the given key in the set.    

FSetElementId FindIdByHash ( uint32 KeyHash,
const ComparableKey& Key
) const

 Finds an element with a pre-calculated hash and a key that can be compared to KeyType    

ElementType & FindOrAdd ( const InElementType& InElement,
bool* bIsAlreadyInSetPtr
)

 Adds an element to the set if not already present and returns a reference to the added or existing element.    

ElementType & FindOrAdd ( InElementType&& InElement,
bool* bIsAlreadyInSetPtr
)

      

ElementType & FindOrAddByHash ( uint32 KeyHash,
ElementReferenceType&& InElement,
bool* bIsAlreadyInSetPtr
)

 Adds an element to the set if not already present and returns a reference to the added or existing element.    

const ElementType & Get ( FSetElementId Id
) const

 Accesses the identified element's value. Element must be valid (see @IsValidId).    

ElementType & Get ( FSetElementId Id
)

 Accesses the identified element's value. Element must be valid (see @IsValidId).    

SIZE_T GetAllocatedSize()

 Helper function to return the amount of memory allocated by this container Only returns the size of allocations made directly by the container, not the elements themselves.    

bool Includes ( const TCompactSet< ElementType, KeyFuncs, Allocator >& OtherSet
) const

 Determine whether the specified set is entirely included within this set    

TCompactSet Intersect ( const TCompactSet& OtherSet
) const

      

bool IsValidId ( FSetElementId Id
) const

 Checks whether an element id is valid.    

void RangeCheck ( FSetElementId Id
) const

 Checks if index is in array range.    

void Relax()

 Deprecated - default behavior now, keeping this here so UE_TCOMPACT_SET can be swapped with TSet without changing code    

int32 Remove ( KeyInitType Key
)

 Removes all elements from the set matching the specified key.    

void Remove ( FSetElementId ElementId
)

 Removes an element from the set.    

int32 RemoveByHash ( uint32 KeyHash,
const ComparableKey& Key
)

 Removes all elements from the set matching the specified key.    

void RemoveStable ( FSetElementId ElementId
)

 Removes an element from the set while maintaining set order.    

int32 RemoveStable ( KeyInitType Key
)

 Removes all elements from the set matching the specified key.    

void Reserve ( int32 Number
)

 Preallocates enough memory to contain Number elements    

void Reset()

 Efficiently empties out the set but preserves all allocations and capacities    

void Shrink()

 Shrinks the set's element storage to avoid slack.    

void Sort ( const PredicateType& Predicate
)

 Sorts the set's elements using the provided comparison class.    

void SortFreeList()

 Deprecated - unnecessary, keeping this here so UE_TCOMPACT_SET can be swapped with TSet without changing code    

void StableSort ( const PredicateType& Predicate
)

 Stable sorts the set's elements using the provided comparison class.    

TCompactSet Union ( const TCompactSet& OtherSet
) const

      

void WriteMemoryImage ( FMemoryImageWriter& Writer
) const

      

Static

Name Remarks Include Path Unreal Specifiers

static void AppendHash ( const FPlatformTypeLayoutParameters& LayoutParams,
FSHA1& Hasher
)

      

static size_t GetAlignment()

 Get the alignment required for the allocation    

static FCompactSetLayout GetSetLayout()

      

static size_t GetTotalMemoryRequiredInBytes ( uint32 NumElements
)

 Calculate the size of the hash table from the number of elements in the set assuming the default number of hash elements    

Operators

Name Remarks Include Path Unreal Specifiers

ElementType & operator[] ( FSetElementId Id
)

 Accesses the identified element's value. Element must be valid (see @IsValidId).    

const ElementType & operator[] ( FSetElementId Id
) const

 Accesses the identified element's value. Element must be valid (see @IsValidId).    

TCompactSet & operator= ( const TCompactSet& Copy
)

 End - intrusive TOptional state //.    
     

TCompactSet & operator= ( TCompactSet< ElementType, KeyFuncs, OtherAllocator >&& Other
)

 Assignment operator for moving elements from a UE_TCOMPACT_SET with a different SetAllocator    

TCompactSet & operator= ( const TCompactSet< ElementType, KeyFuncs, OtherAllocator >& Other
)

 Assignment operator for copying elements from a UE_TCOMPACT_SET with a different SetAllocator    

TCompactSet & operator= ( std::initializer_list< ElementType > InitList
)

      

TCompactSet & operator= ( const TCompactSet< typename TContainerElementTypeCompatibility< ElementType >::CopyFromOtherType, Ot...
)

 Assignment operator.    

TCompactSet & operator= ( TCompactSet< typename TContainerElementTypeCompatibility< ElementType >::CopyFromOtherType, OtherKey...
)

 Move assignment operator. Compatible element type version.    

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page