鏈表基於矢量

Question

我想使用的std::vector容器的缺點，並想知道如果使用的是分塊鏈表的後端可避免當向量擴展發生副本。

類似於this。

我想我的問題是，這是一個實際的想法，我是否正確地認爲從容器讀取將具有與基於陣列的向量相似的運行時，而「增長」時間會大大減少？

Answer 1

解決方案的運行時（隨機）訪問將大於std::vector。

爲了訪問元素N，你可能要經過許多環節才能到適當的塊，然後通過塊訪問的元素。

大型矢量的性能可以通過預先分配更大的尺寸來降低。

如果插入和刪除頻繁，也許是一個矢量是錯誤的數據結構。

Answer 2

你可以用std::deque做一些實驗，它只是作爲你的描述。