1

I have a unique_ptr in a priority_queue and I want to remove it from that collection and put it on a deque while maintaining the ownership semantics of unique_ptr. But I can't find a way to pull it off the priority_queue without a compile error: "attempting to reference a deleted function". What's the right way to accomplish this?

struct MyStruct {
    int val = 2;

    MyStruct(const int val) : val(val) {}
};

void testDeque() {
    std::priority_queue<std::unique_ptr<MyStruct>> q1;
    q1.emplace(std::make_unique<MyStruct>(10));
    std::deque<std::unique_ptr<MyStruct>> q2;
    q2.push_back(q1.top()); // <- compiler error "attempting to reference a deleted function"
    q2.push_back(std::move(q1.top())); // <- compiler error "attempting to reference a deleted function"
    q1.pop();
}
mentics
  • 6,852
  • 5
  • 39
  • 93
  • 2
    Seem like you are not supposed to do that, as [top() returns a const_reference](http://en.cppreference.com/w/cpp/container/priority_queue/top). – Bo Persson Oct 28 '17 at 21:14
  • This is 100% the duplicate suggested by @MateuszDrost, the accepted answer there is even the same as the most upvoted answer here. – Nir Friedman Oct 29 '17 at 03:45

3 Answers3

1

Make your own heap. All the heap functions are already in the <algorithm> header for you.

std::vector<std::unique_ptr<MyStruct>> q1;

auto push = [&q1](std::unique_ptr<MyStruct> p) {
    q1.push_back(std::move(p));
    std::push_heap(q1.begin(), q1.end());
};

auto pop = [&q1]() {
    std::pop_heap(q1.begin(), q1.end());
    auto result = std::move(q1.back());
    q1.pop_back();
    return result;
};

push(std::make_unique<MyStruct>(10));
std::deque<std::unique_ptr<MyStruct>> q2;
q2.push_back(pop());
Benjamin Lindley
  • 101,917
  • 9
  • 204
  • 274
  • So are you saying that because of the way the interface to priority_queue is defined, it can't do what I'm trying to and I have to use something else? – mentics Oct 28 '17 at 21:32
  • @taotree: You could use `std::priority_queue`, but not directly with `std::unique_ptr`. You could wrap it in another struct with a mutable member, for example. But I think making your own little priority queue class with the desired interface would be better in the long run, and trivial to implement. (just wrap the lambdas I provided up into a class). – Benjamin Lindley Oct 28 '17 at 21:36
0

If priority_queue::top returned a non-const reference, the user could change the value of the element, breaking the priority_queue internal invariants that make it work. Citing cppreference:

Working with a priority_queue is similar to managing a heap in some random access container, with the benefit of not being able to accidentally invalidate the heap.

So, your priority_queue is in invalid state between std::move(q1.top()) and q1.pop(): the pointer is null after the move, so it is actually the smallest element now, not the greatest, which violates the class invariants. While this might work in practice, it is generally bad to rely on implementation details rather than on the documented behavior.

You may write your own priority_queue based on the std::heap* functions from <algorithm>, as Benjamin Lindley suggests in his post, that allows to change the values stored. Alternatively, you can use some sorted container, like std::set, sacrificing the benefits of a heap.

lisyarus
  • 15,025
  • 3
  • 43
  • 68
  • He can just write his own `Compare` function where `null`s are the greatest elements. – Mateusz Drost Oct 28 '17 at 21:50
  • @MateuszDrost For sure. Still, `priority_queue` has no way to get a non-const reference to it's top element, and doing a `const_cast` would still violate the class interface: it simply doesn't support changing the stored values. – lisyarus Oct 28 '17 at 21:53
-1

As top returns const_reference which cannot be moved you should const_cast it:

q2.push_back(std::move(const_cast<std::unique_ptr<MyStruct>&>(q1.top())));

move left object in valid state, so following q1.pop() is completely safe.

Mateusz Drost
  • 1,171
  • 10
  • 23