粉丝问：能不能说一下stl deque的源码？

为什么重点讲原理而不是逐行分析源码

deque的源码比较长，一行行来看它的源码不现实，所以这个视频我主要把deque的底层原理讲清楚，你理解原理后再去看代码就会轻松很多。

三大主流实现的共同设计

在三大主流实现中（libstdc++, libc++, MSVC STL）他们都采用相同的分块结构，只在细节策略上不同。

以下我们会以libstdc++实现为例进行讲解。

deque 的基本概念

新手C++程序员可能很难记住deque的用途，其实它的英文完整名称叫：double-ended queue。

中文翻译过来就是双端队列。

它两端插入/删除快，中间插入/删除较慢，随机访问快。

【画图】

参考：https://developer.aliyun.com/article/1377791

用一句话总结就是：分段连续 + 总体拼接，它既能扩容方便，又能随机访问高效。

deque 的底层数据结构

在底层，deque实现了一个中控数组，中控组织是一个指针数组，里边存储的是指向固定大小连续分配的一个分块，通常是512个字节。

它不是从数组开始的地方进行存储的，而是从中间的开始的，这是由deque的特性决定的，deque是一个双端队列，如果从头开始存储，那么push_front的时候就可能会涉及到数据的移动。

从中间开始，push_front的时候就可以从“头”部快速操作，而push_back的时候就可以从“尾”进行快速操作。

当我们需要访问某个元素的时候，只需要先找到对应的分块在哪，然后再通过偏移找到对应的元素。

迭代器设计与头尾快速操作

那它是如何实现快速的头尾操作呢？ 在 GCC libstdc++ 的 deque设计中，会有两个迭代器，一个start,一个finish。

start指向第一个分块，finish指向最后一个分块。

start和finish中都分别有current用于指向当前元素，first用于指向本分块的起点，last用于指向本分块的终点，node指向中控数组的对应位置。

头部操作（push_front / pop_front）

如果是头部操作，先看分块是否有剩余空间，如果有剩余空间，就往头部插入一个元素，再将current向前移动。

如果头部没有剩余空间，那么需要新建一个分块，并把中控数组对应的槽位指针指向新建的分块，把start迭代器相应的指针指向新建的分块，再把需要插入的元素放到新的分块的尾部，最后把start迭代器中current–就可以了。

如果是头部删除，就直接删除第一个元素，并把current++就可以了。

尾部操作（push_back / pop_back）

如果是尾部插入，同样也是先看尾部是否有剩余的空间，有的话就直接插入，没有剩余空间，也是新建一个分块，再把元素插入到新建分块的头部，再把finish相应的指针指向新的分块。

如果是尾部的删除，直接删除最后一个元素，并把迭代器的current指针向前移动。

中间插入和删除的操作复杂度

对于deque中间插入删除的操作是比较复杂的，会涉及到跨块搬运元素。例如在中间这个分块插入元素，它最后一块元素要挪到后边一个分块的开头，如果后一个分块空间不足，则还需要创建新的分块。

如果后边有多个分块的话，也需要将元素一一往后挪动。

deque算法会有一个优化，也就是会看要操作的元素是离头部较近，还是离尾部较近，如果离头部较近，那么就会移动头部的元素。

但这仍然是deque的性能灾难，要慎用。因此deque仅适用于频繁头尾操作的场景中。

总结

理解了deque的分块中控数组设计和start/finish迭代器机制后，再去看libstdc++的源码会清晰很多。deque在头尾操作频繁的场景下性能优秀，但在中间频繁插入删除时需谨慎使用。