據我了解，任何支持 push_back()、pop_back() 和 back() 的容器都可以用作堆疊的底層容器，但默認情況下使用雙端佇列。我通常理解雙端佇列優于向量的優點（可以在開頭和結尾添加元素），但在堆疊的情況下，我認為沒有任何理由更喜歡雙端佇列。
uj5u.com熱心網友回復：
我看不出有任何理由更喜歡雙端佇列。
選擇適用于堆疊用例的雙端佇列的一個原因是，與向量相比，單個推回具有最壞情況下的常數復雜度，而向量在最壞情況下的單個推回是線性的（它在多次推回上具有攤銷的常數復雜度）。當重新分配向量必須復制可能非常昂貴的元素時，這在 C 11 之前尤為重要。考慮元素本身是長字串的情況。
更喜歡雙端佇列的另一個原因是它們在縮小時會釋放記憶體。向量沒有。因此，如果您有一個堆疊暫時變大，然后在執行的其余部分縮小并保持較小，那么底層向量將浪費大量記憶體。
從歷史上看，在設計 STL 并因此選擇默認值時，曾經也存在過大向量的問題，因為地址空間的大小沒有（顯著或根本）不超過記憶體量（這是之前64 位處理很常見）。有限地址空間的結果是記憶體碎片會使分配大型向量所需的大型連續記憶體塊變得昂貴或不可能。此外，向量通過釋放舊緩沖區而增長的方式是導致這種碎片的行為。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/445340.html