C++STL优先队列类模板

1.priority_queue概述

priority_queue类模板可实例化queue型容器，其中的元素根据优先级被读取。该类模板的接口和queue非常接近。在此类队列中，元素并不是按顺序存储在容器中的，而是按优先级顺序存储在容器中，即在此类队列中，被压入的元素已经按优先级进行了自动排序。默认排序准则是“＜”。和常规队列同样，使用priority_queue类模板时需要包含头文件＜queue＞。例如，

priority_queue类模板的定义如下：

该类模板声明中的第1个参数表示元素的型别；第2个参数定义了内部用来存放元素的容器，其默认容器是vector；第3个元素定义了排序准则，默认情况是以“operator＜”作为比较准则。例如，

和前述几种特殊容器相同，priority_queue型容器也是把各项操作转化为容器内部的对应调用。程序开发人员可以使用任何序列类型的容器来支持priority_queue，前提是这些序列式容器要支持front（）、push_back（）、pop_back（）等操作即可。

值得一提的是，在priority_queue型容器中需要用到STL中的“堆”（heap）算法，因此其内部容器必须支持随机存取迭代器。比如deque型容器。

如果程序员需要定义自己的排序准则，必须传递一个函数（或仿函数）作为二元判断式，用于比较两个元素，从而作为排序准则。

2.核心成员函数

priority_queue的核心接口主要由成员函数push（）、top（）和pop（）组成。这3个函数的使用方法和前述的几种特殊容器相同。当容器为空时，若调用成员函数top（）和pop（），会调用失败。

和前面介绍的容器不同之处在于：priority_queue提供了多种形式的构造函数。在C＋＋STL中，stack、bitset和queue在各自的模板中，均提供了一种构造函数；而priority_queue提供了两种构造函数。

1）Visual C＋＋中提供的构造函数。其形式如下：

(www.xing528.com)

2）STL提供的构造函数。其形式如下。

此外，priority_queue提供了两个操作符“＝＝”和“＜”，并提供了size（）函数和empty（）函数。

3.实例

例3-46用于说明priority_queue的使用方法。

例3-46

例3-46的执行效果如图3-47所示。

图3-47 例3-46的执行效果

总结

本节主要讲述如何使用priority_queue类模板，queue与priority_queue的不同之处在于：后者实现了内部自动排序。程序员可根据实际情况自定义排序准则，也可以自己编写函数或仿函数用于内部优先级的确定。在Visual C＋＋ 6.0开发环境中，priority_queue型容器可使用vector和deque两种序列式容器；而在使用list型容器时，出现了编译错误。例3-46对两种排序准则均进行了尝试。读者应该认真阅读，以达到触类旁通、举一反三的效果。