先简单叙述下问题背景：

STL 的 deque 的底层实现是用若干固定大小的块拼接而成，各块可以视为一个普通数组。在队列两端插入删除元素只需要移动头尾指针即可，如果头尾块已满则新创建一个块。

现在的问题是，如何在做到两端插入 $O(1)$ 时间复杂度的同时实现 $O(1)$ 的随机访问时间复杂度？

为了实现 $O(1)$ 的随机访问，我的思路是维护一个指针数组，存储每个块的起始位置，另外维护首块的 begin 指针和尾块的的 end 指针。利用首块的 begin 指针和每个块的大小，可以很快算出要访问第几个块，随后定位到该块内的元素。

但是，在这个实现下，deque 的前端插入就会出现问题。如果前端插入导致新块创建的话，原本存储各块位置的指针数组就要执行一个前端插入的操作，而这一操作显然是做不到 $O(1)$ 的。

所以 STL 的 deque 究竟是怎么实现的呢？