std::priority_queue
std::priority_queue<queue>
class T,
class Container = std::vector <T>,
class Compare = std::less <typename Container::value_type>
The priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.
A user-provided Compare can be supplied to change the ordering, e.g. using std::greater <T> would cause the smallest element to appear as the top() .
Working with a priority_queue is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.
std::priority_queue are constexpr: it is possible to create and use std::priority_queue objects in the evaluation of a constant expression.However, std::priority_queue objects generally cannot be constexpr, because any dynamically allocated storage must be released in the same evaluation of constant expression.
Contents
[edit] Template parameters
T is not the same type as Container::value_type.
- front(), e.g., std::vector::front() ,
- push_back(), e.g., std::deque::push_back() ,
- pop_back(), e.g., std::vector::pop_back() .
The standard containers std::vector (not including std::vector<bool>) and std::deque satisfy these requirements.
Note that the Compare parameter is defined such that it returns 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 Compare.
[edit] Member types
value_compare
Compare
[edit] Member objects
(protected member object)
[edit] Member functions
Element access
Capacity
Modifiers
(public member function) [edit]
(public member function) [edit]
[edit] Non-member functions
[edit] Helper classes
Deduction guides
(since C++17)[edit] Notes
| 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) | constexpr std::priority_queue
|
[edit] Example
#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
[edit] Defect reports
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 be std::vector<bool>
|
allowed |
| LWG 2566 | C++98 | Missing the requirement for Container::value_type
|
ill-formed if T is not the same type as Container::value_type
|
| LWG 2684 | C++98 | priority_queue takes a comparatorbut lacked member typedef for it |
added |