[C++] priority_queue container 정리 및 사용법

• 안녕하세요 BlockDMask 입니다.

• 오늘은 Container Adapter (stack, queue, priority_queue) 중 

• 마지막 priority_queue 에 대해 정리해보겠습니다.

0. priority_queue container

• 우선순위 큐를 구현한 것 입니다.
  
  

• priority_queue container 는 vector, deque container 와 붙어서 사용이 가능합니다. (list 불가능)
  
  

• 내부적으로는 <algorithm>에 있는 힙 관련 함수들을 사용하여 구현되어있습니다.
  
  

• 내부구조 default 는 vector container 기반으로 설정되어 있습니다.
  
  

• 정렬기준 default는 내림차순(less<>) 기반으로 설정 되어있습니다.

1. priority_queue container 사용법

• <queue> 헤더파일 안에 있습니다.
  

• using namespace std; 이름공간을 사용하면 편리합니다.

2. priority_queue container 생성자와 연산자

• 템플릿 선언 부분을 보겠습니다.
  
  template < typename T,
                  typename Container = vector<T>,
                  typename Compare = less<typename Container::velue_type> >
  class priority_queue;
  
  

• 기본 생성자 형식 priority_queue < [Data Type] > [변수이름];
  ex) priority_queue<int> pq;
  
  

• 내부 컨테이너 변경 priority_queue < [Data Type], [Container Type] > [변수이름];
  ex) priority_queue<int, deque<int> > pq;
  
  

• 정렬 기준 변경 priority_queue < [Data Type], [Container Type], [정렬기준] > [변수이름];
  ex) priority_queue<int , vector<int>, greater<int> > pq;

3. priority_queue container 멤버 함수

• bool empty() const;
  - check whether container is empty.
  - 비어있으면 true 반환
  - 비어있다는 것은 size가 0 이기도함.
  
  

• size_type size() const;
  - return size
  - 원소의 개수를 반환합니다.
  
  

• const value_type& top() const;
  - access top element
  - 맨 위에있는 원소를 참조 및 반환 합니다.(삭제하는거 아님)
  

• void push (const value_type& val);
  - insert element
  - 인자를 삽입합니다. 내부적으로는 push_back 함수를 이용하여 삽입이 됩니다.
  
  

• void pop();
  - remove top element
  - 맨위에있는 인자를 삭제합니다.
  - 내부적으로는 pop_heap 알고리즘과 pop_back 함수가 이용되어 우선순위 큐 형태를 유지합니다.
  

• C++ 11 (emplace, swap) 지원

4. priority_queue container 예제

#include<iostream>
#include<queue>
 
using namespace std;
 
int main(void){
    priority_queue<int> pq;
    
    cout << "empty : " << pq.empty() << endl;
    pq.push(20);
 
    cout << "empty : " << pq.empty() << endl;
    cout << "top : " << pq.top() << endl;
 
    pq.push(10);
    cout << "top : " << pq.top() << endl;
 
    pq.push(30);
    cout << "top : " << pq.top() << endl;
 
    pq.push(50);
    pq.push(40);
    cout << "top : " << pq.top() << endl;
    cout << "size : " << pq.size() << endl;
 
    pq.pop();
    cout << "top : " << pq.top() << endl;
 
    while(!pq.empty()){
        cout << pq.top() << endl;
        pq.pop();        
    }
 
    return 0;    
}

• 결과
  

참고 : http://www.cplusplus.com/reference/queue/priority_queue/