How to get last element of priority queue without traversing it

Question

I have the following priority queue:

#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;
}

Now in order to get the last element, I have to pop() all the elements in the queue. Is there some way by which I may retrieve just the last element of this priority queue.

I know that it is possible to reverse the order in "CompareTime" so that the last element becomes the first. I do not want to do it as I want to pop() the elements from priority queue in the order determined by "CompareTime". But at the same time I also want the last element of the priority queue..without popping all the elements from the priority queue. Is it possible to determine the value of the last element of the priority queue.

I am using the following gcc compiler: gcc (Ubuntu/Linaro 4.6.4-6ubuntu2) 4.6.4

Solution 1

std::priority_queue does not support what you want to do directly. Please refer to: http://www.cplusplus.com/reference/queue/priority_queue/

Of course you can always create your own DS but there are a few library containers that can do what you need.

EDIT:

You may consider using

std::set 

http://en.cppreference.com/w/cpp/container/set

It is ordered, you can quickly access to the first and the last element and you can also quickly remove any element. Please note that, the elements need to be unique. If you do not want that you can use

std::multiset 

which is more flexible and can do the trick.

For getting the elements on both ends

std::set::begin
std::set::rbegin

iterators are available. Since the set is sorted all the time, these are the minimum and the maximum elements.

Hope that helps!

Solution 2

You can store the value as, some large value - actual value and then perform the same operation i.e. large value - queue (top) value while retrieving. e.g. say, large value = 100 then store 56 as 44 20 as 80 ... and while retrieving 80 as 100-80 = 20

This is how you can fill the queue in reverse priority order ;)

Comments

[Mark B]

What you want is not a feature/requirement of the standard priority queue. Why do you need to know this value/what do you want to do with it? And as a purely theoretical side comment, I notice your seconds field shows 0-59: will it at least not break on the leap-second this summer (seconds=60 once this year).

[Lightness Races in Orbit]

That's why storing time like this is not a good idea.