iterierbare priority_queue-klasse

[mxm]

Hallo,

ich habe ein Problem bei der Umsetzung eines A-Stern Algorithmus mit VC++ und zwar bei der Auswahl der zugrundeliegenden Datenstruktur.

Ich benötige eine priority_queue (mit top(), pop(), push ()) für meine Punktklasse und muss darüber hinaus alle Elemente in der queue durchlaufen können, um einzelne Punkte über andere Kriterien als den queue-Schlüssel wiederzufinden und gegebenenfalls zu löschen.

Kennt Ihr eine C++ Implementierung so einer Datenstrukturen ... würde mir sehr weiterhelfen?

Gruß,
mxm

 

[Online-Skater]

Hallo ich hab zwar keine Ahnung was du vor hast, aber ich habe selber einen Priority-Queue in C++ umgesetzt hier
Vllt. kannste den so modifizieren wie du es brauchst, eigentlich dienen diese Queues für nacheinander Abarbeitende Prozesse.

Sicherlich gibt es auch woanders fertige Klassen im www.

mfg

 

[mxm]

Hallo Online-Skater,

danke, aber ich glaube deine Queue hilft mir nicht weiter, denn ich suche eine Priority-Queue, die im Gegensatz zum dem FIFO-Prinzip bei Deiner, stets den kleinsten Wert ausgibt.

Es gibt zwar eine Standardklasse priority_queue in c++, aber die ist leider nicht durchlaufbar, und genau diese Funktion brauche ich eben auch dringend. Daher bezieht sich meine Frage nur auf Klasse mit diesen beiden Funktionen

Grüße,
mxm

 

[RedWing]

Hallo,

[2] This restriction is the only reason for priority_queue to exist at all. If iteration through elements is important, you can either use a vector that is maintained in sorted order, or a set, or a vector that is maintained as a heap using make_heap, push_heap, and pop_heap. P

Also kannst du einfach einen stl::vector in Kombination mit dem sort Algorithmus verwenden, ich habe das selbst letztens erst am A* Algo ausprobiert und es funktioniert bestens

Gruß,
RedWing

 

[kle-ben]

Für meinen A* hab ich die hier genommen.

Benny

 

[RedWing]

Hallo,

Für meinen A* hab ich die hier genommen.

Benny

der Threadersteller wollte aber wenn ich mich recht entsinne eine iterierbare Liste und die std:riority_queue aus der stl ist definitiv nicht iterierbar. Bspw. muss man beim A* überprüfen ob die Nachbarknoten vom aktuellen Knoten in der priority_queue, welche die noch abzuarbeitbaren Knoten enthält enthalten ist. Dafür eignet sich std::find, welcher allerdings auf Iteratoren arbeitet, das mit einer std:riority_queue zu erledigen wird imho ein Krampf, eben deshalb bietet sich ein sortierter std::vector an.

Gruß,
RedWing

 

[mxm]

@kle-ben
Red Wing hat Recht. Die Seite, die du verlinkt hast, hatte ich mir auch schon mal angessehen, aber die ist für mich leider unbrauchbar.

@Red Wing
Danke, das ist das, was ich brauche. Den vector zusammen mit sort-Algorithmus werde ich benutzen.

 

[kle-ben]

:-( Oh ja stimmt...

Ich dachte ich hätte mir die Implementierung meines A* angeschaut.
Hab grade nochmal geschaut und festgestellt das der Kruskal-Algorithmus war.
Der vector ist natürlich das richtige für den A*

Benny