假设我在'i'位置插入p个新元素std::vector<mytype>,大小为'n'.
由于物品std::vector保证为其元素使用连续的存储位置,看起来我需要4步才能完成上述操作:
1)如果我们空间不足,可能会重新分配矢量,基本上会使其大小加倍.但这是一个恒定的时间操作(尽管是一个非常大的操作).
2)接下来是从旧向量到新向量的索引0到i-1的元素的memcpy.
3)然后复制在第i个索引处插入的'p'个新项目.
4)然后另一个memcpy用于从旧向量到新向量的i + 1到n索引的所有项目.
是不是所有上述恒定时间操作？那么不应该插入自己的恒定时间操作？那么为什么std::vector::insert插入的元素数量(复制/移动结构)加上位置(移动)后的元素数量是线性的？