C++ Logo

std-proposals

Advanced search

Re: [std-proposals] Add an ability to move the top element from std::priority_queue

From: Brian Bi <bbi5291_at_[hidden]>
Date: Tue, 1 Jul 2025 18:54:04 -0400
*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
> > > )
> > >
> > > 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.


> /MF
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>

Received on 2025-07-01 22:54:21