top() << endl;
toDoList.pop();
}
} ///:~
ToDoItem’s operator< must be a non-member function for it to work with less< >. Other than that, everything happens automatically. The output is:Comment
A1: Water lawn
A2: Feed dog
B1: Feed cat
B7: Feed bird
C3: Mow lawn
C4: Empty trash
Note that you cannot iterate through a priority_queue. However, it is possible to emulate the behavior of a priority_queue using a vector, thus allowing you access to that vector. You can do this by looking at the implementation of priority_queue, which uses make_heap( ), push_heap( ) and pop_heap( ) (they are the soul of the priority_queue; in fact you could say that the heap is the priority queue and priority_queue is just a wrapper around it). This turns out to be reasonably straightforward, but you might think that a shortcut is possible. Since the container used by priority_queue is protected (and has the identifier, according to the Standard C++ specification, named c) you can inherit a new class which provides access to the underlying implementation:Comment
//: C07:PriorityQueue4.cpp
// Manipulating the underlying implementation
//{L} ../TestSuite/Test
#include <iostream>
#include <queue>
#include <cstdlib>
#include <ctime>
using namespace std;
class PQI : public priority_queue<int> {
public:
vector<int>& impl() { return c; }
};
int main() {
PQI pqi;
srand(time(0));
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
copy(pqi.impl().begin(), pqi.impl().end(),
ostream_iterator<int>(cout, " "));
cout << endl;
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~
However, if you run this program you’ll discover that the vector doesn’t contain the items in the descending order that you get when you call pop( ), the order that you want from the priority queue. It would seem that if you want to create a vector that is a priority queue, you have to do it by hand, like this:Comment
//: C07:PriorityQueue5.cpp
// Building your own priority queue
//{L} ../TestSuite/Test
#include <iostream>
#include <queue>
#include <cstdlib>
#include <ctime>
using namespace std;
template<class T, class Compare>
class PQV : public vector<T> {
Compare comp;
public:
PQV(Compare cmp = Compare()) : comp(cmp) {
make_heap(begin(), end(), comp);
}
const T& top() { return front(); }
void push(const T& x) {
push_back(x);
push_heap(begin(), end(), comp);
}
void pop() {
pop_heap(begin(), end(), comp);
pop_back();
}
};
int main() {
PQV<int, less<int> > pqi;
srand(time(0));
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
copy(pqi.begin(), pqi.end(),
ostream_iterator<int>(cout, " "));
cout << endl;
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~
But this program behaves in the same way as the previous one! What you are seeing in the underlying vector is called a heap. This heap represents the tree of the priority queue (stored in the linear structure of the vector), but when you iterate through it you do not get a linear priority-queue order. You might think that you can simply call sort_heap( ), but that only works once, and then you don’t have a heap anymore, but instead a sorted list. This means that to go back to using it as a heap the user must remember to call make_heap( ) first. This can be encapsulated into your custom priority queue:Comment
//: C07:PriorityQueue6.cpp
//{L} ../TestSuite/Test
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
template<class T, class Compare>
class PQV : public vector<T> {
Compare comp;
bool sorted;
void assureHeap() {
if(sorted) {
// Turn it back into a heap:
make_heap(begin(), end(), comp);
sorted = false;
}
}
public:
PQV(Compare cmp = Compare()) : comp(cmp) {
make_heap(begin(), end(), comp);
sorted = false;
}
const T& top() {
assureHeap();
return front();
}
void push(const T& x) {
assureHeap();
// Put it at the end:
push_back(x);
// Re-adjust the heap:
push_heap(begin(), end(), comp);
}
void pop() {
assureHeap();
// Move the top element to the last position:
pop_heap(begin(), end(), comp);
// Remove that element:
pop_back();
}
void sort() {
if(!sorted) {
sort_heap(begin(), end(), comp);
reverse(begin(), end());
sorted = true;
}
}
};
int main() {
PQV<int, less<int> > pqi;
srand(time(0));
for(int i = 0; i < 100; i++) {
pqi.push(rand() % 25);
copy(pqi.begin(), pqi.end(),
ostream_iterator<int>(cout, " "));
cout << "\n-----\n";
}
pqi.sort();
copy(pqi.begin(), pqi.end(),
ostream_iterator<int>(cout, " "));
cout << "\n-----\n";
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~
If sorted is true, then the vector is not organized as a heap, but instead as a sorted sequence. assureHeap( ) guarantees that it’s put back into heap form before performing any heap operations on it.Comment
The first for loop in main( ) now has the additional quality that it displays the heap as it’s being built.Comment
The only drawback to this solution is that the user must remember to call sort( ) before viewing it as a sorted sequence (although one could conceivably override all the methods that produce iterators so that they guarantee sorting). Another solution is to build a priority queue that is not a vector, but will build you a vector whenever you want one:Comment
//: C07:PriorityQueue7.cpp
// A priority queue that will hand you a vector
//{L} ../TestSuite/Test
#include <iostream>