Move out element of std priority_queue in C++11

Question

Minimal working example.

#include <cassert>
#include <list>
#include <queue>
//#define USE_PQ

struct MyClass
{
    const char* str;
    MyClass(const char* _str) : str(_str) {}
    MyClass(MyClass&& src) { str = src.str; src.str = nullptr; }
    MyClass(const MyClass&) = delete;
};

struct cmp_func
{
    bool operator() (const MyClass&, const MyClass&) const
    {
        return true;
    }
};

typedef std::priority_queue<MyClass, std::vector<MyClass>, cmp_func> pq_type;

#ifdef USE_PQ
MyClass remove_front(pq_type& l)
{
    MyClass moved = std::move(l.top());
    // error from the above line:
    // use of deleted function ‘MyClass::MyClass(const MyClass&)’
    l.pop();
    return std::move(moved);
}
#else
MyClass remove_front(std::list<MyClass>& l)
{
    MyClass moved = std::move(l.front());
    l.erase(l.begin());
    return std::move(moved);
}
#endif

int main()
{
    const char* hello_str = "Hello World!";
    MyClass first(hello_str);
#ifdef USE_PQ
    pq_type l;
    l.push(std::move(first));
    MyClass moved = remove_front(l);
#else
    std::list<MyClass> l;
    l.push_back(std::move(first));
    MyClass moved = remove_front(l);
#endif
    assert(moved.str);
    assert(!first.str);
    return 0;
}

So this works. Now remove the comment signs from line 4 and it says that copy constructors would be needed (mine is deleted). Also, it misses operator=. Questions:

• What is the difference here?
• Can the problem be fixed? If yes, how, if no, why not?

Note: You can also use boost's priority_queue for your answer, but I got the same error with it.

Answer 1

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

Answer 2

There might be a very good reason why there is no non-(const-ref) top(): modifying the object would break the priority_queue invariant. So that const_cast trick is probably only going to work if you pop right after.

Answer 3

It's easy to extend std::priority_queue, since it exposes the underlying container as a protected member:

template <
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>>
class extended_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;
};

If you need to move an element out of std::priority_queue instance, you could use extended_priority_queue to implement a helper function:

template<typename PriorityQueue>
auto priority_queue_top_and_pop(PriorityQueue& queue) ->
    typename PriorityQueue::value_type {
  return static_cast<extended_priority_queue<
      typename PriorityQueue::value_type,
      typename PriorityQueue::container_type,
      typename PriorityQueue::value_compare>&>(queue).top_and_pop();
}

Answer 4

What is the difference here?

MyClass remove_front(pq_type& l)
{
    MyClass moved = std::move(l.top()); // PROBLEM
    l.pop();
    return std::move(moved);
}

std::priority_queue::top returns a const value_type&, so you cannot call std::move (which takes a T&&).

MyClass remove_front(std::list<MyClass>& l)
{
    MyClass moved = std::move(l.front());
    l.erase(l.begin());
    return std::move(moved);
}

std::list::front has an overload that returns a reference, so it has a way to bind to a T&&.

I'm unsure why top does not have a non-const overload (potentially an oversight in the standard?). You can use const_cast to get around that, but make sure you write thorough comments describing what you are doing and why.

Answer 5

The top ranked answer looks good, but unfortunately, it is incompatible with -D_GLIBCXX_DEBUG. Example:

#include <iostream>
#include <memory>
#include <queue>
#include <vector>

struct T {
  int x;
  std::shared_ptr<int> ptr;
  T(int x, std::shared_ptr<int> ptr) : x(x), ptr(ptr) {}
};
struct Compare {
  bool operator()(const T& x, const T& y) {
    return *x.ptr < *y.ptr;
  }
};
int main() {
  auto ptr1 = std::make_shared<int>(3);
  auto ptr2 = std::make_shared<int>(3);
  std::priority_queue<T, std::vector<T>, Compare> f;
  f.emplace(3, ptr1);
  f.emplace(4, ptr2);
  T moved = std::move(const_cast<T&>(f.top()));
  f.pop();
  std::cerr << moved.x << "\n";
}

If you run this with g++ foo.cpp -D_GLIBCXX_DEBUG -O0 -g -std=c++11 && ./a.out on GCC (not clang, the macro will not do anything in that case) you will trigger a null pointer dereference in the comparator.

Answer 6

Depending on what type you want to store in the priority queue, an alternative to Angew's solution, that avoids the const_cast and removes some of the opportunities for shooting oneself in the foot, would be to wrap the element type as follows:

struct Item {
    mutable MyClass element;
    int priority; // Could be any less-than-comparable type.

    // Must not touch "element".
    bool operator<(const Item& i) const { return priority < i.priority; }
};

Moving the element out of the queue would then be done as such:

MyClass moved = std::move(l.top().element);
l.pop();

That way, there are no special requirements on the move semantics of MyClass to preserve the order relation on the invalidated object, and there will be no section of code where invariants of the priority queue are invalidated.