【deque容器系列二】基于STL源码分析deque容器增删查实现及时间复杂度
【deque容器系列二】基于STL源码分析deque容器增删查实现及时间复杂度
上篇文章我们介绍了deque容器整体结构和构造实现，链接如下：
本篇文章接上篇，继续基于gcc中stl的源码剖析deque容器插入、删除、取值的实现原理，以提问者的角度去深入分析这些操作过程中发生了什么，并对deque容器适合使用的场景和使用时的注意事项进行说明。
说明一下，我用的是gcc7.1.0编译器，标准库源代码也是这个版本的。
按照惯例，还是先看一下本文大纲，如下：
0. deque容器迭代器说明
在正式开始讲述插入、删除等操作的实现前，我们先看下deque的特殊迭代器。
上篇文章我们说过，deque容器因为它特殊的内存结构，所以它是有自己专属的迭代器的，那就是类模板struct _Deque_iterator，这个类模板主要有4个成员变量，如下：
_Elt_pointer _M_cur; //用于保存迭代器当前位置
_Elt_pointer _M_first; //保存迭代器当前所属buffer的开始位置
_Elt_pointer _M_last;//保存迭代器当前所属buffer的结束位置
_Map_pointer _M_node; //用于保存迭代器当前所属的节点位置
所以deque是用上述成员变量来唯一标示一个迭代器的，下面插入和删除等操作有很多地方用到这些成员变量，就不再单独说明了。
1. 向deque容器插入一个元素
上一篇文章说到deque容器其实是一个双端队列，所以它的插入是可以从两端进行插入的，当然deque容器也支持从中间插入，下面我们结合源码一一的看一下插入的时候都发生了什么？
1.1 从两端插入会发生什么
所谓两端，我们分为头端和尾端，头端插入调用push_front函数，该函数源码如下：
void push_front(const value_type& __x)
{
//头部buffer空间足够时，直接从后往前插入
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
{
_Alloc_traits::construct(this->_M_impl,
this->_M_impl._M_start._M_cur - 1,
__x);
--this->_M_impl._M_start._M_cur;
}
else
//buffer不足，但节点足够时不重新申请节点，重新申请一个buffer即可，但如果节点不足，则重新申请一整块节点内存，并把原来的节点保存的地址都复制过去，而buffer却不会发生拷贝动作
_M_push_front_aux(__x);
}
结合代码和注释，从头部插入的流程就比较清晰了，看下图：
根据图片，一个deque容器从头端插入的大概流程就比较清楚了，但这中间节点数不够时到底怎么操作，我们这里还不是很清楚，那么继续往下看。
这里补充一点，就是deque容器在构造的时候到底构造多少个节点呢，是根据元素数量决定的，这里有一个公式：节点数量 = max(元素数量/512 + 2, 8)，512我们默认的每个buffer大小，如果根据元素数量算出来的节点数加2还小于8，那么就默认是8个节点，也就是说，就算你一开始指定元素数量为0，它构造时也会存在8个节点，只不过buffer只会申请一个而已。
头端插入的时候，如果节点数不够，是根据什么规则重新申请的呢，在_M_push_front_aux函数里面调用了_M_reserve_map_at_front函数，根据这个函数，如果需要新增的节点大于目前deque容器头端剩余备用节点数，就调用函数_M_reallocate_map，那么我们看下这个函数的实现，如下：
template <typename _Tp, typename _Alloc>
void
deque<_Tp, _Alloc>::
_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
{
const size_type __old_num_nodes
= this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
_Map_pointer __new_nstart;
if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
{
。。。。。。//当天头端插入的场景不会走到这里，所以省略掉
}
else
{
//计算出一个新的节点数量，如果需要新增加的节点数量小于原有节点数量，则直接在原来基础上乘以2再加2个备用节点，否则就是旧节点数量 + 待新增节点数量 +2
size_type __new_map_size = this->_M_impl._M_map_size
+ std::max(this->_M_impl._M_map_size,
__nodes_to_add) + 2;
//重新申请一块新的内存用于存放节点
_Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
std::copy(this->_M_impl._M_start._M_node,
this->_M_impl._M_finish._M_node + 1,
__new_nstart);
//释放原来旧的节点内存
_M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
this->_M_impl._M_map = __new_map;
this->_M_impl._M_map_size = __new_map_size;
}
this->_M_impl._M_start._M_set_node(__new_nstart);
this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}
这个函数分为两个分支，很显然我们此时会走到else分支里面，它会先算出新的节点数量，这个数量一般是在原来的基础上乘以2再加2个备用节点，具体规则看代码注释，然后根据当前计算出来节点数量重新申请一块新的内存用于存放节点，原来的节点内存会被释放掉。
尾端插入调用push_back函数，操作与push_front函数基本类似，这里不再多说，同时我们从代码可以看出，整个头部插入过程中没有涉及到数据的拷贝，所以说deque容器头部和尾部插入都十分迅速，时间复杂度基本上是O(1)。
需要特别注意的是，如果在构造的时候指定了大小，那么同时会进行默认的初始化，此时调用push_front和push_back的时候都是直接在现有基础上进行插入的，也就是说不会再改变构造的那部分元素的值了，所以正常情况下我们构造的时候最好不要指定大小，这样后续的调用会更加的清晰和正确。
1.2 从中间插入会发生什么
从中间插入需要根据迭代器位置进行插入，调用insert函数，一个insert源代码实现如下：
template <typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
#if __cplusplus >= 201103L
insert(const_iterator __position, const value_type& __x)
#else
insert(iterator __position, const value_type& __x)
#endif
{
//这里迭代器是头端当前迭代器就直接变为从头端插入了
if (__position._M_cur == this->_M_impl._M_start._M_cur)
{
push_front(__x);
return this->_M_impl._M_start;
}
//这里迭代器是尾端当前迭代器就直接变为从尾端插入了
else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
{
push_back(__x);
iterator __tmp = this->_M_impl._M_finish;
--__tmp;
return __tmp;
}
//这里才是正常从中间插入
else
return _M_insert_aux(__position._M_const_cast(), __x);
}
根据代码，非特殊情况下，主要看函数_M_insert_aux的实现，源代码如下：
template<typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
_M_insert_aux(iterator __pos, const value_type& __x)
{
value_type __x_copy = __x; // XXX copy
difference_type __index = __pos - this->_M_impl._M_start;
//如果待插入位置在deque容器的前半部分，那么就把前半部分从后往前移动
if (static_cast<size_type>(__index) < size() / 2)
{
//这里在头端先预先插入一位，看下是否需要扩充内存，保证内存足够
push_front(_GLIBCXX_MOVE(front()));
iterator __front1 = this->_M_impl._M_start;
++__front1;
iterator __front2 = __front1;
++__front2;
__pos = this->_M_impl._M_start + __index;
iterator __pos1 = __pos;
++__pos1;
//前半部分从后往前移动1位，当然之前的头端元素这里不会再重新处理
_GLIBCXX_MOVE3(__front2, __pos1, __front1);
}
//如果待插入位置在deque容器的后半部分，那么就把后半部分从前往后移动
else
{
//这里在尾端先插入1位，看下内存是否需要扩充，保证空间充足
push_back(_GLIBCXX_MOVE(back()));
iterator __back1 = this->_M_impl._M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
__pos = this->_M_impl._M_start + __index;
//这里后半部分从前往后移动1位
_GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
}
//插入数据
*__pos = _GLIBCXX_MOVE(__x_copy);
return __pos;
}
从代码可以看出，从中间插入说白了，它是做了移动的，根据待插入位置来决定是移动前半部分还是后半部分，而是否需要扩充容器大小还是由头端插入和尾端插入完成的，这里可以看出，中间插入的时间复杂度为O(n)。
2. 从deque容器中删除一个元素会发生什么
删除与插入一样，也是既可以从双端删除，也可以根据指定位置进行删除，下面具体的看一下。
2.1 从两端删除会发生什么
这里以尾端删除为例，源码实现如下：
void pop_back() _GLIBCXX_NOEXCEPT
{
__glibcxx_requires_nonempty();
if (this->_M_impl._M_finish._M_cur
!= this->_M_impl._M_finish._M_first)
{
--this->_M_impl._M_finish._M_cur;
_Alloc_traits::destroy(this->_M_impl,
this->_M_impl._M_finish._M_cur);
}
else
_M_pop_back_aux();
}
在deque容器的尾端迭代器中，如果当前位置不等于开始位置，则直接把当前位置向前移动一位，并把新的当前位置的元素销毁即可，也就是说尾端迭代器所指向的当前位置其实都是已经被删除了的数据，如果已经等于开始位置，则说明要换buffer了，此时就需要调用_M_pop_back_aux函数，所以我们接下来看看这个函数的实现：
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::
_M_pop_back_aux()
{
_M_deallocate_node(this->_M_impl._M_finish._M_first);
this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
_Alloc_traits::destroy(_M_get_Tp_allocator(),
this->_M_impl._M_finish._M_cur);
}
这里就比插入要简单一些了，直接释放了当前尾端迭代器所在的buffer，然后先计算出来新的当前位置，最后才进行删除动作，根据该逻辑，尾端删除时间复杂度为O(1)。
头端删除与尾端删除大同小异，这里不再多说，下面看看从中间删除是什么样的。
2.2 从中间删除会发生什么
从中间删除会调用erase函数，deque容器有诸多erase函数的重载，我们选取其中一个进行解析，如下：
iterator
#if __cplusplus >= 201103L
erase(const_iterator __first, const_iterator __last)
#else
erase(iterator __first, iterator __last)
#endif
{ return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
这个函数根据两个位置删除一段数据，直接调用的_M_erase，看下这个函数的实现：
template <typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::_M_erase(iterator __first, iterator __last)
{
//如果开始位置等于结束位置，就不用删除了
if (__first == __last)
return __first;
//如果开始位置等于容器的开始位置，结束位置等于容器的结束位置，那么直接整个容器清空即可
else if (__first == begin() && __last == end())
{
clear();
return end();
}
else
{
const difference_type __n = __last - __first;
const difference_type __elems_before = __first - begin();
//与从中间插入逻辑类似，如果待插入数据段前面的元素少于后面的元素数量，则从头端进行处理，否则从尾端处理
if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
{
//如果待删除数据段开始位置不等于容器开始位置，那么先把头端遗留数据向后覆盖
if (__first != begin())
_GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
//删除多余元素
_M_erase_at_begin(begin() + __n);
}
else
{
//与if类似，这里不多说了
if (__last != end())
_GLIBCXX_MOVE3(__last, end(), __first);
_M_erase_at_end(end() - __n);
}
return begin() + __elems_before;
}
}
也就是说从中间删除，其实是先用头端或者尾端数据把要删除的数据覆盖掉，然后再从头端和尾端删除掉多余的数据，在这个过程中，如果待删除数据段有跨buffer，那么这个buffer也会被销毁。
那么根据以上逻辑，从中间删除元素的时间复杂度就是O(n)了。
2.3 清空整个deque容器是怎么操作的
清空deque容器使用clear函数，如下：
void
clear() _GLIBCXX_NOEXCEPT
{ _M_erase_at_end(begin()); }
_M_erase_at_end函数是从入参指定位置到容器结束位置全部删掉，在这个过程中所有buffer也会被清掉。
3. deque容器获取元素及遍历
3.1 使用下标和at函数获取元素
下标其实就是重载运算符[]，如下：
reference
operator[](size_type __n) _GLIBCXX_NOEXCEPT
{
__glibcxx_requires_subscript(__n);
return this->_M_impl._M_start[difference_type(__n)];
}
从代码可以看出，其实直接就调用了迭代器_Deque_iterator的重载函数，如下：
reference
operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
{ return *(*this + __n); }
有的人看到这里会很疑惑，感觉不对劲，其实这里我们仔细分析一下，*this+__n其实又调用了_Deque_iterator的另外一个重载运算符函数operator +，如下：
_Self
operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
{
_Self __tmp = *this;
return __tmp += __n;
}
从代码看，还是感觉不大对，因为要跨buffer的，其实这里又调用了重载函数operator +=，我们看看这个函数的实现：
_Self& operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
{
const difference_type __offset = __n + (_M_cur - _M_first);
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
_M_cur += __n;
else
{
const 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个重载运算符函数，这里下标取数的时间复杂度也是O(1)。
接着看下at函数的源码，如下：
reference at(size_type __n) const
{
_M_range_check(__n);
return (*this)[__n];
}
从代码可以看出，其实at就是多检查了一下边界值，后续操作是直接调用的下标运算符函数，这里不再多说。
deque容器通过下标或者at函数获取元素时时间复杂度也为O(1)。
3.2 遍历一个deque容器
我们不要看到deque容器的迭代器比较复杂，就以为遍历比较麻烦，不是这样的，因为所有的操作我们deque的迭代器的运算符重载函数都帮我们做了处理的，所以遍历一个deque容器与遍历一个vector没有区别哈，如下：
#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int> dq(10, 5);//构造一个元素数量为10，且所有元素值都为5的deque
deque<int>::const_iterator it = dq.begin();
for(;it != dq.end(); ++it )
{
cout << "第" << it - dq.begin() << "个元素值为:" << *it << endl;
}
return 0;
}
与vector遍历没有区别哈，一切奥秘尽在运算符重载函数，这里不再多说。
4. deque容器使用总结
现在我们对deque容器总结如下：
- deque是一个双端队列，有一段连续的内存叫做node节点，每一个节点里面保存的是地址，要么为空，要么指向一个buffer块；
- deque的元素实际都保存在一个一个的buffer块中，所以deque扩容或者大量清空数据，则会涉及到多次申请动态内存或者多次释放动态内存的操作；
- 可以从双端进行插入和删除，时间复杂度为O(1)；
- 可以从中间进行插入和删除，此时对元素进行移动，所以时间复杂度为O(n)；
- 因为是双端队列，都是通过地址操作的，所以deque获取元素的速度也很快，时间复杂度为O(1)；
那么根据以上总结，我们可知如果需要同时从头端和尾端进行快速的插入或者删除，则使用deque容器会效率更高，比如12306抢票时候排队的场景，后来的需要进入队列排队，先来的如果抢到票了则需要从队列移除，此时就可以使用deque容器了。
腾讯云开发者
