STL源码分析--deque
文章目录
更多精彩内容,请关注微信公众号:后端技术小屋
1 deque相关头文件
deque
deque.h
stl_deque.h
2 deque的数据结构
deque为双向队列,同时支持从队首和队尾插入和弹出值。其数据结构分为两部分,如下图所示:
- 连续缓冲区
_M_map
, 元素类型为——Tp*
。如果元素值不为NULL
,则指向某个内存块;deque中使用__nstart
(二级指针类型__Tp**
)指向第一个内存块对应的数组元素;__nfinish
指向最后一个内存块对应的数组元素 - 一系列定长(512 Byte)的内存块,又可称为节点(
node
)。
代码如下,_Tp
表示deque
中元素类型,_Alloc
为内存分配器类型。_M_map_size
表示当前连续缓冲区_M_map
的长度,即最多能容纳多少个node
。迭代器_M_start
指向deque
的左确界,对应队首值。迭代器_M_finish
指向deque
的右虚界。
template <class _Tp, class _Alloc>
class _Deque_base {
...
protected:
_Tp** _M_map;
size_t _M_map_size;
iterator _M_start;
iterator _M_finish;
...
}
3 deque的迭代器
deque的迭代器属于random_access_iterator
, 支持随机访问
其中_M_cur
指向当前内存块node
中当前值的位置,_M_first
指向当前内存块node
的首地址,_M_last
指向当前内存块的虚边界
template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator {
typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
...
typedef _Tp** _Map_pointer;
...
_Tp* _M_cur;
_Tp* _M_first;
_Tp* _M_last;
_Map_pointer _M_node;
_Deque_iterator(_Tp* __x, _Map_pointer __y)
: _M_cur(__x), _M_first(*__y),
_M_last(*__y + _S_buffer_size()), _M_node(__y) {}
3.1 构造
迭代器的构造函数中,传入queue中_M_map
中元素地址__y
,和指向内存块node
中值的地址__x
,初始化_M_cur
, _M_first
, _M_last
和_M_node
。
template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator {
typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
...
typedef _Tp** _Map_pointer;
...
_Tp* _M_cur;
_Tp* _M_first;
_Tp* _M_last;
_Map_pointer _M_node;
_Deque_iterator(_Tp* __x, _Map_pointer __y)
: _M_cur(__x), _M_first(*__y),
_M_last(*__y + _S_buffer_size()), _M_node(__y) {}
3.2 operator++
首先判断迭代器当前位置是否为node
尾部,如果是,则跳转至右相邻node
头部,否则_M_cur
自增1
代码如下,其中_M_set_node
重新指定iterator
当前内存块为_M_node+1
,重置_M_first
和_M_last
_Self& operator++() {
++_M_cur;
if (_M_cur == _M_last) {
_M_set_node(_M_node + 1);
_M_cur = _M_first;
}
return *this;
}
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());
3.3 operator–
首先判断迭代器当前位置是否在当前node
头部,如果是,则跳转至左相邻node
的头部,否则_M_curr
自减1
_Self& operator--() {
if (_M_cur == _M_first) {
_M_set_node(_M_node - 1);
_M_cur = _M_last;
}
--_M_cur;
return *this;
}
3.4 operator+=
计算目标位置相对于本node
头部的偏移量,判断:
- 偏移量 <
node
大小,说明目标位置在本node
内,_M_curr
自增n
- 偏移量 >=
node
大小,说明目标位置不在本node
内,分别计算node
偏移量和_M_curr
偏移量,并更新iterator状态
_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 {
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;
}
4 deque的扩缩策略
4.1 push_front和push_back
pop_front
在队列头部压入值, pop_back
在队列尾部压入值。push_front和push_back是对称操作,区别只在于方向不同。流程如下
执行时分为以下几种情况:
- 头部/尾部
node
中是否有可用空间,如果是,则直接用于容纳新值,否则走2.
- deque map头部/尾部是否有可用空间,如果是,则创建新node容纳新值,否则走
3.
- deque map中剩余空间是否超过一半,如果是,则右移/左移所有node, 给deque map头部/尾部腾出空间,然后走
2.
; 否则走4.
- 重新申请更大的deque map空间,复制旧map上的
node
到新map, 继续走2.
void push_back(const value_type& __t) {
if (_M_finish._M_cur != _M_finish._M_last - 1) {
construct(_M_finish._M_cur, __t);
++_M_finish._M_cur;
}
else
_M_push_back_aux(__t);
}
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_push_back_aux()
{
_M_reserve_map_at_back();
*(_M_finish._M_node + 1) = _M_allocate_node();
__STL_TRY {
construct(_M_finish._M_cur);
_M_finish._M_set_node(_M_finish._M_node + 1);
_M_finish._M_cur = _M_finish._M_first;
}
__STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));
}
4.2 pop_front和pop_back
pop_front
在队列头部弹出值, pop_back
在队列尾部弹出值。
分两种情况:
- 更新
_M_start
或者_M_finish
之后仍在原node内,析构对象即可。 - 更新
_M_start
或者_M_finish
之后不在原node内,不仅要析构对象,还要释放node
void pop_back() {
if (_M_finish._M_cur != _M_finish._M_first) {
--_M_finish._M_cur;
destroy(_M_finish._M_cur);
}
else
_M_pop_back_aux();
}
// Called only if _M_finish._M_cur == _M_finish._M_first.
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_back_aux()
{
_M_deallocate_node(_M_finish._M_first);
_M_finish._M_set_node(_M_finish._M_node - 1);
_M_finish._M_cur = _M_finish._M_last - 1;
destroy(_M_finish._M_cur);
4.3 insert
分三种情况:
- 插入位置在头部,等效于
push_front
- 插入位置在尾部,等效于
push_back
- 插入位置既非头部,又非尾部,判断插入位置在前半部分还是后半部分:
- 前半部分: 执行
push_front(front())
, deque map前半部分左移,插入位置上构造对象。 - 后半部分:执行
push_back(back())
, deque map后半部分右移,插入位置上构造对象
- 前半部分: 执行
iterator insert(iterator position, const value_type& __x) {
if (position._M_cur == _M_start._M_cur) {
push_front(__x);
return _M_start;
}
else if (position._M_cur == _M_finish._M_cur) {
push_back(__x);
iterator __tmp = _M_finish;
--__tmp;
return __tmp;
}
else {
return _M_insert_aux(position, __x);
}
}
4.4 erase
判断擦除位置pos在前半部分还是后半部分
- 前半部分:pos之前部分右移,然后执行
pop_front
- 后半部分:pos之后部分左移,然后执行
pop_back
iterator erase(iterator __pos) {
iterator __next = __pos;
++__next;
difference_type __index = __pos - _M_start;
if (size_type(__index) < (this->size() >> 1)) {
copy_backward(_M_start, __pos, __next);
pop_front();
}
else {
copy(__next, _M_finish, __pos);
pop_back();
}
return _M_start + __index;
}
5 deque的适用场景
- 双端队列适合从两端增加和删除数据。不过在极端条件下,会产生节点申请和释放,以及deque map的复制。
- 对随机读写的支持较好,但是效率上不如
vector
, 因为索引到值的映射需要基于deque map进行计算。 - 对中间插入和删除不友好,因为可造成多次
_Tp
对象的copy
操作。因为insert
和erase
使用了push(pop)_front(back)``, 因此极端条件下,也会出现
1.`中的情况。
6 queue/stack/queue的关系
queue
和stack
中缺省底层数据结构是deque
template <class _Tp,
class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) >
class queue;
template <class _Tp,
class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) >
class stack;
当然你也可以自己实现支持front() back() push_front() pop_front() push_back() pop_back()
等接口的_Sequence
容器,不过建议还是用默认设置,除非能保证你实现的_Sequence
在性能能够超过deque
queue
等效于隐藏了接口push_front
和pop_back
的deque
, 而stack
等效于隐藏了接口push_front
和pop_front
的deque
。 仅此而已,所以要研究queue
和stack
的实现,最关键的还是弄清楚deque
推荐阅读
- STL源码分析–内存分配器
- STL源码分析–vector
- STL源码分析–string
- STL源码分析–list
- STL源码分析–hashtable
- STL源码分析–deque
- STL源码分析–iterator
- STL源码分析–traits
- STL源码分析–rbtree
- STL源码分析–bitset
- STL源码分析–algorithm
- STL源码分析–functional
更多精彩内容,请扫码关注微信公众号:后端技术小屋。如果觉得文章对你有帮助的话,请多多分享、转发、在看。
文章作者 后端侠
上次更新 2021-01-28