Create a priority queue to contain user defined objects. In this case, the prior
ID: 3548056 • Letter: C
Question
Create a priority queue to contain user defined objects. In this case, the priority queue needs to know the comparison criterion used to determine which objects have the highest priority. This is done by means of a function object belonging to a class that overloads the operator (). The overloaded () acts as < for the purpose of determining priorities. For example, suppose we want to create a priority queue to store Time objects. A Time object has three fields: hours, minutes, seconds:
struct Time {
int h;
int m;
int s;
};
class CompareTime {
public:
bool operator()(Time& t1, Time& t2) // Returns true if t1 is earlier than t2
{
if (t1.h < t2.h) return true;
if (t1.h == t2.h && t1.m < t2.m) return true;
if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
return false;
}
}
A priority queue to store times accoording the the above comparison criterion would be defined as follows:
priority_queue<Time, vector<Time>, CompareTime> pq;
Explanation / Answer
#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;
struct Time {
int h; // >= 0
int m; // 0-59
int s; // 0-59
};
class CompareTime {
public:
bool operator()(Time& t1, Time& t2)
{
if (t1.h < t2.h) return true;
if (t1.h == t2.h && t1.m < t2.m) return true;
if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true;
return false;
}
};
int main()
{
priority_queue<Time, vector<Time>, CompareTime> pq;
// Array of 4 time objects:
Time t[4] = { {3, 2, 40}, {3, 2, 26}, {5, 16, 13}, {5, 14, 20}};
for (int i = 0; i < 4; ++i)
pq.push(t[i]);
while (! pq.empty()) {
Time t2 = pq.top();
cout << setw(3) << t2.h << " " << setw(3) << t2.m << " " <<
setw(3) << t2.s << endl;
pq.pop();
}
return 0;
}
The program prints the times from latest to earliest:
5 16 13
5 14 20
3 2 40
3 2 26
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.