Erase-Remove

Overview

STL algorithms operate on iterators, not containers. std::remove and std::remove_if cannot call container.erase() — they only rearrange elements within an iterator range. The result is a logically shortened sequence: elements that survive the removal criterion are stable-moved toward the front, a graveyard region of unspecified values accumulates at the back, and a past-the-new-logical-end iterator is returned. The container's size() is unchanged.

The erase-remove idiom closes this gap by feeding that returned iterator directly into container.erase():

container.erase(std::remove(container.begin(), container.end(), value),
                container.end());

Both steps are O(n): std::remove makes one pass rearranging elements, and vector::erase shifts the tail and updates size. For sequence containers such as vector, deque, and string this is the asymptotically optimal approach.

C++20 introduced std::erase and std::erase_if as uniform free functions that encapsulate both steps. For new code targeting C++20 or later, prefer them. The classic idiom remains essential for reading and maintaining older codebases.

Syntax

// Remove all elements equal to value — C++98
container.erase(
    std::remove(container.begin(), container.end(), value),
    container.end()
);

// Remove all elements satisfying a predicate — C++98
container.erase(
    std::remove_if(container.begin(), container.end(), predicate),
    container.end()
);

// C++20: uniform free functions — same semantics, returns count erased
std::size_t n1 = std::erase(container, value);     // C++20
std::size_t n2 = std::erase_if(container, pred);   // C++20

std::remove requires elements to be EqualityComparable against value. std::remove_if accepts any unary predicate returning a contextually-boolean type. Both live in <algorithm>. The C++20 free functions are declared in each container's own header (<vector>, <list>, <string>, etc.).

Examples

Removing a specific value from a vector

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v{1, 3, 2, 3, 4, 3, 5};

    v.erase(std::remove(v.begin(), v.end(), 3), v.end());
    // v == {1, 2, 4, 5}
}

Removing with a predicate

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8};

    v.erase(
        std::remove_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; }),
        v.end()
    );
    // v == {1, 3, 5, 7}
}

C++20 uniform erasure

std::erase and std::erase_if (C++20) implement the idiom internally and are specialised for every standard container — including associative and unordered containers, where std::remove cannot be used at all.

#include <vector>   // provides std::erase / std::erase_if overloads — C++20

int main() {
    std::vector<int> v{1, 2, 3, 4, 5, 6};

    auto removed = std::erase(v, 3);             // C++20 — removed == 1
    std::erase_if(v, [](int x) {                 // C++20
        return x % 2 == 0;
    });
    // v == {1, 5}
}

Cleaning a string

The idiom applies identically to std::basic_string, which models a sequence container:

#include <algorithm>
#include <cctype>
#include <string>

std::string strip_digits(std::string s) {
    s.erase(
        std::remove_if(s.begin(), s.end(),
                       [](unsigned char c) { return std::isdigit(c); }),
        s.end()
    );
    return s;
}

The lambda takes unsigned char rather than char. Passing a negative char value to std::isdigit is undefined behaviour; casting through unsigned char is the correct idiom for character classification.

std::list and std::forward_list — prefer member functions

std::remove is a valid algorithm on bidirectional iterators, so it compiles for std::list. However, it moves elements, which is wasteful when pointer relinking is all that is needed. Both list and forward_list expose member functions remove and remove_if that splice out nodes in O(n) with zero element copies or moves:

#include <list>

int main() {
    std::list<int> lst{1, 3, 2, 3, 4, 3};

    lst.remove(3);                                         // preferred — O(n), no moves
    lst.remove_if([](int x) { return x % 2 == 0; });      // ditto
}

Applying the erase-remove idiom to list is correct but needlessly expensive. For these containers, always prefer the member functions.

Best Practices

Prefer std::erase / std::erase_if (C++20) for all new code. They eliminate the risk of mispairing iterators, communicate intent clearly, and are consistently optimised per container type. The return value — the count of erased elements — is often useful for logging or conditional logic.

Encapsulate the classic idiom in a helper for pre-C++20 codebases. This avoids repetition and prevents the single most common mistake (omitting erase):

// Only needed when targeting pre-C++20
template<typename Container, typename T>
void erase_value(Container& c, const T& value) {
    c.erase(std::remove(c.begin(), c.end(), value), c.end());
}

template<typename Container, typename Pred>
void erase_if(Container& c, Pred pred) {
    c.erase(std::remove_if(c.begin(), c.end(), std::move(pred)), c.end());
}

Consider std::partition when element order of survivors is irrelevant. std::remove is a stable algorithm. std::partition is unstable but may generate fewer writes in practice, since it swaps rather than moves unidirectionally. Neither avoids the subsequent erase call.

For bulk removal from a vector, evaluate whether rebuilding is cheaper. If you are removing more than roughly half the elements, copying survivors to a new vector via std::copy_if can be faster than repeated shifting, because the copy avoids write-backs into cache lines being constantly invalidated.

Common Pitfalls

Forgetting the erase call

std::vector<int> v{1, 2, 3, 4};
std::remove(v.begin(), v.end(), 2); // BUG: returns iterator, does nothing visible
// v.size() is still 4; the "removed" value may still be readable at the back

This is the single most common mistake. std::remove returns the new logical end but leaves the container size unchanged. The elements in [returned_it, v.end()) have unspecified values — in practice they often retain their original values, which makes this bug easy to miss during testing.

Iterator invalidation after erase

vector::erase invalidates all iterators at or after the erased range. Code that holds iterators into a vector and then calls erase has undefined behaviour if those iterators are subsequently used:

auto pos = v.begin() + 2;
v.erase(std::remove(v.begin(), v.end(), 0), v.end());
// pos is now potentially invalid — do not dereference or compare

Recompute iterators after any erase call.

Applying std::remove to associative containers

std::map, std::set, and their unordered variants have const keys. std::remove requires move-assignability of the value type, which these containers do not satisfy for their key component. The code will not compile. Use the container's .erase(key) or, for predicate-based removal, std::erase_if (C++20):

#include <unordered_map>  // std::erase_if overload — C++20

std::unordered_map<int, std::string> m{{1,"a"},{2,"b"},{3,"c"}};
std::erase_if(m, [](const auto& kv) { return kv.second == "b"; }); // C++20

Stateful or side-effectful predicates

The standard does not guarantee that std::remove_if calls the predicate exactly once per element. A predicate that counts invocations, modifies external state, or produces side effects may behave unpredictably. Predicates must be pure functions of their argument.

See Also

• std::remove, std::remove_if — <algorithm>
• std::erase, std::erase_if — C++20; overloads in each container header
• std::partition, std::stable_partition — rearrangement without erasure
• std::list::remove, std::list::remove_if — O(n) pointer-relinking alternatives for linked lists
• std::copy_if — extract survivors into a new container rather than mutating in place