std::vector 的成長模型（the std::vector growth model）

std::vector 是 C++ 的可成長陣列：它把元素存在單一連續的記憶體區塊裡，像 C 陣列一樣，但它能隨著你加入元素而成長。這引出一個明顯的謎題：連續記憶體有固定大小，那它怎麼成長？答案是當它空間用盡時，它悄悄配置一個更大的區塊、把既有元素搬過去、再釋放舊的——而巧妙之處在於它多久做一次，因為每次插入都做的話會慢得不堪設想。

兩個量很重要：大小（size，你有多少元素）與容量（capacity，在必須重新配置前它有空間容納多少）。當你對一個已滿的 vector 做 push_back 時，它不是成長一個——它以乘法因子成長容量（常見是加倍，有時是 1.5 倍），配置那個更大的緩衝區，把元素搬移或複製過去，再釋放舊緩衝區。因為緩衝區大小以幾何級數成長，隨著 vector 變大，昂貴的重新配置以指數方式越來越少發生，所以 n 次 push_back 的總成本與 n 成正比，而非 n 平方。我們說每次 push_back 是攤銷常數時間（amortized constant time）：多數只是寫進備用容量的廉價操作，而偶爾的重新配置平均下來每個元素只增加一個常數。

為何重要：連續性使 std::vector 對快取友善，迭代起來和裸陣列一樣快，而幾何成長使附加在平均上廉價——它之所以是預設容器是有道理的。這個模型誠實的後果很重要：一次重新配置會使指向 vector 的所有指標、參考與迭代器失效（它們指向舊的、已釋放的緩衝區），所以跨越 push_back 持有參考是個臭蟲；攤銷常數成本隱藏了偶爾的大幅最壞情況尖峰（某一次 push_back 可能搬移一百萬個元素），這對即時程式碼很重要；而當你知道大小時，你可以預先呼叫 reserve(n) 完全避免那些重新配置，把多次配置變成一次。