共计 1113 个字符,预计需要花费 3 分钟才能阅读完成。
某日二师兄加入 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
底层容器的最佳抉择。
明天的面试分享到这里就完结了,让咱们持续期待二师兄的体现吧。
关注我,带你 21 天“精通”C++!(狗头)