Priority
queues
When
you
push( )
an object onto a
priority_queue,
that object is sorted into the queue according to a function or function object
(you can allow the default
less
template to supply this, or provide one of your own). The
priority_queue
ensures that when you look at the
top( )
element it will be the one with the highest priority. When you’re done
with it, you call
pop( )
to remove it and bring the next one into place. Thus, the
priority_queue
has nearly the same interface as a
stack,
but it behaves differently.
Like
stack
and
queue,
priority_queue
is an adapter which is built on top of one of the basic sequences – the
default is
vector. It’s
trivial to make a
priority_queue
that works with
ints:
//: C20:PriorityQueue1.cpp
#include <iostream>
#include <queue>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {
priority_queue<int> pqi;
srand(time(0)); // Seed random number generator
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~ This
pushes into the
priority_queue
100
random values from 0 to 24. When you run this program you’ll see that
duplicates are allowed, and the highest values appear first. To show how you
can change the ordering by providing your own function or function object, the
following program gives lower-valued numbers the highest priority:
//: C20:PriorityQueue2.cpp
// Changing the priority
#include <iostream>
#include <queue>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Reverse {
bool operator()(int x, int y) {
return y < x;
}
};
int main() {
priority_queue<int, vector<int>, Reverse> pqi;
// Could also say:
// priority_queue<int, vector<int>,
// greater<int> > pqi;
srand(time(0));
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~ Although
you can easily use the Standard Library
greater
template to produce the predicate, I went to the trouble of creating
Reverse
so you could see how to do it in case you have a more complex scheme for
ordering your objects.
If
you look at the description for
priority_queue,
you see that the constructor can be handed a “Compare” object, as
shown above. If you don’t use your own “Compare” object, the
default template behavior the
less
template
function. You might think (as I did) that it would make sense to leave the
template instantiation as
priority_queue<int>,
thus using the default template arguments of
vector<int>
and
less<int>.
Then you could inherit a new class from
less<int>,
redefine
operator( )
and hand an object of that type to the
priority_queue
constructor. I tried this, and got it to compile, but the resulting program
produced the same old
less<int>
behavior. The answer lies in the
less<
>
template:
template <class T>
struct less : binary_function<T, T, bool> {
// Other stuff...
bool operator()(const T& x, const T& y) const {
return x < y;
}
};The
operator( )
is not
virtual,
so even though the constructor takes your subclass of
less<int>
by reference (thus it doesn’t slice it down to a plain
less<int>),
when
operator( )
is called, it is the base-class version that is used. While it is generally
reasonable to expect ordinary classes to behave polymorphically, you cannot
make this assumption when using the STL.
Of
course, a
priority_queue
of
int
is trivial. A more interesting problem is a to-do list, where each object
contains a
string
and a primary and secondary priority value:
//: C20:PriorityQueue3.cpp
// A more complex use of priority_queue
#include <iostream>
#include <queue>
#include <string>
using namespace std;
class ToDoItem {
char primary;
int secondary;
string item;
public:
ToDoItem(string td, char pri ='A', int sec =1)
: item(td), primary(pri), secondary(sec) {}
friend bool operator<(
const ToDoItem& x, const ToDoItem& y) {
if(x.primary > y.primary)
return true;
if(x.primary == y.primary)
if(x.secondary > y.secondary)
return true;
return false;
}
friend ostream&
operator<<(ostream& os, const ToDoItem& td) {
return os << td.primary << td.secondary
<< ": " << td.item;
}
};
int main() {
priority_queue<ToDoItem> toDoList;
toDoList.push(ToDoItem("Empty trash", 'C', 4));
toDoList.push(ToDoItem("Feed dog", 'A', 2));
toDoList.push(ToDoItem("Feed bird", 'B', 7));
toDoList.push(ToDoItem("Mow lawn", 'C', 3));
toDoList.push(ToDoItem("Water lawn", 'A', 1));
toDoList.push(ToDoItem("Feed cat", 'B', 1));
while(!toDoList.empty()) {
cout << toDoList.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:
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:
//: C20:PriorityQueue4.cpp
// Manipulating the underlying implementation
#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:
//: C20:PriorityQueue5.cpp
// Building your own priority queue
#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:
//: C20:PriorityQueue6.cpp
#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.
The
first
for
loop in
main( )
now has the additional quality that it displays the heap as it’s being
built.
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:
//: C20:PriorityQueue7.cpp
// A priority queue that will hand you a vector
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
template<class T, class Compare>
class PQV {
vector<T> v;
Compare comp;
public:
// Don't need to call make_heap(); it's empty:
PQV(Compare cmp = Compare()) : comp(cmp) {}
void push(const T& x) {
// Put it at the end:
v.push_back(x);
// Re-adjust the heap:
push_heap(v.begin(), v.end(), comp);
}
void pop() {
// Move the top element to the last position:
pop_heap(v.begin(), v.end(), comp);
// Remove that element:
v.pop_back();
}
const T& top() { return v.front(); }
bool empty() const { return v.empty(); }
int size() const { return v.size(); }
typedef vector<T> TVec;
TVec vector() {
TVec r(v.begin(), v.end());
// It’s already a heap
sort_heap(r.begin(), r.end(), comp);
// Put it into priority-queue order:
reverse(r.begin(), r.end());
return r;
}
};
int main() {
PQV<int, less<int> > pqi;
srand(time(0));
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
const vector<int>& v = pqi.vector();
copy(v.begin(), v.end(),
ostream_iterator<int>(cout, " "));
cout << "\n-----------\n";
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~ PQV
follows the same form as the STL’s
priority_queue,
but has the additional member
vector( ),
which creates a new
vector
that’s a copy of the one in
PQV
(which
means that it’s already a heap), then sorts it (thus it leave’s
PQV’s
vector
untouched), then reverses the order so that traversing the new
vector
produces the same effect as popping the elements from the priority queue.
You
may observe that the approach of inheriting from
priority_queue
used in
PriorityQueue4.cpp
could be used with the above technique to produce more succinct code:
//: C20:PriorityQueue8.cpp
// A more compact version of PriorityQueue7.cpp
#include <iostream>
#include <queue>
#include <cstdlib>
#include <ctime>
using namespace std;
template<class T>
class PQV : public priority_queue<T> {
public:
typedef vector<T> TVec;
TVec vector() {
TVec r(c.begin(), c.end());
// c is already a heap
sort_heap(r.begin(), r.end(), comp);
// Put it into priority-queue order:
reverse(r.begin(), r.end());
return r;
}
};
int main() {
PQV<int> pqi;
srand(time(0));
for(int i = 0; i < 100; i++)
pqi.push(rand() % 25);
const vector<int>& v = pqi.vector();
copy(v.begin(), v.end(),
ostream_iterator<int>(cout, " "));
cout << "\n-----------\n";
while(!pqi.empty()) {
cout << pqi.top() << ' ';
pqi.pop();
}
} ///:~ The
brevity of this solution makes it the simplest and most desirable, plus
it’s guaranteed that the user will not have a
vector
in the unsorted state. The only potential problem is that the
vector( )
member function returns the
vector<T>
by value, which might cause some overhead issues with complex values of the
parameter type
T.
Go to CodeGuru.com
Contact: webmaster@codeguru.com
© Copyright 1997-1999 CodeGuru