02.07.2025 01:54, Brian Bi via Std-Proposals пишет:
>
>
> /Brian Bi/
>
> On Tue, Jul 1, 2025, 6:52 PM Magnus Fromreide via Std-Proposals
> <std-proposals_at_[hidden]> 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_at_[hidden]> 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
> <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).