Ch 10. Array and Set

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

10.1-1 언리얼 컨테이너 라이브러리

  - 언리얼 엔진이 자체 제작해 제공하는 자료구조 라이브러리

    줄여서 UCL이라고도 함.

  - 언리얼 오브젝트를 안정적으로 지원하고 다수의 오브젝트 처리에 유용함.

    실제 게임 제작에는 TArray/TSet/TMap이 유용하게 사용됨.

 

10.1-2 C++ STL Vs. UCL

  - STL은 범용적임. UCL은 언리얼 엔진에 특화되어 있음.

    STL은 호환성이 높음. UCL은 언리얼 오브젝트에 특화됨.

    STL은 많은 기능이 구현되어 있어서 컴파일 시간이 오래 걸림.

    UCL은 게임 제작에 최적화되어 있음.

 

10.1-3 TArray, TSet, TMap

  - TArray

    STL의 Vector와 유사함. 오브젝트를 순서대로 담아 관리하는 용도.

  - TSet

    STL의 Unordered Set과 유사함. 중복되지 않는 요소로 구성된 집합을 만드는 용도.

  - TMap

    STL의 Unordered Map과 유사함. 중복되지 않은 키-벨류 쌍의 레코드를 관리하는 용도.

 

10.1-4 TArray 개요

  - 게임 제작에서는 TArray 같은 가변 배열 자료구조를 효과적으로 활용하는 것이 중요함.

    데이터가 순차적으로 모여있기 때문에 메모리를 효과적으로 사용할 수 있고 캐시 효율이 높음.

    컴퓨터 사양이 좋아지면서, 캐시 지역성으로 인한 성능 향상은 굉장히 중요함.

    임의 데이터의 접근이 빠르고, 고속으로 요소를 순회하는 것이 가능함.

  - 가변배열의 단점은 중간에 요소를 삽입/삭제하는 비용이 크다는 것.

    데이터가 많아질수록 검색, 삽입, 삭제 작업이 느려지므로 

    많은 수의 데이터를 검색, 삽입, 삭제 하는 경우에는 TSet을 사용하는 것이 좋음.

  - 프리미티브 타입의 경우엔 Add()를 사용해서 가독성을 고려하고,

    개체의 경우엔 Emplace()를 사용해서 성능을 고려하는게 권장됨.

 

10.1-5 TArray 예제

<hide/>

// MyGameInstance.cpp

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

...

void UMyGameInstance::Init()
{
	Super::Init();

	const int32 ArrayNum = 10;
	TArray<int32> Int32Array;

	for (int32 ix = 1; ix <= ArrayNum; ++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);
}

 

10.1-5 STL Set Vs. TSet Vs. TArray

STL Set	UCL TSet
이진 트리 기반. 정렬을 지원함.	해시 테이블 기반. 빠른 검색이 가능함.
메모리 구성이 효율적이지 않음.	동적 배열의 형태로 메모리 구성이 효율적임.
요소가 삭제될 때 균형을 위한 재구축이 일어날 수 있음.	삭제해도 재구축이 일어나지 않음.
모든 자료를 순회하는데 적합하지 않음.	빠르게 순회할 수 있음.
	비어있는 요소가 있을 수 있음. 추후에 삽입되는 데이터가 비어있는 요소를 채움.

	TArray (캐시 지역성, 임의접근)	TSet (빠른 중복 감지)
접근	O(1)	O(1)
검색	O(N)	O(1)
삽입	O(N)	O(1)
삭제	O(N)	O(1)

 

10.1-6 TSet 실습

<hide/>

// MyGameInstance.cpp

...

void UMyGameInstance::Init()
{
	...

	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);
}