【C++容器】优先级队列 仿函数 反向迭代器

优先级队列，仿函数，反向迭代器

    • 优先级队列
      • 认识优先级队列
      • 模拟实现优先级队列
    • 浅谈仿函数
      • 仿函数的大致了解
      • 仿函数的实现
    • 反向迭代器
      • 什么是反向迭代器？
      • 反向迭代器的实现
    • 结语

优先级队列

认识优先级队列

优先级队列（priority_queue）不是队列。优先级队列是一种容器适配器，与栈（stack），队列（queue）具有类似的功能。

先来了解一下优先级队列有哪些功能。看下图：

在这里插入图片描述

优先级队列底层是一个堆（默认是大堆），第二个参数默认给的是vector，不适合list，第三个参数是仿函数（函数对象）。

在这里插入图片描述

模拟实现优先级队列

大部分成员函数可以通过调用vector的成员函数来实现。

#pragma once

namespace bit {
	//目前建堆默认大堆，如果想建小堆怎么办？
	template<class T, class Container = vector<T>>
	class priority_queue {
	private://不想让别人知道这两个函数，可以设置为私有
		void AdjustUp(int child)
		{
			//向上调整需要和兄弟比较吗？
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (_con[child] > _con[parent])
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
        //向下调整删除数据调用
		void AdjustDown(int parent)
		{
			Compare com;
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _con[child + 1] > _con[child])
				{
					++child;
				}
				if (com(_con[child], _con[parent]))
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
	public:
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			//传过来的迭代器可能不是有序的，所以要排序建堆。
			while (first != last)
			{
				push(*first);
				++first;
			}
		}
		priority_queue()//会调用vector的默认构造函数
		{}
		void push(const T& val)
		{
			_con.push_back(val);
			AdjustUp(_con.size() - 1);
		}
		const T& top() const
		{
			return _con[0];
		}
		bool empty() const
		{
			return _con.empty();
		}
		void pop()
		{
			//为什么swap不交换
			swap(_con[0], _con[_con.size() - 1]);
			//_con.size() - 1;//为什么这个程序不执行？执行了，但是size没变，只是_con.size() - 1
			_con.pop_back();
			AdjustDown(0);
		}
		void swap(priority_queue& pq)
		{
			std::swap(_con, pq._con);
		}
		size_t size() const
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

如果想建小堆，但不增加代码量的冗余，有办法吗？

浅谈仿函数

仿函数的大致了解

怎么建小堆？可以增加一个参数函数指针，这个函数来控制大堆还是小堆。但是函数指针声明比较复杂，有一些声明很长，导致通用性变差。所以，仿函数就来了。

写一个类，类中写相应的方法，这个类作为参数，那么就可以调用该类中的方法了。

仿函数（函数对象）不是函数调用，只是具有函数的功能。

如下代码是对上面代码的补充与修改

仿函数的实现

#pragma once

namespace bit {
	template<class T, class Container = vector<T>, class Compare = Greater<int>>
	class priority_queue {
	private://不想让别人知道这两个函数
		void AdjustUp(int child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[child], _con[parent]))
				{
					std::swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void AdjustDown(int parent)
		{
			Compare com;
			int child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
				{
					++child;
				}
				if (com(_con[child], _con[parent]))
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
	public:
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			//传过来的迭代器可能不是有序的，所以要排序建堆。
			while (first != last)
			{
				push(*first);
				++first;
			}
		}
		priority_queue()//会调用默认的构造函数
		{}
		void push(const T& val)
		{
			_con.push_back(val);
			AdjustUp(_con.size() - 1);
		}
		const T& top() const
		{
			return _con[0];
		}
		bool empty() const
		{
			return _con.empty();
		}
		void pop()
		{
			//为什么swap不交换
			swap(_con[0], _con[_con.size() - 1]);
			//_con.size() - 1;//为什么这个程序不执行？执行了，但是size没变，只是_con.size() - 1
			_con.pop_back();
			AdjustDown(0);
		}
		void swap(priority_queue& pq)
		{
			std::swap(_con, pq._con);
		}
		size_t size() const
		{
			return _con.size();
		}

	private:
		Container _con;
	};
}
template<class T>
struct Less
{
public:
	bool operator()(T& x, T& y)
	{
		return x > y;
	}
};
template<class T>
struct Greater
{
public:
	bool operator()(T& x, T& y)
	{
		return x < y;
	}
};

仿函数很方便，类中写许多的函数，资源的管理性不错，参数就可以只传一个类，封装性很强，灵活性很高。

反向迭代器

什么是反向迭代器？

**反向迭代器（reverse_iterator)**就是迭代器的相反。rbegin就是end，rend就是begin。

在这里插入图片描述

图中表示的rbegin，rend就是反向迭代器。

那如何实现反向迭代器呢？

反向迭代器的实现

仔细观察上面那张图，begin与rbegin，end与rend都是对称的。

·反向迭代器初始化可以调用正向迭代器的初始化

·反向迭代器++就是正向迭代器 的–，–就是正向迭代器的++。

先来看看库里面的反向迭代器是如何实现的。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

反向迭代器中有一个正向迭代器成员。++和–操作没有问题，都是调用正向迭代器的++和–函数，但是解引用（*）函数中为什么要–？

我们根据如下代码进行分析：

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    vector<int>::reverse_iterator rit = v.rbegin();
    for (rit != v.rend())
    {
     	cout << *rit << " ";
        ++rit;
	}
    cout << endl;
}

在这里插入图片描述
)rbegin 是由 end 初始化的，所以指向最后一个元素的下一个位置。所以解引用时，rbegin 要到前一个位置，返回前一个位置的元素，rbegin不变，rbegin 和 rend 相等时循环结束。

反向迭代器的实现：

//反向迭代器可以封装一个正向迭代器，各种操作可以调用正向迭代器的函数
template<class Iterator, class Ref, class Ptr>
class ReverseIterator {
private:
	Iterator _it;
public:
	typedef ReverseIterator<Iterator, Ref, Ptr> Self;
	ReverseIterator()//调用正向迭代器的构造函数
    {}
	ReverseIterator(const Iterator& it)
	:_it(it)//调用正向迭代器的拷贝构造函数
	{}
	Ref operator*()//解引用指向前一个位置的元素，本身不变。
	{
		Iterator tmp = _it;
		return *(--tmp);
	}
	Self& operator++()//调用正向迭代器--函数
	{
		--_it;
		return *this;
	}
	Self& operator--()//调用正向迭代器++函数
	{
		++_it;
		return *this;
	}
	bool operator!=(const Self& s)//调用正向迭代器的!=函数
	{
		return _it != s._it;
	}
};

结语

优先级队列（priority_queue）实现较为简单，与数据结构中的堆很相似。实现优先级队列与实现栈和队列的区别是：栈和队列可以直接复用其他容器的函数，优先级队列则需要自己加一些东西进去加工，如向下调整，仿函数等。

仿函数替换成函数指针。函数指针很麻烦，写个函数声明很长，读懂也容易绕晕。仿函数就是一个类，类中可以写许多函数，封装的很好，使用时很方便。

反向迭代器（reverse_iterator)就是理解解引用（*）的过程，写起来就是封装一个正向迭代器。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

自动化测试 —— 元素定位

自动化测试 —— 元素定位

1.什么是自动化测试 自动化测试的概念:软件自动化测试就是通过测试工具或者其他手段&#xff0c;按照测试人员的预定计划对软件产品进行自动化测试&#xff0c;他是软件测试的一个重要组成部分&#xff0c;能够完成许多手工测试无法完成或者难以实现的测试工作&#xff0c;正确…
阅读更多...
2、数仓理论概述与相关概念

2、数仓理论概述与相关概念

1、问&#xff1a;数据仓库 建设过程中 经常会遇到那些问题&#xff1f; 模型(逻辑)重复建设 数据不一致性 维度不一致&#xff1a;命名、维度属性值、维度定义 指标不一致&#xff1a;命名、计算口径 数据不规范(字段命名、表名、分层、主题命名规范) 2、OneData数据建设核心方…
阅读更多...
报表控件Stimulsoft 操作演示：空数据和 Dock 样式

报表控件Stimulsoft 操作演示：空数据和 Dock 样式

在今天的文章中&#xff0c;我们将讨论如何避免报告中出现空行。我们不仅会介绍在没有数据时禁用组件&#xff1b;还会介绍在没有数据时禁用组件。我们还将探索消除禁用组件时可能出现的空行。但在我们深入探讨之前&#xff0c;让我们检查一下数据带的零数据样本。 Stimulsoft…
阅读更多...
关于ego-planner里面的GridMap

关于ego-planner里面的GridMap

浙大这套开源的代码写得很nice 很值得借鉴 &#xff0c; 对于 GridMap 类的实现。该类通过智能指针的封装简化了 GridMap 实例的创建和管理过程。一旦通过 GridMap::initMap(ros::NodeHandle &nh) 方法初始化&#xff0c;就可以方便地调用 GridMap 及其所有相关功能 它主要…
阅读更多...
PLC 交互逻辑

PLC 交互逻辑

阅读更多...
智能化学习打破资源障碍 成为英语学习新趋势

智能化学习打破资源障碍 成为英语学习新趋势

智能化学习是一种基于互联网和人工智能技术的学习行为,通过网络,学习者可以随时随地进行学习,真正打破了时间和空间的限制。与传统线下学习方式相比,智能化学习更加方便、资源更加丰富,使海量英语学习资源唾手可得,智能化学习正逐渐成为中国孩子习得英语的重要方式。 随着全球…
阅读更多...
通过AX6000路由器，实现外部访问内网的任意主机

通过AX6000路由器，实现外部访问内网的任意主机

概述 这里遇到一个场景，就是需要外部的人员，访问我内网的一台设备，进行内外部的设备联调。 这也是实际环境中，很常见的一种场景。 之前的做法是子设备上运行edge节点，可以直接访问。 但有的设备无法运行edge节点，那么可以参考一下这个方案来实现。 此方案可以摒弃了…
阅读更多...
分享-Spss下载含spss25.spss26.spss27等版本

分享-Spss下载含spss25.spss26.spss27等版本

为了学习spss买的&#xff0c;分享安装程序给大家 SPSS 27是一款用于统计分析和数据挖掘的软件&#xff0c;以下是SPSS 27的功能介绍和配置建议&#xff1a; 功能介绍&#xff1a; 数据管理&#xff1a;SPSS 27可以对数据进行管理和清洗&#xff0c;包括数据输入、缺失值处理…
阅读更多...
什么是开关电源测试系统？如何用它进行测试？

什么是开关电源测试系统？如何用它进行测试？

开关电源测试系统是针对开关电源测试而开发的一种智能自动化测试系统&#xff0c;打破传统测试程序与缺陷&#xff0c;满足客户新的测试需求&#xff0c;助力客户解决测试难点&#xff0c;顺利完成开关电源测试&#xff0c;提高测试效能。那么开关电源自动化测试方案的流程是什…
阅读更多...
【漏洞复现】DPTech VPN存在任意文件读取漏洞

【漏洞复现】DPTech VPN存在任意文件读取漏洞

漏洞描述 DPtech是在网络、安全及应用交付领域集研发、生产、销售于一体的高科技企业。DPtech VPN智能安全网关是迪普科技面向广域互联应用场景推出的专业安全网关产品&#xff0c;集成了IPSec、SSL、L2TP、GRE等多种VPN技术&#xff0c;支持国密算法&#xff0c;实现分支机构…
阅读更多...
监控摄像头连接NAS，实现监控管理一体化

监控摄像头连接NAS，实现监控管理一体化

嗯&#xff1f;你问干嘛要把摄像头连到NAS&#xff1f; 小马给家里安了个监控摄像头 本意是想家里有啥事也能查监控 却没想到这些监控不仅存储回放有限制 要想更多功能还是得多花钱 恰好&#xff0c;我有铁威马NAS 打开Surveillance Manager 轻松搭建网络摄像头管理系统 …
阅读更多...
一键去水印免费网站快速无痕处理图片、视频水印

一键去水印免费网站快速无痕处理图片、视频水印

水印问题往往是一个大麻烦。即使我们只想将这些照片保留在我们的个人相册中以供怀旧&#xff0c;水印也可能像顽固的符号一样刺激我们的眼睛。为了解决这个问题&#xff0c;我们需要不断探索创新的解决方案&#xff0c;让我们深入研究一款强大的一键去水印免费网站“水印云”。…
阅读更多...
ubuntu下docker环境使用GPU配置

ubuntu下docker环境使用GPU配置

本文主要讲述整个命令流程&#xff0c;具体讲解请看官网nvidia-容器工具包和一篇总结得很详细的博文docker使用GPU总结 docker的版本必须安装19.0版本以上的&#xff0c;这里也只讲19.0版本以上的使用方法 首先设置一下网络信息 curl -fsSL https://nvidia.github.io/libnvi…
阅读更多...
Less精简直接上手,纯干货教程

Less精简直接上手,纯干货教程

目录 介绍 安装插件 入门使用测试 ​编辑 less变量 介绍 less作为一门CSS扩展语言&#xff0c;也就是说CSS预处理器。&#xff08;Leaner Style Sheets&#xff09;简称less&#xff0c;它只不过是为css新增这些的功能&#xff0c;比如说&#xff1a;变量、函数、作用域等等…
阅读更多...
【高级网络程序设计】Week3-2 Servlet

【高级网络程序设计】Week3-2 Servlet

一、 What are servlets? 1. 定义 &#xff08;1&#xff09;Servlets are Java’s answer to CGI&#xff1a; programs that run on a web server acting as middle layer between HTTP request and databases or other applications.Used for client requests that cann…
阅读更多...
Tekton — 通过tekton-operator部署tekton组件

Tekton — 通过tekton-operator部署tekton组件

文章目录 版本信息部署准备安装卸载tekton组件 Tektoncd Operator 作为一个 Kubernetes 的扩展&#xff0c;可以方便快捷地在 Kubernetes 集群上安装、升级和管理 Tekton Pipelines、Dashboard、Triggers 等组件。 那么本篇文章介绍在K8S集群中如何通过tekton-operator部署Tekt…
阅读更多...
如何使用ArcGIS Pro进行坐标转换

如何使用ArcGIS Pro进行坐标转换

不同来源的数据坐标系可能是不同的&#xff0c;为了统一使用这些数据就需要进行坐标转换&#xff0c;ArcGIS Pro作为专业的GIS软件&#xff0c;坐标转换功能肯定也是包含的&#xff0c;这里为大家介绍一下ArcGIS Pro如何进行坐标转换&#xff0c;希望能对你有所帮助。 数据来源…
阅读更多...
OFI libfabric原理及应用解析

OFI libfabric原理及应用解析

Agenda 目录/议题 编译通信软件硬件和软件带来的挑战为什么需要libfabriclibfabric架构API分组socket应用 VS libfabric应用区别GPU数据传输示例 编译通信软件 可靠面向连接的TCP和无连接的数据报UDP协议高性能计算HPC或人工智能AI 软硬件复杂性带来的挑战 上千个节点的集群, …
阅读更多...
【算法-哈希表4】 三数之和（去重版）

【算法-哈希表4】 三数之和（去重版）

今天&#xff0c;带来哈希相关算法的讲解。文中不足错漏之处望请斧正&#xff01; 理论基础点这里 三数之和 分析题意 这就是三数之和去重版嘛。 题意转化 求三元组, 满足每个元素相加为0&#xff0c;其中每个元素下标不同&#xff1b;而得到的三元组不能重复。 构成三元…
阅读更多...
【20年扬大真题】删除字符串s中的所有空格

【20年扬大真题】删除字符串s中的所有空格

【20年扬大真题】 删除字符串s中的所有空格 代码思路&#xff1a; 可以定义一个辅助的字符数组tmp&#xff0c;一边遍历字符串s&#xff0c;一边用tmp暂存s中的非空格元素。 遍历完s之后&#xff0c;再把tmp中的元素赋给字符串s即可 #include<stdio.h> #define MaxSize…
阅读更多...
最新文章

Copyright @ 2022~2023