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