stl向量如何隨機訪問

Question

昨天晚上我爲我的工作使用了std :: vector，這個問題突然出現在我腦海裏：vector如何給隨機訪問？

我試圖查看代碼，但不成功。任何人都可以提供一些建議嗎？

感謝， 阿倫

Answer 1

當然，這裏有一些指針：

int *x, *y; 

但嚴重的是，一個vector內部只是實現爲一個數組。它提供了一個超載索引操作符（[]），允許您像訪問數組一樣訪問它。

Answer 2

向量使用下面的連續內存，因此它以與數組本身相同的方式給予隨機訪問：它知道元素的起始地址和大小，並執行一些指針數學運算。

Answer 3

向量通常使用動態數組實現[*] ...在任何時候數據都存儲在一個連續的內存塊中，因此指針運算可用於O（1）訪問任何（已存在的）元件。

高效動態數組的技巧（假設你還不知道它），總是將保留存儲的大小至少增加一個常數（請參閱Jerry Coffin註釋）。這樣做的結果是，當我們添加不定數量的新元素時，爲了簡單起見，將因子設爲2，將第一個元素複製到第n個添加，並且將第（2 * n）個添加和第（4 * n）個添加和...

該系列收斂，所以我們可以保證添加N個新元素需要O（N）時間。但是，任何給定的添加可能需要重新分配以及所有現有元素的副本，因此沒有任何延遲保證。

[*]我不知道會達到所需性能的另一種機制。任何人？

Answer 4

至少兩個

的因素其實，許多實現使用的1.5 的因素，重要的是，它是一個因素，所以你得到的指數向量的增長。