深度剖析C++ STL deque容器的底层构造

在《初识STL库中deque容器》我们谈到“deque底层是中控区+缓冲区，可以理解为通过指针链接数组块”不知读者是否对这句话有印象。理解这句话，其实已经了解deque的60%了。接下来，我将为读者一一解释deque的神秘面纱。

deque分两部分，一部分是中控区，就是一个指针数组，存放着每一块内存的首地址；另一部分是缓冲区，存放着零散的小数组，所以说deque内元素可能不一定连续存储。

画一张图读者就理解了：

存储各个数组首地址的这个指针数组我们称之为map数组，当deque元素需要填充时（即头增或尾增），deque会通过创建内存——移动数据——更新存储指针来实现扩容。同理，如果map数组选哟扩容，也是需要类似操作实现“动态扩展”效果。

一般来说，只要知道map首地址就能够遍历deque内所有元素，但是为了提高性能，deque底层实际上维护了5个指针，分别是：存储位置首尾各一个，实际存储有效元素首尾各一个，一个map二级指针。它们的功能简单描述为是：首尾存储位置方便插入元素，首尾实际存储有效元素方便遍历元素，map二级指针方便管理各块数组头指针。