C++(STL容器适配器)

前言:

适配器也称配接器(adapters)在STL组件的灵活组合运用功能上,扮演着轴承、转换器的角色。

《Design Patterns》对adapter的定义如下:将一个class的接口转换为另一个class的接口,使原本因接口不兼容而不能合作的classes可以一起运作。


目录

1 配接器概观与分类

​编辑 2 stack(栈)

2.1常用接口介绍 

2.2模拟实现

 3.queue(队列)

 3.1接口函数

3.2模拟实现

​编辑 4.小结

​编辑 5 deque(双端队列)



1 配接器概观与分类

stl所提供的各种配接器中,改变仿函数(functors)接口的,我们称作 function adapter,改变容器(containers)接口的,我们称为 container adapter,改变迭代器(iterators)接口的,我们称为 iterator adapter。 所以大致可以分为三类:

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

其中,容器适配器 可修改底层为指定容器,STL提供的两个容器 stack和queue 其实都只不过是一种适配器可以由 vector 构成的栈、由 list 构成的队列,最好由 deque修饰(文末会介绍);迭代器适配器可以 实现其他容器的反向迭代器(后续介绍);最后的仿函数适配器是所有适配器中数量最庞大的,适配灵活度远远高于前两者。,可以 无限制的创造出各种可能的表达式。 

 2 stack(栈)

既然 栈可由适配器构成。我们就从栈开始 ,栈 stack 是一种特殊的数据结构,主要特点为 先进后出 FILO,主要操作有:入栈、出栈、查看栈顶元素、判断栈空等;栈在原则上是不允许进行中部或头部操作的,这样会破坏栈结构的完整性,就不叫栈了

 

 

从库中我们可以发现,实现栈的模板参数有两个 不带缺省值的是元素类型,同时也是适配器所需的元素类型,第二个就是适配器由deque实现。代码实现如下:

#include <iostream>
#include <stack>
#include <vector>
#include <list>using namespace std;int main()
{stack<int> s;	//库里默认底层容器为 dequestack<int, vector<int>> sv;	//显示实例化底层容器为 vectorstack<char, list<char>> sl;	//显示实例化底层容器为 listcout << typeid(s).name() << endl;	//查看具体类型cout << typeid(sv).name() << endl;cout << typeid(sl).name() << endl;return 0;
}

 

alloc是空间适配器 是库里专用的 他会层层 typedef 这里我们不多介绍后续专门介绍。 

2.1常用接口介绍 

 库里的接口都比较简单,知道接口函数,调用即可。

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

2.2模拟实现

我们选择使用vector作为适配器模拟实现 ,代码如下:

#pragma once
#include <vector>using namespace std;namespace cmx
{//这里选择模板参数2 底层容器 的缺省值为 vectortemplate<class T, class Container = vector<int>>class stack{public://需要提供一个带缺省参数的构造函数,因为默认构造函数不接受传参stack(const Container& con = Container()):_con(con){}//不需要显式的去写析构函数,默认生成的够用了//同理拷贝构造、赋值重载也不需要bool empty() const{return _con.empty();}size_t size() const{return _con.size();}//top 需要提供两种版本T& top(){return _con.back();}const T& top() const{return _con.back();}//选取的底层容器必须支持尾部操作void push(const T& val){_con.push_back(val);}void pop(){//空栈不能弹出,可在底层容器中检查出来_con.pop_back();}private:Container _con;	//成员变量为具体的底层容器};
}

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

 

 3.queue(队列)

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

 

 

和栈一样,队列也有两个模板参数:

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

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

#include <iostream>
#include<queue>
#include <vector>
#include <list>using namespace std;int main()
{queue<int> qDeque;	//默认使用 dequequeue<double, vector<double>> qVector;	//指定使用 vectorqueue<char, list<char>> qList;	//指定使用 listcout << typeid(qDeque).name() << endl;	//查看具体类型cout << typeid(qVector).name() << endl;cout << typeid(qList).name() << endl;return 0;
}

 3.1接口函数

常见接口的使用 代码如下:

 

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

3.2模拟实现

 库里常见的适配器是deque,我们选用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、backT& 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;	//成员变量为指定的底层容器对象};
}

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

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

 4.小结

栈和队列在实际开发中作为一种辅助结构被经常使用,比如内存空间划分中的栈区,设计规则符合栈 FILO;操作系统中的各种队列,如阻塞队列,设计规则符合 队列 FIFO。除此以外,在很多 OJ 题中,都需要借助栈和队列进行解题 

 5 deque(双端队列)

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

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

利用 list 构造出一个 map 作为主控数组(通过链式结构链接),数组中元素为数组指针
利用 vector 构造出大小为 N 的小数组(缓冲区),这些小数组才是双端队列存储元素的地方
注意: 此处的 map 并非是容器 map,仅仅是名字相同。

 

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

deque 中的随机访问:

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

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

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

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

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

 

这个迭代器还是一个随机迭代器,因此可以使用 std::sort

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

中间位置插入删除比较麻烦,可以令小数组长度不同解决问题,不过此时影响随机访问效率
结构设计复杂,且不如 vector 和 list 极致
致命缺陷:不适合遍历,迭代器需要频繁检测是否移动某段小空间的边界,效率很低
凑巧的是,栈和队列 可以完美避开所有缺陷,全面汲取其优点,因此 双端队列 为容器适配器的默认底层容器。

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Python之字符串构造

Python之字符串构造 字符串str 一个个字符组成的有序的序列&#xff0c;是字符的集合使用单引号、双引号、三引号引住的字符序列字符串是不可变对象&#xff0c;是字面常量 Python3起&#xff0c;字符串都是Unicode类型 x abcde使用for循环遍历x的值&#xff0c;打印并查看…

2023 年 Web 安全最详细学习路线指南,从入门到入职(含书籍、工具包)【建议收藏】

第一个方向&#xff1a;安全研发 你可以把网络安全理解成电商行业、教育行业等其他行业一样&#xff0c;每个行业都有自己的软件研发&#xff0c;网络安全作为一个行业也不例外&#xff0c;不同的是这个行业的研发就是开发与网络安全业务相关的软件。 既然如此&#xff0c;那其…

从零开始学习线性回归:理论、实践与PyTorch实现

文章目录 &#x1f966;介绍&#x1f966;基本知识&#x1f966;代码实现&#x1f966;完整代码&#x1f966;总结 &#x1f966;介绍 线性回归是统计学和机器学习中最简单而强大的算法之一&#xff0c;用于建模和预测连续性数值输出与输入特征之间的关系。本博客将深入探讨线性…

解决报错: require is not defined in ES module scope

用node启动mjs文件报错&#xff1a;require is not defined in ES module scope 现象如下&#xff1a; 原因&#xff1a; 文件后缀是mjs, 被识别为es模块&#xff0c;但是node默认是commonjs格式&#xff0c;不支持也不能识别es模块。 解决办法&#xff1a;把文件后缀从.mjs改…

Spring web security

儅使用spring的web security時&#xff0c;默認會轉向自帶的spring security example page。而不會轉向error page。 TODO: <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifactId> &l…

【智能家居项目】裸机版本——字体子系统 | 显示子系统

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《智能家居项目》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 今天实现上图整个项目系统中的字体子系统和显示子系统。 目录 &#x1f004;设计思路&#x1…

【网络安全-信息收集】网络安全之信息收集和信息收集工具讲解

一&#xff0c;域名信息收集 1-1 域名信息查询 可以用一些在线网站进行收集&#xff0c;比如站长之家 域名Whois查询 - 站长之家站长之家-站长工具提供whois查询工具&#xff0c;汉化版的域名whois查询工具。https://whois.chinaz.com/ 可以查看一下有没有有用的信息&#xf…

【熬夜爆肝版】JAVA基础入门专栏——1.JAVA开发入门

JAVA开发入门 1、Java概述1&#xff09;起源2&#xff09;特点3&#xff09;应用领域 2、JDK1&#xff09;定义2&#xff09;作用3&#xff09;组成4&#xff09;JDK版本与兼容性5&#xff09;JDK的安装与配置6&#xff09;JDK的发行版 3、系统环境变量1&#xff09;定义2&…

回归预测 | MATLAB实现PSO-SVR粒子群优化支持向量机回归多输入单输出预测

回归预测 | MATLAB实现PSO-SVR粒子群优化支持向量机回归多输入单输出预测 目录 回归预测 | MATLAB实现PSO-SVR粒子群优化支持向量机回归多输入单输出预测预测效果基本介绍模型描述程序设计预测效果 <

Chrome(谷歌浏览器)如何关闭搜索栏历史记录

目录 问题描述解决方法插件解决&#xff08;亲测有效&#xff09;自带设置解决步骤首先打开 地址 输入&#xff1a;chrome://flags关闭浏览器&#xff0c;重新打开Chrome 发现 已经正常 问题描述 Chrome是大家熟知的浏览器&#xff0c;但是搜索栏的历史记录如何自己一条条的删…

时序预测 | MATLAB实现EMD-iCHOA+GRU基于经验模态分解-改进黑猩猩算法优化门控循环单元的时间序列预测

时序预测 | MATLAB实现EMD-iCHOAGRU基于经验模态分解-改进黑猩猩算法优化门控循环单元的时间序列预测 目录 时序预测 | MATLAB实现EMD-iCHOAGRU基于经验模态分解-改进黑猩猩算法优化门控循环单元的时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 EMD-iCHOAGR…

LVGL_基础控件滚轮roller

LVGL_基础控件滚轮roller 1、创建滚轮roller控件 /* 创建一个 lv_roller 部件(对象) */ lv_obj_t * roller lv_roller_create(lv_scr_act()); // 创建一个 lv_roller 部件(对象),他的父对象是活动屏幕对象// 将部件(对象)添加到组&#xff0c;如果设置了默认组&#xff0c…

MFC文本输出学习

void CTxttstView::OnDraw(CDC* pDC) {CTxttstDoc* pDoc GetDocument();ASSERT_VALID(pDoc);// TODO: add draw code for native data hereCString str1;pDC->SetBkColor(RGB(0,0,0));pDC->TextOut(50, 50, "一段文字");pDC->SetBkColor(RGB(255,255,255))…

Linux Vi编辑器基础操作指南

Linux Vi编辑器基础操作指南 Linux中的Vi是一个强大的文本编辑器&#xff0c;虽然它有一些陡峭的学习曲线&#xff0c;但一旦掌握了基本操作&#xff0c;它就变得非常高效。以下是Vi编辑器的一些基本用法&#xff1a; 打开Vi编辑器&#xff1a; vi 文件名退出Vi编辑器&#xff…

kafka初体验基础认知部署

kafka 基础介绍 Apache Kafka是一个分布式流处理平台&#xff0c;最初由LinkedIn开发并于2011年开源。它主要用于解决大规模数据的实时流式处理和数据管道问题。 Kafka是一个分布式的发布-订阅消息系统&#xff0c;可以快速地处理高吞吐量的数据流&#xff0c;并将数据实时地分…

【状态估计】将变压器和LSTM与卡尔曼滤波器结合到EM算法中进行状态估计(Python代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

数据挖掘(3)特征化

从数据分析角度&#xff0c;DM分为两类&#xff0c;描述式数据挖掘&#xff0c;预测式数据挖掘。描述式数据挖掘是以简介概要的方式描述数据&#xff0c;并提供数据的一般性质。预测式数据挖掘分析数据建立模型并试图预测新数据集的行为。 DM的分类&#xff1a; 描述式DM&#…

剑指offer——JZ26 树的子结构 解题思路与具体代码【C++】

一、题目描述与要求 树的子结构_牛客题霸_牛客网 (nowcoder.com) 题目描述 输入两棵二叉树A&#xff0c;B&#xff0c;判断B是不是A的子结构。&#xff08;我们约定空树不是任意一个树的子结构&#xff09; 假如给定A为{8,8,7,9,2,#,#,#,#,4,7}&#xff0c;B为{8,9,2}&…

第一章 visual studio下载安装

一、官网下载 地址&#xff1a;https://visualstudio.microsoft.com/zh-hans/ 点击免费visual studio 二、安装 运行下载好的exe文件&#xff0c;自定义安装目录 三、选择需要的组件安装 只需要选择标记组件&#xff0c;然后点击安装 等待安装完成就行 四、重启电脑 安装完之后…