适配一个容器以提供优先级队列

std::priority_queue

定义于头文件 <queue>

priority_queue 是容器适配器，它提供常数时间的（默认）最大元素查找，对数代价的插入与释出。

可用用户提供的 Compare 更改顺序，例如，用 std::greater<T> 将导致最小元素作为 top() 出现。

用 priority_queue 工作类似管理某些随机访问容器中的堆，优势是不可能突然把堆非法化。

模板形参

注意 比较 (Compare) 形参的定义，使得若其第一参数在弱序中先于其第二参数则返回 true 。但因为 priority_queue 首先输出最大元素，故“先来”的元素实际上最后输出。即队列头含有按照 比较 (Compare) 所施加弱序的“最后”元素。

成员函数

构造 priority_queue

std::priority_queue<T,Container,Compare>::priority_queue

从多种数据源构造容器适配器的底层容器。

1) 默认构造函数。值初始化底层容器。

2) 用 compare 的内容复制构造比较函数对象 comp 。值初始化底层容器 c 。

3) 用 cont 的内容复制构造底层容器 c 。用 compare 的内容复制构造比较函数对象 comp 。调用 std::make_heap(c.begin(), c.end(), comp) 。此亦为默认构造函数。 (C++11 前)

4) 用 std::move(cont) 移动构造底层容器 c 。以 compare 的内容复制构造比较函数对象 comp 。调用 std::make_heap(c.begin(), c.end(), comp) 。

5) 复制构造函数。以 other.c 的内容复制构造底层容器。以 other.comp 复制构造比较函数对象。 (隐式声明)

6) 移动构造函数。以 std::move(other.c) 构造底层容器。以 std::move(other.comp) 构造比较函数对象。 (隐式声明)

7-12) 仅若 std::uses_allocator<container_type, Alloc>::value == true ，即若底层容器是具分配器容器（对所有标准库容器为真），才定义下列构造函数。

7) 以 alloc 为分配器构造底层容器。等效地调用 c(alloc) 。值初始化 comp 。

8) 以 alloc 为分配器构造底层容器。等效地调用 c(alloc) 。从 compare 复制构造 comp 。

9) 用 cont 的内容，以 alloc 为分配器构造底层容器，如同用 c(cont, alloc) 。从 compare 复制构造 comp 。然后调用 std::make_heap(c.begin(), c.end(), comp) 。

10) 用 cont 的内容，以 alloc 为分配器并以移动语义构造底层容器，如同用 c(std::move(cont), alloc) 。从 compare 复制构造 comp 。然后调用 std::make_heap(c.begin(), c.end(), comp) 。

11) 用 other.c 的内容，以 alloc 为分配器构造底层容器。等效地调用 c(other.c, alloc) 。从 other.comp 复制构造 comp 。

12) 用 other 的内容，同时以 alloc 为分配器构造适配器。等效地调用 c(std::move(other.c), alloc) 。从 other.comp 移动构造 comp 。

13) 从 cont 复制构造 c 并从 compare 复制构造 comp 。然后调用 c.insert(c.end(), first, last); ，再调用 std::make_heap(c.begin(), c.end(), comp); 。

14) 从 std::move(cont) 移动构造 c 并从 std::move(compare) 移动构造 comp 。然后调用 c.insert(c.end(), first, last); ，再调用 std::make_heap(c.begin(), c.end(), comp); 。

参数

复杂度

1-2) 常数。

3,5) O(N) 次比较，其中 N 为 cont.size() 。

另外，调用 O(N) 次 value_type 的构造函数，其中 N 为 cont.size() 。

4) O(N) 次比较，其中 N 为 cont.size() 。

6-8) 常数。

9) O(N) 次比较，其中 N 为 cont.size() 。

另外，调用 O(N) 次 value_type 的构造函数，其中 N 为 cont.size() 。

10) O(N) 次比较，其中 N 为 cont.size() 。

11) 与 other 的大小成线性。

12) 常数。

13) O(N) 次比较，其中 N 为 cont.size() + std::distance(first, last) 。

另外，调用 O(N) 次 value_type 的构造函数，其中 N 为 cont.size() 。

14) O(N) 次比较，其中 N 为 cont.size() + std::distance(first, last) 。

析构 priority_queue

std::priority_queue<T,Container,Compare>::~priority_queue

销毁容器适配器。调用元素的析构函数，然后解分配所用的存储。注意，若元素是指针，则不销毁所指向的对象。

复杂度

与容器适配器大小成线性。

调用示例

#include <iostream>
#include <forward_list>
#include <string>
#include <iterator>
#include <algorithm>
#include <functional>
#include <queue>
#include <deque>
#include <time.h>using namespace std;struct Cell
{int x;int y;Cell() = default;Cell(int a, int b): x(a), y(b) {}Cell &operator +=(const Cell &cell){x += cell.x;y += cell.y;return *this;}Cell &operator +(const Cell &cell){x += cell.x;y += cell.y;return *this;}Cell &operator *(const Cell &cell){x *= cell.x;y *= cell.y;return *this;}Cell &operator ++(){x += 1;y += 1;return *this;}bool operator <(const Cell &cell) const{if (x == cell.x){return y < cell.y;}else{return x < cell.x;}}bool operator >(const Cell &cell) const{if (x == cell.x){return y > cell.y;}else{return x > cell.x;}}bool operator ==(const Cell &cell) const{return x == cell.x && y == cell.y;}
};std::ostream &operator<<(std::ostream &os, const Cell &cell)
{os << "{" << cell.x << "," << cell.y << "}";return os;
}template<typename _Tp, typename _Sequence = vector<_Tp>,typename _Compare  = less<typename _Sequence::value_type> >
void queuePrint(const std::string &name,const std::priority_queue<_Tp, vector<_Tp>, _Compare> &queue)
{std::cout << name ;std::priority_queue<_Tp, vector<_Tp>, _Compare> queuep = queue;while (queuep.size() > 0){std::cout << queuep.top() << " ";queuep.pop();}std::cout << std::endl;
}struct Compare
{Compare() {}bool operator()(const Cell &a, const Cell &b)const{if (a.x == b.x){return a.y < b.y;}return a.x < b.x;}
};int main()
{std::cout << std::boolalpha;std::mt19937 g{std::random_device{}()};srand((unsigned)time(NULL));auto generate = [](){int n = std::rand() % 10 + 110;Cell cell{n, n};return cell;};//1) 默认构造函数。值初始化底层容器。std::priority_queue<Cell> queue1;std::cout << "queue1 empty: " << queue1.empty() << std::endl;std::priority_queue<Cell, std::vector<Cell>, Compare> queue3;std::cout << "queue3 empty: " << queue3.empty() << std::endl;std::cout << std::endl;std::vector<Cell> vector1(6);std::generate(vector1.begin(), vector1.end(), generate);std::cout << "vector1:  ";std::copy(vector1.begin(), vector1.end(), std::ostream_iterator<Cell>(std::cout, " "));std::cout << std::endl;//2) 用 compare 的内容复制构造比较函数对象 comp 。值初始化底层容器 c 。std::priority_queue<Cell> queue2(std::less<Cell>(), vector1);queuePrint("queue2:   ", queue2);std::cout << std::endl;//4) 用 std::move(cont) 移动构造底层容器 c 。//以 compare 的内容复制构造比较函数对象 comp 。//调用 std::make_heap(c.begin(), c.end(), comp) 。std::priority_queue<Cell> queue4(std::less<Cell>(), std::move(vector1));queuePrint("queue4:   ", queue4);std::cout << std::endl;//5) 复制构造函数。以 other.c 的内容复制构造底层容器。以 other.comp 复制构造比较函数对象。std::priority_queue<Cell> queue5(queue2);queuePrint("queue5:   ", queue5);std::cout << std::endl;//6) 移动构造函数。以 std::move(other.c) 构造底层容器。//以 std::move(other.comp) 构造比较函数对象。std::priority_queue<Cell> queue6(std::move(queue2));queuePrint("queue6:   ", queue6);std::cout << std::endl;std::vector<Cell> vector2(6);std::generate(vector2.begin(), vector2.end(), generate);std::cout << "vector2:  ";std::copy(vector2.begin(), vector2.end(), std::ostream_iterator<Cell>(std::cout, " "));std::cout << std::endl;//13) 从 cont 复制构造 c 并从 compare 复制构造 comp 。//然后调用 c.insert(c.end(), first, last);//再调用 std::make_heap(c.begin(), c.end(), comp);std::priority_queue<Cell> queue7(vector2.begin(), vector2.end());queuePrint("queue7:   ", queue7);std::cout << std::endl;return 0;
}

输出