std::map과 TMap

C++ 프로그래밍에서 키-값 쌍을 저장하는 연관 컨테이너는 데이터를 효율적으로 관리하고 검색하는 데 필수적입니다. C++ 표준 라이브러리는 std::map을 제공하며, 언리얼 엔진(UE5)은 자체적으로 최적화된 TMap이라는 컨테이너를 제공합니다. 두 컨테이너는 비슷한 목적을 가지지만, 내부 구현 방식, 성능 특성, 그리고 사용되는 생태계에 따라 중요한 차이점을 보입니다.

---

1. C++ std::map

std::map은 C++ 표준 템플릿 라이브러리(STL)의 일부로, 키와 값을 연관시켜 저장하는 컨테이너입니다.

1.1. 내부 구조: 레드-블랙 트리 (Red-Black Tree)

std::map은 대부분의 표준 라이브러리 구현에서 레드-블랙 트리(Red-Black Tree)라는 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)를 기반으로 구현됩니다.

• 이진 탐색 트리 (BST): 각 노드는 키-값 쌍을 가지며, 왼쪽 서브트리의 모든 키는 현재 노드의 키보다 작고, 오른쪽 서브트리의 모든 키는 현재 노드의 키보다 큽니다. 이 구조 덕분에 키를 기준으로 데이터가 항상 정렬된 상태로 유지됩니다.
• 자가 균형 (Self-Balancing): 데이터의 삽입 및 삭제 시 트리가 한쪽으로 치우쳐져 성능이 저하되는 것을 방지하기 위해, std::map은 레드-블랙 트리의 규칙에 따라 스스로 균형을 맞춥니다. 이 규칙들은 트리의 높이가 log N (N은 요소의 개수)에 비례하도록 보장하여, 주요 연산의 시간 복잡도를 예측 가능하게 만듭니다.
• 노드 기반 메모리 할당: 각 키-값 쌍은 개별적인 노드 객체로 동적 할당됩니다. 각 노드는 키, 값, 그리고 부모/자식 노드를 가리키는 포인터, 색상 정보(Red/Black) 등을 포함합니다. 이로 인해 데이터가 메모리 상에 흩어져 존재하게 되어 캐시 지역성(cache locality)이 떨어지는 원인이 될 수 있습니다.

1.2. 계층 구조 및 동작 방식

1. 사용자 코드 계층: myMap[key] = value;와 같은 코드를 작성합니다.
2. C++ 표준 라이브러리 계층:
   • operator[]는 먼저 key를 사용하여 트리를 탐색합니다.
   • 키가 존재하지 않으면, 새로운 노드를 동적 할당(new)하여 생성하고, 키와 기본 생성된 값을 저장한 후 트리에 삽입합니다. 삽입 후에는 레드-블랙 트리의 규칙에 따라 필요시 트리 회전(rotation)과 색상 변경(re-coloring)을 통해 균형을 다시 맞춥니다.
   • 키가 존재하면 해당 노드를 찾아 값을 업데이트합니다.
3. 메모리 관리 계층: new 연산자는 운영체제의 시스템 콜을 통해 힙(Heap) 메모리 공간을 요청하고, 할당된 메모리 주소를 반환합니다.
4. 하드웨어 계층: CPU는 메모리 주소에 접근하여 데이터를 읽거나 씁니다. 노드들이 비연속적인 메모리에 흩어져 있으므로, 포인터를 따라 다음 노드로 이동할 때마다 캐시 미스(cache miss)가 발생할 확률이 높습니다.

1.3. 성능 특성

• 시간 복잡도:
  • 탐색, 삽입, 삭제: O(log N)을 보장합니다. 트리의 높이가 log N으로 유지되기 때문입니다.
  • 순회: 이터레이터를 통해 모든 요소를 순회하는 데 O(N)이 걸립니다. 순회 시 키의 오름차순으로 정렬된 결과를 얻습니다.
• 장점:
  • 정렬: 키가 항상 정렬되어 있어, 순서가 중요한 데이터 처리에 유리합니다.
  • 예측 가능한 성능: 모든 주요 연산이 최악의 경우에도 O(log N)을 보장하여 실시간 시스템 등에서 안정적인 성능을 제공합니다.
• 단점:
  • 상대적으로 느린 속도: O(log N)은 O(1)보다 느리므로, 순수한 속도 경쟁에서는 해시 테이블 기반 컨테이너에 밀립니다.
  • 캐시 비효율성: 노드 기반 할당으로 인해 데이터가 메모리에 분산되어 캐시 효율이 떨어집니다.
  • 메모리 오버헤드: 각 노드는 키와 값 외에도 포인터와 색상 정보를 위한 추가 메모리를 사용합니다.

---

2. Unreal Engine TMap

TMap은 언리얼 엔진에서 제공하는 C++ 표준의 std::unordered_map과 유사한 해시 테이블 기반의 연관 컨테이너입니다.

2.1. 내부 구조: 해시 테이블 (Hash Table)

TMap은 내부적으로 해시 테이블로 구현됩니다.

• 해싱(Hashing): 키를 GetTypeHash라는 전역 함수를 통해 해시 값(정수)으로 변환합니다. 이 해시 값은 내부 배열(버킷)의 인덱스로 사용됩니다.
• 버킷(Bucket)과 충돌 해결: TMap은 TSparseArray와 유사한 구조를 사용하여 데이터를 저장합니다. 내부적으로는 요소들을 저장하는 연속적인 메모리 블록(TArray)과, 각 요소가 활성 상태인지 여부를 나타내는 비트 배열(TBitArray)을 가집니다. 해시 충돌(서로 다른 키가 같은 해시 값을 갖는 경우)이 발생하면, 해당 버킷에 여러 요소를 연결 리스트(chaining) 형태로 저장하여 해결합니다.
• 연속적인 메모리 할당: TMap의 핵심 데이터 구조는 TArray와 유사하게 연속된 메모리 블록에 데이터를 저장하려고 시도합니다. 이는 CPU 캐시 효율성을 극대화하여 빠른 접근 속도를 제공합니다.

2.2. 계층 구조 및 동작 방식

1. 사용자 코드/블루프린트 계층: C++에서 MyMap.Add(Key, Value); 또는 블루프린트에서 "Add to Map" 노드를 사용합니다.
2. 언리얼 엔진 API 계층:
   • Add 함수는 먼저 GetTypeHash(Key)를 호출하여 키의 해시 값을 계산합니다.
   • 해시 값을 내부 배열의 크기로 나눈 나머지 값을 인덱스로 사용하여 해당 버킷에 접근합니다.
   • 해당 버킷이 비어있으면 바로 데이터를 저장합니다.
   • 충돌이 발생하면, 해당 버킷의 연결 리스트를 순회하며 동일한 키가 있는지 operator==로 비교합니다. 키가 존재하면 값을 업데이트하고, 존재하지 않으면 리스트의 끝에 새로운 요소를 추가합니다.
   • 요소의 개수가 특정 임계값(Load Factor)을 초과하면, 내부 배열을 더 크게 리사이징하고 모든 기존 요소들을 새로운 배열에 다시 해싱하여 재배치(re-hashing)합니다.
3. 언리얼 엔진 메모리 관리 계층: TMap은 언리얼의 메모리 관리 시스템(예: FMemory)을 통해 메모리를 할당받습니다. UPROPERTY() 매크로와 함께 사용될 경우, 가비지 컬렉터(GC)가 TMap에 저장된 UObject 포인터들을 추적하여 자동으로 메모리를 관리해줍니다.
4. 하드웨어 계층: 데이터가 연속된 메모리 공간에 모여있을 확률이 높으므로, 하나의 요소에 접근할 때 인접한 다른 요소들도 함께 CPU 캐시에 로드될 가능성이 큽니다(캐시 히트). 이는 반복적인 접근에서 매우 빠른 성능을 보장합니다.

2.3. 성능 특성

• 시간 복잡도:
  • 탐색, 삽입, 삭제: 평균적으로 O(1) 입니다. 이는 해시 함수가 잘 분포되어 충돌이 적을 때의 이상적인 경우입니다. 최악의 경우(모든 키가 같은 해시 값을 가질 때)에는 O(N)까지 성능이 저하될 수 있습니다.
  • 순회: O(N)이지만, 순회 순서는 예측할 수 없으며 실행할 때마다 달라질 수 있습니다.
• 장점:
  • 매우 빠른 속도: 평균 O(1)의 시간 복잡도는 대량의 데이터를 다룰 때 std::map보다 월등히 빠른 성능을 제공합니다.
  • 캐시 친화적: 연속적인 메모리 구조로 인해 캐시 효율이 매우 높습니다.
  • 언리얼 엔진 생태계 통합:
    • 가비지 컬렉션: UPROPERTY()로 지정 시, TMap이 담고 있는 UObject 포인터들을 GC가 자동으로 관리하여 메모리 누수를 방지합니다.
    • 리플렉션: 엔진의 리플렉션 시스템이 TMap을 인식하여 에디터에 속성을 노출하거나, 직렬화(Serialization), 네트워크 리플리케이션(일부 제한적) 등에 활용할 수 있습니다.
    • 블루프린트 연동: UPROPERTY(EditAnywhere, BlueprintReadWrite) 등으로 블루프린트에 직접 노출하여 비주얼 스크립팅에서 사용할 수 있습니다.
• 단점:
  • 순서 미보장: 데이터가 정렬되어 있지 않아 순서가 중요한 로직에는 부적합합니다.
  • 해시 함수 필요: 키로 사용될 타입은 반드시 GetTypeHash 함수와 operator==를 구현해야 합니다.

---

3. std::map vs TMap 비교 분석

특징	std::map	UE5 TMap
핵심 자료구조	레드-블랙 트리 (균형 이진 탐색 트리)	해시 테이블
데이터 정렬	항상 키 순서로 정렬됨	정렬되지 않음 (순서 보장 없음)
탐색/삽입/삭제	O(log N) (예측 가능)	평균 O(1) (매우 빠름), 최악 O(N)
메모리 할당	노드 기반 비연속적 할당	연속적인 블록 할당 시도
캐시 효율성	낮음	높음 (캐시 친화적)
메모리 오버헤드	노드당 포인터/색상 정보로 인해 오버헤드 큼	상대적으로 오버헤드 적음
UE5 통합	GC, 리플렉션, 블루프린트 미지원	UPROPERTY 통해 완벽 지원
주요 장점	데이터 정렬, 예측 가능한 성능	압도적인 속도, 엔진과의 완벽한 통합
주요 단점	상대적으로 느린 속도, 캐시 비효율	순서 보장 안 됨, 직접적인 네트워크 리플리케이션 제한

언제 무엇을 사용해야 하는가?

• TMap을 사용해야 하는 경우 (99%의 언리얼 프로젝트 상황):
  • 일반적인 게임플레이 로직: 플레이어 ID와 플레이어 정보, 아이템 코드와 아이템 데이터 등, 순서와 상관없이 빠른 조회가 필요한 모든 경우.
  • 언리얼 오브젝트 저장: AActor, UActorComponent 등 UObject 파생 객체를 키나 값으로 저장해야 할 때. GC의 보호를 받을 수 있어 메모리 관리가 매우 안전하고 편리합니다.
  • 블루프린트와의 연동: C++에서 정의한 데이터를 블루프린트에서 사용하거나 수정해야 할 때.
• std::map을 고려할 수 있는 경우 (매우 드문 경우):
  • 정렬된 순회가 반드시 필요한 알고리즘: 순위표(Leaderboard)의 일부 로직처럼 항상 정렬된 상태를 유지하며 데이터를 처리해야 할 때. (하지만 이 경우에도 TArray를 정렬하여 사용하는 것이 더 효율적일 수 있습니다.)
  • 언리얼 엔진에 독립적인 순수 C++ 모듈: 게임 엔진의 기능과 완전히 분리된 라이브러리나 시스템을 개발하며, STL 외의 의존성을 만들고 싶지 않을 때.

결론적으로, 언리얼 엔진 프로젝트를 진행한다면 TMap을 사용하는 것이 좋습니다. std::map은 언리얼 생태계의 핵심 기능(GC, 리플렉션)과 통합되지 않아 메모리 관리 문제를 일으킬 수 있고, 성능 면에서도 대부분의 경우 TMap이 좋기 때문입니다.

---

4. 요약

 std::map과 TMap은 모두 키-값 쌍을 저장하는 컨테이너이지만, 내부 구현 방식과 그로 인한 성능 및 사용 환경에 차이가 있습니다.

 

 std::map은 레드-블랙 트리라는 균형 이진 탐색 트리로 구현되어 있습니다. 이 구조의 가장 큰 특징은 키를 기준으로 데이터가 항상 정렬된 상태로 유지된다는 것입니다. 따라서 탐색, 삽입, 삭제 연산은 모두 O(log N)의 시간 복잡도를 가지며, 성능이 예측 가능하다는 장점이 있습니다. 하지만 각 요소가 개별 노드로 메모리에 흩어져 할당되기 때문에 캐시 효율이 떨어지고, 순수한 속도 면에서는 해시 테이블보다 느립니다.

 반면에 언리얼 엔진의 TMap은 해시 테이블로 구현되어 있습니다. 키를 해싱하여 내부 배열의 인덱스를 계산하므로, 평균적으로 O(1)이라는 매우 빠른 시간 복잡도로 데이터에 접근할 수 있습니다. 또한 데이터를 연속된 메모리 블록에 저장하려는 경향이 있어 캐시 효율성이 매우 높습니다. 하지만 데이터의 정렬 순서는 보장되지 않는다는 특징이 있습니다.

 가장 결정적인 차이는 언리얼 엔진 생태계와의 통합입니다. TMap은 UPROPERTY 매크로를 통해 가비지 컬렉션의 관리를 받고, 리플렉션 시스템에 의해 인식되며, 블루프린트에도 직접 노출할 수 있습니다.