How to move elements out of STL priority queue

Question

C++'s STL priority queue have a void pop() method, and a const ref top() method. Thus, if you want to move elements out of the queue, you have to do something like this:

T moved = std::move(const_cast<T&>(myQueue.top())));
myQeue.pop();

This effectively casts the top to not a constant, so that it can be moved (rather than copied). I don't like this code, because the forced move may invalidate the invariants of the priority queue, which should not matter because of the pop, but things could go wrong.

Is there a better way to accomplish the pop/move? Why is there no T&& top_and_pop() function?

Strongminded

Aren't you moving the copy the top function returns? Why do that? It will stop any RVO - what are your trying to achieve? – Kop

Top returns a (const) reference. In this particular case, I want to move the objects from the priority queue to a vector. But it doesn't really matter. – Strongminded

I'm not sure but it looks like, in context to C++03, top_and_pop didn't make much sense since there could only be copies in any case, so adding a convenience method that wouldn't make any performance difference, only having one line less of code, seems like unnecessary. Now with move semantics and members of the underlying container being able to be moved, this seems to make sense, but the interface didn't get any change... I'm curious why too. – Deceased

Related/duplicate: Move out element of std priority_queue in C++11 – Pommard

Related: How to get a non-const top element from priority_queue with user-defined objects? and Getting a unique_ptr out of a priority queue – Pommard

Relevant discussions in isocpp/future proposals: groups.google.com/a/isocpp.org/d/topic/std-proposals/… and groups.google.com/a/isocpp.org/d/topic/std-proposals/… – Pommard

Answer 1

std::priority_queue is basically a thin layer on top of the heap algorithms. You can easily create your own priority queue with:

• std::vector
• std::push_heap
• std::pop_heap

Using these building blocks, the implementation is trivial, and you can easily implement a moving pop operation. The following listing contains a minimal, working implementation:

template <typename Type, typename Compare = std::less<Type>>
class queue
{
private:
    std::vector<Type> _elements;
    Compare _compare;
public:
    explicit queue(const Compare& compare = Compare())
        : _compare{compare}
    { }
    void push(Type element)
    {
        _elements.push_back(std::move(element));
        std::push_heap(_elements.begin(), _elements.end(), _compare);
    }
    Type pop()
    {
        std::pop_heap(_elements.begin(), _elements.end(), _compare);
        Type result = std::move(_elements.back());
        _elements.pop_back();
        return std::move(result);
    }
};

Aric

+1 I'd also should check/static_assert for is_nothrow_move_constructible (even in a minimal implementation), otherwise you might lose an element in pop. – Pommard

This should get the job done, but it's pretty verbose. – Strongminded

The std::move in return std::move(result) is redundant. – Sse

Answer 2

This is indeed a flaw in std::priority_queue. But you can easily extend it like this:

template <
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>>
class priority_queue : public std::priority_queue<T, Container, Compare> {
public:
  T top_and_pop() {
    std::pop_heap(c.begin(), c.end(), comp);
    T value = std::move(c.back());
    c.pop_back();
    return value;
  }

protected:
  using std::priority_queue<T, Container, Compare>::c;
  using std::priority_queue<T, Container, Compare>::comp;
};

(based on @nosid answer)

Stempson