✨个人主页: 北 海
?所属专栏: C++修行之路
?每篇一句: 图片来源
文章目录
?前言?️正文1、适配器模式2、栈 stack2.1、常用接口学习2.2、模拟实现 3、队列 queue3.1、常用接口学习3.2、模拟实现 4、小结5、双端队列 deque(了解) ?总结
?前言
适配器(配接器)是 STL
中的六大组件之一,扮演着轴承、转换器的角色,使得 STL
中组件的使用更为灵活,比如 栈和队列
就是属于适配器而非容器,以及神秘的反向迭代器也属于适配器
具有多种功能的电源适配器,可以满足多种需求
?️正文
1、适配器模式
从应用角度出发,STL
中的适配器可以分为三类:
container adapters
迭代器适配器 iterator adapters
仿函数适配器 functor adapters
其中,容器适配器 可修改底层为指定容器,如由 vector
构成的栈、由 list
构成的队列;迭代器适配器可以 实现其他容器的反向迭代器(后续介绍);最后的仿函数适配器就厉害了,几乎可以 无限制的创造出各种可能的表达式
本文介绍的是容器适配器,即 栈
和 队列
,最后还会介绍一下常作为这两种容器适配器的默认底层容器 双端队列
出自 《STL源码剖析》
2、栈 stack
栈 stack
是一种特殊的数据结构,主要特点为 先进后出 FILO
,主要操作有:入栈、出栈、查看栈顶元素、判断栈空等;栈在原则上是不允许进行中部或头部操作的,这样会破坏栈结构的完整性
栈在生活中比较少见,比较形象的例子是米缸,最先倒进去的米总是最后才能吃到,这正好契合了栈先进后出的思想
官方文档中 stack
的接口也是比较少的
可以看出,栈有两个模板参数
T
栈中的元素类型,同时也是底层容器中的元素类型参数2:Container
实现栈时用到的底层容器,这里为缺省参数,缺省结构为 双端队列 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;}
注意: 关于参数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;}
栈的常用接口就这几个,多用几次就熟悉了
2.2、模拟实现
因为是容器适配器,所以在模拟实现时,需要借助其他容器,这里选择使用 vector
#pragma once#include <vector>using namespace std;namespace Yohifo{//这里选择模板参数2 底层容器 的缺省值为 vectortemplate<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
作为默认底层容器
3、队列 queue
队列 queue
是另一种特殊的数据结构,遵循先进先出 FIFO
,主要操作:入队、出队、判断队空、查看队头尾元素等
队列是一种生活中无处不见的场景,比如食堂打饭、柜台办理业务、排队出车站等等,所谓先来后到,形容的就是队列了
作为容器适配器,queue
官方提供的接口也是一样的少
和栈一样,队列也有两个模板参数:
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、常用接口学习
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;}
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、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
题中,都需要借助栈和队列进行解题
注:二叉树的最近公共祖先可以借助栈完成时间复杂度 O(N) 的解法
注意:
栈和队列都属于特殊的数据结构,原则上是不支持遍历的,因为一旦进行遍历,其中的数据必然被弹出,因此两者都没有提供迭代器假设容器没有提供头尾操作,比如map
和 set
,那么就不能拿它们适配出 栈或队列,强行使用会报错 5、双端队列 deque(了解)
双端队列是官方指定的底层容器,其结构上的特殊设计决定了它只适合于头尾操作需求高的场景:双端队列 = vector
+ list
,设计时就想汲取二者的优点(下标随机访问 + 极致的空间使用),但鱼和熊掌不可兼得,在复杂结构的加持之下,双端队列趋于中庸,无法做到 vector
和 list
那样极致,因此实际中也很少使用,比较适合当作适配器的底层容器
双端队列的数据结构:list
+ vector
list
构造出一个 map
作为主控数组(通过链式结构链接),数组中元素为数组指针利用 vector
构造出大小为 N
的小数组(缓冲区),这些小数组才是双端队列存储元素的地方 注意: 此处的 map
并非是容器 map
,仅仅是名字相同而已
将二者结合起来,就得到了复杂的双端队列
deque
的扩容机制:只需要对中控数组 map
进行扩容,再将原 map
中的数组指针拷贝过来即可,效率比较高
deque
中的随机访问:
(下标 - 前预留位) / 单个数组长度
获取对应小数组位置(下标 - 前预留位) % 单个数组长度
获取其在小数组中的对应下标 由此可见,单个数组大小(缓冲区大小)需要定长,否则访问时计算会比较麻烦,但长度定长后,会引发中间位置插入删除效率低的问题
对此 SGI
版的 STL
选择牺牲中间位置插入,提高下标随机访问速度,令小数组定长,这也是将它作为 栈和队列
默认底层容器的原因之一,因为 栈和队列
不需要对中间进行操作
因为中控数组是链式结构,因此双端队列的迭代器设计极为复杂
cur
指向当前需要的数据位置first
指向 buffer
数组起始位置last
指向 buffer
数组终止位置node
反向指向中控数组
这个迭代器还是一个随机迭代器,因此可以使用 std::sort
deque
还是 list
,直接排序的效率都不如借助 vector
间接排序效率高 deque
的缺点
vector
和 list
极致致命缺陷:不适合遍历,迭代器需要频繁检测是否移动某段小空间的边界,效率很低 凑巧的是,栈和队列
可以完美避开所有缺陷,全面汲取其优点,因此 双端队列 为容器适配器的默认底层容器
对于这种中庸且复杂的容器,只需要做简单了解就行了
?总结
以上就是本篇关于 C++ STL学习之【容器适配器】的全部内容了,在本文中,我们首先学习了适配器默认,了解它存在的意义及种类;其次学习和模拟实现了两种容器适配器 栈和队列
;最后认识了容器适配器的默认底层容器 双端队列
,见识了其复杂的结构设计及优缺点。关于适配的下一种形态:迭代器适配器
将在下文中学习,同时 反向迭代器
的神秘面纱也将被揭开
如果你觉得本文写的还不错的话,可以留下一个小小的赞?,你的支持是我分享的最大动力!
如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正
相关文章推荐
STL 之 list 类
C++ STL学习之【list的模拟实现】
C++ STL学习之【list的使用】
===============
STL 之 vector 类
C++ STL学习之【vector的模拟实现】
C++ STL学习之【vector的使用】
===============
STL 之 string 类
C++ STL学习之【string类的模拟实现】
C++ STL 学习之【string】
![承蒙厚爱,感谢支持 感谢支持](http://zhangshiyu.com/zb_users/upload/2023/05/20230504080103168315846324671.gif)