Comparatori in std :: priority_queue

Question

C'è un motivo per cui il costruttore di std::priority_queue accetta un comparatore per riferimento costante? Cosa succede se il comparatore esce dall'ambito di applicazione?

Stavo pensando a questo nel contesto del possibile spostamento del comparatore come sottolineato da @LightnessRacesInOrbit!

Mi dispiace se c'è già stato un post su questo. Non sono stato in grado di trovarlo!

Answer 1

Non ci ho mai pensato prima, e il const-ref in effetti è un po 'fuorviante. Tuttavia, la firma della funzione è stata pensata prima che la semantica del movimento venisse fuori ed è diventato di moda accettare tutto per valore. In effetti, il comparatore viene copiato!

[C++14: 23.6.4.1/4]:Effetti: inizializza comp con x e c con y (copia costruzione o spostare la costruzione a seconda dei casi); chiama c.insert(c.end(), first, last); e infine chiama make_heap(c.begin(), c.end(), comp).

Lambda non sono copiare cedibile, ma sono copia-costruibile, quindi non c'è problema qui.

[C++14: 5.1.2/20]: Il tipo di chiusura associato con un lambda-espressione ha un soppresso (8.4.3) costruttore di default e un operatore di assegnamento copia cancellato. Ha un costruttore di copie implicitamente dichiarato (12.8) e può avere un costruttore di mosse implicitamente dichiarato (12.8). [..]

Questo impedisce mossa-realizzazione del comparatore stesso? Sì, lo fa. Assumerò che questa convenzione, che consiste nel prendere il comparatore mediante il referegistro e poi copiarlo, deriva dai giorni STL, molto prima di spostare la semantica.Immagino che non sia stato preso seriamente in considerazione l'aggiunta di sovraccarichi per prendere il comparatore in base al valore perché aggiunge complessità e non dovresti avere un comparatore complesso, migliorabile con il movimento, in primo luogo (fornisci loro lo stato, certo, ma non lo troppo). Tuttavia, questo potrebbe essere il valore di che merita di essere sollevato con il comitato se riesci a trovare un solido caso d'uso per spostare un comparatore.

Answer 2

Il costruttore di std::priority_queue produce una copia del comparatore fornito, quindi non è un problema se esce dallo scope.

È possibile utilizzare un lambda come comparatore sia utilizzando std::function<bool(const T&, const T&)> come tipo di confronto, oppure direttamente:

auto comp = [](int x, int y) { return x > y; }; 
std::priority_queue<int, std::vector<int>, decltype(comp)> q(comp); 

Si può facilitare questo con una funzione di supporto:

template<typename T, typename Compare> 
auto make_priority_queue(Compare&& comp) { 
    return std::priority_queue<T, std::vector<T>, Compare>(std::forward<Compare>(comp)); 
} 

int main() { 
    auto q = make_priority_queue<int>([](int x, int y) { return x > y; }); 
} 

Answer 3

E non va fuori ambito - è copia costruita nel contenitore. La descrizione su cppreference.com stati:

explicit priority_queue(const Compare& compare = Compare(), 
         const Container& cont = Container()); 

Copy-costruisce il contenitore c sottostante con il contenuto di cont. Copia-costruisce il confronto del functor comp con il contenuto del confronto. Chiama std :: make_heap (c.begin(), c.end(), comp). Questo è anche il costruttore predefinito.

Ci sono varie altre forme del costruttore, ma in tutti i casi il comparatore interno è costruito in copia o in movimento da quello fornito.