【C++_STL】优先级队列&反向迭代器详解

这篇具有很好参考价值的文章主要介绍了【C++_STL】优先级队列&反向迭代器详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一,栈_刷题必备

二,stack实现

1.什么是容器适配器

2.STL标准库中stack和queue的底层结构 

了解补充:容器——deque 

1. deque的缺陷

2. 为什么选择deque作为stack和queue的底层默认容器

三,queue实现

1. 普通queue 

2,优先级队列(有难度)

<1>. 功能

<2>. 模拟实现

1). 利用迭代器_构造

2).仿函数

sort函数中的仿函数使用理解

结语


【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言

一,栈_刷题必备

常见接口: 

stack()     造空的栈
empty()    检测 stack 是否为空
size()        返回 stack 中元素的个数
top()         返回栈顶元素的引用
push()      将元素 val 压入 stack
pop()        stack 中尾部的元素弹出

 简单应用,刷点题:

155. 最小栈

栈的压入、弹出序列_牛客题霸_牛客网

150. 逆波兰表达式求值

二,stack实现

思路:在C语言期间,我们可以通过链表,数组形式实现过stack,而数组形式效率更高,所以stack的实现可以直接复用vector接口,包装成栈先进后出的特性

#pragma once
#include <iostream>
#include <vector>
#include <list>
using namespace std;
namespace my_s_qu
{
	template <class T >
	class stack
	{
	public:
		void push_back(const T& x)
		{
			Data.push_back(x);
		}

		void Pop()
		{
			Data.pop_back();
		}

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

		const T& top() const 
		{
			return Data.back();
		}

		bool empty() const
		{
			return Data.empty();
		}

		size_t size() const
		{
			return Data.size();
		}

	private:
		vector<T> Data;
	};
}

很简单不是吗? 到这里并没有结束,我们发现,我们的栈只能通过vector实现。根据c++标准库,我们还差个适配器的实现,换句话说,我们实现的栈不支持容器适配器。 

【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言

1.什么是容器适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结), 该种模式是将一个类的接口转换成客户希望的另外一个接口

【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言

2.STL标准库中stack和queue的底层结构 

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为 容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和queue默认使用 deque
【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言

回到我们栈的实现,我们仅支持vector模式设计,优化为成容器适配器支持所有容器,都能支持栈的先进后出的特性。(在我看来这中思想更为重要)

namespace my_s_qu
{
	template <class T, class container = deque<T> >  // 添加容器模板
	{
	public:
		void push_back(const T& x)
		{
			Data.push_back(x);
		}

......
private:
		container Data;  // 容器换成模板
	};
}

其中deque又是什么?

了解补充:容器——deque 

deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。
【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言
deque 并不是 真正 连续的空间 ,而是由 一段段连续的小空间拼接而成的 ,实际 deque 类似于一个动态的 二维数组,其底层结构如下图所示: 【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言
双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了deque的迭代器身上,因此deque的迭代器设计就比较复杂,如下图所示:

 【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言

那deque是如何借助其迭代器维护其假想连续的结构呢? 

 【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言

1. deque的缺陷

优势: 

与vector比较,deque的 优势是: 头部插入和删除效率高。  不需要搬移元素,效率特别高,而且在 扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。
与list比较优势支持随机访问。其底层是连续空间, 空间利用率比较高,不需要存储额外字段。

缺陷:  

不适合遍历。
因为在遍历时,deque的迭代器要 频繁的去 计算每个数据的位置,导致 效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list, deque的应用并不多,而目前能看到的一个应用就是, STL用其作为stack和queue的底层数据结构

2. 为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以;queue是先进先出的特殊线性数据结构, 只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list。但是STL中对sack和queue默认选择deque作为其底层容器,主要是因为:
1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。
结合了deque的优点,而完美的避开了其缺陷。

三,queue实现

1. 普通queue 

 queue实现,我们这次以容器适配器进行。

template <class T, class container = deque<T>>
	class queue
	{
	public:
		void push_back(const T& x)
		{
			Data.push_back(x);
		}


		void Pop()
		{
			Data.pop_front();
		}

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

		const T& back()  const
		{
			return Data.back();
		}

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

		const T& front() const
		{
			return Data.front();
		}

		bool empty() const
		{
			return Data.empty();
		}

		size_t size() const
		{
			return Data.size();
		}

	private:
		container Data;
	};

2,优先级队列(有难度)

【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言

简介:

1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
2. 优先级队列底层类似于堆,在堆中可以随时插入元素,并且只能检索 最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出(Pop),其称为优先队列的顶部。
5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector
6. 需要 支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

<1>. 功能

priority_queue()/priority_queue(fifirst, last)      构造一个空的优先级队列
empty( )                                                                 检测优先级队列是否为空,是返回true,否则返回false
top( )                                                                      返回优先级队列中最大(最小元素),即堆顶元素
push(x)                                                                  在优先级队列中插入元素x
pop()                                                                      删除优先级队列中最大(最小)元素,即堆顶元素
pop_back()                                                            删除容器尾部元素

<2>. 模拟实现

完成优先级队列,需要用到堆方面的知识,如果堆大家不太熟悉了,建议将堆实现内容复习一遍:

详解树与二叉树的概念,结构,及实现(上篇)_花果山~~程序猿的博客-CSDN博客

 利用堆方面知识,完成最基础的框架:

namespace my_priority_queue
{
	template <class T, class container = vector<T>> 
	class priority_queue
	{
	public:
		// 自定义类型,不需要给他初始化

		void ajust_up(size_t child)
		{
			int parent;
			while (child > 0)
			{
				parent = child / 2;
				if (_pri_queue[child] > _pri_queue[parent])  // 写大堆
				{
					std::swap(_pri_queue[child], _pri_queue[parent]);
					child = parent;
					parent = child / 2;
				}
				else
				{
					break;
				}
			}
		}

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

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

		void push(const T& x)
		{
			_pri_queue.push_back(x);
			// 向上调整
			ajust_up(_pri_queue.size() - 1);
		}

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

		void ajust_down()
		{
			size_t  parent = 0;
			size_t child = 2 * parent + 1;

			while (child < _pri_queue.size())
			{
				if (child + 1 < _pri_queue.size() && _pri_queue[child + 1] >  _pri_queue[child])
				{
					child++;
				}

				if (_pri_queue[parent] < _pri_queue[child])
				{
					std::swap(_pri_queue[parent], _pri_queue[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void pop()
		{
			std::swap(_pri_queue[0], _pri_queue[size() - 1]);
			// 向下调整
			_pri_queue.pop_back();
			ajust_down();
		}

	private:
		container _pri_queue;
	};
}

这里我们会有一个疑问,那我们要构建升序怎么办? 仿函数会解释

1). 利用迭代器_构造
// 自定义类型,不需要给他初始化
		priority_queue()
		{}

		template  <class newiterator>
		priority_queue(newiterator begin, newiterator end)
			: _pri_queue()
		{
			while (begin != end)
			{
				push(*begin);
				begin++;
			}
		}
2).仿函数

在该场景下,我们的优先级队列已经实现了降序的功能,那我们如何实现升序? 什么你说再写一段,改一下符号??

这里仿函数就得引出了,仿函数,那么它并不是函数,那是什么? (仿函数比如:less, greater)

【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言

 仿函数本质是一个类,根据上图中,compare 模板,说明这里的仿函数,就是用来灵活改变大小堆符号的。

我们直接实现结果:

    template <class T>
	struct less
	{
		bool operator()(const T& left, const T& right)const
		{
			return left < right;
		}
	};

	template <class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)const
		{
			return left > right;
		}
	};

 这个两个类都是重载了operator(),因此我们在实例化对象后,使用:

template <class T,class compare = less<T>>

compare   t;

cout <<  t(1, 2) << endl;     

从外表来看,就像一个函数调用,但实际是,一个类的成员函数的调用

t.operator(1,2) 

 这样我们就可以直接改变仿函数的类,来控制大小堆了。 

sort函数中的仿函数使用理解

函数模板中: 

【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言 sort函数作为行参中使用:

【C++_STL】优先级队列&反向迭代器详解,C++——从入门到入土,安排!,c++,数据结构,开发语言  

sort(s.begin, s.end, greater<int> () );   // 函数中是要做参数的,我们加个括号就是一个匿名对象

结语

   本小节就到这里了,感谢小伙伴的浏览,如果有什么建议,欢迎在评论区评论,如果给小伙伴带来一些收获请留下你的小赞,你的点赞和关注将会成为博主创作的动力文章来源地址https://www.toymoban.com/news/detail-696551.html

到了这里,关于【C++_STL】优先级队列&反向迭代器详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

    这篇文章我们接着上一篇的内容,再来学一个STL里的容器适配器—— priority_queue (优先级队列) 1.1 priority_queue的介绍 我们上一篇文章学了 queue (队列),那优先级队列也是在 queue 里面的: 和 queue 一样, priority_queue 也是一个容器适配器,那他和 queue 有什么区别呢?我们一

    2024年02月07日
    浏览(47)
  • C++ STL学习之【优先级队列】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎃操作环境: Visual Studio 2019 版本 16.11.17 优先级队列 priority_queue 是容器适配器中的一种,常用来进行对数据进行优先级处理,比如优先级高的值在前面,这其实就是初阶数据结构中的 堆 ,它俩本质上是一样东西,底层都是以数

    2024年02月05日
    浏览(68)
  • C++基础(三)——STL优先级队列

    模板输入 1、元素类型 2、容器类型 3、函数对象类型 priority_queueint name; priority_queue默认为大顶堆 故定义也可以写作: priority_queueint, vectorint, lessint ay; 如果需要构建一个小顶堆,可以改变定义方式为: priority_queueint, vectorint, greaterint ay; 使用std::greater模板无需自定义比较函数。

    2024年02月09日
    浏览(49)
  • 【STL】优先级队列剖析及模拟实现

    ✍ 作者 : 阿润菜菜 📖 专栏 : C++ 优先队列是一种 容器适配器 ,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的(默认大堆)。优先级队列的内部实现通常是用 堆 来维护元素的优先级,使得每次出队的元素都是当前队列中优先级最高的元素。 优先

    2023年04月22日
    浏览(43)
  • STL:双端队列&容器适配器&仿函数&优先级队列

    双端队列可以在头部和尾部进行插入删除操作 与vector相比,头插效率高,不需要搬移元素 与list相比,空间利用率高 deque逻辑上空间是连续的,物理上并不是,是由一段段小空间拼接而成的 双端队列的迭代器比较复杂 cur:指向空间中被遍历的那个元素 first:指向空间开始

    2024年02月16日
    浏览(46)
  • 『C++ - STL』之优先级队列( priority_queue )

    什么是优先级队列,从该名中可以知道他一定有队列的一定属性,即先入先出(LILO),而这里的优先级则可以判断出它的另一个特点就是可以按照一定的条件将符合该条件的先进行出队,这就是优先级队列; 而在数据结构中有一个支持该操作的结构 - 堆( heap ); 而在STL中,这个

    2024年02月07日
    浏览(44)
  • 【C++初阶10-stack&queue】STL中的栈和队列(附优先级队列

    本期分享:STL中的栈和队列。 在数据结构初阶时,我们已经学习这来那个两种数据结构,如今来看STL中的,不过是更加标准化。而实现起来,会简单得超乎你想象! 文中不足错漏之处望请斧正! STL中的栈和队列是容器适配器。容器适配器是对某种已有容器的再次封装。 比如

    2024年02月06日
    浏览(47)
  • 【C++进阶(六)】STL大法--栈和队列深度剖析&优先级队列&适配器原理

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 和C语言学习期间的学习顺序一样 顺序表,链表过了就是栈和队列 但是栈和队列非常特殊,它的内部结构 并不是靠自己实现的,而是一种 适配

    2024年02月08日
    浏览(42)
  • 【C++】STL使用仿函数控制优先级队列priority_queue

    本文章讲解C++STL的容器适配器:priority_queue的实现,并实现仿函数控制priority_queue底层。 priority_queue叫做优先级队列,它的底层结构是堆,在库中,默认生成的是大堆 在库的实现中,使用vector作为该优先级队列的适配容器。 由于priority_queue也是一个适配器,所以它的接口函数

    2024年02月16日
    浏览(47)
  • 【C++】STL优先级队列(priority_queue)功能介绍以及模拟实现

    点进来的小伙伴不知道学过数据结构里的堆没有,如果学过的话,那就好说了,优先级队列就是堆,如果没学过,没关系,可以参考一下我之前写的一篇关于堆的博客,可以点进去看看:【数据结构】堆(包含堆排序和TOPK问题) 那么了解过堆了的话,我就不讲那么细致了,

    2024年02月16日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包