STL之priority_queue与仿函数

news/2024/10/30 23:22:01/

一.仿函数

1.介绍

函数对象，又称仿函数，是可以像函数一样使用的对象，其原理就是重载了函数调用符：()

因此在此类中，一定有operator()的成员函数。

2.示例

template<class T>
struct _less
{//lhs:left-hand sidebool operator() (const T& lhs, const T& rhs){return lhs < rhs;}
};

如果T是内置类型，则直接进行比较。如果T是自定义类型，则会调用其operator<()。

先创建一个_less类型的对象smaller，对于smaller()，则调用其operator()函数

二.priority_queue

1.介绍

在这里插入图片描述

priority_queue，也是一种容器适配器:class Container = vector<T>，底层默认为vector

同时，对于其元素存储，类似于大/小堆（父节点大于(小于)子节点的值），根据某种排序标准，使它的第一个元素总是其所有元素中最大/小的。

是按大还是小来存储，通过第3个模板参数来规定

class Compare= less<T>，缺省为less，即第一个元素总是最大的(其他插入的元素都比第一个less)。

2.成员函数

在这里插入图片描述

3.模拟实现

可以根据大小堆的算法，进行模拟实现
数据结构——堆

#include <vector>
#include <functional>
namespace yyjs
{template<class T, class Container = std::vector<T>,class Compare = std::less<T>>class priority_queue{public:bool empty() const{return _con.empty();}size_t size() const{return _con.size();}const T& top() const{return _con.front();}T& top() {return _con.front();}//从child位置开始向上调整，直到符合Compare的规则void AdjustUp(size_t child){//根据二叉树，求出父节点的位置size_t parent = (child - 1) / 2;//如果当前当前节点不是根节点，且其父节点与当前节点进行比较，符合规则while (child > 0 && _cmp(_con[parent], _con[child])){//交换当前节点与其父节点的值std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;	}}//尾插入一个节点，并将这个节点按规则进行调整void push(const T& x){_con.push_back(x);AdjustUp(size() - 1);}//从parent位置开始向下进行调整，使其符合Compare规则void AdjustDown(size_t parent){size_t child = parent * 2 + 1;//左孩子//当其子节点在有效范围内while (child < size()){	//如果有右节点其右节点更大(小)，选择右节点if (child + 1 < size() && _cmp(_con[child],_con[child + 1])){child++;}//当前节点与其子节点进行比较，符合规则，进行交互if (_cmp(_con[parent], _con[child])){::swap(_con[parent],_con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}//删除第一个元素，然后将剩余元素按规则调整void pop(){//先交换首尾元素，然后再删尾元素std::swap(_con.back(), _con.front());_con.pop_back();//把交换上去的首元素向下调整，使符合规则AdjustDown(0);}private:Container _con;Compare _cmp;};
}