ideas icon indicating copy to clipboard operation
ideas copied to clipboard

Add an ability to move the top element from std::priority_queue

Open a-sid opened this issue 10 months ago • 4 comments

There is an issue that has bothered me for a long time. 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) . This can cause a performance hit if the value type is expensive to copy (large strings, etc.).

The idea is to provide something like a pop(T&) method overload:

// Implementation example. noexcept-based computations and choices are omitted.
template <typename U>
void pop(U& to) {
  to = std::move(container.front());
  pop();
}

// Usage:   
T x;  // or std::optional<T>
queue.pop(x);  // move if T::operator=(T&&) is noexcept

Alternative interface:

T extract_top() {
  T val = std::move(container.front());
  pop();
  return val;
}

I like it even more than the first one.

a-sid avatar Feb 24 '25 11:02 a-sid