std::priority_queue

std::priority_queue (우선순위 큐 컨테이너 어댑터)

가장 큰(기본) 원소를 상수 시간에 조회할 수 있는 컨테이너 어댑터예요. 대신 삽입·추출은 로그 시간이에요. 힙(heap) 기반으로 동작해요.

출처: cppreference

본문

<queue> 헤더에 정의돼 있고, 우선순위 큐 컨테이너 어댑터예요.

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

우선순위 큐는 가장 큰(기본) 원소의 상수 시간 조회를 제공하는 컨테이너 어댑터예요. 로그 시간의 삽입·추출 비용이 들어요. 사용자가 제공한 Compare로 순서를 바꿀 수 있는데, 예를 들어 std::greater<T>를 쓰면 top()에 가장 작은 원소가 오게 돼요.

priority_queue로 작업하는 것은 임의 접근 컨테이너에서 힙을 관리하는 것과 비슷하지만, 실수로 힙을 무효화할 수 없다는 이점이 있어요. C++26부터 모든 멤버 함수가 constexpr이에요.

템플릿 매개변수

  • T: 저장된 원소 타입. T가 Container::value_type과 같지 않으면 프로그램은 ill-formed예요.
  • Container: 원소를 저장하는 기본 컨테이너 타입. SequenceContainer 요구사항을 만족하고 그 반복자가 LegacyRandomAccessIterator 요구사항을 만족해야 해요. 또한 front(), push_back(), pop_back()을 제공해야 해요. 표준 컨테이너 std::vector(std::vector<bool> 제외)와 std::deque가 만족해요.
  • Compare: 엄밀 약순서(strict weak ordering)를 제공하는 Compare 타입. 첫 인자가 두 번째 인자보다 약순서에서 앞서면 true를 반환하도록 정의돼요. 다만 priority_queue는 큰 원소를 먼저 출력하므로 "앞서는" 원소가 실제로는 마지막에 출력돼요.

멤버 타입

container_type = Container, value_compare = Compare, value_type = Container::value_type, size_type, reference, const_reference. 보호 멤버 객체: c(기본 컨테이너), comp(비교 함수 객체).

멤버 함수

  • 생성자, 소멸자, operator=.
  • 원소 접근: top.
  • 용량: empty, size.
  • 수정자: push, push_range(C++23), emplace(C++11), pop, swap(C++11).

비멤버 함수 / 헬퍼

  • std::swap(std::priority_queue) (C++11): std::swap 특수화.
  • std::uses_allocator<std::priority_queue> (C++11), std::formatter<std::priority_queue> (C++23).

예제를 보면 최대·최소 우선순위 큐를 만들 수 있어요.

#include <functional>
#include <iostream>
#include <queue>
#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';
}

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

    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> 로 최소 우선순위 큐 만들기
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        min_priority_queue(data.begin(), data.end());
    pop_println("min_priority_queue", min_priority_queue);
}

출력:

max_priority_queue: 9 8 7 6 5 4 3 2 1 0
min_priority_queue: 0 1 2 3 4 5 6 7 8 9

결함 보고로 LWG 307(C++98, Container가 std::vector<bool>일 수 없음 → 허용), LWG 2566(C++98, Container::value_type 요구 누락 → ill-formed 처리), LWG 2684(C++98, 비교기에 대한 멤버 typedef 없음 → 추가)가 있어요.

더 알아보기 (Learn more)

cppreference