关于c++:C面试八股文stddeque用过吗

某日二师兄加入 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 不须要随机插入)

从上表中看到，三种容器的插入和是删除的工夫复杂度雷同。

然而如果间断插入时，状况发生变化。vector的 capacity 被耗尽，元素产生搬移。

list倒没有这个顾虑，然而当元素尺寸很小时，list的空间利用率太低。

deque尽管遍历效率不如 vector、随机插入效率不然list，但stack 并不需要这两种操作，所以 deque 是stack底层容器的最佳抉择。

明天的面试分享到这里就完结了，让咱们持续期待二师兄的体现吧。

关注我，带你 21 天“精通”C++！（狗头）