1. priority_queue
-
항상 정렬을 유지하는 벡터
-
binary heap 구조를 차용하여, 원소의 삽입 / 삭제에 걸리는 시간 복잡도는 O(logN)
-
삭제는
pop()을 통해 맨 앞에 있는 원소만 삭제 가능 -
삽입 시에는 마지막에 원소를 추가하고, bottom-up의 heapify를 통해 정렬
-
삭제 시에는 마지막 원소를 root로 옮기고, top-down의 heapify를 통해 정렬
2. multiset
-
set과 비슷하나 같은 원소를 중복으로 가질 수 있는 자료구조 -
set과 동일하게, 레드블랙트리 구조를 사용하여 정렬 -
삽입에는 O(logN), 삭제는 반복자를 사용할 경우 거의 상수시간으로 가능
-
값으로 삭제할 경우, 탐색해야하므로 O(logN)
3. priority_queue vs multiset
캐시 성능
-
priority_queue는 내부적으로 벡터 자료구조를 사용하기 때문에 캐시 성능면에서 훨씬 뛰어나다 -
multiset은 레드블랙트리의 노드가 메모리에 띄엄띄엄 존재하므로 캐시 성능이 좋지 않다
삽입 / 삭제
-
삽입 / 삭제 시
priority_queue는 인덱스를 통한 부모 / 자식간의 값만 비교하므로 간단한 로직 -
multiset의 경우 트리 균형을 맞추기 위한 색변경 / 회전 등이 일어나 복잡한 로직. 추가로 메모리 할당 / 해제가 빈번히 일어난다
인덱스
-
priority_queue는 내부적으론 벡터 자료구조이지만, 인덱스 접근이 불가능하며 맨 앞에 있는 원소에만 접근, 삭제가 가능 -
multiset의 경우 반복자를 통해 모든 원소에 순차적 접근 가능하며, 삭제도 모든 원소에 가능 -
따라서
multiset은lower_bound가 가능하지만(내부함수 사용해야함)priority_queue는 불가능
결론
-
정렬된 큐의 성질만이 필요하다면
priority_queue가 성능적으로 훨씬 좋다 -
그 외의 다양한 기능이 필요하다면
multiset이 좋다
4. lower bound
-
입력받은 값 이상의 값이 처음 등장하는 곳의 반복자를 반환한다
-
빠르게 이진탐색하기 위해 정렬된 자료구조에 사용
-
이때, vector와 tree구조(set, map)에서 시간복잡도는 O(logN)으로 동일하나 동작 방식이 다르다
vector
-
algorithm헤더의lower_bound()를 사용 -
인덱스를 통한 접근이 가능하므로,
mid = (low + high) / 2형태의 인덱스 접근을 통해 이진 탐색을 진행 -
당연히 정렬되어 있는 벡터에서 사용해야 함
set / map
-
각 자료구조의 내부함수인
lower_bound()를 사용해야함 -
벡터와 달리 인덱스를 통한 random access가 불가능
-
그러나, 이진 트리구조로 정렬되어 있으므로 root로부터 값을 비교하며 자식으로 내려가면 이진탐색이 가능
