14

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?

6
  • 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, 2014 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, 2014 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, 2014 at 17:16
  • 1
    Related/duplicate: Move out element of std priority_queue in C++11
    – dyp
    Feb 26, 2014 at 17:51
  • 2

2 Answers 2

12

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);
    }
};
3
  • 2
    +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, 2014 at 17:21
  • This should get the job done, but it's pretty verbose.
    – Ant6n
    Mar 2, 2014 at 1:59
  • 3
    The std::move in return std::move(result) is redundant.
    – jupp0r
    Jul 14, 2016 at 11:55
0

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)

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.