简单分析如下：
考虑vector每次内存扩充两倍的情况。
如果我们插入N个元素， 则会引发lgN次的内存扩充，而每次扩充引起的元素拷贝次数为
2^0, 2^1, 2^2, …, 2^lgN.
把所有的拷贝次数相加得到
2^0 + 2^1 + 2^2 + … + 2^lgN = 2 * 2^lgN – 1 约为 2N次
共拷贝了N次最后一个元素， 所以总的操作大概为3N
所以， 每个push_back操作分摊3次， 是O(1) 的复杂度。
map insert
复杂度
如果插入单个元素且无暗示，时间复杂度为
O(logn)
，其中
n
为容器的
大小
。
如果插入单个元素且有最优位置（Position）暗示，时间复杂度为
O(1)
，这是一个平均分摊后的常值（Amortized constant）。
如果插入多个元素，时间复杂度为
O(nlogn)
，“第一个”
n
为插入元素数，“第二个”
n
为插入元素数加容器大小。如果插入的范围中的元素已经按同样的排序规则排序，执行过程将被优化，时间复杂度甚至会降到
O(n)
。
迭代器有效性
不会改变。