Thinking In C++. Volume 2: Practical Programming

You cannot iterate through a priority_queue, but it’s possible to simulate 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 that 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 that provides access to the underlying implementation:

//: C07:PriorityQueue4.cpp

// Manipulating the underlying implementation

#include

#include

#include

#include

#include

using namespace std;

class PQI : public priority_queue {

public:

  vector& 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(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:

//: C07:PriorityQueue5.cpp

// Building your own priority queue

#include

#include

#include

#include

#include

using namespace std;

template

class PQV : public vector {

  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 > pqi;

  srand(time(0));

  for(int i = 0; i < 100; i++)

    pqi.push(rand() % 25);

  copy(pqi.begin(), pqi.end(),

    ostream_iterator(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 data structure 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:

//: C07:PriorityQueue6.cpp

#include

#include

#include

#include

#include

#include

using namespace std;

template

class PQV : public vector {

  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 > pqi;

  srand(time(0));

  for(int i = 0; i < 100; i++) {

    pqi.push(rand() % 25);

    copy(pqi.begin(), pqi.end(),

      ostream_iterator(cout, " "));

    cout << "\n-----\n";

  }

  pqi.sort();

  copy(pqi.begin(), pqi.end(),

    ostream_iterator(cout, " "));

  cout << "\n-----\n";

  while(!pqi.empty()) {

    cout << pqi.top() << ' ';

    pqi.pop();

  }

} ///:~

If sorted is true, the vector is not organized as a heap, but instead as a sorted sequence. The assureHeap( ) function 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 member functions 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:

//: C07:PriorityQueue7.cpp

// A priority queue that will hand you a vector

#include

#include

#include

#include

#include

#include

using namespace std;

template

class PQV {

  vector v;