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" 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.