View source for cpp/container/priority queue

{{cpp/title|priority_queue}}
{{cpp/container/priority_queue/navbar}}
{{ddcl|header=queue|1=
template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;
}}

The {{enwiki|Queue (abstract data type)|priority queue}} is a [[cpp/container#Container adaptors|container adaptor]] that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

A user-provided {{tt|Compare}} can be supplied to change the ordering, e.g. using {{c|std::greater<T>}} would cause the smallest element to appear as the {{lc|top()}}.

Working with a {{tt|priority_queue}} is similar to managing a [[cpp/algorithm/make_heap|heap]] in some random access container, with the benefit of not being able to accidentally invalidate the heap.

===Template parameters===
{{par begin}}
{{par|T|The type of the stored elements. The behavior is undefined if {{tt|T}} is not the same type as {{tt|Container::value_type}}.<!-- LWG2566 -->}}
{{par|Container|The type of the underlying container to use to store the elements. The container must satisfy the requirements of {{named req|SequenceContainer}}, and its iterators must satisfy the requirements of {{named req|RandomAccessIterator}}. Additionally, it must provide the following functions with the [[cpp/named req/SequenceContainer#Optional operations|usual semantics]]:
* {{lc|front()}}, e.g., {{lc|std::vector::front()}},
* {{lc|push_back()}}, e.g., {{lc|std::deque::push_back()}},
* {{lc|pop_back()}}, e.g., {{lc|std::vector::pop_back()}}.

The standard containers {{lc|std::vector}} (including {{rlpt|vector bool|std::vector<bool>}}) and {{lc|std::deque}} satisfy these requirements.}}
{{par|Compare|A {{named req|Compare}} type providing a strict weak ordering.

Note that the {{named req|Compare}} parameter is defined such that it returns {{c|true}} if its first argument comes ''before'' its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by {{named req|Compare}}.}}
{{par end}}

===Member types===
{{dsc begin}}
{{dsc hitem|Member type|Definition}}
{{dsc inc|cpp/container/dsc container_type|priority_queue}}
{{dsc|{{tt|value_compare}}|{{tt|Compare}}}}
{{dsc inc|cpp/container/dsc value_type|priority_queue}}
{{dsc inc|cpp/container/dsc size_type|priority_queue}}
{{dsc inc|cpp/container/dsc reference|priority_queue}}
{{dsc inc|cpp/container/dsc const_reference|priority_queue}}
{{dsc end}}

===Member objects===
{{dsc begin}}
{{dsc hitem|Member name|Definition}}
{{dsc inc|cpp/container/dsc c|priority_queue}}
{{dsc prot mem obj|nolink=true|{{dsc small|Compare}} comp|the comparison function object}}
{{dsc end}}

===Member functions===
{{dsc begin}}
{{dsc inc|cpp/container/dsc constructor|priority_queue}}
{{dsc inc|cpp/container/dsc destructor|priority_queue}}
{{dsc inc|cpp/container/dsc operator{{=}}|priority_queue}}

{{dsc h2|Element access}}
{{dsc inc|cpp/container/dsc top|priority_queue}}

{{dsc h2|Capacity}}
{{dsc inc|cpp/container/dsc empty|priority_queue}}
{{dsc inc|cpp/container/dsc size|priority_queue}}

{{dsc h2|Modifiers}}
{{dsc inc|cpp/container/dsc push|priority_queue}}
{{dsc inc|cpp/container/dsc push_range|priority_queue}}
{{dsc inc|cpp/container/dsc emplace|priority_queue}}
{{dsc inc|cpp/container/dsc pop|priority_queue}}
{{dsc inc|cpp/container/dsc swap|priority_queue}}
{{dsc end}}

===Non-member functions===
{{dsc begin}}
{{dsc inc|cpp/container/dsc swap2|priority_queue}}
{{dsc end}}

===Helper classes===
{{dsc begin}}
{{dsc inc|cpp/container/dsc uses_allocator|priority_queue}}
{{dsc inc|cpp/container/dsc adaptor_formatter|priority_queue}}
{{dsc end}}

{{rrev|since=c++17|
==={{rl|deduction guides|Deduction guides}}===
}}

===Notes===
{{ftm begin|std=1|comment=1}}
{{ftm|__cpp_lib_containers_ranges|value=202202L|std=C++23|[[cpp/ranges/to#container compatible range|Ranges-aware]] construction and insertion for containers}}
{{ftm end}}

===Example===
{{example
|code=
#include <concepts>
#include <functional>
#include <iostream>
#include <queue>
#include <ranges>
#include <string_view>
#include <vector>

template<typename T>
void print(std::string_view name, T const& q)
{
    std::cout << name << ": \t";
    for (auto const& n : q)
        std::cout << n << ' ';
    std::cout << '\n';
}

template<typename Adaptor>
requires (std::ranges::input_range<typename Adaptor::container_type>)
void print(std::string_view name, const Adaptor& adaptor)
{
    struct Printer : Adaptor // to access protected Adaptor::Container c;
    {
        void print(std::string_view name) const { ::print(name, this->c); }
    };
 
    static_cast<Printer const&>(adaptor).print(name);
}

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

    std::priority_queue<int> q1; // Max priority queue
    for (int n : data)
        q1.push(n);

    print("q1", q1);

    // Min priority queue
    // std::greater<int> makes the max priority queue act as a min priority queue
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        minq1(data.begin(), data.end());

    print("minq1", minq1);

    // Second way to define a min priority queue
    std::priority_queue minq2(data.begin(), data.end(), std::greater<int>());

    print("minq2", minq2);

    // Using a custom function object to compare elements.
    struct
    {
        bool operator()(const int l, const int r) const { return l > r; }
    } customLess;
    std::priority_queue minq3(data.begin(), data.end(), customLess);

    print("minq3", minq3);

    // 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)> q5(cmp);

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

    print("q5", q5);
}
|output=
data:   1 8 5 6 3 4 0 9 7 2
q1:     9 8 7 6 5 4 3 2 1 0
minq1:  0 1 2 3 4 5 6 7 8 9
minq2:  0 1 2 3 4 5 6 7 8 9
minq3:  0 1 2 3 4 5 6 7 8 9
q5:     8 9 6 7 4 5 2 3 0 1
}}

===Defect reports===
{{dr list begin}}
{{dr list item|wg=lwg|dr=307|std=C++98|before={{tt|Container}} could not be {{tt|std::vector<bool>}}|after=allowed}}
{{dr list item|wg=lwg|dr=2684|std=C++98|before={{tt|priority_queue}} takes a comparator but lacked member typedef for it|after=added}}
{{dr list end}}

===See also===
{{dsc begin}}
{{dsc inc|cpp/container/dsc vector}}
{{dsc inc|cpp/container/dsc vector bool}}
{{dsc inc|cpp/container/dsc deque}}
{{dsc end}}

{{langlinks|cs|de|es|fr|it|ja|pl|pt|ru|tr|zh}}