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。

这样，你可以复制矢量。