std::priority_queue

정의:

최대 또는 최소 요소를 상수 시간에 접근할 수 있는 컨테이너 어댑터

대신 삽입과 추출 작업에 로그시간이 걸린다

내부 자료구조로는 heap으로 이루어져 있으며 그렇기에 top에 있는 요소를 참조하여 사용한다

선언:

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

템플릿 인자는 3개가 있다

T:

• 저장되는 요소의 타입

Container:

• 요소를 저장하는 기본 컨테이너 타입

Compare:

• 요소간 비교를 위한 비교자 함수 객체의 타입
• e.g. std::less, std::greater

기능:

Member Objects:

C 컨테이터와 comp 비교 함수 객체로 이름이 정의되어 있음

Member fucntions:

생성자, 소멸자, 대입 연산자로 이루어져 있다

요소 참조:

top - 맨 위의 요소 참조

크기:

empty - 컨테이너가 비어있는지 확인
size - 컨테이너의 요소 개수 반환

수정자:

push - 컨테이너에 따라 요소를 삽입하고 정렬함
push_range - 컨테이너에 따라 요소의 범위를 삽입하고 정렬
emplace - 컨테이너에 따라 요소를 생성하고 정렬
pop - 맨 위의 요소를 제거
swap - 두 우선순위 큐의 객체를 맞바꿈

Non-member functions:

std::swap(std::priority_queue)

Helper classes:

std::uses_allocatorstd::poriority_queue
std::formatterstd::priority_queue

Code e.g.:

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

template<typename T>
void pop_println(std::string_view rem, T& pq)
{
    std::cout << rem << ": ";
    for (; !pq.empty(); pq.pop())
        std::cout << pq.top() << ' ';
    std::cout << '\n';
}

template<typename T>
void println(std::string_view rem, const T& v)
{
    std::cout << rem << ": ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}

int main()
{
    const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};
    println("data", data);

    std::priority_queue<int> max_priority_queue;

    // 우선순위 큐 채우기
    for (int n : data)
        max_priority_queue.push(n);

    pop_println("max_priority_queue", max_priority_queue);

    // std::greater<int> 는 max priority_queue를 만든다
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        min_priority_queue1(data.begin(), data.end());

    pop_println("min_priority_queue1", min_priority_queue1);

    // mini priority_queue 만드는 법
    std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>());

    pop_println("min_priority_queue2", min_priority_queue2);

    // 요소를 비교하기위해 함수 객체를 직접 만들 수 있다
    struct
    {
        bool operator()(const int l, const int r) const { return l > r; }
    } customLess;

    std::priority_queue custom_priority_queue(data.begin(), data.end(), customLess);

    pop_println("custom_priority_queue", custom_priority_queue);

    // compare 요소에 람다식 사용
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> lambda_priority_queue(cmp);

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

    pop_println("lambda_priority_queue", lambda_priority_queue);
}

Output:

data: 1 8 5 6 3 4 0 9 7 2
max_priority_queue: 9 8 7 6 5 4 3 2 1 0
min_priority_queue1: 0 1 2 3 4 5 6 7 8 9
min_priority_queue2: 0 1 2 3 4 5 6 7 8 9
custom_priority_queue: 0 1 2 3 4 5 6 7 8 9
lambda_priority_queue: 8 9 6 7 4 5 2 3 0 1