## **Do `std::vector::erase`-returned iterators Point to Valid Elements After Removal?**

Invalidation of std::vector Iterators: A Detailed Explanation

The concept of iterator invalidation in std::vector has been frequently discussed. To clarify, the erasure of vector elements via std::vector::erase invalidates iterators positioned strictly after the erased element.

However, the validity of the iterator at the exact position of the erased element remains uncertain. Logically, one might assume this iterator remains valid since the vector's underlying implementation usually shifts remaining elements to fill the empty space. However, the precise behavior and potential for undefined outcomes are less certain.

Consider the following example, which illustrates the removal of 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>

While this code appears to execute without errors in practice, its validity remains debatable.

The answer lies in the behavior of erase: it does indeed invalidate all iterators at or after the iterator(s) passed to erase. However, it also returns a new iterator指向的元素immediately after the erased element(s) or to the end if such an element does not exist. This iterator can be used to resume iteration.

It's important to note that the above method of odd integer removal is inefficient (O(n²)) because each erasure requires a shift of all subsequent elements. The erase-remove idiom offers a far more efficient solution (O(n)):

<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 ## **Do `std::vector::erase`-returned iterators Point to Valid Elements After Removal?**. For more information, please follow other related articles on the PHP Chinese website!