p**e 发帖数: 335 | 1 int vector,1000个整数, 一个一个push_back,问array resize 多少次?如果是1,
000,000个整数, 一个一个push_back,问array resize 多少次? |
d********t 发帖数: 9628 | 2 你要是一开始就reserve了足够得数,一次都不用resize
【在 p**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : int vector,1000个整数, 一个一个push_back,问array resize 多少次?如果是1, : 000,000个整数, 一个一个push_back,问array resize 多少次?
|
p**e 发帖数: 335 | |
d********t 发帖数: 9628 | 4 那就没准了,取决于vector自己每次increment的size
【在 p**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不 reserve
|
c****p 发帖数: 6474 | 5 经典的做法是满的时候扩一倍,空到一半以下缩一半吧,当然也有别的比例。
这样保证增删操作的均摊成本是O(1)。
【在 p**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : int vector,1000个整数, 一个一个push_back,问array resize 多少次?如果是1, : 000,000个整数, 一个一个push_back,问array resize 多少次?
|
D***h 发帖数: 183 | 6 应该分别是
ceil(log(1000))
ceil(log(1000,000))
【在 p**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : int vector,1000个整数, 一个一个push_back,问array resize 多少次?如果是1, : 000,000个整数, 一个一个push_back,问array resize 多少次?
|
a********m 发帖数: 15480 | 7 要是回答这么精确的话还有一个起始大小要算进去。
【在 D***h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该分别是 : ceil(log(1000)) : ceil(log(1000,000))
|
p**e 发帖数: 335 | 8 正解,
我在电脑上是了一下,capacity是2^n
【在 c****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 经典的做法是满的时候扩一倍,空到一半以下缩一半吧,当然也有别的比例。 : 这样保证增删操作的均摊成本是O(1)。
|
p**e 发帖数: 335 | 9 确实是log 函数
【在 D***h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该分别是 : ceil(log(1000)) : ceil(log(1000,000))
|
l*****a 发帖数: 14598 | 10 头一半听说过
vector的internal implementation is dynamic array
后一半有理论根据吗?似乎没听说过
【在 c****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 经典的做法是满的时候扩一倍,空到一半以下缩一半吧,当然也有别的比例。 : 这样保证增删操作的均摊成本是O(1)。
|
a********m 发帖数: 15480 | 11 后一半好像是有问题。固定增长的均摊是o(1)。指数增长应该是o(lgn/n)吧。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 头一半听说过 : vector的internal implementation is dynamic array : 后一半有理论根据吗?似乎没听说过
|
v**m 发帖数: 706 | 12 why do not you take a look of the STL vector source code? |