双端队列简介

顾名思义,deque支持在头尾进行插入删除操作。类似于vector和array,deque也是顺序存储结构,没有了解过deque的人在主观上可能会以为deque与vector底层结构类似,实际上为了支持头部插入与删除操作,deque采用分段连续存储的数据结构,因此实现上比vector复杂得多。因为采用分段设计,deque的迭代器效率比vector低。
为了管理片段,STL的deque在内部定义了一个_Map成员,_Map底层实际是一个T**,也可以将_Map看作一个数组,每一个数组元素指向内存中的一段连续的元素存储空间

1
2
3
4
5
6
7
8
9
//VS2013 deque节选
template<class _Ty>
struct _Deque_simple_types
: public _Simple_types<_Ty>
{ // wraps types needed by iterators
typedef _Ty **_Mapptr;
};

_Mapptr _Map;

双端队列的迭代器

deque分类上属于顺序存储容器,因此迭代器理所应当提供随机访问迭代器的所有功能。但在内部deque是分段的,因此迭代器需要知道片段的大小以及片段的地址,以在到达片段边缘时跳转到另一个片段。SGI的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
template<typename T,typename Ref,typename Ptr,size_t BufSize>
struct _deque_iterator
{
//省略traits定义
typedef T** map_pointer;
typedef _deque_iterator self;

//每一个片段的元素容量,如果不指定,默认为512/sizeof(T)
static size_t buffer_size(){};

T* cur; //指向片段的当前可插入位置
T* first; //指向片段的头部
T* last; //指向片段的超尾
map_pointer node; //节点

//设置节点
set_node(map_pointer new_node)
{
node=new_node;
first=*new_node;
last=first+difference_type(buffer_size());
}

//迭代器之间的减法
difference_type operator-(self& x) const
{
return difference_type(buffer_size())*(node-x.node-1)+(cur-first)+(x.last-x.cur);
}

self& operator++()
{
++cur;
if(cur==last) //到达当前片段超尾
{
set_node(node+1); //跳转到下一片段
cur=first; //指向头部
}
return *this;
}

//自减操作类似,略过

self& operator+=(difference_type n)
{
difference_type offset=n+cur-first;
//判断是否在同一片段内偏移
if(offset>=0 && offset<difference_type(buffer_size()))
cur+=n;
else
{
difference_type node_offset=offset>0 ? offset/difference(buffer_size()):-difference_type((-offset-1)/buffer_size())-1;
set_node(node+node_offset);
cur=first+offset-node_offset*difference_type(buffer_size());
}
return *this;
}

//省略其它操作
}

双端队列的结构

deque结构图
SGI的deque结构如上图所示,其具体实现见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//基础成员
template<typename T,typename Alloc=alloc,size_t BuffSize=0>
class deque
{
public:
typedef _deque_iterator<T,T&,T*,BuffSize> iterator;

protected:
typedef pointer* map_pointer;

iterator start; //头部迭代器
iterator finish; //尾部迭代器
map_pointer map; //map
size_type map_size; //节点数量

public:
//头部迭代器
iterator begin() {return start;}
//尾部迭代器
iterator end() {return finish;}

//首元素
reference front() {return *start;}
//尾元素
reference back()
{
iterator tmp=finish;
--tmp;
return *tmp;
}

//略过其它常用接口
}

注意deque迭代器取值操作符返回*cur,start迭代器的cur总是指向首元素,finish迭代器的cur指向最后一个元素的下一位,因此需要前移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//构造函数
deque(int n,const value_type& value):start(),finish(),map(0),map_size(0)
{
fill_initialize(n,value);
}

template<typename T,typename Alloc,size_t BuffSize>
void fill_initialize(size_type n,const value_type& value)
{
create_map_and_nodes(n);
map_pointer cur;
for(cur=start.node;cur<finish.node;++cur)
uninitialized_fill(*cur,*cur+buffer_size(),value);
//尾部片段可能还有空闲,因此单独初始化
uninitialized_fill(finish.first,finish.cur,value);
}

template<typename T,typename Alloc,size_t BuffSize>
void create_map_and_nodes(size_type num_element)
{
//计算初始需要分配的节点数,如果刚好占满n个片段,则额外加一
size_type num_nodes=num_element/buffer_size()+1;
//初始节点数,最少为8。首尾各增加一个以供备用
map_size=max(8,num_nodes+2);
//为map分配内存保存节点
map=map_allocator::allocate(map_size);

//使初始占用的空间尽量居中,便于首尾插入
map_pointer nstart=map+(map_size-num_nodes)/2;
map_pointer nfinish=nstart+num_nodes-1;

map_pointer cur;
//为片段分配空间
for(cur=nstart;cur<=nfinish;++cur)
*cur=allocate_node();

start.set_node(nstart);
finish.set_node(nfinish);
start.cur=start.first;
finish.cur=finish.first+num_element%buffer_size();
}

再来看看deque在内部如何处理元素插入,以push_back为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
void push_back(const value_type& t)
{
//如果尾片段空余空间大于1,则直接赋值
if(finish.cur != finish.last -1)
{
construct(finish.cur,t);
++finish.cur;
}
//否则新分配一个片段
else
push_back_aux(t);
}

void push_back_aux(const value_type& t)
{
value_type t_copy=t;
//判断是否需要重新分配map
reserve_map_at_back();
//为下一个节点分配一个片段
*(finish.node+1)=alocate_node();
//现在finish所指的片段已满
construct(finish.cur,t_copy);
//尾迭代器指向下一个片段
finish.set_node(finish.node+1);
finish.cur=finish.first;
}

//判断尾部是否需要重新分配
void reserve_map_at_back(size_type node_to_add=1)
{
//尾部备用空间不足
if(node_to_add>map_size-(finish.node-map)-1)
//false尾部分配
reallocate_map(node_to_add,false);
}

//头部操作类似,略过

void reallocate_map(size_type node_to_add,bool add_at_front)
{
size_type old_num_nodes=finish.node-start.node+1;
size_type new_num_nodes=old_num_nodes+node_to_add;
map_pointer new_nstart;
//对应于一端插入,另一端删除时的极端情况,此时map中只有后半段的节点被利用,不需要重新申请更大的map
if(map_size>2*new_num_nodes)
{
//重新安排头部节点到中间
new_nstart=map+(map_size-new_num_nodes)/2+(add_at_front?node_to_add:0);
if(new_nstart<start.node)
//先序复制防止左边被覆盖
copy(start.node,finish.node+1,new_nstart);
else
//后序复制防止右边被覆盖
copy_backward(start.node,finish.node+1,new_nstart+old_num_nodes);
}
//对应正常情况,map中空余节点不足
else
{
size_type new_map_size=map_size+max(map_size,node_to_add)+2;
//申请更大的map
map_pointer new_map=map_allocator::allocate(new_map_size);
//开始节点居中
new_nstart=new_map+(new_map_size-new_num_nodes)/2+(add_at_front?node_to_add:0);
//复制原节点
copy(start.node,finish.node+1,new_start);
//释放原map
map_allocator::deallocate(map,map_size);
map=new_map;
map_size=new_map_size;
}
start.set_node(new_nstart);
finish.set_node(new_nstart+old_num_nodes+1);
}

接下来是删除操作,SGI的deque在片段中没有元素时会销毁片段以节省内存,具体实现如下,以pop_back为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void pop_back()
{
//尾部片段有元素
if(finish.cur!=finish.first)
{
//注意cur指向最后一个元素的下一位
--finish.cur;
destroy(finish.cur);
}
else
//没有元素
pop_back_aux();
}

void pop_back_aux()
{
//销毁这个空片段
deallocate_node(finish.first);
//跳转到上一个节点
finish.set_node(finish.node-1);
finish.cur=finish.last-1;
destroy(finish.cur);
}

//pop_front类似,略过

接下来是clear方法,该方法清除deque所有元素并将deque初始化,SGI的deque在初始状态仍会保留一个片段,代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void clear()
{
for(map_pointer node=start.node+1;node<finish.node;++node)
{ //析构元素
destroy(*node,*node+buffer_size());
//销毁片段
deallocate(*node,buffer_size());
}

//头尾不在同一个片段
if(start.node!=finish.node)
{
destroy(start.cur,start.last);
destroy(finish.first,finish.cur);
//仅销毁尾部
deallocate(finish.first,buffer_size());
}
else
//仅析构
destroy(start.cur,finish.cur);
finish=start;
}

基本上常见的deque操作都与上面的实现类似,注意map的操作即可。

MS的deque实现

MS与SGI的实现有较大区别,首先在deque内部成员上VS2013没有定义start和finish两个迭代器,而是定义了一个_Myoff记录头节点偏移量以及_Mysize记录元素数量:

1
2
size_type _Myoff;
size_type _Mysize;

在内部,deque利用_Myoff计算节点下标来访问节点:

1
2
3
4
5
size_type _Getblock(size_type off) const
{
//_DEQUESIZE片段长度,_Mapsize代表map的大小
return ((off/_DEQUESIZE) & (this->_Mapsize-1));
}

其次,MS的deque采用倍增的扩展策略,即每次重新分配map时大小变为原来的2倍(初始为8,不可自定义):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//VS2013
void _Growmap(size_type _Count)
{
typedef typename _Alpty::pointer _Blockptr;
_Alpty _Almap(this->_Getal());
size_type _Newsize = 0 < this->_Mapsize ? this->_Mapsize : 1;
while (_Newsize - this->_Mapsize < _Count || _Newsize < _DEQUEMAPSIZ)
{
//size加倍
_Newsize *= 2;
}
//计算需要新增的节点数量
_Count = _Newsize - this->_Mapsize;
//计算头节点偏移
size_type _Myboff = this->_Myoff / _DEQUESIZ;
//申请新的map
_Mapptr _Newmap = _Almap.allocate(this->_Mapsize + _Count);
//新的头节点
_Mapptr _Myptr = _Newmap + _Myboff;
//复制旧节点
_Myptr = _Uninitialized_copy(this->_Map + _Myboff,this->_Map + this->_Mapsize,_Myptr, _Almap);
//如果新增节点数量大于头节点偏移
if (_Myboff <= _Count)
{
//复制旧map头节点之前未使用的节点到新map的尾部(意义不明,应该是为了减少初始化次数)
_Myptr = _Uninitialized_copy(this->_Map,this->_Map + _Myboff,_Myptr, _Almap);
//初始化剩余的尾部节点
_Uninitialized_default_fill_n(_Myptr, _Count - _Myboff,_Almap);
//初始化头部节点
_Uninitialized_default_fill_n(_Newmap, _Myboff, _Almap);
}
else
{
//复制旧map头部未使用的节点到新map尾部
_Uninitialized_copy(this->_Map,this->_Map + _Count,_Myptr, _Almap);
//复制剩余的旧map头部到新map头部
_Myptr = _Uninitialized_copy(this->_Map + _Count,
this->_Map + _Myboff,_Newmap, _Almap);
//初始化新map头部未能复制到的节点
_Uninitialized_default_fill_n(_Myptr, _Count, _Almap);
}
//析构旧map元素
_Destroy_range(this->_Map + _Myboff, this->_Map + this->_Mapsize, _Almap);
//释放旧map空间
if (this->_Map != _Mapptr())
_Almap.deallocate(this->_Map,this->_Mapsize);
this->_Map = _Newmap; // point at new
this->_Mapsize += _Count;
}

相比起来MS的实现更加复杂化,结构层次也不明显,代码质量明显比SGI差很多。最后再吐槽一下MS神奇的变量命名方式以及各种奇葩#define。

 评论




载入天数...载入时分秒...  |  总访问量为
Powered by Github and MarkdownPad 2

--------------------------- 别拉了,我是有底线的>_< ---------------------------