Time complexity of removing items in vectors and deque

Erasing an element in a vector is O(n) since once you remove the element you still need to shift all successive elements to fill the gap created. If a vector has n elements, then at the worst case you will need to shift n-1 elemets, hence the complexity is O(n).

Removing elements is indeed O(n) not because of what you have to do to find the element to remove but because of what you have to do to all of the ones after it. Those elements need to be slid down to fill the empty slot.

So on average, erase will take an element about halfway through the vector, so you'll have to shift about half the elements. Hence O(n). Best case, you erase the last element - no sliding necessary. Worst case, you erase the first element - have to then move every other element.

The things are a bit different for std::vector and std::deque, as well as they are different for C++98 and C++11.

std::vector

The complexity of std::vector::erase() is linear both to the length of the range erased and to the number of elements between the end of the range and the end of the container (so erasing an element from the end takes constant time).

C++2003 [lib.vector.modifiers] reads:

iterator erase(iterator position);
iterator erase(iterator first, iterator last);`

...

Complexity: The destructor of T is called the number of times equal to the number of the elements erased, but the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

C++14 draft N4140 [vector.modifiers] reads:

Complexity: The destructor of T is called the number of times equal to the number of the elements erased, but the move assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

So you see that C++11/14 implementation is more efficient in general since it perform move assignment instead of copy assignment, but the complexity remains the same.

std::deque

The complexity of std::deque::erase() is linear both to the length of the range erased and to the minimum of two numbers: number of remaining elements before the start of the range, and number of remaining elements after the end of the range. So, erasing an element either from the beginning or from the end takes constant time.

C++2003 [lib.deque.modifiers]:

iterator erase(iterator position);
iterator erase(iterator first, iterator last);

Complexity: The number of calls to the destructor is the same as the number of elements erased, but the number of the calls to the assignment operator is at most equal to the minimum of the number of elements before the erased elements and the number of elements after the erased elements.

C++14 draft N4140 [deque.modifiers]/5:

Complexity: The number of calls to the destructor is the same as the number of elements erased, but the number of calls to the assignment operator is no more than the lesser of the number of elements before the erased elements and the number of elements after the erased elements.

So, it's the same in C++98 and C++11/14, again except that C++11 can choose between move assignment and copy assignment (here I see some inconsistency in the standard because the wording doesn't mention move assignment like for std::vector - might be a reason for another question).

Note also the "at most" and "no more" in the wordings. This allows for implementations to be more efficient than linear, though in practice they are linear (DEMO).