插入到STL向量中

Question

使用C++ STL向量，我們正在構建N個元素的向量，並且由於我們選擇將它們插入到向量的前面，所以有一些原因。 （1 + 2 + 3 + ... + N）向量元素的總體偏移量爲（N/2）（N +1）輪班。我認爲它應該是1 + 1 + 1 ... N，因爲我們在一個位置移動一個元素以獲得空的開始時？

謝謝！

Answer 1

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

複雜性：複雜性是在插入元件的數量加至該載體的端部的距離是線性的。

每次添加元素時，距離矢量的距離都增加1。

第一次添加元素時，插入1，到末尾的距離爲0，因此複雜度爲1 + 0 = 1。第二次插入1，並且到最後的距離是1，所以複雜度是1 + 1 = 2。第三次到末端的距離是2，所以複雜度是1 + 2 = 3。這就是創建1 + 2 + 3的原因作者正在描述的+ ... + N模式。

Answer 2

第一個值被移位N-1次，每次插入一個新值時它必須移動。第二個值被移位N-2次，因爲在它之後只添加了N-2個值。下一個值被移位N-3等等。最後的值不會被移位。

我不知道作者爲什麼談論N而不是N-1。但是你的困惑的原因是，作者計算單個值的轉換，並且你計算涉及多個單值轉換的轉換試驗的數量。

Answer 3

在插入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); 
}