On Wed, Jan 21, 2026 at 5:33 AM Сидорин Алексей <alexey.v.sidorin_at_[hidden]>
wrote:

> On Sat, Jan 17, 2026 at 3:19 PM 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.
>
>
> You propose:
> - T std::priority_queue<T>::extract_top()
> - T std::extract_heap_top(It first, It last, Compare c);
>
> (1) The existing heap algorithms are always named with the suffix `_heap`;
> you propose a name with `_heap_` on the inside. I don't like that. The
> natural name given your nomenclature would be simply `std::extract_heap`.
>
> As I mentioned in the proposal, naming is a subject for discussion. I
> thought `extract_heap_top` expresses the action better. However, your point
> is true, and `extract_top` is shorter, so we can follow this way.
>

Correction: `std::extract_heap`, not `std::extract_top`. Although
I still recommend adopting the verb "displace" for "remove and return,"
which makes it `std::displace_heap`.
This morning it occurs to me that `std::remove_heap` is a decent name for
the void-returning version (i.e. the version which I called
`std::foobar_trashing_pop_heap` yesterday). std::list<T> has `remove` and
`remove_if` with vaguely similar semantics (no value returned), and the
`std::remove` algorithm works almost exactly this way: it shifts items down
leaving the tail of the range in a "moved-from" state. So, yeah, I'm
talking myself into supporting `std::remove_heap` for the void-returning
version.

So this makes my proposed API look like this:

- T std::displace_heap(It first, It last, Compare c);
    The same as pop_heap, except that it leaves last[-1] in a moved-from
state and returns the old top. Compared to C++26 pop_heap, saves one
move-assign.
- T std::priority_queue<T>::displace_top();
    Implemented in terms of std::displace_heap. Enables using
priority_queue with unique_ptr. This is a big deal. *(Sadly, this cannot be
implemented in terms of std::remove_heap!)*
- void std::remove_heap(It first, It last, Compare c);
    The same as pop_heap, except that it leaves last[-1] in a moved-from
state. Compared to C++26 pop_heap, saves one each of move-construct,
move-assign, destroy.
- void std::priority_queue<T>::pop();
<https://eel.is/c++draft/priqueue.members#6>
    Re-specify in terms of std::remove_heap. Compared to C++26 pop, saves
one each of move-construct, move-assign, destroy.

What I'm seeing here is that what-I'm-now-calling-`std::remove_heap`, the
void-returning version, is actually the core of this proposal: it lets us
speed up `priority_queue::pop`.
It is very unfortunate that `priority_queue::displace_top` cannot also be
implemented in terms of `std::remove_heap`. (This is because
`std::remove_heap` requires that the range be in heap-order, and if you
start by moving-out-of the top element, the range will no longer be in
heap-order. Precondition violation, UB.) If we could relax the precondition
on `std::remove_heap` until it was usable by
`priority_queue::displace_top`, then we wouldn't need to provide
`std::displace_heap` at all. That would be great, because (1) STL
algorithms that return non-iterators are annoying and ugly, and (2) it
would reduce the surface area of this proposal.

I'm curious if jwakely is reading this thread and if he has any ideas here,
either implementation-wise or wording-wise, that will let
`std::remove_heap` be the sole new algorithm in this proposal.


[...] My point was that the final `*std::prev(last) =
> std::extract_top_heap(first, last);` in std::pop_heap will not just result
> in a redundant move constructor call,
>

[Correction: s/move constructor/move-assignment/ ]


[...] Maybe we should name the returning function `extract_heap` and
> non-returning (aka "t[]rashing") `displace_heap`?
>

Hopefully this is a moot point now, because I think `std::remove_heap` is
the right name for the trashing version.
But FWIW, I would try to strongly oppose any use of the verb "displace" to
mean anything different from "move/relocate out and return by value." I
have no formal proposal for this, but it's a super useful verb that we can
use in places like
    T t = vec.displace_back();
    t = deque.displace_front();
    t = pq.displace_top();
    auto it = std::find_if(lst.begin(), lst.end(), isOdd);
    t = lst.displace(it);
etc. etc. I don't want to see people start using "displace" to mean simply
"pop and discard," because the STL already has *multiple* verbs for that —
it's "pop" (pop_back, pop_front, pq.pop(), stack.pop()), and simultaneously
it's "erase" (lst.erase(it)) and it's "remove" (lst.remove(v)). We don't
need a *fourth* verb to mean that same thing. What we need is a *first*
verb with the meaning "pop and return," which can be applied consistently
across the whole STL.

–Arthur