Extracting last element of a priority_queue

Question

I'm using a std::priority_queue to write an algorithm that computes the Distance Function of a data-set on a 3D grid. After having initialized the queue I'd like to store in a separate variable the last element, just like you do with std::queue.back() but, of course, this is not possible with priority queues, so my work-around is the following:

CellQueue q; //this is the actual priority_queue

//...
//initialization
//...

Cell* last = 0;
CellQueue dummy(q);
while (!dummy.empty()) {
    last = dummy.top();
    dummy.pop();
}

Of course there is a better way to solve this problem, so I'd be very glad if someone could show it to me.

Thanks,

Federico

---

EDIT

@Sam @Dietmar The algorithm to compute the distance function (DF) works in this way: you fill the priority_queue with the cells of the grid that contain at least one point of the data-set and you order them by distance (which at this step is zero) in increasing order. Then, for each element of the queue, you visit the neighbors and for each neighbor you compute the distance with respect to its parent. Now, for efficiency reasons I'd like to compute the DF only on a narrow band around the data-set. So in order to stop this process after having visited the 3rd ring neighborhood, I have to keep track of the last element of the current ring.

Answer 1

The "obvious" way is to store a copy of the last (smallest) element along with the priority_queue. The additional work to track this is proportional to the number of elements added to the priority queue, whereas your workaround is N log(N) in the size of the queue at the time you call it, so take your pick.

Whenever you pop, by definition you can only be removing the last value if the pop causes the queue to be empty, so you don't need to worry about updating anything on pop.

Whenever you push to the priority queue, compare the value being pushed with the current minimum and replace it if necessary. Same goes for emplace.

If you want to be really fancy you can present this by writing your own container adaptor, priority_queue_that_additionally_accesses_the_min_value. Or maybe a shorter name.

If you need to access the actual element, rather than a copy of it, then you have a problem in that the priority_queue itself will move things around internally while you aren't looking, so you can't just keep a pointer to the minimum. Wrapping the elements up in smart pointers might deal with that, and of course you need to supply priority_queue with a comparator that deferences the smart pointer.

Finally, there is such a thing as a "double-ended priority queue". This will allow you to efficiently remove at both ends rather than efficiently removing from one end and examining both. It's not in standard C++, but either look up the necessary structures and algorithms and implement it yourself, or else search for C++ implementations of "double-ended priority queue" or "min/max heap". I've never used the structure myself so I won't recommend a specific one.