priority_queueの最後の要素を抽出する

Question

私はstd :: priority_queueを使用して、3Dグリッド上のデータセットの距離関数を計算するアルゴリズムを作成しています。キューを初期化した後は、std :: queue.back（）と同様に、別の変数に最後の要素を格納したいと思いますが、もちろん、これはプライオリティキューでは不可能なので、私の回避策以下れる：もちろん

CellQueue q; //this is the actual priority_queue 

//... 
//initialization 
//... 

Cell* last = 0; 
CellQueue dummy(q); 
while (!dummy.empty()) { 
    last = dummy.top(); 
    dummy.pop(); 
} 

この問題を解決するための良い方法はありますので、誰かが私にそれを示すことができる場合、私は非常に喜んでいると思います。

おかげで、

フェデリコ

---

EDIT

@Sam @Dietmar距離関数（DF）を計算するアルゴリズムは、このように動作します：あなたはの細胞とPRIORITY_QUEUEを埋めますグリッドはデータセットの少なくとも1つのポイントを含み、距離順に並べ替えられます（このステップではゼロです）。次に、キューの各要素について、隣人を訪問し、各隣人について、その親に関して距離を計算します。さて、効率の理由から、私はデータセットの周りの狭いバンドでのみDFを計算したいと思います。ですから、第3リング近隣を訪れた後にこのプロセスを止めるには、現在のリングの最後の要素を追跡しなければなりません。

Answer 1

最後の（最小の）要素のコピーをpriority_queueと共に保存することは、「明白な」方法です。これを追跡する追加の作業は、優先キューに追加される要素の数に比例しますが、対処方法は呼び出すときのキューのサイズでN log（N）ですので、選択してください。

popの場合は、popがキューを空にする場合にのみ、最後の値を削除することができます。したがって、popの更新について心配する必要はありません。

プライオリティキューにpushがある場合は、プッシュされている値を現在の最小値と比較し、必要に応じて置き換えます。 emplaceも同じです。

あなたが本当に気に入っていたい場合は、独自のコンテナアダプタpriority_queue_that_additionally_accesses_the_min_valueを書いてください。あるいは、もっと短い名前。

実際の要素にアクセスする必要がある場合は、その要素のコピーではなく、priority_queue自体があなたが見ていない間に物事を動かすという点で問題があります。最小値へのポインタ。スマートポインタで要素をラップすると、それに対処することができます。もちろん、priority_queueにスマートポインタをデバイスするコンパレータを指定する必要があります。

最後に、「両端の優先度キュー」などがあります。これにより、一方の端から効率的に取り除き、両方を調べるのではなく、両端で効率的に取り除くことができます。これは標準のC++ではなく、必要な構造とアルゴリズムを調べて自分で実装するか、あるいはC++の "double-ended priority queue"や "min/max heap"の実装を探します。私は自分自身で構造を使用したことはないので、私は特定のものをお勧めしません。