C++ STL学习之【容器适配器】

这篇具有很好参考价值的文章主要介绍了C++ STL学习之【容器适配器】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

✨个人主页: 北 海
🎉所属专栏: C++修行之路
🎊每篇一句: 图片来源

  • A year from now you may wish you had started today.
    • 明年今日,你会希望此时此刻的自己已经开始行动了。

C++ STL学习之【容器适配器】



🌇前言

适配器(配接器)是 STL 中的六大组件之一,扮演着轴承、转换器的角色,使得 STL 中组件的使用更为灵活,比如 栈和队列 就是属于适配器而非容器,以及神秘的反向迭代器也属于适配器

具有多种功能的电源适配器,可以满足多种需求

C++ STL学习之【容器适配器】


🏙️正文

1、适配器模式

从应用角度出发,STL 中的适配器可以分为三类:

  • 容器适配器 container adapters
  • 迭代器适配器 iterator adapters
  • 仿函数适配器 functor adapters

其中,容器适配器 可修改底层为指定容器,如由 vector 构成的栈、由 list 构成的队列;迭代器适配器可以 实现其他容器的反向迭代器(后续介绍);最后的仿函数适配器就厉害了,几乎可以 无限制的创造出各种可能的表达式

本文介绍的是容器适配器,即 队列,最后还会介绍一下常作为这两种容器适配器的默认底层容器 双端队列

C++ STL学习之【容器适配器】
出自 《STL源码剖析》


2、栈 stack

stack 是一种特殊的数据结构,主要特点为 先进后出 FILO,主要操作有:入栈、出栈、查看栈顶元素、判断栈空等;栈在原则上是不允许进行中部或头部操作的,这样会破坏栈结构的完整性

栈在生活中比较少见,比较形象的例子是米缸,最先倒进去的米总是最后才能吃到,这正好契合了栈先进后出的思想
C++ STL学习之【容器适配器】

官方文档中 stack 的接口也是比较少的

C++ STL学习之【容器适配器】
C++ STL学习之【容器适配器】
可以看出,栈有两个模板参数

  • 参数1:T 栈中的元素类型,同时也是底层容器中的元素类型
  • 参数2:Container 实现栈时用到的底层容器,这里为缺省参数,缺省结构为 双端队列 deque

如何优雅的创建一个栈对象?

#include <iostream>
#include <stack>
#include <vector>
#include <list>

using namespace std;

int main()
{
	stack<int> s;	//默认底层容器为 deque

	stack<int, vector<int>> sv;	//显示实例化底层容器为 vector
	
	stack<char, list<char>> sl;	//显示实例化底层容器为 list

	cout << typeid(s).name() << endl;	//查看具体类型
	cout << typeid(sv).name() << endl;
	cout << typeid(sl).name() << endl;

	return 0;
}

C++ STL学习之【容器适配器】
注意:关于参数3 allocator 是空间配置器,这里先不作讲解,后续再学习

2.1、常用接口学习

学习使用接口时,直接使用默认的底层容器即可(不需要传递模板参数2)

因为接口少且非常简单,所以上手起来很方便

#include <iostream>
#include <stack>

using namespace std;

int main()
{
	stack<int> s;	//构造一个栈对象

	cout << "Original:>" << endl;
	cout << "empty(): " << s.empty() << endl;
	cout << "size(): " << s.size() << endl;

	cout << endl << "Push:>" << endl;
	s.push(1);	//入栈3个元素
	s.push(2);
	s.push(3);
	cout << "empty(): " << s.empty() << endl;
	cout << "size(): " << s.size() << endl;
	cout << "top(): " << s.top() << endl;

	cout << endl << "Pop:>" << endl;
	s.pop();	//出栈两次
	s.pop();
	cout << "empty(): " << s.empty() << endl;
	cout << "size(): " << s.size() << endl;
	cout << "top(): " << s.top() << endl;

	return 0;
}

C++ STL学习之【容器适配器】

栈的常用接口就这几个,多用几次就熟悉了

2.2、模拟实现

因为是容器适配器,所以在模拟实现时,需要借助其他容器,这里选择使用 vector

#pragma once
#include <vector>

using namespace std;

namespace Yohifo
{
	//这里选择模板参数2 底层容器 的缺省值为 vector
	template<class T, class Container = vector<int>>
	class stack
	{
	public:
		//需要提供一个带缺省参数的构造函数,因为默认构造函数不接受传参
		stack(const Container& c = Container())
			:_c(c)
		{}

		//不需要显式的去写析构函数,默认生成的够用了
		//同理拷贝构造、赋值重载也不需要

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

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

		//top 需要提供两种版本
		T& top()
		{
			return _c.back();
		}

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

		//选取的底层容器必须支持尾部操作
		void push(const T& val)
		{
			_c.push_back(val);
		}

		void pop()
		{
			//空栈不能弹出,可在底层容器中检查出来
			_c.pop_back();
		}

	private:
		Container _c;	//成员变量为具体的底层容器
	};
}

适配器的厉害之处就在于 只要底层容器有我需要的函数接口,那么我就可以为其适配出一个容器适配器,比如 vector 构成的栈、list 构成的栈、deque 构成的栈,甚至是 string 也能适配出一个栈,只要符合条件,都可以作为栈的底层容器,当然不同结构的效率不同,因此库中选用的是效率较高的 deque 作为默认底层容器

C++ STL学习之【容器适配器】


3、队列 queue

队列 queue 是另一种特殊的数据结构,遵循先进先出 FIFO,主要操作:入队、出队、判断队空、查看队头尾元素等

队列是一种生活中无处不见的场景,比如食堂打饭、柜台办理业务、排队出车站等等,所谓先来后到,形容的就是队列了
C++ STL学习之【容器适配器】

作为容器适配器,queue 官方提供的接口也是一样的少

C++ STL学习之【容器适配器】
C++ STL学习之【容器适配器】
和栈一样,队列也有两个模板参数:

  • 参数1:T 队列中的元素类型,同时也是底层容器中的元素类型
  • 参数2:Container 实现队列时用到的底层容器,这里为缺省参数,缺省结构为 双端队列 deque

双端队列的优点在于高效的头尾操作和极致的空间使用,正好符合 栈和队列 的特殊需求

创建队列对象时,我们也可以指定其底层容器

#include <iostream>
#include<queue>
#include <vector>
#include <list>

using namespace std;

int main()
{
	queue<int> qDeque;	//默认使用 deque
	queue<double, vector<double>> qVector;	//指定使用 vector
	queue<char, list<char>> qList;	//指定使用 list

	cout << typeid(qDeque).name() << endl;	//查看具体类型
	cout << typeid(qVector).name() << endl;
	cout << typeid(qList).name() << endl;
	return 0;
}

C++ STL学习之【容器适配器】

3.1、常用接口学习

queue 中的接口与 stack 差不多,不过 queue 出元素时是在队头操作,同时它支持访问队头、队尾元素,而 stack 只能访问栈顶元素

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	queue<int> q;	//构建出一个队列对象

	cout << "Original:>" << endl;
	cout << "empty(): " << q.empty() << endl;
	cout << "size(): " << q.size() << endl;

	cout << endl << "Push:>" << endl;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	cout << "empty(): " << q.empty() << endl;
	cout << "size(): " << q.size() << endl;
	cout << "front(): " << q.front() << endl;
	cout << "back(): " << q.back() << endl;

	cout << endl << "Pop:>" << endl;
	q.pop();
	q.pop();
	q.pop();
	cout << "empty(): " << q.empty() << endl;
	cout << "size(): " << q.size() << endl;
	cout << "front(): " << q.front() << endl;
	cout << "back(): " << q.back() << endl;

	return 0;
}

C++ STL学习之【容器适配器】

3.2、模拟实现

队列的模拟实现也是相当简单,这里选用 list 作为底层容器

#pragma once
#include <list>

using namespace std;

namespace Yohifo
{
	template<class T, class Container = list<T>>
	class queue
	{
	public:
		queue(const Container& c = Container())
			:_c(c)
		{}

		//这里也不需要提供拷贝构造、赋值重载、析构函数

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

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

		//选取的底层容器中,已经准备好了相关函数,如 front、back
		T& front()
		{
			return _c.front();
		}
		const T& front() const
		{
			return _c.front();
		}

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

		void push(const T& val)
		{
			_c.push_back(val);	//队列只能尾插
		}

		void pop()
		{
			_c.pop_front();	//队列只能头删
		}

	private:
		Container _c;	//成员变量为指定的底层容器对象
	};
}

队列和栈在进行适配时,都是在调用已有的接口,若是特殊接口,比如 toppushpop 等,进行相应转换即可

  • top -> back 尾元素
  • 栈、队列 push -> push_back 尾插
  • pop -> pop_back 尾删
  • 队列 pop -> pop_front 头删

C++ STL学习之【容器适配器】


4、小结

栈和队列在实际开发中作为一种辅助结构被经常使用,比如内存空间划分中的栈区,设计规则符合栈 FILO;操作系统中的各种队列,如阻塞队列,设计规则符合 队列 FIFO。除此以外,在很多 OJ 题中,都需要借助栈和队列进行解题
C++ STL学习之【容器适配器】
注:二叉树的最近公共祖先可以借助栈完成时间复杂度 O(N) 的解法

注意:

  • 栈和队列都属于特殊的数据结构,原则上是不支持遍历的,因为一旦进行遍历,其中的数据必然被弹出,因此两者都没有提供迭代器
  • 假设容器没有提供头尾操作,比如 mapset,那么就不能拿它们适配出 栈或队列,强行使用会报错

C++ STL学习之【容器适配器】


5、双端队列 deque(了解)

双端队列是官方指定的底层容器,其结构上的特殊设计决定了它只适合于头尾操作需求高的场景:双端队列 = vector + list,设计时就想汲取二者的优点(下标随机访问 + 极致的空间使用),但鱼和熊掌不可兼得,在复杂结构的加持之下,双端队列趋于中庸,无法做到 vectorlist 那样极致,因此实际中也很少使用,比较适合当作适配器的底层容器

C++ STL学习之【容器适配器】

双端队列的数据结构:list + vector

  • 利用 list 构造出一个 map 作为主控数组(通过链式结构链接),数组中元素为数组指针
  • 利用 vector 构造出大小为 N 的小数组(缓冲区),这些小数组才是双端队列存储元素的地方

注意:此处的 map 并非是容器 map,仅仅是名字相同而已

将二者结合起来,就得到了复杂的双端队列
C++ STL学习之【容器适配器】

deque 的扩容机制:只需要对中控数组 map 进行扩容,再将原 map 中的数组指针拷贝过来即可,效率比较高

deque 中的随机访问:

  1. (下标 - 前预留位) / 单个数组长度 获取对应小数组位置
  2. (下标 - 前预留位) % 单个数组长度 获取其在小数组中的对应下标

由此可见,单个数组大小(缓冲区大小)需要定长,否则访问时计算会比较麻烦,但长度定长后,会引发中间位置插入删除效率低的问题

对此 SGI 版的 STL 选择牺牲中间位置插入,提高下标随机访问速度,令小数组定长,这也是将它作为 栈和队列 默认底层容器的原因之一,因为 栈和队列 不需要对中间进行操作

因为中控数组是链式结构,因此双端队列的迭代器设计极为复杂

  • cur 指向当前需要的数据位置
  • first 指向 buffer 数组起始位置
  • last 指向 buffer 数组终止位置
  • node 反向指向中控数组

C++ STL学习之【容器适配器】
这个迭代器还是一个随机迭代器,因此可以使用 std::sort

  • 无论是 deque 还是 list,直接排序的效率都不如借助 vector 间接排序效率高

deque 的缺点

  • 中间位置插入删除比较麻烦,可以令小数组长度不同解决问题,不过此时影响随机访问效率
  • 结构设计复杂,且不如 vectorlist 极致
  • 致命缺陷:不适合遍历,迭代器需要频繁检测是否移动某段小空间的边界,效率很低

凑巧的是,栈和队列 可以完美避开所有缺陷,全面汲取其优点,因此 双端队列 为容器适配器的默认底层容器

对于这种中庸且复杂的容器,只需要做简单了解就行了


🌆总结

以上就是本篇关于 C++ STL学习之【容器适配器】的全部内容了,在本文中,我们首先学习了适配器默认,了解它存在的意义及种类;其次学习和模拟实现了两种容器适配器 栈和队列;最后认识了容器适配器的默认底层容器 双端队列,见识了其复杂的结构设计及优缺点。关于适配的下一种形态:迭代器适配器 将在下文中学习,同时 反向迭代器 的神秘面纱也将被揭开

如果你觉得本文写的还不错的话,可以留下一个小小的赞👍,你的支持是我分享的最大动力!

如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正


C++ STL学习之【容器适配器】

文章来源地址https://www.toymoban.com/news/detail-420971.html

相关文章推荐

STL 之 list 类

C++ STL学习之【list的模拟实现】

C++ STL学习之【list的使用】

===============

STL 之 vector 类

C++ STL学习之【vector的模拟实现】

C++ STL学习之【vector的使用】

===============

STL 之 string 类

C++ STL学习之【string类的模拟实现】

C++ STL 学习之【string】

C++ STL学习之【容器适配器】

到了这里,关于C++ STL学习之【容器适配器】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器)

    🌏博客主页: 主页 🔖系列专栏: C++ ❤️感谢大家点赞👍收藏⭐评论✍️ 😍期待与大家一起进步! 虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和

    2024年02月15日
    浏览(53)
  • 容器适配器---deque和STL ---stack queue priority_queue的模拟实现 C++

    目录 一、容器适配器 deque原理 deque的缺陷 deque的优势 二、stack的模拟实现  三、queue的模拟实现 四、优先级队列的模拟实现 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户

    2024年02月02日
    浏览(55)
  • 【C++】STL中的容器适配器 stack queue 和 priority_queue 的模拟实现

    适配器是一种设计模式 (设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。 例如我们常见的充电器就是一种适配器,它将我们常用的220V交流电压转化为4,5V (或者其他更高的电

    2023年04月26日
    浏览(61)
  • 【C++】STL——容器适配器priority_queue(优先级队列)详解 及 仿函数的介绍和使用

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

    2024年02月07日
    浏览(48)
  • 【STL】顺序容器与容器适配器

    给出以下顺序容器表: 顺序容器类型 作用 vector 可变大小的数组,支持快速访问,除尾元素的插入或者删除很慢 string 与vector相似,只不过专门用来存字符 list 双向链表。只能双向顺序访问,插入删除的效率都很高 forward_list 单向链表。只能单向顺序访问,插入删除的效率都

    2024年04月14日
    浏览(31)
  • [C++] STL_priority_queue(优先级队列) 的使用及底层的模拟实现,容器适配器,deque的原理介绍

    priority_queue文档介绍 翻译: 1. 优先队列是一种 容器适配器 ,根据严格的弱排序标准, 它的第一个元素总是它所包含的元素中最大的。 2. 此上下文类似于 堆 , 在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。 3. 优先队列被实现为容器适配

    2024年02月04日
    浏览(47)
  • STL: 容器适配器stack 与 queue

      目录 1.容器适配器 1.1 STL标准库中stack和queue的底层结构 1.2 deque的简单介绍(了解) 1.2.1 deque的原理介绍 1.2.2 deque的缺陷 1.2.3 为什么选择deque作为stack和queue的底层默认容器 2. stack的介绍和使用 2.1 stack的介绍  2.2 stack的使用 2.3 利用deque模拟实现stack 3.queue的介绍和使用 3.1 queue的

    2024年02月05日
    浏览(47)
  • 22 标准模板库STL之容器适配器

    概述         提到适配器,我们的第一印象是想到设计模式中的适配器模式:将一个类的接口转化为另一个类的接口,使原本不兼容而不能合作的两个类,可以一起工作。STL中的容器适配器与此类似,是一个封装了序列容器的类模板,它在一般序列容器的基础上提供了一

    2024年02月05日
    浏览(41)
  • STL:双端队列&容器适配器&仿函数&优先级队列

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

    2024年02月16日
    浏览(46)
  • 【STL】容器适配器stack和queue常见用法及模拟实现

    1.stack介绍及使用 1.1 stack的介绍 stack文档介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。 stack是作为容器适配器被实现的,容器适配器是使用特定容器类的封装对象作为其基础容器的类,提供一

    2024年02月06日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包