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.