STL之priority_queue与仿函数

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

目录

    • 一.仿函数
      • 1.介绍
      • 2.示例
    • 二.priority_queue
      • 1.介绍
      • 2.成员函数
      • 3.模拟实现
      • 4.使用
    • 三.其他
      • 1.typename Container::value_type

一.仿函数

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;};
}

4.使用

在这里插入图片描述

三.其他

1.typename Container::value_type

在这里插入图片描述

在less的显示实例化时,所传入的typename Container::value_type类型,所代表的是:Container类中定义的value_type类型

因为class Container = vector<T>,以vector示例:
在这里插入图片描述

using:相当于typedef

由此可见typename Container::value_type其实就相当于T类型,只是库中的更加规范


🦀🦀观看~~


http://www.ppmy.cn/news/396722.html

相关文章

C语言实现的简易五子棋

#include <stdlib.h> #include <stdio.h> #include <conio.h> #include <string.h> #define MAXIMUS 15 ///定义棋盘大小 int p[MAXIMUS][MAXIMUS];///存储对局信息 char buff[MAXIMUS*21][MAXIMUS*43];///输出缓冲器 int Cx,Cy;///当前光标位置 int N…

win10系统上安装cmder并实现右键启动

周末把笔记本的win10系统重置了,再安装cmder时遇到了一系列的坑。经过不断地尝试,终于解决了一个个问题,写成一篇攻略,以备查询,也希望能够帮助到别人。 cmder下载 进入[cmder官网](https://cmder.net/)下载安装包,Mini版本或Full版本按需选择即可。此时会出现一个问题,…

.NET的基元类型包括哪些?Unmanaged和Blittable类型又是什么?

在讨论.NET的类型系统的时候&#xff0c;我们经常提到“基元类型&#xff08;Primitive Type&#xff09;”的概念&#xff0c;我发现很多人并没有真正理解基元类型就究竟包含哪些&#xff08;比如很多人觉得字符串是基元类型&#xff09;。除了明确界定基元类型外&#xff0c;…

小米手机关闭自带服务器,小米手机耗电大?关闭这两个设置,小米手机能更省电!...

原标题&#xff1a;小米手机耗电大&#xff1f;关闭这两个设置&#xff0c;小米手机能更省电&#xff01; 小米手机耗电大、续航差是很多小米用户最头疼的事&#xff0c;明明刚充满的电&#xff0c;才玩了一会儿就去掉了一大半&#xff0c;真的很忧伤~ 那么怎么做才能让小米更省…

手机充不进电什么原因怎么办

品牌型号&#xff1a;iPhone 13 pro 系统&#xff1a;iOS 16.1.1 手机充不上电什么原因 手机充不上电原因&#xff1a; 1、电压不够&#xff1a;建议换个插口&#xff0c;或者把手机的屏幕亮度调到最暗&#xff0c;然后重新插上充电器。 2、检查室温是不是过低&#xff1a;部…

如何查看手机电量消耗是否正常?

【查看方法】 1、手机自带有电量使用信息查询&#xff0c;进入方式&#xff1a;设置——电池&#xff0c;见下图&#xff1a; 这个界面可以查看各应用耗电信息&#xff0c;还可以查看各应用耗电排行。 2、点击“电量使用详情”&#xff0c;进入如下界面&#xff1a; 该界面显示…

手机边充电边玩,消耗的电量是来自电池还是充电器呢?

如今人们最离不开的是手机&#xff0c;从睁开眼&#xff0c;手机就是他的全部&#xff0c;在地铁上、公交上&#xff0c;随处可见一些低头族专注于玩手机&#xff0c;甚至大部分的人都是边充电边玩&#xff0c;那么很多人又会存在这样的疑问&#xff1a;手机边充电边玩&#xf…

小米八android耗电比例很大,小米手机耗电太快?MIUI系统最全的省电方法,解决手机耗电问题...

原标题&#xff1a;小米手机耗电太快&#xff1f;MIUI系统最全的省电方法&#xff0c;解决手机耗电问题 MIUI10系统作为小米8周年发布会上的一个重磅产品&#xff0c;一发布就有不少小米完成升级。随着近期的MIUI10稳定版的推出&#xff0c;并且支持多款机型升级尝鲜&#xff0…