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

看板C_and_CPP作者 (しゅん)時間8年前 (2017/03/22 15:55), 編輯推噓4(4推 0噓 7→)
留言11則, 6人參與, 最新討論串1/1
大一生弱弱的問一下 我原本以為 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
→
03/22 15:57, , 1F
vector的定義是連續的記憶體，不可能用linklist
03/22 15:57, 1F
推
03/22 15:57, , 2F
vector內部是用類似array的連續記憶體下去實作的
03/22 15:57, 2F
→
03/22 16:00, , 3F
可以用倍增法擴充陣列，可以證明這樣花費平均是O(1)的
03/22 16:00, 3F
→
03/22 16:04, , 4F
所以假如它在擴增的時候下一個位置已經被佔用就會錯誤嗎
03/22 16:04, 4F
推
03/22 16:06, , 5F
不會, 他會要一個兩倍大的空間, 把整個array搬過去
03/22 16:06, 5F
→
03/22 16:09, , 6F
喔這樣我懂了 感謝各位回答
03/22 16:09, 6F
推
03/24 23:25, , 7F
他的Insert是amortized的
03/24 23:25, 7F
推
03/24 23:49, , 8F
amortized O(1) 的不是 insert 喔, 是由於重新分配空間
03/24 23:49, 8F
→
03/24 23:49, , 9F
而複製的資料的個數
03/24 23:49, 9F
→
03/24 23:50, , 10F
單純的任意位置 insert 依然是 O(n)
03/24 23:50, 10F
→
03/24 23:51, , 11F
如果你是說 push_back 的話那才是
03/24 23:51, 11F
‣ 更多 shashun 的文章
文章代碼(AID): #1OqYtnUv (C_and_CPP)