Priority Queues using std::priority_queue

A priority queue works in much the same way as a queue, which we covered in the previous lesson. There is one key difference: when we insert an object into a priority queue, it is not necessarily inserted into the back of the queue.

Rather, its insertion point is determined by its priority, with higher-priority objects being inserted closer to the front of the queue.

We cover how priority works, and how to customize it, later in the lesson. For now, let's see a simple example of creating a priority queue using std::priority_queue

std::priority_queue

The C++ standard library’s implementation of a priority queue is std::priority_queue. It’s available to us after we #include the <queue> header.

It is a template class that has 3 template parameters:

1. The type of data we’re storing in the queue
2. The type of underlying container we want to use
3. A comparison function for determining the priority of objects

The second and third parameters are optional, and we’ll cover them later. For now, let's see how we can create a simple priority queue of integers:

1#include <queue>
2
3int main() {
4  std::priority_queue<int> Numbers;
5}

Providing Initial Values using Iterators

The queue class does not have a constructor that lets us provide a list of initial values, but we can construct a priority queue from an iterator pair.

The iterator pair specifies a start and end for a range of values we want our priority queue to be initialized with:

1#include <queue>
2#include <vector>
3
4int main() {
5  std::vector<int> Source{1, 2, 3};
6  std::priority_queue<int> Numbers{
7      Source.begin(), Source.end()};
8}

Iterators

This lesson provides an in-depth look at iterators in C++, covering different types like forward, bidirectional, and random access iterators, and their practical uses.

Copying and Moving Queues

We can also construct a priority queue by copying or moving another priority queue.

1#include <queue>
2
3int main() {
4  std::priority_queue<int> Numbers;
5  std::priority_queue<int> A{Numbers};
6  std::priority_queue<int> B{std::move(Numbers)};
7}

We covered the difference between copying and moving objects in more detail earlier in the course:

Copy Semantics and Return Value Optimization

Learn how to control exactly how our objects get copied, and take advantage of copy elision and return value optimization (RVO)

Move Semantics

Learn how we can improve the performance of our types using move constructors, move assignment operators and std::move()

Class Template Argument Deduction (CTAD)

When providing initial values for our priority queue, we can typically omit the template argument. The compiler can infer what data type our queue will be storing based on the type of the initial values we’re populating it with:

1#include <queue>
2#include <vector>
3
4int main() {
5  std::vector<int> Source{1, 2, 3};
6  
7  // Creates a std::priority_queue<int>
8  std::priority_queue Numbers{
9    Source.begin(), Source.end()};
10      
11  // Creates a std::priority_queue<int>
12  std::priority_queue Copy{Numbers};
13}

In the next sections, we’ll see how we can construct a priority queue from another container, or how we can push a collection of objects to the queue at once.

Container Adaptors

The std::priority_queue class is a container adaptor. This means it does not manage the storage of its objects - rather, it defers that to another container class. std::priority_queue then interacts with the underlying container, to provide us with an API that acts like a priority queue.

By default, the container underlying std::priority_queue is a std::vector.

We can specify the underlying container by passing it as the second template parameter when creating our priority queue. As such, we could replicate the default behavior like this:

1#include <queue>
2#include <vector>
3
4int main() {
5  std::priority_queue<int, std::vector<int>>
6      Numbers;

In this example, we set the underlying container to a std::deque instead of a std::vector. We cover std::deque (a double-ended queue) later in this chapter.

1#include <deque>
2#include <queue>
3
4int main() {
5  std::priority_queue<int, std::deque<int>>
6      Numbers;
7}

To maintain the priority ordering behavior, the std::priority_queue adaptor requires the underlying container to support random access to its elements. Specifically, the container needs to provide this capability through random access iterators.

In addition, the container needs to have the following methods:

• push_back() - adds an object to the end of the container
• pop_back() - removes the object at the end of the container
• front() - returns a reference to the object at the front of the container

Beyond implementing these methods, we’d preferably want the underlying container to be set up such that it can execute them efficiently. This is not enforced by the compiler, but if we want our priority queue to be performant, we should ensure the underlying container is performant when it comes to these functions.

Both std::vector and std::deque meet all these requirements, but we’re not restricted to using the standard library containers. Any class that meets the requirements can be used.

Initializing from a Container

We can initialize a queue using a collection of the queue’s underlying type. Given the default underlying type is a std::vector, if we don’t change that, we can initialize our priority queue directly from a vector.

Note, that there is not currently a dedicated constructor for this, but there is one that accepts an optional comparison function as the first argument, and an optional container as the second.

We’ll introduce custom comparers later in this lesson. For now, we don’t want to provide a custom compare, so we can pass {} as the first argument, and the vector as our second:

1#include <queue>
2#include <vector>
3
4int main() {
5  std::vector<int> Source{1, 2, 3};
6  std::priority_queue<int> Numbers{{}, Source};
7}

If we no longer need the container from which we’re creating our priority queue, we can move it to our queue rather than performing a slower, unnecessary copy:

1#include <queue>
2#include <vector>
3
4int main() {
5  std::vector<int> Source{1, 2, 3};
6  std::priority_queue<int> Numbers{
7      {}, std::move(Source)};
8}

Accessing Objects

Given the intended use of a priority queue, we should typically only be accessing elements at the front of it. If we need to access other elements, a queue is unlikely to be the correct data structure for our task.

The top() method returns a reference to the object that is currently at the top of the queue, ie the object with the highest priority:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5int main() {
6  std::vector<int> Source{1, 2, 3};
7  std::priority_queue<int> Numbers{
8      {}, std::move(Source)};
9
10  std::cout << "The top of the queue is "
11            << Numbers.top();
12}

1The top of the queue is 3

Removing (Popping) Objects

We use the pop() method to remove the item at the top of the queue:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5int main() {
6  std::vector<int> Source{1, 2, 3};
7  std::priority_queue<int> Numbers{
8      {}, std::move(Source)};
9
10  std::cout << "The top of the queue is "
11            << Numbers.top();
12
13  Numbers.pop();
14
15  std::cout << "\nThe top of the queue is now "
16            << Numbers.top();
17}

1The top of the queue is 3
2The top of the queue is now 2

Customizing the Priority Order

To customize the priority of objects in our queue, we pass a comparison function as the first argument to our constructor.

The comparison function will receive two objects as parameters and should return true if the first parameter has a lower priority than the second.

For example, if we want our queue of numbers to prioritize lower numbers, our comparison function might look like the following lambda:

1auto Comparer{
2  [](int x, int y) { return x > y; }};

Lambda expressions are a shorter syntax for defining functions. We cover them in detail later in the course:

Lambdas

An introduction to lambda expressions - a concise way of defining simple, ad-hoc functions

When constructing our queue, we need to pass the comparison function into an appropriate constructor. Here is a complete working example:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5int main() {
6  std::vector<int> Source{1, 2, 3};
7
8  auto Comparer{
9      [](int x, int y) { return x > y; }};
10
11  std::priority_queue Numbers{
12    Comparer, std::move(Source)};
13
14  std::cout << "The top of the queue is "
15            << Numbers.top();
16
17  Numbers.pop();
18
19  std::cout << "\nThe top of the queue is now "
20            << Numbers.top();
21}

1The top of the queue is 1
2The top of the queue is now 2

Providing the Comparison Function Type

The examples in this section used class template argument deduction to have the compiler deduce the type of our comparer, but we may want (or need) to be explicit.

In the following example, we provide the template arguments, but ask the compiler to figure out the comparer’s type using decltype:

1#include <queue>
2#include <vector>
3
4int main() {
5  std::vector<int> Source{1, 2, 3};
6
7  auto Comparer{[](int x, int y) { return x > y; }};
8
9  std::priority_queue<
10    int, std::vector<int>, decltype(Comparer)
11  > Numbers{
12    Comparer, std::move(Source)
13  };
14}

Remember, we can add a using statement to alias complex types:

1using pq = std::priority_queue<
2  int,
3  std::vector<int>,
4  decltype(Comparer)>;

Rather than using decltype, we could be explicit about our comparer type using std::function from the <functional> header:

1using pq = std::priority_queue<
2  int,
3  std::vector<int>,
4  std::function<bool(int, int)>>;

We cover std::function, and other functional helpers in a dedicated lesson:

Standard Library Function Helpers

A comprehensive overview of function helpers in the standard library, including std::invocable, std::predicate and std::function.

Getting the Size

The priority_queue class has two more useful functions:

size()

The size method returns an integer representing how many objects are in the queue:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5int main() {
6  std::vector<int> Source{1, 2, 3};
7  std::priority_queue<int> Numbers{
8      {}, std::move(Source)};
9
10  std::cout << "The queue's size is "
11            << Numbers.size(); 
12
13  Numbers.pop();
14
15  std::cout << "\nThe size is now "
16            << Numbers.size(); 
17}

1The queue's size is 3
2The size is now 2

empty()

If we only care whether the object is empty (ie, size() == 0) we can use the dedicated empty() method:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5int main() {
6  std::priority_queue<int> Numbers;
7  Numbers.emplace(5);
8
9  std::cout << "The queue "
10            << (Numbers.empty() ? "is" 
11                                : "is not")
12            << " empty\n";
13
14  Numbers.pop();
15
16  std::cout << "Now the queue "
17            << (Numbers.empty() ? "is" 
18                                : "is not")
19            << " empty";
20}

1The queue is not empty
2Now the queue is empty

Adding (Enqueueing) Objects

Similar to the regular std::queue, we have two ways to insert objects into our priority queue: we can either emplace() them or push() them.

emplace()

The emplace() method will construct our object directly into the queue’s memory, which is preferred if the object doesn’t yet exist. Constructing an object in place is usually faster than constructing it elsewhere, and then moving or copying it.

The emplace() method passes any arguments along to the constructor of the type stored in our priority queue:

1#include <iostream>
2#include <queue>
3
4int main() {
5  std::priority_queue<int> Nums;
6  Nums.emplace(10);
7
8  std::cout << Nums.top()
9            << " is at the top of the queue";
10}

110 is at the top of the queue

push()

If our object already exists, we can use the priority queue’s push() method to copy or move it into our container:

1#include <iostream>
2#include <queue>
3
4int main() {
5  std::priority_queue<int> Nums;
6
7  int x{10};
8  int y{20};
9
10  // Copy
11  Nums.push(x); 
12
13  // Move
14  Nums.push(std::move(y));
15
16  std::cout << "We have " << Nums.size()
17            << " items in the queue";
18}

1We have 2 items in the queue

push_range() (C++ 23)

Note: this is a C++23 feature, and is not yet supported by all compilers

Since C++23, we can now push a range into a priority queue.

Ranges were introduced in C++20, and we cover them in detail in our later chapters on algorithms. For now, the key point is that most of the sequential containers we work with will be a valid range, and can be passed to the push_range() method.

Pushing a range into a priority queue looks like this:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5int main() {
6  std::priority_queue<int> Nums;
7  std::vector Range{1, 2, 3};
8
9  Nums.push_range(Range);
10
11  std::cout << "We have " << Nums.size()
12            << " items in the queue";
13}

1We have 3 items in the queue

Typical Priority Queue Usage

The typical approach for consuming a priority queue uses a while loop that continues whilst Queue.empty() is false. Within the body of the loop, we access the front() object, perform the required operations, and then pop() it off.

It might look something like this, where we maintain a queue of Character objects prioritized by their Level member variable:

1#include <iostream>
2#include <queue>
3
4class Character {
5 public:
6  Character(std::string Name, int Level)
7      : Name{Name}, Level{Level} {}
8  std::string Name;
9  int Level;
10};
11
12int main() {
13  auto compare{[](Character& x, Character& y) {
14    return x.Level < y.Level;
15  }};
16
17  using QueueType = std::priority_queue<
18      Character, std::vector<Character>,
19      decltype(compare)>;
20
21  QueueType Q{compare};
22
23  Q.emplace("Anna", 40);
24  Q.emplace("Roderick", 50);
25  Q.emplace("Bob", 20);
26  Q.emplace("Fred", 30);
27
28  int SpaceInParty{3};
29
30  while (SpaceInParty && !Q.empty()) {
31    std::cout << "Adding " << Q.top().Name
32              << " (" << Q.top().Level
33              << ") to the party\n";
34    Q.pop();
35    --SpaceInParty;
36  }
37
38  std::cout << Q.size()
39            << " Character is still in queue";
40}

1Adding Roderick (50) to the party
2Adding Anna (40) to the party
3Adding Fred (30) to the party
41 Character is still in queue

Reprioritization and Dynamic Priorities

The standard library’s implementation of a priority queue does not support reprioritization or dynamic priority of objects that are already in the queue. The priority of each object is calculated only one time: when it is first inserted into the queue. This has two implications:

• If we change an element in our queue in a way that would affect its prioritization, the object is going to remain in its original position. This leaves our queue in an inaccurate state
• std::priority_queue does not allow us to change the comparison function after the queue is created.

Below, we prioritize our characters by highest Health. After modifying our top Character, it remains at the top of the queue, even though it no longer has the highest Health:

1#include <iostream>
2#include <queue>
3
4class Character {
5 public:
6  Character(std::string Name, int Health)
7      : Name{Name}, Health{Health} {}
8  std::string Name;
9  int Health;
10};
11
12int main() {
13  auto compare{[](Character* x, Character* y) {
14    return x->Health < y->Health;
15  }};
16
17  using QueueType = std::priority_queue<
18      Character*, std::vector<Character*>,
19      decltype(compare)>;
20
21  QueueType Q{compare};
22
23  Character Anna{"Anna", 100};
24  Character Roderick{"Roderick", 50};
25
26  Q.push(&Anna);
27  Q.push(&Roderick);
28
29  std::cout
30    << "The highest priority is "
31    << Q.top()->Name
32    << " ("<< Q.top()->Health << " Health)\n";
33
34  Anna.Health = 0; 
35
36  std::cout
37    << "The highest priority is still "
38    << Q.top()->Name
39    << " ("<< Q.top()->Health << " Health)";
40}

1The highest priority character is Anna
2The highest priority character is still Anna

The standard library does not have a class that implements a priority queue with reprioritization and dynamic priority. If we need that, we need to build it ourselves or look for 3rd party options outside of the standard library.

Summary

In this lesson, we introduced the notion of a priority queue, and in particular, the C++ standard library’s implementation of such a structure: std::priority_queue. The key takeaways include:

• Priority queues are similar to regular queues, but elements are inserted based on their priority.
• std::priority_queue is a container adaptor in the C++ Standard Library that provides a priority queue data structure.
• The underlying container for std::priority_queue is std::vector by default, but it can be changed to other containers like std::deque.
• Priority queues can be initialized using iterators, copying/moving from other priority queues, or using class template argument deduction (CTAD).
• The top element of the priority queue can be accessed using the top() method, and elements can be removed using pop().
• The priority order can be customized by providing a comparison function as a template argument.
• Elements can be added to the priority queue using emplace(), push(), or push_range() (C++23).
• The size of the priority queue can be obtained using size(), and empty() checks if the queue is empty.
• Typical usage involves a loop that processes elements from the top of the queue until it is empty.
• The standard library implementation does not support reprioritization or dynamic priorities for elements already in the queue.

Next Lesson

Introduction to Stacks using std::stack

An introduction to the stack data structure, and the standard library implementation - std::stack

ContinueView Course