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();
}

有没有更好的方法来做到这一点？

我们可以这样做吗

vector<int> res = pq;

前 k 个元素不需要排序。

Answer 1

vector<int>一开始就可以用。

并将这个向量视为堆，带有std::make_heap, std::push_heap, std::pop_heap。

这样，您就可以复制向量。

Answer 2

不，您无法在不弹出的情况下访问priority_queue 的所有元素。也没有内置方法可以将元素移出，但有一种方法，使用 const 强制转换。对于整数来说，这肯定不值得，但想象一下复制该类型的成本很高。只要 pq 本身不在 const 存储中（即首先声明为 const），该技巧就是安全的，这对于优先级队列来说应该很少见。

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