引導示例

#include <iostream>
#include <vector>int main() {std::vector<int> v;std::cout << v.capacity() << " ";int last = 0;for (int i = 1; i <= 10; i++) {v.push_back(1);std::cout << v.capacity() << " ";}return 0;
}

我們在C++17下運行上面的代碼，可以得到如下的結果：

0 1 2 4 4 8 8 8 8 16 16

初步觀察到，當進行push_back時，如果容器的大小達到容量，就會再開辟一個新的內存。

---

復雜度分析：

假設容量從 1 開始，逐步倍增到 2, 4, 8, …, 2^k；總共進行n次插入。

每次擴容的代價為：

總的擴容代價：(求和公式)

加上n次插入：
總的代價為 (3n-1) / n = O(3) = O(1)