Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::priority_queue — coda con priorità

std::priority_queue espone l’elemento con la priorità più alta, non quello inserito per primo. Per impostazione predefinita, in cima si trova il valore più grande; std::greater<T> inverte l’ordine.

Versione: C++23; repository compiler flag, production runtime not attested

Sintassi

#include <functional>
#include <queue>
#include <vector>

std::priority_queue<T> q;
std::priority_queue<T, std::vector<T>, std::greater<T>> min_q;

std::priority_queue di <queue> è un adattatore di contenitore che mantiene un heap, non una coda FIFO. Per impostazione predefinita usa std::vector<T> e std::less<T>, quindi top() indica il valore più grande. La variante con std::greater<T> indica il più piccolo e richiede <functional>.

push() inserisce un valore, mentre emplace() costruisce un elemento nel contenitore e ripristina la proprietà di heap. top() fornisce accesso in sola lettura. pop() rimuove l’elemento in cima e restituisce void: copia prima della rimozione i valori che ti servono. Controlla empty() prima di top() e pop(); entrambe le operazioni richiedono una coda non vuota.

Il comparatore deve definire un ordinamento debole stretto. Compare(a, b) == true significa che a precede b in tale ordinamento e ha quindi una priorità di estrazione inferiore. L’adattatore non espone iteratori né un’operazione per modificare la priorità di un elemento arbitrario.

top() ha costo costante. Il ripristino dell’heap durante push(), emplace() e pop() richiede O(log n) confronti. L’inserimento include anche il costo del contenitore sottostante: la riallocazione del std::vector<T> predefinito può rendere lineare un singolo inserimento.

L’esempio stampa gli stessi dati in ordine decrescente e crescente, svuotando entrambe le code. Questa voce riguarda C++23; la bozza di lavoro collegata è più recente e non è un testo C++23 congelato.

Esempi

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> max_q;
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_q;

    for (int value : {4, 1, 7, 1}) {
        max_q.push(value);
        min_q.push(value);
    }

    while (!max_q.empty()) {
        std::cout << max_q.top();
        max_q.pop();
        std::cout << (max_q.empty() ? '\n' : ' ');
    }
    while (!min_q.empty()) {
        std::cout << min_q.top();
        min_q.pop();
        std::cout << (min_q.empty() ? '\n' : ' ');
    }
}

Risultato

7 4 1 1
1 1 4 7

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti