[C++] std::priority_queue

개요

 C++에서는 우선 순위 큐 자료구조를 갖는 컨테이너 어댑터로 표준 라이브러리의 priority_queue를 사용할 수 있습니다.

priority_queue<int, vector<int>, less<int>> qp;

 priority_queue는 queue의 특징과 다르게 선입선출이 아닌 특정 조건에 따른 우선 순위에 따라 데이터가 처리됩니다. std::queue의 주요 특징은 아래 링크에서 자세히 확인할 수 있습니다.

 

[C++] std::queue

---

특징

• 컨테이너 어댑터 (Container Adapter)
  • 우선 순위 큐의 자료구조를 사용하면서 실제로 저장되는 컨테이너 형식을 선택할 수 있습니다.
  • 기본적으로 std::vector를 사용하고, 그 외에도 list 등 다른 컨테이너를 사용할 수도 있습니다.
• 우선 순위에 따른 자동 정렬
  • _Pr 템플릿 매개변수를 이용하여 우선 순위를 결정하는 방식을 선택할 수 있습니다.
  • 내부적으로 힙(Heap) 구조를 사용하여 정렬하며, 기본적으로는 less(내림차순) 정렬 객체를 사용하고, greator(오름차순) 정렬 객체를 사용하거나 사용자가 직접 작성할 수도 있습니다.
  • 요소의 삽입 및 삭제 후 정렬까지 O(log n) 시간 복잡도를 가집니다.
• 임의/순차적인 접근 제한
  • 단방향 구조로 구성되어 우선순위가 가장 높은 요소(top)의 데이터에만 접근할 수 있습니다.
  • 따라서 priority_queue는 iterator를 지원하지 않으며, 컨테이너 내의 모든 요소를 순회하기 어렵습니다.

 

---

헤더

#include <queue>

 priority_queue를 사용하기 위해서 <queue> 헤더를 포함해야 합니다.

 

---

선언 및 초기화

 

템플릿 매개변수

priority_queue<_Ty, _Container = vector<_Ty>, _Pred = less<_Ty>>

 priority_queue는 타입을 선언할 때, 최대 3개의 템플릿 매개변수를 받습니다.

• _Ty은 실제 저장되는 데이터의 형식을 나타냅니다.
• _Container는 우선 순위 큐 자료구조를 사용할 컨테이너를 나타냅니다. 지정하지 않으면 기본적으로 std::vector 컨테이너를 사용합니다.
• _Pred는 데이터를 정렬할 비교 함수 객체를 나타냅니다. 지정하지 않으면 기본적으로 std::less 객체를 사용합니다.

 

---

생성자

priority_queue<_Ty> pq;

 priority_queue를 선언하면 빈 상태의 우선 순위 큐 컨테이너를 선언할 수 있습니다. 추가로 priority_queue는 중괄호를 이용해 컨테이너의 초기 요소 값을 설정할 수 없습니다.

 

컨테이너와 비교 함수 객체 지정

priority_queue<_Ty> pq(_Container, _Pred);

priority_queue의 사용할 컨테이너와 비교 함수 객체를 설정합니다. 컨테이너만 설정할 수도, 비교 함수 객체만 설정할 수도 있습니다.

• _Container는 사용할 컨테이너를 나타냅니다.
• _Pred는 비교 함수 객체를 나타냅니다.

 

iterator 복사

priority_queue<_Ty> pq(_First, _Last);

 다른 컨테이너의 iterator를 이용하여 요소를 복사합니다. _Last 매개 변수 뒤에 컨테이너와 비교 함수 객체를 추가로 설정할 수도 있습니다.

• _First는 복사할 컨테이너의 첫 iterator를 나타냅니다.
• _Last는 복사할 컨테이너의 마지막 iterator를 나타냅니다.

 

priority_queue 복사

priority_queue<_Ty> pq(_Right);

 다른 priority_queue를 복사하여 새로운 priority_queue를 생성합니다.

 

---

주요 함수

 

size()

priority_queue<int> pq; // 컨테이너는 { 6, 5, 4, 3, 2, 1 } 상태라고 가정합니다.
size_t s = pq.size(); // 6을 반환합니다.

 priority_queue의 크기를 반환합니다.

 

---

empty()

priority_queue<int> pq; // 컨테이너는 { 6, 5, 4, 3, 2, 1 } 상태라고 가정합니다.
bool is_empty = pq.empty(); // false를 반환합니다.

 priority_queue가 비어있는지 여부(크기가 0이면 true, 그렇지 않으면 false)를 반환합니다.

 

---

top()

priority_queue<int> pq; // 컨테이너는 { 6, 5, 4, 3, 2, 1 } 상태라고 가정합니다.
int t = pq.top(); // 6을 반환합니다.

 priority_queue에서 우선 순위가 가장 높은(가장 앞에 정렬된) 요소를 반환합니다.

 

---

push()

priority_queue<int> pq; // 컨테이너는 { 6, 5, 4, 3, 2, 1 } 상태라고 가정합니다.
pq.push(7); // 컨테이너는 { 7, 6, 5, 4, 3, 2, 1 } 상태입니다.

 priority_queue에 요소를 추가하고 정렬 조건에 따라 정렬합니다.

 

---

pop()

priority_queue<int> pq; // 컨테이너는 { 6, 5, 4, 3, 2, 1 } 상태라고 가정합니다.
pq.pop(); // 컨테이너는 { 5, 4, 3, 2, 1 } 상태입니다.

 priority_queue에서 우선 순위가 가장 높은(가장 앞에 정렬된) 요소를 제거합니다.

 

---

swap()

priority_queue<int> pq1; // 컨테이너는 {  6,  5,  4,  3,  2,  1 } 상태라고 가정합니다.
priority_queue<int> pq2; // 컨테이너는 { 66, 55, 44, 33, 22, 11 } 상태라고 가정합니다.
pq1.swap(pq2);
// pq1 컨테이너는 { 66, 55, 44, 33, 22, 11 } 상태입니다.
// pq2 컨테이너는 {  6,  5,  4,  3,  2,  1 } 상태입니다.

priority_queue의 모든 요소를 교환합니다.