↓Skip to main content

[Unreal] 언리얼 컨테이너 라이브러리

Table of Contents



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

  • Unreal Container Library (UCL)
  • 언리얼이 자체적으로 제작해서 제공하는 라이브러리이다. 언리얼 엔진에 특화되어 있으며, 언리얼 오브젝트 구조만 안정적으로 지원한다. 따라서 언리얼 엔진에서는 C++ STL이 아닌 UCL을 사용하자.

  • 다양한 라이브러리가 있지만 실제 게임 제작에 유용하게 사용되는 라이브러리는 다음 세 가지이다.
    • TArray, TSet, TMap



각 라이브러리의 특징 #


  • 공통 특징
    • 동질성 컨테이너이므로, 안에 있는 요소는 전부 반드시 같은 유형이어야 한다.
    • int32, float 와 같은 값 유형이다. 안에 있는 요소도 모두 값 유형이어야 한다.
    • 소멸되면 그 안의 요소들도 모두 소멸된다.

항목 TArray TSet TMap TMultiMap
구현 방식 동적 배열 해시 테이블 해시 테이블 해시 테이블
저장 방식 연속 저장 이빠진 배열
삽입 시 중간에
빈 공간으로 들어간다.
(순서 보장 X)		 이빠진 배열
삽입 시 중간에
빈 공간으로 들어간다.
(순서 보장 X)		 이빠진 배열
삽입 시 중간에
빈 공간으로 들어간다.
(순서 보장 X)
접근 방식 Via Index Via Key Via Key Via Key
중간 삽입 시
원소 밀어냄		 O X X X
중복 가능 O X
(새 값으로 대체됨)		 X
(새 값으로 대체됨)		 O
자동 정렬 X X X X
이럴 때 사용하자! 고속 순회
랜덤 접근		 빠른 중복 감지 중복 없이
Key, Value로 관리		 중복 있게
Key, Value로 관리

  • 시간 복잡도는 다음과 같다.
항목 TArray TSet, TMap, TMultiMap
접근 $O(1)$ $O(1)$
검색 $O(N)$ $O(1)$
삽입 $O(N)$ $O(1)$
삭제 $O(N)$ $O(1)$



TArray와 슬랙 #

  • 매번 재할당하는 것을 피하기 위해서 얼로케이터는 요청한 것보다 넉넉한 메모리를 마련한다.
  • 그리고 엘리먼트를 삭제한다고 해서 메모리가 해제되진 않는다. 따라서 배열에 슬랙(slack: 여유분)이 남게 된다.
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

  • Empty()
    • 슬랙 인수를 받아서 해당 개수만큼 슬랙을 만든다.
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

  • Reset()
    • 슬랙 인수를 받아서 해당 개수만큼 슬랙을 만드는데,
    • 요청된 슬랙이 현재 할당으로 충분한 경우 메모리를 해제하지 않는다.
SlackArray.Reset(0);
// SlackArray.GetSlack() == 3
// SlackArray.Num()      == 0
// SlackArray.Max()      == 3

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

  • Shrink()
    • 모든 슬랙을 제거해서 현재 엘리먼트 저장에 필요한 최소 크기로 할당을 조정한다.
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



TSet, TMap은 이빠진 배열 #

  • TSet과 TMap은 이빨이 빠져 있다. 그래서 데이터가 추가되면 그 빈 공간으로 들어가므로, 엘리먼트들의 순서를 보장할 수가 없다.

  • TSet에 원소를 넣고 몇 개를 빼보자.
TSet<int32> Int32Set;
for (int32 ix = 1; ix <= ArrayNum; ++ix)
{
    Int32Set.Add(ix); // 1 ~ 10을 채워넣는다. 
}

// 짝수를 모두 제거한다. 
Int32Set.Remove(2); 
Int32Set.Remove(4);
Int32Set.Remove(6);
Int32Set.Remove(8);
Int32Set.Remove(10);

  • 보여지는 것은 5개의 엘리먼트이지만, 안에 들어가보면 Invalid들이 있다는 것을 알 수 있다. (이빨이 빠져있다)
  • 실제 메모리는 처음 할당한 그대로 10개를 차지하고 있다.

짝수 원소를 제거한 후 디버깅 결과


  • 짝수를 다시 넣으면?
// 짝수를 다시 넣는다. 
Int32Set.Add(2);  
Int32Set.Add(4);
Int32Set.Add(6);
Int32Set.Add(8);
Int32Set.Add(10);

  • 채워 넣을 때는 가장 마지막에 빠진 곳부터 채워진다.
    • 10 을 가장 마지막에 뺐으므로 10 이 있던 공간(9번 인덱스)부터 채워진다. (순서를 보장할 수 없다)

짝수 원소를 다시 넣은 후 디버깅 결과



TSet, TMap에 커스텀 Key를 사용하는 방법 #

  • 예를 들어, 커스텀 구조체를 Key로 사용하고 싶다고 하자.
struct FMyStruct
{
    // 고유한 Key이다.  
    FString UniqueID;

    // 이것은 중복될 수 있는 값이다. 이건 Key의 고유성을 판별하는 데 필요없는 값이다. 
    float SomeFloat;

    explicit FMyStruct(float InFloat) : UniqueID (FGuid::NewGuid().ToString()), SomeFloat(InFloat)
    {
    }
};

  • 커스텀 구조체는 고유성을 판별하기 위한 opreator==() 와 GetTypeHash()가 없으므로, 컴파일 에러가 발생한다. 따라서 추가해주어야 Key로 사용할 수 있다.
struct FMyStruct
{
//...

    // (1) 
    bool operator==(const FMyStruct& InOther) const 
    {
        return UniqueID == InOther.UniqueID;
    }

    // (2) 
    friend FORCEINLINE uint32 GetTypeHash(const FMyStruct& InData)
    {
        return GetTypeHash(InData.UniqueID);
    }
};

  • 하지만 이런 함수를 만드는 것이 바람직하지 않은 경우에는 별도의 커스텀 KeyFuncs 를 제공하면 된다.
template <typename ValueType>
struct TMyStructMapKeyFuncs : BaseKeyFuncs<TPair<FMyStruct, ValueType>, FString>
{
private:
    typedef BaseKeyFuncs<TPair<FMyStruct, ValueType>, FString> Super;

public:
    // (1) 키 전달에 사용
    typedef typename Super::KeyInitType     KeyInitType;
    // (2) 엘리먼트 전달에 사용
    typedef typename Super::ElementInitType ElementInitType;

    // (3) 엘리먼트의 키를 반환
    static KeyInitType GetSetKey(ElementInitType Element)
    {
        return Element.Key.UniqueID;
    }

    // (4) A 와 B 가 동일하면 true, 아니면 false 를 반환
    static bool Matches(KeyInitType A, KeyInitType B)
    {
        return A.Compare(B, ESearchCase::CaseSensitive) == 0;
    }

    // (5) 키의 해시 값을 반환
    static uint32 GetKeyHash(KeyInitType Key)
    {
        return FCrc::StrCrc32(*Key);
    }
};



STL과의 차이점 #

  • TArray의 경우 STL의 vector 와 동작 원리가 유사하다.

  • 반면 TSet, TMap은 STL의 set, map과 차이점이 있다.
항목 set, map TSet, TMap
구현 방식 이진 트리 해시 테이블
저장 방식 불연속 저장
순회에 적합하지 않음		 동적 배열 형태 (모여 있다)
빠르게 순회 가능
중복 가능 X
(첫 값만 유지)		 X
(새 값으로 대체됨)
자동 정렬 O
(삭제 시 재구축이 일어남)		 X
(재구축 없음)
비어 있는 데이터 없음 있을 수 있음



References #



↑