Time complexity of removing items in vectors and deque

19
votes

I have read that time complexity of adding items to end of a std::vector is amortized constant and inserting items at the top and bottom of a std::deque is constant.Since both these containers have a random access iterator thus accessing elements at any index is constant. Please let me know if I have any of these facts wrong.My question is if accessing an element in a std::vector or std::deque is constant then why is the time complexity of removing an element via erase O(n). One of the answers here here states that removing elements via erase is O(n). I know that erase removes the elements between the starting iterators and the ending one so does the answer basically mean that its O(n) depending on the no of elements between the two iterators and that removing a single element from a vector/deque in any index will be zero?

4
c++vectordequec++98
deque::erase should be faster than vector::erase (for an average element), since it only needs to re-shuffle the elements in the block affected, but not in the whole of the vector. – Walter
@Walter: Are you sure about this? – user541686
@Walter that's not exactly true, see my answer and a demo – Anton Savin
@Mehrdad no I'm not sure, just a thought based on what I would implement (and assuming only one element is erased). In fact, if erasing without preserving the order of the remaining elements were possible/allowed, this could be done in constant time! Why does the standard not support this explicitly? (you can implement this simply by first swapping the last element with the one to be erased, then erase the last, but that may be slower, since swapping is potentially more expensive than a single move.) – Walter
@Walter: Well I'm pretty sure it's wrong because otherwise finding the distance between two iterators wouldn't take constant time. – user541686

4 Answers

10
votes

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).

6
votes

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).

5
votes

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.

0
votes

by using this way time complexity = range length + shifting length(n - range end)

    vector<int> it = (vector<int>::iterator) &vec[pos];
    vec.erase(it, it+length);