Skip to main content
caution

Note, this article is not finished! You can help by editing this doc page.

Overview

template< class T, /* ... */ >
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 inqueue

Template parameters

pubT

The type of the stored elements.

danger

The behaviour is undefined if T is not Container::value_type.

pubContainer

The type of the underlying container used to store the elements. By default std::vector<T>.

The container must satisfy SequenceContainer and it's iterators must satisfy LegacyRandomAccesIterator.
Additionally, it must provide the following functions with the usual semantics:

  • back()
  • front()
  • push_back()
  • pop_front()

The standard containers std::vector and std::deque satisfy these requirements.

pubCompare

A Compare type providing a strict weak ordering.

note

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.

Type names

pubcontainer_typeContainer
pubvalue_compareCompare
pubvalue_typeContainer::value_type
pubsize_typeContainer::size_type
pubreferenceContainer::reference
pubconst_referenceContainer::const_reference

Member functions

pub(constructors)

Constructs a priority_queue.

pub(destructor)

Destructs a priority_queue.

puboperator=Assigns one priority queue to another.

Element access

pubtopAccesses the element at the top.

Capacity

pubemptyReturns true if the queue is empty, otherwise false.
pubsizeReturns the number of elements in the queue.

Modifiers

pubpushInserts an element and sorts the underlying container using Compare.
pubemplace (since C++11) Constructs an element in-place and sorts the underlying container.
pubpopRemoves the top element.
pubswap (since C++11) Swaps two queues.

Member objects

protContainer CThe underlying container. By default std::vector<T>.
protCompare compThe comparator object.

Non-member functions

pubstd::swap (std::priority_queue)An overload for a std::swap algorithm.

Helper classes

pubstd::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

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:

note

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:

Examples

Basic manipulation

Push and pop on queue, printing the values
#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();
}
}
Result
3
2
1
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.
caution

Note, this article is not finished! You can help by editing this doc page.

Overview

template< class T, /* ... */ >
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 inqueue

Template parameters

pubT

The type of the stored elements.

danger

The behaviour is undefined if T is not Container::value_type.

pubContainer

The type of the underlying container used to store the elements. By default std::vector<T>.

The container must satisfy SequenceContainer and it's iterators must satisfy LegacyRandomAccesIterator.
Additionally, it must provide the following functions with the usual semantics:

  • back()
  • front()
  • push_back()
  • pop_front()

The standard containers std::vector and std::deque satisfy these requirements.

pubCompare

A Compare type providing a strict weak ordering.

note

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.

Type names

pubcontainer_typeContainer
pubvalue_compareCompare
pubvalue_typeContainer::value_type
pubsize_typeContainer::size_type
pubreferenceContainer::reference
pubconst_referenceContainer::const_reference

Member functions

pub(constructors)

Constructs a priority_queue.

pub(destructor)

Destructs a priority_queue.

puboperator=Assigns one priority queue to another.

Element access

pubtopAccesses the element at the top.

Capacity

pubemptyReturns true if the queue is empty, otherwise false.
pubsizeReturns the number of elements in the queue.

Modifiers

pubpushInserts an element and sorts the underlying container using Compare.
pubemplace (since C++11) Constructs an element in-place and sorts the underlying container.
pubpopRemoves the top element.
pubswap (since C++11) Swaps two queues.

Member objects

protContainer CThe underlying container. By default std::vector<T>.
protCompare compThe comparator object.

Non-member functions

pubstd::swap (std::priority_queue)An overload for a std::swap algorithm.

Helper classes

pubstd::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

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:

note

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:

Examples

Basic manipulation

Push and pop on queue, printing the values
#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();
}
}
Result
3
2
1
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.