View source for cpp/container/priority queue

You do not have permission to edit this page, for the following reasons:
The action you have requested is limited to users in one of the groups: Users, Administrators.
Due to recent vandalism, editing of this page is temporarily disabled for new users.If you want to suggest a change, please leave a message on the suggestions page for new users instead (don't be surprised if that page appears vandalized!).
You can view and copy the source of this page.
{{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.

{{cpp/is_constexpr|since=c++26|transient=yes}}

===Template parameters===
{{par begin}}
{{par|T|The type of the stored elements. The program is ill-formed if {{tt|T}} is not the same type as {{tt|Container::value_type}}.}}
{{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}} (not 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|__cpp_lib_constexpr_containers|value=202502L|std=C++26|{{c/core|constexpr}} {{tt|std::priority_queue}}}}
{{ftm end}}

===Example===
{{example
|code=
#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;

    // Fill the priority queue.
    for (int n : data)
        max_priority_queue.push(n);

    pop_println("max_priority_queue", max_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>>
        min_priority_queue1(data.begin(), data.end());

    pop_println("min_priority_queue1", min_priority_queue1);

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

    pop_println("min_priority_queue2", min_priority_queue2);

    // 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 custom_priority_queue(data.begin(), data.end(), customLess);

    pop_println("custom_priority_queue", custom_priority_queue);

    // 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)> 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
}}

===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=2566|std=C++98|before=Missing the requirement for {{tt|Container::value_type}}|after=ill-formed if {{tt|T}} is not the same type as {{tt|Container::value_type}}}}
{{dr list item|wg=lwg|dr=2684|std=C++98|before={{tt|priority_queue}} takes a comparator<br>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}}
Templates used on this page:
cppreference.com

Search

Namespaces

Variants

Views

Actions

View source for cpp/container/priority queue
