vector 是 cpp 中常用的一种容器，是一种可以动态扩容的数组。他在每次插入的时候，当它的 capacity 不满足要求的时候，会重新申请一块两倍的内存，把之前的内容复制过来。在这种情况下，复制的时间复杂度为 $O(n)$。如果不涉及扩容，那么它只修改一个元素的内存，时间复杂度为 $O(1)$。
也就是说，它扩容的时机为，容器大小达到以下时：
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 …
则每次插入代价设为 $c_i$，则
$$
c_i = \begin{cases}
i & i 为 2 的幂\
1 & others \
\end{cases}
$$
那么则有：
$$
\begin{aligned}
\sum_{i = 0}^nc_i &\le n + \sum_{j = 0}^{\lfloor log_2n \rfloor}2^j \
&\le n + 2n\
&\le 3n
\end{aligned}
$$
因为共有 $n$ 次插入，所以总时间复杂度为 $O(3n)$，均摊下来平均时间复杂度为 $O(3)$。