[언리얼 C++] 컨테이너 클래스 TArray 사용법 (힙, 슬랙)

TArray 컨테이너 클래스의 기본적인 설명과 간단한 사용법은 [언리얼 C++] 컨테이너 클래스 TArray 사용법 (생성 및 삽입, 반복처리) (tistory.com) 글을 참고하시기 바랍니다.

이 글에서는 TArray 컨테이너 클래스의 힙과 슬랙에 대해 알아보겠습니다.

 

 

1. TArray 컨테이너 힙 구조 지원

TArray 컨테이너에는 이진 힙 데이터 구조체를 지원하는 함수가 존재합니다. 힙은 부모 노드가 자신의 어떠한 자식 노드보다 이전 순서 또는 동등한 순서에 위치한 이진 트리 유형입니다. 컨테이너로 구현되면, 트리의 루트 노드는 0번째 인덱스의 엘리먼트이며, N번째 인덱스 노드의 좌우 자식 인덱스는 각각 2N+1과 2N+2입니다. 그리고 같은 레벨에 존재하는 자식 노드들은 서로에 대해 특정한 순서가 없습니다.

 

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 컨테이너는 Heapify() 함수를 사용하여 힙 구조의 컨테이너로 변환시킬 수 있습니다.

술부가 존재할 수도 존재하지 않을 수도 있는데, 술부가 없으면 순서 결정에 엘리먼트 타입의 연산자<를 사용합니다.

힙 구조로 변한 컨테이너의 엘리먼트 순서대로 트리의 노드는 왼쪽에서 오른쪽, 위에서 아래로 읽을 수 있습니다.

참고로 컨테이너는 힙으로 변환시킨 이후 소팅할 필요가 없습니다.

 

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

HeapPush() 함수를 사용하여 힙에 새로운 엘리먼트를 추가할 수 있습니다.

이런식으로 힙에 새로운 엘리먼트를 추가하면 힙 구조의 컨테이너는 트리 유지를 위해 노드의 순서를 변경합니다.

 

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

HeapPop() 함수와 HeapPopDiscard() 함수는 힙 맨 위의 루트 노드를 제거하는데 사용됩니다. 해당 함수들의 차이점은 HeapPop() 함수는 엘리먼트 타입으로의 레퍼런스를 파라미터로 받아 루트 노드의 엘리먼트 사본을 반환하는 반면, HeapPopDiscard() 함수는 반환없이 루트 노드의 엘리먼트를 제거합니다.

두 함수 모두 컨테이너에 가하는 변화는 같으며, 힙의 순서 역시 다른 엘리먼트들을 적절히 변경하여 유지합니다.

 

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

HeapRemoveAt() 함수는 컨테이너에서 주어진 인덱스의 엘리먼트를 제거한 후, 다른 엘리먼트들의 순서를 변경하여 힙의 순서를 유지합니다.

 

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

마지막으로, HeapTop() 함수를 사용하여 루트 노드의 엘리먼트 값을 받아올 수 있습니다.

해당 함수로 힙의 순서가 변경되지는 않습니다.

 

 

2. TArray 컨테이너의 슬랙 지원

컨테이너는 크기 변경이 가능하므로, 메모리 사용량이 가변적입니다. 컨테이너에 엘리먼트가 추가될때마다 메모리 재할당을 매번 하는것을 피하기 위해, 얼로케이터는 보통 요청한 것보다 넉넉한 메모리를 제공하여 앞으로의 Add() 함수 호출시 메모리 재할당에 드는 퍼포먼스 비용을 물지 않도록 합니다. 마찬가지로 엘리먼트를 삭제한다고 메모리가 해제되지는 않으며, 컨테이너의 슬랙(여유분), 즉 현재 사용되지는 않아도 사실상 미리 할당된 엘리먼트 저장 슬롯을 남길 뿐입니다. 컨테이너의 슬랙 양은 현재 컨테이너에 있는 엘리먼트의 수와, 엘리먼트를 몇 개나 더 추가하면 다음 할당이 일어나는지에 대한 차이로 정의할 수 있습니다.

 

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

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

SlackArray.Add(2);
SlackArray.Add(3);
SlackArray.Add(4);
SlackArray.Add(5);
// SlackArray.GetSlack() = 17
// SlackArray.Num()      = 5
// SlackArray.Max()      = 22

기본 생성된 컨테이너는 메모리 할당이 없으므로, 초기 슬랙은 0이 됩니다.

GetSlack() 함수를 사용하면 컨테이너의 슬랙 크기가 얼마나 되는지 알아낼 수 있습니다. 다른 방법으로, Max() 함수를 사용하면 재할당이 일어나기 전까지 컨테이너에 저장할 수 있는 최대 엘리먼트 개수를 구할 수 있습니다.

GetSlack() 함수의 반환값은 Max() 함수의 반환값과 Num() 함수의 반환값의 차이와 같습니다.

재할당 이후 컨테이너의 슬랙 양은 얼로케이터에 의해 결정되므로, 사용자가 남아있는 슬랙이 일정할 거라 믿어서는 안됩니다.

 

SlackArray.Empty();
// SlackArray.GetSlack() = 0
// SlackArray.Num()      = 0
// SlackArray.Max()      = 0
SlackArray.Empty(3);
// SlackArray.GetSlack() = 3
// SlackArray.Num()      = 0
// SlackArray.Max()      = 3
SlackArray.Add(1);
SlackArray.Add(2);
SlackArray.Add(3);
// SlackArray.GetSlack() = 0
// SlackArray.Num()      = 3
// SlackArray.Max()      = 3

슬랙 관리가 필수는 아니지만, 알아두면 컨테이너 최적화 힌트를 얻는데 도움이 될 수는 있습니다. 예를 들어 컨테이너에 엘리먼트를 100개쯤 추가해야 겠다고 알고 있는 상황에서, 슬랙이 최소 100개 이상은 되는 것으로 알고있다면 그냥 추가해도 할당이 새로 일어나지는 않을 것입니다.

Empty() 함수는 선택사항으로 슬랙 인수를 받습니다. 위 예제 코드에서는 3을 받아서 3개의 슬랙이 생성되었습니다.

 

SlackArray.Reset(0);
// SlackArray.GetSlack() = 3
// SlackArray.Num()      = 0
// SlackArray.Max()      = 3
SlackArray.Reset(10);
// SlackArray.GetSlack() = 10
// SlackArray.Num()      = 0
// SlackArray.Max()      = 10

Empty() 함수와 비슷한 방식으로 작동하는 Reset() 함수가 있는데, 요청된 슬랙이 현재 할당으로 충분한 경우 메모리를 해제하지 않는다는 차이점이 있습니다. 하지만 요청된 슬랙이 더 크다면, 메모리를 추가로 할당합니다.

 

SlackArray.Add(5);
SlackArray.Add(10);
SlackArray.Add(15);
SlackArray.Add(20);
// SlackArray.GetSlack() = 6
// SlackArray.Num()      = 4
// SlackArray.Max()      = 10
SlackArray.Shrink();
// SlackArray.GetSlack() = 0
// SlackArray.Num()      = 4
// SlackArray.Max()      = 4

마지막으로, Shrink() 함수를 사용하여 모든 슬랙을 제거할 수 있습니다.

해당 함수를 사용하면 현재 엘리먼트 저장에 필요한 최소 크기로 할당을 조정합니다.

Shrink() 함수로 인해서는 컨테이너의 엘리먼트에 어떠한 변경도 발생하지 않습니다.