某日二师兄参加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
底层容器的最佳选择。
今天的面试分享到这里就结束了,让我们继续期待二师兄的表现吧。文章来源:https://www.toymoban.com/news/detail-501270.html
关注我,带你21天“精通”C++!(狗头)文章来源地址https://www.toymoban.com/news/detail-501270.html
到了这里,关于C++面试八股文:std::deque用过吗?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!