home *** CD-ROM | disk | FTP | other *** search
/ Reverse Code Engineering RCE CD +sandman 2000 / ReverseCodeEngineeringRceCdsandman2000.iso / RCE / Ebooks / Thinking in C++ V2 / C20 / PriorityQueue7.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2000-05-25  |  1.5 KB  |  61 lines
  1. //: C20:PriorityQueue7.cpp
  2. // From Thinking in C++, 2nd Edition
  3. // Available at http://www.BruceEckel.com
  4. // (c) Bruce Eckel 1999
  5. // Copyright notice in Copyright.txt
  6. // A priority queue that will hand you a vector
  7. #include <iostream>
  8. #include <queue>
  9. #include <algorithm>
  10. #include <cstdlib>
  11. #include <ctime>
  12. using namespace std;
  13.  
  14. template<class T, class Compare>
  15. class PQV {
  16.   vector<T> v;
  17.   Compare comp;
  18. public:
  19.   // Don't need to call make_heap(); it's empty:
  20.   PQV(Compare cmp = Compare()) : comp(cmp) {}
  21.   void push(const T& x) {
  22.     // Put it at the end:
  23.     v.push_back(x);
  24.     // Re-adjust the heap:
  25.     push_heap(v.begin(), v.end(), comp);
  26.   }
  27.   void pop() {
  28.     // Move the top element to the last position:
  29.     pop_heap(v.begin(), v.end(), comp);
  30.     // Remove that element:
  31.     v.pop_back();
  32.   }
  33.   const T& top() { return v.front(); }
  34.   bool empty() const { return v.empty(); }
  35.   int size() const { return v.size(); }
  36.   typedef vector<T> TVec;
  37.   TVec vector() {
  38.     TVec r(v.begin(), v.end());
  39.     // It's already a heap
  40.     sort_heap(r.begin(), r.end(), comp);
  41.     // Put it into priority-queue order:
  42.     reverse(r.begin(), r.end());
  43.     return r;
  44.   }
  45. };
  46.  
  47. int main() {
  48.   PQV<int, less<int> > pqi;
  49.   srand(time(0));
  50.   for(int i = 0; i < 100; i++)
  51.     pqi.push(rand() % 25);
  52.   const vector<int>& v = pqi.vector();
  53.   copy(v.begin(), v.end(),
  54.     ostream_iterator<int>(cout, " "));
  55.   cout << "\n-----------\n"; 
  56.   while(!pqi.empty()) {
  57.     cout << pqi.top() << ' ';
  58.     pqi.pop();
  59.   }
  60. } ///:~
  61.