Is erase() in std::vector linear time operation?

问题:

Page http://www.cplusplus.com/reference/vector/vector/erase/ says

Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving).

So, if I am deleting an element, say, with index j from vector of some length n (n>j) - will it be constant or linear(O(n))?

Or, if I have p elements after Jth element, then it will be of order O(p) - am I right?

回答1:

From the link you provided:

Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving)

This means that when deleting N=1 elements from the std::vector. It will take make N call to the destructor which is equal to 1 in your case. Then it will make M move operation which is equal to (n-j-1) in your case. So it is linear not a constant.

So the complixity of std::vector::erase is: O(Deleted_Items_Count) + O(Moved_Items_Count).

In your case: 1*Destructor_Time + (n-j-1)*Moving_Time

---

In order to erase items from vector in constant time,you may erase them from the tail of the vector(e.g. std::vector::pop_back)

So if you want a constant time erasing with no importance of sorting:

auto linear_erase=[](auto& v, const size_t index){
    std::swap(v[index], v.back());
    v.pop_back();
};

回答2:

Deleting N elements from a vector will take a time complexity of O(N), because the application has to iterate over M elements, and call each element's destructor, then copy the rest of the elements to the gap created by destroying the erased elements.

So if we have a vector with N elements, and we erase the elements from the range (p,q] , than destroying the the range will take O(q-p) time complexity, which you can say is O(1), because p and q are constants. then you will have to copy/move the range (q,N] . since N-q is linear, the time complexity is O(N).

together we get O(N) + O(1) = O(N)

of course, if you delete a range that ends in the end of the array, the Complexity is O(1) because there are no elements to copy/move.

回答3:

I learned here on SO that the standard is the best reference.

From 23.3.11.1/1 [vector.overview]:

A vector is a sequence container that supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time.

So, in this case erase is neither constant nor linear time.
It mostly depends on the kind of operation you are performing:

• It's constant if you are erasing at the end of the vector,
• Otherwise it's linear.