【C++】priority_queue仿函数

今天我们来学习C++中另一个容器适配器：优先级队列——priority_queue；和C++一个重要组件仿函数：

目录

一、priority_queue

1.1 priority_queue是什么

1.2 priority_queue的接口

1.2.1 priority_queue使用举例

二、仿函数

三、关于priority_queue的例题

四、模拟实现priority_queue

五、priority_queue的使用拓展

---

一、priority_queue

1.1 priority_queue是什么

priority_queue介绍文档：priority_queue - C++ Reference (cplusplus.com)

优先队列（priority_queue）是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

其底层就是堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。对于堆不熟悉的可以看到这里：【精选】【数据结构初阶】树与二叉树——堆

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

底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类（默认使用vector）。容器应该可以通过随机访问迭代器访问，并支持以下操作： empty()：检测容器是否为空、size()：返回容器中有效元素个数 、front()：返回容器中第一个元素的引用、push_back()：在容器尾部插入元素、pop_back()：删除容器尾部元素

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

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

1.2 priority_queue的接口

函数声明	接口说明
priority queue()/priority queue(first,last)	构造一个空的优先级队列（）
empty	检测优先级队列是否为空，是返回true，否则返回 false
size	返回优先级队列中元素总个数
top	返回优先级队列中最大(最小元素)，即堆顶元素
push	在优先级队列中插入元素
pop	删除优先级队列中最大(最小)元素，即堆顶元素

1.2.1 priority_queue使用举例

#include<iostream>
#include<vector>
#include<queue>
#include<functional>using namespace std;
int main()
{priority_queue<int> q1;//大堆q1.push(5);q1.push(1);q1.push(10);q1.push(8);q1.push(7);while (!q1.empty()){cout<<q1.top()<<" ";q1.pop();}cout << endl;priority_queue<int,vector<int>,greater<int>> q2;//小堆q2.push(5);q2.push(1);q2.push(10);q2.push(8);q2.push(7);while (!q2.empty()){cout << q2.top() << " ";q2.pop();}return 0;
}

运行效果：

我们可以看到构建一个小堆要用到仿函数，下面我们来看看仿函数是个什么东西：

二、仿函数

我们先来看到下面这段代码：

struct ADD
{int operator()(int x, int y){return x + y;}
};
int main()
{struct ADD add;cout << add(1,9) << endl;return 0;
}

运行效果：

我们可以看到，该段代码在结构体中实现了一个（）的运算符重载，接着使用该结构体定义了一个对象add，用该对象调用里面的运算符重载函数实现了一个功能，这就是大名鼎鼎的仿函数

由此看来仿函数的本质就是（）的运算符重载，使创建的对象可以像函数一样使用

三、关于priority_queue的例题

题目地址：

215. 数组中的第K个最大元素

解题思路：对于该使一个经典的top-k问题，对于题我们可以先取k个数建立一个小堆，再将后面的数依次与堆顶元素相比较，如果比堆顶元素大就将堆顶元素丢弃后，将该数入堆；接着再接着与下一个数相比，这样最终堆顶元素就是第K个最大的数了：

解题代码：

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int,vector<int>,greater<int>> q(nums.begin(),nums.begin()+k);for(int i=k;i<nums.size();++i){if(nums[i]>q.top()){q.pop();q.push(nums[i]);}}return q.top();}
};

 

四、模拟实现priority_queue

下面我们来手搓一个priority_queue：

#pragma once
#include<iostream>
#include<vector>
#include<algorithm>namespace lhs
{template<class T, class container = std::vector<T>>class priority_queue{private:void adjustup(size_t child)//向上调整{while (child > 0){size_t parent = (child - 1) / 2;if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;}else break;}}void adjustdown(size_t parent)//向下调整{size_t child = parent * 2 + 1;while (child < size()){if (child + 1 < size() && _con[child] < _con[child + 1]){++child;}if (_con[parent] < _con[child]){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else break;}}public:void push(const T& x){_con.push_back(x);adjustup(size() - 1);}void pop(){std::swap(_con[0], _con[size() - 1]);_con.pop_back();adjustdown(0);}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con[0];}private:container _con;};
}

测试代码：

int main()
{lhs::priority_queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);q.push(10);q.push(18);while (!q.empty()){std::cout << q.top() << " ";q.pop();}std::cout << std::endl;return 0;
}

运行效果：

但是上面手搓的priority_queue只能实现大堆的效果，要实现小堆怎么办？我们不可能手动修改代码中向上和向下调整函数中的判断符吧？

这里就要轮到仿函数登场了：

#pragma once
#include<iostream>
#include<vector>
#include<algorithm>namespace lhs
{template<class T>struct less{bool operator()(const T& x, const T& y){return x > y;}};template<class T>struct greater{bool operator()(const T& x, const T& y){return x < y;}};template<class T, class container = std::vector<T>, class compare = less<T>>class priority_queue{private:void adjustup(size_t child)//向上调整{compare com;while (child > 0){size_t parent = (child - 1) / 2;if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);child = parent;}else break;}}void adjustdown(size_t parent)//向下调整{compare com;size_t child = parent * 2 + 1;while (child < size()){if (child + 1 < size() && com(_con[child + 1], _con[child])){++child;}if (com(_con[child], _con[parent])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else break;}}public:void push(const T& x){_con.push_back(x);adjustup(size() - 1);}void pop(){std::swap(_con[0], _con[size() - 1]);_con.pop_back();adjustdown(0);}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con[0];}private:container _con;};
}

我们可以看到，我们上面定义了两个仿函数：less（构建大堆）和greater（构建小堆），我们在测试代码中传入我们所要选择的仿函数类型来控制大小堆的构建（本质是通过不一样的仿函来控制运算符的改变）：

int main()
{//lhs::priority_queue<int> q;//大堆lhs::priority_queue<int, std::deque<int>, lhs::greater<int>> q;//小堆q.push(1);q.push(2);q.push(3);q.push(4);q.push(10);q.push(18);while (!q.empty()){std::cout << q.top() << " ";q.pop();}std::cout << std::endl;return 0;
}

运行效果：

五、priority_queue的使用拓展

我们把之前写的日期类拿出来：

class Date
{friend ostream& operator<<(ostream& out, const Date& d);
public:Date(int year, int month, int day);//构造函数int GetMonthDay(int year, int month) const;//获取year年month月的天数//运算符重载bool operator==(const Date& d) const;//判断日期是否相同bool operator!=(const Date& d) const;//判断日期是否不相同bool operator<(const Date& d) const;//判断当前日期是否在传入日期之前bool operator<=(const Date& d) const;//判断当前日期是否在传入日期之前或相同bool operator>(const Date& d) const;//判断当前日期是否在传入日期之后bool operator>=(const Date& d) const;//判断当前日期是否在传入日期之后或相同private:int _year;int _month;int _day;
};int Date::GetMonthDay(int year, int month) const
{int MonthDay[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };//用数组来依次存储平年1到12月的天数if (month == 2 && ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0))//判断是否为闰年的2月{return 29;}return MonthDay[month - 1];
}
Date::Date(int year, int month, int day)
{if (month < 1 || month>12 || (day<1 || day>GetMonthDay(year, month)))//判断日期是否合法{cout << "Illegal date!" << endl;}else{_year = year;_month = month;_day = day;}
}
bool Date::operator==(const Date& d) const
{return 	_year == d._year && _month == d._month && _day == d._day;
}
bool Date::operator!=(const Date& d) const
{return 	!(*this == d);
}
bool Date::operator<(const Date& d) const
{return _year < d._year || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day);
}
bool Date::operator<=(const Date& d) const
{return (*this < d) || (*this == d);
}
bool Date::operator>(const Date& d) const
{return !(*this <= d);
}
bool Date::operator>=(const Date& d) const
{return !(*this < d);
}ostream& operator<<(ostream& out, const Date& d)
{out << d._year << "/" << d._month << "/" << d._day << endl;return out;
}

下面我们可以使用priority_queue对自己写的日期类进行存储：

int main()
{Date d1(2022, 10, 23);Date d2(2022, 10, 25);Date d3(2022, 10, 24);priority_queue<Date> q1;q1.push(d1);q1.push(d2);q1.push(d3);cout << q1.top() << endl;priority_queue<Date,vector<Date>, greater<Date>> q2;q2.push(d1);q2.push(d2);q2.push(d3);cout << q2.top() << endl;return 0;
}

运行效果：

因为我们自实现的Date重载了<和>运算符，所以在我们使用priority_queue来存储时，其内部会自动调用我们所写的运算符重载来构建大小堆

再看到下面的代码：

int main()
{priority_queue<Date*> q1;q1.push(new Date(2022, 10, 23));q1.push(new Date (2022, 10, 25));q1.push(new Date (2022, 10, 24));cout << *q1.top() << endl;return 0;
}

多次运行效果：

 

 

咦？怎么每次运行的结果都不一样？

仔细看，这里我们传入的存储类型是Date*，而对于指针类型，按默认的<和>运算符来比较这是比较指针所指向地址空间的大小，但new创建空间时地址是随机的，所以这是不合理的

下面我们来写两个仿函数实现一下Date*类型的比较：

class Date_less
{
public:bool operator()(Date*a, Date* b){return *a < * b;}
};class Date_greater
{
public:bool operator()(Date* a, Date* b){return *a > *b;}
};
int main()
{priority_queue<Date*,vector<Date*>,Date_less> q1;priority_queue<Date*, vector<Date*>, Date_greater> q2;q1.push(new Date(2022, 10, 23));q1.push(new Date (2022, 10, 25));q1.push(new Date (2022, 10, 24));cout << *q1.top() << endl;q2.push(new Date(2022, 10, 23));q2.push(new Date(2022, 10, 25));q2.push(new Date(2022, 10, 24));cout << *q2.top() << endl;return 0;
}

在使用priority_queue时传入我们所写的仿函数就可以实现Date*类型的大小堆存储啦

综上所述，泛型和运算符重载为我们提供了极大的方便，我们如果对系统所提供的东西不满意，就可以使用自己所定义的方法，一切都自在掌控~