c++ - std::vector iterator invalidation

Question

There have been a few questions regarding this issue before; my understanding is that calling std::vector::erase will only invalidate iterators which are at a position after the erased element. However, after erasing an element, is the iterator at that position still valid (provided, of course, that it doesn't point to end() after the erase)?

My understanding of how a vector would be implemented seems to suggest that the iterator is definitely usable, but I'm not entirely sure if it could lead to undefined behavior.

As an example of what I'm talking about, the following code removes all odd integers from a vector. Does this code cause undefined behavior?

typedef std::vector<int> vectype;
vectype vec;

for (int i = 0; i < 100; ++i) vec.push_back(i);

vectype::iterator it = vec.begin();
while (it != vec.end()) {
    if (*it % 2 == 1) vec.erase(it);
    else ++it;
}

The code runs fine on my machine, but that doesn't convince me that it's valid.

Answer 1

after erasing an element, is the iterator at that position still valid

No; all of the iterators at or after the iterator(s) passed to erase are invalidated.

However, erase returns a new iterator that points to the element immediately after the element(s) that were erased (or to the end if there is no such element). You can use this iterator to resume iteration.

---

Note that this particular method of removing odd elements is quite inefficient: each time you remove an element, all of the elements after it have to be moved one position to the left in the vector (this is O(n²)). You can accomplish this task much more efficiently using the erase-remove idiom (O(n)). You can create an is_odd predicate:

bool is_odd(int x) { return (x % 2) == 1; }

Then this can be passed to remove_if:

vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd), vec.end());