在使用c++容器的时候其底层如何实现  例如  vector 容器  :是一个内存可以二倍扩容的向量容器,使用方便但是对内存要求严格,弊端明显    list  容器  : 双向循环链表    deque  容器 :双端队列

deque容器是C++标准模版库(STL,Standard Template Library)中的部分内容。deque容器类与vector类似,支持随机访问和快速插入删除,它在容器中某一位置上的操作所花费的是线性时间。与vector不同的是,deque还支持从开始端插入数据:push_front()。

实际上双端队列是一个二维数组,但是实际存储数据的部分并不是连续的,一维数组存放指针,指向二维申请出来的空间,如图

首先申请一维空间存放指向二维的指针,例如一维空间长度为int len;则在len/4的位置先申请一块二维空间,指向前的指针*_frist与指向后的指针*_last 位于二维空间的中间,前插数据则*_frist--,后插数据则*_last++;

如果前插到二维的0下标位置,若一维数组上一个位置指向的空间为空,此时会在一维上一个位置申请二维,*_frist指向二维尾部,例如上图,会在*p   0 的位置申请二维,*_frist指向新开辟的二维的尾部,实现继续前插,若上面的所有一维都申请了二维,但是下面还有一维数组还有空,则整体将数据往下挪,把一维0号下标的二维空出来,继续前插,直到所有的一维都申请了二维并且数据放满,此时需要扩容,将一维数组2倍扩大,然后将所有数据移到新的一维数组所指向的二维数组中,满足数据位置为  :(新的一维数组长度/4)的位置。尾插同理  只是向下插方向相反。

下面是数据结构和基本函数

#define QUE_SIZE(T) 4096 / sizeof(T)
#define DEFAULT_QUE 2
class Deque
{
public:
  Deque();     //构造函数
  ~Deque();   // 析构函数
  Deque(const Deque &src);  // 左值引用参数构造拷贝函数 防止浅拷贝

  Deque(Deque &&src);        // 右值引用参数拷贝构造函数 防止临时量对空间时间的浪费


  Deque& operator=(const Deque &src);    //  左值引用参数赋值构造函数


  Deque& operator=(Deque &&src);          //  带右值引用参数的赋值构造函数

void push_back(int val); // 尾部入队

  void pop_back();         // 尾部删除

  void push_front(int val);  //  前插

  void pop_front();            //前删


  int front();          //返回队头元素

  int back();         //  返回队尾元素


  bool empty();   //   是否对空



private:
  int **mMapper;
  int *mFirst;
  int *mLast;
  int mMapperSize;
};

具体函数 封装成类

#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define QUE_SIZE(T) 4096 / sizeof(T)
#define DEFAULT_QUE 2
class Deque
{
public:
  Deque()
  {
  mMapper=new int*[DEFAULT_QUE]();
  mMapperSize=DEFAULT_QUE;
  mMapper[DEFAULT_QUE/4]=new int[QUE_SIZE(int)];
  mFirst=mMapper[DEFAULT_QUE/4]+QUE_SIZE(int)/2;
  mLast=mFirst+1;
  }
  ~Deque()
  {
  int i=0;
  for(;i<mMapperSize;i++)
  {
    delete []mMapper[i];
    mMapper[i]=nullptr;
  }
  delete []mMapper;
  mMapper=nullptr;
  }

  Deque(const Deque &src)
  {
    mMapper=new int*[src.mMapperSize]();
    int mfirst=-1;
    int mlast=-1;
    bool sign=1;
    int i;
    for(i=0;i<src.mMapperSize;i++)
    {
       if(src.mMapper[i]==nullptr)
       {
          continue;
       }
       if(src.mMapper[i]!=nullptr)
       {

         if(sign)
         {
           mfirst=i;
           sign=0;
         }

      int j;
      mMapper[i]=new int[QUE_SIZE(int)];
      for(j=0;j<QUE_SIZE(int);j++)
      {
        *(mMapper[i]+j)=*(src.mMapper[i]+j);
      }
      mlast=i;
     }

    }
    mFirst=mMapper[mfirst]+(src.mFirst-src.mMapper[mfirst]);
    mLast=mMapper[mlast]+(src.mLast-src.mMapper[mlast]);
    mMapperSize=src.mMapperSize;
  }
  Deque(Deque &&src)
  {
    mMapper=src.mMapper;
    mMapperSize=src.mMapperSize;
    mFirst=src.mFirst;
    mLast=src.mLast;
    src.mMapper=nullptr;
  }

  Deque& operator=(const Deque &src)
  {
    if(this==&src)
    {
      return *this;
    }
    int i=0;
    for(;i<mMapperSize;i++)
    {
      delete[]mMapper[i];
    }
    delete []mMapper;
    mMapper=new int*[src.mMapperSize]();
    int mfirst=-1;
    int mlast=-1;
    bool sign=-1;
    for(i=0;i<src.mMapperSize;i++)
    {
       if(src.mMapper[i]==nullptr)
       {
          continue;
       }
       if(src.mMapper[i]!=nullptr)
       {
         if(sign)
         {
           mfirst=i;
           sign=0;
         }
      int j;
      mMapper[i]=new int[QUE_SIZE(int)];
      for(j=0;j<QUE_SIZE(int);j++)
      {
        *(mMapper[i]+j)=*(src.mMapper[i]+j);
      }
      mlast=i;
     }
    }
    mFirst=mMapper[mfirst]+(src.mFirst-src.mMapper[mfirst]);
    mLast=mMapper[mlast]+(src.mLast-src.mMapper[mlast]);
mMapperSize=src.mMapperSize;
    return *this;
  }

  Deque& operator=(Deque &&src)
  {
    int i=0;
    for(;i<mMapperSize;i++)
    {
      delete []mMapper[i];
    }
    delete []mMapper;
    mMapper=src.mMapper;
    mMapperSize=src.mMapperSize;
    mLast=src.mLast;
    mFirst=src.mFirst;
    src.mMapper=nullptr;
    return *this;
  }
void push_back(int val) // 尾部入队
  {
     int index = -1;
     for (int i = 0; i < mMapperSize; ++i)
     {
         if (mMapper[i] == nullptr)
         {
            index = i;
            continue;
         }

   // 表示last已经指向行的末尾了,需要扩容
        if (mMapper[i] + QUE_SIZE(int) == mLast)
        {
  // 说明下面还有空行,直接分配新的第二维数组
        if (i != mMapperSize - 1)
        {
           mMapper[i+1] = new int[QUE_SIZE(int)];
           mLast = mMapper[i + 1];
           break;
        }

  // 说明last下面已经没有空闲行了
        if (index != -1)
        {
  // 说明上面还有空闲行,整体往上挪一行,下面就有一个空闲行了
           for (int i = index; i < mMapperSize-1; ++i)
           {
               mMapper[i] = mMapper[i + 1];
           }
               mMapper[mMapperSize-1] = new int[QUE_SIZE(int)];
               mLast = mMapper[mMapperSize - 1];
               break;
        }
        else
        {
   // 说明上面没有空闲行,一维需要开始扩容了
            int **tmpMapper = new int*[2* mMapperSize];
            int idx = 2 * mMapperSize / 4;
            for (int i = 0; i < mMapperSize; ++i)
            {
                tmpMapper[idx++] = mMapper[i];
            }
                   delete[]mMapper;
                        mMapper = tmpMapper;
                        mMapperSize *= 2;

                        mMapper[idx] = new int[QUE_SIZE(int)];
                        mLast = mMapper[idx];
                        break;
                    }
                }
            }
            // 添加元素
            *mLast++ = val;
  }
  void pop_back()
  {
    int i;
    bool sign=1;
    for(i=0;i<mMapperSize;i++)
    {
      if(mMapper[i]==mLast)
      {
        mLast=mMapper[i-1]+QUE_SIZE(int);
        sign=0;
        break;
      }
    }
    if(sign)
    {
      mLast--;
    }
  }

  void push_front(int val)
  {

    // 遍历第一维的数组,从下往上遍历 与尾插方法一样
     int index = -1;
     int i=mMapperSize-1;
     for (; i>=0; i--)
     {
        if (mMapper[i] == nullptr)
        {
             index = i;
             continue;
        }

       // 表示frist已经指向行首,需要扩容
       if (mMapper[i] ==mFirst)
         {
       // 说明上面还有空行,直接分配新的第二维数组
       if (i != 0)
       {
           mMapper[i-1] = new int[QUE_SIZE(int)];
           mFirst = mMapper[i-1]+QUE_SIZE(int);
             break;
       }

     // 说明frist下面已经没有空闲行了
       if (index != -1)

       {
     // 说明下面还有空闲行,整体往下挪一行,上面就有一个空闲行了
       for (i = index; i >0; i--)
       {
         mMapper[i] = mMapper[i-1];
       }
         mMapper[0] = new int[QUE_SIZE(int)];
         mFirst= mMapper[0]+QUE_SIZE(int);
          break;
        }
         else
        {
         // 说明下面没有空闲行,一维需要开始扩容了
           int **tmpMapper = new int*[2* mMapperSize];
           int idx = 2 * mMapperSize / 4;
           for (int i = 0; i < mMapperSize; ++i)
           {
               tmpMapper[idx+i] = mMapper[i];
           }
               delete[]mMapper;
               mMapper = tmpMapper;
               mMapperSize *= 2;

               mMapper[idx-1] = new int[QUE_SIZE(int)];
               mFirst = mMapper[idx-1]+QUE_SIZE(int);
               break;
                    }
                }
            }
            // 添加元素
            *mFirst-- = val;
  }
  void pop_front()
  {
    int i;
    bool sign=1;
    for(i=0;i<mMapperSize;i++)
    {
      if(mMapper[i]+QUE_SIZE(int)==mFirst)
      {
        mFirst=mMapper[i+1];
        sign=0;
        break;
      }
    }
    if(sign)
    {
      mFirst++;
    }

  }
  int front()
  {
    int i;
    for(i=0;i<mMapperSize;i++)
    {
      if(mMapper[i]+QUE_SIZE(int)==mFirst)
      {
        return *mMapper[i+1];
      }
    }
    return *(mFirst+1);

  }

  int back()
  {
    int i=0;
    for(;i<mMapperSize;i++)
    {
      if(mMapper[i]==mLast)
      {
        return *(mMapper[i-1]+QUE_SIZE(int));
      }
    }
    return *(mLast-1);

  }


  bool empty()
  {
    return mFirst+1==mLast;
  }



private:
  int **mMapper;
  int *mFirst;
  int *mLast;
  int mMapperSize;
};
int main()
{
     Deque s1;
     Deque s2;
     int i=0;
     for(;i<10000;i++)
     {
       s1.push_back(i);
     }
     s2=s1;
     for(i=0;i<10000;i++)
     {
      cout<<s2.front()<<' ';
       s2.pop_front();
     }
    cout<<endl;
    return 0;
}
01-19 01:09