某日二師兄參加XXX科技公司的C++工程師開發(fā)崗位第26面：
面試官：
deque用過嗎？二師兄：說實話，很少用，基本沒用過。
面試官：為什么？
二師兄：因為使用它的場景很少，大部分需要性能、且需要自動擴容的時候使用
vector，需要隨機插入和刪除的時候可以使用list。面試官：那你知道STL中的
stack是如何實現(xiàn)的嗎？二師兄：默認情況下，
stack使用deque作為其底層容器，但也可以使用vector或list作為底層容器。面試官：你覺得為什么STL中默認使用
deque作為stack的底層容器嗎？二師兄：額。。（
stack也不需要雙端插入啊，不應(yīng)該vector更好嗎。。）不是很清楚。。面試官：沒關(guān)系。那你知道
deque是如何實現(xiàn)的嗎？二師兄：與
vector內(nèi)存空間連續(xù)不同，deque是部分連續(xù)的。deque通常維護了一個map（不是std::map），map的每個元素指向一個固定大小的chunk。同時維護了兩個指針，指向頭chunk和尾chunk。在deque的頭部或尾部插入元素時，deque會找到頭部或尾部的指針，并通過指針找到對應(yīng)的chunk。如果chunk中還有未被元素填充的位置，則將元素填充到數(shù)組中，如果此指針指向的chunk已經(jīng)被元素填滿，則需要重新開辟一塊固定大小的chunk，并將chunk記錄在map中。
面試官：
deque的查找、插入、刪除的時間復(fù)雜度是什么？二師兄：
dqueue查找的時間復(fù)雜度是O(N)，插入要分情況，如果是頭插和尾插，時間復(fù)雜度為O(1)，如果是中間插入，則是O(N)。刪除元素和插入元素的時間復(fù)雜度相同。面試官：好的。面試結(jié)束，回去等通知吧。
讓我們來看一下二師兄的表現(xià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) |
從上表中看到，三種容器的插入和是刪除的時間復(fù)雜度相同。
但是如果連續(xù)插入時，情況發(fā)生變化。vector的capacity被耗盡，元素發(fā)生搬移。
list倒沒有這個顧慮，但是當元素尺寸很小時，list的空間利用率太低。
deque雖然遍歷效率不如vector、隨機插入效率不然list，但stack并不需要這兩種操作，所以deque是stack底層容器的最佳選擇。
今天的面試分享到這里就結(jié)束了，讓我們繼續(xù)期待二師兄的表現(xiàn)吧。文章來源：http://www.zghlxwxcb.cn/news/detail-501270.html
關(guān)注我，帶你21天“精通”C++?。ü奉^）文章來源地址http://www.zghlxwxcb.cn/news/detail-501270.html
到了這里，關(guān)于C++面試八股文：std::deque用過嗎？的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
