Brian Bi

On Tue, Jul 1, 2025, 6:52 PM Magnus Fromreide via Std-Proposals <std-proposals@lists.isocpp.org> wrote:

On Tue, Jul 01, 2025 at 10:03:55PM +0100, Jonathan Wakely via Std-Proposals wrote:
> On Tue, 1 Jul 2025 at 21:27, Alexey Sidorin via Std-Proposals <
> std-proposals@lists.isocpp.org> wrote:
>
> > Hello everyone,
> > I would like to propose adding extract_top() method to `
> > std::priority_queue` backed by a set of freestanding functions in
> > <algorithm> header.
> >
> > 1. Problem statement
> >
> > In order to extract the top element from std::priority_queue, we have to
> > write something like this:
> > auto x = queue.top(); // Copy constructor or copy assignment.
> > queue.pop();
> >
> > Unfortunately, we cannot move a top value from the queue because top() is
> > of const_reference type (
> > https://eel.is/c++draft/priority.queue#priqueue.members).
> > The first problem is that this can cause a performance hit if the value
> > type is expensive to copy (a structure containing large strings, etc.).
> > The second problem is that this also makes impossible to use
> > priority_queue with move-only types.
> > I've made a search in chromium sources showing that almost all heap
> > structure usage have a similar pattern:
> >
> > std::pop_heap(msg_queue.begin(), msg_queue.end());
> > *event = std::move(msg_queue.back());
> > msg_queue.pop_back();
> > (
> > https://github.com/search?q=repo%3Achromium%2Fchromium%20pop_heap&type=code
> > )
> >
> > I think this clearly indicates that we can have a better interface here.
> >
>
>
> See  https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3182r1.html

When I look at https://www.wg21.link/p3182/status it looks like this paper
have stalled despite the initially positive response it received.

Is this the case or is there some work going on in the background?

There was an LEWG mailing list review where most people didn't seem convinced of the utility of the proposed additions. I published a new revision attempting to address some of the concerns, which I think is in the LEWG scheduling black hole right now.

Hi Brian. I took a pause to wait for any movement of your proposal as it covers most of mine, but I didn't see any. Do you need assistance in working on it? Or, maybe, it is better to resurrect this one and eat this elephant piece by piece?

One more issue in priority_queue top()&pop() approach is that pop() uses pop_heap() + pop_back() call pair internally. And pop_heap() is required to move the top element to the sequence end. This can introduce stores hard to elide by compilers. If I do not mistake, in https://godbolt.org/z/r7KK7MYzc we can find such a store in assembly line 13.

There were also no remarks about adding free functions (extract_heap_top()).

I'm also cc'ing Arthur O'Dwyer who had some excellent notes on the previous proposal (and even suggested the same method name).