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.