双端队列简介

顾名思义，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。

 上一页

.NET 多线程

 评论

 2018 - 2019 |  IntPtr.Zero



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

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