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.

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@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals