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

Question

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?

Answer 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();
};