Estrazione di unique_ptr da una coda di priorità

Question

Sto mantenendo un insieme di istanze unique_ptr in un priority_queue. Ad un certo punto, voglio ottenere il primo elemento e rimuoverlo dalla coda. Tuttavia, questo produce sempre un errore del compilatore. Vedi il codice di esempio qui sotto.

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

Questo produce il seguente errore del compilatore (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; 
    ^

Cambiare il codice per utilizzare queue come nel this question risolve il problema e il codice compila bene.

Non c'è modo di mantenere unique_ptr s in un priority_queue o mi manca qualcosa?

Answer 1

std::priority_queue::top() restituisce un riferimento const per cui non è possibile spostarlo. Guardando il public interface of priority_queue non c'è alcun metodo per ottenere un riferimento non const che è possibile spostare (che è obbligatorio per unique_ptr, non ha costruttore di copie).

Soluzione: sostituire unique_ptr con shared_ptr per essere in grado di copiare loro (e non solo spostarli).

O, ovviamente, utilizzare un altro tipo di contenitore del tutto (ma se si è scelto priority_queue in primo luogo, questo probabilmente non è accettabile per voi).

Si potrebbe anche usare un "membro protetto" per accedere al membro protetto c (il contenitore sottostante) ma non lo consiglierei, questo è piuttosto sporco e molto probabilmente UB.

Answer 2

Sono d'accordo, questo è incredibilmente fastidioso. Perché mi lascia elementi std::move nella coda, quindi non mi consente di spostarli? Non abbiamo più una copia dell'originale, quindi ho bisogno di un oggetto non const quando faccio un top() e pop().

Soluzione: estendere std::priority_queue, aggiungendo un metodo pop_top() che esegue entrambi contemporaneamente. Questo dovrebbe preservare qualsiasi ordine della coda. Dipende comunque da C++ 11. La seguente implementazione funziona solo con i compilatori 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 

};