c++ - 内部データへの参照を変更するときに STL Priority Queue を更新する

Question

Dijkstra の Algorithmを書いているとしましょう。最短距離ノードを一番上に保持する優先キューがあります。ただし、グラフをトラバースすると、その頂点までの距離が更新されます。データ構造に含まれるプライオリティ キュー内のすべての頂点への参照を配置しました。データ構造の頂点を更新すると、優先度キューのデータがそれらの変更に適応するようになり、最も近いノードが常に最上位になります。しかし、デバッガーを使用してアプリケーションをステップ実行した後、優先キューが更新されないことに気付きました。すべての頂点を再挿入せずに、これを行うにはどうすればよいですか?

Answer 1

STL priority_queue は、push() および pop() メソッドのみを使用してデータ構造を変更することを前提としています。データ構造への変更は追跡しません。

priority_queue の基礎となるコンテナーの内部を変更した後、コンテナーで make_heap() を呼び出して、ヒープ プロパティを復元する必要があります。STL priority_queue は、基になるコンテナーにイテレーターを提供しません。代わりに、deque または vector を優先キューとして手動で管理し、必要に応じて make_heap()、push_heap()、および pop_heap() を呼び出す必要があります。