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(); 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