UE5 TSet

1. TSet

TSet은 언리얼 엔진에서 제공하는 "고유한(unique) 원소들을 순서 없이(unordered) 저장하는 컨테이너"입니다. C++ 표준 라이브러리의 std::unordered_set과 유사한 개념이지만, 언리얼 엔진의 UObject 시스템과 긴밀하게 통합되어 있으며, 가비지 컬렉션, 리플렉션, 직렬화와 같은 엔진 기능을 지원합니다.

• 고유성: TSet에 저장되는 모든 원소는 유일해야 합니다. 중복된 원소의 추가는 무시됩니다.
• 빠른 검색: 해시 테이블(Hash Table)을 기반으로 구현되어 있어 평균적으로 O(1)의 시간 복잡도로 원소의 검색, 추가, 삭제가 가능합니다. 최악의 경우(해시 충돌이 많이 발생하는 경우) O(N)이 될 수 있습니다.
• 순서 없음: 원소들은 특정 순서에 따라 정렬되지 않습니다. 삽입 순서나 값의 크기에 관계없이 내부 해시 함수에 의해 위치가 결정됩니다.
• 메모리 관리: 언리얼의 메모리 관리 시스템을 사용하므로, UObject 포인터를 저장할 경우 가비지 컬렉터가 자동으로 참조를 관리합니다.
• 리플렉션 및 직렬화: UPROPERTY 매크로와 함께 사용하면 언리얼 리플렉션 시스템에 의해 인식되어 에디터에서 편집하거나 디스크에 저장/로드할 수 있습니다.

2. 내부 구조 및 구현 방식

TSet의 핵심은 해시 테이블입니다. 내부적으로 TArray를 사용하여 해시 버킷(bucket)을 관리하고, 각 버킷에서 연결 리스트(linked list) 또는 다른 자료구조를 통해 해시 충돌(hash collision)을 처리합니다.

TSet의 내부 구조는 FSparseArray와 FSetElement의 조합으로 이루어져 있습니다.

1. Elements (TSparseArray<FSetElement, ...>):
   • TSet의 핵심 데이터 저장소입니다. TSparseArray를 사용하여 원소들을 저장하며, 이는 메모리 할당/해제 오버헤드를 줄이고 데이터 접근을 효율적으로 만듭니다.
   • TSparseArray는 할당된 원소의 유효 여부를 비트 배열(AllocationFlags)로 관리하여, 원소를 삭제하더라도 메모리를 즉시 해제하지 않고 "빈 공간"으로 표시합니다. 이 공간은 나중에 새로운 원소가 추가될 때 재사용될 수 있습니다.
2. FSetElement:
   • TSet에 저장되는 각 원소는 FSetElement 구조체로 래핑됩니다.
   • 이 구조체는 실제 데이터(Value)와 함께, 해시 테이블의 연결 리스트를 구현하기 위한 NextInHash 인덱스, 그리고 원소 자체의 해시 값을 캐싱하는 ValueHash를 포함합니다.

   template<typename InElementType>
   struct FSetElement
   {
       InElementType Value;
       int32 NextInHash;
       int32 ValueHash;
   };

3. Hash (int32* 또는 TArray<int32>):
   • 해시 테이블의 버킷 역할을 하는 배열입니다. HashSize만큼의 크기를 가지며, 각 인덱스는 특정 해시 값에 해당하는 첫 번째 원소의 인덱스를 Elements 배열 내에서 가리킵니다.
   • 만약 해당 버킷이 비어있다면 -1 (INDEX_NONE) 값을 가집니다.
4. HashSize:
   • 해시 테이블의 버킷 수입니다. 원소의 수가 늘어남에 따라 동적으로 크기가 조절(rehash)되어 성능을 유지합니다.

동작 과정

TSet::Add(Element)가 호출될 때의 내부 동작은 다음과 같습니다.

1. 해시 계산: 추가할 Element의 해시 값(KeyFuncs::GetKeyHash(Element))을 계산합니다.
2. 버킷 인덱스 결정: 계산된 해시 값을 HashSize로 나눈 나머지(Hash % HashSize)를 통해 해당 원소가 위치할 버킷의 인덱스를 결정합니다.
3. 중복 확인:
   • Hash 배열에서 버킷 인덱스에 해당하는 Elements의 인덱스를 가져옵니다.
   • 해당 인덱스부터 시작하여 FSetElement의 NextInHash를 따라가며 연결 리스트를 순회합니다.
   • 순회하면서 같은 해시 값과 동일한 Element가 있는지 확인합니다. 동일한 원소가 이미 존재하면 추가를 중단하고 해당 원소의 인덱스를 반환합니다.
4. 원소 추가:
   • 중복된 원소가 없다면, Elements(TSparseArray)에 새로운 FSetElement를 추가합니다. 이 과정에서 TSparseArray는 비어있는 공간을 재사용하거나, 공간이 없다면 배열의 크기를 늘립니다.
   • 새로 추가된 FSetElement의 Value에 Element를 저장하고, ValueHash에 계산된 해시 값을 저장합니다.
   • 기존 버킷의 첫 번째 원소 인덱스를 새로운 FSetElement의 NextInHash에 저장합니다.
   • Hash 배열의 해당 버킷 인덱스가 새로운 FSetElement의 인덱스를 가리키도록 업데이트합니다.
5. Rehash (필요시): 원소의 수가 특정 임계값(Load Factor)을 초과하면, 해시 충돌을 줄이고 성능을 유지하기 위해 Hash 배열의 크기(HashSize)를 늘리고 모든 원소를 새로운 해시 테이블에 재배치하는 Rehash 과정이 발생합니다.

3. 계층 구조

TSet의 동작 계층은 다음과 같이 나눌 수 있습니다.

1. 사용자 영역 (User-Level Code):
   • 게임플레이 로직이나 에디터 기능에서 TSet을 선언하고 Add, Remove, Contains 등의 API를 사용합니다.
   • UPROPERTY()를 붙여 리플렉션 시스템에 노출시킵니다.
   • 예: TSet<AActor*> OverlappingActors;
2. 언리얼 API 계층 (Unreal API Layer):
   • TSet 클래스에 정의된 public 메서드들입니다. 사용자가 호출한 함수를 내부 구현에 맞게 변환합니다.
   • 이 계층에서 KeyFuncs 템플릿을 통해 원소 타입에 맞는 해시 함수(GetKeyHash)와 비교 함수(Matches)를 결정합니다.
3. 컨테이너 구현 계층 (Container Implementation Layer):
   • TSet의 핵심 로직이 위치하는 곳입니다.
   • 해시 값을 계산하고, TSparseArray를 사용하여 원소를 저장하며, Hash 배열을 통해 버킷을 관리합니다.
   • 해시 충돌 처리, Rehash 등 실제 자료구조의 동작이 이루어집니다.
4. 메모리 할당 계층 (Memory Allocation Layer):
   • FMemory API를 통해 언리얼 엔진의 메모리 관리자(예: FMallocBinned2)로부터 필요한 메모리를 할당받습니다.
   • TSparseArray가 내부적으로 원소를 저장할 TArray의 메모리를 할당/재할당하는 부분입니다.
5. UObject 시스템 계층 (UObject System Layer):
   • TSet이 UObject*를 저장하는 경우, 가비지 컬렉션(GC) 시스템과 상호작용합니다.
   • TSet은 GC 과정에서 자신이 참조하는 UObject들을 보고하여, 해당 객체들이 메모리에서 해제되지 않도록 합니다.
   • 직렬화(Serialization) 시, FArchive를 통해 TSet의 내용이 디스크에 저장되거나 로드됩니다.

4. TSet과 다른 컨테이너와의 비교

특징	TSet	TArray	TMap	TSparseArray
주요 목적	고유 원소의 빠른 검색 및 관리	순서가 있는 동적 배열	Key-Value 쌍의 빠른 검색	메모리 안정성을 보장하는 동적 배열
원소 고유성	보장 (Unique)	보장 안 함 (Duplicates allowed)	Key는 고유, Value는 중복 가능	보장 안 함
순서	없음 (Unordered)	있음 (Ordered)	없음 (Unordered Keys)	있음 (Ordered, 단 삭제된 공간 존재)
검색 시간 복잡도	평균 O(1), 최악 O(N)	O(N)	평균 O(1), 최악 O(N)	O(1) (인덱스 접근 시)
추가/삭제 시간 복잡도	평균 O(1)	끝: O(1) (Amortized), 중간: O(N)	평균 O(1)	O(1) (Amortized)
메모리 포인터 안정성	불안정 (Rehash 시 주소 변경 가능)	불안정 (재할당 시 주소 변경 가능)	불안정 (Rehash 시 주소 변경 가능)	안정 (원소의 메모리 주소 불변)
주요 사용 사례	- 중복 없이 여러 객체를 관리할 때 - 특정 아이템의 존재 여부를 빠르게 확인할 때 - 오버랩된 액터 목록 관리	- 순서가 중요한 데이터 목록 - 대부분의 일반적인 동적 배열 요구사항	- ID로 객체를 빠르게 찾을 때 - 설정 값, 상태 등 관리	- 원소의 포인터/인덱스가 변하지 않아야 할 때 - 잦은 추가/삭제가 일어나는 경우

TSet의 장단점

장점:

• 매우 빠른 원소 조회: Contains() 연산이 평균 O(1)이므로, 특정 원소가 집합에 포함되어 있는지 매우 빠르게 확인할 수 있습니다.
• 자동 중복 제거: 원소의 고유성이 보장되므로, 중복 데이터를 신경 쓸 필요가 없습니다.
• UObject 통합: 가비지 컬렉션, 리플렉션, 직렬화를 완벽하게 지원하여 언리얼 생태계에서 사용하기 편리합니다.

단점:

• 순서 없음: 원소들이 정렬되지 않으므로, 순서가 중요한 경우에는 TArray를 사용해야 합니다.
• 메모리 오버헤드: 해시 테이블 구조를 유지하기 위해 TArray보다 추가적인 메모리(해시 버킷, FSetElement 래퍼 등)를 사용합니다.
• 포인터 불안정성: Rehash가 발생하면 내부 데이터의 메모리 위치가 변경될 수 있으므로, TSet 내부 원소의 주소를 직접 저장하여 사용하는 것은 위험합니다.
• 해시 함수 의존성: 성능이 해시 함수의 품질에 크게 의존합니다. 사용자 정의 struct나 class를 TSet에 사용하려면 좋은 해시 함수를 직접 구현해야 합니다.

5. 언제 어디에 사용하는가?

TSet은 다음과 같은 상황에서 유용하게 사용됩니다.

• 존재 여부의 빠른 확인: 플레이어가 특정 버프에 걸려있는지, 특정 아이템을 이미 획득했는지 등을 확인할 때.

    TSet<TSubclassOf<UMyBuff>> ActiveBuffs;
    if (ActiveBuffs.Contains(FireBuffClass))
    {
        // 화염 버프에 걸려있을 때의 로직
    }

• 중복 없는 목록 관리: 트리거 볼륨 안에 들어온 액터들의 목록을 관리할 때. OnBeginOverlap에서 추가하고 OnEndOverlap에서 제거하면, 같은 액터가 여러 번 추가되는 것을 신경 쓸 필요가 없습니다.

    UPROPERTY()
    TSet<AActor*> OverlappingActors;

    void AMyTriggerVolume::NotifyActorBeginOverlap(AActor* OtherActor)
    {
        OverlappingActors.Add(OtherActor);
    }

• 데이터 처리 파이프라인: 대규모 데이터 집합에서 중복을 제거하고 고유한 값만 추출하여 다음 단계로 넘길 때.

6. 요약

TSet은 언리얼 엔진에서 사용하는 컨테이너 중 하나로, 수학의 '집합'처럼 고유한 원소들만 순서 없이 모아놓는 데 사용됩니다. C++의 std::unordered_set과 비슷하다고 생각하시면 됩니다. 가장 큰 특징은 특정 원소가 이 집합 안에 들어있는지 아닌지를 매우 빠르게, 평균적으로 O(1) 시간 복잡도로 확인할 수 있다는 점입니다.

TSet은 내부적으로 '해시 테이블'이라는 자료구조를 사용합니다. 각 원소의 데이터를 기반으로 '해시 값'이라는 고유한 숫자 값을 계산하고, 이 해시 값을 배열의 인덱스로 사용해서 원소를 저장할 위치를 빠르게 찾아냅니다. 만약 다른 원소가 같은 위치를 차지하려고 하면(해시 충돌), 연결 리스트 방식으로 그 뒤에 연결해서 데이터를 저장합니다. 이러한 구조 덕분에 데이터가 아무리 많아져도 검색, 추가, 삭제 속도가 거의 일정하게 유지됩니다. 또한, 언리얼의 TSparseArray를 기반으로 메모리를 관리하여, 원소를 삭제해도 메모리 재할당이 자주 발생하지 않도록 최적화되어 있습니다.

TArray는 데이터를 순서대로 저장하는 동적 배열이고, TSet은 순서 없이 고유한 데이터만 저장하는 집합입니다. 따라서 데이터의 순서가 중요하거나 중복된 값을 허용해야 한다면 TArray를 써야 합니다. 반면, 데이터의 순서는 상관없고, '이 데이터가 목록에 존재하는가?'를 매우 빠르게 확인해야 하거나 중복된 데이터를 자동으로 걸러내고 싶을 때 TSet을 사용하는 것이 훨씬 효율적입니다. 예를 들어, 스킬 범위 안에 들어온 적들을 중복 없이 관리하거나, 플레이어가 이미 방문한 지역인지를 체크하는 등의 용도로 TSet이 아주 유용합니다.