【C++】stack、queue模拟实现+仿函数

stack、queue模拟实现+仿函数

  • stack
    • 定义
    • stack模拟实现
  • queue
    • 定义
    • queue模拟实现
  • priority_queue
    • 定义
    • priority_queue模拟实现
  • deque
    • 定义
    • 底层分析
  • 容器适配器
    • 定义
    • 种类
  • 仿函数
  • 控制类里面数据的比较逻辑
    • 回调函数
    • 仿函数
    • 两者区别

铁汁们，今天给大家分享一篇stack、queue模拟实现+仿函数，来吧，开造⛳️

stack

定义

在这里插入图片描述

  • stack是容器适配器，专门用于进行”先进后出”操作的环境中，只能在容器的一端进行数据的插入和删除操作，元素在特定容器的尾部(即栈顶)被压入和弹出。
  • 容器适配器是将特定的类进行封装，将其作为该容器的底层容器，通过调用底层容器提供的一系列成员函数来实现该容器。
  • stack的底层容器既可以是任何标准容器类模板(list、vector、deque),也可以是其他特定的容器类,它必须支持以下操作：push_back()->入栈、pop_back()->出栈、back()->获取栈顶元素、empty()->判断栈是否为空、size()->获取栈中元素总个数。
  • stack底层容器可以是list、vector、deque,若未实例化指定特定的底层容器，则默认为deque。
  • 栈空间从高地址往低地址方向增长，堆从低地址往高地址方向增长。
template<class T, class Container = deque<T>> 
class stack {

private:
	Container _con;
};

stack模拟实现

在这里插入图片描述在这里插入图片描述

template<class T, class Container = deque<T>> 
class stack {
public:
    stack()  //构造空栈
	{  }

	void push(const T& val)  //入栈
	{
		_con.push_back(val);
	}
		 
	void pop()  //出栈
	{
		_con.pop_back();
	}
		 
	T& top() //获取栈顶元素 可读可修改
	{
		return _con.back();
	}

	const T& top()const  //获取栈顶元素 只可读不可修改
	{
		return _con.back();
	}

	bool empty()const  //判断栈是否为空
	{
		return _con.empty();
	}
		 
	size_t size()const //获取栈中元素的总个数
	{
		return _con.size();
	}

private:
	Container _con;  //底层容器创建的对象
};

queue

定义

  • queue是容器适配器，专门用于进行”先进先出”操作的环境中，从容器的一端插入数据并从容器的另一端取出数据。
  • 容器适配器是将特定的类进行封装，将其作为该容器的底层容器，通过调用底层容器提供的一系列成员函数来实现该容器。
  • queue的底层容器既可以是某些标准容器类模板(list、deque),也可以是其他特定的容器类,它必须支持以下操作：push_back()->入队、pop_front()->出队、back()->获取队尾元素、front()->获取队头元素、empty()->判断队列是否为空、size()->获取队列中元素总个数。
  • queue底层容器可以是list、deque,但不可以是vector(没有支持pop_front())，若未实例化指定特定的底层容器，则默认为deque。
  • 队列从队尾入队列，从队头从队列。
template<class T, class Container = deque<T>>
class queue {

private:
	Container _con; //底层容器创建的对象
};

queue模拟实现

在这里插入图片描述在这里插入图片描述

template<class T, class Container = deque<T>>
class queue {
public:
    queue() //构造空队列
	{ }

	void push(const T& val)  //入队
	{
		_con.push_back(val);
	}

	void pop() //出队
	{
		_con.pop_front();
	}

	T& front() //获取队头元素 可读可修改
	{
		return _con.front();
	}

	const T& front()const  //获取队头元素 只可读不可修改
	{
		return _con.front();
	}

	T& back()  //获取队尾元素
	{
		return _con.back();
	}

	const T& back()const //获取队尾元素 只可读不可修改
	{
		return _con.back();
	}

	bool empty()const  //判断队列是否为空
	{
		return _con.empty();
	}

	size_t size()const  //获取队列中元素的总个数
	{
    	return _con.size();
	}

private:
	Container _con; //底层容器创建的对象
};

priority_queue

定义

在这里插入图片描述

  • priority_queue为优先队列，是容器适配器，默认情况下元素呈降序排列，且它的第一个元素总是它所有元素中最大的。
  • 容器适配器是将特定的类进行封装，将其作为该容器的底层容器，通过调用底层容器提供的一系列成员函数来实现该容器。元素从优先队列的顶部弹出。
  • priority_queue的底层容器既可以是某些标准容器类模板(vector、deque),也可以是其他特定的容器类,它必须支持以下操作：push_back()->插入元素、pop_back()->删除元素、front()->获取优先队列顶部的元素、empty()->判断优先队列是否为空、size()->获取优先队列中元素总个数。
  • priority_queue底层容器可以是vector、deque,但不可以是list(不支持随机访问[])，若未实例化指定特定的底层容器，则默认为vector。
  • priority_queue底层结构为堆，所有需要用到堆的地方，都可以考虑使用priority_queue。默认情况下为大堆，即小于less-》降序(大堆），greater-》升序(小堆)。
  • priority_queue底层容器要支持随机访问，以保持堆的结构。在堆中可以随时插入数据，且只检索到最大元素(大堆)或者最小元素(小堆）。
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue {

private:
	Container _con;
	Compare _com;
};

priority_queue模拟实现

在这里插入图片描述

💡void push(const T& val) ；

  • 方法: 在堆的底部插入元素，在采用向上调整法

在这里插入图片描述

💡void pop( )

  • 方法: 堆顶元素和堆中最后一个元素交换，在删除最后一个元素，在采用向下调整法

在这里插入图片描述

//仿函数:功能像函数，但它就是个类模板，重载了operator(),通过将其设置为类模板参数，在其他类中通过该参数创造出对象，直接()调用
template<class T> //设计为类模板，泛型编程，是为了支持所有数据类型的比较
class less {  //小于
public:
	bool operator()(int x, int y)
	{
		return x < y;
	}
};

template<class T>
class greater { //大于
public:
	bool operator()(int x, int y)
	{
		return x > y;
	}
};

template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue {//默认为大堆，且底层容器为vector
public:
	priority_queue()  //构造空优先队列
	{ }

	void Adjust_up(int child)  //向上调整法
	{
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			if (_com(_con[parent], _con[child])) 
			{
				std::swap(_con[child], _con[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
				break;
		}
	}

	void Adjust_down(int parent) //向下调整法
	{ //找到左、右孩纸中最大一个 -》假设法，假设左孩纸大，在与右孩纸进行比较
		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])) // 默认情况下为大堆，大的优先级高
			{
				std::swap(_con[child], _con[parent]);
				parent = child;
    			child = parent + 1;
			}
			else
				break;  //前提:该堆已经是个大堆(小堆)了
		}
	}

	void pop() //堆顶元素和堆中最后一个元素交换，在删除最后一个元素，在采用向下调整法
	{
		std::swap(_con[0], _con[size() - 1]);
		_con.pop_back();

		Adjust_down(0);
	}

	void push(const T& val) //在堆的底部插入元素，在采用向上调整法
	{
		_con.push_back(val); 

		Adjust_up(size() - 1);
	}

	const T& top()const //获取优先队列中顶部元素，即：堆顶元素
	{
		return _con.front();
	}

	bool empty()const  //判断优先队列是否为空
	{
		return _con.empty();
	}

	int size()const  //获取优先队列中总元素个数
	{
		return _con.size();
	}

private:
	Container _con;  //底层容器创建的对象
	Compare _com;  //仿函数类创建的对象
};

deque

定义

  • deque是双端队列，是一种双开口的“连续”空间的数据结构，可以在头尾进行插入和删除操作，时间复杂度为O(1),与vector相比，头插效率高，不需要挪动数据，与list相比，空间利用率高，缓存命中率高。
  • deque实际上并不是连续的空间，而是由一段段连续的小空间拼接而成，为了维护其"整体的连续"以及随机访问。deque底层类似于动态二维数组。
    在这里插入图片描述

底层分析

在这里插入图片描述在这里插入图片描述

  • 与list相比 ，缓存命中率高，空间利用率高，因为deque底层空间连续。deque支持随机访问。
  • 与vector相比 ，对于在头、尾部插入和删除上，效率高于vector，因为不需要挪动数据。对于在扩容消耗上，效率高于vector，因为不需要频繁挪动数据，只要"中控"满了扩容就可以了，且只需要拷贝指针(4个字节)。
  • stack和deque为容器适配器，不需要遍历数据，所以它们没有迭代器，只需要在固定一端或者两端进行插入和删除数据。在插入元素时，deque效率高于vector(扩容消耗小），相比于list，deque不仅头、尾插效率高，且内存利用率高。综上所述，选择deque作为stack和deque默认的底层容器更有优势。

容器适配器

定义

  • 适配器是一种设计模式，该模式是将一种接口转换成另一种接口。
  • 容器适配器是一个对特定的类进行封装的类模板，它在底层容器的基础上提供了一些其他的功能。它是适配其他容器来提供不同的功能，通过调用底层容器提供的一系列成员函数来实现我们需要的功能。
  • stack和queue都可以存储元素，但未将他们划分到容器序列，而是将他们称为容器适配器，是因为stack和queue是对其他容器进行了封装，默认情况下，stack和queue的底层容器为deque。
    在这里插入图片描述
  • 💡Tips : 容器适配器中不存在迭代器。

种类

三种容器适配器：stack、queue、priority_queue。

在这里插入图片描述

仿函数

  • 💡仿函数：又称为函数对象，是一个重载了operator()运算符的类。
  • 仿函数，不是函数，在语法上与普通函数调用的语法调用一样，在功能上仿函数通过创建的对象去调用operator()运算符，从而达到函数一样的功能。
//仿函数
template<class T>
class less { //小于
public:
    bool operator()(int x, int y)
    {
    	return x < y;
    }
};

 template<class T>
class greater {  //大于
public:
    bool operator()(int x, int y)
    {
    	return x > y;
    }
};

void test()
{
	less<int> LessFu;
	cout << LessFu(3, 4) << endl;

	greater<int> GreaterFu;
	cout << GreaterFu(3, 4) << endl;
}

int main()
{
    test();

	return 0;
}

在这里插入图片描述

控制类里面数据的比较逻辑

回调函数

  • 回调函数就是一个通过函数指针调用的函数。如果你把函数的地址作为参数传递给另一个函数，当这个指针被用来调用其所指向的函数时，我们就说被调用的函数称为回调函数。回调函数不是由该函数的实现方直接调用，而是在特定的事件或条件发生时由另外的一方调用的，用于对该事件或条件进行响应。
namespace yun {
	bool Less(int x, int y)
	{
		return x < y;
}

	bool Greater(int x, int y)
	{
		return x > y;
	}

	//在A这个类中调用
	class A1 {
	public:
		A1(bool(*pf)(int, int))
			:_pf(pf)
		{ }

		void fun(int x, int y)
		{
			cout << _pf(x, y) << endl;  //回调函数
		}

		bool(*_pf)(int, int);
	};

	//通过回调函数去调用:缺点-》函数指针类型抒写太复杂、需要通构构造函数参数传递(成员变量_pf为虚拟指针，无值）
	void test1()
	{
		A1 aa1(Less); 
		aa1.fun(3, 4);
		A1 aa2(Greater);
		aa2.fun(3, 4);
	}
}

int main()
{
	yun::test1();  //回调函数
    
	return 0;
}

在这里插入图片描述

仿函数

namespace yun {
    //仿函数
	template<class T>
	class less { //小于
	public:
		bool operator()(int x, int y)
		{
			return x < y;
		}
	};

	template<class T>
	class greater {  //大于
	public:
		bool operator()(int x, int y)
		{
			return x > y;
		}
	};

	template<class T, class Compare = less<T>> 
	class A2{  
	public:
		void fun(int x, int y)
		{
			cout << _com(x, y) << endl;  //调用仿函数，实际上就是通过类对象去调用operator()运算符
		}

	private:
		Compare _com; //创建仿函数对象
	};


	void test2() 
	{
		A2<int, less<int>> aa2;
		aa2.fun(5, 6);
		A2<int, greater<int>> aa3;
		aa3.fun(5, 6);
	}
}

int main()
{
	yun::test2();  //仿函数
    
	return 0;
}

在这里插入图片描述

两者区别

  • 回调函数缺点：函数指针类型相对比较复杂、只能通过函数参数传递（在类中，通过构造函数参数传递，且需要定义函数指针类型的成员变量，进行值的接收，从而实现回调。在普通函数中，通过函数参数直接传递)。
  • 仿函数优点：类型相对比较简单、只需要在类中创建对象，通过该对象去调用operator()运算符，就可以实现回调。

铁铁们，就到此结束啦，若博主有不好的地方，请指正，欢迎铁铁们留言，请动动你们的手给作者点个👍鼓励吧，你们的鼓励就是我的动力✨

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

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

相关文章

Vue+SpringBoot打造服装店库存管理系统

Vue+SpringBoot打造服装店库存管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 角色管理模块2.3 服装档案模块2.4 服装入库模块2.5 服装出库模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 角色表3.2.2 服装档案表3.2.3 服装入库表3.2.4 服装出库表 四、系统展示五、核心代码5.…
阅读更多...
算法打卡day17|二叉树篇06|Leetcode 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

算法打卡day17|二叉树篇06|Leetcode 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

算法题 Leetcode 654.最大二叉树 题目链接:654.最大二叉树 大佬视频讲解&#xff1a;最大二叉树视频讲解 个人思路 大概思路就是在数组中 找最大值的节点作为当前节点&#xff0c;用最大值的index切割左右子树的区间&#xff0c;往复循环到数组元素为0&#xff1b; 解法 递…
阅读更多...
【数据结构】二叉搜索树底层刨析

【数据结构】二叉搜索树底层刨析

文章目录 1. 二叉搜索树的实现2. 二叉搜索树的应用3. 改造二叉搜索树为 KV 结构4. 二叉搜索树的性能分析 1. 二叉搜索树的实现 namespace key {template<class K>struct BSTreeNode{typedef BSTreeNode<K> Node;Node* _left;Node* _right;K _key;BSTreeNode(const…
阅读更多...
【1】Python零基础起步

【1】Python零基础起步

什么是编程(Programming) 编程是编定程序的中文简称&#xff0c;就是让计算机代码解决某个问题&#xff08;目的&#xff09;&#xff0c;对某个计算体系规定一定的运算方式&#xff0c;使计算体系按照该计算方式运行&#xff0c;并最终得到相应结果的过程&#xff08;手段&am…
阅读更多...
Java Day 10 io流

Java Day 10 io流

IO流 1、前置知识 字符集1.1 标准ASCII1.2 GBK编码1.3 UTF-321.4 UTF-81.5 编码和解码方法 2、IO流2.1 流的分类2.2 FileInputStream2.2.1 常用方法 2.3 FileOutputStram2.3.1 常用方法2.3.2 文件复制案例 2.4 释放资源的方式2.4.1 try-catch-finally2.4.2 try-with-resource 1…
阅读更多...
ftp和fxp哪个传传输快，传输大文件该怎么选择？

ftp和fxp哪个传传输快，传输大文件该怎么选择？

在当今数字化时代&#xff0c;大文件传输已成为日常工作和商业活动中不可或缺的一部分。无论是跨国公司的数据交换&#xff0c;还是个人用户的大型媒体文件分享&#xff0c;选择一个高效的传输协议至关重要。FTP和FXP是两种常用的文件传输方式&#xff0c;但在传输大文件时&…
阅读更多...
nginx gzip性能优化 —— 筑梦之路

nginx gzip性能优化 —— 筑梦之路

对比使用和不使用gzip static处理 1. 不使用 gzip static 时的 gzip 处理 如果你不使用 gzip_static 而只是 "gzip on"&#xff0c;它每次都会被压缩并发送。 虽然它实际上可能缓存在内存中&#xff0c;但传统观点是 "每次都会执行压缩处理&#xff0c;因此 CP…
阅读更多...
【SRE系列之docker容器】--dockerfile镜像优化

【SRE系列之docker容器】--dockerfile镜像优化

dockerfile镜像优化 1.1 镜像优化方法 系统镜像采用ubuntu或者alpine&#xff0c;会比centos少1G左右编写业务镜像时从官网拉取镜像&#xff0c;其余配置根据业务需求再配置编写dockerfile时把不用的安装包卸载或者删除尽量减少run命令的使用&#xff08;一个run命令&#xf…
阅读更多...
【兆易创新GD32H759I-EVAL开发板】图像处理加速器（IPA）的应用

【兆易创新GD32H759I-EVAL开发板】图像处理加速器（IPA）的应用

GD32H7系列的IPA&#xff08;Image Pixel Accelerator&#xff09;是一个高效的图像处理硬件加速器&#xff0c;专门设计用于加速图像处理操作&#xff0c;如像素格式转换、图像旋转、缩放等。它的优势在于能够利用硬件加速来实现这些操作&#xff0c;相比于软件实现&#xff0…
阅读更多...
YOLOv9实例分割教程|（二）验证教程

YOLOv9实例分割教程|（二）验证教程

专栏地址&#xff1a;目前售价售价59.9&#xff0c;改进点30个 专栏介绍&#xff1a;YOLOv9改进系列 | 包含深度学习最新创新&#xff0c;助力高效涨点&#xff01;&#xff01;&#xff01; 一、验证 打开分割验证文件&#xff0c;填入数据集配置文件、训练好的权重文件&…
阅读更多...
go语言基础笔记

go语言基础笔记

1.基本类型 1.1. 基本类型 bool int: int8, int16, int32(rune), int64 uint: uint8(byte), uint16, uint32, uint64 float32, float64 string 复数&#xff1a;complex64, complex128 复数有实部和虚部&#xff0c;complex64的实部和虚部为32位&#xff0c;complex128的实部…
阅读更多...
yocto是个什么东东

yocto是个什么东东

yocto不是个什么东东 在我们了解Yocto项目是什么之前&#xff0c;让我们先了解一下它不是什么。 Yocto项目不是用于现有硬件的软件开发工具包&#xff08;SDK&#xff09;&#xff0c;而是用于构建这样一个工具包。 Yocto项目不是可以部署到硬件上的系统二进制镜像&#xff…
阅读更多...
客服销冠偷偷用的提效神器！无广很实用

客服销冠偷偷用的提效神器！无广很实用

近期发现我的同事每天上班必登录的一款软件——客服宝聊天助手&#xff0c;用过才发现&#xff1a;真客服办公的提效神器&#xff01;感兴趣的小伙伴请往下看~一、客服宝的简介&#xff1a;客服宝聊天助手&#xff0c;是一款跨平台快捷回复工具。自带多种功能&#xff0c;有效帮…
阅读更多...
leetcode判断子序列

leetcode判断子序列

本题中&#xff0c;我们可以删除原始字符串的一些字符但是不能改变其他字符的位置&#xff0c;这种求子序列的题都可以用动态规划来解决。 首先我们要确定dp数组的定义&#xff0c;这里我们将dp数组定义为dp[i][j] 表示以下标i-1为结尾的字符串s&#xff0c;和以下标j-1为结尾的…
阅读更多...
蓝桥杯[OJ 1621]挑选子串-CPP-双指针

蓝桥杯[OJ 1621]挑选子串-CPP-双指针

目录 一、题目描述&#xff1a; 二、整体思路&#xff1a; 三、代码&#xff1a; 一、题目描述&#xff1a; 二、整体思路&#xff1a; 要找子串&#xff0c;则必须找头找尾&#xff0c;找头可以遍历连续字串&#xff0c;找尾则是要从头的基础上往后遍历&#xff0c;可以设头…
阅读更多...
OSCP靶场--BlackGate

OSCP靶场--BlackGate

OSCP靶场–BlackGate 考点(1.redis rce 2. CVE-2021-4034提权) 1.nmap扫描 ┌──(root㉿kali)-[~/Desktop] └─# nmap -sV -sC -p- 192.168.163.176 --min-rate 2500 Starting Nmap 7.92 ( https://nmap.org ) at 2024-03-14 03:32 EDT Nmap scan report for 192.168.163.…
阅读更多...
MongoDB实战面试指南：常见问题一网打尽

MongoDB实战面试指南：常见问题一网打尽

码到三十五 &#xff1a; 个人主页 心中有诗画&#xff0c;指尖舞代码&#xff0c;目光览世界&#xff0c;步履越千山&#xff0c;人间尽值得 ! MongoDB是一款流行的非关系型数据库&#xff0c;以其高效、可扩展的特性受到开发者的青睐。了解MongoDB的架构、存储引擎和数据结…
阅读更多...
python 基础知识点（蓝桥杯python科目个人复习计划63）

python 基础知识点（蓝桥杯python科目个人复习计划63）

今日复习内容&#xff1a;做题 例题1&#xff1a;蓝桥骑士 问题描述&#xff1a; 小蓝是蓝桥王国的骑士&#xff0c;他喜欢不断突破自我。 这天蓝桥国王给他安排了N个对手&#xff0c;他们的战力值分别为a1,a2,...,an&#xff0c;且按顺序阻挡在小蓝的前方。对于这些对手小…
阅读更多...
剪辑设计软件如何跨系统使用？PC也能用Mac Final Cut

剪辑设计软件如何跨系统使用？PC也能用Mac Final Cut

我猜你工作中&#xff0c;常常遇到这样那样的麻烦&#xff1a; 临时接手一个项目&#xff0c;之前的同事用Final Cut&#xff0c;而你是Windows系统&#xff1b; 临时有紧急需求要调整&#xff0c;而本地电脑却没有工作软件/性能不给力&#xff1b; 那这样的情况&#xff0c…
阅读更多...
SSL证书如何实现数据加密传输？

SSL证书如何实现数据加密传输？

在当前互联网的洪流中&#xff0c;用户对网站隐私与安全性的重视程度日益提升。为了确保用户信息和交易数据的安全传输&#xff0c;SSL证书在网络世界中扮演了关键角色。本文将深入解析SSL证书的核心功能及其重要作用。 1、SSL证书采用加密技术保障数据传输安全 通过应用公钥加…
阅读更多...
最新文章

Copyright @ 2022~2023