[UE/Basic] 자료구조 - TArray

1. 개요

오늘은 언리얼 컨테이너 라이브러리(Unreal Container Library)에서 제공하는

TArray 자료구조에 대해 살펴보고자 한다.

 

2. 자료구조의 선택

개발 시 데이터 저장하기 위해 어떤 자료구조를 사용할 지 고민을 해야한다.

자료구조를 공부한다는 것은 이러한 고민의 시간을 줄이기 위함이며

어떤 것들을 고려하며 살펴보면 좋을지 살펴보자.

• 자료구조의 형태
• 데이터 추가 비용
• 삭제 비용
• 순회 비용
• 검색 비용
• 임의 접근 여부
• 데이터 중복 여부

 

2.1 TArray 자료구조의 형태

TArray 배열은 연속된 저장공간을 가진다.

• 연속된 저장공간은 인덱스 접근이 가능하다.
• 즉, 임의 접근이 가능하며 빠르게 데이터를 가져올 수 있다.

 

TArray 배열은 동적 가변 배열을 가진다.

• 힙영역에 할당되며 데이터 추가시 길이가 변경된다.

 

2.2 TArray 데이터 추가

데이터 추가는 3가지로 나눌 수 있다. 

• 처음 추가
• 중간 추가
• 마지막 추가

 

TArray 배열의 첫 부분 데이터 추가

• 앞에 데이터 추가 후, 뒤의 값들은 모두 한칸씩 밀려나게 된다.
• O(n) 시간 복잡도를 가진다.

 

TArray 배열의 중간 부분 데이터 추가

• 중간에 데이터 추가 후, 뒤의 값들은 모두 한칸씩 밀려나게 된다.
• O(n) 시간 복잡도를 가진다.

 

TArray 배열의 마지막 부분 데이터 추가

• 뒤에 데이터를 추가한다. 밀려나는 데이터가 없다.
• O(1) 시간 복잡도를 가진다.
• 하지만 가변 길이 배열로 용량이 부족하여 추가가 안될 경우 복사 비용이 발생할 수 있다. (시간 복잡도 O(n))

 

정리하면 TArray 배열은 처음(n), 중간(n), 마지막(1) 효율이 나는 것을 알 수 있다.

 

2.3 TArray 데이터 삭제

데이터 삭제도 3가지로 처음, 중간, 마지막으로 나눌 수 있다.

추가와 동일하게 데이터가 삭제시 그 빈칸을 채우기 위해 모든 값들이 앞으로 한칸씩 당겨지게 된다.

 

정리하면 TArray 배열은 처음(n), 중간(n), 마지막(1) 효율이 난다.

 

2.4 TArray 순회

순회는 저장공간의 모든 요소를 살펴보는 것을 말한다.

예를 들어 게임 속에서 인벤토리 창을 켰을 때 모든 아이템 정보를 표시할 수 있어야 한다. 이 때 순회가 이루어진다.

 

TArray 배열은 연속된 저장공간을 가지고 있다.

그러므로 자료구조 중 TArray는 가장 빠른 순회 속도를 가진다.

 

2.5 TArray 검색

검색은 저장공간에서 특정 요소와 일치하는 요소를 찾아내는 것이다.

TArray 배열은 기본적으로 정렬이 되어 있지 않으며

특정 요소를 찾기 위해 모든 요소를 순차적으로 살펴봐야 한다.

 

그러므로 TArray 배열은 검색에 있어 O(n) 시간 복잡도를 가진다.

 

2.6 TArray 데이터 중복 여부

TArray는 데이터 중복을 허용한다.

저장공간 안에 동일한 데이터를 여러개 저장할 수 있다.

 

데이터 중복이 중요한 이유는

단순히 동일한 값이 더 저장될지 아닐지도 있지만

중복이 되지 않음으로써 유일성을 보장하고 그것을 특정 데이터를 빠르게 찾는 키로 사용될 수 있다.

이는 다음에 얘기할 TSet에서 다시 살펴보자.

  

 

3. 정리

TArray는 연속된 저장공간을 가진 동적 가변 배열이다.

TArray의 장점은 빠른 임의 접근, 빠른 순회를 가진다.

TArray의 단점은 삽입, 삭제, 검색 비용이 높다.

 

게임 구현시 활용될 부분을 생각해보면

빠른 순회 장점을 살린 퀘스트 목록 조회, 인벤토리 아이템 목록 조회가 떠오른다. 

 

 

참고

[UE] 언리얼 C++의 TArray, TSet, TMap 자료구조 라이브러리와 활용방법
[자료구조] Array 와 LinkedList의 차이 — 카멜레온 개발자 이야기