(C++17) | ||||
Sequence | ||||
(C++11) | ||||
(C++26) | ||||
(C++26) | ||||
(C++11) | ||||
Associative | ||||
Unordered associative | ||||
(C++11) | ||||
(C++11) | ||||
(C++11) | ||||
(C++11) | ||||
Adaptors | ||||
priority_queue | ||||
(C++23) | ||||
(C++23) | ||||
(C++23) | ||||
(C++23) | ||||
Views | ||||
(C++20) | ||||
(C++23) | ||||
Tables | ||||
Iterator invalidation | ||||
Member function table | ||||
Non-member function table |
std::priority_queue
Member functions | ||||
Element access | ||||
Capacity | ||||
Modifiers | ||||
(C++23) | ||||
(C++11) | ||||
(C++11) | ||||
Non-member functions | ||||
(C++11) | ||||
Helper classes | ||||
Deduction guides(C++17) |
Defined in header <queue> | ||
template< class T, | ||
Thepriority queue is acontainer adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.
A user-providedCompare
can be supplied to change the ordering, e.g. usingstd::greater<T> would cause the smallest element to appear as thetop().
Working with apriority_queue
is similar to managing aheap in some random access container, with the benefit of not being able to accidentally invalidate the heap.
All member functions ofstd::priority_queue areconstexpr: it is possible to create and usestd::priority_queue objects in the evaluation of a constant expression.However, | (since C++26) |
Contents |
T | - | The type of the stored elements. The program is ill-formed ifT is not the same type asContainer::value_type . |
Container | - | The type of the underlying container to use to store the elements. The container must satisfy the requirements ofSequenceContainer, and its iterators must satisfy the requirements ofLegacyRandomAccessIterator. Additionally, it must provide the following functions with theusual semantics:
The standard containersstd::vector (not including |
Compare | - | ACompare type providing a strict weak ordering. Note that theCompare parameter is defined such that it returnstrue if its first argument comesbefore 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 byCompare. |
Member type | Definition |
container_type | Container [edit] |
value_compare | Compare |
value_type | Container::value_type [edit] |
size_type | Container::size_type[edit] |
reference | Container::reference [edit] |
const_reference | Container::const_reference [edit] |
Member name | Definition |
Container c | the underlying container (protected member object)[edit] |
Compare comp | the comparison function object (protected member object) |
constructs thepriority_queue (public member function)[edit] | |
destructs thepriority_queue (public member function)[edit] | |
assigns values to the container adaptor (public member function)[edit] | |
Element access | |
accesses the top element (public member function)[edit] | |
Capacity | |
checks whether the container adaptor is empty (public member function)[edit] | |
returns the number of elements (public member function)[edit] | |
Modifiers | |
inserts element and sorts the underlying container (public member function)[edit] | |
(C++23) | inserts a range of elements and sorts the underlying container (public member function)[edit] |
(C++11) | constructs element in-place and sorts the underlying container (public member function)[edit] |
removes the top element (public member function)[edit] | |
(C++11) | swaps the contents (public member function)[edit] |
specializes thestd::swap algorithm (function template)[edit] |
specializes thestd::uses_allocator type trait (class template specialization)[edit] | |
formatting support forstd::priority_queue (class template specialization)[edit] |
Deduction guides | (since C++17) |
Feature-test macro | Value | Std | Feature |
---|---|---|---|
__cpp_lib_containers_ranges | 202202L | (C++23) | Ranges-aware construction and insertion for containers |
__cpp_lib_constexpr_queue | 202502L | (C++26) | constexprstd::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(constauto& e: v)std::cout<< e<<' ';std::cout<<'\n';} int main(){constauto 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()(constint l,constint 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 2max_priority_queue: 9 8 7 6 5 4 3 2 1 0min_priority_queue1: 0 1 2 3 4 5 6 7 8 9min_priority_queue2: 0 1 2 3 4 5 6 7 8 9custom_priority_queue: 0 1 2 3 4 5 6 7 8 9lambda_priority_queue: 8 9 6 7 4 5 2 3 0 1
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
DR | Applied to | Behavior as published | Correct behavior |
---|---|---|---|
LWG 307 | C++98 | Container could not bestd::vector<bool> | allowed |
LWG 2566 | C++98 | Missing the requirement forContainer::value_type | ill-formed ifT is not the same type asContainer::value_type |
LWG 2684 | C++98 | priority_queue takes a comparatorbut lacked member typedef for it | added |
resizable contiguous array (class template)[edit] | |
space-efficient dynamic bitset (class template specialization)[edit] | |
double-ended queue (class template)[edit] |