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.

Mckeever

priority_queue::top() returns const reference, so even after move it is still an lvalue. – Pacifist

@C.R. std::move is just a cast to an rvalue reference, so any lvalue of type const T will be converted to const T&&, which is an rvalue -- even though you cannot acquire resources through it. – Runnel

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

Menispermaceous

Thanks, but I still get errors, because my operator= is missing (error comes from the line l.pop()). Can we get around this error aswell? – Mckeever

@Mckeever Edited; just provide the assignment op. – Menispermaceous

It might be necessary to carefully formulate the requirements on the moved object: it still has to be able to be compared with, as top+pop are not "atomic". Maybe someone could propose an extension? – Runnel

@DyP Correct, and indeed something I failed to consider. But (ignoring multithreading for now), would this be an actual issue? If the top() is immediately followed by a pop(), would the comparator ever be invoked on the moved-from top item? – Menispermaceous

@Angew I think it wouldn't be necessary (pop is defined in terms of pop_heap); however it is error prone as you can add elements to the queue after moving the top out. So maybe an "atomic" (not in terms of concurrency) pop+top is possible, returning the element by value. – Runnel

@DyP That's what I meant with "such code should be encapsulated in a function." I will edit the answer to spell it out explicitly. – Menispermaceous

@Angew No, the answer is fine, I just didn't put your comment in its context ;) – Runnel

There's already a proposal in the the isocpp proposals forum from May to solve this issue, see groups.google.com/a/isocpp.org/d/msg/std-proposals/TIst1FOdveo/… – Runnel

Answer 2

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.

Weigand

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

UPDATE. As @FrançoisAndrieux pointed out, in real code it's better to: avoid using priority_queue_top_and_pop (which is technically UB); inherit extended_priority_queue from std::priority_queue privately in order to avoid unwanted implicit conversions.

Milanmilanese

This solution exposes the user to accidentally using extended_priority_queue polymorphically, for example object slicing or owning with the wrong kind of pointer (ex. std::unique_ptr<std::priority_queue<T>> owning a extended_priority_queue<T>. It would make it safe if private inheritance was used, at the cost of having to implement the interface of std::priority_queue in extended_priority_queue. – Suppletion

@FrançoisAndrieux, there will be no slicing as such, since extended_priority_queue adds no new data members. And in fact I reply on polymorphism in priority_queue_top_and_pop implementation. Two questions: 1. Do you see any problems with the current extended_priority_queue implementation or are you worried about a potential future version that may add data members? 2. How would one implement priority_queue_top_and_pop with private inheritance? I think you need this function, because you can't always replace the underlying type. For example, it may be coming from a library. – Milanmilanese

There is both a risk of future changes causing slicing, and an immediate risk of accidentally deleting extended_priority_queue using a std::priority_queue*. There is also no obstacle to private inheritance, that doesn't change what extended_priority_queue can access. But more importantly, looking at your helper function, that static_cast is Undefined Behavior unless PriorityQueue is extended_priority_queue. You can't cast an object of base type to one of a derived type if it isn't actually that derived type. – Suppletion

Hmm, good point. Do you think there is any way to extract an element from an existing std::priority_queue? May be, some reinterpret_cast / memcpy trick? – Milanmilanese

There is no memcpy or cast trick you can do, inheritance is the correct solution, but it should be private. The standard library provides the c member for this purpose which requires inheritance. – Suppletion

Meaning that there is no way to move an element out of an std::priority_queue that you got from a library? This is sad. Anyway, thanks for the comments! I've updated the post. – Milanmilanese

Answer 4

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.

Jaipur

Answer 5

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.

Venturesome

Thanks, but any solution to the missing operator= problem from the line l.pop()? – Mckeever

You'd need to define that function. Currently you are defining the move-constructor, but not the move-assignment operator. – Venturesome

The top() function does not have a non-const overload because any modification to an element on the queue would risk breaking queue invariants. Note that the value of an item put into the priority queue affects the ordering of it, unlike a list which only stores elements in sequence. – Weigand

Answer 6

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.

Dormitory