I’ve been using `std::pop_heap`

for a combined pop-push operation by appending a new element at the end, then calling `std::pop_heap`

and then removing the last element. It used to work just fine, and it still works in the latest libstdc++ but not the latest libc++.

I used this as an optimization, relying on what cppreference.com says about it:

Swaps the value in the position

`first`

and the value in the position`last-1`

and makes the subrange`[first, last-1)`

into aheap. This has the effect of removing the first element from the heap defined by the range`[first, last)`

.

But now that I found it to break, I couldn’t really find any confirmation as to what the actual standard says. Does anybody know? I’d appreciate the help.

I looked into the algorithms in both libc++ and libstdc++, and they seem to both work in a very similar way, except *I think* (as far as I could understand) that the GNU one sifts down excluding the last element, but the LLVM one includes all elements, and in result it can push that last element up when doing the initial sifting…

This should be relatively easy to fix, but of course the real question is whether it the precondition of `std::pop_heap`

is that `[first, last)`

is a valid heap, or whether we only need `[first, last - 1)`

(which is what I’ve been doing).

Another question is: **does my pop-push optimization make sense?** At the first glance: yes; but since that “bottom-up heapsort” strategy is used (first sift the hole all the way down, and then sift up), and the new element does not necessarily belong at the bottom, maybe it is less of an optimization.

I plan to do some benchmarking soon, but I’d love to know what y’all think, especially on the standard/correctness issue.