[C++] Map vs Set vs Priority Queue

맵과 셋, 우선순위 큐는 항상 헷갈린다. 이번에 확실히 정리해 보자.

Map, multi Map

맵은 기본적으로 레드-블랙 트리를 사용한 자료구조이다. key, value쌍을 가지며 key를 기준으로 오름차순 정렬하여 저장한다. 레드-블랙 트리로 구성되어 있으므로 항상 트리의 높이가 log n을 유지한다. 또, 중복을 허용하지 않고 multi Map만 중복을 허용한다.

맵은 주로 고유한 키와 값을 연결하여 정렬할 필요가 있을 때 사용한다. 또, 모든 값에 대해 빠른 접근과 삽입/삭제를 지원한다.

Set, MultiSet

셋 또한 레드-블랙 트리를 사용한 자료구조이다. value 하나의 값만을 가지며 오름차순 정렬이 디폴트이며 중복을 허용하지 않는다. 

셋은 고유한 값에 대한 정렬된 자료구조가 필요할 때 사용한다. Map과 거의 똑같지만 key-value가 아닌 value만 가지고 있는 것이 차이점이다.

Prioirty Queue

우선순위 큐는 기본적으로 최대 힙으로 구현되어 있다. 중복된 값을 허용하며 가장 높은 우선순위의 원소에 위의 두 자료구조보다 빠른 O(1) 시간에 접근이 가능하다. 삽입, 삭제는 log n이 소모된다.

우선순위 큐는 가장 높은 우선순위의 원소에 가장 빠르게 접근할 수 있다. multi set과 똑같은 기능을 하는 것처럼 보이지만 multi set은 모든 원소에 균등한 접근 속도를 지원한다면 우선순위 큐는 가장 높은 원소에만 굉장히 빠른 속도를 지원한다.