一篇文章搞懂STL中的顺序容器之deque
0.概述
什么是deque呢?
一句话来概括 ,deque是一种 双向开口的"连续"线性空间存储数据的数据结构(注意这里的连续打了双引号,后面会解释)
咱们来对比一下deque和vector的一些区别
优点:
1.vector是单向开口 deque是双向开口.也就是说vector只能在一端插入和删除数据,而deque在两端都可以插入和删除数据
(其实vector也可以在头部插入和删除,但是头部插入,后面的元素就得后移,所以效率奇差,一般不采用)
2.如第一条所说,vector在头部插入删除元素效率很低,但是deque在头部插入和删除元素是常数时间.
3.vector是一端连续线性空间,满了以后,在重新分配空间 搬运元素,回收原来空间.但是deque的连续线性空间的"连续"其实是一种假象,实际上他是动态的以分段连续空间组合而成的(这一点到后面会有讲解),所以deque没有必要提供空间保留功能
缺点:
1.vector和deque的迭代器都属于Random Acess Iterator ,且vector的迭代器本质上就是指针,而deque由于结构的复杂性,他的迭代器也会相应复杂得多,从而也影响了一些deque成员函数计算复杂性,所以一般可以用vector的地方尽量用vector.比如要对deque的元素排序时,为了提高效率,一般会把deque元素复制到vetor然后在vector里面排好序复制回deque.
下面将通过源码 分几个部分来讲解deque
1. 中控器与迭代器
-
原理讲解
现在来说一下为什么deque的连续是一种"假象"
deque本质上是由一段一段小的连续子空间拼在一起的,
当要在deque已满的情况下在尾部插入元素,deque会在尾部再加入一段小的连续子空间.
同样在deque已满的情况下在头部插入元素,deque会在头部再加入一段小的连续子空间.
然后通过某种办法来把这些分段的连续子空间维护其整体连续的假象.这个办法就是 中控器.
这样就避免了vector每次空间满了以后的"重新配置,搬运元素 回收内存"的麻烦 带来了上一节所说的三个优点
同时由于设计相对会复杂一点,所以就导致了deque实现复杂度会大很多.
下面来具体讲一讲整体连续的假象是怎么实现的.
所谓的中控器实际上就是一个指针数组(即数组元素是指针),叫map(注意不是STL的map容器)
上面讲的每一段小的连续子空间叫deque的缓冲区
然后map数组的每一个元素,即每一个指针都会指向一个相应的缓冲区,
当map数组满了以后,需要再找一个更大的空间来作为map,如下图
中控器对这些一段一段的缓冲区有一个很好的组织之后,下面就是迭代器发挥作用了.
一个deque会有两个迭代器,start和finish
start 迭代器负责起始的那块缓冲区,finish迭代器负责最后的那块缓冲区
每个迭代器会有四个指针域cur first last node
node指向在map中该缓存区所处的位置
first指向当前缓冲区的整体空间的头部
last指向当前缓冲区的整体空间的尾部
对于finish迭代器,cur指向当前缓冲区已用空间的最后一个元素位置(的下一个位置),
对于start迭代器,cur指向当前缓冲区已用空间的第一个元素位置
具体表示如下图
-
源码实现
先看一下map是怎么定义的
我们看到本质上map就是T**类型的一个指针数组.
再看一下迭代器_deque_iterator是怎么实现的
下面对迭代器的各个运算符进行了重载
再看一下中控器map和迭代器是怎么合作的
3.内存管理
过例子一步一步讲解内存模型
1、首先调用deque<int , alloc , 4> ideq(20,9)；函数，对应于下面构造函数及其调用函数
deque(size_type n, const value_type& value)
: start(), finish(), map(0), map_size(0)
{
fill_initialize(n, value);
}
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::fill_initialize(size_type n,
const value_type& value) {
create_map_and_nodes(n);
map_pointer cur;
__STL_TRY {
for (cur = start.node; cur < finish.node; ++cur)
uninitialized_fill(*cur, *cur + buffer_size(), value);
uninitialized_fill(finish.first, finish.cur, value);//尾部可能有多余空间
}
}
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::create_map_and_nodes(size_type num_elements) {
size_type num_nodes = num_elements / buffer_size() + 1;
/*
相当于20/8 + 1 = 3。刚好整除，则多分配一个节点
*/
map_size = max(initial_map_size(), num_nodes + 2);//map至少管理8个节点，最多是所需节点+2，前后各预留一个位置，扩充时候使用。
map = map_allocator::allocate(map_size);//分配指针数组
//先使用map指针数组中间的位置，方便前后扩充
map_pointer nstart = map + (map_size - num_nodes) / 2;
map_pointer nfinish = nstart + num_nodes - 1;
map_pointer cur;
__STL_TRY {
for (cur = nstart; cur <= nfinish; ++cur)
*cur = allocate_node();//初始化指针数组成员
}
start.set_node(nstart);//存储开始node
finish.set_node(nfinish);//存储结束node
start.cur = start.first;//指向第一个元素
finish.cur = finish.first + num_elements % buffer_size();//指向最后元素的后面一个元素形成[start , finish)左闭右开空间。
}
对应于下面过程fill_initialize首先调用create_map_and_nodes分配指针数组对应的内存和节点连续空间对应的内存，然后调用uninitialized_fill通过对应的构造函数初始化节点内存块。尾部设定稍微不同，因为可能有剩余空间。最后设定起始和终止迭代器。上述完成之后，内存空间布局如下。
2、接下来调用ideq[i]
先调用deque类里面的操作操作符重载函数reference operator[](size_type n) { return start[difference_type(n)];，进而调用迭代器类里面的操作符重载函数reference operator[](difference_type n) const { return *(*this + n); }，进而通过迭代器访问了元素。这里一个小小看似简单的操作其实涉及大量的重载运算符也就是大量的函数调用过程，访问异常复杂。在使用中给了人方便，但是相应的代价就是设计大量函数调用降低了效率。注意这里通过start[i]访问元素，其中start迭代器里面的内容没有变化，因为最后是通过operator+
self operator+(difference_type n) const {//对象重载+号
self tmp = *this;
return tmp += n;
}
上述返回了对象self，注意看effective上面全部有说明。执行完毕后对应的内存模型如下：
3、调用push_back(0);push_back(1);push_back(2)
看看下面函数注释就可以，具体考虑的细节不用明白，知道架构即可。后面有多余空间，直接构造，否则添加节点，再构造。
//尾部添加元素
void push_back(const value_type& t) {
if (finish.cur != finish.last - 1) {//尾部还有多余空间，一个以上的空间
construct(finish.cur, t);//直接构造
++finish.cur;//调整缓冲区状态finish的cur+1
}
else
push_back_aux(t);//没有或者只剩下一个，添加node，然后构造
}
// Called only if finish.cur == finish.last - 1.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_back();//加入后是否大于map内存空间
*(finish.node + 1) = allocate_node();//分配节点，node
__STL_TRY {
construct(finish.cur, t_copy);//构造元素
finish.set_node(finish.node + 1);
finish.cur = finish.first;//设定finish
}
__STL_UNWIND(deallocate_node(*(finish.node + 1)));//释放返回
}
4、再次调用push_back(3)
此时尾端仅仅只可以容纳一个元素，于是调用push_back_aux，再调用allocate_node分配一个节点空间。
5、调用push_front(99)
前面没有位置了，然后前面需要动态在添加一个位置，不像vector一样，需要移动再添加。这个就是deque的方便之处。这里调用了push_front_aux增加了一个节点。
void push_front(const value_type& t) {
if (start.cur != start.first) {
construct(start.cur - 1, t);
--start.cur;
}
else
push_front_aux(t);
}
// Called only if start.cur == start.first.
template <class T, class Alloc, size_t BufSize>
void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_front();//是否需要重新分配map
*(start.node - 1) = allocate_node();//分配node
__STL_TRY {
start.set_node(start.node - 1);
start.cur = start.last - 1;
construct(start.cur, t_copy);
}
}
6、再次调用push_front(98)，push_front(97)
内存模型如下：
7、当节点个数太多，8个节点map无法满足的时候，那么就需要动态分配map，设计map内存分配，数据拷贝，然后释放原来。
void reserve_map_at_back (size_type nodes_to_add = 1) {
if (nodes_to_add + 1 > map_size - (finish.node - map))
reallocate_map(nodes_to_add, false);
}
void reserve_map_at_front (size_type nodes_to_add = 1) {
if (nodes_to_add > start.node - map)
reallocate_map(nodes_to_add, true);
}
功能就是增加指针数组维度。