Getting a unique_ptr out of a priority queue
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_ptr
s in a priority_queue
or am I missing something?
Solution 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.
Solution 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
};