Getting a unique_ptr out of a priority queue

Question

I am maintaining a set of unique_ptr instances in a priority_queue. At some point, I want to get the first element and remove it from the queue. However, this always produces a compiler error. See sample code below.

int main ()
{
  std::priority_queue<std::unique_ptr<int>> queue;
  queue.push(std::unique_ptr<int>(new int(42)));

  std::unique_ptr<int> myInt = std::move(queue.top());
  return 1;
}

This produces the following compiler error (gcc 4.8.0):

uptrtest.cpp: In function ‘int main()’: uptrtest.cpp:6:53: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = int; _Dp = std::default_delete<int>]’    std::unique_ptr<int> myInt = std::move(queue.top());
                                                     ^ In file included from /usr/include/c++/4.8/memory:81:0,
                 from uptrtest.cpp:1: /usr/include/c++/4.8/bits/unique_ptr.h:273:7: error: declared here
       unique_ptr(const unique_ptr&) = delete;
       ^

Changing the code to use queue like in this question fixes the issue and the code compiles just fine.

Is there no way to keep unique_ptrs in a priority_queue or am I missing something?

Answer 1

std::priority_queue::top() returns a const reference so you can't move it. Looking at the public interface of priority_queue there is no method to get a non-const reference that you can move (which is mandatory for unique_ptr, it has no copy constructor).

Solution: replace unique_ptr with shared_ptr to be able to copy them (and not just move them).

Or, of course, use another kind of container altogether (but if you chose priority_queue in the first place, this is probably not acceptable for you).

You could also maybe use a "protected member hack" to access the protected member c (the underlying container) but I wouldn't recommend it, this is quite dirty and quite probably UB.

Answer 2

I agree, this is incredibly annoying. Why does it let me std::move elements into the queue, then give me no way of moving them out? We no longer have a copy of the original, so I need a non-const object when I do a top() and pop().

Solution: extend std::priority_queue, adding a method pop_top() that does both at once. This should preserve any ordering of the queue. It does depend on c++11 though. The following implementation only works for gcc compilers.

template<typename _Tp, typename _Sequence = std::vector<_Tp>,
    typename _Compare = std::less<typename _Sequence::value_type> >
class priority_queue: std::priority_queue<_Tp, _Sequence, _Compare> {
public:
    typedef typename _Sequence::value_type value_type;
public:

#if __cplusplus < 201103L
explicit
priority_queue(const _Compare& __x = _Compare(),
        const _Sequence& __s = _Sequence()) : 
        std::priority_queue(__x, __s) {}
#else
explicit 
priority_queue(const _Compare& __x, const _Sequence& __s) :
        std::priority_queue<_Tp, _Sequence, _Compare>(__x, __s) {}

explicit 
priority_queue(const _Compare& __x = _Compare(), _Sequence&& __s =
        _Sequence()) :
        std::priority_queue<_Tp, _Sequence, _Compare>(__x, std::move(__s)) {}
#endif

using std::priority_queue<_Tp, _Sequence, _Compare>::empty;
using std::priority_queue<_Tp, _Sequence, _Compare>::size;
using std::priority_queue<_Tp, _Sequence, _Compare>::top;
using std::priority_queue<_Tp, _Sequence, _Compare>::push;
using std::priority_queue<_Tp, _Sequence, _Compare>::pop;

#if __cplusplus >= 201103L

using std::priority_queue<_Tp, _Sequence, _Compare>::emplace;
using std::priority_queue<_Tp, _Sequence, _Compare>::swap;

/**
 *  @brief  Removes and returns the first element.
 */
value_type pop_top() {
    __glibcxx_requires_nonempty();

    // arrange so that back contains desired
    std::pop_heap(this->c.begin(), this->c.end(), this->comp);
    value_type top = std::move(this->c.back());
    this->c.pop_back();
    return top;
}

#endif

};

Answer 3

This is another ugly workaround. Personally, I like it more than the other suggested ugly workarounds. Depending on your situatation, you might need to use this one. Store raw pointers in the priority queue. Every time you pop make sure to put it in a unique pointer. Also have a destructor to clean up remaining stuff.

Here is an untested code.

class Queue_with_extra_steps {
public:
  void push( std::unique_ptr<int>&& value ) {
    queue.push( value.release() );
  }
  std::unique_ptr<int> pop() {
    if( queue.empty() ) {
      return nullptr;
    }
    std::unique_ptr<int> ans( queue.top() );
    queue.pop();
    return ans;
  }
  ~Queue_with_extra_steps() {
    while( !queue.empty() ) {
      this->pop();
    }
  }
  // Add other functions if need be.
private:
  std::priority_queue<int*> queue;
};

Answer 4

A little less ugly workaround is to create wrapper with mutable unique_ptr. You can also separate "priority data" to keep it safe from breaking the heap.

#include <iostream>
#include <queue>
#include <memory>
using namespace std;

template<typename T>
struct unique_ptr_storage{
    unique_ptr_storage(uint32_t _priority,std::unique_ptr<T> &&_ptr)
    : priority(_priority)
    , ptr(std::move(_ptr)){}
    
    mutable std::unique_ptr<T> ptr;
    std::unique_ptr<T> release()const{
        return std::move(ptr);
    }
    uint32_t priority;
    bool operator<(const unique_ptr_storage<T> &other)const{
        return priority<other.priority;
    }
};

int main() {
    std::priority_queue<unique_ptr_storage<int>> q;
    
    q.emplace(1,std::make_unique<int>(10));
    q.emplace(3,std::make_unique<int>(30));
    q.emplace(2,std::make_unique<int>(20));
    
    while(!q.empty()){
        std::unique_ptr<int> p=q.top().release();
        q.pop();
        std::cout<<*p<<std::endl;
    }
    return 0;
}

Output:

30
20
10

Answer 5

Since std::priority_queue::top() returns a const reference, we have to use some alternative approach for addressing it. Depending on your objects' life time, you may choose this solution:

1. store a const MyObject * as the value in the priority_queue
2. std::priority_queue::top() will give you an const MyObject *
3. use the const_cast (https://en.cppreference.com/w/cpp/language/const_cast) to drop the const qualifier from the pointer

With this solution, if you need to manage the objects' life time as well, you may manage the unique_ptr outside of priority_queue in another container while still leveraing priority_queue's capability for ordering your objects.