How to move items from an STL priority queue

Question

The C ++ STL priority queue has the void pop () method and the const ref top () method. Thus, if you want to move items from the queue, you should do something like this:

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

This effectively translates the vertex not into a constant, so it can be moved (rather than copied). I don’t like this code, because a forced move can invalidate the priority queue invariants, which should not matter due to pop music, but everything can go wrong.

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

Answer 1

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

• std :: vector
• std :: push_hap
• std :: pop_heap

Using these building blocks, the implementation is trivial, and you can easily implement a moving pop operation. The following list 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); } };