STL priority_queue适配器

STL priority_queue适配器教程

priority_queue 容器适配器模拟的也是队列这种存储结构，即使用此容器适配器存储元素只能 “从一端进（称为队尾），从另一端出（称为队头）”，且每次只能访问 priority_queue 中位于队头的元素。

但是，priority_queue 容器适配器中元素的存和取，遵循的并不是 “First in,First out”（先入先出）原则，而是 “First in，Largest out” 原则。直白的翻译，指的就是先进队列的元素并不一定先出队列，而是优先级最大的元素最先出队列。

那么，priority_queue 容器适配器中存储的元素，优先级是如何评定的呢？很简单，每个 priority_queue 容器适配器在创建时，都制定了一种排序规则。根据此规则，该容器适配器中存储的元素就有了优先级高低之分。

举个例子，假设当前有一个 priority_queue 容器适配器，其制定的排序规则是按照元素值从大到小进行排序。根据此规则，自然是 priority_queue 中值最大的元素的优先级最高。

priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素，每当有新元素进入，它都会根据既定的排序规则找到优先级最高的元素，并将其移动到队列的队头；同样，当 priority_queue 从队头移除出一个元素之后，它也会再找到当前优先级最高的元素，并将其移动到队头。

基于 priority_queue 的这种特性，因此该容器适配器有被称为优先级队列。

STL priority_queue适配器详解

语法

#include <queue>
using namespace std;

模板

template <typename T,
        typename Container=std::vector<T>,
        typename Compare=std::less<T> >
class priority_queue{
}

说明

可以看到，priority_queue 容器适配器模板类最多可以传入 3 个参数，它们各自的含义如下：

typename T：指定存储元素的具体类型；
typename Container：指定 priority_queue 底层使用的基础容器，默认使用 vector 容器。作为 priority_queue 容器适配器的底层容器，其必须包含 empty()、size()、front()、push_back()、pop_back() 这几个成员函数，STL 序列式容器中只有 vector 和 deque 容器符合条件。
typename Compare：指定容器中评定元素优先级所遵循的排序规则，默认使用 std::less<T> 按照元素值从大到小进行排序，还可以使用 std::greater<T> 按照元素值从小到大排序，但更多情况下是使用自定义的排序规则。

其中，std::less<T> 和 std::greater<T> 都是以函数对象的方式定义在 <function> 头文件中。

STL priority_queue适配器成员函数

成员函数列表

成员函数	功能
empty()	如果 priority_queue 为空的话，返回 true；反之，返回 false。
size()	返回 priority_queue 中存储元素的个数。
top()	返回 priority_queue 中第一个元素的引用形式。
push(const T& obj)	根据既定的排序规则，将元素 obj 的副本存储到 priority_queue 中适当的位置。
push(T&& obj)	根据既定的排序规则，将元素 obj 移动存储到 priority_queue 中适当的位置。
emplace(Args&&… args)	Args&&… args 表示构造一个存储类型的元素所需要的数据（对于类对象来说，可能需要多个数据构造出一个对象）。此函数的功能是根据既定的排序规则，在容器适配器适当的位置直接生成该新元素。
pop()	移除 priority_queue 容器适配器中第一个元素。
swap(priority_queue& other)	将两个 priority_queue 容器适配器中的元素进行互换，需要注意的是，进行互换的 2 个 priority_queue 容器适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同。

说明

和 queue 一样，priority_queue 也没有迭代器，因此访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素。

案例

创建并使用priority_queue适配器

创建一个 priority_queue 适配器，并使用

#include <iostream>
#include <queue>
#include <array>
#include <functional>
using namespace std;
int main()
{
    cout << "嗨客网(www.haicoder.net)\n" << endl;
    std::priority_queue<int>values;
    values.push(1024);
    values.push(99);
    values.push(1188);
    values.push(109);
    while (!values.empty())
    {
        std::cout << values.top() << endl;
        values.pop();
    }
    return 0; 
}

我们在 Linux 下使用 g++ 进行编译，具体命令如下：

g++ priority_queue.cpp -std=c++11

编译后，我们直接运行生成的二进制文件 a.out，如下图所示：

07_STL priority_queue容器适配器使用.png

我们创建了一个 priority_queue 适配器，并使用其访问了所有元素。