언리얼 컨테이너 라이브러리(1) - Array와 Set

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

• UCL(Unreal Container Library)
• 언리얼 엔진이 자체 제작해 제공하는 자료구조 라이브러리
• 실제 게임 제작에 유용하게 사용되는 라이브러리: TArray, TMap, TSet
• T: Template Library
• TMap, TSet의 이름과 용도는 map, set과 유사하지만, 내부적으로 다르게 구현되어 있음.

TArray

• 가변 배열 자료구조
• STL의 vector와 유사
• 게임 제작에서는 가변 배열 자료구조를 효과적으로 활용하는 것이 좋음.
  • 데이터가 순차적으로 모여있기 때문에 메모리 사용 효과적, 캐시 효율이 높다.
  • 컴퓨터의 사양이 좋아지면서, 캐시 용량이 늘어나고 캐시 지역성으로 인한 성능이 굉장히 높아짐.
  • 랜덤 엑세스, 고속 요소 순회 가능.

---

// Fill out your copyright notice in the Description page of Project Settings.


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

void UMyGameInstance::Init()
{
	Super::Init();
	
	const int32 ArrayNum = 10;
	TArray<int32> Int32Array;

	for (int32 ix = 1; ix <= 10; ++ix)
	{
		Int32Array.Add(ix);
	}

	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(ArrayNum);
	FMemory::Memcpy(Int32ArrayCompare.GetData(), CArray, sizeof(int32) * ArrayNum);

	ensure(Int32Array == Int32ArrayCompare);

	int32 Sum = 0;
	for (const int32& Int32Elem : Int32Array)
	{
		Sum += Int32Elem;
	}

	ensure(Sum == 55);

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

---

TSet

• STL set의 특징
  • 이진 트리로 구성, 정렬 지원.
  • 메모리 구성이 효율적이지 않음.
  • 요소가 삭제될 때 균형을 위한 재구축이 일어날 수 있음.
  • 모든 자료를 순회하는데 적합하지 않음.
• 언리얼 TSet의 특징
  • 해시테이블 형태, 빠른 검색 가능.
  • 동적 배열의 형태로 데이터가 모여있음
  • 빠르게 순회할 수 있음.
  • 재구축이 일어나지 않음.
  • 비어있는 데이터가 있을 수 있음.

---

// Fill out your copyright notice in the Description page of Project Settings.


#include "MyGameInstance.h"

void UMyGameInstance::Init()
{
	Super::Init();
	
	const int32 ArrayNum = 10;

	TSet<int32> Int32Set;
	for (int32 ix = 1; ix <= ArrayNum; ++ix)
	{
		Int32Set.Add(ix);
	}

	Int32Set.Remove(2);
	Int32Set.Remove(4);
	Int32Set.Remove(6);
	Int32Set.Remove(8);
	Int32Set.Remove(10);
	Int32Set.Add(2);
	Int32Set.Add(4);
	Int32Set.Add(6);
	Int32Set.Add(8);
	Int32Set.Add(10);
}

---

시간 복잡도 비교

• TArray: 빈틈없는 메모리, 가장 높은 접근성능, 가장 높은 순회성능
• TSet: 빠른 중복 감지

	TArray	TSet
접근	O(1)	O(1)
검색	O(N)	O(1)
삽입	O(N)	O(1)
삭제	O(N)	O(1)