作者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/cn.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