C++ STL priority queue 사용법

[priority queue] 기본 요소

헤더 < queue > 에 저장되어 있다. 다음은 priority queue의 템플릿 구조이다.

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

• 먼저 T 는 저장되어야할 요소의 타입이다. 또한 Container에서 지정한 타입과 일치하지않으면 동작 하지 않는다. ex) int
• 다음으로 Container 요소를 저장 컨테이너의 유형이다. 이는 sequenceContainer를 만족해야 하며, front(), push_back(), pop_back() 의 기능을 가져야 한다. ex) vector
• 마지막으로 Compare 는 정렬을 위해 사용된다. default 로 less 이 지정되어 있어, 내림차순으로 정렬된다. 사용자가 원하는 정렬을 위해 따로만들어 지정하거나 greater같은 제공 비교 연산자를 사용하면된다. ex) greater<>

멤버함수

• construtor 와, destructor를 제공하며
• operator = 할당자함수도 제공한다.

요소 접근방법

• top -> queue의 탑의 요소에 접근할 수 있다. 변수.top();

Capacity

• empty -> 컨테이너가 비어있는지 확인가능하다.
• size -> 컨테이너의 사이즈를 확인가능하다.

수정

• push -> 컨테이너의 요소를 추가하기 위해 사용된다.
• emplace -> 요소를 구성하고, 원래로 정렬한다.
• pop -> top 위치의 요소를 제거한다.
• swap -> 요소들을 바꾼다.

Examples

#include <functional>
#include <queue>
#include <vector>
#include <iostream>

// pq 출력   
template<typename T>
void print_queue(T q) { // NB: pass by value so the print uses a copy
    while(!q.empty()) {
        std::cout << q.top() << ' ';
        q.pop();
    }
    std::cout << '\n';
}

int main() {
    std::priority_queue<int> q;

    const auto data = {1,8,5,6,3,4,0,9,7,2};
    // push 를 이용해 q에 데이터 삽입.
    for(int n : data)
        q.push(n);

    print_queue(q);
    // q2를 data를 데이터로 가지며 오름차순이고 벡터 컨테이너를 가진 pq로 선언.  
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        q2(data.begin(), data.end());

    print_queue(q2);

    // Using lambda to compare elements.
    // 람다를 사용하여 비교연산자를 설정한다.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);

    for(int n : data)
        q3.push(n);

    print_queue(q3);
}

Output:

9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
8 9 6 7 4 5 2 3 0 1

자세한 내용은 아래의 레퍼런스 참조 하세용
click reference site