The Erase–Remove Idiom

The previous lesson showed that std::sort reorders a vector‘s elements in place, which changes the source. The container’s element count never changed during the sort. This lesson moves to an operation that reduces the element count, but with an unexpected detail: std::remove, whose name includes “remove,” does not change a vector’s size. So what does it do?

This detail is one of the points that newcomers find most surprising: a function’s name never lines up exactly one to one with what it actually does. std::remove is an algorithm, and algorithms only work with iterator pairs — they have no access to the container itself, and therefore no authority to shrink the container’s size either. This lesson shows step by step where this boundary comes from and how the actual removal is completed.

std::remove: A “Removal” That Does Not Remove

std::remove walks the given range; it moves elements not equal to the sought value toward the front of the range and returns an iterator marking where the new “valid” region ends. It does not change the container’s size — it cannot, because it works with an iterator pair, not with the container itself.

// remove-without-erase.cpp — what std::remove does on its own
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> numbers{1, 7, 2, 7, 3, 7};
    std::size_t before = numbers.size();

    auto new_end = std::remove(numbers.begin(), numbers.end(), 7);

    std::printf("did the size change %s\n",
        (numbers.size() != before) ? "yes" : "no");
    std::printf("length of the valid region %ld\n",
        static_cast<long>(std::distance(numbers.begin(), new_end)));
    return 0;
}

did the size change no
length of the valid region 3

SL19. After the call to std::remove, numbers.size() is still 6 — the container’s size did not change. The new_end iterator shows that the valid region is three elements long: the values 1, 2, 3 were moved forward. The remaining three positions (from new_end to numbers.end()) still exist, but their contents are no longer meaningful. The kind of this first step is changed: the array’s first three positions carry a defined result (1, 2, 3).

The Values Left in the Tail: Unspecified

The positions from new_end to numbers.end() depend on std::remove‘s implementation detail — the standard does not define what these positions’ values will be, it only says they will carry “an unspecified value.” This lesson does not read those positions.

// remove-does-not-read-the-tail.cpp — why the region outside the valid one is never looked at
#include <algorithm>
#include <cstdio>
#include <vector>

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

    auto new_end = std::remove(numbers.begin(), numbers.end(), 7);

    std::printf("valid region:");
    for (auto it = numbers.begin(); it != new_end; ++it) {
        std::printf(" %d", *it);
    }
    std::printf("\n");
    // The values from new_end to numbers.end() are not read,
    // because the standard does not define the values in this region.
    return 0;
}

valid region: 1 2 3

SL20. This lesson never read the three tail positions (after new_end) in any printf call — not to avoid undefined behavior (reading the tail is not undefined behavior, the elements still exist and are valid), but to avoid presenting an unspecified value as if it were a definite number. Because the standard does not define what values these positions will carry, printing these values could produce a different output in a different standard library implementation five years from now. The kind of this operation is unspecified: the content of the tail positions is not guaranteed by the standard.

Actually Removing the Tail with erase

Giving the iterator std::remove returns to the container’s own erase member function actually removes the tail and shrinks the container’s size. This two-step pattern is called the erase–remove idiom.

// remove-erase-idiom.cpp — actual removal in two steps
#include <algorithm>
#include <cstdio>
#include <vector>

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

    auto new_end = std::remove(numbers.begin(), numbers.end(), 7);
    numbers.erase(new_end, numbers.end());

    std::printf("size %zu\n", numbers.size());
    std::printf("contents:");
    for (int value : numbers) {
        std::printf(" %d", value);
    }
    std::printf("\n");
    return 0;
}

size 3
contents: 1 2 3

SL21. After the call erase(new_end, numbers.end()), numbers.size() dropped to 3 and the contents are only 1, 2, 3. The kind of this step is changed: both the size and the contents reached a definite result, in the form the standard defines. Combining the two steps gives this picture: remove alone puts the source into the changed state but leaves the tail unspecified; once erase is added, the tail is also removed and the source becomes fully changed again — no unread unspecified region remains. This is also where the reason for keeping the two steps separate becomes clear: because remove only works with an iterator pair, it cannot shrink the container itself; the authority to shrink the container exists only in that container’s own erase member function. The two separate steps reflect two separate responsibilities: one takes on moving the elements, the other takes on giving back the memory.

C++20: The std::erase Free Function

C++20 added free functions that collapse this frequently used two-step pattern into a single call: std::erase and std::erase_if. These functions are defined in the <vector> header and apply the remove+erase pair without requiring a container-specific member function.

// std-erase-free-function.cpp — erase-remove in one call
#include <cstdio>
#include <vector>

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

    std::erase(numbers, 7);

    std::printf("size %zu\n", numbers.size());
    std::printf("contents:");
    for (int value : numbers) {
        std::printf(" %d", value);
    }
    std::printf("\n");
    return 0;
}

size 3
contents: 1 2 3

SL22. std::erase(numbers, 7) did in one line what the previous two steps (SL19 and SL21) did; the result is the same: size 3, contents 1, 2, 3. The kind of this operation is also changed — this time no unspecified intermediate state was ever visited, because the tail move and the actual removal happened inside a single function, without ever exposing an intermediate iterator to the caller. The older remove+erase idiom still compiles and is still seen in pre-C++20 code; std::erase gives the same result with fewer lines of code and hides the intermediate unspecified state.

This Course Does Not Count: The Measurement Axis Is Not How Many Elements Were Deleted

The axis of the “Traits, Generics and Error Handling” lesson (the rust-soyutlama course in the Rust curriculum) is how many times a body runs — it measures how many times a predicate or a closure is called. This lesson stands on a different axis: how many elements std::erase_if removes is not this lesson’s subject. numbers.size() dropping from 6 to 3 is not a counter, it is a single value showing the container’s current state — just as, in the previous lesson, the number std::count returned was a result, not a count of how many times it was called. What this lesson measures is not the number of removed elements, but which kind (unspecified or changed) the source falls into after removal.

std::remove’s Complexity: Independent of the Number of Matches

std::remove and std::remove_if scan the range from start to end in a single pass; their complexity is O(n), and this is independent of how many elements in the range turn out equal to the sought value. The algorithm never visits any element twice: it either moves the element forward or skips over it, then advances to the next position.

// remove-complexity.cpp — single pass, independent of the number of matches
#include <algorithm>
#include <cstdio>
#include <vector>

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

    auto end1 = std::remove(none_match.begin(),
        none_match.end(), 9);
    auto end2 = std::remove(all_match.begin(),
        all_match.end(), 9);

    std::printf("none_match valid length %ld\n",
        static_cast<long>(std::distance(none_match.begin(), end1)));
    std::printf("all_match valid length %ld\n",
        static_cast<long>(std::distance(all_match.begin(), end2)));
    return 0;
}

none_match valid length 5
all_match valid length 0

SL23. Both calls scan a range of the same size (5 elements) in a single pass; in the first, no element matches, so the valid region covers the whole range (5); in the second, every element matches, so the valid region becomes empty (0). Both run in the same order of magnitude of time — std::remove does not take a different path depending on how many matches it finds, it visits every element exactly once. This is an example showing that the algorithm’s complexity depends on the input’s length, not its content.

std::list::remove: A Member Function That Needs No Idiom

While the remove+erase idiom is necessary for std::vector, std::list provides its own remove and remove_if member functions, and these need no idiom — the moment they are called, they actually take matching nodes out of the linked list, no separate erase call is needed.

// list-remove-member-function.cpp — list provides its own remove
#include <cstdio>
#include <list>

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

    numbers.remove(7);

    std::printf("size %zu\n", numbers.size());
    std::printf("contents:");
    for (int value : numbers) {
        std::printf(" %d", value);
    }
    std::printf("\n");
    return 0;
}

size 3
contents: 1 2 3

SL24. numbers.remove(7) alone, without a separate erase call, reached the same result the two-step idiom reached in the vector example: size 3, contents 1, 2, 3. The kind of this operation is changed. The difference is in the mechanism: because std::list keeps its nodes in a linked structure, removing a node does not require shifting neighboring nodes; the remove member function can perform this removal directly. std::vector, because it keeps elements in contiguous memory, gives the generic std::algorithm no authority to change the container’s size — this is why std::remove only moves elements, and the actual removal is left to the container-specific erase.

std::remove_if and std::erase_if: Removal by a Predicate

std::remove only measures equality to a value. If the removal decision depends on a condition, std::remove_if is used; its first argument is not a value but a predicate. The idiom stays the same: the iterator remove_if returns is given to erase, or std::erase_if is used in C++20 for a single call.

// remove-if-erase-if.cpp — removal by predicate
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
    std::vector<int> numbers{4, 15, 8, 23, 6, 42};

    std::erase_if(numbers, [](int value) { return value > 10; });

    std::printf("size %zu\n", numbers.size());
    std::printf("contents:");
    for (int value : numbers) {
        std::printf(" %d", value);
    }
    std::printf("\n");
    return 0;
}

size 3
contents: 4 8 6

SL25. std::erase_if removed the three elements (15, 23, 42) that satisfy the predicate (greater than 10); the remaining three elements kept their input order (4, 8, 6). The kind of this operation is changed: the size dropped from 6 to 3, and the standard defines which elements remain (those that do not satisfy the predicate) and that their relative order is preserved. The relationship between the remove_if+erase pair and erase_if is the same as the relationship between remove+erase and erase: both apply the same two steps, erase_if only hides those steps in a single call and never exposes the intermediate unspecified tail to the caller.

If the Tail Is Read: Not a Crash, an Undefined Value

Code that tries to loop over and print the positions from the new_end iterator std::remove returns to numbers.end() compiles and runs — there is no compile error or crash here. The problem is not visible at runtime either: the program prints some number. The problem is that which value that number will be is undefined across different standard library implementations.

// if-the-tail-is-read.cpp — why reading the tail is wrong, not a crash
#include <algorithm>
#include <cstdio>
#include <vector>

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

    auto new_end = std::remove(numbers.begin(), numbers.end(), 7);

    std::printf("valid region length %ld\n",
        static_cast<long>(std::distance(numbers.begin(), new_end)));
    // The values in the tail are deliberately not printed: the standard
    // does not define them, so this lesson produces no output based on them.
    return 0;
}

valid region length 3

This code runs, but a version of it that tries to read the tail has its output never shown in this lesson, because that output would rest on a value the standard does not guarantee. Run five years from now with a different compiler or a different library implementation, the same line could print a different number — this is exactly the sort of evidence this lesson has avoided from the start.

C++20’s std::erase/std::erase_if free functions are overloaded not only for std::vector but also for std::list, std::deque and std::forward_list. This provides a common interface independent of container type: whichever container is being used, the operation “remove the elements matching this value/predicate” is expressed with the same call. But different mechanisms still run underneath this common interface — for std::vector the remove+erase idiom is applied internally, while for std::list direct node removal is done. A common interface does not mean the implementation detail is the same; the distinction followed throughout this lesson (the source’s kind: unchanged, changed, empty, unspecified) still applies to both mechanisms, because the outcome is evaluated by looking at the source’s state, not at the implementation detail.

The Bounding Measurement

The remove+erase idiom makes the two steps visible separately and briefly exposes the unspecified tail in between. std::erase, which does the same work in one call, never shows this intermediate state, and it even reports how many elements it removed — its return value is not a predicate call counter, it is the operation’s result:

#include <cstdio>
#include <vector>

int main() {
    std::vector<int> numbers{7, 1, 7, 2, 7};

    auto removed = std::erase(numbers, 7);

    std::printf("%zu removed, %zu remaining\n", removed, numbers.size());
    return 0;
}

3 removed, 2 remaining

std::erase(numbers, 7) removed the three 7s from the five-element numbers and reported this with a single return value: removed is 3, the remaining size is 2. In the if-the-tail-is-read.cpp example above, the tail was never read because its content was unspecified; here there is no tail at all to read — because std::erase completes the removal and size-shrinking steps internally, the source moves directly into the changed kind, never visiting an intermediate unspecified state. This shares the same root as what was seen above for the std::list::remove member function: both fold the idiom’s two steps (move, then shorten) into a single operation without exposing them to the caller; their only difference is in the mechanism — std::list::remove changes node linkage, while std::erase on a vector internally calls the remove+erase idiom itself. The difference between the identically named std::remove (which does not remove) and std::list::remove (which actually removes) reappears here too: both carry the name “remove,” but only the member function carries the authority to actually remove.

Summary

• std::remove does not delete elements; it moves the ones not equal to the sought value forward and does not change the container’s size. The tail region from the returned iterator to the container’s end carries an unspecified value, and this lesson never reads that region.
• erase(new_end, end()) actually removes the tail and shrinks the container’s size; the kind of this step is changed.
• C++20’s std::erase free function collapses the remove+erase idiom into a single line and delivers the same changed result without ever visiting an intermediate unspecified state; it also reports how many elements it removed through its return value. The bounding measurement confirms exactly this: the call std::erase(numbers, 7) moves the source directly into the changed kind without ever visiting the tail.
• The kind of this lesson’s central measurement is unspecified: the content of the values in the tail after std::remove is not defined by the standard.
• The complexity of std::remove/std::remove_if is O(n) and is independent of how many elements in the range match; this lesson measures not the number of matches but the source’s kind.
• std::list performs direct removal, needing no idiom, through its remove/remove_if member functions; why std::vector‘s generic algorithm lacks this authority comes from the difference in the containers’ memory layout.

Next Step

This lesson used the iterator an algorithm returns, but the comparison was not always equality to a value — some calls passed a predicate. Up to now these predicates could be thought of as an ordinary function pointer or a named struct, but in practice they are mostly written as a small, single-use expression. The next lesson moves to the mechanism behind these predicates, lambda expressions and function objects: what happens to a value when a lambda captures it?