c++ - 我可以通过清除底层容器来清除 priority_queue 吗？

Question

以下代码继承std::priority_queue并提供clear()调用内部std::vector的clear()

#include<iostream>
#include<queue>
using namespace std;
template<class type>
struct mypq :public priority_queue<type> {
    void clear(){
        this->c.clear();
    }
};
mypq<int>pq;
int main() {
    for(int i=0;i<10;++i)
        pq.push(i);
    pq.clear();
    for(int j=-5;j<0;++j)
        pq.push(j);
    while (!pq.empty()){
        cerr<<pq.top()<<endl;
        pq.pop();
    }
}

当我用 g++、MSVC++ 和 clang 测试它时，它产生了预期的输出:

-1
-2
-3
-4
-5

但我还没有看到对此有任何保证，即当 priority_queue 不为空时，清除内部 vector 将与调用 pop() 相同。虽然我知道其他清除它的方法，例如交换或使用空的 priority_queue 分配它，但我认为如果这段代码可以正常工作，它会更有效，因为 vector 中分配的内存是可重用的。所以我想知道这段代码是可移植的还是不总是有效？

Answer 1

But I haven't seen any guarantee for this, i.e. clearing the internal vector will be the same as calling pop() when the priority_queue isn't empty.

因为那不是一回事。 std::priority_queue是一个专门设计的容器适配器，通过严格的弱排序来保持有序。如果您不指定队列将具有的容器类型(您在示例中没有指定)，则默认类型为 std::vector .

所以调用 pop() 在非空优先级队列上将具有在调用 clear() 时从队列中删除顶部元素的效果在底层容器上将从队列中删除所有元素，而不仅仅是最上面的元素。

Although I know other ways to clear it such as swap or assign it using an empty priority_queue, I think if this code can work well, it would be more efficient since the allocated memory in the vector is reusable. So I wonder if this code is portable or won't always work?

根据reference , 底层 c成员对象是 protected ，因此应该保证跨编译器访问您的方式，即调用 this->c.clear();应该是可移植的(有趣的是，它适用于旧版本 OpenBSD 的 g++ 4.2.1)。

就效率而言，这在某种程度上取决于。做类似 this->c.clear(); 的事情与 q = priority_queue <int>();在内存使用或复杂性方面可能没有什么不同，尽管您必须在不同的平台上对其进行测试以进行验证。但是，做类似 this->c.clear(); 的事情与 while(!q.empty()) { q.pop(); } , 会更有效率。

在内存效率方面，pop优先级队列函数调用底层容器 pop_back 函数，也不是 pop_back也不是 clear影响底层 vector 的 capacity ，因此实际上并没有任何“节省”的方式；尽管如此，如果您有特定需要，您可以调整 vector 的大小以增加/减少容量。

只要记住优先级队列pop函数调用底层容器 pop_back函数，并调用 pop_back在空容器上是未定义的行为。

希望对您有所帮助。