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.

Stability Guarantee

Both std::remove and std::remove_if are stable algorithms. The relative order of elements that are not removed is preserved exactly. This is confirmed by the standard: surviving elements are move-assigned toward the front in their original relative order, and the algorithm makes exactly N comparisons or predicate applications where N is the distance between the iterators.

Stability matters in practice when the surviving elements carry meaningful ordering or identity beyond the removal criterion — for example, removing duplicates by value while preserving the first occurrence of each distinct value, or removing entries from a log while retaining the chronological order of remaining entries.

Contrast this with std::partition and std::stable_partition:

• std::partition — unstable; survivors may be reordered (but may generate fewer writes)
• std::stable_partition — stable, same guarantee as std::remove, but more complex

std::ranges::remove and std::ranges::remove_if carry the same stability guarantee.

C++20: std::ranges::remove and std::ranges::remove_if

The Ranges library provides constrained versions of both algorithms in <algorithm>. The key difference from their classic counterparts is the return type: instead of a single past-the-new-end iterator, they return a ranges::subrange<I> representing the "tail" to be erased — the range [new_end, last).

#include <algorithm>
#include <vector>

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

    // ranges::remove returns subrange{new_end, last}
    auto tail = std::ranges::remove(v, 2);
    v.erase(tail.begin(), tail.end());
    // v == {1, 3, 4, 5}
}

Structured bindings work cleanly because the return is a two-iterator subrange:

auto [first, last] = std::ranges::remove_if(v, [](int x) {
    return x % 2 == 0;
});
v.erase(first, last);

A common mistake when migrating from classic to ranges is passing the subrange directly to vector::erase expecting it to accept an iterator. vector::erase takes either one iterator or two iterators — not a subrange. You must call .begin() on the returned subrange, or use structured bindings:

// WRONG — does not compile: erase does not accept a subrange
// v.erase(std::ranges::remove(v, 2), v.end());

// CORRECT — extract the begin iterator
auto r = std::ranges::remove(v, 2);
v.erase(r.begin(), r.end());

std::ranges::remove also supports projections, allowing removal by a computed key without modifying the predicate:

#include <algorithm>
#include <string>
#include <vector>

struct Entry {
    std::string name;
    int score;
};

int main() {
    std::vector<Entry> entries{
        {"alice", 0}, {"bob", 42}, {"carol", 0}
    };

    // Remove entries where score == 0, using projection
    auto tail = std::ranges::remove(entries, 0, &Entry::score);
    entries.erase(tail.begin(), tail.end());
    // entries == { {"bob", 42} }
}

C++20: std::erase and std::erase_if — Container-Specific Overloads

C++20 introduced uniform free functions that encapsulate the entire erase-remove idiom in a single call. Each standard container header declares its own overloads:

std::erase is only defined for sequence containers (the key is not modifiable in associative containers, so value-equality removal by element is not meaningful). std::erase_if covers all standard containers because the predicate can inspect any aspect of the element.

Both functions return a typename Container::size_type — the count of elements erased — which is useful for logging and conditional logic.

#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    // Sequence container — both overloads available
    std::vector<int> v{1, 2, 3, 2, 4};
    auto n1 = std::erase(v, 2);             // n1 == 2; v == {1, 3, 4}
    auto n2 = std::erase_if(v, [](int x) {
        return x > 2;
    });                                      // n2 == 1; v == {1, 3}

    // std::map — only std::erase_if available
    std::map<std::string, int> scores{
        {"alice", 80}, {"bob", 45}, {"carol", 90}
    };
    // Predicate receives const std::pair<const Key, Value>&
    std::erase_if(scores, [](const auto& kv) {
        return kv.second < 50;
    });
    // scores == { {"alice", 80}, {"carol", 90} }

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

For std::list and std::forward_list, the std::erase and std::erase_if overloads internally call the member remove / remove_if functions, so no element copies or moves occur — only pointer relinking. The C++20 free functions are therefore equally efficient on linked lists as the member functions.

Container-Specific Member Functions: std::list and std::forward_list

std::list and std::forward_list expose member functions remove and remove_if that physically erase nodes in a single O(n) pass by relinking pointers. No elements are moved or copied — only the prev/next pointers change. This contrasts with std::remove, which must move-assign elements within the buffer, followed by erase, which must then deallocate the tail.

#include <forward_list>
#include <list>

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

    auto removed1 = lst.remove(3);              // C++20: returns count erased
    // lst == {1, 2, 4}

    auto removed2 = lst.remove_if([](int x) {
        return x % 2 == 0;
    });
    // lst == {1}

    std::forward_list<int> flst{5, 1, 5, 2, 5};
    flst.remove(5);
    // flst == {1, 2}
}

Prior to C++20, list::remove and list::remove_if returned void. Since C++20 they return the count of removed elements, consistent with std::erase / std::erase_if.

The erase-remove idiom compiles for std::list (bidirectional iterators satisfy std::remove's requirements) but is wasteful — prefer the member functions or std::erase/std::erase_if for linked lists.

C++20 std::erase and std::erase_if: Return Value and Count Semantics

std::erase and std::erase_if return the number of elements removed, not an iterator. This makes them immediately useful for logging, assertions, and conditional branches without requiring a pre- or post-call size() snapshot.

// C++20
#include <vector>

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

    // Return value is std::vector<int>::size_type (usually std::size_t)
    std::size_t removed = std::erase(v, 4);
    // removed == 3; v == {1, 2, 3}

    std::size_t evens = std::erase_if(v, [](int x) { return x % 2 == 0; });
    // evens == 1; v == {1, 3}
}

The classic idiom provides no direct count — you must compute std::distance(new_end, old_end) before calling erase, or diff size() before and after. The C++20 functions remove this ceremony. Because each container header provides its own specialisation of std::erase / std::erase_if, the implementation is always optimal for that container — sequence containers use the erase-remove pattern internally, while linked lists use pointer relinking and associative containers use node extraction.

// C++20
#include <list>
#include <vector>
#include <cstdio>

int main() {
    std::vector<int> v{1, 0, 2, 0, 3};
    if (std::size_t n = std::erase(v, 0); n > 0)
        std::printf("Removed %zu zero(s) from vector.\n", n);

    std::list<int> lst{0, 1, 0, 2, 0};
    std::size_t n = std::erase(lst, 0);
    // n == 3; internally calls lst.remove(0) — zero element copies
    std::printf("Removed %zu zero(s) from list.\n", n);
}

std::list and std::forward_list: O(n) Member Removal Without Element Copies

Linked lists pay no move cost during removal because erasure is purely a pointer operation. When you apply the generic erase-remove idiom to a std::list, std::remove must move-assign elements through the buffer, wasting cycles on assignments that will be thrown away. The member functions list::remove and list::remove_if skip all of that — they traverse the list once, unlinking matching nodes and deallocating them in place.

// C++11
#include <forward_list>
#include <list>

int main() {
    std::list<std::string> words{"keep", "drop", "keep", "drop"};

    // Preferred: pointer relinking only, no string copies or moves
    words.remove("drop");
    // words == {"keep", "keep"}

    words.remove_if([](const std::string& s) {
        return s.size() > 5;
    });

    std::forward_list<int> fl{1, 2, 3, 2, 1};
    fl.remove(2);          // fl == {1, 3, 1}
    fl.remove_if([](int x) { return x == 1; });
    // fl == {3}
}

std::forward_list exposes the same remove and remove_if members, but because it is a singly-linked list it has no size() member and its erase_after iterator semantics differ. Using the member removal functions is always correct and avoids accidental quadratic behaviour from manual loops that call erase. Since C++20 both member functions return the count of removed elements; earlier standards returned void.

Stable Removal with std::stable_partition

std::stable_partition is the right tool when you need to separate elements into two groups and use both groups afterward. Unlike std::remove — which moves survivors forward and leaves the tail in an unspecified state — std::stable_partition stably rearranges elements so that all elements satisfying the predicate come first, and all others come second, with both partitions retaining their original relative order. The iterator to the second partition's beginning is returned, giving you a clean split point.

// C++11
#include <algorithm>
#include <vector>

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

    // Partition: evens first, odds second — both halves stay in original order
    auto mid = std::stable_partition(v.begin(), v.end(),
                                     [](int x) { return x % 2 == 0; });
    // v == {2, 4, 6, 8, 1, 3, 5, 7}
    // [v.begin(), mid) == evens;  [mid, v.end()) == odds

    // Physically separate the two groups
    std::vector<int> odds(mid, v.end());
    v.erase(mid, v.end());
    // v == {2, 4, 6, 8};  odds == {1, 3, 5, 7}
}

This pattern is valuable when the "removed" elements are not discarded but forwarded elsewhere — moved into a secondary container, dispatched to a different processing path, or returned to the caller. Attempting the same with std::remove_if loses access to the unwanted elements because their state after removal is unspecified.

// C++17
#include <algorithm>
#include <string>
#include <vector>

struct Task { std::string name; bool urgent; };

// Split tasks into urgent and deferred without losing either group
std::pair<std::vector<Task>, std::vector<Task>>
split_tasks(std::vector<Task> tasks) {
    auto boundary = std::stable_partition(
        tasks.begin(), tasks.end(),
        [](const Task& t) { return t.urgent; }
    );
    std::vector<Task> deferred(
        std::make_move_iterator(boundary),
        std::make_move_iterator(tasks.end())
    );
    tasks.erase(boundary, tasks.end());
    return {std::move(tasks), std::move(deferred)};
}

std::stable_partition is O(n log n) when additional memory is unavailable (it falls back to an in-place rotation algorithm), but O(n) when it can allocate a temporary buffer. For most practical vector sizes the allocating path is taken, making it as fast as a linear pass.

Performance: Erase-Remove vs std::ranges::remove + Erase vs Lazy Pipelines

Erase-remove, std::ranges::remove + erase, and std::erase_if all perform one pass over the data and one in-place compaction — they are asymptotically equivalent for eager removal. The differences are ergonomic and constant-factor, not algorithmic.

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

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

    // Option A: classic erase-remove (C++98)
    v.erase(std::remove_if(v.begin(), v.end(),
                           [](int x){ return x % 2 == 0; }),
            v.end());

    v = {1, 2, 3, 4, 5, 6, 7, 8}; // reset

    // Option B: ranges::remove + erase (C++20)
    auto tail = std::ranges::remove_if(v, [](int x){ return x % 2 == 0; });
    v.erase(tail.begin(), tail.end());

    v = {1, 2, 3, 4, 5, 6, 7, 8}; // reset

    // Option C: std::erase_if — single call, returns count (C++20)
    std::erase_if(v, [](int x){ return x % 2 == 0; });
    // v == {1, 3, 5, 7} in all three cases
}

Lazy range pipelines via std::views::filter are a different trade-off: they produce a view of the surviving elements with zero allocation and zero mutation, but do not shrink the underlying container. They are ideal for read-only traversal or when the result will be materialised into a new container via std::ranges::to (C++23).

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

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

    // Lazy: no allocation, no mutation, just a view
    auto odds_view = v | std::views::filter([](int x){ return x % 2 != 0; });
    // Iterate odds_view without touching v

    // Eager: materialise into a new vector (C++23 ranges::to)
    // auto odds = odds_view | std::ranges::to<std::vector>();

    // Or: eager in-place removal using erase_if (C++20)
    std::erase_if(v, [](int x){ return x % 2 == 0; });
    // v == {1, 3, 5}
}

Choose lazy views when you only need to read the filtered sequence once or when composing multiple transformations; choose std::erase_if or the classic erase-remove idiom when the container must be durably compacted and subsequent code relies on the reduced size() or contiguous memory layout.

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