STL의 경우 Vector, Set, Map에 해당하는 3가지 자료구조에 대해 알아볼 것이다.
언리얼 엔진에서 std::vector는 TArray, std::set은 TSet, std::map은 TMap이다.
먼저, 시간 복잡도에 알아보자.
| 원소 접근 | 탐색 | 삽입 | 삭제 | |
| TArray | O(1) | O(n) | O(n) | O(n) |
| TSet | O(1) | O(1) | O(1) | O(1) |
| TMap | O(1) | O(1) | O(1) | O(1) |
신기하게도, 거의 모든 시간복잡도가 O(1)이다.
STL의 경우 Set과 Map의 탐색 시간복잡도는 O(logN) 이다.
어떻게 이럴 수 있는지 간단히 알아보자.
먼저, TArray의 경우는 std::vector와 거의 동일하다.
배열 기반의 자료구조이며, 인덱스로 접근이 가능하다. 메모리에 연속적으로 위치하기 때문에 캐시적중률이 높으며, 삽입과 삭제는 다소 긴 연산을 하게된다.
TSet과 TMap은 STL과 많이 다르다.
차이점을 알아보자.
std::set, std::map
- 포인터, 노드 기반의 자료구조
- 데이터가 삽입, 삭제될 때마다 정렬 진행
- 데이터의 개수만큼 메모리가 할당
TSet, TMap
- 배열, 해시테이블 기반의 자료구조
- 데이터를 정렬하지 않음
- 배열 형태이기 때문에, 데이터의 개수보다 많은 메모리를 할당
먼저, 첫번째 차이점을 알아보자.
std::set과 std::map은 포인터, 노드 기반의 자료구조이다. 그렇기 때문에, 배열 기반의 자료구조보다 낮은 캐시적중률을 보유하고 있다. 동일한 시간복잡도를 가진 연산을 하더라도 배열기반의 자료구조보다 더 느릴 수 밖에 없다.
반면, TSet과 TMap은 그러한 성능 차이를 극복하기 위해, 배열 형태로 구성되어있다. 메모리를 연속적으로 붙임으로써 높은 캐시적중률을 갖게 된다.
또한, TSet과 TMap은 해시테이블을 기반으로 데이터를 보관하게 된다.
해시테이블이란, 데이터를 암호화하여 빠르게 접근하기 위한 것이다.
예를들어, "ABCDEFG"라는 key를 가진 데이터를 std::set에 넣는다고 한다면, key를 탐색할 때마다 문자열의 길이만큼 반복문을 돌며 검사를 해야한다. 이는 문자열의 길이가 길어질수록 더 많은 연산을 요구할 것이다.
하지만, ABCDEFG 를 1이라는 숫자로 대체할 수 있다면?
길이가 몇이든지 단 1번의 비교연산으로 key를 찾을 수 있다.
이 것이 해시테이블이다. 데이터를 암호화하여 단순한 형태로 만들어 탐색을 쉽게 하는 것이다. TSet과 TMap은 해시테이블 형태로 구성되어, 빠른 key탐색과 접근을 허용한다고 한다.
두 번째 차이점
std::set과 std::map은 데이터가 삽입, 삭제될 때마다 자동 정렬을 하며 재구축을 진행한다. 이로 인해, 오버헤드가 발생할 수 밖에 없는데 TSet과 TMap은 정렬을 진행하지 않는다. (중복 검사는 진행한다.)
정렬을 하지 않기 떄문에, 당연히 삽입, 삭제 연산이 std::map, std::set에 비해 빠를 수 밖에 없다.
만약 정렬을 원한다면, 멤버함수 sort를 사용하면 된다.
세 번째 차이점
이 것은 TSet,TMap의 단점이라고도 할 수 있는데, 얘네는 배열 기반이기 때문에 데이터를 삭제한다고 해서 메모리를 해제하지는 않는다. 즉, 비어있는 메모리로 남아있는 것이다.
TSet, TMap은 TArray와 다르게 중간에서 데이터가 삭제된다고 하더라도 앞으로 땡기거나 하지 않는다. 그냥 비어있는 채로 냅둔다. 이 비어있는 공간을 슬랙이라고 한다.
물론 언리얼 엔진에선 이 슬랙을 제거하는 방법도 제공해주고 있다.
멤버함수 Shrink를 사용하면 된다. 이는 TArray에도 사용할 수 있다.
배열의 뒤쪽에 남아있는 빈 공간을 모두 제거해서 배열과 메모리 크기를 딱 맞춰준다.
하지만, Shrink는 끝에 있는 슬랙만 제거하기 때문에 중간에 비어있는 놈은 해결할 수 없다.
중간에 있는 슬랙까지 해결하고 싶다면 Compact(), CompactStable() 함수를 사용하면 된다.
Compact()는 슬랙을 지우는 과정에서 순서가 보장되지 않는 함수고, CompactStable()은 순서를 보장한 상태로 슬랙을 지우는 함수이다.
이 두 함수로 중간에 있는 슬랙을 해결한 뒤, Shrink함수를 사용하면 완벽하게 데이터의 개수와 메모리의 크기가 일치하게 되어 내부 단편화를 해결할 수 있다.
언리얼 엔진의 자료구조에 대해 알아보았다. 막상 사용해보면 STL과 다른 점이 꽤 많기 때문에 직접 사용해보며 익혀보는게 좋을 것이다.