Safely Erasing Elements from std::vector During Iteration: From Erase-Remove Idiom to C++20 Features

Iterator Invalidation Problem Analysis

In the C++ Standard Library, std::vector is a dynamic array container that supports random access and dynamic resizing. When using the erase method to remove elements, all iterators, pointers, and references to elements after the erased position become invalid. The original code's issue lies in using a fixed endIter within a for loop, while erase operations modify the container's end() iterator, leading to iterator invalidation and undefined behavior.

Detailed Explanation of Erase-Remove Idiom

Prior to C++20, the standard approach for removing all matching elements from std::vector was the erase-remove idiom. This method operates in two phases: first, the std::remove or std::remove_if algorithm relocates elements that should not be deleted to the front of the container; then, the erase method removes the leftover elements at the end.

The std::remove algorithm works by traversing the container and shifting elements not equal to the specified value to the beginning positions. It returns an iterator pointing to the first element that should be erased. Below is a complete example:

void eraseElements(std::vector<int>& vec, int value) {
    // Using erase-remove idiom
    vec.erase(std::remove(vec.begin(), vec.end(), value), vec.end());
}

// Usage example
int main() {
    std::vector<int> numbers = {1, 2, 3, 2, 4, 2, 5};
    eraseElements(numbers, 2);
    // numbers now contains: {1, 3, 4, 5}
    return 0;
}

For more complex removal criteria, std::remove_if can be used with a predicate function:

void eraseIf(std::vector<int>& vec, int threshold) {
    vec.erase(std::remove_if(vec.begin(), vec.end(), 
        [threshold](int x) { return x > threshold; }), 
        vec.end());
}

Improvements in C++11 and Later Versions

C++11's introduction of lambda expressions significantly simplified the use of std::remove_if, eliminating the need for separate functor classes. While C++11 also introduced range-based for loops, caution is still required regarding iterator invalidation when erasing elements.

A common error pattern is attempting to call erase directly within a range-based for loop:

// Incorrect example: iterator invalidation
for (auto& item : vec) {
    if (item == value) {
        vec.erase(&item); // Dangerous! Iterator invalidated
    }
}

C++20 New Features

C++20 introduced the free functions std::erase and std::erase_if, providing a more concise interface for containers. These functions internally implement the erase-remove idiom but expose a more intuitive API.

// C++20 approach
#include <vector>
#include <algorithm>

void modernErase(std::vector<int>& vec, int value) {
    // Erase all elements equal to value
    std::erase(vec, value);
    
    // Or conditional erasure
    std::erase_if(vec, [value](int x) { return x % value == 0; });
}

The advantages of these new functions include cleaner code, clearer intent, and compatibility with all standard containers, including std::list, std::deque, etc.

Performance Analysis and Comparison

All discussed methods have O(n) time complexity, where n is the number of elements in the container. The erase-remove idiom and C++20's new functions are performance-equivalent, both requiring only a single pass to relocate and erase elements.

In contrast, the approach using a while loop with erase returning an iterator (as shown in Answer 2), while functionally correct, may cause element shifting with each deletion, resulting in worst-case O(n²) time complexity.

// Suboptimal approach: each erase may cause element shifting
void iterativeErase(std::vector<int>& vec, int value) {
    auto it = vec.begin();
    while (it != vec.end()) {
        if (*it == value) {
            it = vec.erase(it); // erase returns next valid iterator
        } else {
            ++it;
        }
    }
}

Best Practice Recommendations

Based on different C++ standard versions, the following best practices are recommended:

1. C++20 and later: Prefer std::erase and std::erase_if free functions for the most concise code.
2. C++11/C++14/C++17: Use the erase-remove idiom with lambda expressions for improved readability.
3. C++98/C++03: Use the erase-remove idiom, possibly requiring functor class definitions as predicates.
4. Special cases: When additional logic needs to be executed based on erasure results, consider using the while loop approach with iterator returns from erase.

Regardless of the chosen method, it is crucial to respect iterator invalidation rules and ensure that invalidated iterators are not used after container modifications.