网站导航
> 技术文档 > 【C++】容器适配器 + stack/queue/deque详解_c++ queue和deque优缺点

【C++】容器适配器 + stack/queue/deque详解_c++ queue和deque优缺点

网友: 技术文档 2025-09-02 18:39:43

文章目录

  • 上文链接
  • 一、STL 中的 stack/queue
  • 二、容器适配器
  • 三、deque
    • 1. vector 和 list 的对比
    • 2. deque 的诞生
    • 3. deque 的迭代器
    • 4. deque 的优缺点
    • 5. 为什么选择 deque 作为 stack 和 queue 的底层默认容器
  • 四、stack/queue模拟实现（完整）
  • 下文链接

上文链接

  • 【 list 简介与模拟实现（详解）】

一、STL 中的 stack/queue

【C++】容器适配器 + stack/queue/deque详解_c++ queue和deque优缺点

STL 中的 stack (栈) 与 vector、list 这些容器不太一样，它不是一种容器而是一种容器适配器。像 vector、list 这样的容器的底层是自己来管理自己的结构与数据，而栈并不是自己去管理自己的结构与数据，而是由其他的容器进行适配的。观察上图可以发现它的模板参数第二个值是一个容器，这也就意味着它是由另外的容器 (deque) 适配出来的。

同样的，queue (队列) 也是如此。

【C++】容器适配器 + stack/queue/deque详解_c++ queue和deque优缺点

二、容器适配器

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

我们在用电脑的时候可能会用到电源适配器，它可以将日常使用的 220V 的电压转换成为电脑需要的电压大小。而适配的本质其实就是一种转换。

比如，现在我想自己实现一个 stack，那么我们可以利用库中的 vector，用 vector 中的接口将其转换成为我们希望的 stack 的接口。

#includenamespace mine{template<class T>class stack{public:void push(const T& x) { _con.push_back(x); }void pop() { _con.pop_back(); }T& top() { return _con.back(); }const T& top() const { return _con.back(); }bool empty() const { return _con.empty(); }private:std::vector<T> _con; // 用 vector 的接口实现 stack};}

当然，我们不止可以用 vector 实现一个顺序结构的栈，我们也可以实现一个链式结构的栈，比如我们可以用 list 来实现。

#includenamespace mine{template<class T>class stack{public:// ...private:std::list<T> _con; // 用 list 的接口实现 stack};}

可以看到我们有很多容器都可以转换成为一个栈，于是我们就可以将这个容器写在模板中作为一个参数 Container，与 STL 库中一致。

namespace mine{template<class T, class Container>class stack{public:void push(const T& x) { _con.push_back(x); }void pop() { _con.pop_back(); }T& top() { return _con.back(); }const T& top() const { return _con.back(); }bool empty() const { return _con.empty(); }private:Container _con;};}

我们在使用时，只需要指定你想要利用的容器即可。

mine::stack<int, vector<int>> st;mine::stack<int, list<int>> st;

上面的例子很好地展示了适配器这种模式的应用，queue 的模拟实现也是同理。但是注意 queue 最好不要用 vector 去实现。这是因为 queue 的出队操作是从队头出队，对应到 vector 中就是头删操作，而 vector 不像 list，它没有直接的 pop_front 接口，想要强行实现头删操作只能用 erase 函数，而 erase 函数进行头删是一个 O ( n ) O(n) O(n) 的接口，效率很低，最好不要用。

我们还发现，STL 库中 stack 和 queue 的 Container 模板参数设置了一个默认参数 deque，熟悉数据结构的同学应该知道这是一种双端队列。当我们定义一个栈时不指定特定的容器时，就用这个 deque 去适配这个栈，如果显式地传入了一个容器时，那么就用传入的容器去适配。

三、deque

deque 名叫双端队列，虽然名叫队列，但是其实和队列没有什么太大的关系。它支持下边随机访问，支持 O ( 1 ) O(1) O(1) 时间内的头插头删和尾插尾删操作，可以认为它是一个综合了 vector 和 list 优点的一种新容器。

【C++】容器适配器 + stack/queue/deque详解_c++ queue和deque优缺点

1. vector 和 list 的对比

优点 缺点 vector 1. 支持下标随机访问 1. 头部或中部插入删除效率低下，因为要挪动数据 2. CPU高速缓存命中率高 2. 扩容有一定成本，且存在一定的浪费 list 1. 任意位置可以 O ( 1 ) O(1) O(1) 时间插入删除，不需要挪动数据 1. 不支持下标的随机访问 2. 不存在扩容，按需申请释放，不浪费空间 2. CPU高速缓存命中率低

关于什么是高速缓存命中率，这里做个简单的讲解。

当 CPU 想要访问一个数据时，要看这个数据是否在缓存区域，在就叫缓存命中，不在就是不命中。如果数据不在缓存，那么就要先将数据从内存中加载到缓存，然后再访问缓存。而加载的过程需要读取数据，往往都是一段一段地读取，像 vector 这样的连续的空间，容易成片地被读取到然后加载到缓存中，因此缓存命中率较高；而像 list 这样的链式结构，物理空间上不连续，大概率只能一个数据一个数据地被读取到缓存中，因此缓存命中率相对较低。

2. deque 的诞生

可以看到 vector 和 list 的优缺点都是互补的，vector 有的 list 没有，而 list 有的 vector 没有。因此将二者折中一下就诞生了 deque 这样的容器。

deque 既不是 vector 这样的完全连续的空间，也不是 list 这样完全单个单个的空间，而是用一个一个的小数组 (buffer) 来存储数据。一个 buffer 数组存储满了之后又再开一个新的 buffer 数组来存储数据，buffer 数组本身不会去扩容。这一个一个的 buffer 数组则由一个中控数组来管理的。中控数组本质是一个指针数组，数组的内部存储的是每一个 buffer 数组的地址 (指针)，扩容时只需要扩这个中控数组即可。

【C++】容器适配器 + stack/queue/deque详解_c++ queue和deque优缺点

由于扩容只需要扩这个中控数组，而它内部仅存储指针，所以扩容的成本较低。并且如果一个 buffer 数组的大小为 10，那么扩充 10 个中控数组的空间就等同于扩充了 10 个 buffer 数组，即 100 个空间。

3. deque 的迭代器

deque 的迭代器设计要比我们之前学习的 list 的迭代器复杂得多，list 的迭代器内部只封装了一个指针，而 deque 的迭代器内部封装了 4 个指针，分别是 cur、first、last、node。

【C++】容器适配器 + stack/queue/deque详解_c++ queue和deque优缺点

  • cur：指向当前要访问的位置。
  • first：指向对应 buffer 数组的开始位置。
  • last：指向对应 buffer 数组的结束位置。
  • node：一个二级指针，指向中控数组中当前访问的 buffer 数组的地址。

下面是 deque 的底层结构示意图：

【C++】容器适配器 + stack/queue/deque详解_c++ queue和deque优缺点

4. deque 的优缺点

优点 缺点 1. 头尾插入删除效率很高 1. 中间位置插入删除效率一般 2. 下标随机访问效率也不错，但是相比 vector 还差些 2. 对比 vector 和 list，没有那么极致 3. 底层是连续的空间，空间利用率比较高 3. 不适合遍历

为什么说 deque 不适合遍历呢？因为在遍历时，deque 的迭代器要频繁的去检测其是否移动到 buffer 数组的边界，导致效率低下。而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 或 list，deque 的应用并不多，而目前能看到的一个应用就是，STL 中用其作为 stack 和 queue 的底层数据结构。

5. 为什么选择 deque 作为 stack 和 queue 的底层默认容器

根据 stack 和 queue 的性质我们知道，stack 的底层容器可以选择 vector 或者 list，queue 的底层容器可以选择 list，那么为什么 STL 中要选择 deque 作为其底层容器呢？主要有以下两点：

  1. stack 和 queue 不需要遍历 (因此 stack 和 queue 没有迭代器)，只需要在固定的一端或者两端进行操作。

  2. 在 stack 中元素增长时，deque 比 vector 的效率高 (扩容时不需要搬移大量数据)；queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。

四、stack/queue模拟实现（完整）

#includenamespace mine{template<class T, class Container = std::deque<T>>// template<class T, class Container = std::vector>// template<class T, class Container = std::list>class stack{public:stack() {}void push(const T& x) { _con.push_back(x); }void pop() { _con.pop_back(); }T& top() { return _con.back(); }const T& top()const { return _con.back(); }size_t size()const { return _con.size(); }bool empty()const { return _con.empty(); }private:Container _con;};}
#includenamespace mine{template<class T, class Container = std::deque<T>>// template<class T, class Container = std::list>class queue{public:queue() {}void push(const T& x) { _con.push_back(x); }void pop() { _con.pop_front(); }T& back() { return _con.back(); }const T& back()const { return _con.back(); }T& front() { return _con.front(); }const T& front()const { return _con.front(); }size_t size()const { return _con.size(); }bool empty()const { return _con.empty(); }private:Container _con;};}

下文链接

  • 【C++】优先队列简介与模拟实现 + 仿函数
网络标签：

相关问题