【C++从0到王者】第十七站:手把手教你写一个stack和queue及deque的底层原理

简介: 【C++从0到王者】第十七站:手把手教你写一个stack和queue及deque的底层原理

一、stack

1.利用适配器

我们不可能写了一份数组栈以后,还要在手写一个链式栈,这样显得太冗余了。于是我们可以利用适配器,传递一个我们想要使用的类型。这样我们的栈就可以做到数组栈和链式栈的秒切换了。从我们用的角度来说并没有太大差别,但是底层早已大变样了。

template<class T, class Container>
  class stack
  {
  public:
  private:
    Container _con;
  };

2.栈的实现

有了上面的思路,我们就可以很容易的完成栈的接口

#pragma once
#include<vector>
#include<list>
namespace Sim
{
  template<class T, class Container = vector<T>>
  class stack
  {
  public:
    void push(const T& val)
    {
      _con.push_back(val);
    }
    void pop()
    {
      _con.pop_back();
    }
    const T& top()
    {
      return _con.back();
    }
    size_t size()
    {
      return _con.size();
    }
    bool empty()
    {
      return _con.empty();
    }
  private:
    Container _con;
  };
  void test_stack()
  {
    stack<int> st1;
    stack<int, list<int>> st2;
    st1.push(1);
    st1.push(2);
    st1.push(3);
    st1.push(4);
    while (!st1.empty())
    {
      cout << st1.top() << " ";
      st1.pop();
    }
    cout << endl;
  }
};

二、queue

如下所示,是queue的模拟实现,需要注意的是,queue是不可以用vector进行适配的,因为vector并未提供pop_front接口,但是如果想要强制适配的话也是可以的,使用erase接口即可

#pragma once
#pragma once
#include<vector>
#include<list>
namespace Sim
{
  template<class T, class Container = list<T>>
  class queue
  {
  public:
    void push(const T& val)
    {
      _con.push_back(val);
    }
    void pop()
    {
      _con.pop_front();
    }
    const T& front()
    {
      return _con.front();
    }
    const T& back()
    {
      return _con.back();
    }
    size_t size()
    {
      return _con.size();
    }
    bool empty()
    {
      return _con.empty();
    }
  private:
    Container _con;
  };
  void test_queue()
  {
    queue<int> q1;
    q1.push(1);
    q1.push(2);
    q1.push(3);
    q1.push(4);
    while (!q1.empty())
    {
      cout << q1.front() << " ";
      q1.pop();
    }
    cout << endl;
  }
};

三、deque

1.deque介绍

虽然我们上面使用的适配器缺省参数都是vector或者list,但是我们会发现,库里面的stack和list它的适配器都是deque。deque听名字好像是个队列,名字是双端队列。但是队列是有先进先出的特性的,它不是那么特别符合队列。

Deque(通常发音像“deck”)是双端队列的不规则缩写。双端队列是具有动态大小的序列容器,可以在两端(前端或后端)扩展或收缩。

特定的库可能以不同的方式实现deque,通常是某种形式的动态数组。但在任何情况下,它们都允许通过随机访问迭代器直接访问单个元素,并根据需要通过扩展和收缩容器来自动处理存储。

因此,它们提供了类似于向量的功能,但在序列的开始,而不仅仅是在序列的末尾,也可以有效地插入和删除元素。但是,与vector不同,deque不能保证将其所有元素存储在连续的存储位置:通过偏移指向另一个元素的指针来访问deque中的元素会导致未定义的行为。

vector和deque都提供了非常相似的接口,可以用于类似的目的,但两者在内部的工作方式却完全不同:vector使用单个数组,偶尔需要为增长重新分配,而deque的元素可以分散在不同的存储块中,容器内部保留必要的信息,以便在恒定时间内使用统一的顺序接口(通过迭代器)直接访问其任何元素。因此,deque在内部比vector更复杂,但这使得它们在某些情况下更有效地增长,特别是对于非常长的序列,重新分配变得更加昂贵。

对于涉及频繁插入或删除除开始或结束位置以外的元素的操作,deque的性能更差,迭代器和引用的一致性也不如列表和前向列表。

2.deque的接口

如下所示,是deque的接口,我们可以发现,它似乎同时具有list和vector的接口。而且它的迭代器还是随机迭代器。

deque的接口像是vector和list的合体。但是它看似很强,实际上效率不是很高。单论头插头删,尾插尾删效率还是不错的,但是综合性不是很好。

3.deque的基本使用

void test_deque()
{
  deque<int> dq;
  dq.push_back(1);
  dq.push_back(2);
  dq.push_back(3);
  dq.push_back(4);
  for (int i = 0; i < dq.size(); i++)
  {
    cout << dq[i] << " ";
  }
  cout << endl;

我们可以得知

4.deque的效率

我们在前面说过,deque的综合效率是不高的。我们可以用下面的代码来看出

void test_op()
{
  srand(time(0));
  const int N = 1000000;
  vector<int> v1;
  vector<int> v2;
  v1.reserve(N);
  v2.reserve(N);
  deque<int> dq1;
  deque<int> dq2;
  for (int i = 0; i < N; ++i)
  {
    auto e = rand();
    //v1.push_back(e);
    //v2.push_back(e);
    dq1.push_back(e);
    dq2.push_back(e);
  }
  // 拷贝到vector排序,排完以后再拷贝回来
  int begin1 = clock();
  // 先拷贝到vector
  for (auto& e : dq1)
  {
    v1.push_back(e);
  }
  // 排序
  sort(v1.begin(), v1.end());
  // 拷贝回去
  size_t i = 0;
  for (auto& e : dq1)
  {
    e = v1[i++];
  }
  int end1 = clock();
  int begin2 = clock();
  sort(dq2.begin(), dq2.end());
  int end2 = clock();
  printf("deque copy vector sort:%d\n", end1 - begin1);
  printf("deque sort:%d\n", end2 - begin2);
}

deque效率慢的原因主要就是因为它的随机访问[]的效率太低

5.deque的原理

我们知道:

  1. 对于数组,可以下标随机访问,但是存在扩容问题,中间和头部插入效率低下

  2. 对于链表,任意位置插入删除效率合适,按需申请释放,但是不支持随机访问

而现在,我们使用的deque的结构是这样,它是一段一段的开空间,每段空间都是一样大的,然后通过一个中控数组(指针数组)进行连接起来。想要扩容就在连接一块空间即可。当指针数组满了,就中控数组扩容即可。这样一来扩容的代价就很低。不需要拷贝原来的数组。对于头插尾插也很简单,就用专门的两个空间进行头插尾插即可

它相比vector极大的缓解了扩容、头插头删问题。但是它的[]运算符不够极致。它的[]需要计算在哪个buff数组,在哪个buff数组的第几个。如果我们想要使用它的[]运算符,它内部的逻辑会经历一下几个步骤

  1. 先看在不在第一个buff数组里面,如果在,就直接访问
  2. 不在第一个buff数组里面,i-=第一个buff数组的size
  3. 第几个buff=i/buff.size()
  4. 在这个buff的第几个=i%buff.size()

它相比list,可以支持随机访问,cpu高速缓存访问效率不错,头插尾插删除不错,但是中间位置插入删除效率低下。因为我们需要扩容或者挪动buff的数据。无论哪一种,效率都很低。

根据deque的底层原理,其实对于高频的头插头删,尾插尾删来说,deque还很适合,所以deque用于适配stack和queue来说是很合适的,因为它们只涉及到头部和尾部的插入删除,不涉及中间位置的插入删除

实际上在库里面的deque是更加复杂的,它的迭代器由四个指针组成,这使得deque更加复杂,首先由node指向中控,即指向当前的buff数组,cur指向当前buff数组中的某个数据,first和last指向当前数组的头和尾


好了,本期内容就到这里了

如果对你有帮助的话,不要忘记点赞加收藏哦!!!

相关文章
|
1天前
|
C++ 容器
黑马c++ STL部分 笔记(6) queue 容器
黑马c++ STL部分 笔记(6) queue 容器
|
1天前
|
C++ 容器
黑马c++ STL部分 笔记(3) deque容器
黑马c++ STL部分 笔记(3) deque容器
|
4天前
|
设计模式 存储 编译器
【C++ STL】容器适配器(Stack & Queue & Priotity_Queue)-- 详解(下)
【C++ STL】容器适配器(Stack & Queue & Priotity_Queue)-- 详解(下)
|
4天前
|
存储 算法 C语言
【C++ STL】容器适配器(Stack & Queue & Priotity_Queue)-- 详解(上)
【C++ STL】容器适配器(Stack & Queue & Priotity_Queue)-- 详解(上)
|
4天前
|
编译器 C++ 容器
C++模板的原理及使用
C++模板的原理及使用
|
10天前
|
设计模式 算法 C++
【C++】STL之迭代器介绍、原理、失效
【C++】STL之迭代器介绍、原理、失效
14 2
|
3天前
|
C++
C++派生类
C++派生类
12 0
|
3天前
|
存储 程序员 数据安全/隐私保护
C++类
C++类
12 0
|
3天前
|
设计模式 安全 Java
【C++】特殊类设计
【C++】特殊类设计
|
4天前
|
编译器 C++
【C++】类和对象(下)
【C++】类和对象(下)