This Thread: February 2012

std::priority_queue

The C++ STL priority_queue, found in the standard queue include file, is not a stand alone specific container, but an adapter, that could be based on each container that provides access to its elements through random access iterators and supports front(), push_back(), and pop_back(). The default implementation is based on std::vector, but std::deque could be used instead.

The random access iterator requirement is due to the need of keeping and internal heap structure, that is the way used by this class to organize the structure as required.

Three template parameters are used to specify the underlying type, container, and comparator for a priority queue. The last two are defaulted to std::vector and less. The comparator is used to determine the order in the queue. By default the first element is ensured to be not lesser than any other element in the queue.

There are a couple of constructors, one requires a compare object and a container, both of them defaulted to the default ctor for the class specified in the template; the other one is in its turn a template function on InputIterator. It expects in input a begin-end pair of iterators delimiting a sequence in a container used to initialize our queue, and then an optional compare and container object.

Given a priority queue, we can just push and pop and element, get the top, get the size, or check if it is empty.

Calling top() or pop() on an empty priority queue results in an undefined behavior, so pay a lot of attention in not doing that.

Let's have some fun writing some example code.

All our queues will be integer based, and will be initialized from this bare array:

int values[] = { 42, 12, 99, 42, 72 };
const int vSize = sizeof(values) / sizeof(int);

First test, we create a plain priority queue for integers. After filling on construction, we'll dump its data, extracting one element after the other from its top:

#include <queue>
#include <iostream>
// ...

typedef std::priority_queue<int> MyPriQue;
std::priority_queue<int> pq(values, values + vSize);

std::cout << "Plain int priority queue: ";
while (pq.empty() == false)
{
    std::cout << pq.top() << ' ';
    pq.pop();
}
std::cout << std::endl;

The expected output is:

Plain int priority queue: 99 72 42 42 12

If we want to have queue organized in the other way round, we change the comparator to greater:

typedef std::priority_queue<int, std::vector<int>, std::greater<int> > MyPriQue;
MyPriQue pq(values, values + vSize);

std::cout << "The smallest first: ";
while (pq.empty() == false)
{
    std::cout << pq.top() << ' ';
    pq.pop();
}
std::cout << std::endl;

As output I would expect to see:

The smallest first: 12 42 42 72 99

It is easy to provide as comparator a custom functor, and that gives us an extra degree of flexibility, when we specify it as parametrized:

class MyComp
{
    bool regular;
public:
    MyComp(bool regular = true)
    {
        this->regular = regular;
    }

    bool operator()(int lhs, int rhs) const
    {
        return regular ? lhs < rhs : lhs > rhs;
    }
};

On creation, we can pass to this comparator a boolean, defaulted to true, that is used to determine how to compare the elements passed to it. In this way we could use the same priority queue definition for both increasing and decreasing ordering, what changes is just the constructor call in the code:

typedef std::priority_queue<int, std::vector<int>, MyComp > MyPriQue;

MyPriQue pq(values, values + vSize); // 1
// MyPriQue pq(values, values + vSize, MyComp(false)); // 2

while (pq.empty() == false)
{
    std::cout << pq.top() << ' ';
    pq.pop();
}
std::cout << std::endl;

1. Here we are saying to the compiler to use the default ctor for the comparer (and for the container), actually, the MyComp ctor expects one parameter in input, but it is defaulted to true.
2. If you comment the previous line and uncomment this one, the queue elements are printed in increasing order.

Pages