Question

STL priority_queue如何输出容器中优先级最高与最低的元素

找到优先级最高与最低元素后如何删除这两个元素？

Answer 1

首先，获取优先级最高的元素用top函数，移出它用pop函数

关于优先级最低的那个元素，理论上优先队列应该只让你获得最高优先的那个元素，因为这是优先队列逻辑上的定义。就像栈这种结构不应该让你获取到栈底的元素一样。

但是有些实现（尤其是以STL模板形式存在的那些）或多或少会暴露一些内部实现。这样你就可以利用到，从而实现，例如以下代码：

template <typename T>
class my_priority_queue : public priority_queue<T> {
public:
T& least_priority() {
return *(c.rbegin());
}
};

这个是我继承标准库的优先队列，利用到它底层是一个线性表，而线性表的最后一个元素就是队列优先级最低的元素。

但是话要说回来，这个实现依赖于底层的实现，不具有可移植性。
这体现在以上代码在VS中可以编译，在gcc中则不可以。同时，即便是VS，下一个版本的STL可能 就不能编译。

想要移除最低级别的元素，你可以用我上述继承的类实现，同样是将remove函数代理给底层的线性表实现。

最后说一句，无论什么时候，你都可以重新创建一个优先队列，并且使用与原来队列相反比较器的方式，来获取优先级最低的元素。这种方式将不会有移植性问题，但会有 效率问题。