【C++】STL之容器适配器——使用deque适配stack和queue

简介: 【C++】STL之容器适配器——使用deque适配stack和queue

前言

本文章主要介绍容器适配器的功能,以及一个适配的场景。


一、什么是容器适配器?

容器适配器,按字面意思理解的话,就是用来对一个容器进行匹配的。在C++STL中,容器有:vector,list,deque,map,set等。

而在C++STL中不把stack和queue纳入容器的范围而是纳入容器适配器的范围是因为:

stack和queue没有下标随机访问等操作,只有普通的pop_front,push_back,pop_back()等操作,而这些函数在其他容器中完全可以有,栈和队列的实现完全可以将其他容器的操作进行复用,这就是stack和queue作为容器适配器的原因。

至于为什么用deque(双端队列)作为stack和queue的默认适配容器,先看一看stack和queue的基本函数使用。

二、stack的基本函数和模拟实现

可以看到在stl库开放的栈的接口中,仅有寥寥无几的几个接口,主要为:push,pop,size,empty,top。

由于栈的后进先出的特性,

  • 1.push是往栈顶进行push元素。
  • 2.pop是删除栈顶元素。
  • 3.size是计算当前的栈有多少元素
  • 4.empty是判断栈是否为空
  • 5.top是取栈顶元素

这几个函数完全可以复用其他容器的函数。

所以栈其实可以用vector,list等容器进行适配。

下面来模拟实现:

namespace dzt
{
  template<class T, class container = deque<T> >
  class stack
  {
  public:
    void push(const T& x)
    {
      _con.push_back(x);
    }
    void pop()
    {
      _con.pop_back();
    }
    bool empty()
    {
      return _con.empty();
    }
    size_t size()
    {
      return _con.size();
    }
    T& top()
    {
      return _con.back();
    }
  private:
    container _con;
  };
}

为了和库里面的stack不冲突,这里给了一个命名空间域dzt作为限定。

三、queue的基本函数和模拟实现

与stack类似,主要的函数有:

push,pop,front,back,size,empty。

由于队列先进先出的特性

  • 1.push,向队列尾部插入元素
  • 2.pop,删除队头元素
  • 3.front,取队头元素
  • 4.back,取队尾元素
  • 5.size,计算当前队列的元素个数
  • 6.empty,判断当前队列是否为空

下面来模拟实现queue

namespace dzt
{
  template<class T, class container = deque<T> >
  class queue
  {
  public:
    void push(const T& x)
    {
      _con.insert(_con.end(),x);
    }
    void pop()
    {
      _con.erase(_con.begin());
    }
    bool empty() const
    {
      return _con.empty();
    }
    size_t size() const 
    {
      return _con.size();
    }
    //取队头
    T& front()
    {
      return _con.front();
    }
    //取队尾
    T& back()
    {
      return _con.back();
    }
  private:
    container _con;
  };
}

四、deque

4.1deque的底层结构

deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比较高。

deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组

deque的底层结构如下:

  • 1.使用一个中控指针数组来存储各个位置的指针,而存储的位置一般只在数组的中间部分,大多数指针指向的内容都是一小块连续的空间,并且这些连续的空间的大小都是一样的。
  • start(iterator)记录头部数据,finish(iterator)记录尾部数据,头尾的插入删除效率非常高,O(1)。

  • cur记录指向的连续空间的第一个位置,first和last是该空间的区间,node反指回中控数组,方便找到下一个连续空间。

但是deque也有缺点,虽然它重载了[]访问,但是在访问中间元素时不够极致,需要进行计算。假设给定的下标为i,计算过程如下:

  • 1.i如果在第一个数组的范围,直接访问
  • 2.如果不在,i-=第一个数组的size
  • i/buffersize = 第i个数组的位置
  • 此时i指向了第i个数组,再用i/buffersize = 第i个位置的元素。

相比于vector,deque的下标访问的效率不够高,
相比于list,deque的中间位置插入删除效率不够高。

4.2使用deque适配stack和queue的原因

  • deque作为栈和队列的容器适配器而不是用vector/list的优点:
  • 1.deque的底层结构是使用中控指针数组来存储头和尾等各个空间的地址,对头尾的插入删除效率极高O(1)
  • 2.栈就需要push_back()和pop_back(),队列需要支持pop_front()和push_back() ——— 战胜了vector
  • 3.每一小块空间都是连续的,可以提高cpu高速缓存加载的效率。 ————战胜了list
  • 4.stack和queue都不需要[]随机访问,而deque的缺陷就是下标随机访问的效率不够高
  • 5.这样栈和队列的需求完美迎合了deque的优点,避开了deque的缺点

总结

本篇文章简单讲述了deque容器的底层原理以及相比于vector和list的缺点,还有用deque作为stack和queue的适配器的原因。

相关文章
|
23天前
|
设计模式 存储 C++
C++:Stack和Queue的模拟实现
C++:Stack和Queue的模拟实现
|
1月前
|
存储 算法 C++
C++初阶--queue和stack
C++初阶--queue和stack
|
存储 消息中间件 调度
【C++】容器篇(三)—— stack的基本介绍及其模拟实现
【C++】容器篇(三)—— stack的基本介绍及其模拟实现
|
21天前
|
C++ 容器
【C++练级之路】【Lv.9】【STL】stack类和queue类的模拟实现
【C++练级之路】【Lv.9】【STL】stack类和queue类的模拟实现
|
存储 算法 C++
【C++】容器篇(四)—— queue的基本介绍以及模拟实现
【C++】容器篇(四)—— queue的基本介绍以及模拟实现
【C++】容器篇(四)—— queue的基本介绍以及模拟实现
|
1月前
|
存储 安全 C++
深入理解C++ STL中的vector容器
深入理解C++ STL中的vector容器
12 0
|
1月前
|
存储 C++ 容器
【C++修行之道】STL(初识list、stack)
【C++修行之道】STL(初识list、stack)
|
20天前
|
存储 C++ 容器
C++入门指南:string类文档详细解析(非常经典,建议收藏)
C++入门指南:string类文档详细解析(非常经典,建议收藏)
31 0
|
20天前
|
存储 编译器 C语言
C++入门: 类和对象笔记总结(上)
C++入门: 类和对象笔记总结(上)
30 0
|
1天前
|
C++
【C++成长记】C++入门 | 类和对象(下) |Static成员、 友元
【C++成长记】C++入门 | 类和对象(下) |Static成员、 友元