A specialization of the priority_queue class template holds elements of type T and implements the five operations given in Table 18:
Elements of type T must be comparable to each other, either through the use of the default less-than operator, operator<(), or through a comparison function passed either as a template argument or as an optional argument on the constructor. The latter form will be illustrated in the example program provided later in this chapter. As with all the containers in the C++ Standard Library, there are several constructors. The default constructor requires either no arguments or the optional comparison function. An alternative constructor takes two iterators and initializes the values in the container from the range the iterators define. An optional third argument can be used to define the comparison function.
The priority_queue datatype is built on top of a container class, which is the structure actually used to maintain the values in the collection. There are two containers in the C++ Standard Library that can be used to construct priority_queues: vectors or deques. By default, a priority_queue will use vector.
The following illustrates the declaration of several priority_queues:
// minimal case -- uses std::vector<int> and std::less<int>
std::priority_queue<int> queue_one;
std::priority_queue<int, std::vector<int>, std::greater<int> >
queue_two;
std::priority_queue<double, std::deque<double> >
queue_three(aList.begin(), aList.end());
std::priority_queue<myData, std::vector<myData> >
queue_four(myComparison);
std::priority_queue<myData, std::deque<myData> >
queue_five(aVector.begin(), aVector.end(), myComparison);
When deciding whether to use a vector or deque as the underlying container, consider the data which is to be stored. The default, vector, performs quite well for most cases. If the number of elements will vary, a deque will use less memory when the priority_queue has few elements. A vector has less overhead, so may be more efficient in cases where the priority_queue will tend to remain at approximately the same size. However, increasing the memory allocated to a vector may require copying the elements into newly allocated space. Copying takes time, so a vector may be inefficient if the size of the priority_queue will tend to increase. These are, of course, generalized statements which may not apply to the problem at hand. In cases where performance or memory consumption is important, you should try both underlying containers and compare the results.
Because the priority_queue data structure does not itself know how to construct iterators, very few of the algorithms noted in Chapter 13 can be used with priority_queues. Instead of iterating over values, a typical algorithm that uses a priority_queue constructs a loop, which repeatedly pulls values from the structure (using the top() and pop() member functions) until the collection becomes empty (tested using the empty() member function). The example program described in Section 11.3 illustrates this use.
A priority_queue is implemented by internally building a data structure called a heap. Abstractly, a heap is a binary tree in which the value associated with every node is smaller than or equal to the value associated with either child node. Details of the algorithms used in manipulating heaps will not be discussed here, but can be found in most textbooks on data structures.