7.8　优先队列

当向一个优先队列priority_queue用push（）压入一个对象时，那个对象根据一个比较函数或函数对象在队列中排序。（可以允许用默认的less模板来代替这个函数或函数对象，或者可以提供一个用户自己定义的函数或函数对象。）priority_queue确定在用top（）查看顶部元素时，该元素将是具有最高优先级的一个元素。当处理完该元素以后，调用pop（）删除它，并且促使下一个元素进入该位置。因此，priority_queue拥有与stack几乎相同的接口，但它的表现不同。

就像stack和queue一样，priority_queue是一个基于某个基本序列容器进行构建的适配器—默认的序列容器是vector。

创造一个用来处理int型数据的priority_queue是个很平常的工作：

该程序向priority_queue压入100个数值介于0到24之间的随机数。在运行这个程序时，会看到它允许出现重复的值，而且最高值先出现。为了演示如何通过提供用户自己的函数或函数对象以改变其元素的排列顺序，下面的程序给予较低值的数以最高的优先级：

一个更有趣的问题是to-do列表，这里每个对象都包含一个string，和一个主优先级及一个次优先级的值：

由于是与less＜＞一同工作，所以ToDoItem的operator＜必须是一个非成员函数。除此之外，每一件事情都是自动发生的。输出结果如下：

由于设计上的原因，不能在一个priority_queue上从头到尾进行迭代，但是可以用一个vector来模拟priority_queue的行为，因此允许访问那个vector。可以通过观察priority_queue的实现来这样做，它使用的函数有make_heap（）、push_heap（）以及pop heap（）。（这些函数是priority_queue的灵魂—事实上，可以说堆就是一个优先队列，priority_queue只是对它的一个封装。）结果相当简单，但是读者可能会想，可能还存在一个捷径。因为priority_queue使用的容器是protected的（并且有标识符，根据标准C++规格说明，该标识符被命名为c），所以可以继承一个新类，该新类提供了访问底层实现的途径：

然而，如果运行这个程序，就会发现当调用pop（）时，得到的这个vector包含的元素并不是按降序排列，这就是想要从优先队列得到的顺序。似乎如果想要创建一个作为优先队列的vector，必须手工完成它。就像下面这样：

但是这个程序表现得跟前面那个程序一样！读者在vector底层中的一个被称为堆（heap）的存储区观察到什么。这个堆数据结构表现为一个优先队列的树的结构（被存储在vector的线性结构中），但是在对其从头到尾进行迭代的时候，并不会得到一个线性的优先队列顺序。你可能认为可以仅调用sort_heap（）进行排序，但是那只能起一次作用，然后你将不再拥有一个堆，而只剩一个被排过序的列表。这意味着，要返回将其作为一个堆来使用，用户必须记住首先调用make_heap（）。这些都可以被封装到自定义的优先队列中去：

如果sorted为真，vector就不是作为一个堆来进行组织的，而仅仅是个排过序的序列。函数assureHeap（）保证在对其进行任何堆操作之前使其倒退成为一个堆的形式。main（）中的第1个for循环引入了新的额外特性，它显示一个正在被构建的堆。

在前面的两个程序中采用了“this-＞”前缀的这种表面上并非必要（extraneous）的用法。虽然某些编译器不需要这种用法，但标准C++的定义有这种用法。注意，类PQV派生自vector＜T＞，因此继承自vector＜T＞的begin（）和end（）都是依赖的名字。^[1]在模板的定义中，编译器不能查寻这些来自于依赖的基类的名字（在这种情况下为vector），因为对于某个给定的实例，一个明确特化的模板版本可能使用的并不是一个给定的成员。特别的命名需求保证在某些情况下用户不会结束正在调用的一个基类成员，在另外的情况下函数可能来自一个外围空间（比如一个全局的）的函数。编译器无法知道调用的begin（）是依赖的，因此必须使用“this-＞”限定给它提供一个线索。^[2]这就告诉了编译器，这个begin（）是在PQV的范围之内的，因此它就会等待直到PQV的一个实例完全地被实例化。如果去掉这个限定前缀，编译器就会对名字begin和end尝试进行早期查找（在模板定义期间查找，并且会查找失败，因为在这个例子中包含的外围字典空间中并不包括这些名字声明）。然而在上面的程序代码中，编译器一直在pqi实例化的那一点等待，然后在vector＜int＞中寻找begin（）和end（）的正确的特化。

这个解决方案的惟一的缺点就是，用户必须记住在将其作为一个排过序的序列进行查看之前必须先调用sort（）（一个可以想得到的方法，就是重新定义所有能够产生迭代器的成员函数，以便保证排序的进行）。另一个解决方案就是创建一个非vector的优先队列，但是，每当需要时就构建一个使用vector的优先队列：

PQV类模板随后采用了与STL的priority_queue相同的形式，但是拥有一个附加的成员函数getVector（），该函数创建了一个从PQV中（这意味着它已经是一个堆）复制来的新的vector。然后它对那些副本进行排序（而PQV的vector并没有受到影响），并且将序列的顺序逆转，所以在遍历新的vector时产生了与从一个优先队列中弹出元素的操作等效的结果。

可以观察到，如果采用在PriorityQueue4.cpp中使用的从priority_queue中派生的方法来实现上述技术的话，可以得到更简洁的代码：

以上简洁的解决方案，加上它保证用户不会得到一个处在未经排序状态的vector，使它变得最简单且最令人期待。惟一潜在的问题就是成员函数getVector（）采用传值的方式返回vector＜T＞，这可能在参数类型T的值比较复杂时会引发某些经常性的开销问题。

[1]这意味着它们在以某种方式依赖于一个模板参数。参看第5章中的“名字查找问题”一节。

[2]如第5章所述，即任何有效限定，比如PQV：，所做的那样。