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