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?

Electrotype

Have you tried std::unique_ptr<int> myInt{std::move(queue.top())}? – Amaranth

Yup, gives the same error message. – Electrotype

how about using std::map instead of std::priority_queue? – Trod

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.

Enterogastrone

The practical reason has to do with the difficulty of creating an exception-safe "extract element and modify container" method. So C++ std container-editing functions do not extract elements, and element extractors do not modify the container, as a general rule. – Conchoid

@Yakk Thanks. Can you also explain why std::queue implements a non-const front() method? – Electrotype

@Chris: I think priority_queue only provides const access to its elements because otherwise one would be able to break invariants (namely, the elements ordering according to the comparison function). queue doesn't have such invariants so it's fine to allow you to modify its elements. – Enterogastrone

Yep. If you changed the front element of the priority_queue, you'd break the ordering requirements of the container. And most std containers with such invariants break hard if you violate the invariants: the code tends to be written and use those assumptions to run faster than it could otherwise... – Conchoid

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

};

Ermentrude

Shouldn't you also be std:moveing for the return top line? – Neonate

I suppose you should... but it's done automatically because you're returning a local variable. For completeness you are correct though. – Ermentrude

No you shouldn't. It's always implied and not a useful C++ idiom. – Valenta

This sort of thing is not exception safe - if the return by value causes a copy which throws an exception the value is lost forever. – Ives

@ChrisHartman True, but the use-case is for objects that are only move-assignment-able, otherwise we wouldn't have this issue (and you could just use top()). It's your duty to ensure that the move assignment cannot throw an exception. – Ermentrude

@AntonioSanchez Agreed, I just wanted to make sure the point was clear. I can see an argument for an extension (using SFINAE) to containers to allow "pop_top()" / back_and_pop_back()" / whateverYouWantToCallIt if there are noexept moves. – Ives

Answer 3

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

Cytology

Answer 4

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

Cyd

From my understanding, this is a very dangerous solution. You push a unique pointer into the priority queue and this just saves the raw pointer in the queue. Afterwards, you pop it and create a new unique pointer. You now have the original unique pointer and the new unique pointer both pointing to the same object. This is undefined behavior! See also https://mcmap.net/q/831997/-c-multiple-unique-pointers-from-same-raw-pointer/447490 – Electrotype

@Electrotype no. release() will empty out the first original unique_ptr (don't mistake it with get()). That is why I am accepting an xvalue for push() to tell the user that the unique_ptr that they are sending in will be diminished. To call push you need to do queue_with_extra_steps.push( std::move(unique_pointer) ), and then the unique_pointer will be empty. – Cyd

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.

Aulea