CODEWITHSUNDEEP
c++vectorerasec++03
sharptooth
sharptooth

Reputation: 170489

Does std::vector::erase() invalidate the iterator at the point of erase?

C++03 Standard § 23.2.4.3/3 describes std::vector::erase(iterator position) and says specifically

Invalidates all the iterators and references after the point of the erase.

Is the iterator at the point of the erase not invalidated? Specifically if I have a vector with a single element and I copy begin() iterator into a local variable and then call

vec.erase(vec.begin())

Will that iterator I have in a local variable get invalidated or not?

Will the iterators be invalidated after the point of erasure or after and including the point of erasure?

Upvotes: 7

Views: 539

Answers (2)

Robin Hsu
Robin Hsu

Reputation: 4484

The complexity of vector::erase() says: Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving).

It seems to me that it is implemented as a lazy grow/shrink array. The iterator, a pointer to the data, when erased, the following data will copied into its place. And thus the iterator you keep, will point to some data else, provided that the data you erase is not the last one.

In fact, it may depend on implementation. Yet I think a lazy grow/shrink array is the best-fit implementation for vector::erase(). [Since it may depends on implementation, don't count on anything like invalidate...]

Upvotes: 0

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171117

I'd say that your example with erasing the only element in the vector shows that the iterator at the insertion point must be invalidated.

Anyway, in C++11, the wording has been changed (23.3.6.5/3):

Effects: Invalidates iterators and references at or after the point of the erase.

Upvotes: 8

Related Questions