언리얼 C++ - 자료 구조 ~ TMap

https://monstrosite.tistory.com/44

언리얼 C++ - 자료 구조 ~ TSet

TSet에 이은 언리얼 C++의 자료구조 마지막 포스트입니다.

이번 포스트에서는 TMap에 대해 알아보도록 하겠습니다.

 

1) TMap

TMap에는 std::map이 대응됩니다. 

이번에도 std::map과 TMap과의 차이점을 한번 알아보겠습니다.

우선 std::map의 특징을 간단하게 적어보겠습니다.

1. set과 동일하게 이진 트리로 구성됩니다.
2. 정렬은 지원하지만, 이진 트리 기반이기에 메모리 구성이 효율적이지 못합니다.
3. 데이터가 삭제되면 트리의 균형을 맞추기 위해 재구축이 일어날 수 있습니다.
4. 모든 자료를 순회하는데 적합하지 못합니다.

map은 set과 마찬가지로 이진 트리로 구성됩니다. 빠른 검색이 가능하지만 메모리 효율이 좋지 못한 문제가 있습니다.

이번에는 언리얼 엔진에서 제공하는 TMap에 대해 알아보겠습니다.

1. Key - Value 구성의 tuple 데이터 구조로 구현되어 있습니다.
2. 해시 테이블의 형태로 구축되어 빠른 검색이 가능하고 동적 배열의 형태이므로 메모리 구성이 효율적입니다.
3. 동적 배열의 형태로 인해 빠른 순회가 가능하고 데이터를 삭제해도 재구축이 일어나지 않습니다.
4. 데이터가 저장된 데이터 배열에 빈틈이 있을 수 있고 중복이 허용되지 않습니다.
5. 단, 중복이 허용되지 않는 문제는 TMulitiMap을 사용하여 해결이 가능합니다.

TMap은 TSet과 마찬가지로 동적 배열로 구성되어 있습니다.

그러나 이 데이터 배열에 빈틈이 존재할 수 있다는 점을 염두해야 합니다.

 

2) TMap의 특징

TSet은 Key - Value로 구성된 tuple로 데이터를 저장한다고 말씀드렸습니다.

따라서 TMap에서 데이터는 

TPair<KeyType, ValueType>

으로 저장하고

불러올때는 Key만 사용합니다.

 

또한 해시 테이블 기반으로 빠르게 검색이 가능하지만, 

문제는 Key만이 해시 테이블에 저장된다는 것입니다. 

따라서 Key를 통한 조회는 빠르지만 Value를 사용하는 경우는 TArray와 같은 O(N)의 조회가 됩니다.

 

3) TMap의 API

https://dev.epicgames.com/documentation/ko-kr/unreal-engine/map-containers-in-unreal-engine?application_version=5.4

TMap에 관련된 API는 공식문서의 링크로 대체하겠습니다.

이 포스팅에서는 자주 사용하는 API를 간단하게 설명드리겠습니다.

 

1. Add() : Key와 Value를 인자로 받아 추가
2. Emplace() : Add와 동일하지만 복사 비용이 발생하지 않음
3. Num() : 원소의 개수를 리턴
4. Contains() : 키를 인자로 받아 TMap에 키가 있는지 여부를 bool로 리턴
5. [ ] 연산자 : 키가 확실하게 들어가있는 경우 사용, Contains()에 인자로 사용하여 확실하지 않은 경우의 키를 찾음
6. Find() : 5의 경우를 한번의 조회로 해결, 있다면 원소의 포인터를 없다면 nullptr를 리턴
7. Remove() : 키 값을 인자로 받아 원소 삭제
8. Empty() / Reset() : 모든 원소를 삭제

 

4) TMap의 내부구조

 

5) TMap의 시간복잡도

 

TMultiMap은 위의 사진에서 중복 허용으로만 바꿔주면 완전히 일치하는 특징을 갖고 있습니다.

 

6) TMap 사용예시

간단한 예시를 통해 TMap을 사용하는 방법에 대해 알아보겠습니다.

 

 

코드는 위와 같고 실행결과는 다음과 같습니다.

 

 

상수를 사용하기보다는 변수를 사용해야 하지만 편의상 사용하였음을 알아주셨으면 합니다.

TMap은 한쌍으로 이뤄진 데이터를 다룰 때 특히, 유용합니다.

그리고 이렇게 한쌍으로 이뤄진 데이터를 해시값을 통해 빠르게 검색할 수 있습니다.

 

언리얼 엔진에는 많은 자료구조가 존재하지만, 자료구조에 관한 포스트는 이것으로 마지겠습니다.

언리얼 엔진에서 제공하는 자료구조의 이점과 특징을 배우시는데 이 포스트가 도움이 되셨기를 바랍니다.