[C++] Priority_queue: come si inizializzano?

[tulkas85]

salve, devo creare una coda con priorità, precisamente gli elementi devono essere ordinati per minimo, cioè man mano devo estrarre l'elemento minimo.
la coda deve essere di tipo grafo* (dove grafo è una mia classe) e gli elementi devono essere ordinati a seconda di key che è un membro di grafo.
Come posso fare ?
ho preso spunto da questo link ma non riesco a capirci molto :
http://www.cppreference.com/cppprior...ontstruct.html

grazie.

[tulkas85]

come posso fare ?
priority_queue<grafo*, poi ??
sto cercando un pò in giro su internet qualche guida, purtroppo le fonti più interessanti sono in inglese

tipo questa : http://www.sgi.com/tech/stl/priority_queue.html

vacci a a capire qualcosa....

[tulkas85]

[tulkas85]

al limite se nessuno può aiutarmi, accetto consigli per la realizzazione di una classe che gestisca una coda con priorità , tramite heap binario....

grazie !

[unomichisiada]

Originariamente inviato da tulkas85
al limite se nessuno può aiutarmi, accetto consigli per la realizzazione di una classe che gestisca una coda con priorità , tramite heap binario....

grazie !

Ho dato uno sguardo al secondo link che hai postato e non mi pare un inglese trascendentale, sei completamente digiuno di inglese o c'è qualche passaggio che non capisci?Nel secondo caso sono disposto ad aiutarti, nel primo ti do il consiglio di fare almeno un corso di base perchè in questo settore senza l'inglese ha un grave deficit. Per quanto riguarda scrivere un'implementazione tua dell'heap binario (cosa che ti sconsiglio dato che c'è un'implementazione bell'è pronta nella STL della coda con priorità) gli algoritmi relativi a questa struttura dati li conosci?Il c++? Presumo di si se ti stai cimentando,quindi dov'è il problema, si tratta di una mera trasposizione da pseudocodice o quello che è in c++.

[tulkas85]

mah, qualcosina ci capisco d'inglese il guaio è che non ho capito come dichiarare questa coda utilizzando le stl del c++.
Dovrei dichiarare da quel che ho capito il tipo dei componenti che la struttura coda a andrà ad implementare, poi se nn sbaglio la struttura che deve utilizzare ed infine un metodo per il confronto....compare()

Parameter Description Default
T The type of object stored in the priority queue.
Sequence The type of the underlying container used to implement the priority queue. vector<T>
Compare The comparison function used to determine whether one element is smaller than another element. If Compare(x,y) is true, then x is smaller than y. The element returned by Q.top() is the largest element in the priority queue. That is, it has the property that, for every other element x in the priority queue, Compare(Q.top(), x) is false. less<T>

per definizione le priority queue ordinano in modo decrescente, io invece ho bisogno che il minimo sia in testa alla coda per essere poi estratto.
I tipi da inserire sono grafo* mentre devo confrontarli per grafo->key

come posso fare ?

[tulkas85]

sto implementando una classe coda per fare questa gestione, ma non riesco a capire come devo allocare lo spazio...
sto facendo una lista che ad ogni inserimento alloca spazio per un elemento xò non è per nulla semplice,
volendo potrei anche usare un array, l'importante che quando estraggo da questa coda mi restituisca il minimo e mi cancelli l'elemento .
che struttura mi consigliate di usare ?

[unomichisiada]

Originariamente inviato da tulkas85
sto implementando una classe coda per fare questa gestione, ma non riesco a capire come devo allocare lo spazio...
sto facendo una lista che ad ogni inserimento alloca spazio per un elemento xò non è per nulla semplice,
volendo potrei anche usare un array, l'importante che quando estraggo da questa coda mi restituisca il minimo e mi cancelli l'elemento .
che struttura mi consigliate di usare ?

Ciao purtroppo con mingw ho problemi a far funzionare la STL scaricata da questo sito che hai postato (invito chiunque usi la STL con questo compiler a postare istruzioni che sono interessato anche io) quindi non poddo fare delel prove dirette per darti una mano. Per quanto riguarda un'implementazione casalinga direi che puoi anche usare una banale lista concatenata con inserimento ordinato e cancellazione dalla testa.La lista si manterrà sempre ordinata (con l'elemento più grande/piccolo sempre in testa) se scrivi una funzione di inserimento tale da mantenere sempre questa proprietà,non è molto difficile.Poi ti basta cancellare sempre dalla testa per implementare l'estarzione dell'elemento top nella coda con priorità.
Con un array non dovresti far altro che implementare l'heapsort ad ogni inserimento/estarzione dell'ememnto top.Scegli tu

[tulkas85]

si sto provando a fare questa lista...
ma lo spazio per gli elementi della lista lo alloco man mano che inserisco giusto ?

[unomichisiada]

Originariamente inviato da tulkas85
si sto provando a fare questa lista...
ma lo spazio per gli elementi della lista lo alloco man mano che inserisco giusto ?

Si certo per ogni inserimento devi allocare un nuovo nodo.
A grandi linee l'algoritmo è questo:


Crei innanzitutto una struttura nodo che abbia un puntatore a nodo per il successore (lista concatenata semplice) ed un campo dati in cui memorizzi le informazioni (nel tuo caso una struttura di tipo grafo mi pare di capire).

INSERIMENTO:
Quando devi inserire un nuovo elemento la prima cosa da fare è creare un nuovo elemento nodo ed inizializzare i suoi campi (il puntatore next a NULL e il campo dati con i dati del nuovo elemento).Poi occorre controllare se la lista è vuota ,cosa che si può vedere dal puntatore alla testa che è ancora NULL.Nel caso sia vuota non hai da far nulla oltre ad aggiornare il puntatore alla testa facendolo puntare al nuovo nodo appena creato.Se la lista non vuota (puntatore alla testa non NULL) allora devi scandire la lista elemento per elemento a partire dalla testa fino a trovare la corretta posizione.Tale posizione è indicata dal fatto che (supponendo un ordinamento decrescente) l'elemento corrente è diventato minore (il confronto lo farai in base a un campo chiave dei dati) di quello da inserire.Quando hai trovato la posizione devi solo aggiustare i puntatori in modo opportuno.In realtà hai due scelte:dato che stai lavorando con una lista semplicemente concatenata in teroria quando arrivi alla condizione in cui l'elemento corrente è diventato minore di quello da inserire è già tardi perchè non puoi più lavorare sul puntatore a next del nodo che lo precede.Qquindi o ti sei premunito e per ogni nodo hai memorizzato anche il puntatore al precedente durante la scansione della lista, (ma questo richiede di distinguere il caso speciale della testa) o usi i doppi puntatori.Quest'ultimo approccio è leggermente più sottile e difficile da comprendere ma consente di scrivere del codice più compatto ed elegante per fare l'inserimento.
Ovviamnete l'inserimento si avvale dell'ipotesi che la tua funzione sia l'unioca a manipolare la lista e che quindi gli elemnti inseriti siano costantemente ordinati.

CANCELLAZIONE DELL'ELEMENTO TOP
Direi che è banale, devi solo fare in modo che il puntatore alla testa della lista punti al nodo next della testa attuale e restituire il nodo cancellato.