Set / Unordered Set

Set

정의

• set은 균형 이진 트리(일반적으로 레드-블랙 트리)로 구현된 정렬된 집합이다.

특징

• 정렬된 순서 : 원소들이 자동으로 정렬된 상태로 저장된다.
• 탐색 시간 : 삽입, 삭제 검색 연산의 평균 시간 복잡도는 O(log n)이다.
• 순회 : 원소들을 순회할 때 항상 정렬된 순서로 순회한다.

사용 예

• 데이터가 항상 정렬된 상태로 필요할 때
• 특정 범위의 원소들을 빠르게 찾을 때
• 게임 내 순위 리스트
  • 게임 내에서 플레이어 점수 또는 순위 리스트를 관리할 때, 점수를 정렬된 상태로 유지해야 할 때 사용된다.
  • 자동으로 정렬된 상태로 저장되기 때문에, 순위를 빠르게 검색하거나 특정 범위의 순위를 쉽게 추출할 수 있다.
• 퀘스트 트래킹
  • 플레이어가 완료한 퀘스트를 추적하고, 완료한 순서대로 정렬하여 저장할 대 유용하다.
  • 완료한 퀘스트를 정렬된 상태로 저장하여, 다음 퀘스트 진행을 쉽게 파악할 수 있다.
• 이벤트 스케줄링
  • 게임 내 이벤트나 타이머를 관리할 때, 이벤트 발생 시간을 기준으로 정렬된 리스트를 유지해야 할 때 사용된다.
  • 이벤트 발생 시간을 기준으로 자동 정렬되어, 다음 이벤트를 빠르게 확인하고 처리할 수 있다.

Unordered_Set

정의

• unordered_set은 해시 테이블로 구현된 집합이다.

특징

• 정렬되지 않은 순서 : 원소들이 특정 순서 없이 저장된다.
• 탐색 시간 : 삽입, 삭제, 검색 연산의 평균 시간 복잡도는 O(1)이다.
• 순회 : 원소들을 순회할 때 순서가 정렬되지 않는다.

사용 예

• 원소들의 순서가 중요하지 않고, 빠른 삽입, 삭제, 검색이 필요할 때
• 충돌 감지
  • 게임 내에서 충돌 감지를 할 때, 충돌 대상 오브젝트의 ID를 빠르게 검색해야 할 경우 유용하다.
  • 해시 테이블 기반이므로 충돌 대상 오브젝트를 빠르게 확인할 수 있다.
• 상태 추적
  • 플레이어 상태나 오브젝트 상태를 추적할 때, 특정 상태가 존재하는지 여부를 빠르게 확인해야 할 때 사용된다.
  • 상태 변경 시 빠르게 삽입 및 삭제할 수 있으며, 현재 상태를 O(1) 시간 복잡도로 확인할 수 있다.
• 아이템 인벤토리
  • 플레이어의 인벤토리에서 아이템의 고유 ID를 관리할 때 유용하다.
  • 특정 아이템의 존재 여부를 빠르게 확인하고, 인벤토리에 아이템을 추가하거나 제거할 때 효율적이다.
• 유니크 엔티티 관리
  • 게임 내에서 유일해야 하는 엔티티를 관리할 때 사용된다.
  • 유니크한 엔티티를 빠르게 추가, 삭제, 검색할 수 있어 게임 로직을 효율적으로 관리할 수 있다.