Vector分配空间的策略是: 当vector空间满时, 在需要分配新空间以容纳新元素的情况下，将增加分配当前capacity的空间, 即vector的Capacity翻倍.
为什么这么设计呢? 原因是C++标准要求通过重复调用push_back而创建一个具有n个元素的vector耗费的时间不得超过O(n). 我们看看为什么这种方法可以达到要求。
假设现在需要给vector增加空间, 目前vector的capacity是N. 那么其中 N/2的数据，是没有经历过Copy的, N/4的数据的一半(N/8)是拷贝过两次的, N/8的数据的一半(N/16)的数据是拷贝过2次, N/16的数据的一半(N/32)的数据是拷贝过3次的, 依此类推:
Total_Move = N/2 * 1 + N/8 * 2 + N/32 * 3 + ... + N/(2^i + 1) * i
Lim(Total_move) = N.
因此, 使用新空间分配时倍增空间的方式，是可以达到内存拷贝复杂度为N的要求的。
另外一种每次给空间增加固定大小的方式，其复杂度是达不到要求的, 复杂度为o(N^2)级.
1 条评论:
fwx说: vector若空间不够，要扩大的时，的确是新new出一块新的来，然后再copy....，没有用realloc()可能用这个函数达不到空间复杂度为o(n).又把打包的改了。不用realloc()了。郁闷...
发表评论