uwaga

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

Overview

Simplified

template< class T, /* ... */ >
class priority_queue;

Detailed

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. od C++17 uwaga The behaviour is undefined if T is not Container::value_type.
pub	Container	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.
pub	Compare	A Compare type providing a strict weak ordering. zanotuj 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

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 priority_queue.
pub	(destructor)	Destructs a priority_queue.
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;

zanotuj

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 satisfies LegacyInputIterator
• Comp doesn't satisfy Allocator
• Container doesn't satisfy Allocator
• for (3) and (5), (since C++23) Alloc satisfies Allocator
• for (2) and (4), std::uses_allocator_v<Container, Alloc> is true

zanotuj

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

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