C++STL-deque、stack、queue、priority_queue

C++教学总目录

deque、stack、queue、priority_queue

  • 1、deque
  • 2、stack使用介绍
  • 3、stack实现
  • 4、queue使用介绍
  • 5、queue实现
  • 6、priority_queue使用介绍
  • 7、priority_queue实现
  • 8、反向迭代器

1、deque

在这里插入图片描述
deque是双端队列，我们学习的队列是先进先出的(First in first out)，相比于队列，双端队列是支持头插头删、尾插尾删的。包含于头文件<deque>

我们之前学的vector实际上就是顺序表，它重载了operator[]，所以可以随意访问任意一个位置的元素，但是如果扩容需要挪动数据，消耗较大，并且头插头删/中间插入删除都需要挪动数据。
我们之前学的list是带头双向循环链表，它在任意位置的插入删除效率很高，并且不存在扩容问题，按需申请按需释放，但是不支持下标随机访问。
vector和string各有优缺点：而deque双端队列就是结合了vector和list的优点设计出来的，它支持任意位置的下标访问，也支持头插头删/尾插尾删。

下面这张图描述了deque的底层实现原理：
在这里插入图片描述

下面看看deque的接口：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
用法基本上同之前的vector，这里就不再赘述。由于deque的底层实现比较复杂，我们不模拟实现，有兴趣可以去看看库里是如何实现的。

2、stack使用介绍

在这里插入图片描述
栈是先进后出的一种数据结构，STL中的stack是一种容器适配器，包含于头文件<stack>，stack也是类模板，有两个模板参数，第一个T代表数据类型，第二个Container表示容器，模板参数也可以给缺省值，这里默认用deque来作为stack的容器。

下面是stack的核心接口：
主要是：1、size返回栈中元素个数。2、empty判断栈是否为空。3、top返回栈顶元素。4、push元素入栈。5、pop弹出栈顶元素。
在这里插入图片描述
stack是没有迭代器的，不能使用迭代器/范围for进行遍历，可以用下面方式遍历：

在这里插入图片描述

上面模板参数我们只给了类型，所以默认stack的底层容器就是deque，假设我不想用deque呢？我可以传vector或list：

stack<int, list<int>> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
while (st.size())
{
	cout << st.top() << " ";
	st.pop();
}

stack<int, vector<int>> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
while (st.size())
{
	cout << st.top() << " ";
	st.pop();
}

3、stack实现

我们直接使用deque作为stack的默认容器：

#pragma once

namespace zzy
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_back();
		}

		T& top() 
		{
			return _con.back();
		}

		size_t size() 
		{
			return _con.size();
		}

		bool empty() 
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

4、queue使用介绍

在这里插入图片描述
队列的性质是先进先出，STL中的queue和stack一样，都是容器适配器，默认底层容器也是deque。包含于头文件<queue>

下面给出核心接口：1、empty判断队列是否为空。2、size返回队列元素个数。3、front返回队头元素。4、back返回队尾元素。5、push在队尾插入元素。6、pop弹出队头元素。
在这里插入图片描述
queue也是没有迭代器的。用法如下：

在这里插入图片描述
和上面stack一样，如果不想使用deque作为queue的底层容器，可以自己传模板参数。

5、queue实现

#pragma once

namespace zzy
{
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		
		void pop()
		{
			_con.pop_front();
		}

		T& front()
		{
			return _con.front();
		}

		T& back()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

6、priority_queue使用介绍

在这里插入图片描述
priority_queue是优先级队列（堆），它也是容器适配器，包含于头文件<queue>
可以看到这里有三个模板参数，第三个是仿函数——用来控制比较大小从而实现大堆/小堆。

下面看看优先队列的接口：
在这里插入图片描述
1、empty判断堆是否为空。2、size计算堆中元素个数。3、top获取堆顶元素。4、push向堆中插入元素并调整堆。5、pop弹出堆顶元素并调整堆。

用法如下：
在这里插入图片描述
如果要用大堆，可以传仿函数的模板参数：

priority_queue<int, vector<int>, greater<int>> pq;
pq.push(10);
pq.push(24);
pq.push(17);
pq.push(30);
pq.push(1);
while (pq.size())
{
	cout << pq.top() << " ";
	pq.pop();
}

7、priority_queue实现

仿函数/函数对象：这个类对象可以像函数一样使用——实际上是重载了operator()
看下面的类：

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

int main()
{
	Less<int> lessfunc;
	cout << lessfunc(1, 2) << endl;  // 像函数一样使用
	cout << lessfunc.operator()(1, 2) << endl; // 实际上是重载了operator()
	return 0;
}

这就是仿函数。官方实现了less和greater两个仿函数，less比较就是<，而greater就是>。
针对内置类型，我们可以直接使用less和greater。如果是自定义类型，也可以使用less和greater，但是要保证自定义类型中重载了operator</operator>。
另外有些场景我们需要自己实现仿函数，例如存放的是指针类型。

下面是priority_queue的实现：

#pragma once

template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};

namespace zzy
{
	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;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					child++;
				}
				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 >> 1; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}
		
		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(_con.size() - 1);
		}

		const T& top()
		{
			return _con[0];
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}
	private:
		Container _con;
	};

	void test_priority_queue1()
	{
		priority_queue<int, vector<int>, Greater<int>> pq;

		pq.push(3);
		pq.push(5);
		pq.push(1);
		pq.push(4);

		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}

	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;
	}

	struct LessPDate
	{
		bool operator()(const Date* p1, const Date* p2)
		{
			return *p1 < *p2;
		}
	};

	void test_priority_queue2()
	{
		// 仿函数控制实现小堆
		//priority_queue<Date, vector<Date>, greater<Date>> pq;
		//pq.push(Date(2023, 7, 20));
		//pq.push(Date(2023, 6, 20));
		//pq.push(Date(2023, 8, 20));

		//while (!pq.empty())
		//{
		//	cout << pq.top() << " ";
		//	pq.pop();
		//}
		//cout << endl;

		priority_queue<Date*, vector<Date*>, LessPDate> pq;
		pq.push(new Date(2023, 7, 20));
		pq.push(new Date(2023, 6, 20));
		pq.push(new Date(2023, 8, 20));

		while (!pq.empty())
		{
			cout << *pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}
}

关于模板中的仿函数有一个注意点：
在这里插入图片描述

8、反向迭代器

反向迭代器的实现需要创建自定义类型，反向迭代器是一种适配器，通过对正向迭代器的封装来实现。
在这里插入图片描述
如图：反向迭代器的rbegin就是正向迭代器的end，反向迭代器的rend就是正向迭代器的begin，之所以这么设计是考虑了镜像对称。
因此，反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++。由于反向迭代器与容器中元素错位，所以实现operator*的时候需要–再解引用获取元素。

下面先给出模板参数：

template<class Iterator, class T, class Ref, class Ptr>

第一个模板参数是正向迭代器，后面两个Ref和Ptr是为了通过不同的参数实例化出普通反向迭代器和const反向迭代器。之所以还需要给一个T类型的模板参数是因为需要实现普通反向迭代器构造const反向迭代器的函数，否则无法使用const反向迭代器。

template<class Iterator, class T, class Ref, class Ptr>
struct ReverseIterator
{
	typedef ReverseIterator<Iterator, T, Ref, Ptr> self;
	typedef ReverseIterator<Iterator, T, T&, T*> reverseiterator;

	Iterator _it;

	ReverseIterator(Iterator it)
		:_it(it)
	{}

	ReverseIterator(const reverseiterator& it)
		:_it(it._it)
	{}

	Ref operator*()
	{
		Iterator tmp = _it;
		return *(--tmp);
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	self& operator++()
	{
		--_it;
		return *this;
	}
	
	self operator++(int)
	{
		self tmp(_it);
		--_it;
		return tmp;
	}

	self& operator--()
	{
		++_it;
		return *this;
	}

	self& operator--(int)
	{
		self tmp(_it);
		++_it;
		return tmp;
	}

	bool operator!=(const self& s) const
	{
		return _it != s._it;
	}

	bool operator==(const self& s) const
	{
		return _it == s._it;
	}
};

然后在容器中加入以下代码：

typedef ReverseIterator<iterator, T, T&, T*> reverse_iterator;
typedef ReverseIterator<iterator, T, const T&, const T*> const_reverse_iterator;

reverse_iterator rbegin() { return end(); }
reverse_iterator rend() { return begin(); }
const_reverse_iterator rbegin() const { return end(); }
const_reverse_iterator rend() const { return begin(); }

以上是实现方式之一，对于之前写的string和vector都可以使用。库里的实现方式是迭代器萃取，有兴趣可以了解一下。

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

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

相关文章

【c++篇】：掌握vector基础知识--基本操作与使用全知道

【c++篇】：掌握vector基础知识--基本操作与使用全知道

✨感谢您阅读本篇文章&#xff0c;文章内容是个人学习笔记的整理&#xff0c;如果哪里有误的话还请您指正噢✨ ✨个人主页&#xff1a;余辉zmh–CSDN博客 ✨文章所属专栏&#xff1a;c篇–CSDN博客 文章目录 前言一.vector的基本概念1.定义2.主要特性和优点 二.vector的基本操作…
阅读更多...
如何建购物网站提升用户体验

如何建购物网站提升用户体验

在构建一个购物网站时&#xff0c;用户体验是至关重要的&#xff0c;它直接影响到顾客的满意度和转化率。为了提升用户体验&#xff0c;可以从以下几个方面入手。 首先&#xff0c;网站设计应简洁明了。确保导航栏清晰易懂&#xff0c;让用户在寻找商品时不会迷失。此外&#x…
阅读更多...
勒索软件如何传播？

勒索软件如何传播？

在本文中&#xff0c;我们将讨论勒索软件对企业的影响并解释这些攻击的具体传播方式。 我们还将提供可采取的切实步骤来保护您自己和您的企业免受这些不断上升的威胁。 勒索软件对小型企业的攻击日益增多 勒索软件仍然是全球各种规模企业的头号威胁。 小型企业数据泄露的成…
阅读更多...
Claude 3.5 新功能 支持对 100 页的PDF 图像、图表和图形进行可视化分析

Claude 3.5 新功能 支持对 100 页的PDF 图像、图表和图形进行可视化分析

Claude 3.5 Sonnet发布PDF图像预览新功能&#xff0c;允许用户分析长度不超过100页的PDF中的视觉内容。 此功能使用户能够轻松上传文档并提取信息&#xff0c;特别适用于包含图表、图形和其他视觉元素的研究论文和技术文档。 视觉PDF分析&#xff1a;用户现在可以从包含各种视觉…
阅读更多...
交换排序（冒泡/快排）

交换排序（冒泡/快排）

一 . 交换排序 交换排序基本思想 : 所谓交换 &#xff0c; 就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置 。 交换序列的特点是 &#xff1a; 将键值较大的记录向序列的尾部移动 &#xff0c; 键值较小的记录向序列的前部移动 1.1 冒泡排序 在前面中 …
阅读更多...
【反射率】-- Lab 转换(excel)

【反射率】-- Lab 转换(excel)

系列文章目录 文章目录 系列文章目录前言一、CIE1.CIE 简介2.cie 1931标准色度匹配函数数据3.从CIE1931RGB到CIE1931 XYZ 二、Lab颜色空间的理解1.Lab色差公式怎么计算色差 三、D65光源Lab计算总结 前言 一、CIE 1.CIE 简介 CIE是由国际照明工程领域中光源制造、照明设计和光…
阅读更多...
[ 问题解决篇 ] win11中本地组策略编辑器gpedit.msc打不开(gpedit.msc缺失)

[ 问题解决篇 ] win11中本地组策略编辑器gpedit.msc打不开(gpedit.msc缺失)

&#x1f36c; 博主介绍 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 _PowerShell &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【数据通信】 【通讯安全】 【web安全】【面试分析】 &#x1f389;点赞➕评论➕收藏 养成习…
阅读更多...
c语言素数优化，图解

c语言素数优化，图解

方法① 2~m-1范围 整体思路就是&#xff0c;整数取余0就break&#xff0c;后续判断取余不为0的i次数&#xff0c;如果到头也就是i值溢出m-1 也就是最后一次循环i都没break&#xff0c;说明全部取余都不为0&#xff0c;贼为素数 尽头 i<m-1 等于号和-1可以抵消&#xff0c; …
阅读更多...
跨境电商行业中的主数据有哪些？

跨境电商行业中的主数据有哪些？

在全球化和数字化的推动下&#xff0c;跨境电商行业正迎来前所未有的发展机遇。无论是品牌拓展国际市场还是小型卖家进入全球电商平台&#xff0c;跨境电商企业都需要面对海量数据的管理与整合。在这个行业中&#xff0c;主数据管理尤为重要&#xff0c;因为跨境电商涉及到复杂…
阅读更多...
opencv - py_imgproc - py_grabcut GrabCut 算法提取前景

opencv - py_imgproc - py_grabcut GrabCut 算法提取前景

文章目录 使用 GrabCut 算法进行交互式前景提取目标理论演示 使用 GrabCut 算法进行交互式前景提取 目标 在本章中 我们将了解 GrabCut 算法如何提取图像中的前景我们将为此创建一个交互式应用程序。 理论 GrabCut 算法由英国剑桥微软研究院的 Carsten Rother、Vladimir K…
阅读更多...
Android编译环境构建（二）（可用于物理机、虚拟机、容器化Jenkins环境）

Android编译环境构建（二）（可用于物理机、虚拟机、容器化Jenkins环境）

文章目录 需求环境要求文件下载Gradle Version:7.5cmdline-tools至此普通物理环境的Android编译环境已部署完毕 部署maven(可选)Jenkins配置Android构建环境 说明&#xff1a; 物理环境&#xff1a;物理机、虚拟机等 容器化环境&#xff1a;docker等 需求 Gradle Version:7.5 …
阅读更多...
Django安装

Django安装

在终端创建django项目 1.查看自己的python版本 输入对应自己本机python的版本&#xff0c;列如我的是3.11.8 先再全局安装django依赖包 2.在控制窗口输入安装命令&#xff1a; pip3.11 install django 看到Successflully 说明我们就安装成功了 python的Scripts文件用于存…
阅读更多...
【免费】跟网型逆变器小干扰稳定性分析与控制策略优化

【免费】跟网型逆变器小干扰稳定性分析与控制策略优化

目录 主要内容 模型研究 数学模型 2.小信号控制结构 3.仿真模型 结果一览 下载链接 主要内容 弱电网往往具有阻抗较大和短路比较小等特点&#xff0c;易导致系统不稳定&#xff0c;限制了功率传输能力。该仿真建立了弱电网下跟网型逆变器的小信号扰动状态空间模…
阅读更多...
aws(学习笔记第十课) 对AWS的EBS如何备份（snapshot）以及使用snapshot恢复数据，AWS实例存储

aws(学习笔记第十课) 对AWS的EBS如何备份（snapshot）以及使用snapshot恢复数据，AWS实例存储

aws(学习笔记第十课) 对AWS的EBS如何备份&#xff08;snapshot&#xff09;以及使用snapshot&#xff0c;AWS实例存储 学习内容&#xff1a; 对AWS的EBS如何备份AWS实例存储EBS和实例存储的不足 1. 对AWS的EBS如何备份&#xff08;snapshot&#xff09;以及使用snapshot恢复数…
阅读更多...
开源 AI 智能名片 2 + 1 链动模式 S2B2C 商城小程序中积分使用价值的拓展策略

开源 AI 智能名片 2 + 1 链动模式 S2B2C 商城小程序中积分使用价值的拓展策略

摘要&#xff1a;本文围绕开源 AI 智能名片 2 1 链动模式 S2B2C 商城小程序&#xff0c;深入探讨其积分使用价值的丰富策略。详细分析积分兑换礼品、会员升级、积分抵现等方式在该特定商城小程序环境下的应用特点、存在问题及对用户和商城的影响&#xff0c;旨在为商城的优化运…
阅读更多...
async函数和await表达式

async函数和await表达式

async函数 函数的返回值为promise对象 promise对象的结果由async函数执行的返回值决定 async函数的返回值 和then方法的返回值以及返回类型的判断办法一致 如果返回值是一个非promise类型的数据 返回的promise的类型为fulfilled或者resolved 如果返回的是一个promise对象 …
阅读更多...
软件测试--BUG篇

软件测试--BUG篇

博主主页: 码农派大星. 数据结构专栏:Java数据结构 数据库专栏:MySQL数据库 JavaEE专栏:JavaEE 软件测试专栏:软件测试 关注博主带你了解更多知识 目录 1. 软件测试的⽣命周期 2. BUG 1. BUG 的概念 2. 描述bug的要素 3.bug级别 4.bug的⽣命周期 5 与开发产⽣争执怎…
阅读更多...
Linux云计算 |【第五阶段】CLOUD-DAY8

Linux云计算 |【第五阶段】CLOUD-DAY8

主要内容&#xff1a; 掌握DaemonSet控制器、污点策略&#xff08;NoSchedule、Noexecute&#xff09;、Job / CronJob资源对象、掌握Service服务、服务名解析CluterIP&#xff08;服务名自动发现&#xff09;、&#xff08;Nodeport、Headless&#xff09;、Ingress控制器 一…
阅读更多...
基于java+SpringBoot+Vue的新闻推荐系统设计与实现

基于java+SpringBoot+Vue的新闻推荐系统设计与实现

项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&#xff1a; Springboot mybatis Maven mysql5.7或8.0等等组成&#x…
阅读更多...
我主编的电子技术实验手册（22）——RC并联电路

我主编的电子技术实验手册（22）——RC并联电路

本专栏是笔者主编教材&#xff08;图0所示&#xff09;的电子版&#xff0c;依托简易的元器件和仪表安排了30多个实验&#xff0c;主要面向经费不太充足的中高职院校。每个实验都安排了必不可少的【预习知识】&#xff0c;精心设计的【实验步骤】&#xff0c;全面丰富的【思考习…
阅读更多...
最新文章

Copyright @ 2022~2023