Per utilizzare C++ priority_queue, il programma dovrebbe iniziare con un codice come:
#includere
#includere
usando spazio dei nomiore;
Include la libreria delle code nel programma.
Per continuare a leggere, il lettore dovrebbe avere una conoscenza di base del C++.
Contenuto dell'articolo
- Costruzione di base
- Funzioni importanti per i membri
- Altre funzioni della coda prioritaria
- Dati stringa
- Altre costruzioni di code prioritarie
- Conclusione
Costruzione di base
La struttura dati deve essere costruita prima di poter essere utilizzata. La costruzione qui significa istanziare un oggetto dalla classe della coda della libreria. L'oggetto coda deve quindi avere un nome assegnatogli dal programmatore. La sintassi più semplice per creare una coda prioritaria è:
priority_queue<genere>nomecoda;
Con questa sintassi, il valore più grande viene rimosso per primo. Un esempio di istanziazione è:
priority_queue<int>pq;o
priority_queue<char>pq;
Il vettore e il deque sono due strutture dati in C++. Una priority_queue può essere creata con entrambi. La sintassi per creare una coda prioritaria dalla struttura vettoriale è:
priority_queue<tipo, vettore<stesso tipo>, confrontare>pq;Un esempio di questa istanza è:
priority_queue<int, vettore<int>, meno<int> >pq;Notare lo spazio tra > e > alla fine della dichiarazione. Questo per evitare confusione con >>. Il codice di confronto predefinito è minore, il che significa che il valore più grande, e non necessariamente il primo, verrebbe rimosso per primo. Quindi, l'istruzione di creazione può essere semplicemente scritta come:
priority_queue<int, vettore<int> >pq;Se il valore minimo deve essere rimosso per primo, l'istruzione deve essere:
priority_queue<int, vettore<int>, maggiore<int> >pq;Funzioni importanti per i membri
La funzione push()
Questa funzione inserisce un valore, che è il suo argomento, nella coda_priorità. Ritorna vuoto. Il codice seguente lo illustra:
pq.spingere(10);
pq.spingere(30);
pq.spingere(venti);
pq.spingere(cinquanta);
pq.spingere(40);
Questa priority_queue ha ricevuto 5 valori interi nell'ordine di 10, 30, 20, 50, 40. Se tutti questi elementi devono essere estratti dalla coda di priorità, usciranno nell'ordine di 50, 40, 30, 20, 10.
La funzione pop()
Questa funzione rimuove da priority_queue il valore con la priorità più alta. Se il codice di confronto è maggiore, rimuoverà l'elemento con il valore più piccolo. Se richiamato di nuovo, rimuove l'elemento successivo con il valore più piccolo del resto; richiamato di nuovo, rimuove il successivo valore più piccolo presente, e così via. Ritorna vuoto. Il codice seguente lo illustra:
pq.spingere('a');pq.spingere('C');pq.spingere('B');pq.spingere('e');pq.spingere('D');
Si noti che per chiamare una funzione membro, il nome dell'oggetto deve essere seguito da un punto e quindi dalla funzione.
La funzione top()
Il pop () la funzione rimuove il valore successivo con la priorità più alta, ma non lo restituisce, come pop () è una funzione nulla. Utilizzare il superiore() funzione per conoscere il valore di priorità più alta che deve essere successivamente rimosso. Il superiore() La funzione restituisce una copia del valore di priorità più alta in priority_queue. Il codice seguente, dove il valore successivo di priorità più alta è il valore minimo, lo illustra
pq.spingere('a');pq.spingere('C');pq.spingere('B');pq.spingere('e');pq.spingere('D');
charch1=pq.superiore();pq.pop();
charch2=pq.superiore();pq.pop();
charch3=pq.superiore();pq.pop();
charch4=pq.superiore();pq.pop();
charch5=pq.superiore();pq.pop();
costo<<ch1<<''<<ch2<<''<<ch3<<''<<ch4<<''<<ch5<<' ';
L'output è 'a' 'b' 'c' 'd' 'e'.
La funzione empty()
Se un programmatore utilizza il superiore() funzione su una priority_queue vuota, dopo la corretta compilazione, riceverà un messaggio di errore del tipo:
Quindi, controlla sempre se la coda di priorità non è vuota prima di utilizzare il superiore() funzione. Il vuoto() La funzione membro restituisce un bool, true, se la coda è vuota e false se la coda non è vuota. Il codice seguente lo illustra:
priority_queue<int>pq;inti1= 10; inti2= 30; inti3= venti; inti4= cinquanta; inti5= 40;
pq.spingere(i1);pq.spingere(i2);pq.spingere(i3);pq.spingere(i4);pq.spingere(i5);
mentre(!pq.vuoto())
{
costo <<pq.superiore() << '';
pq.pop();
}
costo << ' ';
Altre funzioni della coda prioritaria
La funzione size()
Questa funzione restituisce la lunghezza della coda di priorità, come illustra il codice seguente:
inti1= 10; inti2= 30; inti3= venti; inti4= cinquanta; inti5= 40;
pq.spingere(i1);pq.spingere(i2);pq.spingere(i3);pq.spingere(i4);pq.spingere(i5);
intlen=pq.dimensione();
costo <<len<< ' ';
L'uscita è 5.
La funzione swap()
Se due priority_queues sono dello stesso tipo e dimensione, allora possono essere scambiate da questa funzione, come mostra il codice seguente:
inti1= 10; inti2= 30; inti3= venti; inti4= cinquanta; inti5= 40;
pq1.spingere(i1);pq1.spingere(i2);pq1.spingere(i3);pq1.spingere(i4);pq1.spingere(i5);
priority_queue<int>pqA;
intit1= 1; intit2= 3; intit3= 2; intit4= 5; intit5= 4;
pqA.spingere(it1);pqA.spingere(it2);pqA.spingere(it3);pqA.spingere(it4);pqA.spingere(it5);
pq1.scambio(pqA);
mentre(!pq1.vuoto())
{
costo <<pq1.superiore() << '';
pq1.pop();
} costo<<' ';
mentre(!pqA.vuoto())
{
costo <<pqA.superiore() << '';
pqA.pop();
} costo<<' ';
L'uscita è:
5 4 3 2 1
50 40 30 20 10
La funzione emplace()
Il posto() la funzione è simile alla funzione push. Il codice seguente lo illustra:
inti1= 10; inti2= 30; inti3= venti; inti4= cinquanta; inti5= 40;
pq1.posto(i1);pq1.posto(i2);pq1.posto(i3);pq1.posto(i4);pq1.posto(i5);
mentre(!pq1.vuoto())
{
costo <<pq1.superiore() << '';
pq1.pop();
} costo<<' ';
L'uscita è:
50 40 30 20 10
Dati stringa
Quando si confrontano le stringhe, è necessario utilizzare la classe stringa e non l'uso diretto dei valori letterali della stringa perché confronterebbe i puntatori e non le stringhe effettive. Il codice seguente mostra come viene utilizzata la classe stringa:
#includerepriority_queue<corda>pq1;
stringa s1=corda('penna'), s2=corda('matita'), s3=corda('quaderno'), s4=corda('manuale'), s5=corda('governate');
pq1.spingere(s1);pq1.spingere(s2);pq1.spingere(s3);pq1.spingere(s4);pq1.spingere(s5);
mentre(!pq1.vuoto())
{
costo <<pq1.superiore() << '';
pq1.pop();
} costo<<' ';
L'uscita è:
libro di testo righello matita penna libro degli esercizi
Altre costruzioni di code prioritarie
Creazione esplicita da un vettore
Una coda prioritaria può essere creata esplicitamente da un vettore come mostra il codice seguente:
vettore<int>vtr= {10,30,venti,cinquanta,40};
priority_queue<int>pq(vtr.inizio(), vtr.fine());
mentre(!pq.vuoto())
{
costo <<pq.superiore() << '';
pq.pop();
} costo<<' ';
L'output è: 50 40 30 20 10. Questa volta deve essere inclusa anche l'intestazione del vettore. Gli argomenti per la funzione di costruzione accettano i puntatori di inizio e fine del vettore. Il tipo di dati per il vettore e il tipo di dati per priority_queue devono essere gli stessi.
Per rendere il valore minimo la priorità, la dichiarazione per il costruttore sarebbe:
priority_queue<int, vettore<int>, maggiore>int> >pq(vtr.inizio(), vtr.fine()); Creazione esplicita da un array
Una coda prioritaria può essere creata esplicitamente da un array come mostra il codice seguente:
priority_queue<int>pq(arr, arr+5);
mentre(!pq.vuoto())
{
costo <<pq.superiore() << '';
pq.pop();
} costo<<' ';
L'output è: 50 40 30 20 10. Gli argomenti per la funzione di costruzione prendono i puntatori di inizio e fine dell'array. arr restituisce il puntatore iniziale, arr+5 restituisce il puntatore appena oltre l'array e 5 è la dimensione dell'array. Il tipo di dati per l'array e il tipo di dati per priority_queue devono essere gli stessi.
Per rendere il valore minimo la priorità, la dichiarazione per il costruttore sarebbe:
priority_queue<int, vettore<int>, maggiore<int> >pq(arr, arr+5);Nota: in C++, priority_queue è in realtà chiamato adattatore, non solo contenitore.
Codice di confronto personalizzato
Avere tutti i valori nella coda di priorità crescenti o tutti discendenti non è l'unica opzione per la coda di priorità. Ad esempio, un elenco di 11 numeri interi per un heap massimo è:
88, 86, 87, 84, 82, 79,74, 80, 81,,, 64, 69
Il valore più alto è 88. Questo è seguito da due numeri: 86 e 87, che sono inferiori a 88. Il resto dei numeri è inferiore a questi tre numeri, ma non proprio in ordine. Ci sono due celle vuote nell'elenco. I numeri 84 e 82 sono inferiori a 86. I numeri 79 e 74 sono inferiori a 87. I numeri 80 e 81 sono inferiori a 84. I numeri 64 e 69 sono inferiori a 79.
Il posizionamento dei numeri segue i criteri di max-heap - vedere più avanti. Per fornire un tale schema per priority_queue, il programmatore deve fornire il proprio codice di confronto - vedere più avanti.
Conclusione
Una C++ priority_queue è una coda first-in-first-out. La funzione membro, spingere(), aggiunge un nuovo valore alla coda. La funzione membro, superiore(), legge il valore in cima alla coda. La funzione membro, pop (), rimuove senza restituire il valore superiore della coda. La funzione membro, vuoto(), controlla se la coda è vuota. Tuttavia, priority_queue differisce dalla coda, in quanto segue un algoritmo di priorità. Può essere il più grande, dal primo all'ultimo, o il minimo, dal primo all'ultimo. I criteri (algoritmo) possono anche essere definiti dal programmatore.