は、誰かが私がのstd ::作業プライオリティキューに大きなを理解することはできませんPRIORITY_QUEUE

Question

std::priority_queue<int, vector<int>, std::greater<int> > pq;

---

を実装するために使用される方法のstd ::大きい説明することができます。 minheapを優先キューに置き換えています。 geeksForGeeks implementation of Prims algorithm using STL

Answer 1

std::priority_queueタイプはコンテナアダプタと呼ばれています。これは、シーケンスを表すために使用できる型から始まり、次にその型を使用して優先度キュー（特にバイナリヒープ）を構築します。デフォルトでは、ベクトルを使用します。

これを行うためには、プライオリティキューのタイプは、他の要素よりも「小さい」である要素を決定する方法で、互いに対して要素を比較する方法を知っている必要があります。デフォルトでは、より小さい演算子が使用されます。

あなたが標準std::priority_queue<int>を作る場合、あなたはプライオリティキューを取り戻す

• は、ストレージのためのstd::vectorを使用し、
• は、要素を比較する小なり演算子を使用していること。多くの場合

、これはあなたが望むものです。このようにして作成された優先度キューに要素を挿入すると、要素を最大から最小に戻すことができます。

しかし、場合によっては、これは必要な動作ではありません。プリム法やダイクストラ法では、例えば、あなたは値がが昇順ではなくが降順に戻って来てほしいです。これを行うには、結果として、より小さい演算子の代わりにより大きい演算子を使用して、比較の順序を逆にする必要があります。

はこれを行うには、別の比較方法を使用するようにプライオリティキューを指示する必要があります。残念ながら、プライオリティ・キュー・タイプは、そのようにしたい場合は、使用する基本のコンテナを指定する必要があるように設計されています。私はこれが設計上の間違いだと思っています。コンパレータとコンテナではなく比較器を指定するだけでいいのですが、それは本当ですか？このための構文は

std::priority_queue<int,    // store integers... 
        std::vector<int>, // ... in a vector ... 
        std::greater<int>> // ... comparing using > 

です