## Is the Iterator at the Erased Position in std::vector::erase() Still Valid?

Understanding Iterator Invalidation in std::vector::erase()

In this discussion, we delve into the topic of iterator invalidation when invoking std::vector::erase(). As known from previous debates, it is established that erasing an element from a vector invalidates iterators located after the erased element. However, a question arises: is the iterator positioned at the erased element still considered valid?

Despite our intuitive understanding that the iterator at the erased position should remain usable, the precise behavior is not always clear. To illustrate this concept, let's analyze the following code snippet that removes all odd integers from a vector:

<code class="cpp">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;
}</code>

Although this code executes successfully, it violates best practices. According to the C standard, erase() invalidates all iterators at or after the iterator(s) provided as parameters. In this case, it means the iterator at the erased position becomes invalid.

However, erase() conveniently returns a new iterator that points to the element immediately following the erased element(s), or to vec.end() if no such element exists. This new iterator can be utilized to resume iteration safely.

It is important to note that the aforementioned method of removing odd elements is not efficient. Each time an element is deleted, subsequent elements must be shifted to the left in the vector, resulting in O(n²) complexity. This task can be accomplished more efficiently using the erase-remove idiom, which operates in O(n). By creating a predicate like is_odd(), we can refine the erase operation:

<code class="cpp">bool is_odd(int x) { return (x % 2) == 1; }
vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd), vec.end());</code>

The above is the detailed content of ## Is the Iterator at the Erased Position in std::vector::erase() Still Valid?. For more information, please follow other related articles on the PHP Chinese website!