--- title: 'The Erase–Remove Idiom' source: 'https://academia.sh/en/courses/cpp-standard-library/erase-remove-idiom' course: 'Resource Management and the Standard Library' language: en updated: '2026-09-26T03:02:47+00:00' license: 'CC BY-SA 4.0' objectives: - 'Shows that std::remove does not actually delete elements, it only moves them forward' - "Measures that the values in a vector's tail after remove are unspecified" - 'Shows that the tail is actually removed once combined with erase' - "Recognizes that C++20's std::erase free function collapses the same idiom into one line" --- # The Erase–Remove Idiom The measurement of how the elements left in a vector's tail after std::remove carry an unspecified value, and how erase actually removes that tail. 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. ```cpp // remove-without-erase.cpp — what std::remove does on its own #include #include #include int main() { std::vector 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(std::distance(numbers.begin(), new_end))); return 0; } ``` ```text 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. ```cpp // remove-does-not-read-the-tail.cpp — why the region outside the valid one is never looked at #include #include #include int main() { std::vector 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; } ``` ```text 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**. ```cpp // remove-erase-idiom.cpp — actual removal in two steps #include #include #include int main() { std::vector 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; } ``` ```text 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 `` header and apply the `remove`+`erase` pair without requiring a container-specific member function. ```cpp // std-erase-free-function.cpp — erase-remove in one call #include #include int main() { std::vector 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; } ``` ```text 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. ```cpp // remove-complexity.cpp — single pass, independent of the number of matches #include #include #include int main() { std::vector none_match{1, 2, 3, 4, 5}; std::vector 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(std::distance(none_match.begin(), end1))); std::printf("all_match valid length %ld\n", static_cast(std::distance(all_match.begin(), end2))); return 0; } ``` ```text 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. ```cpp // list-remove-member-function.cpp — list provides its own remove #include #include int main() { std::list 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; } ``` ```text 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. ```cpp // remove-if-erase-if.cpp — removal by predicate #include #include #include int main() { std::vector 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; } ``` ```text 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. ```cpp // if-the-tail-is-read.cpp — why reading the tail is wrong, not a crash #include #include #include int main() { std::vector 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(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; } ``` ```text 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: ```cpp title="erase-returned-count.cpp" #include #include int main() { std::vector numbers{7, 1, 7, 2, 7}; auto removed = std::erase(numbers, 7); std::printf("%zu removed, %zu remaining\n", removed, numbers.size()); return 0; } ``` ```text title="output" 3 removed, 2 remaining ``` `std::erase(numbers, 7)` removed the three `7`s 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?