为什么std :: vector :: insert复杂度是线性的（而不是常量）？ [英] Why is std::vector::insert complexity linear (instead of being constant)?

问题描述

假设我在大小为'n'的 std :: vector< mytype> 中的第i个位置插入了p个新元素。

Lets say I was inserting p new elements at the 'i' th position in an std::vector<mytype> of size 'n'.

由于 std :: vector 中的项目被保证为其元素使用连续的存储位置，所以看起来像这将需要我4执行上述操作的步骤：

Since items in std::vector are guaranteed to use contiguous storage locations for their elements, it seems like this would take me 4 steps to do the above:

1）如果我们的空间不足，可能重新分配向量，基本上使其大小加倍。但是这是一个常数时间运算（尽管是一个非常大的运算）。

1) Possible reallocation of the vector if we are out of space, basically doubling its size. But that is a constant time operation (albeit a very large one).

2）接下来有一个memcpy元素从索引0到i-1从旧向量

2) Next there is a memcpy of elements from index 0 through i-1 from the old vector into the new one.

3）然后你复制'p'个新项目插入第i个索引。

3) Then you copy 'p' new items being inserted at ith index.

4）然后对于从旧向量到新向量的从i + 1到n的所有项目的另一个memcpy。

4) Then another memcpy for all items from i+1 through n indexes from the old vector to the new vector.

不是所有上述常量时间操作？那么应该不应该插入本身是否是一个常量时间运算？为什么 std :: vector :: insert linear对插入的元素数量（复制/移动结构）加上位置（移动）后的元素数量？

Aren't all the above constant time operations? Then shouldn't insertion itself be a constant time operation? Why then is std::vector::insert linear on the number of elements inserted (copy/move construction) plus the number of elements after position (moving)?

推荐答案

不是所有上述常量时间操作吗？

Aren't all the above constant time operations?

不， memcpy 和 memmove 的时间复杂度是线性的因为正在移动的 k 字节中的每一个都需要被精确地触摸一次，所以块被复制或移动的大小。正在移动的块的大小为 sizeof（T）* N ，这使得时序也是线性的。

No, the time complexity of memcpy and memmove is linear in the size of the block being copied or moved, because each of the k bytes being moved needs to be touched exactly once. The size of the block being moved is sizeof(T) * N, making the timing linear as well.

在向量的末尾处的元素的甚至添加具有线性复杂性，因为在重新分配时复制数据（然而，向向量的末尾添加 N 元素线性复杂性，这意味着摊销的常量项目复杂性）。

Even addition of an element at the end of a vector has linear complexity because of copying data on reallocation (however, adding N elements to the end of a vector has amortized linear complexity, which translates to amortized constant per-item complexity).

这篇关于为什么std :: vector :: insert复杂度是线性的（而不是常量）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！