【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的适配器的原因。