当前位置: 首页 > news >正文

Stack和Queue(3)

Stack和Queue(3)

priority_queue的模拟实现

在这里插入图片描述

priority_queue.h

#include <vector>namespace soobin
{template<class T, class Container = vector<T>>class priority_queue{public://强制生成默认构造priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){//建堆//起始位置是最后一个非叶子节点的位置for (int i = (_con.size() - 1 - 1) / 2; i > 0; i--){AdjustDown(i);}}void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void AdjustDown(int parent){size_t child = parent * 2 + 1;while (child < _con.size()){// 假设法,选出左右孩子中小的那个孩子if (child + 1 < _con.size() && _con[child + 1] > _con[child]){++child;}if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}const T& top(){return _con[0];}size_t size(){return _con.size();}private:Container _con;};
}

Test.cpp

#include<iostream>
#include<stack>
#include<queue>using namespace std;#include "priority_queue.h"int main()
{int a[] = { 1,4,2,5,6,3,2 };soobin::priority_queue<int> pq1(a, a + sizeof(a) / sizeof(int));//默认是大的优先级高soobin::priority_queue<int> pq;//小的优先级高的写法//priority_queue<int, vector<int>, less<int>> pq;pq.push(1);pq.push(2);pq.push(3);pq.push(4);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

仿函数

例子如下:

template <class T>struct less {bool operator() (const T& x, const T& y) const{ return x < y;}};template <class T>struct greater{bool operator() (const T& x, const T& y) const{return x > y;}};

是结构体,但是通过operator()进行重载

两个地方的应用:

1.比较大小怕与库里面的函数冲突

拿上面建堆来举例子:

#include <vector>namespace soobin
{template <class T>struct less{bool operator() (const T& x, const T& y) const{return x < y;}};template <class T>struct greater{bool operator() (const T& x, const T& y) const{return x > y;}};template<class T, class Container = vector<T>, class Compare = less<T>>//template<class T, class Container = vector<T>>class priority_queue{public://强制生成默认构造priority_queue() = default;template <class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){//建堆//起始位置是最后一个非叶子节点的位置for (int i = (_con.size() - 1 - 1) / 2; i > 0; i--){AdjustDown(i);}}void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parent])if(com(_con[child],_con[parent])){swap(_con[child], _con[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void AdjustDown(int parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){// 假设法,选出左右孩子中小的那个孩子//if (child + 1 < _con.size() && _con[child + 1] > _con[child])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[child] > _con[parent])if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}const T& top(){return _con[0];}size_t size(){return _con.size();}private:Container _con;};
}

2.想要实现比较大小,但是不是我们预期效果的时候

class Date
{
public:Date(int year = 1900, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool 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 operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d);
private:int _year;int _month;int _day;
};ostream& operator<<(ostream& _cout, const Date& d)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}
int main()
{soobin::priority_queue<Date*> q1;q1.push(new Date{ 2024, 10, 23});q1.push(new Date{ 2024, 5, 27 });q1.push(new Date{ 2024, 11, 2 });while (!q1.empty()){cout << *q1.top() << " ";q1.pop();}cout << endl;return 0;
}

我们在实现上面日期类的时候,如果不去自己设置仿函数,编译器可能会比较指针,而不是里面的内容,需要自己去设置仿函数比较里面内容的大小

相关文章:

Stack和Queue(3)

Stack和Queue&#xff08;3&#xff09; priority_queue的模拟实现 priority_queue.h #include <vector>namespace soobin {template<class T, class Container vector<T>>class priority_queue{public://强制生成默认构造priority_queue() default;temp…...

怎样把学生的成绩单独告知家长?

期中考试季的到来让校园里的气氛似乎也变得紧张起来。家长们开始频繁地联系老师&#xff0c;希望了解孩子的表现&#xff1b;孩子们则在考试后&#xff0c;绞尽脑汁地想出各种理由&#xff0c;以期在成绩不理想时能减轻家长的失望。老师们更是忙得不可开交&#xff0c;不仅要批…...

vue3父组件控制子组件表单验证及获取子组件数值方法

1、关键部分的代码如下&#xff0c;我努力交代清楚了&#xff0c;希望能让大家看懂。 <template><KeepAlive><component ref"comp" :is"compNames[steps[compIndex].comp]" /></KeepAlive><el-button click"prevBtn"…...

【JavaEE】【多线程】单例模式

目录 一、设计模式1.1 单例模式1.1.1 饿汉模式1.1.2 懒汉模式 1.2 线程安全问题1.3 懒汉模式线程安全问题的解决方法1.3.1 原子性问题解决1.3.2 解决效率问题1.3.3 解决内存可见性问题和指令重排序问题 一、设计模式 在讲解案例前&#xff0c;先介绍一个概念设计模式&#xff…...

Java.6--多态-设计模式-抽象父类-抽象方法

一、多态 1.定义--什么是多态&#xff1f; a.同一个父类的不同子类对象&#xff0c;在做同一行为的时候&#xff0c;有不同的表现形式&#xff0c;这就是多态。&#xff08;总结为&#xff1a;一个父类下的不同子类&#xff0c;同一行为&#xff0c;不同表现形式。&#xff0…...

JAVA Maven 的安装与配置

一、下载地址 官方网站&#xff1a;Maven – Download Apache Maven 我这里是3.8.6版本 二、安装步骤 maven安装之前要先安装jdk&#xff0c;请确保你的系统已经安装了jdk环境。 1.将下载好的 Maven 进行解压 apache-maven-3.6.8-bin.zip 2.配置本地仓库:修改 conf/settin…...

【程序分享】PCB元件坐标对齐工具 V1.3

↑↑↑点击上方蓝字&#xff0c;关注我们&#xff01; “PCB元件坐标对齐工具 V1.3”脚本程序在PCB文档中将元件的坐标自动移动到参考圆弧的中心&#xff0c;参考圆弧支持机械层1层和禁止布线层&#xff0c;参考图元的位置任意&#xff0c;不局限于栅格位置。 程序会自动…...

[bug] vllm 0.6.1 RuntimeError: operator torchvision::nms does not exist

[bug] vllm 0.6.1 RuntimeError: operator torchvision::nms does not exist 环境 python 3.10 torch 2.4.0cu118 torchvision 0.19.0cu118 vllm 0.6.1.post2cu118问题详情 if torch._C._d…...

处理Hutool的Http工具上传大文件报OOM

程序环境 JDK版本&#xff1a; 1.8Hutool版本&#xff1a; 5.8.25 问题描述 客服端文件上传主要代码&#xff1a; HttpRequest httpRequest HttpUtil.createPost(FILE_UPLOAD_URL); Resource urlResource new UrlResource(url, fileName); httpRequest.form("file&q…...

transforms的使用

示例代码 from PIL import Image from torch.utils.tensorboard import SummaryWriter from torchvision import transforms#打开该图片 img_path"hymenoptera_data/val/bees/10870992_eebeeb3a12.jpg" imgImage.open(img_path) writerSummaryWriter("logs&quo…...

python-PyQt项目实战案例:制作一个视频播放器

文章目录 1. 关键问题描述2. 通过OpenCV读取视频/打开摄像头抓取视频3. 通过PyQt 中的 QTimer定时器实现视频播放4. PyQt 视频播放器实现代码参考文献 1. 关键问题描述 在前面的文章中已经分享了pyqt制作图像处理工具的文章&#xff0c;也知道pyqt通过使用label控件显示图像的…...

反向传播的微积分原理 | Chapter 4 | Deep Learning | 3Blue1Brown

目录 前言1. 简介2. 神经网络中的链式法则3. 微积分的计算4. 公式含义5. 代价函数对权重偏置的敏感度6. 多个神经元的情形7. 回顾相关资料结语 前言 3Blue1Brown 视频笔记&#xff0c;仅供自己参考 这个章节主要来深度讲解反向传播中的一些微积分理论 官网&#xff1a;https://…...

matlab读取excel表格

使用matlab读取excel表格中的数据 使用推荐代码读取excel表格中的数据 path "C:\Users\24975\Desktop\503\GUI展示案例\Tx_20_0_Rx_40_90_0.1_95_L.xlsx";%文件路径 data readtable(path,Sheet,Sheet1,ReadRowNames,false,ReadVariableNames,false&#xff0c;Ra…...

基于springboot+vue实现的助学兼职系统(源码+L文+ppt)4-092

基于springbootvue实现的助学兼职系统&#xff08;源码L文ppt&#xff09;4-092 第4章 系统设计 4.1 总体功能设计 一般学生、招聘公司和管理者都需要登录才能进入助学兼职系统&#xff0c;使用者登录时会在后台判断使用的权限类型&#xff0c;包括一般使用者和管理者,一般使…...

⌈ 传知代码 ⌋ 农作物病害分类(Web端实现)

&#x1f49b;前情提要&#x1f49b; 本文是传知代码平台中的相关前沿知识与技术的分享~ 接下来我们即将进入一个全新的空间&#xff0c;对技术有一个全新的视角~ 本文所涉及所有资源均在传知代码平台可获取 以下的内容一定会让你对AI 赋能时代有一个颠覆性的认识哦&#x…...

CMU生成式人工智能大模型:从入门到放弃(九)

引言 在前面的系列博客中&#xff0c;我们深入探讨了生成式对抗网络&#xff08;GANs&#xff09;和变分自编码器&#xff08;VAEs&#xff09;等生成式模型。今天&#xff0c;我们将探索扩散模型&#xff08;Diffusion Models&#xff09;的进一步应用&#xff0c;并讨论在上…...

HTML基础总结

一、简介 HTML&#xff08;HyperText Markup Language&#xff09;即超文本标记语言&#xff0c;是用于创建网页的标准标记语言。它通过使用各种标签来定义网页的结构和内容&#xff0c;告诉浏览器如何显示网页。HTML 文档由标签和文本组成&#xff0c;标签用于描述文本的性质…...

EXCELL中如何两条线画入一张图中,标记坐标轴标题?

1&#xff0c;打开excel&#xff0c;左击选中两列&#xff0c; 2&#xff0c;菜单栏>“插入”>”二维折线图”选中一个 3&#xff0c;选中出现的两条线中的一条右击>最下一行&#xff0c;“设置数据系列格式” 4&#xff0c;右测“系列选项中”>点击“次坐标轴” 5…...

Zabbix企业级分布式监控环境部署

“运筹帷幄之中&#xff0c;决胜千里之外”。在IT运维中&#xff0c;监控占据着重要的地位&#xff0c;按比例来算&#xff0c;说占30%一点也不为过。对IT运维工程师来说&#xff0c;构建一个真正可用的监控告警系统是一项艰巨的任务。在监控系统的开源软件中&#xff0c;可供选…...

水轮发电机油压自动化控制系统解决方案介绍

在现代水电工程中&#xff0c;水轮机组油压自动化控制系统&#xff0c;不仅直接关系到水轮发电机组的安全稳定运行&#xff0c;还影响着整个水电站的生产效率和经济效益。 一、系统概述 国科JSF油压自动控制系统&#xff0c;适用于水轮发电机组调速器油压及主阀&#xff08;蝶…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...