当前位置: 代码迷 >> 综合 >> C ++ deque
  详细解决方案

C ++ deque

热度:95   发布时间:2023-12-12 23:41:58.0

1.基本概念

deque是一个双端队列,内容保存在堆中,支持随即访问和快速插入删除,在容器中某一位置上的操作所花费的是线性时间。它的保存形式为:堆1       堆2        堆3

每个堆保存好几个元素,堆和堆之间有指针指向。

使用时添加头文件#include<deque>。

1.1内部原理

     vector内部采用连续的线性空间,空间不足时会重新申请空间。deque容器存储数据的空间是由一段一段等长的连续空间组成,各段可能位于内存的不同区域。

        deque容器使用数组map存储各个连续空间的首地址,map中存储的都是指针,指向真正的连续存储空间,从而实现整体连续的效果。当向deque容器头部或尾部插入元素需要增加存储空间时,会申请一段新的连续空间,同时在map数组的开头或结尾添加指向该空间的指针,将该空间链接到deque容器的头部或尾部。

         如果map数组满了,再申请一块更大的空间供map数组使用,将原有数据(指针)拷贝到新的map数组中,然后释放旧的空间。

        deque容器的分段存储结果,提高了在序列两端添加或删除元素的效率,同时也使得容器的底层实现变得更复杂。

1.2底层实现

 deque迭代器的内部结构如下

template<class T,...>
struct __deque_iterator{...T* cur;T* first;T* last;map_pointer node;//map_pointer 等价于 T**
}

内部维护了4个指针:

  • cur:当前正在遍历的元素
  • first:当前连续空间的首地址
  • last:当前连续空间的末尾地址
  • node:是一个二级指针,指向map数组中存储的指向当前连续空间的指针

deque容器的底层实现

deque容器除了维护map数组,还维护start,finish迭代器,deque容器的定义如下:

//_Alloc为内存分配器
template<class _Ty,class _Alloc = allocator<_Ty>>
class deque{...
protected:iterator start;iterator finish;map_pointer map;
...
}

 其中,start迭代器记录中map数组中首个连续空间的信息,finish迭代器记录着map数组中最后一个连续空间的信息。和普通迭代器不同的是,start迭代器中的cur指针指向的是连续空间的首个元素,finish迭代器的cur指针指向的连续空间最后一个元素的下一个位置。

 

1.3构造函数

deque<T> deq;///默认构造
deque(begin,end);///构造函数将[begin,end)之间的元素拷贝给本身
deque(n,val);///构造函数将n个val拷贝给本身
deque(const deque &deq);///拷贝构造函数

示例如下:

deque<int> deq1;for(int i=0;i<5;i++)deq1.push_back(i);deque<int> deq2(deq1.begin(),deq1.end());///值为0,1,2,3,4deque<int> deq3(3,50);///50,50,50deque<int> deq4=deq2;//值为0,1,2,3,4deque<int> deq5={1,2,3,4,5};deque<int> deq6(deq1);

二、操作函数

1)赋值操作

对deque容器进行赋值。函数原型为:

deque& operator=(const deque &deq);///重载等号操作符assign(deq.begin(),deq.end());///将[begin,end)中的元素拷贝赋值assign(n,val);//将n个val拷贝赋值

示例如下:

 deque<int> deq1={1,2,3,4,5};deque<int> deq2=deq1;//1,2,3,4,5deque<int> deq3;
deq3.assign(deq2.begin(),deq2.end());///1,2,3,4,5deque<int> deq4;
deq4.assign(5,3);//3,3,3,3,3

2)插入元素

deque可以从两端插入元素。函数原型为:

push_back(val);//尾部插入
push_front(val);//头部插入insert(pos,val);//位置pos插入元素val,返回的是新元素的位置
insert(pos,n,val);//位置pos插入n个val,无返回值
insert(pos,begin,end);//位置pos插入[begin,end)之前的元素,无返回值

示例如下:

    deque<int> deq1={1,2,3,4,5};deq1.push_back(6);//1,2,3,4,5,6deq1.push_front(0);//0,1,2,3,4,5,6deq1.insert(deq1.begin()+2,0);//0,1,0,2,3,4,5,6deq1.insert(deq1.begin()+4,2,0);//0,1,0,2,0,0,3,4,5,6

3)删除元素

删除同样可以从两端进行删除

pop_back();//删除最后一个元素
pop_front();//删除第一个元素erase(begin,end);//删除[begin,end)之间的元素
erase(pos);//删除指定pos位置的元素clear();//删除所有的元素

示例如下:

deque<int> deq1={1,2,3,4,5,6};deq1.pop_back();//1,2,3,4,5
deq1.pop_front();//2,3,4,5deq1.erase(deq1.begin(),deq1.begin()+1);///3,4,5
deq1.erase(deq1.begin()+2);//3,4
deq1.clear();//删除所有

4)获取数据

at(int idx);//返回索引idx所指的数据
operator[idx];//返回索引idx所指的数据
front();//返回第一个元素
back();//返回最后一个元素

示例如下

 deque<int> deq1={1,2,3,4,5,6};cout<<deq1.at(3)<<endl;//4
cout<<deq1[5]<<endl;//6
cout<<deq1.front()<<endl;//1
cout<<deq1.back()<<endl;//6

5)容器大小

函数原型为:

empty();//判断是否为空,为空返回1,否则返回0size();//容器中元素个数resize(num);//重新指定容器长度,容器变长,使用默认值0填充,容器变短,超过的部分被删除resize(num,val);//重新指定容器长度,容器变长,使用值val填充,容器变短,超过的部分被删除

示例如下:

 deque<int> deq1={1,2,3,4,5};cout<<deq1.empty()<<endl;//0
cout<<deq1.size()<<endl;///5
deq1.resize(10);///1,2,3,4,5,0,0,0,0,0
deq1.resize(12,2);///1,2,3,4,5,0,0,0,0,0,2,2

6)排序

使用sort函数,示例如下:

    deque<int> deq1={1,2,8,0,4,5,6};sort(deq1.begin(),deq1.end());//0,1,2,4,5,6,8

  相关解决方案