Note, this article is not finished! You can help by editing this doc page.
Overview
- Simplified
- Detailed
template< class T, /* ... */ >
class priority_queue;
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
>
class priority_queue;
Priority queue is a container adapter - it adapts a container by providing a new interface to it.
The new interface resembles a queue with a specified order that's not based on the order of insertion, but rather based on some specified relation between the elements.
Technical definition of a priority queue
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 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
Defined in | queue |
Template parameters
pub | T | The type of the stored elements.
danger The behaviour is undefined if |
pub | Container | The type of the underlying container used to store the elements. By default The container must satisfy SequenceContainer and it's iterators must satisfy LegacyRandomAccesIterator.
The standard containers |
pub | Compare | A Compare type providing a strict weak ordering. note The Compare parameter is defined such that it returns |
Type names
pub | container_type | Container |
pub | value_compare | Compare |
pub | value_type | Container::value_type |
pub | size_type | Container::size_type |
pub | reference | Container::reference |
pub | const_reference | Container::const_reference |
Member functions
pub | (constructors) | Constructs a |
pub | (destructor) | Destructs a |
pub | operator= | Assigns one priority queue to another. |
Element access
pub | top | Accesses the element at the top. |
Capacity
pub | empty | Returns true if the queue is empty, otherwise false . |
pub | size | Returns the number of elements in the queue. |
Modifiers
pub | push | Inserts an element and sorts the underlying container using Compare . |
pub | emplace (since C++11) | Constructs an element in-place and sorts the underlying container. |
pub | pop | Removes the top element. |
pub | swap (since C++11) | Swaps two queues. |
Member objects
prot | Container C | The underlying container. By default std::vector<T> . |
prot | Compare comp | The comparator object. |
Non-member functions
pub | std::swap (std::priority_queue) | An overload for a std::swap algorithm. |
Helper classes
pub | std::uses_allocator (std::priority_queue) | Specializes the std::uses_allocator type trait. |
Deduction guides (since C++17)
Click to expand
Deduction guides
// (1)
template< class Comp, class Container >
priority_queue( Comp, Container )
-> priority_queue<typename Container::value_type, Container, Comp>;
// (2)
template< class Comp, class Container, class Alloc >
priority_queue( Comp, Container, Alloc )
-> priority_queue<typename Container::value_type, Container, Comp>;
// (3)
template< class InputIt, class Comp, class Container, class Alloc >
priority_queue( InputIt, InputIt, Comp, Container, Alloc )
-> priority_queue<typename Container::value_type, Container, Comp>;
(1 - 3)
allow deduction from an underlying container type
// (4)
template< class InputIt, class Comp, class Alloc >
priority_queue( InputIt, InputIt, Comp, Alloc )
-> priority_queue<iter_val_t<InputIt>,
std::vector<iter_val_t<InputIt>, Alloc>, Comp>;
// (5)
template< class InputIt, class Alloc >
priority_queue( InputIt, InputIt, Alloc )
-> priority_queue<iter_val_t<InputIt>,
std::vector<iter_val_t<InputIt>, Alloc>,
std::less<iter_val_t<InputIt>>>;
// (6)
template< class InputIt,
class Comp = std::less<iter_val_t<InputIt>>,
class Container = std::vector<iter_val_t<InputIt> >
priority_queue( InputIt, InputIt, Comp = Comp(), Container = Container() )
-> priority_queue<iter_val_t<InputIt>, Container, Comp>;
(4 - 6)
allow deduction from an iterator range
Alias iter_val_t
is defined as if follows:
template< class InputIt >
using iter_val_t = typename std::iterator_traits<InputIt>::value_type;
Note that this alias isn't guaranteed to be found anywhere in the standard library. It is defined solely for presentation purposes of these deduction guides and weren't present in the standard library at the point of writing this document.
Overload resolution
In order for any of the deduction guides to participate in overload resolution, the folllowing requirements must be met:
InputIt
satisfiesLegacyInputIterator
Comp
doesn't satisfyAllocator
Container
doesn't satisfyAllocator
- for
(3)
and(5)
, (since C++23)Alloc
satisfiesAllocator
- for
(2)
and(4)
,std::uses_allocator_v<Container, Alloc>
istrue
The extent to which the library determines that a type does not satisfy LegacyInputIterator
is unspecified,
except that as a minimum:
- Integral types do not qualify as input iterators.
Likewise, the extent to which it determines that a type does not satisfy Allocator
is unspecified,
except that as a minimum:
- The member type
Alloc::value_type
must exist. - The expression
std::declval<Alloc&>().allocate(std::size_t{})
must be well-formed when treated as an unevaluated operand.
Examples
Basic manipulation
#include <iostream>
#include <queue>
int main()
{
std::priority_queue<int> q;
queue.push(1);
queue.push(2);
queue.push(3);
while (!queue.empty()) {
std::cout << queue.top() << '\n';
queue.pop();
}
}
3
2
1
Hover to see the original license.