C++ - std :: priority_queueからstd :: vectorに要素をコピーする方法

Question

たとえば、入力ベクトルからk番目に大きい要素を選びたいとします。

私は、QuickSelect std :: nth_elementを使用する方が良いことが分かります。

私の質問は、このコーディングの問題を解決するのではなく、std :: priority_queueの基になるコンテナstd :: vectorを別のベクターにコピーする方法です。

priority_queue<int, vector<int>, greater<int>> pq; 
for (int num : nums) { 
    pq.push(num); 
    if (pq.size() > k) { 
     pq.pop(); 
    } 
} 

私のやり方は愚かである：

vector<int> res; 
while (!pq.empty()) { 
    res.push_back(pq.top()); 
    pq.pop(); 
} 

はそれを行うには良い方法はありますか？

は、我々はトップk個の要素を注文する必要はありません

vector<int> res = pq; 

のようにそれを行うことができます。

Answer 1

いいえ、ポップすることなくpriority_queueのすべての要素にアクセスすることはできません。要素を移動させる方法も組み込まれていませんが、constキャストを使用する方法があります。整数の場合は、必ずしも価値がありませんが、コピーするのに高価であると想像してください。このトリックは、pqがそれ自体がconstストレージ（つまり、constで始まると宣言されている）でない限り、安全です。これは優先キューでは稀です。

vector<int> res; 
while (!pq.empty()) { 
    res.push_back(std::move(const_cast<int&>(pq.top()))); 
    pq.pop(); 
} 

Answer 2

最初にvector<int>を使用できます。

そしてこのベクトルをヒープとして扱います。std::make_heap,std::push_heap,std::pop_heapです。

こうすれば、ベクターをコピーすることができます。