模拟实现（优先级队列）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.xdnf.cn/news/1543426.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

面向对象 vs 面向过程

面向对象 vs 面向过程

Java 和 C 语言的区别&#xff1a;面向对象 vs 面向过程 在编程世界中&#xff0c;不同的编程语言承载着不同的编程范式。C 语言作为一门经典的面向过程编程语言&#xff0c;注重函数的调用和操作&#xff1b;而Java则是典型的面向对象编程语言&#xff0c;重视对象与类的设计…
阅读更多...
【计算机网络】传输层协议TCP

【计算机网络】传输层协议TCP

目录 一、重新理解封装和解包二、TCP协议段格式三、确认应答(ACK)机制四、超时重传机制五、连接管理机制六、理解TIME_WAIT状态和CLOSE_WAIT状态七、流量控制八、滑动窗口九、拥塞控制十、延迟应答十一、面向字节流十二、粘包问题 一、重新理解封装和解包 在网络协议栈中&…
阅读更多...
【LeetCode】动态规划—第 N 个泰波那契数（附完整Python/C++代码）

【LeetCode】动态规划—第 N 个泰波那契数（附完整Python/C++代码）

动态规划—#1137. 第 N 个泰波那契数 前言题目描述基本思路1. 泰波那契数列的定义:2. 理解递推关系:3. 解决方法:4. 进一步优化:5. 小总结: 代码实现Python3代码实现Python 代码解释C代码实现C 代码解释 总结: 前言 泰波那契数列是斐波那契数列的扩展版本。在斐波那契数列中&a…
阅读更多...
三款远控工具大比拼，哪款更胜一筹？

三款远控工具大比拼，哪款更胜一筹？

当我们处在日益便捷的数字化生活中&#xff0c;我们不仅需要在实体空间与物理环境间活动&#xff0c;我们更可以通过科技的力量在屏幕间自由穿梭&#xff1b;向日葵远程控制工具&#xff0c;就是这样一款能让你在指尖上体验到操作乐趣的神奇工具&#xff1b;今天&#xff0c;就…
阅读更多...
着色器（Vertex Shader）基础

着色器（Vertex Shader）基础

什么是顶点着色器 顶点着色器处理顶点并告知它们在“剪辑空间”中的坐标，该空间使计算机可以轻松了解哪些顶点对摄像机可见，哪些顶点不可见，必须剪切或“剪切”掉。 这使得 GPU 在后期阶段的速度更快，因为它们需要处理的数据较少。 它们通过接收来自顶点列表中的单个顶…
阅读更多...
优可测一键闪测仪：实现冲压端子的快速精准尺寸检测

优可测一键闪测仪：实现冲压端子的快速精准尺寸检测

上期&#xff0c;小优博士讲述了和白光干涉仪在红外探测行业的应用与优势&#xff0c;今天&#xff0c;小优博士为大家继续带来&#xff1a; 《优可测一键式影像测量仪&#xff1a;实现冲压端子的快速精准尺寸检测》 冲压端子是通过金属冲压工艺制成&#xff0c;用于电气导线与…
阅读更多...
排序题目：将矩阵按对角线排序

排序题目：将矩阵按对角线排序

文章目录 题目标题和出处难度题目描述要求示例数据范围 前言解法思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;将矩阵按对角线排序 出处&#xff1a;1329. 将矩阵按对角线排序 难度 5 级 题目描述 要求 矩阵对角线是一条从矩阵最上面行或者最左侧列中的某…
阅读更多...
【C++代码运行结果测试】基类与派生类的成员变量值的调用结果

【C++代码运行结果测试】基类与派生类的成员变量值的调用结果

【铺垫】派生类对象可被基类指针所指向&#xff0c;效果与被派生类指针指向等效 【代码测试1】15浙工大卷一读程序5题代码改 【代码测试2】C教辅p206例7.21 【代码1】15浙工大卷一读程序5题代码改 #include "bits/stdc.h" #include<iostream> using namesp…
阅读更多...
谷歌发布新 RL 方法，性能提升巨大；苹果前设计总监正与 OpenAI 合作开发 AI 设备丨 RTE 开发者日报

谷歌发布新 RL 方法，性能提升巨大；苹果前设计总监正与 OpenAI 合作开发 AI 设备丨 RTE 开发者日报

开发者朋友们大家好&#xff1a; 这里是 「RTE 开发者日报」 &#xff0c;每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享 RTE&#xff08;Real-Time Engagement&#xff09; 领域内「有话题的 新闻 」、「有态度的 观点 」、「有意思的 数据 」、「有思考的 文…
阅读更多...
机器人顶刊IEEE T-RO发布无人机动态环境高效表征成果：基于粒子的动态环境连续占有地图

机器人顶刊IEEE T-RO发布无人机动态环境高效表征成果：基于粒子的动态环境连续占有地图

摘要&#xff1a;本研究有效提高了动态环境中障碍物建模的精度和效率。NOKOV度量动作捕捉系统助力评估动态占用地图在速度估计方面的性能。 近日&#xff0c;上海交通大学、荷兰代尔夫特理工研究团队在机器人顶刊IEEE T-RO上发表题为Continuous Occupancy Mapping in Dynamic …
阅读更多...
数据加密和数字证书

数据加密和数字证书

1 什么是数据加密 数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理，使其成为不可读的一段代码，通常称为"密文"，使其只能在输入相应的密钥之后才能显示出本来内容，通过这样的途径来达到保护数据不被非法人窃取、阅读的目的。 该过程的逆过程…
阅读更多...
人工智能课程实训方案

人工智能课程实训方案

第一章 发展背景 当今&#xff0c;世界无时无刻不在发生着变化。对于技术领域而言&#xff0c;普遍存在的一个巨大变化就是为大数据&#xff08;Big data&#xff09;打开了大门。随着国家大数据战略推进实施以及配套政策的贯彻落实&#xff0c;大数据产业发展环境进一步优化&a…
阅读更多...
2024.9.23

2024.9.23

阅读更多...
Tauri 应用 input 输入自动大写问题定位解决

Tauri 应用 input 输入自动大写问题定位解决

使用 Tauri React 开发 MinApi(http api接口测试工具) 时&#xff0c;在 Mac 系统中遇到一个很奇怪的问题&#xff1a;在 input 输入框中输入内容时&#xff0c;如果输入的是全小写英文字母&#xff0c;会自动将首字母转换为大写&#xff0c;效果如下图所示。 问题定位 经过排…
阅读更多...
JS执行机制(同步和异步)

JS执行机制(同步和异步)

JavaScript语言的一大特点就是单线程,也就是说,同一个时间只能做一件事。 异步:在做这件事的同时&#xff0c;你还可以去处理其他事 他们的本质区别&#xff1a;这条流水线上各个流程的执行顺序不同。 同步任务 同步任务都在主线程上执行&#xff0c;形成一个执行栈。 异步…
阅读更多...
asp.net core grpc快速入门

asp.net core grpc快速入门

环境 .net 8 vs2022 创建 gRPC 服务器 一定要勾选Https 安装Nuget包 <PackageReference Include"Google.Protobuf" Version"3.28.2" /> <PackageReference Include"Grpc.AspNetCore" Version"2.66.0" /> <PackageR…
阅读更多...
统信服务器操作系统a版e版【dde桌面限制登录次数】介绍

统信服务器操作系统a版e版【dde桌面限制登录次数】介绍

dde桌面登录规则、tty限制登录次数、ssh限制登录次数、ssh限制地点登录、本地限制终端登录、时间限制登录等内容 文章目录 功能概述功能介绍1.查看dde桌面登录规则2.tty限制登录次数3.ssh限制登录次数4.ssh限制地点登录5.本地限制终端登录6.时间限制登录 功能概述 限制dde桌面…
阅读更多...
【计算机基础】用bat命令将Unity导出PC包转成单个exe可执行文件

【计算机基础】用bat命令将Unity导出PC包转成单个exe可执行文件

Unity打包成exe可执行文件 上边连接是很久以前用过的方法&#xff0c;发现操作有些不一样了&#xff0c;并且如果按上述操作比较麻烦&#xff0c;所以写了个bat命令。 图1、导出的pc程序 如图1是导出的pc程序&#xff0c;点击exe文件可运行该程序。 添加pack_project.bat文件 …
阅读更多...
自学前端的正确姿势是...

自学前端的正确姿势是...

师傅带进门&#xff0c;修行在个人。 在前端自学成才的道路上&#xff0c;有些人走的很快&#xff0c;有些人却举步维艰。 为什么会这样子呢&#xff1f;因为他们没有掌握自学前端的正确姿势。 在介绍应该要怎样自学前端之前&#xff0c;首先来看下&#xff0c;自学前端容易…
阅读更多...
vue-router路由(重定向，嵌套，动态路由匹配，命名，高亮，守卫)

vue-router路由(重定向，嵌套，动态路由匹配，命名，高亮，守卫)

一、前端路由的概念与原理 路由router就是对应关系。分为前端路由和后端路由。 1后端路由 后端路由指的是&#xff1a;请求方式、请求地址与function处理函数之间的对应关系。在node.js中&#xff0c;express理由的基本用法如下&#xff1a; const express require(expres…
阅读更多...
最新文章

Copyright @ 2022~2023