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

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

面试官:deque用过吗?

二师兄:说实话,很少用,基本没用过。

面试官:为什么?

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

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

二师兄:默认情况下,stack使用deque作为其底层容器,但也可以使用vectorlist作为底层容器。

面试官:你觉得为什么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的底层容器肯定是有原因的。vectorlist同样可以作为deque的底层容器,让我们比较一下三个容器的差异:(只考虑头插和尾插,因为stack不需要随机插入)

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

从上表中看到,三种容器的插入和是删除的时间复杂度相同。

但是如果连续插入时,情况发生变化。vectorcapacity被耗尽,元素发生搬移。

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

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

今天的面试分享到这里就结束了,让我们继续期待二师兄的表现吧。

关注我,带你21天“精通”C++!(狗头)

热门相关:恭喜你被逮捕了   锦乡里   重生野性时代   天神诀   半仙