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