stl 中 vector 的 resize

溫 315 溫到 memory 的部份, 突然想起很久以前就想知道 stl::vector (下稱 vector) 是怎樣寫
為甚麼 vector 可以這麼神奇, 能不受限制地 push_back, 又可以快速地 random access?

最合理的解釋便是一開始預留了 memory 給那條 vector, 當不夠用時便 malloc 更多的空間
然後當然很好奇想知道每次預留多少空間 (估計是 4K), 一於寫個 program 試下

vector<int> a;
int *expect, *real;
a.push_back(0);

for (int i=1; i<1000; i++){
   expect = &a[i-1] + 1;
   a.push_back(0);
   real = &a[i];
   if (expect != real) printf("Reallocated at %d\n", i);
}

expect 是下一個 push_back 後預計的 address, 照理說如果 reallocate 了的話 real 和 expect 便應該不一樣
run 得到以下 output:

Reallocated at 1
Reallocated at 2
Reallocated at 4
Reallocated at 8
Reallocated at 16
Reallocated at 32
Reallocated at 64
Reallocated at 128
Reallocated at 256
Reallocated at 512

即是說, 每次 push_back 空間不足, 便會resize 成自身長度 2 倍的空間
假設 resize 的時間是線性, push_back N 次後的時間 = O(N) + O(N/2) + O(N/4) + ... = O(2N) = O(N)
所以 vector 的 push_back 平攤後是 O(1)