skip to content

In C++, why does std::remove_if not shrink a std::vector, and how do you actually delete the matching elements?

level: middleimportance: must knowfreq 75%

answer

  1. algorithms only see iterators
  2. kept elements move forward
  3. returns the new logical end
  4. erase from there to end()
  5. C++20 does both in one call

basics

~20 s

std::remove_if works on iterators, so it cannot change the container's size: it moves the kept elements to the front and returns the new logical end. Calling erase(newEnd, end()) deletes the leftovers; C++20's std::erase_if(v, pred) does both steps and returns the count.

solid answer

~40 s

Algorithms in `<algorithm>` receive only an iterator range, and an iterator has no way to destroy an element of the container it points into. So `std::remove_if(v.begin(), v.end(), pred)` compacts: it move-assigns every element that does not match towards the front, keeping their order, and returns an iterator to the new logical end. The elements from there to `v.end()` are still in the vector, in a valid but unspecified (often moved-from) state, and `v.size()` is unchanged. The **erase-remove idiom** finishes the job: `v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());`. Since C++20, `std::erase_if(v, pred)` (and `std::erase(v, value)`) wrap both steps for every standard container and return how many elements were removed; for node-based containers they call the container's own erase instead of shifting elements.

code

cpp · 25 lines
cpp
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct LogRecord {
    std::string level;
    std::string message;
};

int main() {
    std::vector<LogRecord> log{{"INFO", "start"}, {"DEBUG", "x=1"},
                               {"WARN", "slow"},  {"DEBUG", "x=2"}};
    auto isDebug = [](const LogRecord& r) { return r.level == "DEBUG"; };

    auto newEnd = std::remove_if(log.begin(), log.end(), isDebug);
    std::cout << "after remove_if: size " << log.size()
              << ", kept " << (newEnd - log.begin()) << '\n';
    log.erase(newEnd, log.end());                 // the erase half of the idiom
    std::cout << "after erase: size " << log.size() << '\n';

    log.push_back({"DEBUG", "x=3"});
    auto removed = std::erase_if(log, isDebug);   // C++20: both steps in one call
    std::cout << "erase_if removed " << removed << ", size " << log.size() << '\n';
}

go deeper

for a junior

Write the idiom from memory: v.erase(std::remove_if(v.begin(), v.end(), pred), v.end()), and know std::erase_if does it in C++20.

for a middle

Explain why an iterator-based algorithm cannot shrink a container, what state the tail is in, and why a per-element erase loop is quadratic on a vector.

for a senior

Spot the single-iterator erase bug and code that reads moved-from tail elements, and choose list::remove_if or std::erase_if per container.

for a principal

Set a C++20 coding rule that prefers std::erase and std::erase_if over the hand-written idiom so the second half cannot be forgotten.

## Why an algorithm cannot shrink a container The standard algorithms are written against **iterators**, not containers. `std::remove_if` receives `first` and `last`; it can read, compare and assign through them, but it has no access to the `std::vector` that owns the storage, so it cannot call `erase`, update the size or free memory. Its specification therefore says it **eliminates** matching elements from the range in a narrower sense: - every element for which the predicate is false is move-assigned towards the front, keeping its relative order (the algorithm is **stable**); - it returns an iterator `j` marking the end of the kept elements; - the elements in `[j, last)` are left in a **valid but unspecified state**, because they may have been moved from; - it applies the predicate exactly `last - first` times. After the call, `v.size()` is the same as before. Code that forgets this keeps processing the leftovers - typically empty strings or stale copies - as if they were real records. ## The erase-remove idiom The fix is one expression: ```cpp log.erase(std::remove_if(log.begin(), log.end(), isDebug), log.end()); ``` `std::remove_if` compacts and returns the new end; `vector::erase(first, last)` destroys the tail and reduces the size. The vector's capacity does not change; call `shrink_to_fit` separately if the memory matters. `std::remove(first, last, value)` is the value-based twin, using `==` instead of a predicate. ## C++20: std::erase and std::erase_if C++20 added free functions that do both steps for each standard container: | Container | `std::erase_if(c, pred)` does | |---|---| | `vector`, `deque`, `basic_string` | `remove_if` then `c.erase(it, c.end())` | | `list`, `forward_list` | the member `c.remove_if(pred)` (relinks nodes) | | `map`, `set`, `unordered_map`, ... | loops with `c.erase(it)` for each match | Each returns the number of elements removed as the container's `size_type`. For a `std::vector` the standard specifies `std::erase_if` exactly as `remove_if`, `distance`, `erase`, so it has the same cost and the same stability. Prefer it in C++20 code: it removes the chance of forgetting the second half, and the same spelling works for every container. `std::erase(c, value)` is the value-based form for the sequence containers and strings. ## Cleaning a log buffer A service keeps the last few thousand `LogRecord` entries in a vector and drops debug lines before shipping them: 1. Define the predicate once: `auto isDebug = [](const LogRecord& r) { return r.level == "DEBUG"; };`. 2. In C++17: `log.erase(std::remove_if(log.begin(), log.end(), isDebug), log.end());`. 3. In C++20: `auto dropped = std::erase_if(log, isDebug);` and report `dropped` as a metric. Both run in linear time with one pass over the data. The tempting alternative - a loop that calls `log.erase(it)` for each debug line - shifts every later element on every erase and is quadratic on a vector, and it needs care with the iterator `erase` returns. ## What happens inside, step by step Trace a typical implementation of `std::remove_if` over `{INFO start, DEBUG x=1, WARN slow, DEBUG x=2}` with the debug predicate: 1. A write position starts at the first element. `INFO start` is kept, so the write position moves past it. 2. `DEBUG x=1` matches and is skipped; the write position stays on it. 3. `WARN slow` is kept and is move-assigned into the slot that held `DEBUG x=1`; the write position advances. 4. `DEBUG x=2` matches and is skipped. The algorithm returns the write position, index 2. The vector now holds `INFO start`, `WARN slow`, then two tail elements whose values the standard leaves unspecified - here a moved-from `WARN` record and the untouched `DEBUG x=2`. Nothing was destroyed and the size is still 4. Each kept element was moved at most once, which is why the idiom is linear, and the kept elements stayed in their original order, which is what "stable" promises here. ## Mistakes interviewers look for - **Calling `remove_if` alone** and assuming the size changed. - **Passing only one iterator to `erase`**: `log.erase(std::remove_if(...))` compiles - it is the single-element `erase(const_iterator)` overload - and deletes just the first leftover, or has undefined behaviour when nothing matched and the returned iterator is `end()`. - **Reading the tail** `[newEnd, end())` and expecting the removed values; they are unspecified. - **Calling `std::remove_if` on a `std::list`** when its member `remove_if` relinks nodes without moving any values. - **Using `std::remove_if` on a `std::set` or `std::map`**: their elements or keys are const, so the call does not compile; use `std::erase_if` or an erase loop.

  • What goes wrong with v.erase(std::remove_if(v.begin(), v.end(), pred)) written with a single argument?
    It calls the single-element overload `erase(const_iterator)`, so only the first leftover after the new end is destroyed and the rest stay in the vector. If nothing matched, `remove_if` returns `end()`, and erasing `end()` is undefined behaviour. The idiom needs the two-iterator form: `v.erase(newEnd, v.end())`.
  • How does std::erase_if behave on a std::list compared with a std::vector?
    For `std::list` it is specified as the member `c.remove_if(pred)`, which unlinks and destroys matching nodes without moving any other element, so iterators to the survivors stay valid. For `std::vector` it is `remove_if` followed by a range `erase`, which move-assigns survivors forward. Both return the number of removed elements.

  • Saying std::remove_if reduces the vector's size
  • Expecting the removed values to sit at the end after std::remove
  • Calling erase with only the iterator returned by remove_if
  • Erasing matches one at a time inside a loop over a vector
  • Believing std::erase_if is a member function of std::vector

Assumes C++23; std::erase and std::erase_if for the standard containers are C++20 additions, and in C++17 the explicit erase-remove idiom is the only option.