On Tue, 1 Jul 2025 at 21:27, Alexey Sidorin via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> 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.
>
> 1. Problem statement
>
> In order to extract the top element from std::priority_queue, we have to
> write something like this:
> auto x = queue.top(); // Copy constructor or copy assignment.
> queue.pop();
>
> Unfortunately, we cannot move a top value from the queue because top() is
> of const_reference type (
> https://eel.is/c++draft/priority.queue#priqueue.members).
> The first problem is that this can cause a performance hit if the value
> type is expensive to copy (a structure containing large strings, etc.).
> The second problem is that this also makes impossible to use
> priority_queue with move-only types.
> I've made a search in chromium sources showing that almost all heap
> structure usage have a similar pattern:
>
> std::pop_heap(msg_queue.begin(), msg_queue.end());
> *event = std::move(msg_queue.back());
> msg_queue.pop_back();
> (
> https://github.com/search?q=repo%3Achromium%2Fchromium%20pop_heap&type=code
> )
>
> I think this clearly indicates that we can have a better interface here.
>


See https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2024/p3182r1.html


2. Proposed changes
>
> The idea is to provide `extract_top()` method behaving like pseudo-code
> below:
> T extract_top() {
> T val = std::move_if_noexcept(container.front());
> pop();
> return val;
> }
>
> I've made a reference implementation in my libc++ fork if anyone is
> interested: https://github.com/a-sid/llvm-project/pull/1/files.
>
> The summary of the changes proposed is the following:
> 1. Add a method `extract_top()` to `std::priority_queue`:
> template <class _Tp, class _Container, class _Compare>
> constexpr _Tp priority_queue<_Tp, _Container, _Compare>::extract_top();
>
> This method will return the top value of the queue and remove it from the
> queue with restoring the heap property of the data structure.
>
> 2. Add symmetric functions to <algorithm> header:
> template <class RandomAccessIterator>
> constexpr iterator_traits_t<RandomAccessIterator>::value_type
> extract_heap_top(RandomAccessIterator first, RandomAccessIterator
> last);
>
> template <class RandomAccessIterator, class Compare>
> constexpr iterator_traits_t<RandomAccessIterator>::value_type
> extract_heap_top(RandomAccessIterator first, RandomAccessIterator
> last, Compare comp);
>
> These functions will return the top value of the queue and remove it from
> the queue with restoring the heap property of the data structure. Unlike
> pop_heap, these functions will leave the last element in an unspecified
> state.
>
> 3. Add corresponding range object template:
> template<random_access_iterator I, sentinel_for<I> S, class Comp =
> ranges::less,
> class Proj = identity>
> requires sortable<I, Comp, Proj>
> constexpr iterator_traits<I>::value_type
> ranges::extract_heap_top(I first, S last, Comp comp = {}, Proj proj
> = {});
>
> template<random_access_range R, class Comp = ranges::less, class Proj =
> identity>
> requires sortable<iterator_t<R>, Comp, Proj>
> constexpr iterator_traits<iterator_t<R>>::value_type
> ranges::extract_heap_top(R&& r, Comp comp = {}, Proj proj = {});
>
> These functions will return the top value of the queue and remove it from
> the queue with restoring the heap property of the data structure. Again,
> the last element is left in an unspecified state.
>
> 3. Related work
> There was already another proposal which pointed that const reference
> interface makes priority_queue unusable for move-only types:
> https://lists.isocpp.org/std-proposals/2021/02/2390.php. As I understand,
> this proposal haven't met strong objections, but it looks like it was
> abandoned.
>
> Thank you in advance for any feedback.
>
> ---
> Best regards,
> Aleksei Sidorin.
>
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>