[Unreal] TArray, TSet

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

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

■ C++ STL과 UCL의 차이

· C++ STL은 범용적으로 설계됨
· C++ STL은 표준이기 때문에 호환성이 높음
· C++ STL은 많은 기능이 엮여 있어 컴파일 시간이 오래 걸림
· UCL은 언리얼 엔진에 특화됨
· UCL은 언리얼 오브젝트 구조를 안정적으로 지원함
· UCL은 가볍고 게임 제작에 최적화되어 있음.

* 언리얼 사용 중에는 STL은 인클루드하지 말고 UCL을 사용해야 한다.

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

· 두 라이브러리의 이름과 용도는 유사하지만, 내부적으로 Set과 Map은 다르게 구현되어 있음.
· TArray (C++ vector) : 오브젝트를 순서대로 담아 효율적으로 관리하는 용도로 사용
· TSet (C++ set) : 중복되지 않는 요소로 구성된 집합을 만드는 용도로 사용
· TMap (C++ map) : 키, 밸류 조합의 레코드를 관리하는 용도로 사용

 

■ TArray 개요

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

Array Containers In Unreal Engine | 언리얼 엔진 5.4 문서 | Epic Developer Community

· TArray는 가변 배열의 자료구조. STL vector의 동작 원리와 거의 비슷함
· 게임 제작에선 가변 배열 자료구조를 효과적으로 활용하는 것이 좋음
    · 데이터가 순차적으로 모여있기 때문에 메모리를 효과적으로 사용할 수 있고 캐시 효율이 높다.
     · 컴퓨터 사양이 좋아지면서, 캐시 지역성 (Locality)으로 인한 성능 향상은 굉장히 중요해짐.
     · 임의 데이터의 접근이 빠르고, 고속으로 요소를 순회하는 것이 가능.

· 가변배열의 단점
     · 맨 끝에 데이터를 추가하는 것 (Add/Emplace, Append, +=연산자)은 가볍지만, 중간에 요소를 추가하거나 삭제하는 작업은 비용이 큼 (Insert, Remove)

· 데이터가 많아질수록 검색, 삭제, 수정 작업이 느려지기 때문에, 많은 수의 데이터에서 검색 작업이 빈번하게 일어난다면 TArray대신 TSet을 사용하는 것이 좋음.

■ TArray 특징

· TArray는 값 유형으로, TArray 인스턴스를 new 혹은 delete로 생성 또는 소멸시키는 것은 좋지 않다. 다른 TArray 변수에서 TArray 변수를 만들면 그 엘리먼트를 새 변수에 복사하며, 공유되는 상태는 없다.
· 선언만 했을 경우 이 시점에선 비어있는 컨테이너이고 아직 할당된 메모리가 없다.
(ex. TArray<int32> IntArray;)

· 수동으로 값을 채워줘야 하는데, Init함수로 기본값들을 채울 수 있다.
(ex. IntArray.Init(10, 5); // -> IntArray == [10, 10, 10, 10, 10] )

· 요소를 끝에서 추가하는 방법은 Add나 Emplace 함수를 활용할 수 있다.
    · Add 는 추가할 데이터를 밖에서 생성한 뒤 복사해서 TArray에 집어넣는 방식이다.
     · Emplace는 TArray 자체에서 그냥 바로 생성해버리는 방식이다.
          * 그렇기 때문에 Emplace가, 복사 비용과 절차를 생략하기 때문에, 조금 더 효율적이라고 볼 수가 있다.

          * 사소한 유형에는 Add를, 그 외에는 Emplace를 사용하길 에픽에서 권장함. Emplace가 Add보다 효율이 떨어질 일은 절대 없지만, 가독성은 Add가 더 나을 수 있다.

          * 그러므로 Int32와 같은 Primitive 타입은 별로 상관 없지만 데이터가 큰 경우에는 반복문에선 Emplace를 사용하는 것이 훨씬 좋음.

· Append는 다수의 엘리먼트를 한꺼번에 추가할 때 사용한다.

· AddUnique는 기존 컨테이너에 동일한 엘리먼트가 이미 존재하지 않는 경우 새 엘리먼트만 추가한다. <- 이 경우엔 이 함수를 굳이 사용하지 않고 Set을 쓰는 것이 효율적
· Insert는 주어진 인덱스에 추가해 주기 때문에 전체적인 메모리 구조가 바뀌게 된다. 이 경우엔 비용이 좀 발생한다.

· UCL 같은 경우 컨테이너의 요소 수를 가져올 때 Count가 아니라 Num을 사용한다. (ex. SetNum)

· SetNum을 사용하면 우리가 임의로 배열의 크기를 줄였다 늘였다 할 수 있다.

■ TArray Sorting

· 일반적인 Sort 함수를 지원해준다.
· HeapSort를 지원하는데 Sort와 마찬가지로 안정적이지 못하다.
· StableSort를 지원하는데 이는 Merge Sort로 구현되어있다.

 

■ TArray Query

· Num함수를 이용해 엘리먼트가 몇 개인지 확인할 수 있다.
· GetData 함수를 통해 배열 내 엘리먼트에 대한 포인터를 반환시킬 수 있다. 컨테이너가 const인 경우, 반환되는 포인터 역시 const이다.
· GetTypeSize 함수를 통해 엘리먼트가 얼마나 큰지 물어볼 수 있다.
    // uint32 ElementSize = StrArr.GetTypeSize();  -> ElementSize == sizeof(FString)

· IsValidIndex 함수를 통해 유효하지 않은 인덱스에 접근하고 있는지 [Num보다 높거나 0 미만인지] 체크할 수 있다.
     (ex. StrArr.IsValidIndex(-1) -> false, StrArr.IsValidIndex(0) -> true, ...)

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

· Last 혹은 Top 함수를 사용하여 배열 끝에서부터 역순으로 접근할 수 있다. Top은 Last와 달리 인덱스를 받지 않는다.

· Contains 함수를 사용할 수 있는데 ContainsByPredicate를 통해 좀 더 세밀한 검색이 가능하다.

· Find 함수를 통해 엘리먼트를 찾을 수 있다. 하지만 모든 요소를 순회해야 할 수도 있다.
     · 엘리먼트를 찾지 못하면, 특수 값 'INDEX_NONE' 이 반환된다.

· 빈번하게 검색 혹은 제거를 해야한다면 Set 컨테이너를 사용하는 것이 좋다.

※ 엘리먼트가 제거될 경우, 그 뒤의 엘리먼트가 낮은 인덱스로 정리되므로, 배열엔 절대 '구멍'이 생길 수 없다. 즉, 전체 데이터가 재정렬된다.

· 정리 프로세스는 비용이 따른다. 나머지 요소가 어떤 순서로 남아있든 신경쓰지 않는다면 RemoveSwap, RemoveAtSwap, RemoveAllSwap 같은 함수를 사용해 부하를 줄일 수 있다.
하지만 굳이 이렇게까지 해야할 필요가 없다면 Set 컨테이너를 사용하는 것이 좋음

· Empty 함수는 모든 것을 제거한다.

 

■ TArray Operator

· 배열은 일반적인 값 유형으로, 일반적인 생성자 복사나 할당 연산자를 통해 '복사'할 수 있다.

(ex) 
TArray<int32> ValArr3;
ValArr3.Add(1);
ValArr3.Add(2);
ValArr3.Add(3);

auto ValArr4 = ValArr3; // ValArr4 == [1, 2, 3];
ValArr4[0] = 5;

// ValArr3 == [1, 2, 3];
// ValArr4 == [5, 2, 3];

· Append 함수 대신, operator+=를 통해 배열을 연결할 수 있다.
(ex. ValArr4 += ValArr3; // ValArr4 == [5, 2, 3, 1, 2, 3];

· MoveTemp를 사용해 원래 컨테이너가 갖고있었던 데이터를 아예 이주시키는 것도 가능하다.
(ex. ValArr3 = MoveTemp(ValArr4); 
// ValArr3 == [5, 2, 3, 1, 2, 3]
// ValArr4 == []


· operator==, operator!=를 사용해 비교한다. 이때 FString 요소를 비교할 경우 대소문자를 구분하지 않지만, 순서가 뒤바뀐 것은 확인할 수 있다.

 

■ TArray Heap

· TArray에는 이진 힙 데이터 구조체를 지원하는 함수가 있다. Heapify 함수를 사용해 기존 배열을 이진 힙으로 변환할 수 있다.

(ex)
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]

 

■ TArray Slack

배열이 추가될 때마다 매번 메모리 공간을 재할당 하는 것을 피하기 위해, Allocator는 보통 요청한 것보단 넉넉하게 메모리를 제공하여 Add 호출시 재할당에 드는 퍼포먼스 비용을 물지 않도록 한다.
배열에 Slack(여유분, 슬랙), 즉 현재 사용되지는 않아도 사실상 미리 할당된 엘리먼트 저장슬롯을 남길 뿐 엘리먼트를 삭제한다고 해서 메모리가 바로 해제되지는 않는다.

기본 생성된 배열은 메모리 할당이 없으므로, 초기 슬랙은 0이 된다. GetSlack 함수를 통해 배열의 슬랙 크기를 알 수 있다. Max함수를 사용하면 재할당이 일어나기 전까지 배열에 저장할 수 있는 엘리먼트 최대 개수를 구할 수 있다.

* GetSlack == Max - Num

(ex)
TArray<int32> SlackArray;
// SlackArray.GetSlack() == 0
// SlackArray.Num() == 0
// SlackArray.Max() == 0

SlackArray.Add(1);
// SlackArray.GetSlack() == 3
// SlackArray.Num() == 1
// SlackArray.Max() == 4

■ TArray Primitive

TArray는 궁극적으로 할당된 메모리를 둘러싼 포장 단위일 뿐이다.

AddUninitialized 혹은 InsertUninitialized 함수를 통해 배열에 초기화되지 않은 공간에 추가할 수 있다. 이는 각각 Add와 Insert처럼 작동은 하지만, 해당 요소 타입의 생성자를 호출하지 않는다.

 

■ 알고리즘 라이브러리

언리얼 엔진에선 컨테이너에 사용할 수 있는 여러가지 최적화된 알고리즘을 제공해준다.

예로 #include "Algo/Accumulate.h"를 해주면 합계를 구할 수 있는 Accumulate 함수를 구할 수 있다.
(ex. int32 SumByAlgo = Algo::Accumulate(Int32Array, 0); // 첫번째 인자 : 컨테이너, 두번째 인자: 시작위치)

 

■ TSet

참고 : https://dev.epicgames.com/documentation/ko-kr/unreal-engine/set-containers-in-unreal-engine?application_version=5.4

언리얼 엔진의 세트 컨테이너 | 언리얼 엔진 5.4 문서 | Epic Developer Community

 

TSet(세트)는 TMap 및 TMultiMap과 비슷하지만 주요한 차이점이 있다. TSet은 독립된 키로 데이터 값을 연결하기 보단, 데이터 값 자체를 키로 사용한다. 
이는 TSet가 내부적으로 해시테이블로 구성이 되어있어서 요소 값을 평가하는 오버라이드 가능 함수를 사용할 수 있기 때문에 가능하며
요소 추가, 검색, 제거가 매우 빠르다. 기본적으로 TSet은 중복값을 허용하지 않는다. 

* 주로 순서가 중요치 않은 상황에서 고유 요소를 저장하는데 사용되는 고속 컨테이너 클래스이다.

■ TSet의 특징

· STL set VS Unreal TSet
    · STL Set
          · 이진 트리로 구성되어 있어 정렬을 지원
           · 메모리 구성이 효율적이지 않음
           · 요소가 삭제될 때 균형을 위한 재구축이 일어날 수 있음
           · 모든 자료를 순회하는데 적합하지 않음

     · Unreal TSet
           · 해시테이블 형태로 키 데이터가 구축되어 있어서 빠른 검색 가능
           · 동적 배열의 형태로 데이터가 모여있음 (캐시 지역성↑)
           · 데이터를 빠르게 순회할 수 있다.
           · 데이터를 삭제해도 재구축이 일어나지 않음.
           · 비어있는 데이터가 있을 수 있다.

· 따라서 STL set과 Unreal TSet의 활용 방법은 다르기 때문에 주의해야함
· STL의 unordered_set과 유사하게 동작하지만 동일하지 않음
· TSet은 중복없는 데이터 집합을 구축하는데 유용하게 사용할 수 있음

· 중간에 빈 공간이 있으면 해당 공간에 데이터를 추가하기 때문에 순서는 보장이 되지 않는다. 

이는 세트의 데이터 구조가 희소 배열 (Sparse Array) 이기 때문이다.

 

■ TSet 생성 및 채우기

TSet은 operator==로 요소를 직접 비교하고 이때 GetTypeHash로 해싱한다. 만약 새로운 형태의 구조체를 사용해 TSet으로 만들고 싶다면 해당 자료형에 대한 GetTypeHash 함수를 직접 만들어줘야 한다.
세트를 채우는 방식은 TArray와 동일하게 Add 및 Emplace 함수를 사용한다.
또한, TArray와 비슷하게 Append 함수를 통해 다른 세트의 모든 요소를 삽입하는 것도 가능하다.

그리고 UPROPERTY 매크로를 통해 언리얼 에디터에서 요소 추가 및 편집이 가능하다.

■ 찾기

세트에 키가 있는지 확실하지 않은 경우, Contains 함수와 operator[]를 사용해서 검사할 수 있으나, 이는 같은 키에 두 번 조회를 해야하기 때문에 이상적이지 않다.
그러므로 Find 함수를 통해 단 한 번의 조회로 처리하는 것이 합리적이다. 찾지 못할 경우 nullptr를 반환한다.

■ 제거

Remove 함수에 인덱스를 붙여 제거할 수 있긴 하지만, 이는 이터레이션 처리 도중에만 사용하길 에픽에서 권장한다.

■ 복사

TArray와 마찬가지로, TSet는 정규 값 유형이므로 값 대입 시 복사 생성자 또는 할당 연산자를 통해 복사할 수 있다.

■ 슬랙 (Slack)

TArray와 마찬자기로 요소 제거 시 메모리를 해제하는 것이 아니라 <Invalid> 처리를 해주는 것이다. 
이러한 슬랙을 제거해주고 싶다면 Collapse나 Shrink 함수를 사용할 수 있는데 Shrink 함수는 컨테이너 끝 부분부터 모든 슬랙을 제거하지만, 중간이나 시작 부분의 빈 요소는 냅둔다.

 

■ 참고 및 추천 강의

https://www.inflearn.com/course/%EC%9D%B4%EB%93%9D%EC%9A%B0-%EC%96%B8%EB%A6%AC%EC%96%BC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-part-1/dashboard

이득우의 언리얼 프로그래밍 Part1 - 언리얼 C++의 이해 | 이득우 - 인프런