Difference between revisions of "cpp/container/priority queue"
From cppreference.com
m (guides) |
|||
| Line 72: | Line 72: | ||
{{dsc inc | cpp/container/dsc uses_allocator | priority_queue}} | {{dsc inc | cpp/container/dsc uses_allocator | priority_queue}} | ||
{{dsc end}} | {{dsc end}} | ||
| + | |||
| + | ===[[cpp/container/multiset/priority_queue|Deduction guides]]{{mark since c++17}}=== | ||
===Example=== | ===Example=== | ||
Revision as of 11:48, 12 April 2017
| Defined in header <queue>
|
||
| template< class T, |
||
A 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.
Contents |
Template parameters
| T | - | The type of the stored elements. The behavior is undefined if T is not the same type as Container::value_type.(since C++17)
|
| Container | - | The type of the underlying container to use to store the elements. The container must satisfy the requirements of Template:concept, and its iterators must satisfy the requirements of Template:concept. Additionally, it must provide the following functions with the usual semantics:
The standard containers std::vector and std::deque satisfy these requirements. |
| Compare | - | A Template:concept type providing a strict weak ordering. |
Member types
| Member type | Definition |
container_type
|
Container
|
value_compare (C++17)
|
Compare
|
value_type
|
Container::value_type
|
size_type
|
Container::size_type |
reference
|
Container::reference
|
const_reference
|
Container::const_reference
|
Member functions
constructs the priority_queue (public member function) | |
destructs the priority_queue (public member function) | |
| assigns values to the container adaptor (public member function) | |
Element access | |
| accesses the top element (public member function) | |
Capacity | |
| checks whether the container adaptor is empty (public member function) | |
| returns the number of elements (public member function) | |
Modifiers | |
| inserts element and sorts the underlying container (public member function) | |
| (C++11) |
constructs element in-place and sorts the underlying container (public member function) |
| removes the top element (public member function) | |
| (C++11) |
swaps the contents (public member function) |
Member objects | |
| Container c |
the underlying container (protected member object) |
| Compare comp |
the comparison function object (protected member object) |
Non-member functions
| specializes the std::swap algorithm (function template) |
Helper classes
| specializes the std::uses_allocator type trait (class template specialization) |
Deduction guides(since C++17)
Example
Run this code
#include <functional> #include <queue> #include <vector> #include <iostream> template<typename T> void print_queue(T& q) { while(!q.empty()) { std::cout << q.top() << " "; q.pop(); } std::cout << '\n'; } int main() { std::priority_queue<int> q; for(int n : {1,8,5,6,3,4,0,9,7,2}) q.push(n); print_queue(q); std::priority_queue<int, std::vector<int>, std::greater<int> > q2; for(int n : {1,8,5,6,3,4,0,9,7,2}) q2.push(n); print_queue(q2); // 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)> q3(cmp); for(int n : {1,8,5,6,3,4,0,9,7,2}) q3.push(n); print_queue(q3); }
Output:
9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 8 9 6 7 4 5 2 3 0 1
