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?

Aren't you moving the copy the `top` function returns? Why do that? It will stop any RVO - what are your trying to achieve? — doctorlove, Feb 26 '14 at 16:54
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. — Ant6n, Feb 26 '14 at 16:56
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. — oblitum, Feb 26 '14 at 17:16
Related/duplicate: [Move out element of std priority_queue in C++11](http://stackoverflow.com/q/20149471/420683) — dyp, Feb 26 '14 at 17:51
Related: [How to get a non-const top element from priority_queue with user-defined objects?](http://stackoverflow.com/q/16754745/420683) and [Getting a unique_ptr out of a priority queue](http://stackoverflow.com/q/16661038/420683) — dyp, Feb 26 '14 at 17:53
Relevant discussions in isocpp/future proposals: https://groups.google.com/a/isocpp.org/d/topic/std-proposals/Tp_HjVlXa7M/discussion and https://groups.google.com/a/isocpp.org/d/topic/std-proposals/TIst1FOdveo/discussion — dyp, Feb 26 '14 at 17:56

nosid · Accepted Answer · 2014-02-26T19:26:25.353

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

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);
    }
};

+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`. — dyp, Feb 27 '14 at 17:21

score 0 · Answer 2 · answered Jul 16 '18 at 18:43

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)

How to move elements out of STL priority queue

2 Answers2

Linked

Related