作者shashun (しゅん)
看板C_and_CPP
標題[問題] vector 的存取為何能達到O(1)?
時間Wed Mar 22 15:55:27 2017
大一生弱弱的問一下
我原本以為 vector 的作法類似 linked list 不過我最近在Wiki上看到vector的存
取是O(1)
但是 vector 不是動態記憶體嗎 陣列因為是連續的記憶體所以可以馬上知道位置
vector 的記憶體應該是分散的吧 那它的存取為什麼可以是 O(1)呢
我找到介紹 vector 的文章幾乎都只提說 vector 支援隨機存取 並沒有提到如何達成的
請問它是用了什麼方法才能隨機存取呢
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.59.150
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1490169329.A.7B9.html
1F：→ Sylveon: vector的定義是連續的記憶體，不可能用linklist 03/22 15:57
2F：推 suwako: vector內部是用類似array的連續記憶體下去實作的 03/22 15:57
3F：→ Sylveon: 可以用倍增法擴充陣列，可以證明這樣花費平均是O(1)的 03/22 16:00
4F：→ shashun: 所以假如它在擴增的時候下一個位置已經被佔用就會錯誤嗎 03/22 16:04
5F：推 AstralBrain: 不會, 他會要一個兩倍大的空間, 把整個array搬過去 03/22 16:06
6F：→ shashun: 喔這樣我懂了 感謝各位回答 03/22 16:09
7F：推 jaid: 他的Insert是amortized的 03/24 23:25
8F：推 LPH66: amortized O(1) 的不是 insert 喔, 是由於重新分配空間 03/24 23:49
9F：→ LPH66: 而複製的資料的個數 03/24 23:49
10F：→ LPH66: 單純的任意位置 insert 依然是 O(n) 03/24 23:50
11F：→ LPH66: 如果你是說 push_back 的話那才是 03/24 23:51