C++面试八股文：std::deque用过吗？

jinchanchanwaji

某日二师兄参加XXX科技公司的C++工程师开发岗位第26面：

面试官：deque用过吗？

二师兄：说实话，很少用，基本没用过。

面试官：为什么？

二师兄：因为使用它的场景很少，大部分需要性能、且需要自动扩容的时候使用vector，需要随机插入和删除的时候可以使用list。

面试官：那你知道STL中的stack是如何实现的吗？

二师兄：默认情况下，stack使用deque作为其底层容器，但也可以使用vector或list作为底层容器。

面试官：你觉得为什么STL中默认使用deque作为stack的底层容器吗？

二师兄：额。。（stack也不需要双端插入啊，不应该vector更好吗。。）不是很清楚。。

面试官：没关系。那你知道deque是如何实现的吗？

二师兄：与vector内存空间连续不同，deque是部分连续的。deque通常维护了一个map（不是std::map），map的每个元素指向一个固定大小的chunk。同时维护了两个指针，指向头chunk和尾chunk。在deque的头部或尾部插入元素时，deque会找到头部或尾部的指针，并通过指针找到对应的chunk。如果chunk中还有未被元素填充的位置，则将元素填充到数组中，如果此指针指向的chunk已经被元素填满，则需要重新开辟一块固定大小的chunk，并将chunk记录在map中。

面试官：deque的查找、插入、删除的时间复杂度是什么？

二师兄：dqueue查找的时间复杂度是O(N)，插入要分情况，如果是头插和尾插，时间复杂度为O(1)，如果是中间插入，则是O(N)。删除元素和插入元素的时间复杂度相同。

面试官：好的。面试结束，回去等通知吧。

让我们来看一下二师兄的表现：

为什么STL中默认使用deque作为stack的底层容器吗？

STL默认选择deque最为stack的底层容器肯定是有原因的。vector和list同样可以作为deque的底层容器，让我们比较一下三个容器的差异：(只考虑头插和尾插，因为stack不需要随机插入)

	deque	vector	list
插入	O(1)	O(1)	O(1)
删除	O(1)	O(1)	O(1)

从上表中看到，三种容器的插入和是删除的时间复杂度相同。
但是如果连续插入时，情况发生变化。vector的capacity被耗尽，元素发生搬移。
list倒没有这个顾虑，但是当元素尺寸很小时，list的空间利用率太低。
deque虽然遍历效率不如vector、随机插入效率不然list，但stack并不需要这两种操作，所以deque是stack底层容器的最佳选择。
今天的面试分享到这里就结束了，让我们继续期待二师兄的表现吧。

jinchanchanwaji

<顺便吆喝一句，技术大厂年前捞人，前后端测试都有→https://jsj.top/f/o38ijj，感兴趣试试~>