假设我在'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插入的元素数量(复制/移动结构)加上位置(移动)后的元素数量是线性的？
是不是所有上述恒定时间操作？
不,时间复杂度memcpy和memmove被复制或移动的块的大小是线性的,因为每个k被移动的字节需要被触摸一次.正在移动的块的大小也sizeof(T) * N使得时序也是线性的.
即使在向量的末尾添加N元素也具有线性复杂性,因为在重新分配时复制数据(然而,向量的末尾添加元素具有分摊的线性复杂度,这转化为按项目的复杂性分摊的常量).
| 归档时间： |
|
| 查看次数： |
12888 次 |
| 最近记录： |