写在前面
优先队列模拟题最近常出, 记录一下学C++优先队列的一些代码与用法, 当然也有重载输出操作符的方法(优先队列的构造函数真奇怪). 参考std::priority_queue - cppreference.com;
基本用法
头文件与定义
需要包含queue头文件, 这里我还用到了输出类名的typeinfo.
#include <iostream>
#include <queue>
#include <vector>
#include <typeinfo>
using namespace std;
// 输出vector元素
ostream &operator<<(ostream &os, const vector<int> &c) {
for (auto i : c) os << i << " ";
return os << endl;
}
其类型定义为:
template<
class T,
class Container = std::vector<T>,
class Compare = std::less<typename Container::value_type>
> class priority_queue;
由于模版参数中有两个默认参数, 这就导致后面在创建优先队列的时候会有一些问题.
基本类型与构造函数
一些基本的类型介绍: (很重要, 对应了后面的各种构造函数的用法)
void t1() {
cout << typeid(priority_queue<int>::container_type).name() << endl;
// The type of first-class container upon which a container adaptor is
// based.
// 容器适配器所基于的一级容器类型。
cout << typeid(vector<int>).name() << endl;
//=========================================
cout << typeid(priority_queue<int>).name() << endl;
cout << typeid(priority_queue<int, vector<int>, less<int>>).name() << endl;
cout << typeid(priority_queue<int, vector<int>, greater<int>>).name()
<< endl;
cout << typeid(priority_queue<int, vector<int>>).name() << endl;
cout << typeid(priority_queue<less<int>>).name() << endl;
cout << typeid(priority_queue<greater<int>>).name() << endl;
}
#if 0
St6vectorIiSaIiEE
St6vectorIiSaIiEE
St14priority_queueIiSt6vectorIiSaIiEESt4lessIiEE
St14priority_queueIiSt6vectorIiSaIiEESt4lessIiEE
St14priority_queueIiSt6vectorIiSaIiEESt7greaterIiEE
St14priority_queueIiSt6vectorIiSaIiEESt4lessIiEE
St14priority_queueISt4lessIiESt6vectorIS1_SaIS1_EES0_IS1_EE
St14priority_queueISt7greaterIiESt6vectorIS1_SaIS1_EESt4lessIS1_EE
#endif
从上面的输出就看出了其参数的多样性, 默认内部容器为vector, 默认比较函数为less, 也就是大顶堆.
使用方法(构造函数)有以下几种:
-
priority_queue() : priority_queue(Compare(), Container()) { }基本构造函数, 通过给出比较函数(函数对象)和内置容器完成构造. 其他形式的只是增加了const关键字就不列出了.
-
template< class InputIt > priority_queue( InputIt first, InputIt last, const Compare& compare = Compare() );通过给出现有容器的迭代器和比较函数(可设置为默认less)构造, 最后一个参数是容器类型, 没必要加, 常用.
-
template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue;这里是优先队列的类型定义, 其实也就是构造了, 这种方法后面会提到. 需要指定元素类型, 容器类型以及比较函数.
重载输出操作符
有了上面的三大类构造, 就可以写出对应版本的泛型输出操作符重载:
template <typename Q, template <typename> class Comp>
ostream &operator<<(ostream &os, priority_queue<Comp<Q>, vector<Q>> q) {
for (; !q.empty(); q.pop()) { os << q.top() << " "; }
return os << endl;
}
template <typename Q, template <typename> class Comp>
ostream &operator<<(ostream &os, priority_queue<Q, vector<Q>, Comp<Q>> q) {
for (; !q.empty(); q.pop()) { os << q.top() << " "; }
return os << endl;
}
第一种是沿用构造函数写的, 第二种是由模板类定义给出的, 需要注意这里的一个巧妙的写法, pop放在for的第三部分, 然后每次输出top值, 需要注意这里不能pass by reference, 否则输出操作会修改原来的优先队列元素, 这里直接传值相当于复制了一份, 不会原有的结果产生影响.
使用方法
void t2() {
priority_queue<int, vector<int>, less<int>> q1;
priority_queue<int, vector<int>, greater<int>> q2;
for (auto i : {1, 8, 5, 6, 3, 4, 0, 9, 7, 2}) {
q1.push(i);
q2.push(i);
}
cout << q1;
cout << q2;
cout << q1.size() << endl;
cout << q2.size() << endl;
/*
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
10
10*/
}
void t3() {
const auto v = {1, 0, 5, 4, 9, 7, 6, 2};
cout << v;
// cout << typeid(v).name() << endl;
// St16initializer_listIiE
priority_queue q3(v.begin(), v.end(), less<int>(), vector<int>());
//最后的容器参数可以省略
priority_queue q4(v.begin(), v.end(), greater<int>(), vector<int>());
cout << typeid(q3).name() << endl;
// NSt3__114priority_queueIiNS_6vectorIiNS_9allocatorIiEEEENS_4lessIiEEEE
cout << q3;
cout << q4;
cout << q3.size() << endl;
cout << q4.size() << endl;
/*
1 0 5 4 9 7 6 2
9 7 6 5 4 2 1 0
0 1 2 4 5 6 7 9
8
8
*/
}
void t4() {
priority_queue q5{less<int>{}, vector<int>{}};
priority_queue q6{greater<int>{}, vector<int>{}};
// cout << typeid(q5).name() << endl;
// St14priority_queueIiSt6vectorIiSaIiEESt4lessIiEE
for (int i : {1, 8, 5, 6, 3, 4, 0, 9, 7, 2}) {
q5.emplace(i);
q6.emplace(i);
}
cout << q5;
cout << q6;
/*9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9*/
}
使用上就这三种构造方法, 最后一种的临时对象写成圆括号也行(但是参数列表外面的大括号不能改, 需要用一致初始化的写法), 参数列表对应就可以, 我这里比较推荐第二种方法, 写起来比较简洁.