Move Out Element of Std Priority_Queue in C++11

Move out element of std priority_queue in C++11

That seems to be an oversight in the design of std::priority_queue<T>. There doesn't appear to be a way to directly move (not copy) an element out of it. The problem is that top() returns a const T&, so that cannot bind to a T&&. And pop() returns void, so you can't get it out of that either.

However, there's a workaround. It's as good as guaranteed that the objects inside the priority queue are not actually const. They are normal objects, the queue just doesn't give mutable access to them. Therefore, it's perfectly legal to do this:

MyClass moved = std::move(const_cast<MyClass&>(l.top()));
l.pop();

As @DyP pointed out in comments, you should make certain that the moved-from object is still viable for being passed to the queue's comparator. And I believe that in order to preserve the preconditions of the queue, it would have to compare the same as it did before (which is next to impossible to achieve).

Therefore, you should encapsulate the cast & top() and pop() calls in a function and make sure no modifications to the queue happen in between. If you do that, you can be reasonably certain the comparator will not be invoked on the moved-from object.

And of course, such a function should be extremely well documented.

---

Note that whenever you provide a custom copy/move constructor for a class, you should provide the corresponding copy/move assignment operator as well (otherwise, the class can behave inconsistently). So just give your class a deleted copy assignment operator and an appropriate move assignment operator.

_{(Note: Yes, there are situations when you want a move-constructible, but not move-assignable class, but they're extremely rare (and you'll know them if you ever find them). As a rule of thumb, always provide the ctor and assignment op at the same time)}

How to move elements out of STL priority queue

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

std::move() with priority_queue.top()

priority_queue::top returns a const& to the top element.

std::shared_ptr<Base> p = queue.top();

The line above creates a new shared_ptr which now shares ownership of the top element with the shared_ptr that's in the priority_queue, so use_count is 2.

std::move doesn't affect the result because moving a const object will call the shared_ptr copy constructor, same as the line above.

To keep use_count at 1, use

std::shared_ptr<Base> const& p = queue.top();

C++ priority queue swapping contents

Is there a way I could possibly bend std::priority_queue to do my
bidding without making it extremely ugly?

You could write a wrapper that hides the predicate and uses inheritance behind the scenes. However, that seems overkill.

If not then could I perhaps re-structure my class to do the same
thing, but still use std::priority_queue?

You could wrap the access to the queues in functions. Then use a bool or integer variable to check which queue needs to be accessed.

Otherwise could I maybe re-use most of the heapify logic in the std
library to achieve this?

This sounds like the best option, based on what you explained. Store each priority_queue in a std::vector and use the std::make_heap, std::push_heap and std::pop_heap functions to manage the heap structure. If you keep all priority queues in a std::array<std::vector<int>, 3>, you can use std::rotate to perform the logic you described. In addition, you would need to keep a boolean variable indicating which predicate to use for the heap operations.

How does std::priority_queue accomplish O(log n) insertion?

while in a priority queue one might need to add elements somewhere in the middle of the vector, in which case all elements that follow have to be shifted to the right

No. The right shift does not occur.

The new element is added to the end, at index i: O(1)

Then its priority is compared to its parent at index i/2 and swapped if of higher priority.

If a swap occurs, compare the next parent.

Repeat above 2 steps until at at index 0. O(log(i))

---

Related Topics