본문 바로가기
<개인공부>/[C++]

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

by 사용자 BlockDMask 2017. 8. 4.
반응형
  • 안녕하세요 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 예제


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;    
}
cs
  • 결과

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

반응형

댓글4