STL deque实现解析

1.总体概览

• 双向开口的连续线性空间
• 头尾均可以常数时间插入和删除
• 空间是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，不用像vector那样重新分配新空间再拷贝
• deque提供Random Access Iterator 但是其迭代器不是普通指针，复杂度较之于vector会高出很多，所以一般使用vector而不是deque

2.deque的中控器（map)

• 采用一块所谓的map（并非STL的map容器），map是一小块连续空间，每个元素都是指针，指向一段连续空间（缓冲区)
• 缓冲区才是数据存储的主体
• 允许指定缓冲区大小，当默认值0表示缓冲区使用512字节
  
  

3.迭代器

• 需要指出分段连续空间在哪，并判断是否处于缓冲器边缘，并能够跳跃到另一个缓冲区
• 迭代器中含有三个T*指针，cur,first,last指的是迭代器所指的缓冲区中的当前元素、头、尾
• 此外还含有一个map_pointer类型的指针（可以看为T**)，指向map指针数组的一项，代表当前迭代器所属的缓冲区

3.1buffer_size,主要调用全局函数__deque_buf_size,获取缓冲区的大小

3.2 set_node跳跃一个缓冲区

    void set_node(map_pointer new_node){node=new_node;first=*new_node;last=first+(difference_type)buffer_size();}

3.3 重载运算符-，两个迭代器相减

• 除去两个操作数所在的缓冲区个数*buf_size

• 尾部部分 cur-first

• 头部部分 x.last-x.cur

  

3.4 随机存取，跳跃n个位置

4.deque数据结构

deque内部除了一个指向map的指针，还有两个指针start end，分别指向第一个缓冲区的第一个元素和最后一个缓冲区最后一个元素
此外，也需要记住map的大小，再map空间不足时，需要扩展map（重新分配空间，并且，map是从中间开始，向两侧扩散使用）

5.deque的内存管理

deque有两个空间配置器，一个用来分配元素的存储空间（即缓冲区），另一个用来分配map的空间

 typedef simple_alloc<value_type,Alloc> data_allocator;typedef simple_alloc<pointer,Alloc> map_allocator;

5.1 create_map_and_nodes(size_type num_elements)

1. 求出需要都少个缓冲区

size_type num_nodes=num_elements/buffer_size()+1;

2. 一个map最少管理8个节点，最多是“所需节点数+2”

map_size = max(initial_map_size(),num_nodes+2);

3. 配置map的空间
4. 使得map使用的部分处于整体的中间部位，利于之后的扩充、

map_pointer nstart =map+(map_size-num_nodes)/2;
map_pointer nfinish = nstart+num_nodes-1; 

5. 为map中每个现用节点配置空间，即让其指向缓冲区，也即开始配置缓冲区的空间

for(cur = nstart;cur<=nfinish;++cur)*cur=allocate_node()

6. 调整start和end的内容

完整代码如下：

5.2 填入初值

主要是调用create_map_and_nodes和uninitialized_fill

5.3 构造函数

6.deque的操作

6.1 push_back

1. 最后的缓冲区还有>=2的可用空间，则在这个缓冲区的cur位置构造新元素（注意:push_back中，cur表示下一个可用位置）
2. 若只有一个可用空间，则调用push_back_aux可能涉及到map的调整

6.2 push_back_aux

reverse_map_at_back以及后面的reverse_map_at_front都是重新调整map的结构

6.3 push_front

• 往前插时与往后插不同，cur表示的是第一个元素，往前插是需要在++cur上构造新的元素
• 故，push_front只需要判断是否还有可用空间即可，若无可用空间，则使用push_front_aux
  

6.4 push_front_aux

6.5 reverse_map_at_back 和reverse_map_at_front

都是调用reallocate_map完成，注意finish指向的是一个有效的节点，其代表最后一个缓冲区

6.6 reallocate_map

• 第一种情况，造成空间map空间不足的原因可能是因为一直往一个方向插入数据，使得map的分布没有处在中间位置，所以可以通过内部移动来解决。判定条件为：

size_type old_num_nodes=finish.node-start.node+1;
size_type new_num_node=old_num_nodes+nodes_to_add;if(map_size>2*new_num_nodes)//内部调整

• 第二种情况，重新分配更大的内存，new_map_size=map_size+max(map_size,node_to_add)+2;

6.7 clear

恢复最初状态，保留一个缓冲区

6.8 insert，支持任意位置插入，只是除首尾外，其效率较低

• 判断位置是否为首/尾，真，则直接交由push_back和push_front处理
• 否则，调用insert_aux

上述代码简而言之为：若前半部分元素数量少，则选择移动前半部分来完成插入，首先，复制第一个元素，push_front(front()),然后移动其他元素，空出一个位置，最后在该位置上填入要插入的元素；若后半部分元素少，先复制最后一个元素，push_back(back()),然后逆序复制其他元素，空出一个位置，最后在该位置填入要插入的值。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！