• Choose a category
• All
• Classic-Fiction

The STL priority_queue container adapter is also defined in . Its template definition looks something like this (slightly simplified):

template ,

class Compare = less >;

It’s not as complicated as it looks. You’ve seen the first two parameters before: T is the element type stored in the priority_queue and Container is the underlying container on which the priority_queue is adapted. The priority_queue uses vector as the default, but deque works as well. list does not work because the priority_queue requires random access to its elements. The third parameter, Compare, is trickier. As you’ll learn more about in Chapter 13, less is a class template that supports comparison of two objects of type T with operator<. What this means for you is that the priority of elements in the queue is determined according to operator<. You can customize the comparison used, but that’s a topic for Chapter 13. For now, just make sure that you define operator< appropriately for the types stored in the priority_queue.

The head element of the priority_queue is the one with the “highest” priority, by default determined according to operator< such that elements that are “less” than other elements have lower priority.

priority_queue Operations

The priority_queue provides even fewer operations than does the queue. The push() and emplace() methods allow you to insert elements, pop() allows you to remove elements, and top() returns a const reference to the head element.

top() returns a const reference even when called on a non-const object, because modifying the element might change its order, which is not allowed. The priority_queue provides no mechanism to obtain the tail element.

pop() does not return the element popped. If you want to retain a copy, you must first retrieve it with top().

Like the queue, the priority_queue supports size(), empty() and swap(). However, it does not provide any comparison operators. Consult the Standard Library Reference resource on the website for details.

This interface is obviously limited. In particular, the priority_queue provides no iterator support, and it is impossible to merge two priority_queues.

priority_queue Example: An Error Correlator

Single failures on a system can often cause multiple errors to be generated from different components. A good error-handling system uses error correlation to process the most important errors first. You can use a priority_queue to write a very simple error correlator. Assume all error events encode their own priority. This class simply sorts error events according to their priority, so that the highest-priority errors are always processed first. Here is the class definition:

// Sample Error class with just a priority and a string error description.

class Error

{

public:

Error(int priority, const std::string& errMsg

: mPriority(priority), mError(errMsg) {}

int getPriority() const { return mPriority; }

std::string getErrorString() const { return mError; }

friend bool operator<(const Error& lhs, const Error& rhs);

friend std::ostream& operator<<(std::ostream& os,

const Error& err);// See Chapter 18 for details on implementing operator<<

protected:

int mPriority;

std::string mError;

};

// Simple ErrorCorrelator class that returns highest priority errors first.

class ErrorCorrelator

{

public:

ErrorCorrelator() {}

// Add an error to be correlated.

void addError(const Error& error);

// Retrieve the next error to be processed.

Error getError() throw(std::out_of_range);

protected:

std::priority_queue mErrors;

};

Code snippet from ErrorCorrelatorPqueue\ErrorCorrelator.h

Here are the definitions of the functions and methods:

bool operator<(const Error& lhs, const Error& rhs)

{

return (lhs.mPriority < rhs.mPriority);

}

ostream& operator<<(ostream& os, const Error& err)

{

os << err.mError << " (priority " << err.mPriority << ")";

return os;

}

void ErrorCorrelator::addError(const Error& error)

{

mErrors.push(error);