模拟实现（优先级队列）priority_queue：优先级队列、仿函数、 反向迭代器等的介绍

文章目录

  • 前言
  • 一、优先级队列
  • 二、仿函数
  • 三、 反向迭代器
  • 总结

前言

模拟实现（优先级队列）priority_queue：优先级队列、仿函数、 反向迭代器等的介绍

一、优先级队列

优先级队列本质是一个堆，使用vector容器进一步改进进行实现，优先级队列可以传入比较模板参数，来确定建立大根堆还是小根堆， 比较模板参数本质上是一个仿函数。

namespace hhb
{template<class T>struct Less{bool operator()(const T& left, const T& right){return (left < right);}};template<class T>struct Greater{bool operator()(const T& left, const T& right){return (left > right);}};template <class T, class Container = vector<T>, class Compare = Less<T>>class priority_queue{private:void AdjustDown(int parent){Compare _com;// 找到子节点int child = parent * 2 + 1;// 找字节点中大的一个if (child + 1 < _con.size() && _com(_con[child], _con[child + 1])){++child;}while (child < _con.size()){if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void AdjustUp(int child){Compare _com;// 找到父节点int parent = (child - 1) / 2;while (child > 0){if (_com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}public:priority_queue() {};template<class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){_con.push_back(*first);++first;}// 向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}const T& top(){return _con.front();}size_t size(){return _con.size();}private:Container _con;};
}

测试：

#include <iostream>
#include <vector>using namespace std;#include "Priority_queue.h"void test_priority_queue1()
{hhb::priority_queue<int> pq1;pq1.push(3);pq1.push(1);pq1.push(5);pq1.push(2);pq1.push(4);while (!pq1.empty()){cout << pq1.top() << " ";pq1.pop();}cout << endl;vector<int> v;v.push_back(1);v.push_back(2);v.push_back(4);v.push_back(3);v.push_back(5);hhb::priority_queue<int> pq2(v.begin(), v.end());while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}cout << endl;
}void test_priority_queue2()
{//Less<int> less;//cout << less(1, 2) << endl;hhb::priority_queue<int, vector<int>, hhb::Less<int>> pq1;pq1.push(1);pq1.push(2);pq1.push(3);pq1.push(4);pq1.push(5);while (!pq1.empty()){cout << pq1.top() << " ";pq1.pop();}cout << endl;hhb::priority_queue<int, vector<int>, hhb::Greater<int>> pq2;pq2.push(5);pq2.push(4);pq2.push(3);pq2.push(2);pq2.push(1);while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}cout << endl;}class Date
{
public:Date(int year = 1949, int month = 10, int day = 1):_year(year),_month(month),_day(day){}Date(const Date& d){_year = d._year;_month = d._month;_day = d._day;}bool operator<(const Date& d) const{if (_year < d._year){return true;}else if (_year == d._year && _month < d._month){return true;}else if (_year == d._year && _month == d._month && _day < d._day){return true;}else{return false;}}bool operator>(const Date& d) const{if (_year > d._year){return true;}else if (_year == d._year && _month > d._month){return true;}else if (_year == d._year && _month == d._month && _day > d._day){return true;}else{return false;}}friend ostream& operator<<(ostream& out, const Date& d);private:int _year;int _month;int _day;
};ostream& operator<<(ostream& out, const Date& d)
{out << d._year << '-' << d._month << '-' << d._day;return out;
}void test_priority_queue3()
{hhb::priority_queue<Date, vector<Date>, hhb::Less<Date>> pq1;pq1.push(Date(2024, 9, 23));pq1.push(Date(2024, 10, 23));pq1.push(Date(2024, 8, 23));while (!pq1.empty()){cout << pq1.top() << " ";pq1.pop();}cout << endl;hhb::priority_queue<Date, vector<Date>, hhb::Greater<Date>> pq2;pq2.push(Date(2024, 9, 23));pq2.push(Date(2024, 10, 23));pq2.push(Date(2024, 8, 23));while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}cout << endl;}int main()
{//test_priority_queue1();//test_priority_queue2();test_priority_queue3();return 0;
}

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

二、仿函数

仿函数指的是类的实例化对象可以像函数一样使用，也可以叫函数对象。
本质上，仿函数是在类中进行了()运算符重载。

template<class T>
struct Less
{bool operator()(const T& left, const T& right){return (left < right);}
};void test_priority_queue4()
{Less<int> less; // 类的实例化对象cout << less(1, 2) << endl; // 可以像函数一样使用
}

测试：

void test_priority_queue4()
{Less<int> less; // 类的实例化对象cout << less(1, 2) << endl; // 可以像函数一样使用
}

在这里插入图片描述

有些特殊情况下，必须要使用仿函数， 比如在优先级队列中，比较两个指针

void test_priority_queue5()
{hhb::priority_queue<Date*> pq;pq.push(new Date(2024, 9, 23));pq.push(new Date(2024, 10, 23));pq.push(new Date(2024, 8, 23));while (!pq.empty()){cout << *pq.top() << " ";pq.pop();}cout << endl;
}

在这里插入图片描述

  • 直接进行指针的比较，是随机的，应该比较指针指向的对象。
struct LessPDate
{bool operator()(const Date* left, const Date* right){return (*left < *right);}
};void test_priority_queue5()
{hhb::priority_queue<Date*, vector<Date*>, LessPDate> pq;pq.push(new Date(2024, 9, 23));pq.push(new Date(2024, 10, 23));pq.push(new Date(2024, 8, 23));while (!pq.empty()){cout << *pq.top() << " ";pq.pop();}cout << endl;
}

在这里插入图片描述

三、 反向迭代器

反向迭代器使用的是一种是适配器模式。可以适配所有支持迭代器的容器
反向迭代器与正向迭代器是镜像的，如： 反向迭代器的rbegin是正向迭代器的end();

在这里插入图片描述


namespace hhb
{template <class Iterator, class Ref, class Ptr>struct ReverseIterator{typedef ReverseIterator<Iterator, Ref, Ptr> Self;ReverseIterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}Iterator _it;};
}

vector：

namespace hhb
{template <class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;iterator begin() {return _start;}iterator end() {return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}reverse_iterator rbegin(){return end();}reverse_iterator rend(){return begin();}const_reverse_iterator rbegin() const{return end();}const_reverse_iterator rend() const{return begin();}}
}

list:

 template<class T> 
class list
{typedef list_node<T> Node;
public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef ReverseIterator<iterator, T&, T*> reverse_iterator;typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}
}

测试：

#include "vector.h"
#include "list.h"void test6()
{hhb::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt){cout << e << " ";}cout << endl;hhb::list<int>::reverse_iterator rit1 = lt.rbegin();while (rit1 != lt.rend()){cout << *rit1 << " ";++rit1;}cout << endl;hhb::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);v.push_back(6);for (auto e : v){cout << e << " ";}cout << endl;hhb::vector<int>::reverse_iterator rit2 = v.rbegin();while (rit2 != v.rend()){cout << *rit2 << " ";++rit2;}cout << endl;}

在这里插入图片描述

总结

模拟实现（优先级队列）priority_queue：优先级队列、仿函数、 反向迭代器等的介绍

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/430487.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

vue使用PDF.JS踩的坑--部署到服务器上显示pdf.mjs viewer.mjs找不到资源

vue使用PDF.JS踩的坑--部署到服务器上显示pdf.mjs viewer.mjs找不到资源

之前项目使用的pdf.js 是2.15.349版本&#xff0c;最近换了一个4.6.82的版本&#xff0c;在本地上浏览文件运行的好好的&#xff0c;但是发布到服务器&#xff08;IIS&#xff09;上打不开文件&#xff0c;控制台提示找不到pdf.mjs viewer.mjs。 之前使用的2.15.349pdf和viewer…
阅读更多...
mock虚拟接口技术

mock虚拟接口技术

一、什么是mock mock指的就是使用mock创建出来的一个虚拟的接口 二、对于测试人员而言&#xff0c;我们为什么要使用mock 当我们进行接口测试时&#xff0c;如果对应的接口还没有开发好&#xff0c;但是我们又需要用到这个接口响应的信息&#xff0c;这个时候我们就可以使用…
阅读更多...
邮件发送高级功能详解：HTML格式、附件添加与SSL/TLS加密连接

邮件发送高级功能详解：HTML格式、附件添加与SSL/TLS加密连接

目录 一、邮件HTML格式设置 1.1 HTML邮件的优势 1.2 HTML邮件的编写 二、添加附件 2.1 附件的重要性 2.2 添加附件的代码示例 2.3 注意事项 三、使用SSL/TLS加密连接 3.1 SSL/TLS加密的重要性 3.2 SSL/TLS加密的工作原理 3.3 在邮件发送中启用SSL/TLS 3.3.1 邮件客…
阅读更多...
智能算法躲避拥堵，高德企业用车上线“动态选路服务”为出行提效

智能算法躲避拥堵，高德企业用车上线“动态选路服务”为出行提效

近日&#xff0c;高德企业用车正式上线了一项全新服务——“动态选路服务”&#xff0c;旨在基于智能算法&#xff0c;动态规避突发拥堵路线&#xff0c;为企业用车用户提供更便捷、智能的出行方案。 以技术着眼细节&#xff0c;高德企业用车在帮助企业用车用户节约出行时间和…
阅读更多...
飞睿智能实时雷达活体探测传感器模块，智能家居静止检测实时感知人员有无

飞睿智能实时雷达活体探测传感器模块，智能家居静止检测实时感知人员有无

随着科技的飞速发展&#xff0c;我们的生活正在经历着未有的创新。在这个创新的浪潮中&#xff0c;实时雷达活体探测传感器模块的技术正逐渐崭露头角&#xff0c;以其独特的优势为我们的生活带来安全与便捷。今天&#xff0c;我们就来详细探讨一下这项技术&#xff0c;看看它是…
阅读更多...
TCL25届校招测评笔试TAS人才测评题库：高分攻略真题分析

TCL25届校招测评笔试TAS人才测评题库：高分攻略真题分析

&#x1f31f; 职场新人必看&#xff1a;TCL校招测评全解析 &#x1f31f; 亲爱的小伙伴们&#xff0c;你是否正准备踏入职场&#xff0c;或是对即将到来的校招感到既兴奋又紧张&#xff1f;今天&#xff0c;我将带你深入了解TCL校招中的TAS人才测评&#xff0c;让你在面试前做…
阅读更多...
MyBatis - 动态SQL

MyBatis - 动态SQL

前言 我们在某网站填写个人信息时&#xff0c;时常会遇到可以选填的空&#xff08;即可填&#xff0c;可不填&#xff09;&#xff0c;由于之前讲过的Java中的SQL语句都是固定的&#xff0c;且我们不可能对所有情况都写出与之对应的插入语句&#xff08;太过繁琐&#xff09;&…
阅读更多...
最新简洁大方的自动发卡网站源码/鲸发卡v11.61系统源码/修复版

最新简洁大方的自动发卡网站源码/鲸发卡v11.61系统源码/修复版

源码简介&#xff1a; 最新简洁大方的自动发卡网站源码&#xff0c;它就是鲸发卡v11.61系统源码&#xff0c;它是修复版。 说到鲸发卡系统&#xff0c;鲸发卡系统在发卡圈很多人都知道的&#xff0c;它是市面最好发卡系统之一&#xff0c;操作起来简单得很&#xff0c;界面也…
阅读更多...
03-Docker下载加速

03-Docker下载加速

03-Docker下载加速 docker下载加速 方式1&#xff1a;使用 网易数帆、阿里云等容器镜像仓库进行下载。 网易数帆官网&#xff1a;https://sf.163.com/ 例如&#xff0c;下载网易数帆镜像中的mysql。&#xff08;网易数帆的地址为 hub.c.163.com&#xff0c;网易数帆对dockerh…
阅读更多...
Protobuf：基本概念与使用流程

Protobuf：基本概念与使用流程

Protobuf&#xff1a;基本概念与使用流程 基本概念Linux 安装使用流程.proto文件编译使用 运行机制 基本概念 在进行网络编程时&#xff0c;经常需要进行数据传输&#xff0c;只有双方主机都保证数据格式的一致性&#xff0c;才能保证数据被正常解析。这个过程称为序列化与反序…
阅读更多...
Android平台Unity3D下如何同时播放多路RTMP|RTSP流？

Android平台Unity3D下如何同时播放多路RTMP|RTSP流？

技术背景 好多开发者&#xff0c;提到希望在Unity的Android头显终端&#xff0c;播放2路以上RTMP或RTSP流&#xff0c;在设备性能一般的情况下&#xff0c;对Unity下的RTMP|RTSP播放器提出了更高的要求。实际上&#xff0c;我们在前几年发布Unity下直播播放模块的时候&#xf…
阅读更多...
CTFHub技能树-SQL注入-Cookie注入

CTFHub技能树-SQL注入-Cookie注入

使用bp发现cookie的注入点 id1&#xff0c;发现为数字型 首先使用联合查询 id 1 order by 2 id 1 order by 3发现2的时候有回显&#xff0c;而3的时候无回显 Cookie: id-1 union select database(),user() 后面开始库->表->列->数据 Cookie: id-1 union select 1…
阅读更多...
Gin中间件

Gin中间件

Gin框架允许开发者在处理请求的过程中&#xff0c;加入用户自己的钩子&#xff08;Hook&#xff09;函数。这个钩子函数就叫中间件&#xff0c;中间件适合处理一些公共的业务逻辑&#xff0c;比如登录认证、权限校验、数据分页、记录日志、耗时统计等。 定义中间件 Gin中的中…
阅读更多...
上半年亏损扩大/百亿资产重组终止，路畅科技如何“脱困”？

上半年亏损扩大/百亿资产重组终止，路畅科技如何“脱困”？

在智能网联汽车市场形势一片大好的前提下&#xff0c;路畅科技上半年的营收却出现了下滑&#xff0c;并且亏损也进一步扩大。 2024年半年度报告显示&#xff0c;路畅科技营业收入1.35亿元&#xff0c;同比下滑7.83%&#xff1b;实现归属上市公司股东的净利润为亏损2491.99万元…
阅读更多...
一篇讲完CSS的核心内容

一篇讲完CSS的核心内容

目录 一 、引言 1.1CSS概念 二、 CSS简介 2.1 什么是CSS 2.2 CSS能干什么 2.3 CSS书写规范 2.4 基础语法 三、 CSS导入方式 3.1 内嵌方式(内联方式) 3.2 内部方式 3.3 外部方式 四、 CSS选择器 4.1 基本选择器 [重点] 4.2 属性选择器 五、 CSS属性 5.1 文字属性…
阅读更多...
sheng的学习笔记-AI-强化学习（Reinforcement Learning, RL）

sheng的学习笔记-AI-强化学习（Reinforcement Learning, RL）

AI目录&#xff1a;sheng的学习笔记-AI目录-CSDN博客 基础知识 什么是强化学习 强化学习&#xff08;Reinforcement Learning, RL&#xff09;&#xff0c;又称再励学习、评价学习或增强学习&#xff0c;是机器学习的范式和方法论之一&#xff0c;用于描述和解决智能体&#…
阅读更多...
【RabbitMQ】RabbitMQ 的概念以及使用RabbitMQ编写生产者消费者代码

【RabbitMQ】RabbitMQ 的概念以及使用RabbitMQ编写生产者消费者代码

目录 1. RabbitMQ 核心概念 1.1生产者和消费者 1.2 Connection和Channel 1.3 Virtual host 1.4 Queue 1.5 Exchange 1.6 RabbitMO工作流程 2. AMQP 3.RabbitMO快速入门 3.1.引入依赖 3.2.编写生产者代码 ​3.3.编写消费者代码 4.源码 1. RabbitMQ 核心概念 在安装…
阅读更多...
Blender软件三大渲染器Eevee、Cycles、Workbench对比解析

Blender软件三大渲染器Eevee、Cycles、Workbench对比解析

Blender 是一款强大的开源3D制作平台&#xff0c;提供了从建模、雕刻、动画到渲染、后期制作的一整套工具&#xff0c;广泛应用于电影、游戏、建筑、艺术等领域。 渲染101云渲染云渲6666 相比于其他平台&#xff0c;如 Autodesk Maya、3ds Max 或 Cinema 4D&#xff0c;Blende…
阅读更多...
好用的idea方法分隔符插件

好用的idea方法分隔符插件

好用的idea方法分隔符插件
阅读更多...
频率增强通道注意力机制（FECAM）学习总结

频率增强通道注意力机制（FECAM）学习总结

本文提出了一种新的频率增强通道注意力机制&#xff08;FECAM&#xff09;&#xff0c;旨在解决时间序列预测中傅里叶变换因吉布斯现象导致的高频噪声问题。FECAM基于离散余弦变换&#xff0c;能自适应地模拟信道间的频率依赖性&#xff0c;有效避免预测误差。实验显示&#xf…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023