C++ - 如何將std :: priority_queue中的元素複製到std :: vector

Question

例如，我想從輸入向量中挑出第k個最大的元素。

我知道用QuickSelect std :: nth_element可以做得更好。

我的問題是如何複製std :: priority_queue的底層容器std :: vector到另一個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(); 
} 

有沒有更好的方式來做到這一點？

我們可以像

vector<int> res = pq; 

的前k元素並不需要訂購。

Answer 1

不，您無法訪問沒有彈出的priority_queue的所有元素。也沒有內置的方式來移動元素，但有一種方法，使用const cast。對於整數來說，它肯定是不值得的，但想象這種類型的拷貝是昂貴的。這個技巧是安全的，只要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。

這樣，你可以複製矢量。