[問題] vector 的存取為何能達到O(1)?

[shashun (しゅん)]

大一生弱弱的問一下

我原本以為 vector 的作法類似 linked list     不過我最近在Wiki上看到vector的存
取是O(1)

但是 vector 不是動態記憶體嗎   陣列因為是連續的記憶體所以可以馬上知道位置

vector 的記憶體應該是分散的吧  那它的存取為什麼可以是 O(1)呢

我找到介紹 vector 的文章幾乎都只提說 vector 支援隨機存取 並沒有提到如何達成的

請問它是用了什麼方法才能隨機存取呢

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.59.150
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1490169329.A.7B9.html
→ Sylveon: vector的定義是連續的記憶體，不可能用linklist
推 suwako: vector內部是用類似array的連續記憶體下去實作的
→ Sylveon: 可以用倍增法擴充陣列，可以證明這樣花費平均是O(1)的
→ shashun: 所以假如它在擴增的時候下一個位置已經被佔用就會錯誤嗎
推 AstralBrain: 不會, 他會要一個兩倍大的空間, 把整個array搬過去
→ shashun: 喔這樣我懂了 感謝各位回答
推 jaid: 他的Insert是amortized的
推 LPH66: amortized O(1) 的不是 insert 喔, 是由於重新分配空間
→ LPH66: 而複製的資料的個數
→ LPH66: 單純的任意位置 insert 依然是 O(n)
→ LPH66: 如果你是說 push_back 的話那才是