Why std::remove Doesn't Shrink Your Vector: Erase-Remove, std::erase_if and the Moved-From Tail

The one fact that explains every remove surprise

std::remove and std::remove_if live in <algorithm>, and like every algorithm there they receive only a pair of iterators. An iterator can read and write elements, but it has no pointer back to the container and no way to call erase or resize. So the algorithm physically cannot delete anything. What it does instead is compaction: it walks the range once, moves every element you want to keep to the front, and returns an iterator to the new logical end.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 2, 5};
    auto new_end = std::remove(v.begin(), v.end(), 2);

    std::cout << "size=" << v.size()
              << " logical=" << (new_end - v.begin()) << " contents:";
    for (int x : v) std::cout << ' ' << x;
    std::cout << '\n';

    v.erase(new_end, v.end());
    std::cout << "after erase size=" << v.size() << '\n';
}

Output with g++ 10.3 (libstdc++):

size=5 logical=3 contents: 1 3 5 2 5
after erase size=3

The first three slots are the kept values in their original order. The last two slots are whatever was left behind; here they happen to be the old 2, 5, but the standard only promises they are “valid but unspecified”. The container still owns five objects until erase(new_end, v.end()) destroys the tail. That two-step pattern is the erase-remove idiom:

v.erase(std::remove(v.begin(), v.end(), 2), v.end());

This design is not an accident. Splitting “reorder” from “shrink” means the same algorithm works on a plain array, a std::array, a sub-range of a vector, or a range whose size must never change. The price is that the second step is easy to forget.

remove_if and the moved-from tail

remove_if is the same algorithm with a predicate. The detail most tutorials skip is how the kept elements get to the front: by move assignment. For int a move is a copy, so the tail looks harmless. For types with real resources it does not:

std::vector<std::string> s = {"alpha", "bb", "gamma", "dd", "epsilon"};
auto e = std::remove_if(s.begin(), s.end(),
                        [](const std::string& x) { return x.size() == 2; });
for (auto it = s.begin(); it != s.end(); ++it)
    std::cout << (it == e ? "| " : "") << '[' << *it << "] ";

[alpha] [gamma] [epsilon] | [dd] []

"epsilon" was moved into slot 2, so slot 4 is now a moved-from string (empty in libstdc++, but you cannot rely on that). Slot 3 still says "dd", a value you asked to remove. If you “peek” at the tail, you see a mix of stale originals and hollow objects. That is why the tail must be erased, not inspected.

A pattern I have seen go wrong more than once is code that calls remove_if, then loops from new_end to end() to “clean up” or log the removed items. With int the log looks right in testing. With std::string or std::unique_ptr the removed items are already gone: the unique_ptrs you meant to release were moved into the kept slots, and the tail holds nulls. If you need the removed elements, use std::stable_partition (kept first, removed second, both intact) and process the second half before erasing it.

C++20: std::erase and std::erase_if

C++20 added free functions that do both steps and cannot be half-written. They are declared in each container’s own header (<vector>, <string>, <list>, <map>…), not in <algorithm>:

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

std::vector<int> c = {1, 2, 3, 2, 5};
auto n = std::erase(c, 2);               // n == 2, c.size() == 3

std::set<int> st = {1, 2, 3, 4, 5, 6};
std::erase_if(st, [](int x) { return x % 2 == 0; });   // returns 3

std::map<std::string, int> m = {{"a", 0}, {"b", 3}, {"c", 0}};
std::erase_if(m, [](const auto& kv) { return kv.second == 0; });  // m.size() == 1

Things worth knowing:

• They return the number of erased elements (size_type). The very first implementations (GCC 9) returned void; the count was added by P1115 before C++20 was finalized, and g++ 10.3 returns it.
• Coverage differs by container. Sequence containers (vector, deque, string, list, forward_list) get both std::erase(c, value) and std::erase_if(c, pred). Associative and unordered containers (set, map, unordered_map…) get only erase_if, because they already have a member erase(key) that does the value case in O(log n).
• For vector, deque and string they are defined as exactly the erase-remove idiom, so there is no performance difference, just less room for error.

If your codebase is on C++20, I would treat hand-written erase-remove as a code smell in new code. The idiom is not wrong, but std::erase_if states the intent and removes the “forgot the second v.end()” class of bug.

Mistakes that compile

Forgetting the erase

std::vector<int> v = {1, 2, 3, 2, 5};
std::remove(v.begin(), v.end(), 2);   // size is still 5

g++ 10.3 accepts this silently even with -Wall. MSVC’s standard library marks std::remove as [[nodiscard]] and warns (C4834). Either way, the discarded return value is the bug: you threw away the only information about where the valid data ends.

Using an element of the range as the value

std::vector<int> w = {1, 2, 1, 3};
w.erase(std::remove(w.begin(), w.end(), w[0]), w.end());
// prints: 2 1 3   <- a 1 survived

std::remove takes the value as const T&. It is a reference to w[0], and the first thing the algorithm does is move 2 into w[0]. From that point on it is removing 2s, not 1s. Copy the value first:

const int target = w[0];
w.erase(std::remove(w.begin(), w.end(), target), w.end());   // 2 3

This is a real, well-known trap (the same aliasing rule applies to std::erase(v, v.front())), and it only shows up when the value you pass happens to live inside the range.

A stateful predicate

The standard lets the implementation copy your predicate. libstdc++‘s remove_if first calls find_if with a copy, then continues with another copy. A lambda that counts calls to “remove the third element” therefore restarts its count halfway:

std::vector<int> v = {10, 20, 30, 40, 50, 60};
int calls = 0;
v.erase(std::remove_if(v.begin(), v.end(),
            [calls](int) mutable { return ++calls == 3; }), v.end());
// prints: 10 20 40 50   <- both 30 and 60 were removed

Predicates for remove_if should be pure functions of the element. If you need position-based removal, compute the index and use v.erase(v.begin() + i), or keep state outside the lambda and capture it by reference, which at least makes all copies share it.

Erasing inside a loop

for (auto it = v.begin(); it != v.end(); ++it)
    if (*it == 2) v.erase(it);        // undefined behavior: 'it' is invalidated

The fixed version, it = v.erase(it) without the ++it on that path, is correct but O(n^2) for a vector, because every erase shifts the whole tail. erase-remove does one pass and moves each kept element at most once. The difference is invisible for 10 elements and dominant for large vectors with many matches.

Calling std::remove on a set or map

std::set<int> s = {1, 2, 3};
s.erase(std::remove(s.begin(), s.end(), 2), s.end());

error: assignment of read-only location '__result.std::_Rb_tree_const_iterator<int>::operator*()'

Set iterators yield const elements, because assigning a new value through them would break the tree ordering. The error points deep into stl_algo.h, which confuses people the first time. Use s.erase(2) or std::erase_if.

std::list: use the member function

std::remove does work on std::list (its iterators are writable), but it does the wrong kind of work: it move-assigns values from node to node, then erase frees the leftover nodes at the end. The member list::remove(value) and list::remove_if(pred) unlink the matching nodes directly. No element is moved, which matters for expensive-to-move types, and iterators and references to the kept elements stay valid. Since C++20 the member versions return the number of removed elements, same as std::erase.

list::unique and forward_list::remove_if follow the same logic. The rule of thumb: if a container has a member function with the same name as an algorithm, the member exists because it can do better.

std::unique: adjacent duplicates only

std::unique is a remove algorithm too: it compacts the range so that each run of equal adjacent elements keeps one copy, returns the new logical end, and needs an erase.

std::vector<int> u = {1, 1, 2, 2, 2, 3, 1};
u.erase(std::unique(u.begin(), u.end()), u.end());
// 1 2 3 1   <- the last 1 was not adjacent to the others

To remove all duplicates, sort first (O(n log n)), then unique. If you must keep the original order of first occurrences, sort + unique is the wrong tool; track seen values in an std::unordered_set and use remove_if.

unique accepts a binary predicate, which is how you dedupe case-insensitively. The sort and the equality must agree on what “equal” means, and if you care which spelling survives, use stable_sort:

auto lower_less = [](const std::string& a, const std::string& b) {
    return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),
        [](unsigned char x, unsigned char y) { return std::tolower(x) < std::tolower(y); });
};
auto lower_eq = [](const std::string& a, const std::string& b) {
    return std::equal(a.begin(), a.end(), b.begin(), b.end(),
        [](unsigned char x, unsigned char y) { return std::tolower(x) == std::tolower(y); });
};

std::vector<std::string> words = {"Hello", "world", "HELLO", "World"};
std::stable_sort(words.begin(), words.end(), lower_less);
words.erase(std::unique(words.begin(), words.end(), lower_eq), words.end());
// Hello world

Stripping characters from a string

std::string is a sequence container, so the same idiom (or C++20 std::erase_if) applies:

std::string text = "Hello   World\n\tTest";
text.erase(std::remove_if(text.begin(), text.end(),
               [](unsigned char ch) { return std::isspace(ch); }),
           text.end());
// HelloWorldTest

Note the unsigned char parameter. Passing a plain char with a negative value (any byte above 0x7F on platforms where char is signed, which includes UTF-8 text) to std::isspace is undefined behavior. It is one of those bugs that works on ASCII test data and crashes, or asserts in MSVC debug builds, the first time a user types a non-ASCII name. I now write the unsigned char lambda parameter out of habit for every <cctype> call.

Choosing the right tool

Situation	Use
C++20, any standard container	std::erase(c, value) / std::erase_if(c, pred)
Pre-C++20 vector, deque, string	c.erase(std::remove_if(...), c.end())
list / forward_list	member remove / remove_if
set, map before C++20	loop with it = c.erase(it), or member erase(key)
Need the removed elements intact	std::stable_partition, process the tail, then erase
Fixed-size range (array, span)	std::remove_if and keep the returned end

Related Articles

• C++ Iterators: Categories, Operations and Invalidation Bugs
• std::vector in Practice: reserve vs resize, Iterator Invalidation
• C++ Partition Algorithms
• C++ Count Algorithms: count, count_if, all_of, any_of