This is an archive of the discontinued LLVM Phabricator instance.

priority_queue::replace_top(x)
Needs ReviewPublic

Authored by Quuxplusone on Feb 4 2019, 8:11 PM.

Details

Summary

Add a fast replace_top method to std::priority_queue.

Also std::poke_heap(first, last), which assumes that the given range is in max-heap order *except* for the first element, which needs to be put into its proper place. This is just like push_heap, except that push_heap assumes the *last* element is out of order, whereas poke_heap assumes the *first* element is out of order.

The changes in <queue> could use _VSTD::poke_heap instead of __sift_down, but they do not, in order to keep the <queue> changes usable as a single-file patch (in case someone wants to take the <queue> changes without the <algorithm> changes).

The poke_heap approach would replace the last line of each new method with this line instead:

_VSTD::poke_heap(c.begin(), c.end(), comp);

I did this patch a while back for a blog post, and initially didn't intend to do anything else with it. Just recently I learned that people (well, Simon Brand and @Leandros) apparently want it enough to tweet about the existence of the patch
https://twitter.com/ArvidGerstmann/status/1071033081719676928
so I figure I should take the next step and actually post it for review.
(The blog post in question was https://quuxplusone.github.io/blog/2018/04/27/pq-replace-top/ )

Diff Detail

Repository
rCXX libc++

Event Timeline

Quuxplusone created this revision.Feb 4 2019, 8:11 PM

Arthur - I'm sorry to say that this will go nowhere.
You're introducing non-reserved identifiers into libc++, which can cause legal code to break.

For example:

#define poke_heap 9+7
#include <queue>

Same with replace_top
Users are prohibited from doing this for names that is mentioned in the standard, but neither of those fall into that category.
that's why __sift_down is named how it is, for example - users can't define them as a macro.

@mclow.lists: Easy peasy! Please take another look.

@mclow.lists: Easy peasy! Please take another look.

Now no one outside of libc++ can call it (legally)

@mclow.lists wrote:

Now no one outside of libc++ can call it (legally)

True. Is that a problem for libc++? I mean, what you're forced to do in the absence of this patch is to call __sift_down, which also can't be done (legally).

Anyway, I'd like to see if anyone else registers an opinion on the desirability of this feature.

No one is "forced" to call __sift_down. In fact, it's explicitly forbidden by the standard.

Reverted names back to friendly names. (The uglified __names were a conforming extension; but the friendly names are what people would actually want to use. As this patch is likely going to be stagnant on Phab for a while, I'd rather have it be in the state that's directly apply-able for anyone who does want to merge it locally.)

I think this functionality might be interesting, but trying to get this into libc++ before it is standardized is definitely putting the cart before the horse. I understand that putting the patch here may make it easier for people to apply it to their local copy of libc++. Hopefully not many people think of themselves as vendors and maintain their own libc++ :-).

include/queue
549

This should instead be #if _LIBCPP_STD_VER > 23, or whatever standard version you target with this feature.

test/libcxx/containers/container.adaptors/priority.queue/priqueue.members/replace_top_rvalue.pass.cpp
10

This should be UNSUPPORTED until the standard version where the feature is being added.

@Quuxplusone Please re-ping this when/if this feature makes it into the standard so that we avoid re-doing the work.