deque

deque

底层数据结构

• 动态开辟的二维数组
• 第一维数组中存放的是第二维数组的指针
• 每个第二维数组大小为512字节。假如存放的是**_Tp类型,每个第二维数组存放512/(sizeof(_Tp**))个元素
• 按照第一维数组大小二倍进行扩容

举例

• 当deque进行push_back，将下半部分空间元素添加满的时候会进行扩容，以原来空间二倍进行扩容。如下所示。

  
  

  会以原来2倍空间开辟新的空间，并且将原数据复制到新的内存空间。

• deque进行push_front与push_back类似。

二倍扩容代码

template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_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 + __nodes_to_add;_Map_pointer __new_nstart;//省略部分.....{size_type __new_map_size = _M_map_size + max(_M_map_size, __nodes_to_add) + 2; // _M_map_size第一维数组大小，新扩容空间为原空间2倍_Map_pointer __new_map = _M_allocate_map(__new_map_size); // 按照新空间大小进行扩容__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2+ (__add_at_front ? __nodes_to_add : 0); // 定位新空间中元素存放的起始位置，起始位置为__new_nstartcopy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);  // 将原二维数组元素拷贝到新数组_M_deallocate_map(_M_map, _M_map_size);// 释放原二维数组空间_M_map = __new_map; _M_map_size = __new_map_size;}
}