c++ - 插入 STL 向量

Question

使用 C++ STL 向量，我们正在构建一个包含 N 个元素的向量，出于某种原因，我们选择将它们插入向量的前面。向量前面的每个元素插入都会强制所有现有元素移位 1。这导致向量元素的 (1+2+3+...+N) 整体移位，即 (N/2)(N +1) 轮班。

我的问题是作者是如何获得 (1+2+3+...N) 的，我认为它应该是 1+1+1..N，因为我们将一个元素移动到一个位置以在一开始就变空？

谢谢！

Answer 1

从[vector.modifiers]/2（描述vector::insert）：

复杂度：复杂度与插入的元素数量加上到向量末端的距离成线性关系。

每次添加元素时，到向量末端的距离都会增加 1。

第一次添加元素，有1个要插入，到末尾的距离为0，所以复杂度是1+0=1。第二次，有1个要插入，到末尾的距离end 是 1，所以复杂度是 1 + 1 = 2。第三次，到 end 的距离是 2，所以复杂度是 1 + 2 = 3。这就是创建 1 + 2 + 3 + ... + 作者描述的 N 模式。

Answer 2

在插入n时，n向量中当前存在需要移动的元素。

vector<int> values;
for (size_t i = 0; i < N; ++i)
{
     //At this point there are `i` elements in the vector that need to be moved
     //to make room for the new element
     values.insert(values.begin(), 0); 
}

Answer 3

第一个值被移动 N-1 次，每次插入新值时它都必须移动。第二个值移动了 N-2 次，因为在它之后只添加了 N-2 个值。下一个值被移动 N-3 等等。最后一个值不会移动。

我不知道为什么作者说的是 N 而不是 N-1。但是您感到困惑的原因是，作者计算了单个值的移位，而您计算了涉及多个单个值移位的移位过程的数量。