Namespaces
Variants

std:: priority_queue

From cppreference.net
C++
Containers library
std::priority_queue
헤더 파일에 정의됨 <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 와 작업하는 것은 일부 임의 접근 컨테이너에서 heap 을 관리하는 것과 유사하며, 힙을 실수로 무효화하지 못하게 하는 장점이 있습니다.

std::priority_queue 의 모든 멤버 함수는 constexpr 입니다: 상수 표현식 평가에서 std::priority_queue 객체를 생성하고 사용하는 것이 가능합니다.

그러나 std::priority_queue 객체는 일반적으로 constexpr 일 수 없습니다. 동적으로 할당된 저장 공간은 동일한 상수 표현식 평가에서 해제되어야 하기 때문입니다.

(C++26부터)

목차

템플릿 매개변수

T - 저장되는 원소의 타입. T 가 Container::value_type 와 동일한 타입이 아닌 경우 프로그램은 ill-formed입니다.
Container - 원소를 저장하는 데 사용되는 기반 컨테이너의 타입. 컨테이너는 SequenceContainer 요구 사항을 충족해야 하며, 해당 반복자는 LegacyRandomAccessIterator 요구 사항을 충족해야 합니다. 추가적으로 다음과 같은 함수들을 일반적인 의미론 으로 제공해야 합니다:

표준 컨테이너 std::vector ( std::vector<bool> 제외)와 std::deque 는 이러한 요구 사항을 충족합니다.

Compare - 엄격한 약순서(strict weak ordering)를 제공하는 Compare 타입.

Compare 매개변수는 첫 번째 인수가 약순서에서 두 번째 인수보다 먼저 오는 경우 true 를 반환하도록 정의되어 있습니다. 그러나 우선순위 큐는 가장 큰 원소를 먼저 출력하기 때문에, "먼저 오는" 원소들이 실제로는 마지막에 출력됩니다. 즉, 큐의 맨 앞에는 Compare 에 의해 부과된 약순서에 따른 "마지막" 원소가 포함됩니다.

멤버 타입

멤버 타입 정의
container_type Container
value_compare Compare
value_type Container::value_type
size_type Container :: size_type
reference Container::reference
const_reference Container::const_reference

멤버 객체

멤버 이름 정의
Container c
기반 컨테이너
(보호된 멤버 객체)
Compare comp
비교 함수 객체
(보호된 멤버 객체)

멤버 함수

priority_queue 를 생성합니다
(public member function)
priority_queue 를 소멸합니다
(public member function)
컨테이너 어댑터에 값을 할당합니다
(public member function)
요소 접근
최상위 요소에 접근합니다
(public member function)
용량
컨테이너 어댑터가 비어 있는지 확인합니다
(public member function)
요소의 개수를 반환합니다
(public member function)
수정자
요소를 삽입하고 내부 컨테이너를 정렬합니다
(public member function)
(C++23)
요소들의 범위를 삽입하고 내부 컨테이너를 정렬합니다
(public member function)
(C++11)
요소를 제자리에서 생성하고 내부 컨테이너를 정렬합니다
(public member function)
최상위 요소를 제거합니다
(public member function)
(C++11)
내용을 교환합니다
(public member function)

비멤버 함수

(C++11)
std::swap 알고리즘을 특수화함
(함수 템플릿)

헬퍼 클래스

(C++11)
std::uses_allocator 타입 특성의 특수화
(클래스 템플릿 특수화)
(C++23)
std::priority_queue 에 대한 포매팅 지원
(클래스 템플릿 특수화)

추론 가이드

(C++17부터)

참고 사항

기능 테스트 매크로 값 표준 기능
__cpp_lib_containers_ranges 202202L (C++23) 레인지 인식 컨테이너 생성 및 삽입
__cpp_lib_constexpr_queue 202502L (C++26) constexpr std::priority_queue

예제

이 코드 실행 
#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>는 최대 우선순위 큐를 최소 우선순위 큐처럼 동작하게 만듭니다.
    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);
    // 최소 우선순위 큐를 정의하는 두 번째 방법
    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);
    // 람다를 사용하여 요소 비교
    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);
}

출력: 

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

결함 보고서

다음 동작 변경 결함 보고서는 이전에 게시된 C++ 표준에 소급 적용되었습니다.

DR 적용 대상 게시된 동작 올바른 동작
LWG 307 C++98 Container 가 std::vector<bool> 일 수 없었음 허용됨
LWG 2566 C++98 Container::value_type 에 대한 요구사항 누락 T 가 Container::value_type 와 동일한 타입이 아닌 경우 형식 오류
LWG 2684 C++98 priority_queue 가 비교자를 받지만
이를 위한 멤버 typedef가 없었음 		추가됨

참고 항목

크기 조정 가능한 연속 배열
(클래스 템플릿)
공간 효율적인 동적 비트셋
(클래스 템플릿 특수화)
양방향 큐
(클래스 템플릿)