vector是如何增长的：

为了支持快速随机访问，vector是连续存储的。

当添加一个新元素时，如果没有空间容纳新元素，为了保持连续存储，容器必须分配新的内存空间保存已有元素和新元素。

转移流程：申请新空间，转移元素，释放旧空间。

为了避免每次添加元素都需要转移一次空间，当需要扩容时，vector会申请一个比需求更大的内存空间，即预留一部分空间作为备用。

push_back复杂度分析：

push_back均摊后的时间复杂度为O(1)。

vector只有当达到capacity之后才会扩容。

设倍增因子为m，即达到容量上限后，新空间容量翻m倍。

现在假设要往vector丢入n个元素，

假设要扩容k次，那么有：
$1+m+m^2+m^3...+m^k>=n$
根据等比数列前n项和公式，式子可以化简为：
$m^k-1>=n\ast (m-1)$
$k=lo{g}_{m}n\ast (m-1)=lo{g}_{m}n+lo{g}_m(m-1)\approx lo{g}_{m}n$
即将会进行$lo{g}_{m}n次扩容操作$

k次扩容过程中，复制数据需要的操作次数大概为：
${\sum }_{i=1}^k{m}^i=\frac{m\ast (m^k-1)}{m-1}=\frac{m\ast (m^{lo{g}_{m}n}-1)}{m-1}=\frac{m\ast (n-1)}{m-1}$
均摊给n次push_back，那么：
$\frac{m\ast (n-1)}{m-1}/n<\frac{m}{m-1}$

$\frac{m}{m-1}$是常数级别的。

复制部分均摊O(1)，单个元素新增O(1)，因此均摊后的总复杂度为O(1)。