【C++】详解STL容器之一的deque和适配器stack,queue

简介: 【C++】详解STL容器之一的deque和适配器stack,queue

deque的概述

deque的设计参考了另外两大容器vectorlist。可参考下面两篇文章

vector容器管理的是线性空间,vector的容器是单向开口。这说明vector的容器的头部插入,头部删除的时间效率是O(N),尾部插入,尾部删除的效率是O(1)。

与之相对的deque所管理的空间也可以看作是线性空间。deque的线性空间是双向开口。这说明deque容器的头部插入,头部删除,尾部插入,尾部删除的效率是O(1)

deque管理的空间不够时,不需要像vector那样成倍的扩容。此时,管理一段线性空间的deque却能像list的那样一小段一小段的扩容,并且还能保证自己管理的依旧是一段线性空间。

既然deque管理的是一段线性的空间,那一定支持随机访问,那么在deque的容器中排序的效率怎么样呢?实际上,在deque容器中的排序效率并不理想,在一亿这个数据量级,用deque容器排序的用时是用vector容器排序用时的五倍。现在给出如下两个方案,方案一:直接用deque排序。方案二:把deque容器中的数据拷贝给vector,让vector排序,再把排好的数据拷贝给deque。方案一的效率也远远的不如方案二。

从排序的效率中可以看出,deque容器管理的线性空间是一种假象

deque空间的结构

deque会开一小段空间存数据,如果空间不够,会再开一小段相等大小的空间,这一小段空间称为缓冲区这些缓冲区的才是deque容器存数据的空间而这些一小段一小段的空间的指针会按一定顺序存入一段名为map的连续的空间,map就是管理所有缓冲区的中控器,如下图

如下是源码定义

template <class T, class Alloc = alloc, size_t BufSize = 0>
class deque
{
public:
typedef T value_type;
typedef value_type* pointer;
 
//......
protected:
typedef pointer* map_pointer;  //指向数据的指针
 
protected:
map_pointer map; //储存指针空间的map,本质是个二级指针,map指向的连续的空间
 
size_t map_size; //map可容纳指针的个数
}

deque的迭代器

要让如此复杂的空间关系在上层表现的像线性空间一样,需要设计一个很复杂的迭代器。源码的迭代器封装了四个指针。

T* cur; 用来遍历缓冲区,也可以用来数据的存取

T* first; 指向缓冲区的头

T* last; 指向缓冲区的尾

map_pointer node; 指向中控器的指针,被指向的指针又指向该缓冲区

用如此复杂的迭代器想要随机访问数据是要付出代价的,因为缓冲区在内存中是不连续的,想要从一个缓冲区去下一个缓冲区,必须通过迭代器的node指针在中控器的空间上偏移实现。这便是用deque容器排序效率不高的原因。

deque的数据设计

iterator start; 用一个迭代器指向第一个缓冲区

iterator finish; 用一个迭代器指向最后一个缓冲区

map_pointer map; 指向中控器,方便管理中控器

size_type map_size; 中控器中有多少指针


deque的优缺点

总结一下deque容器的优缺点

deque优点:

与vector比较,头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不 需要搬移大量的元素,头插头删,尾插尾删的效率很高

与list比较,其底层是连续空间,空间利用率比list较高,不需要存储额外字段。缓存命中率比list高

deque缺点:

与vector比较deque不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到

某段小空间的边界,导致效率低下,因此用deque容器排序的效率也是低下的

与list比较:deque不适合在中间插入数据,因为需要挪动数据。而list只需改变指向关系即可。

vector和list都有很明显的优点和很明显的缺点,deque就好像夹在vector和list中间的容器,找不到很亮眼的优点。

适配器的概念

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

虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配

器,这是因为stack和queue只是对其他容器的接口进行了包装,STL中stack和queue默认使用deque,比如:

STL在实现stack, queue时,并没有再去设计一个容器,而是直接复用其他容器,这便是适配器。这是一种设计思想


stack的概述

stack别名为,栈是一种先进后出的数据结构。栈只有一个开口,只能从这个开口入数据和出数据。

栈没有迭代器,这说明栈是不允许遍历的

栈的底层可以适配vector容器,list容器,deque容器,默认适配deque容器

stack的模拟实现

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

queue的概述

dueue别名为队列,队列是一种先进先出的数据结构。队列只能队尾如数据,队头出数据。

队列没有迭代器,这说明队列是不允许遍历的

队列的底层可以适配list容器,deque容器,默认适配deque容器


queue的模拟实现

#include<vector>
#include<list>
#include<deque>
 
namespace bit
{
  // 
  template<class T, class Container = deque<T>>
  class queue
  {
  public:
    void push(const T& x)
    {
      _con.push_back(x);
    }
 
    void pop()
    {
      _con.pop_front();
      //_con.erase(_con.begin());
    }
 
    T& front()
    {
      return _con.front();
    }
 
    T& back()
    {
      return _con.back();
    }
 
    size_t size()
    {
      return _con.size();
    }
 
    bool empty()
    {
      return _con.empty();
    }
  private:
    Container _con;
  };
相关文章
|
8月前
|
存储 缓存 C++
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
C++ 标准模板库(STL)提供了一组功能强大的容器类,用于存储和操作数据集合。不同的容器具有独特的特性和应用场景,因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说,了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器,包括序列容器(`std::vector`、`std::array`、`std::list`、`std::deque`)、关联容器(`std::set`、`std::map`)和无序容器(`std::unordered_set`、`std::unordered_map`),全面解析它们的特点、用法
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
8月前
|
设计模式 C++ 容器
c++中的Stack与Queue
c++中的Stack与Queue
|
9月前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
188 21
|
12月前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
147 1
|
12月前
|
设计模式 存储 C++
C++之stack 和 queue(下)
C++之stack 和 queue(下)
137 1
|
11月前
|
存储 设计模式 C++
【C++】优先级队列(容器适配器)
本文介绍了C++ STL中的线性容器及其适配器,包括栈、队列和优先队列的设计与实现。详细解析了`deque`的特点和存储结构,以及如何利用`deque`实现栈、队列和优先队列。通过自定义命名空间和类模板,展示了如何模拟实现这些容器适配器,重点讲解了优先队列的内部机制,如堆的构建与维护方法。
152 0
|
3月前
|
存储 监控 测试技术
如何将现有的应用程序迁移到Docker容器中?
如何将现有的应用程序迁移到Docker容器中?
279 57
|
3月前
|
存储 监控 Java
如何对迁移到Docker容器中的应用进行性能优化?
如何对迁移到Docker容器中的应用进行性能优化?
258 59
|
3月前
|
NoSQL Redis Docker
使用Docker Compose工具进行容器编排的教程
以上就是使用Docker Compose进行容器编排的基础操作。这能帮你更有效地在本地或者在服务器上部署和管理多容器应用。
336 11
|
3月前
|
缓存 Java Docker
如何对应用代码进行优化以提高在Docker容器中的性能?
如何对应用代码进行优化以提高在Docker容器中的性能?
220 1