[UE/Basic] 자료구조 - TSet

1. 개요

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

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

 

2. 자료구조의 선택

자료구조를 공부할 때

어떤 것들을 고려하면 좋을지 다시 한 번 살펴보자.

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

 

2.1 TSet 자료구조의 형태

[UE] 언리얼 C++의 TArray, TSet, TMap 자료구조 라이브러리와 활용방법 (참고)

 

TSet은 연속된 저장공간을 가진다.

• 연속된 저장공간은 임의 접근이 가능하다. 
• 즉, 임의 접근이 가능하며 빠르게 데이터를 가져올 수 있다.
• TArray와 다른 점은 중간에 데이터가 비어 있을 수 있다.

 

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

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

 

TSet은 중복된 데이터를 저장할 수 없다.

• TArray는 중복된 데이터를 저장할 수 있지만 TSet은 불가능하다.
• 데이터가 유일성을 보장하기에 TArray보다 검색, 삭제, 삽입 속도가 빠르다는 장점을 가진다

 

2.2 TSet 데이터 추가

www.scholarhat.com 참고

 

TSet은 추가시 Key로 사용한다.

• 데이터가 추가되면 데이터를 해시화하여 인덱스를 얻는다.
• 얻어진 인덱스로 연속된 저장공간에 접근하여 데이터를 저장한다.

 

TSet의 데이터 추가는 O(1) 시간복잡도를 가진다.

• 해시 함수를 통해 인덱스를 구하고 해당 저장공간에 저장하게 된다.
• 대신 언제나 O(1)을 보장하진 않으며 충돌 비용이 발생할 수 있다.

 

2.3 TSet 데이터 삭제

TSet은 삭제시 Key로 사용한다.

• 추가와 동일하게 작동한다.
• 삭제할 데이터를 전달받으면 해시 함수를 통해 인덱스를 구하고 해당 저장공간을 비우게 된다.

 

TSet의 데이터 삭제는 O(1) 시간복잡도를 가진다.

• 이또한 충돌 비용이 발생할 수 있다.

 

2.4 TSet 순회

TSet은 연속된 저장공간을 가짐으로 순회가 가능하다.

• 대신 중간 중간 빈 공간이 존재하여 TArray에 비해 순회 속도는 느리다.

 

2.5 TSet 검색

TSet의 데이터 검색은 추가, 삭제와 동일하게 O(1) 시간복잡도를 가진다.

 

2.6 TSet 데이터 중복 여부

TSet은 중복된 데이터를 허용하지 않는다.

 

3. 정리

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

TSet은 Key를 사용하며 빠르게 저장공간에 접근한다.

TSet의 장점은 중복을 허용하지 않으며 삭제,추가,검색시 빠른 속도를 가진다.

TSet의 단점은 순회 속도는 TArray보다 낮으며, 임의 접근을 활용하기 어렵다.

 

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

버프 또는 디버프를 중첩없이 한 번만 적용하고자 할 때 빠른 검색이 가능할 것 같다.

 

 

참고

[UE] 언리얼 C++의 TArray, TSet, TMap 자료구조 라이브러리와 활용방법

Hash Table in Data Structures