언리얼 컨테이너 라이브러리(UCL)

• 언리얼 엔진이 자체 제작해 제공하는 자료구조 라이브러리
• 언리얼 오브젝트를 안정적으로 지원
• 다양한 라이브러리가 있는데 TArray, TMap, TSet이 제일 유용하게 쓰임

STL과 UCL 차이

• STL
  • 범용적
  • 호환성 높음
  • 기능이 많아 컴파일 오래 걸림
• UCL
  • 언리얼 엔진 특화
  • UObject 안정적 지원
  • 가볍고 게임 제작 최적화

TArray

• 가변 배열 자료구조
• STL의 vector와 유사
• 게임 제작에는 가변 배열 자료구조를 효과적으로 활용하는 것이 좋음
  • 데이터가 순차적으로 모여있어 메모리를 효과적으로 사용할 수 있고 캐시 효율이 높음
  • 컴퓨터 사양이 좋이자면서 캐시 지역성으로 인한 성능 향상이 굉장히 중요
  • 임의 데이터 접근이 빠르고 고속으로 요소를 순회하는 것이 가능
• 가변 배열의 단점
  • 중간 요소 추가, 삭제가 비용이 큼
  • 데이터가 많을수록 검색, 삭제, 수정이 느려 빈번하다면 TArray 대신 TSet을 사용하는 것이 좋음

https://docs.unrealengine.com/5.3/ko/array-containers-in-unreal-engine/

• 신속성, 메모리 효율성, 안전성
• 동질성 컨테이너
  • 유형이 같은 엘리먼트만 저장 가능
• 얼로케이터는 꽤 자주 생략되나 기본값은 1 로, 대부분의 경우 적합한 값
• 값 유형
  • TArray 인스턴스를 new 및 delete 로 생성 또는 소멸시키는 것은 좋지 않음
• 다른 TArray 변수에서 TArray 변수를 만들면 그 엘리먼트를 새 변수에 복사하며, 공유되는 상태는 없음

• 보통의 C++ 값 규칙에 따라 복사 및 소멸 가능한 값 유형은 어떤 것이든 가능
• 기본 힙 기반 얼로케이터를 사용

• Init: 채우기
• Add: 밖에서 생성한 인스턴스를 배열에 복사 (또는 이동)
• Emplace: TArray 자체에서 생성
  • 임시 변수를 생성하지 않아 더 효율적
• Append: 한 번에 다수의 객체를 넣음
• AddUnique: 동일하지 않은 엘리먼트만 추가
  • 검색 비용이 있기 때문에 TSet을 쓰는게 더 유용
• Insert: 해당 인덱스에 추가
  • 비용 발생
• SetNum: 배열의 크기 변경
  • 배열의 크기는 Num을 통해서

반복처리

• C++ 의 범위 for 기능을 사용하는 것을 추천
• 인덱스 기반 반복처리 역시도 가능
• 반복처리에 대한 보다 세밀한 제어가 가능하도록 별도의 반복처리 유형가능
  • CreateIterator 및 CreateConstIterator 라는 함수가 두 개 있는데, 각각 엘리먼트에 대한 읽기-쓰기 또는 읽기-전용 접근이 가능한 것

소팅

• Sort
  • 안정적 X
• HeapSort
  • 안정적 X
• StableSort
  • 머지 소트로 구현
  • 순서 유지(안정적)

쿼리

• Num 함수로 배열에 엘리먼트가 몇 개인지 확인 가능
• GetData 함수를 사용해서 배열 내 엘리먼트에 대한 포인터를 반환
  • 인덱스로 개별 요소 접근 가능
• 컨테이너가 const 인 경우, 반환되는 포인터 역시 const
• GetTypeSize로 컨테이너의 엘리먼트의 크기를 알 수 있음
• operator[] 인덱싱을 사용해 원하는 엘리먼트 접근 가능
• IsValidIndex 함수를 통해 인덱스가 유효한지 판단 가능
• operator[] 는 레퍼런스를 반환하므로, 배열이 const 가 아니라는 가정하에 배열 내 엘리먼트 변형 가능
• Top 또는 Last 함수를 사용하여 배열 끝에서부터 역순으로 인덱스를 사용할 수도 있음
• Contains를 통해 배열에 특정 엘리먼트가 들어있는지 알 수 있음
• ContainsByPredicate를 통해 지정된 술부와 일치하는 엘리먼트가 있는지 물어볼 수 있음
  • 세밀한 검색이 가능
• Find로 엘리먼트가 존재하는지 검사해서 있으면 인덱스를 반환 가능
  • 처음으로 찾은 인덱스 반환
  • FindLast 를 통해 마지막 요소의 인덱스 반환 가능
  • 인덱스가 없으면 INDEX_NONE 반환

• 검색 기능은 전체를 순회할 수 있기 때문에 효율이 좋지 않음
  • TSet을 이용하는 것이 나음

제거

• Remove를 통해 입력된 값과 동일한 모든 요소를 제거
• RemoveSingle는 처음 일치한 엘리먼트를 제거
• RemoveAt는 인덱스 접근 제거
  • 유효하지 않은 인덱스를 전달하면 런타임 오류가 발생
• RemoveAll 함수로 술부에 일치하는 모든 엘리먼트를 제거
• 엘리먼트가 제거되는 모든 경우, 그 뒤의 엘리먼트가 낮은 인덱스로 정리되므로, 배열에는 절대 '구멍'이 생길 수 없음
• 정리 프로세스에는 비용 들음
• Empty는 전부 제거

연산자

• 일반적인 생성자 복사나 할당 연산자를 통해 복사
  • emplace가 아닌 add처럼 동작
• Append 함수의 대안으로, operator+= 를 통해 배열 연결 가능
• MoveTemp 함수를 사용해서 부를 수 있는 이동 의미론도 지원
• operator== 나 operator!= 를 사용해서 비교 가능
  • 엘리먼트의 수와 순서가 같을 경우만 true
  • FString은 operator==가 대소 구분이 없어서 같다고 판별 가능

슬랙

• 배열이 추가될 때마다 매번 재할당을 피하기 위해, 얼로케이터는 보통 요청한 것보다 넉넉한 메모리를 제공
• GetSlack, Empty, Reset, Shrink 등 활용

원시 메모리

• AddUninitialized 및 InsertUninitialized 함수는 배열에 초기화되지 않은 공간에 추가
  • Add 와 Insert 처럼 작동은 하지만, 해당 엘리먼트 유형의 생성자를 호출하지는 않음
  • Memcpy 호출로 전체 구조체를 덮어쓰려는 경우처럼 생성자 호출을 피할 때 좋음

TSet

• STL set
  • 이진 트리 -> 자동정렬
  • 메모리 구성 효율 낮음
  • 요소가 삭제될 때 균형을 위한 재구축
  • 자료 순회 적합 x
• 언리얼 TSet
  • 해시테이블 형태로 빠른 검색 가능
  • 동적 배열의 형태로 데이터가 모여있음
  • 빠르게 순회 가능
  • 삭제해도 재구축 x
  • 비어있는 데이터가 있을 수 있음
• STL set과 TSet은 활용 방법이 다르므로 주의
• STL의 unordered_set과 유사하지만 동일하진 않음
• TSet은 중복 없는 데이터 집합을 구축하는데 유용

https://docs.unrealengine.com/5.3/ko/set-containers-in-unreal-engine/

• 데이터 값 자체를 키로 사용하며, 이 때 엘리먼트를 값을 평가하는 오버라이드 가능 함수를 사용
• 엘리먼트 추가, 검색, 제거가 매우 빠름
• 중복 키를 지원하지 않음

• 순서가 중요치 않은 상황에서 고유 엘리먼트를 저장하는 데 사용되는 고속 컨테이너 클래스
• 동질성 컨테이너
• TSet 가 소멸되면 엘리먼트도 같이 소멸되도록 하는 강 오너십도 지원
• 해시를 사용하는데, KeyFuncs 템플릿 파라미터가 제공된 경우, 세트더러 엘리먼트에서 키를 결정하는 방법, 두 키가 같은지 비교하는 방법, 키를 해싱하는 방법, 중복 키 허용 여부 등을 지정할 수 있음
  • 즉, 커스터마이징 가능
• TArray 와는 달리 TSet 엘리먼트의 메모리 내 상대 순서는 신뢰성이 있거나 안정적이지 않음
• 데이터 구조는 sparse array(희소 배열)
• 엘리먼트가 제거되면, 희소 배열에 간극이 생김
  • 추가되는 엘리먼트가 메꿈

Set 생성 및 채우기

• 선언만 하면 빈 Set 생성
• operator== 로 엘리먼트를 직접 비교
• GetTypeHash 로 해싱
  • 기본적인 FString이나 integer, UObject들은 해싱 값들을 가지고 있음
  • 새로운 구조체를 사용해 TSet을 만들고 싶으면 해당 자료형에 대한 GetTypeHash 함수를 만들어줘야 함

• Add를 통해 삽입
• Emplace를 통해 복사 없이 데이터 추가 가능
• Append를 통해 병합 가능

이터레이션

• TArray 동일

쿼리

• TArray와 유사
• 해시 테이블로 구성되어 있어 검색 기능이 빠름
• FSetElementId 구조체를 사용하여 세트 내 키 인덱스를 찾을 수 있음
• Find 는 맵에 키가 있는 경우 엘리먼트 값으로의 포인터를, 없으면 널 포인터를 반환
• Array 함수는 TSet 의 모든 엘리먼트 사본으로 채워진 TArray 를 반환

제거

• 내부 순서를 알기 까다롭기 때문에 인덱스를 이용해서 작업하는 것은 비추천
• 엘리먼트 제거는 실제로 데이터 구조에 간극을 남길 수 있음

소팅

• 소팅 가능

연산자

• TArray 유사

슬랙

• 데이터를 제거할 때 완전히 제거하는 것이 아니라 비어있는 상태로 놔두기 때문에 <invalid>로 표시
  • 뒷부분에 생기는 슬랙이 있고 중간중간에 생기는 슬랙이 있음
• Shrink 는 컨테이너 끝에서부터 모든 슬랙을 제거하지만, 중간이나 시작 부분의 빈 엘리먼트는 놔둠

TArray vs TSet

	TArray	TSet
접근	O(1)	O(1)
검색	O(N)	O(1)
삽입	O(N)	O(1)
삭제	O(N)	O(1)

• TArray
  • 빈틈없는 메모리
  • 가장 높은 접근성능
  • 가장 높은 순회성능
• TSet
  • 빠른 중복 감지