C++ Erase Function Comprehensive Guide

Introduction

The erase function is a fundamental operation in C++ containers that removes elements. This guide covers its various forms, common idioms, and best practices across different container types.

Basic Syntax and Container-Specific Behavior

Vector and Sequence Containers

Sequence containers like vector provide two basic forms of erase:

iterator erase(iterator position);                  // Single element
iterator erase(iterator first, iterator last);      // Range of elements

After erasure, all elements after the erased position(s) are moved forward, and the container size is reduced accordingly. The function returns an iterator to the element following the last removed element.

String Special Case

std::string offers an additional overload optimized for string operations:

string& erase(size_type pos = 0, size_type len = npos);

This form is particularly useful for string manipulation as it operates directly with character positions and lengths rather than iterators.

Associative Containers (map/set)

Associative containers provide three overloads:

iterator erase(iterator position);                  // Single element
iterator erase(iterator first, iterator last);      // Range of elements
size_type erase(const key_type& key);              // Key-based removal

Unlike sequence containers, erasing elements from associative containers doesn't require shifting elements, making these operations more efficient.

The Erase-Remove Idiom

The Erase-Remove idiom is a powerful technique for removing elements that satisfy specific criteria. It combines erase with algorithms like remove or remove_if:

// Remove all occurrences of value 2
vec.erase(remove(vec.begin(), vec.end(), 2), vec.end());
 
// Remove all even numbers
vec.erase(
    remove_if(vec.begin(), vec.end(), 
             [](int x) { return x % 2 == 0; }),
    vec.end()
);

How It Works

1. remove or remove_if moves elements to be kept to the front of the container
2. Returns an iterator to the new logical end
3. erase then removes the unwanted elements from this position to the end

Modern C++ (C++20) Improvements

C++20 introduced global erase and erase_if functions that simplify common erasure patterns:

template<class C, class T>
void erase(C& c, const T& value);
 
template<class C, class Pred>
void erase_if(C& c, Pred pred);

These functions provide a more uniform interface across all container types:

vector<int> vec = {1, 2, 3, 2, 4, 2, 5};
erase(vec, 2);                    // Removes all 2s
erase_if(vec, [](int x) {        // Removes all even numbers
    return x % 2 == 0;
});

Iterator Invalidation and Best Practices

Iterator Invalidation Rules

• Vector: Erasing invalidates iterators at and after the point of erasure
• List: Only iterators pointing to erased elements are invalidated
• Map/Set: Only iterators to erased elements are invalidated

Safe Erasure in Loops

Incorrect way:

for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (should_erase(*it)) {
        vec.erase(it);    // Iterator invalidation!
    }
}

Correct way:

for (auto it = vec.begin(); it != vec.end();) {
    if (should_erase(*it)) {
        it = vec.erase(it);
    } else {
        ++it;
    }
}

Performance Considerations

• Vector: Erasing from the end is O(1), from the beginning or middle is O(n)
• List: Erasing is always O(1), but finding elements is O(n)
• Map/Set: Erasing is O(log n)
• Unordered Map/Set: Erasing is O(1) average case

Best Practices

1. Use the Erase-Remove idiom for sequence containers when removing multiple elements
2. Consider using C++20's global erase/erase_if for cleaner code
3. Be careful with iterator invalidation in loops
4. Choose the appropriate container based on your erasure patterns
5. For strings, use the position-based overload when possible
6. When dealing with associative containers, prefer key-based erasure when applicable

Conclusion

Understanding the various forms of erase and their proper usage is crucial for writing efficient C++ code. The choice of container type and erasure method can significantly impact both code clarity and performance. Modern C++ continues to evolve, providing more convenient and safer ways to perform element removal operations.