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:
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:
#include <queue>
int main() {
std::priority_queue<int> Numbers;
}
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:
#include <queue>
#include <vector>
int main() {
std::vector<int> Source{1, 2, 3};
std::priority_queue<int> Numbers{
Source.begin(), Source.end()};
}
We can also construct a priority queue by copying another priority queue.
#include <queue>
int main() {
std::priority_queue<int> Numbers;
std::priority_queue<int> Copy{Numbers};
}
When creating a queue from another queue, we can omit the template parameter. This will let the compiler infer it, using Class Template Argument Deduction (CTAD):
#include <queue>
int main() {
std::priority_queue<int> Numbers;
std::priority_queue Copy{Numbers};
}
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.
std::priority_queue
Container TypeThe 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:
#include <queue>
#include <vector>
int main() {
std::priority_queue<int, std::vector<int>>
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.
#include <deque>
#include <queue>
int main() {
std::priority_queue<int, std::deque<int>>
Numbers;
}
To maintain the priority ordering behavior, std::priority_queue
adaptor needs random access to its elements, using the []
, so we need to use a container that supports this.
In addition, the container needs to have the following methods:
push_back()
- adds an object to the end of the containerpop_back()
- removes the object at the end of the containerfront()
- returns a reference to the object at the front of the containerBeyond 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.
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, 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:
#include <queue>
#include <vector>
int main() {
std::vector<int> Source{1, 2, 3};
std::priority_queue<int> Numbers{{}, Source};
}
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:
#include <queue>
#include <vector>
int main() {
std::vector<int> Source{1, 2, 3};
std::priority_queue<int> Numbers{
{}, std::move(Source)};
}
We cover copy semantics, move semantics, and rvalue references in more detail in these lessons:
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 two methods we use for working with the front (or the “top”) of our priority queues are top
and pop
.
top()
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:
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::vector<int> Source{1, 2, 3};
std::priority_queue<int> Numbers{
{}, std::move(Source)};
std::cout << "The top of the queue is "
<< Numbers.top();
}
The top of the queue is 3
pop()
We use pop
to remove the item at the top of the queue:
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::vector<int> Source{1, 2, 3};
std::priority_queue<int> Numbers{
{}, std::move(Source)};
std::cout << "The top of the queue is "
<< Numbers.top();
Numbers.pop();
std::cout << "\nThe top of the queue is now "
<< Numbers.top();
}
The top of the queue is 3
The top of the queue is now 2
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 this:
auto Comparer{
[](int x, int y) { return x > y; }};
When creating our queue, we need to pass the type of our comparison function as the third template parameter. Here, we ask the compiler to work it out, by passing our comparison function to decltype
:
using queue = std::priority_queue<
int,
std::vector<int>,
decltype(Comparer)>;
We can be explicit using std::function
(from <functional>
) instead of decltype
:
using queue = std::priority_queue<
int,
std::vector<int>,
std::function<bool(int, int)>>;
We cover std::function
, and other functional helpers in a dedicated lesson:
Finally, when constructing our queue, we need to pass the comparison function into an appropriate constructor.
As of C++23, there are 19 different std::priority_queue
constructors and 15 of them allow us to pass a comparison function.
We can see all the options in our IDE, but the following example uses the simplest, where we pass the comparer as the only argument:
auto Comparer{
[](int x, int y) { return x > y; }};
using queue = std::priority_queue<
int,
std::vector<int>,
std::function<bool(int, int)>>;
queue Numbers{Comparer};
Here is a complete working example:
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::vector<int> Source{1, 2, 3};
auto Comparer{
[](int x, int y) { return x > y; }};
using queue = std::priority_queue<
int, std::vector<int>,
std::function<bool(int, int)>>;
queue Numbers{Comparer, std::move(Source)};
std::cout << "The top of the queue is "
<< Numbers.top();
Numbers.pop();
std::cout << "\nThe top of the queue is now "
<< Numbers.top();
}
The top of the queue is 1
The top of the queue is now 2
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:
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> Nums;
Nums.emplace(10);
std::cout << Nums.top()
<< " is at the top of the queue";
}
10 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:
#include <iostream>
#include <queue>
int main() {
std::priority_queue<int> Nums;
int x{10};
int y{20};
// Copy
Nums.push(x);
// Move
Nums.push(std::move(y));
std::cout << "We have " << Nums.size()
<< " items in the queue";
}
We have 2 items in the queue
push_range()
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:
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<int> Nums;
std::vector Range{1, 2, 3};
Nums.push_range(Range);
std::cout << "We have " << Nums.size()
<< " items in the queue";
}
We have 3 items in the queue
The priority_queue
class has two more useful functions:
size()
The size
method returns an integer representing how many objects are in the queue:
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::vector<int> Source{1, 2, 3};
std::priority_queue<int> Numbers{
{}, std::move(Source)};
std::cout << "The queue's size is "
<< Numbers.size();
Numbers.pop();
std::cout << "\nThe size is now "
<< Numbers.size();
}
The queue's size is 3
The size is now 2
empty()
If we only care whether the object is empty (ie, size() == 0
) we can use the dedicated empty()
method:
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<int> Numbers;
Numbers.emplace(5);
std::cout << "The queue "
<< (Numbers.empty() ? "is"
: "is not")
<< " empty\n";
Numbers.pop();
std::cout << "Now the queue "
<< (Numbers.empty() ? "is"
: "is not")
<< " empty";
}
The queue is not empty
Now the queue is empty
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:
#include <iostream>
#include <queue>
class Character {
public:
Character(std::string Name, int Level)
: Name{Name}, Level{Level} {}
std::string Name;
int Level;
};
int main() {
auto compare{[](Character& x, Character& y) {
return x.Level < y.Level;
}};
using QueueType = std::priority_queue<
Character, std::vector<Character>,
decltype(compare)>;
QueueType Q{compare};
Q.emplace("Aragorn", 40);
Q.emplace("Gandalf", 50);
Q.emplace("Bilbo", 20);
Q.emplace("Frodo", 30);
int SpaceInParty{3};
while (SpaceInParty && !Q.empty()) {
std::cout << "Adding " << Q.top().Name
<< " (" << Q.top().Level
<< ") to the party\n";
Q.pop();
--SpaceInParty;
}
std::cout << Q.size()
<< " Character is still in queue";
}
Adding Gandalf (50) to the party
Adding Aragorn (40) to the party
Adding Frodo (30) to the party
1 Character is still in queue
std::priority_queue
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.
std::priority_queue
does not give us a way to change the comparison function after our queue is created. Additionally, 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, leaving our queue inaccurate.
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
:
#include <iostream>
#include <queue>
class Character {
public:
Character(std::string Name, int Health)
: Name{Name}, Health{Health} {}
std::string Name;
int Health;
};
int main() {
auto compare{[](Character* x, Character* y) {
return x->Health < y->Health;
}};
using QueueType = std::priority_queue<
Character*, std::vector<Character*>,
decltype(compare)>;
QueueType Q{compare};
Character Legolas{"Legolas", 100};
Character Gandalf{"Gandalf", 50};
Q.push(&Legolas);
Q.push(&Gandalf);
std::cout
<< "The highest priority character is "
<< Q.top()->Name;
Legolas.Health = 0;
std::cout << "\nThe highest priority "
"character is still "
<< Q.top()->Name;
}
The highest priority character is Legolas
The highest priority character is still Legolas
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.
— Created
Comprehensive course covering advanced concepts, and how to use them on large-scale projects.