[UE] 언리얼 C++의 TArray, TSet, TMap 자료구조 라이브러리와 활용방법

언리얼에서 제공하는 대표 컨테이너 라이브러리의 동작 원리와 활용 방법을 예제를 통해 살펴보자.

• 언리얼 대표 컨테이너 라이브러리 TArray, TSet 의 내부 구조 이해
• 각 컨테이너 라이브러리의 장단점을 파악하고, 알맞게 활용하는 방법의 학습

 

 

인프런 이득우님의 '언리얼 프로그래밍 Part1 - 언리얼 C++의 이해' 강의를 참고하였습니다. 
😎 [이득우의 언리얼 프로그래밍 Part1 - 언리얼 C++의 이해] 강의 들으러 가기!

 

 

 

목차

 

 

---

 

 

언리얼 컨테이너 라이브러리

---

 

 

언리얼 컨테이너 라이브러리

 

언리얼 컨테이너 라이브러리 (Unreal Container Library, UCL)

• 언리얼 엔진이 자체 제작해 제공하는 자료구조 라이브러리.
• 줄여서 UCL(Unreal Container Library)라고도 함..
• 언리얼 오브젝트를 안정적으로 지원하며 다수 오브젝트 처리에 유용하게 사용됨
• 언리얼 C++은 다양한 자료구조 라이브러리를 직접 만들어 제공하고 있음.
• 접두사 T 는 Template Library 를 의미한다.
• 실제 게임 제작에 유용하게 사용되는 라이브러로 TArray, TMap, TSet 이 세 가지를 추천함.

---

 

 

C++ STL과 UCL의 차이점

 

• C++ STL은 범용적으로 설계되어 있다.
• C++ STL은 표준이기 때문에 호환성이 높다.
• C++ STL에는 많은 기능이 엮여 있어 컴파일 시간이 오래 걸린다.
• 언리얼 컨테이너 라이브러리(UCL)는 언리얼 엔진에 특화되어 있음.
• 언리얼 컨테이너 라이브러리(UCL)는 언리얼 오브젝트 구조를 안정적으로 지원한다.
• 언리얼 컨테이너 라이브러리(UCL)는 가볍고 게임 제작에 최적화된 구조로 설계되어 있다.
• ⇒ 그래서 언리얼 엔진에는 UCL을 사용을 권장한다!

---

 

 

언리얼 C++ 주요 컨테이너 라이브러

 

두 라이브러리의 이름과 용도는 유사하지만 내부적으로 다르게 구현되어 있음. 특히 set과 map은 내부적으로 다르다. 

• TArray : 오브젝트를 순서대로 담아 효율적으로 관리하는 용도
• TSet : 중복되지 않는 요소로 구성된 집합을 만드는 용도
• TMap : Key, Value 쌍의 레코드를 관리하는 용도

---

 

 

 

 

TArray 의 구조와 활용

---

 

 

TArray 개요

 

• 가변 배열(Dynamic Array) 자료구조
• STL 의 vector와 동작 원리가 유사함.
• 게임 제작에서는 가변 배열 자료구조를 효과적으로 활용하는 것이 좋음.
  • 데이터가 순차적으로 모여있으므로 메모리를 효과적으로 사용할 수 있고 캐시 효율이 높다.
  • 컴퓨터 사양이 좋아지면서, 캐시 지역성(Locality)으로 인한 성능 향상은 굉장히 중요해졌다.
  • 임의 데이터의 접근이 빠르고, 고속으로 요소를 순회하는 것이 가능하다.
• 가변 배열의 단점
  • 맨 끝에 데이터를 추가하는 것은 가볍지만, 중간에 요소를 추가하거나 삭제하는 작업은 비용이 크다.
  • Index operator [ ] 는 특정한 인덱스가 주어졌을때, 해당 인덱스를 빠르게 가져오는 작업은 균일한 데이터로 배열이 되어 있기 때문에 바로 주소를 알 수 있어서 한 번에 가져올 수 있다.
  • Add(), Emplace(), Append() 는 바로 추가해주면되기 때문에 빠르다.
  • Insert()는 중간에 추가하기 때문에 전체적인 메모리를 변경해주어야 되기 때문에 느리고 비용이 많이 발생한다.
  • Remove()의 함수도 마찬가지로 느리다.
• 데이터가 많아질 수록 검색, 삭제, 수정 작업이 느려지기 때문에, 많은 수의 데이터에서 검색 작업이 빈번하게 일어난다면 TArray 대신 TSet 을 사용하는 것이 좋음.

 

 

 

• TArray는 두 가지 property로 정의됨: Element type(= 타입 유형), Optional allocator(= 메모리를 어떻게 관리하는지에 대해 지정. 이 옵션은 일반적으로 사용하지 않음). 
• TArray 는 값 유형으로, int32 나 float 같은 다른 내장형과 비슷하게 취급해야 한다. 확장을 염두에 두지는 않았기에, TArray 인스턴스를 new 및 delete 로 생성 또는 소멸시키는 것은 좋지 않다. 엘리먼트는 값 유형이기도 하며 배열이 소유합니다. TArray 소멸은 곧 거기 들어있는 엘리먼트의 소멸로 이어진다. 다른 TArray 변수에서 TArray 변수를 만들면 그 엘리먼트를 새 변수에 복사하며(= 항상 복제해서 새로 만듬) , 공유되는 상태는 없다.
• 동적 할당이 지원되지 않는다.

 

 

https://dev.epicgames.com/documentation/ko-kr/unreal-engine/array-containers-in-unreal-engine?application_version=5.3

Array Containers in Unreal Engine

---

 

 

TArray 배열 만들고 채우기

 

TArray<int32> IntArray;

IntArray.Init(10, 5); // 10, 10, 10, 10, 10 이렇게 들어감.

 

 

TArray<FString> StrArr;

StrArr.Add(TEXT("Hello"));
StrArr.Emplace(TEXT("World"));
// StrArr == ["Hello", "World"]

• Add(또는 Push)는 Element type의 인스턴스를 배열에 복사 (또는 이동)한다.
• Emplace는 지정한 인수를 사용하여 Element type의 인스턴스를 새로 생성한다.
  • Emplace가 조금 더 효율적이다. 호출되는 곳에 임시 생성 후 컨테이너에 복사 내지 이동하는 불필요한 절차를 피할 수 있기 때문이다.

 

FString Arr[] = { TEXT("of"), TEXT("Tomorrow") };
StrArr.Append(Arr, ARRAY_COUNT(Arr));
// StrArr == ["Hello","World","of","Tomorrow"]

• Append는 다수의 Element를 한꺼번에 추가한다.

 

StrArr.AddUnique(TEXT("!"));
// StrArr == ["Hello","World","of","Tomorrow","!"]

StrArr.AddUnique(TEXT("!"));
// StrArr is unchanged as "!" is already an element

• AddUnique는 기존 컨테이너에 동일한 Element가 이미 존재하지 않는 경우 새 Element만 추가한다.
• 존재 여부는 Element type의 operator== 를 사용하여 검사한다.
• AddUnique를 계속해서 사용해야되는 상황이면 자료형을 TSet으로 대체가 가능한지 생각해봐야 한다.

---

 

 

쿼리

 

배열의 개수 

int32 Count = StrArr.Num();
// Count == 6

 

 

배열 내 Element에 대한 포인터를 반환

FString* StrPtr = StrArr.GetData();

// FString* StrPtr에 TArray의 첫번째 인자의 포인터를 얻어오면 Index operator []를 통해서 개별요소에 접근할 수 있다.
// StrPtr[0] == "!"
// StrPtr[1] == "of"
// ...
// StrPtr[5] == "Tomorrow"
// StrPtr[6] - undefined behavior

 

 

컨테이너가 const인 경우, 반환되는 포인터 역시 const다.

 

operator[]는 레퍼런스를 반환하므로, 배열이 const가 아니라는 가정하에 배열 내 Element를 변형시킬 수 있다.

StrArr[3] = StrArr[3].ToUpper();
// StrArr == ["!","of","Brave","HELLO","World","Tomorrow"]

 

 

특정 Element가 들어있는지 확인할 수 있는 Contains() 함수

bool bHello   = StrArr.Contains(TEXT("Hello"));
bool bGoodbye = StrArr.Contains(TEXT("Goodbye"));
// bHello   == true
// bGoodbye == false

 

 

Find 함수 Element가 존재하는지 검사해서 있으면 인덱스를 반환한다.

다만 이러한 검색 기능의 경우에는 모든 요소를 순회해야 될 수도 있기 때문에 효율이 좋지 않다.

int32 Index;
if (StrArr.Find(TEXT("Hello"), Index))
{
    // Index == 3
}

 

---

 

 

제거

 

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]

 

 

모든 요소 비우기

ValArr2.Empty();
// ValArr2 == []

---

 

 

힙

 

TArray는 Heapify 함수를 사용하여 이진 힙으로 변경시킬 수 있다.

TArray<int32> HeapArr;

for (int32 Val = 10; Val != 0; --Val)
{
    HeapArr.Add(Val);
}
// HeapArr == [10,9,8,7,6,5,4,3,2,1]

HeapArr.Heapify();
// HeapArr == [1,2,4,3,6,5,8,10,7,9]

 

위와 같이 Heap 형태로 변경되는 아래의 Heap 전용 방법들을 사용할 수 있다.

HeapArr.HeapPush(4);
// HeapArr == [1,2,4,3,4,5,8,10,7,9,6]

int32 TopNode;
HeapArr.HeapPop(TopNode);
// TopNode == 1
// HeapArr == [2,3,4,6,4,5,8,10,7,9]

HeapArr.HeapRemoveAt(1);
// HeapArr == [2,4,4,6,9,5,8,10,7]

int32 Top = HeapArr.HeapTop();
// Top == 2

---

 

 

 

Slack

 

• 배열은 크기변경이 가능하므로, 메모리 사용량이 가변적이다.
• 배열이 추가될 때마다 매번 재할당을 피하기 위해, Allocator는 보통 요청양보다 더 큰 메모리 공간을 만든다. 이는 Add 호출시 재할당에 드는 퍼포먼스 비용을 줄이기 위해서다.
• 마찬가지로 엘리먼트를 삭제한다고 메모리가 해제되지는 않으며, 배열에 여유분 Slack(=현재 사용되지는 않아도 사실상 미리 할당된 엘리먼트 저장 슬롯)을 남길 뿐이다.

 

• Vector의 Capacity와 유사한 개념.
• 기본 생성된 배열은 메모리 할당이 없으므로, 초기 Slack은 0.
• Slack를 고려하여 메모리를 할당하면 오버헤드를 줄일 수 있다.
• 연관 함수: GetSlack, Empty, Reset, Shrink 

---

 

 

원시 메모리

 

• TArray는 할당된 메모리를둘러싼 포장 단위일 뿐이다. 
• AddUninitialized, InsertUninitialized 함수는 배열에 초기화되지 않은 공간 추가한다. Add, Insert 함수처럼 작동은 하지만, 해당 Element type의 생성자를 호출하지는 않는다.
• Memcpy 호출로 전체 구조체를 덮어쓰려는 경우처럼 생성자 호출을 피할 때 좋다.

int32 SrcInts[] = { 2, 3, 5, 7 };
TArray<int32> UninitInts;
UninitInts.AddUninitialized(4);
FMemory::Memcpy(UninitInts.GetData(), SrcInts, 4*sizeof(int32));
// UninitInts == [2,3,5,7]

---

 

 

예제 코드

 

#include "MyGameInstance.h"
#include "Algo/Accumulate.h"

void UMyGameInstance::Init()
{
	const int32 ArrNum = 10;
	
	TArray<int32> Int32Array; 
    
    // 1~10까지 넣기
	for (int32 i = 1; i <= ArrNum; ++ix)
	{
		Int32Array.Add(i); // Emplace를 사용해도 된다.
	}

	// 짝수 없개기
	Int32Array.RemoveAll([](int32 Val) 
		{
			return Val % 2 == 0;
		});

	// 짝수 넣기
	Int32Array += { 2,4,6,8,10 };
    
    
    TArray<int32> Int32ArrayCompare;
	int32 CArray[] = { 1,3,5,7,9,2,4,6,8,10 };

	Int32ArrayCompare.AddUninitialized(ArrNum); // ArrNum 개수 만큼의 공간을 추가
	FMemory::Memcpy(Int32ArrayCompare.GetData(), CArray, sizeof(int32) * ArrNum); // CArray의 모든 요소가 Int32ArrayCompare 배열로 복사
	
	ensure(Int32Array == Int32ArrayCompare); // 다르면 Error. 해당 예제는 통과.
    
    
    
	int32 Sum = 0;
	for (const int32& Int32Elem : Int32Array) {
		Sum += Int32Elem;
	}
    
    ensure(Sum == 55);

	int32 SumByAlgo = Algo::Accumulate(Int32Array, 0);
	ensure(Sum == SumByAlgo);
}

 

 

 

---

 

 

 

 

TSet의 구조와 활용 

---

 

 

TSet의 특징

 

• STL의 set과 언리얼 TSet의 비교 
  • 이진 트리로 구성되어 있어 자동 정렬을 지원함.
  • 메모리 구성이 효율적이지 않음.
  • 요소가 삭제될 때 균형을 위한 재구축이 일어날 수 있음.
  • 모든 자료를 순회하는데 적합하지 않음.
• 언리얼 TSet의 특징
  
  • 해시 테이블 형태로 Key 데이터가 구축되어 있어 빠른 검색이 가능함.
  • 동적 가변 배열의 형태로 데이터가 모여있음.
  • 데이터를 빠르게 순회할 수 있음.
  • 동적 배열에 비어있는 데이터가 있을 수 있음. 순서가 보장되지 않음.
  • 데이터 삽입 시 비어있는 부분을 메꾸는 방식으로 데이터를 삽입한다.
  • 삭제해도 재구축이 일어나지 않음. 데이터 구조는 sparse array(희소 배열)
• STL set과 TSet은 활용 방법은 서로 다르기 때문에 주의할 것.
• TSet은 STL의 unordered_set과 유사하지만 동일하진 않음.
• TSet은 중복 없는 데이터 집합을 구축하는데 유용하게 사용할 수 있음

 

 

• operator== :  Element를 직접 비교
• GetTypeHash :  해싱
  • 기본적인 `FString`이나 `int`, `UObject`들은 해싱 값들을 가지고 있다.
  • 새로운 구조체를 사용해 `TSet`을 만들고 싶으면 해당 자료형에 대한 `GetTypeHash` 함수를 만들어줘야 한다.
• Add , Emplace :  삽입. Emplace의 경우 복사 없이 데이터 추가
• Append :  병합

 

https://dev.epicgames.com/documentation/ko-kr/unreal-engine/set-containers-in-unreal-engine

언리얼 엔진의 세트 컨테이너

---

 

 

 

 

Iterator

 

for (auto& Elem : FruitSet)
{
    FPlatformMisc::LocalPrint(
        *FString::Printf(
            TEXT(" \"%s\"\n"),
            *Elem
        )
    );
}
// Output:
// 	"Banana", "Grapefruit", "Pineapple", "Pear", ...

 

for (auto It = FruitSet.CreateConstIterator(); It; ++It)
{
    FPlatformMisc::LocalPrint(
        *FString::Printf(
            TEXT("(%s)\n"),
            *It
        )
    );
}

---

 

 

Slack

 

• 데이터를 제거할 때 메모리에서 완전히 제거하는 것이 아니라, 비어있는 상태로 그냥 놔두는 거다. 비어있는 상태로 놔두기 때문에 <invalid>로 표시해둔다. 그렇기 때문에 데이터의 뒷부분에 생기는 슬랙이 있고, 이 데이터 중간중간에 생기는 슬랙이 있다.
• Shrink 함수는 컨테이너 끝에서부터 모든 슬랙을 제거하지만, 중간이나 시작 부분의 빈 Element는 놔둔다.

// 세트에서 엘리먼트를 하나 건너 하나씩 제거합니다.
for (int32 i = 0; i < 10; i += 2)
{
    FruitSet.Remove(FSetElementId::FromInteger(i));
}
// FruitSet == ["Fruit8", <invalid>, "Fruit6", <invalid>, "Fruit4", <invalid>, "Fruit2", <invalid>, "Fruit0", <invalid> ]

---

 

 

 

 

예제 코드

 

#include "MyGameInstance.h"
#include "Algo/Accumulate.h"

void UMyGameInstance::Init()
{
	TSet<int32> Int32Set;
	for (int32 i = 1; i <= 10; i++) {
		Int32Set.Add(i);
	}

	// Remove All처럼 한번에 다 지우는 함수는 없다. 아래와 같이 하나씩 지워줘야 한다.
	Int32Set.Remove(2);
	Int32Set.Remove(4);
	Int32Set.Remove(6);
	Int32Set.Remove(8);
	Int32Set.Remove(10);
}

 

5개를 지웠지만 메모리는 여전히 10개를 차지하고 있다. 비어있는 부분은 < invalid > 로 남아있다.

만약에 이 상태에서 Add 로 데이터를 추가하면 비어있는 부분을 우선적으로 채운다.

---

 

 

자료구조의 시간 복잡도 비교

 

	TArray	TSet
접근	O(1)	O(1)
검색	O(N)	O(1)
삽입	O(N)	O(1)
삭제	O(N)	O(1)
	빈틈없는 메모리 (캐시 지역성 높음) 가장 높은 접근성능 가장 높은 순회성능	메모리에 빈틈이 있을 수 있음 빠른 중복 감지

 

---