7-2. 언리얼 컨테이너 라이브러리 - TSet

TSet의 특징

• STL의 set과 언리얼 TSet의 비교
  • STL set의 특징
    • STL set은 이진 트리(Red-Black Tree)로 구성되어 있어 정렬을 지원함.
    • STL set은 메모리 구성이 효율적이지 않음.
    • STL set은 요소가 삭제될 때 규형을 위한 재구축이 일어날 수 있음.
    • STL set의 모든 자료를 순회하는데 적합하지 않음.
  • 언리얼 TSet의 특징
    • TSet은 해시 테이블 형태로 키 데이터 구축되어 있어 빠른 검색이 가능함.
    • TSet은 동적 배열의 형태로 데이터가 모여있음
    • TSet의 데이터는 빠르게 순회할 수 있음.
    • TSet의 데이터는 삭제해도 재구축이 일어나지 않음.
    • TSet의 자료에는 비어있는 데이터가 있을 수 있음.
• 따라서 STL set과 언리얼 TSet의 활용 방법은 서로 다르기 때문에 주의할 것.
• STL의 unordered_set과 유사하게 동작하지만, 동일하진 않음.
• TSet은 중복 없는 데이터 집합을 구축하는데 유용하게 사용할 수 있음.

 

https://docs.unrealengine.com/4.27/ko/ProgrammingAndScripting/ProgrammingWithCPP/UnrealArchitecture/TSet/

TSet

TSet문서이다.

드래그한 부분의 이야기는 내부적으로 해시 테이블로 구성이 되어 있고 그 데이터 자체가 키를 가지고 있어서 빠르게 검색할수 있다. 는 이야기다.

해시 테이블이다 보니, 하나의 키만 갖고 있을 수 있다. 또한 검색하는 속도가 빠르다(해시 테이블이면 O(1)이다.)
또한 TSet이 소멸되면 엘리먼드도 같이 소멸되도록 하는 강 오너십도 지원한다.

대부분은 저 문서를 보면 거의 이해가 될것이다.(아마?도?)

 

코드

7-1에서 했던 코드 베이스로 추가해준다.

	TSet<int32> Int32Set;
	for (int32 ix = 1; ix <= ArrayNum; ++ix)
	{
		Int32Set.Add(ix);
	}

	Int32Set.Remove(2);
	Int32Set.Remove(4);
	Int32Set.Remove(6);
	Int32Set.Remove(8);
	Int32Set.Remove(10);
	Int32Set.Add(2);
	Int32Set.Add(4);
	Int32Set.Add(6);
	Int32Set.Add(8);
	Int32Set.Add(10);

그냥 간단하게 1~10까지 넣는 코드만 작성 해준다. 그 후 짝수 삭제 다시 추가 하는 코드이다.
이 상태에서 내부 자료구조는 어떻게 달라지는지 확인 해보자

일단 1~10 넣었을 때이다.

그 다음 짝수를 지우면 보이는건 저렇게 보이지만, Element를 확인해보면

이렇게 각 메모리에서 값이 삭제가 된다.
그 후, 추가를 하면 가장 마지막에 빠진 요소에 대해서 빈틈을 채워 넣는 방식으로 진행이 된다.

 

2를 추가하면

마지막에 넣었던 순서대로 들어간다.

끝에 보면

 

이런 순서대로 들어가게 된다.

자료구조의 시간 복잡도 비교

	TArray	TSet
접근	O(1)	O(1)
검색	O(n)	O(1)
삽입	O(n)	O(1)
삭제	O(n)	O(1)
	빈틈없는 메모리 가장 높은 접근 성능 가장 높은 순회 성능	빠른 중복 감지