容器适配器：Stack与Queue的底层奥秘
🔥个人主页：胡萝卜3.0
📖个人专栏： 《C语言》、《数据结构》 、《C++干货分享》、LeetCode&牛客代码强化刷题
⭐️人生格言：不试试怎么知道自己行不行
🎥胡萝卜3.0🌸的简介：
目录
一. 容器适配器的核心思想
适配器 是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口，本质是接口转换：通过封装一个底层容器（如 deque、vector、list），屏蔽藏其部分接口，仅暴露符合自身数据访问规则的方法。例如：
- Stack 需 “后进先出（LIFO）”，只需底层容器支持尾插（push_back）、尾删（pop_back）、取尾元素（back） 即可；
- Queue 需 “先进先出（FIFO）”，只需底层容器支持尾插（push_back）、头删（pop_front）、取头元素（front）、取尾元素（back） 即可。
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：
二、基于容器适配器的Stack实现
Stack 的核心是 “仅允许栈顶操作”，我们通过模板参数指定底层容器（默认使用 deque，兼顾效率与灵活性），封装其尾操作接口
2.1 代码实现
#include<iostream>
#include<vector>
#include<list>
#include<deque>
using namespace std;
namespace carrot
{
//T为元素类型，Container为底层容器类型
template<class T,class Container=deque<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
const T& top()
{
return _con.back();
}
void pop()
{
_con.pop_back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}- 模板参数灵活性：用户可指定任意支持
push_back/pop_back/back的容器作为底层（如stack<int, vector<int>> st; 或stack<int, list<int>> st;）
如果底层容器中不支持这些操作，则报错！！！
2.2 测试接口
#include"stack_queue.h"
namespace carrot
{
void testStack1()
{
//底层容器可以是vector<int> 、list<int>
//如果不传底层容器，默认是deque(双端队列)
stack<int, vector<int>> st;
//入栈
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
st.push(6);
//取栈顶元素
int top = st.top();
cout << top << endl;
//出栈
st.pop();
//栈中元素个数
size_t _size = st.size();
cout << _size << endl;
//打印栈中元素
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
}
}
int main()
{
carrot::testStack1();
return 0;
}- 输出结果：
三、适配器模式：Queue的模拟实现
Queue 的核心是 “队尾入、队头出”，同样通过模板参数指定底层容器（默认 deque），封装其尾插、头删等接口。
3.1 代码实现
#include<iostream>
#include<vector>
#include<list>
#include<deque>
using namespace std;
namespace carrot
{
//T为元素类型，Container为底层容器类型
template<class T, class Container = deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
const T& front()
{
return _con.front();
}
const T& back()
{
return _con.back();
}
void pop()
{
_con.pop_front();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}对于queue的底层容器，不使用vector容器，因为vector容器中不支持pop_front（头删）的接口，如果使用vector作为底层容器，头删只能调用erase接口，但是时间复杂度为O(n)， 所以不建议使用vector作为底层容器
3.2 接口测试
namespace carrot
{
void testQueue1()
{
//底层容器默认是deque，不建议使用vector
queue<int, list<int>> q;
//入队列
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
//取队头
int front = q.front();
cout << front << endl;
//出队头
q.pop();
front = q.front();
cout << front << endl;
//取队尾
int back = q.back();
cout << back << endl;
//有效数据个数
size_t _size = q.size();
cout << _size << endl;
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
}
}- 运行结果：
四. 双端队列 deque：结构与适配逻辑
4.1 容器特性对比：Stack与List
| 优点 | 缺点 | |
| vector | 1、支持快速下标随机访问 2、尾删尾插效率很高 3、CPU高速缓存访问命中率高，数据访问效率高 | 1、头部或者中间位置的插入和删除效率很低（O(N） 2、插入存在扩容，扩容也有一定性能的消耗，扩容也会存在空间的浪费 |
| list | 1、任意位置插入删除效率很高O(1) 2、插入不存在扩容，按需申请释放内存 | 1、不支持快速下标的随机访问 2、CPU高速缓存访问命中率低，数据访问效率低 |
大家对CPU高速缓存感兴趣的话可以看一下这篇文章：
与程序员相关的CPU缓存知识 | 酷 壳 - CoolShell
4.2 deque原理介绍
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
4.3 deque 底层结构：缓冲区与中控器的协作
deque 的底层结构可拆解为 “中控器 + 缓冲区” 两部分，二者配合实现 “伪连续” 特性，具体结构如下：
deque 通常由一个中控器（Map） 和多个固定大小的缓冲区组成。
-
中控器（Map）：
-
它是一个动态数组（例如
vector），存储的是指针。 -
每个指针指向一块固定大小的连续线性空间（即一个缓冲区）。
- 本质是一个动态数组，存储的是各个缓冲区的首地址。
-
-
缓冲区（Buffer）：
-
是实际存储数据的单元。
-
大小是固定的，例如 512 字节或 16 个元素（取决于实现和元素类型）
-
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
迭代器的 “衔接” 作用：
deque 的迭代器是实现 “伪连续” 的关键，它内部包含四个核心成员：
- cur：指向当前缓冲区中正在访问的元素。
- first：指向当前缓冲区的起始位置。
- last：指向当前缓冲区的末尾位置（不含有效元素）。
- node：指向中控器中当前缓冲区地址所在的节点。
当迭代器从一个缓冲区的末尾（cur == last）移动到下一个元素时，会通过 node 找到下一个缓冲区的地址，再将 cur 指向新缓冲区的 first，从而实现 “跨缓冲区连续访问” 的效果。
底层的一些源码和满了之后头插尾插的逻辑：
4.4 deque 的优缺点：适用场景与局限性
| 类别 | 优点 | 缺点 |
| 头尾操作 | 头尾插入、删除效率都不错 | |
| 数据访问 | CPU高速缓存命中也不错，数据访问效率高 | 随机访问支持，但是相对vector不够极致，大量[ ] 访问，还得是vector |
| 中间操作 | 中间插入、删除效率低，时间复杂度为O(n) |
适用场景：
- 适合只需头尾操作、无需频繁遍历的场景，因此成为 stack（仅尾操作）、queue（头尾操作）的默认底层容器，能 “扬长避短”。
deque的使用：
#include<iostream>
#include<deque>
using namespace std;
void testdeque1()
{
deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_back(3);
dq.push_back(4);
dq.push_back(5);
for (auto& e : dq)
{
cout << e << " ";
}
cout << endl;
for (auto& e : dq)
{
e += 10;
cout << e << " ";
}
}
deque的使用和string、vector、list的使用没有任何区别。
和vector的sort效率对比：
#include<iostream>
#include<deque>
#include<vector>
#include<time.h>
#include<algorithm>
using namespace std;
void test_op1()
{
srand(time(0));
const int N = 1000000;
deque<int> dq;
vector<int> v;
for (int i = 0; i < N; ++i)
{
auto e = rand() + i;
v.push_back(e);
dq.push_back(e);
}
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
int begin2 = clock();
sort(dq.begin(), dq.end());
int end2 = clock();
printf("vector:%d\n", end1 - begin1);
printf("deque:%d\n", end2 - begin2);
}
//
void test_op2()
{
srand(time(0));
const int N = 1000000;
deque<int> dq1;
deque<int> dq2;
for (int i = 0; i < N; ++i)
{
auto e = rand() + i;
dq1.push_back(e);
dq2.push_back(e);
}
int begin1 = clock();
sort(dq1.begin(), dq1.end());
int end1 = clock();
int begin2 = clock();
// 拷贝到vector
vector<int> v(dq2.begin(), dq2.end());
sort(v.begin(), v.end());
dq2.assign(v.begin(), v.end());
int end2 = clock();
printf("deque sort:%d\n", end1 - begin1);
printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
}
int main()
{
test_op1();
test_op2();
return 0;
}
结尾
本文主要介绍了容器适配器通过封装底层容器实现特定接口转换，如stack（后进先出）和queue（先进先出）。它们基于模板参数指定底层容器（默认使用deque），仅暴露符合自身规则的操作方法。理解适配器模式，能帮助我们更深入地掌握 C++ 标准库的设计哲学，在实际开发中写出更优雅、高效的代码。
更多推荐
56
0- 0
已为社区贡献3条内容
所有评论(0)