从零开始，打造自己的STL(五、deque)

发表于 | 更新于 | 分类于

deque简介

deque是双向开口的连续线性空间，支持内部元素的随机访问。看到这个概念，相信大家一定会想起vector，vector是单向开口的连续线性空间，内部元素也是可以随机访问的。

deque的元素类似这样

mark

那么deque像比于vector的差异在哪里

  1. deque的头部插入是vector没有的，虽然从技术角度来讲，vector实现头部插入也不是很难，但是效率太低，不值得且没必要
  2. 除了一些极端情况下，deque的空间是不需要重新分配的。大家都知道，vector在空间不足的时候，会重新分配一块新的空间，然后将原空间的数据全部copy进去，这个操作其实是非常低效率的。而deque在空间不足的时候，只需要再分配一块空间，并将这块空间链接到原空间上，具体怎么链接，基本上就是deque核心的东西了
  3. deque的排序效率非常低，所以一般是将deque的数据copy到vector中，排好序之后再copy回来
  4. deque同样支持元素的随机访问，这个要归功于其迭代器设计的精妙之处，不像vector，vector的迭代器本身就是元素类型的指针，只是因为他的内存结构，所以能够支持元素的随机访问

deque的内存结构

相信大家对deque如何将一块新空间链接到原空间上非常感兴趣，当时我学deque时也是这样，真正看了deque的源码之后，内心真正的感受是，还有这种操作(手动黑人问号)

下面先看一张deque的内存结构图

mark

首先，deque设计了一块map的映射区域，这块map本质就是元素类型的二级指针，并且用了一块连续的空间来存放这些二级指针，每一个二级指针就会指向一块数据的缓冲区，这样当所有的数据区域都分配完了之后，只需要重新再分配一块空间，并使得map的一块区域指向这块空间即可，这样就成功的将新空间链接上了原空间。

如果map的所有空间都已经映射满了，此时再新增空间的话，就要重新分配map的空间，其分配策略和vector类似，接下来将map中的指针域copy至新空间即可，而数据域是不需要改变的。

deque的空间分配

deque中数据区的大小

看了上面的内存结构之后不知道大家有没有一个疑问，数据区的内存要分配多大呢？因为数据区中一块空间的大小是固定的，它并不会动态的增长，我们分配了多大的空间就固定了它能存储的数据量，当这块空间用完了之后就只能再分配一块的数据区

再SGI的STL中是这样设计的

1
2
3
4
inline size_t _Deque_buf_size(size_t _size)
{
	return _size < 512 ? size_t(512 / _size) : size_t(1);
}

参数size为元素类型的大小，比如int就是4B，也就是说一块数据区就可以存128个int的数据，512是一个写死的魔数。当然，我们自己也可以将512这个基数通过模板参数传递，让我们自己决定分配多大

deque的内存分配

deque的内存分配方式分两步走，下面我们将一块数据区的空间称为node

  1. 分配map
  2. 分配node

具体怎么分配的我们从源码上了解最为直观

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
template<typename _Tp, typename _Alloc>
class _Deque_base
{
protected:
	iterator _m_start;			// 第一个有效node的位置
	iterator _m_finish;			// 最后一个有效node的位置
	_Tp** _m_map;
	size_t _m_map_size;
}

// map的大小默认为8, 超过8时为nodes+2 -- 使得map不会被占满
template <typename _Tp, typename _Alloc>
void _Deque_base<_Tp, _Alloc>::_M_initialize_map(size_t _num_elements)
{
	size_t _num_nodes = _num_elements / _Deque_buf_size(sizeof(_Tp)) + 1;
	_m_map_size = _S_initial_map_size > _num_nodes + 2 ? _S_initial_map_size : _num_nodes + 2;
	_m_map = _M_allocate_map(_m_map_size);

	// 使得start和finish所夹的空间尽量在整个空间的中央，使得向两边扩充的区域尽量相等
	_Tp** _start = _m_map + (_m_map_size - _num_nodes) / 2;
	_Tp** _finish = _start + _num_nodes;

	_M_create_nodes(_start, _finish);
	_m_start._M_set_node(_start);
	_m_finish._M_set_node(_finish - 1);
	_m_start._m_cur = _m_start._m_first;

	// finish.cur 指向的是有效元素的后一个位置
	_m_finish._m_cur = _m_finish._m_first + _num_elements % _Deque_buf_size(sizeof(_Tp));
}

从源码中应该展现了不少分配的细节

  1. 首先根据元素的个数和元素类型的大小决定所需node的个数
  2. 根据node的个数决定map的大小
  3. 分配map
  4. start和finish所夹的空间为整个map的中心，
  5. 分配node

看看分配node的详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename _Tp, typename _Alloc>
void _Deque_base<_Tp, _Alloc>::_M_create_nodes(_Tp** _start, _Tp** _finish)
{
	_Tp** _cur;
	for (_cur = _start; _cur != _finish; ++_cur)
	{
		*_cur = _M_allocate_node();
	}
}

_Tp *_M_allocate_node()
{
	return _Node_alloc_type::allocate(_Deque_buf_size(sizeof(_Tp)));
}

static _TP* allocate(size_t _n)
{
	return 0 == _n ? nullptr : (_TP*)_Alloc::allocate(_n * sizeof(_TP));
}

从代码中可以看到map中的[start, finish)区域分别存了每个node的指针，也就实现了map管理node，以后就可以直接通过map访问node了

deque的迭代器实现

从deque的内存结构中可以看到，deque中的空间并不像vector那样是完全连续的空间，只是一个node中的空间是连续的，那么如何实现对deque中元素的随机访问呢，这个就要归功于deque的iterator了，我们来看一下iterator的实现

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
template<typename _Tp, typename _Ref, typename _Ptr>
class _Deque_iterator
{
public:
	_Tp *_m_cur;			// 指向当前node的  当前位置		
	_Tp *_m_first;			// 指向当前node的  开始位置
	_Tp *_m_last;			// 指向当前node的  最后空间的下一个位置
	_Map_pointer _m_node;	// 指向当前node所在map
    
    // 通过该函数来跳到另一个缓冲区
	void _M_set_node(_Map_pointer _new_node)
	{
		_m_node = _new_node;
		_m_first = *_new_node;
		_m_last = _m_first + difference_type(_S_buffer_size());
	}

    reference operator[](difference_type _index)const
	{
		return *(*this + _index);
	}

    _Self operator+(difference_type _n)const
	{
		_Self _tmp = *this;
		return _tmp += _n;
    }

    _Self& operator+=(difference_type _n)
	{
		difference_type _offset = _n + (_m_cur - _m_first);
		if (_offset >= 0 && _offset < difference_type(_S_buffer_size()))
			_m_cur += _n;
		else//需要跳到另一个node中
		{
			// 计算向上或向下的node偏移量
			difference_type _node_offset = _offset > 0 ? _offset / difference_type(_S_buffer_size()) :
				-difference_type((-_offset - 1) / _S_buffer_size()) - 1;

			_M_set_node(_m_node + _node_offset);
			_m_cur = _m_first + (_offset - _node_offset * difference_type(_S_buffer_size()));
		}
		return *this;
	}

对元素的随机访问的操作方式是通过obj[num]来实现的，也就是说我们要实现operator[]操作符，代码中可以看到，op[]是通过op+=()实现的，我们重点也就看op+=()了。

通过一副图来解释一下

mark

假设我们的偏移大于了一个node的总空间， 也就是n+(cur-start)>_Deque_buf_size(sizeof(_Tp))，此时我们需要调到下一个node之中，可能是向下跳，也可能是向上跳，我们就用向下来举例，此时通过set_node函数调到下一个node之中，访问到我们想访问的元素了。所谓的跳到下一个node，也就是改变了当前node所在map中的指向而已。

deque的构造

1
2
3
4
deque(size_type _n, const_reference _value,) : _Base(_n)
{
	_M_fill_initialize(_value);
}

通过这个构造函数再来理一下我们之前说的空间分配和迭代器

首先通过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
_Deque_base(size_t _num_elements)
	:_m_start(), _m_finish(), _m_map(nullptr), _m_map_size(0)
{
	_M_initialize_map(_num_elements);
}

// map的大小默认为8, 超过8时为nodes+2 -- 使得map不会被占满
template <typename _Tp, typename _Alloc>
void _Deque_base<_Tp, _Alloc>::_M_initialize_map(size_t _num_elements)
{
	size_t _num_nodes = _num_elements / _Deque_buf_size(sizeof(_Tp)) + 1;
	_m_map_size = _S_initial_map_size > _num_nodes + 2 ? _S_initial_map_size : _num_nodes + 2;
	_m_map = _M_allocate_map(_m_map_size);

	// 使得start和finish所夹的空间尽量在整个空间的中央，使得向两边扩充的区域尽量相等
	_Tp** _start = _m_map + (_m_map_size - _num_nodes) / 2;
	_Tp** _finish = _start + _num_nodes;

	_M_create_nodes(_start, _finish);
	_m_start._M_set_node(_start);
	_m_finish._M_set_node(_finish - 1);
	_m_start._m_cur = _m_start._m_first;

	// finish.cur 指向的是有效元素的后一个位置
	_m_finish._m_cur = _m_finish._m_first + _num_elements % _Deque_buf_size(sizeof(_Tp));
}

通过上面的代码分配好了map和node的空间之后，接下来就是对元素的值进行填充了

1
2
3
4
5
6
7
8
9
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_fill_initialize(const_reference _value)
{
	_map_pointer _cur;
	for (_cur = _m_start._m_node; _cur < _m_finish._m_node; ++_cur)
		uninitialized_fill(*_cur, *_cur + _S_buffer_size(), _value);
	
	uninitialized_fill(_m_finish._m_first, _m_finish._m_cur, _value);
}

mark

填充分两步走，先将所有要填满的node进行填充，再填充剩余的

deque的map重分配策略

1
2
3
4
5
6
7
8
9
10
11
12
void _M_reserve_map_at_back(size_type _node_to_add = 1)
{
	if (_node_to_add + 1 > _m_map_size - (_m_finish._m_node - _m_map))
		_M_reallocate_map(_node_to_add, false);
}
void _M_reserve_map_at_front(size_type _node_to_add = 1)
{
	if (_node_to_add > size_type(_m_start._m_node - _m_map))
		_M_reallocate_map(_node_to_add, true);
}

void _M_reallocate_map(size_type _node_to_add, bool _add_at_front);

map的空间重分配分两种情况

  1. 在头部添加数据的时候发现前面空间不足
  2. 在尾部添加数据时发现尾部空间不足
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
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_reallocate_map(size_type _node_to_add, bool _add_at_front)
{
	size_type _old_num_nodes = _m_finish._m_node - _m_start._m_node + 1;
	size_type _new_num_nodes = _old_num_nodes + _node_to_add;

	_map_pointer _new_start;

	//  TODO: 当向某一边添加元素过多时，会导致一边的空间被占满，而另一边还有很多空间，这个时候只需要调整
	// TODO： start 和 finish的指向，使其尽量在整个空间的中间，即可满足条件。不需要重新分配空间
	if (_m_map_size > 2 * _new_num_nodes)
	{
		_new_start = _m_map + (_m_map_size - _new_num_nodes) / 2 + (_add_at_front ? _node_to_add : 0);

		if (_new_start < _m_start._m_node)
			copy(_m_start._m_node, _m_finish._m_node + 1, _new_start);
		else
			copy_backward(_m_start._m_node, _m_finish._m_node + 1, _new_start + _old_num_nodes);
	}
	else
	{
		size_type _new_map_size = _m_map_size + 
			(_m_map_size > _node_to_add ? _m_map_size : _node_to_add) + 2;

		_map_pointer _new_map = _M_allocate_map(_new_map_size);
		_new_start = _new_map + (_new_map_size - _new_num_nodes) / 2 +
			(_add_at_front ? _node_to_add : 0);

		copy(_m_start._m_node, _m_finish._m_node + 1, _new_start);
		_M_deallocate_map(_m_map);

		_m_map = _new_map;
		_m_map_size = _new_map_size;
	}
	_m_start._M_set_node(_new_start);
	_m_finish._M_set_node(_new_start + _old_num_nodes - 1);

在添加数据时发现空间不足时并不是一定会对map的空间重新尽心分配，如果一直在尾部添加数据，发现空间不足时，回去检测头部是否有足够的空间，如果有，则直接调整[start, finish)在map中的位置，使其处于map的中间，使map的空间相对平衡，也就不需要重新分配map空间了。

在map的空间实在不足的时候，重新分配map空间，大小为

1
2
size_type _new_map_size = _m_map_size + 
			(_m_map_size > _node_to_add ? _m_map_size : _node_to_add) + 2;

再将原map中的数据copy到现在的map中即可，当然[start, finish)依然处于新map的中心处