Получение уникального_птима из очереди приоритетов

Question

Я поддерживаю набор unique_ptr экземпляров в priority_queue. В какой-то момент я хочу получить первый элемент и удалить его из очереди. Однако это всегда приводит к ошибке компилятора. См. Пример кода ниже.

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

Это производит следующее сообщение об ошибке компилятора (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; 
    ^

Изменение кода для использования queue как в this question исправляет ошибку и код компилируется нормально.

Невозможно сохранить unique_ptr s в priority_queue или я что-то упустил?

Answer 1

std::priority_queue::top() возвращает ссылку на константу, поэтому вы не можете ее перемещать. Глядя на public interface of priority_queue, нет способа получить неконстантную ссылку, которую вы можете переместить (что обязательно для unique_ptr, у нее нет конструктора копирования).

Решение: заменить unique_ptr с shared_ptr, чтобы иметь возможность копировать их (и не только перемещать их).

Или, конечно, использовать другой вид контейнера в целом (но если вы выбрали priority_queue в первую очередь, это, вероятно, неприемлемо для вас).

Возможно, вы также можете использовать «защищенный член взлома» для доступа к защищенному элементу c (базовый контейнер), но я бы не рекомендовал его, это довольно грязно и, скорее всего, UB.

Answer 2

Согласен, это невероятно раздражает. Почему это дает мне std::move элементов в очереди, а затем не давайте мне не трогать их? У нас больше нет копии оригинала, поэтому мне нужен неконстантный объект, когда я делаю top() и pop().

std::priority_queue, добавляя метод pop_top(), который делает оба одновременно. Это должно сохранить любое упорядочение очереди. Однако это зависит от C++ 11. Следующая реализация работает только для gcc-компиляторов.

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 

};