C++ 适配器模式实现 STL 的 stack 和 queue

1. 队列是一种容器适配器，专门用于在FIFO 上下文 (先进先出) 中操作，其中从容器一端插入元素，另一端提取元素。
2. queue 是作为容器适配器实现的，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. queue 底层容器可以是任意标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
   • empty：检测队列是否为空
   • size：返回队列中有效元素的个数
   • front：返回队头元素的引用
   • back：返回队尾元素的引用
   • push_back：在队列尾部入队列
   • pop_front：在队列头部出队列
4. 标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque

• std::queue 的成员函数

有了前面 STL 的基础，queue 和 stack 的函数功能我们一看便知。

2. 容器适配器

2.1 什么是适配器

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

2.2 C++中的适配器

• 在 C++ 中适配器，顾名思义，是一个中间'转换器'，它可以把一种接口'适配'为另一种接口，使得原本不兼容的类可以协同工作。
• 在 STL 中，适配器通常是对已有容器的封装与限制，通过限制接口、修改行为等方式，让一个已有的类表现出不同的'外观'或'用途'。

虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack 和 queue 只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque 作为实现

3. 手搓 stack 和 queue

在 STL 中，stack 和 queue 就是对底层容器的适配器。它们不是自己实现底层的数据结构，而是使用已有容器（如 deque、vector、list）进行封装，只暴露特定的接口。

3.1 实现 stack

我们依旧将实现的 stack 封装在命名空间 m_stack 中

基础架构

namespace m_stack {
template<typename T, typename Container = deque<T>>
class stack {
private:
    Container _con; // 这是自定义类型，该类内无需实现构造函数和析构函数
public:
    // ... 成员函数
};
}

• 模板参数：
  • T 为 stack 中存放的数据类型，Container 是我们添加模版参数，用于接收容器。默认使用 deque<T> 进行适配，构造 stack 时也可以选择其他的支持相应操作的容器进行适配。
• 成员变量：
  • Container _con：将用于适配的其他容器定义在 stack 中，通过相应的接口适配出 stack 所需的的功能
• 构造函数与析构函数：
  • 由于成员 Container _con 为自定义类型，该 stack 类默认生成的构造函数会自动调用 Container 类型的构造函数，默认生成的析构函数会自动调用 Container 类型的析构函数。因此我们的 stack 无需手动实现构造和析构函数

// 类内是 自定义类型时，构造函数和析构函数无需实现
// 编译器默认生成的 会自动调用 自定义类型的构造函数和析构函数
// stack(){}
// ~stack(){}

push 和 pop

public:
void push(const T& val) { _con.push_back(val); }
void pop() { _con.pop_back(); }

• push：栈的 push，尾插，直接调用相应容器 push_back 即可
• pop：栈的 pop，尾删，直接调用相应容器 pop_back 即可
• 调用容器的 push_back 和 pop_back使其满足后进先出的特性

数据访问

public:
// top 应该同时实现 const 和 非 const 版本 保证只读 stack 和可修改 stack 的使用
const T& top() const {
    return _con.back();
    // return _con[size-1]; //这是错误写法 不能用 [] 因为当适配器是 list 时，没有 [] 重载
}
T& top() {
    return _con.back();
}

• top：top 访问栈顶的元素，应当返回容器的最后一个元素，应当调用 _con.back() 接口
• top 函数需要实现两个版本：
  • 非 const 版本 (T& top()): 允许通过返回的引用直接修改栈顶元素（例如 stack.top() = 10;），适用于需要修改栈顶元素的场景
  • const 版本 (const T& top() const): 返回常量引用，禁止修改栈顶元素，适用于只读访问（如打印栈顶值），且可在 const 对象上调用

容量访问

public:
size_t size() const {
    return _con.size();
}
bool empty() const {
    return _con.empty();
}

• 不对成员做修改的函数应当定义为 const 成员函数
  • size：直接返回容器相应的 size() 函数的返回值，获取栈中的元素个数。
  • empty：直接返回容器相应的 empty() 函数的返回值，判断栈是否为空。

完整实现

// 适配器模式
// 没必要再从 0 实现一个栈，数据的存储可以用其他容器实现。栈由其他容器适配出来
// 可以增加一个模板参数来接受容器，然后
// 容器适配器就是 将已有的容器封装改造，设计出想要的容器
// STL 中给的默认适配容器是 deque
namespace m_stack {
template<typename T, typename Container = deque<T>>
class stack {
private:
    Container _con;
public:
    void push(const T& val) { _con.push_back(val); }
    void pop() { _con.pop_back(); }
    const T& top() const { return _con.back(); }
    T& top() { return _con.back(); }
    size_t size() const { return _con.size(); }
    bool empty() const { return _con.empty(); }
};
}

3.2 实现 queue

queue 的适配实现与 stack 的方法类似，这里就不在过多赘述。

基础架构

• 设计原理同上文的 stack

namespace m_queue {
template<typename T, typename Container = deque<T>>
class queue {
private:
    Container _con;
public:
    // ... 成员函数
};
}

push 和 pop

public:
void push(const T& val) { _con.push_back(val); }
void pop() { _con.pop_front(); }
//_con.erase(_con.begin()); // 可以调用 erase, 强制使用 vector 适配
// 但是不合适，因为 vector 头删效率更低

• push：尾插，直接调用相应容器 push_back 即可
• pop：头删，直接调用相应容器 pop_front 即可
• 调用容器的 push_back 和 pop_front使其满足先进先出的特性

数据访问

public:
const T& front() const {
    return _con.front();
    // return _con[size-1]; //这是错误写法 不能用 [] 因为适配器是 list 时，没有 [] 重载
}
T& front() {
    return _con.front();
}
const T& back() const {
    return _con.back();
}
T& back() {
    return _con.back();
}

• front 和 back 函数分别需要实现两个版本：
  • 非 const 版本: 允许通过返回的引用直接修改队头或队尾元素，适用于需要修改队头或队尾元素的场景
  • const 版本: 返回常量引用，禁止修改队头或队尾元素，适用于只读访问，且可在 const 对象上调用

容量访问

public:
size_t size() const {
    return _con.size();
}
bool empty() const {
    return _con.empty();
}

• 不对成员做修改的函数应当定义为 const 成员函数
  • size：直接返回容器相应的 size() 函数的返回值，获取队列中的元素个数。
  • empty：直接返回容器相应的 empty() 函数的返回值，判断队列是否为空。

完整实现

namespace m_queue {
template<typename T, typename Container = deque<T>>
class queue {
private:
    Container _con;
public:
    void push(const T& val) { _con.push_back(val); }
    void pop() { _con.pop_front(); }
    const T& front() const { return _con.front(); }
    T& front() { return _con.front(); }
    const T& back() const { return _con.back(); }
    T& back() { return _con.back(); }
    size_t size() const { return _con.size(); }
    bool empty() const { return _con.empty(); }
};
}

4. deque 简单剖析

简介

deque(双端队列)：是一种双开口的连续空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)。

• 与 vector 相比：头插效率更高，不需要搬移元素
• 与 list 相比：空间利用率比较高。

• 观察，deque 的接口很神奇，可以同时支持 operator[] 即随机访问（vector 的性质）和头插头删（list 的性质）尾插尾删。但他它实际上并没有撼动 vector 和 list 的地位，并不能达到替代 vector 和 list 的目的

deque 无法替代 vector 和 list

• deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的。实际 deque 类似于一个动态的二维数组，其底层结构与 vector 和 list 的对比如下图所示：

deque 内部的空间实现：

deque 相比于 vector：

1. 头部插入和删除时，不需要搬移元素，效率特别高。在扩容时，也不需要搬移大量的元素，因此头插头删时效率是比 vector 高的
2. deque 中 operator[] 实现的不够极致，取数据时，需要计算数据在哪一段空间 (buff) 中，在哪段空间 (buff) 的第几个。基于这个原因，在需要进行频繁的进行下标访问的情况下，其效率和性能不及 vector，所以无法替代 vector

deque 中 operator[] 的计算过程：

1. 先看 [] 访问的位置 是否在第一个用于头插的空间（buff）中，如果在，使用位置进行访问
2. 如果不在，将下标 i 减去第一段空间（buff）的元素个数大小 sz，得出新的下标 i
   • 再将下标 i / 空间中的数据个数——>得出是在第几个空间（buff）
   • 再将下标 i % 空间中的数据个数——>得出是在空间中的第几个位置

deque 相比于 list：

• deque 支持下标的随机访问
• deque 的CPU 缓存命中率较高，不需要频繁的去堆上申请空间
• 头尾的插入和删除效率高，为 O(1) 时间复杂度。但是中间位置插入删除需要进行挪动数据。
  • 因为不能将插入位置所在的空间进行扩容，一旦扩容，那么 operator[] 的计算就没有办法确定具体是在哪一个空间（buff），哪个空间的第几个位置了，只能从头开始依次遍历空间（buff）去寻找所在位置了。
  • 所以一旦进行扩容之后 deque 的 operator[] 的效率会变差很多，所以这里不能进行对插入位置所在空间进行扩容，针对插入和删除，只能进行挪动数据

作为容器适配器

• stack 是后进先出的特殊线性数据结构。只要具有push_back() 和 pop_back() 操作(尾插尾删) 的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以；
• queue 是先进先出的特殊线性数据结构。只要具有push_back() 和 pop_front() 操作(尾插头删) 的线性结构，都可以作为 queue 的底层容器，比如 list。

但是STL 中对 stack 和 queue 默认选择 deque 作为其底层容器，主要是因为：

1. stack 和 queue 不需要遍历 (因此 stack 和 queue 没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在 stack 中元素增长时，deque 比 vector 的效率高 (扩容时不需要搬移大量数据)；
3. queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。
4. stack 中进行了高频的尾插尾删，queue 中进行了高频的尾插头删。头插头删，尾插尾删对于 deque 来讲时间复杂度是 O(1)，所以作为 stack 和 queue 的容器适配器完美契合

STL 使用 deque 作为 stack 和 queue 的实现，结合了 deque 的优点，而完美的避开了其缺陷

deque 的迭代器

deque 的缺陷：

deque 有一个致命缺陷：不适合遍历。

• 在遍历时，deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下。

而序列式场景中，可能需要经常遍历，因此在实际中需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多。

目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构

deque 的迭代器：

双端队列 deque 底层是一段假象的连续空间，实际是分段连续的。为了维护其'整体连续'以及随机访问的假象，重任落在了 deque 的迭代器身上，因此 deque 的迭代器设计就比较复杂，如下图所示：

_Tp* _M_cur; 
_Tp* _M_first; 
_Tp* _M_last; 
_Map_pointer _M_node;

• deque 的迭代器同样也是一个模板类，其成员变量包括四个指针：
  • cur：指向当前所处的位置
  • first：指向当前所处空间的起始位置
  • end：指向当前所处空间的结束位置
  • node：指向中控指针数组的位置
  • 由于中控指针数组的物理空间是连续的，所以使用 *(node+1) 就可以找到下一个空间的指针，进而进行空间（buff）的的跳转
• 访问元素时：便可以从 begin 返回的迭代器指向的空间（buff）的 cur 位置处开始进行访问遍历，当遍历到当前空间（buff）的 last 指针位置处的时候通过node 指针使用 *(node+1) 进行跳转空间（buff），跳转空间继续执行遍历操作，再跳转进行遍历，直到跳转遍历到 end 迭代器指向的空间（buff）的 cur 指针指向的位置处结束遍历

5. 结语

适配器模式让我们意识到，编程不一定要从零开始，借力也能打出精彩。STL 中 stack 和 queue 的实现，不是另起炉灶，而是通过适配已有容器，封装出特定功能的接口。这种思路不仅提升了开发效率，更展示了面向对象设计中'组合优于继承'的智慧。

通过本文的学习，我们从 stack 和 queue 的接口设计讲起，到手搓自定义容器适配器，再深入了解了 deque 作为底层实现的优势与限制。希望你不仅学会了如何实现这两个容器，更领悟到设计模式在 STL 中的实际运用。