priority_queue的介绍仿函数

1.priority_queue的介绍

1.优先队列是⼀种容器适配器，根据严格的弱排序标准，它的第⼀个元素总是它所包含的元素中最⼤的。

2.此上下⽂类似于堆，在堆中可以随时插⼊元素，并且只能检索最⼤堆元素（优先队列中位于顶部的元素）

3.优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供⼀组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

4.底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类

5.标准容器类vector和deque满⾜这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使⽤vector。

6.需要⽀持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时⾃动调⽤算法函数 make_heap、push_heap和pop_heap来⾃动完成此操作。

1.2优先级队列的使用

1.3测试代码

这里的建堆一般有两种方式：
(1) 一种是一个一个push进vector容器再进行向上调整建堆
(2) 另一种是直接用迭代器区间构造直接建堆(推荐用这种)。

#include<iostream>
using namespace std;
#include<vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{// 默认情况下，创建的是大堆vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };priority_queue<int> q1; //使用范围for入队列for (auto e : v)q1.push(e);while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;// 建小堆，将第三个模板参数换成greater比较方式//迭代器区间构造，直接建堆priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());while (!q2.empty()){cout << q2.top() << " ";q2.pop();}
}

注意：优先级队列默认的大堆，降序排列，如果要升序，就要换仿函数。下图中第三个模板参数就是传仿函数。

使用算法库里的 less 和 greater 算法，需要包含头文件< functional >

2.仿函数

2.1仿函数的介绍

仿函数也叫函数对象，是一个重载了运算符operator() 的类或结构体，可以使得类的对象像函数一样使用，通过重载函数调用运算符，仿函数可以实现自定义的操作行为。

2.2 仿函数的简单示例

// 仿函数/函数对象：重载了oparator（）的类，类的对象可以像函数一样使用
// operator()特点，参数个数和返回值根据需求确定，不固定，很多样化
class Func
{
public://void operator()() //()函数调用参数列表括号运算//{//	cout << "Func调用" << endl;//}void operator()(int n = 1) //有参{while (n--){cout << "Func调用" << endl;}}
};int main()
{Func f1;f1();//使得对象像函数一样使用f1.operator()(); //显示调用cout << endl;Func f2;f2(3);return 0;
}

3.优先级队列的模拟实现

#pragma once
#include<vector>
namespace bit
{template<class T>class myless{public:bool operator()(const T& x, const T& y){return x < y;}};template<class T>class mygreater{public:bool operator()(const T& x, const T& y){return x > y;}};template<class T , class Container , class Compare = myless<T>>class priority_queue{public:priority_queue() = default;  //默认的构造函数来初始化template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}for (int i = (_con.size() - 1 - 1 ) / 2; i >= 0; i--){adjust_down(i);}}void adjust_up(int child){Compare comfunc;    //这里默认的是less, <  默认建大堆int parent = (child - 1) / 2;while (child > 0){//_con[parent] < _con[child]if (comfunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else { break; }}}void adjust_down(int parent){Compare confunc;size_t child = parent * 2 + 1;  // 计算当前父节点的左子节点的索引while (child < _con.size())  // 只要左子节点存在{if (child + 1 < _con.size() && comfunc(_con[child + 1], _con[child])){++child;  // 如果右子节点存在且更大（或更小），则选择右子节点}// 如果父节点的值小于（或大于）子节点的值，进行交换if (confunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);  // 交换父节点和子节点的值parent = child;  // 更新父节点索引为当前子节点索引child = parent * 2 + 1;  // 计算新的左子节点的索引}else { break; }}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};}

4.测试代码

void test_priority_queue()
{int a[] = { 2,1,7,6,0,4,3,9,8,5 };// 默认是大堆qian::priority_queue<int> q1(a, a+sizeof(a)/sizeof(int));// 小堆qian::priority_queue<int, vector<int>, qian::greater<int>> q2(a, a + sizeof(a) / sizeof(int));cout << "大堆：" << " ";while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;cout << "小堆：" << " ";while (!q2.empty()){cout << q2.top() << " ";q2.pop();}cout << endl;}