How to Safely Erase Elements From a std::vector During Iteration?

Erasing Elements from a std::vector During Iteration: Strategies and Performance

When iterating through a std::vector while needing to erase elements based on a condition, the traditional approach using a for loop with iterators can encounter issues. Erasing an element invalidates the iterator, making the loop incomplete. To address this challenge, let's explore optimal strategies for handling such scenarios.

Iterating with Invalidation Tracking

One approach is to explicitly track the iterator invalidation caused by erasing elements. In the provided sample code:

<code class="cpp">for (iterator it = begin; it != end(container) /* !!! */; )
{
    if (it->somecondition())
    {
        it = vec.erase(it); // Returns the new iterator to continue from.
    }
    else
    {
        ++it;
    }
}</code>

The key difference here is the use of end(container) instead of a precalculated end, which updates the iterator reference after each erase operation. This ensures valid iterator comparisons during the loop.

Combining std::remove_if and erase

A more efficient approach involves combining the std::remove_if and erase functions. This optimizes the process by removing the need for invalidation tracking:

<code class="cpp">iterator it = std::remove_if(begin, end, pred);
vec.erase(it, vec.end());</code>

Here, pred represents a removal predicate that determines which elements to remove. This approach eliminates the O(N^2) complexity associated with iterated erasing and improves performance to O(N).

Example Applications

In the provided code sample, the RemoveTimedEvent struct serves as the removal predicate to identify and remove events associated with a specific widget in a vector of timed events.

By leveraging one of these strategies, you can effectively erase elements from a std::vector during iteration while maintaining correct iterator functionality and performance.

The above is the detailed content of How to Safely Erase Elements From a std::vector During Iteration?. For more information, please follow other related articles on the PHP Chinese website!