目录
一、 仿函数
1.1仿函数的概念+使用
1.2模拟实现仿函数
二、优先级队列（priority_queue)
2.1 优先级队列概念
2.2 优先级队列使用
2.3 模拟实现优先级队列
2.3.1 优先级队列类框架
2.3.2 模板参数
2.3.3 构造函数
2.3.4 仿函数
2.3.5 adjust_up (堆向上排序)
2.3.6 adjust_down(堆向下排序)
2.3.7 push(尾插数据)
2.3.8 pop(出队头数据)
2.3.9 top(取堆顶)
2.3.A size(容器元素个数)
2.3.B empty(判断容器是否为空)
2.4 优先级队列完整 + 模拟测试
2.4.1 priority_queue.h
2.4.2 test.cpp
一、 仿函数
1.1仿函数的概念+使用
💡仿函数(functor)，就是使一个类的使用看上去像一个函数。其实本质就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了
接下来我们要来了解库中两个常用的比较仿函数 less / greater
直接看库代码：
//less
template <class T> struct less : binary_function <T,T,bool> {bool operator() (const T& x, const T& y) const {return x<y;}
};//greater
template <class T> struct greater : binary_function <T,T,bool> {bool operator() (const T& x, const T& y) const {return x>y;}
};
它们的本质就是类封装operator()函数，只不过模板参数让它们的比较类型可以灵活化！下面我们来看看它的使用场景！控制数据排序是升序还是降序！
#include <iostream> // std::cout
#include <functional> // std::greater
#include <algorithm> // std::sortint main () {int numbers[]={20,40,50,10,30};//升序sort (numbers, numbers+5, greater<int>());for (int i=0; i<5; i++)cout << numbers[i] << ' ';cout << '\n';//降序sort (numbers, numbers+5, less<int>());for (int i=0; i<5; i++)cout << numbers[i] << ' ';cout << '\n';return 0;
}代码结果：
结论：less是决定排降序，greater决定是升序
1.2模拟实现仿函数
我们直接看代码：
template<class T>class Less{public:bool operator()(const T& left, const T& right)const{return left > right;}};template<class T>class greater{public:bool operator()(const T& left, const T& right)const{return left < right;}};二、优先级队列（priority_queue)
在此之前需要你知道数据结构的堆概念！我写的另一篇博客数据结构的堆介绍了堆！
2.1 优先级队列概念
1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大优先级的。（本质数据排序是数据结构的堆！)
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
函数声明 接口说明 priority_queue()/priority_queue(first,
last)构造一个空的优先级队列 empty( ) 检测优先级队列是否为空，是返回true，否则返回
falsetop( ) 返回优先级队列中最大(最小元素)，即堆顶元素 push(x) 在优先级队列中插入元素x pop() 删除优先级队列中最大(最小)元素，即堆顶元素 5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
2.2 优先级队列使用
#include<vector>
#include<iostream>
#include<queue>
#include<functional>
using namespace std;
int main()
{priority_queue<int,vector<int>,greater<int>> pq;int arr[] = { 9,7,2,6,3,5,1,4,8 };for (int i = 0;i < sizeof(arr) / sizeof(arr[0]);i++)pq.push(arr[i]);while (!pq.empty()){cout << pq.top() << ' ';pq.pop();}return 0;
}
2.3 模拟实现优先级队列
2.3.1 优先级队列类框架
#pragma once
#include<vector>
#include<iostream>
#include<deque>
using namespace std;
namespace wyz
{//仿函数template<class T>class lesser{public:bool operator()(const T& left, const T right)const{return left > right;}};template<class T>class greater{public:bool operator()(const T& left, const T right)const{return left < right;}};//优先级队列template<class T,class contain=vector<T>,class compare=lesser<T>>class priority_queue{public://默认构造priority_queue(){}//容器迭代器区间构造template <class InputIterator>priority_queue(InputIterator first, InputIterator last)//向上排序void adjust_up(size_t child)//向下排序void adjust_down(size_t parent）//尾插 + 堆向上排序void push(const T& val)//出堆顶 + 堆向下排序void pop()//取堆顶const T& top()const//返回容器数据个数size_t size()const//判断容器是否为空bool empty()constprivate:contain con;//容器};
}2.3.2 模板参数
template<class T,class contain=vector<T>,class compare=lesser<T>>
💡💡三个类型参数分别代表 数据存储类型、底层容器类型、仿函数决定排序顺序！
我们默认容器时Vector,堆是大堆，即堆顶是最大值！
2.3.3 构造函数
//默认构造
priority_queue()
{}
//容器迭代器区间构造
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last):con(first, last)//直接迭代器区间构造底层容器
{}2.3.4 仿函数
💡💡注意两个仿函数各自比较方式！使用的是后注意传给letf、right参数值！
template<class T>
class lesser
{
public:bool operator()(const T& left, const T right)const{return left > right;}
};
template<class T>
class greater
{
public:bool operator()(const T& left, const T right)const{return left < right;}
};2.3.5 adjust_up (堆向上排序)
void adjust_up(size_t child)
{compare com;size_t parent = (child - 1) / 2;while (child > 0){//Less 建大堆 比较符号是> child>parent匹配符号左右参数if (com(con[child], con[parent])){swap(con[child], con[parent]);child = parent;parent = (child - 1) / 2;}else break;}
}2.3.6 adjust_down(堆向下排序)
void adjust_down(size_t parent)
{//别忘记创建仿函数类compare com;size_t child = parent * 2 + 1;while (child < con.size()){//lesser 建大堆 比较符号> child+1>child匹配符号左右参数if (child + 1 < con.size() && com(con[child + 1], con[child])){child = child + 1;}//lesser 建大堆 比较符号> child>parent匹配符号左右参数if (com(con[child], con[parent])){swap(con[child], con[parent]);parent = child;child = parent * 2 + 1;}else break;}
}2.3.7 push(尾插数据)
void push(const T& val)
{con.push_back(val);adjust_up(con.size() - 1);
}2.3.8 pop(出队头数据)
void pop()
{//底层是vector,不能直接出头元素，要不然要挪动数据，影响堆整体父子关系//我们将首尾元素交换后，再pop尾数据，然后重新向下建堆swap(con[0], con[con.size() - 1]);con.pop_back();adjust_down(0);
}2.3.9 top(取堆顶)
const T& top()const
{return con[0];
}2.3.A size(容器元素个数)
size_t size()const
{return con.size();
}2.3.B empty(判断容器是否为空)
bool empty()const
{return con.empty();
}2.4 优先级队列完整 + 模拟测试
2.4.1 priority_queue.h
#pragma once
#include<vector>
#include<iostream>
#include<deque>
using namespace std;
namespace wyz
{//仿函数template<class T>class lesser{public:bool operator()(const T& left, const T right)const{return left > right;}};template<class T>class greater{public:bool operator()(const T& left, const T right)const{return left < right;}};//优先级队列template<class T,class contain=vector<T>,class compare=lesser<T>>class priority_queue{public:priority_queue(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last):con(first,last){}void adjust_up(size_t child){compare com;size_t parent= (child - 1) / 2;while (child > 0){//lesser 建大堆 child>parentif (com(con[child], con[parent])){swap(con[child], con[parent]);child = parent;parent = (child - 1) / 2;}else break;}}void adjust_down(size_t parent){compare com;size_t child = parent * 2 + 1;while (child < con.size()){//lesser 建大堆 child+1>child if (child + 1 < con.size() && com(con[child + 1], con[child])){child = child + 1;}//lesser 建大堆 child>parentif (com(con[child], con[parent])){swap(con[child], con[parent]);parent = child;child = parent * 2 + 1;}else break;}}//尾插 + 堆向上排序void push(const T& val){con.push_back(val);adjust_up(con.size()-1);}//取队头（堆顶） + 堆向下排序void pop(){swap(con[0], con[con.size() - 1]);con.pop_back();adjust_down(0);}//取堆顶const T& top()const{return con[0];}//返回容器数据个数size_t size()const{return con.size();}//判断容器是否为空bool empty()const{return con.empty();}private:contain con;//容器};
}2.4.2 test.cpp
#include"priority_queue.h"
#include<queue>
#include<functional>
void Test1()
{wyz::priority_queue<int, vector<int>, wyz::greater<int>> pq;int arr[] = { 9,7,2,6,3,5,1,4,8 };for (int i = 0;i < sizeof(arr) / sizeof(arr[0]);i++)pq.push(arr[i]);cout << "greater优先级队列结果：";while (!pq.empty()){cout << pq.top() << ' ';pq.pop();}cout << endl
}
void Test2()
{int arr[] = { 9,7,2,6,3,5,1,4,8 };wyz::priority_queue<int, vector<int>, wyz::lesser<int>> pq;for (int i = 0;i < sizeof(arr) / sizeof(arr[0]);i++)pq.push(arr[i]);cout << "lesser优先级队列结果：";while (!pq.empty()){cout << pq.top() << ' ';pq.pop();}cout << endl;
}
int main()
{Test1();Test2();return 0;
}
