STL-Prioritätswarteschlange aktualisieren, wenn Verweise auf interne Daten geändert werden

Question

Sagen wir, ich schreibe Dijkstra's Algorithm, und ich habe eine Prioritätswarteschlange, die den Knoten mit der kürzesten Entfernung an der Spitze hält. Wenn ich jedoch den Graph durchquere, werde ich den Abstand zu diesem Eckpunkt aktualisieren. Ich habe Verweise auf alle Scheitelpunkte in der Prioritätswarteschlange platziert, die in der Datenstruktur enthalten sind. Wenn ich nun die Scheitelpunkte in der Datenstruktur aktualisiere, möchte ich, dass sich die Daten in der Prioritätswarteschlange an diese Änderungen anpassen, sodass der nächste Knoten immer oben ist. Nach dem Durchlaufen meiner Anwendung mit dem Debugger habe ich jedoch bemerkt, dass die Prioritätswarteschlange sich nicht selbst aktualisiert. Wie bekomme ich es dazu, ohne alle Scheitelpunkte wieder einzufügen?

Answer 1

STL priority_queue setzt voraus, dass Sie nur die Methoden push() und pop() verwenden, um die Datenstruktur zu ändern. Änderungen an der Datenstruktur werden nicht verfolgt.

Nachdem Sie das Innere des zugrunde liegenden Containers der priority_queue geändert haben, müssen Sie make_heap() für den Container aufrufen, um die Heap-Eigenschaft wiederherzustellen. STL priority_queue stellt keine Iteratoren für den zugrunde liegenden Container bereit. Stattdessen müssen Sie eine Deque oder einen Vektor manuell als Prioritätswarteschlange verwalten und make_heap(), push_heap() und pop_heap() bei Bedarf aufrufen.