某日二師兄參加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++！（狗頭）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/556016.html
標籤：其他
上一篇：[ARM 匯編]高級部分—系統控制協處理器—3.2.3 控制暫存器的讀寫操作
下一篇：返回列表