Hi,

This seems like a reasonable and useful addition to the standard.

However, I'm not a fan of how we're throwing more papers into the pipeline.
Brian's
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3182r1.html
covers more containers than just addressing std::priority_queue, and I like
that holistic approach. People have been asking for a way to pop the top
value of a stack instead of having to do it in two separate calls, so the
design space is broader than just priority queues.

Ironically, Brian's paper is described as "stalled" in your references, and
Brian is stalling his paper because he's waiting for you (
https://github.com/cplusplus/papers/issues/1843#issuecomment-5268122492).
Can you please coordinate? I don't see any reason for this to turn into an
anthology of competing papers when you all agree on the problem statement
and design direction.


Yours
Jan

On Sun, 11 Oct 2026 at 22:57, Aleksei Sidorin via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> Hi Arthur and std-proposals,
>
> My reply with the updated proposal version is a bit late. I'm sorry for
> that, but I needed some time to thoroughly verify my benchmarking.
> Unfortunately, careful measurements showed that the performance does not
> change noticeably (falling within noise levels for most types), at least on
> my benchmarking sets. However, there is a consistent generated code size
> reduction across all benchmarks which even allows inlining for some complex
> types. I've reflected these updated findings in the 'Benchmarks' sections.
> I've also addressed the review comments.
>
> Please find the updated proposal attached. Thank you for your review and
> any comments in advance.
>
> ---
> Best regards,
> Aleksei Sidorin.
>
>
> Hi Alexey, Sorry for the belated reply. :)
>>
>> (1) I'd like to see the benchmarks sections rearranged so that the
>> differences between runs are legible. Right now you have them not even on
>> the same page; it's like
>>
>> > (page 5)
>> > uint32_1 3.51 ns 3.51 ns 199491584
>> > uint32_4 3.73 ns 3.73 ns 187170816
>> > uint32_16 8.65 ns 8.65 ns 81002496
>> > (page 6)
>> > uint32_1 3.61 ns 3.60 ns 193462272
>> > uint32_4 3.56 ns 3.56 ns 196870144
>> > uint32_16 8.57 ns 8.57 ns 81788928
>>
>>
>> What I'd like to see is: Instead of two numbers "Time" and "CPU" in each
>> row, show me two numbers "CPU before" and "CPU after". And instead of
>> "Iterations," which I don't care about, show me "Ratio" — i.e. "After"
>> divided by "Before," so that lower numbers are better.
>>
>> (2) I'd like the paper to contain a little section on naming. What verbs
>> were considered, and why were "displace" and "remove" chosen? Why does
>> "pq.displace_top()" conserve the number of live objects but
>> "std::displace_heap" leave an extra object in a moved-from state? This
>> section needn't be long, and it probably *shouldn't* be phrased as a
>> question to LEWG; it should simply explain the reasons these names were
>> considered good, and at least one reason why other plausible names were
>> considered bad.
>> I know you and I specifically have had the naming discussion already, so
>> I
>> assume I should like the names you chose. But I'm not sure I remember
>> *why*
>> I liked them. Remind me, in the paper. ;) I do recall that
>> "std::remove_heap" leaves the tail in a moved-from state analogously to
>> "std::remove" and "std::remove_if". I *don't* recall whether we
>> considered
>> "std::shift_heap", since std::shift_{left,right} are also algorithms that
>> produce moved-from tails.
>>
>> (3) The one place you say "unspecified state" I think you should say
>> "moved-from state." Not only is that clearer, I think we actually intend
>> to
>> *guarantee* that (for types like unique_ptr whose moved-from state is not
>> unspecified).
>>
>> (4) Stylistically, I think "Technical specification" should be called
>> "Proposed wording" and should come last in the paper (before
>> "Acknowledgments" but after "Benchmarks"), to make it easy to find and to
>> scroll to. I'd also rename "Reference implementation" to "Implementation
>> experience."
>>
>> (5) I'm sure we've discussed this already, but I'd like to see some
>> discussion preserved in the paper.— `pq.displace_top()` could be (thought
>> of / implemented) as either your
>> T t = std::displace_heap(c.begin(), c.end()); c.pop_back(); return t;
>> or my own fork's
>> std::pop_heap(c.begin(), c.end()); return c.displace_back();
>> The latter works even for "relocate-only types," i.e., it does not
>> require
>> T to have a moved-from state. But it depends on e.g. `vector` to have a
>> `displace_back()` method, and just generally is more invasive than your
>> proposal. Your proposal (the former) requires T to have a moved-from
>> state,
>> but is much less invasive and thus much more achievable politically. I
>> believe we also examined the operations involved and decided that the
>> former was actually more efficient (required fewer operations), but I
>> don't
>> remember the details. It would be nice to have this analysis preserved in
>> the paper. The analysis might usefully end with a reassuring assertion
>> such
>> as "A sufficiently smart implementation might use either algorithm, since
>> they produce the same results for value-semantic types." In fact, you
>> could
>> even link to Giuseppe D'Angelo's paper P4102R0 "Container insertion and
>> erasure should be allowed to relocate"
>> <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2026/p4102r0.html>
>> in
>> the just-released April mailing!
>>
>> Cheers and HTH,
>> –Arthur
>>
>>
>> On Sun, Mar 8, 2026 at 5:26 PM Alexey Sidorin
>> <alexey.v.sidorin_at_[hidden]>
>> wrote:
>>
>> > Hello again.
>> > Sorry for a long delay, but it took me some time to update the document
>> > and the reference implementation. But finally, there is an update.
>> > 1. extract_heap_top() renamed to displace_top()
>> > 2. Added remove_heap function
>> > 3. Changed pop_heap wording (remove_heap() + pop_back())
>> > 4. Added benchmark results for `pop_heap() + pop_back()` against
>> > `remove_heap() + pop_back()`. I wished to recheck my claim about
>> potential
>> > performance improvements.
>> > 5. Added motivation for adding freestanding functions
>> > 6. Different minor improvements.
>> >
>> > Thank you in advance.
>> >
>> > ---
>> > Best regards,
>> > Aleksei Sidorin.
>
>
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>