In C++, a loop runs for (auto it = c.begin(); it != c.end(); ++it) if (skip(*it)) c.erase(it); — what is wrong, and what is the correct pattern?
answer
- erase kills the iterator you hold
- ++ on a dead iterator
- erase hands back a replacement
- advance only when you keep
basics
~10 sc.erase(it) invalidates it, so the following ++it is undefined behaviour. Use the iterator erase returns, which refers to the element after the erased one: it = c.erase(it) when removing, ++it only when keeping.
solid answer
~40 s`erase(it)` invalidates `it` in every standard container that has it: for `std::vector` it invalidates iterators at or after the erase point, for `std::list`, `std::map` and the hash containers just the erased element's iterator. The loop then evaluates `++it` on an invalidated iterator, which is undefined behaviour. On a `std::list` it reads a freed node, which AddressSanitizer reports as heap-use-after-free; on a `std::vector` it typically skips the element that shifted into place and can run past `end()` when the last element is erased. The correct loop advances in exactly one branch: `it = c.erase(it);` when removing, `++it;` otherwise. Every standard container with an `erase(iterator)` member returns the next iterator; the ordered associative containers have done so since C++11. To remove all matches at once, C++20's `std::erase_if` is simpler and, for vectors, linear.
code
cpp · 30 lines#include <iostream>
#include <list>
#include <map>
#include <string>
#include <vector>
bool skipped(const std::string& s) { return s.starts_with("Ad:"); }
int main() {
std::vector<std::string> queue{"Intro", "Ad: shoes", "Ad: cars", "Outro"};
for (auto it = queue.begin(); it != queue.end();) {
if (skipped(*it))
it = queue.erase(it); // erase returns the element after the erased one
else
++it;
}
std::list<std::string> history{"Ad: tea", "Ballad", "Ad: phones"};
for (auto it = history.begin(); it != history.end();)
it = skipped(*it) ? history.erase(it) : std::next(it);
std::map<int, std::string> byId{{1, "Ad: x"}, {2, "Anthem"}, {3, "Ad: y"}};
for (auto it = byId.begin(); it != byId.end();)
it = skipped(it->second) ? byId.erase(it) : std::next(it);
for (const auto& s : queue) std::cout << s << ' ';
for (const auto& s : history) std::cout << s << ' ';
for (const auto& [id, s] : byId) std::cout << id << ':' << s << ' ';
std::cout << '\n';
}go deeper
Recall that erase invalidates the iterator passed to it, and that the safe loop writes it = c.erase(it) and only increments when it keeps an element.
Explain what each container's erase invalidates and that erase returns the next iterator, including the forward_list erase_after variant.
Spot the bug in review across containers, explain why the vector version silently skips elements while the list version crashes, and know when std::erase_if or remove_if is the better rewrite.
Decide whether hand-written erase loops are allowed at all once the codebase is on C++20, given std::erase_if expresses the same thing with no iterator to get wrong.
## The bug in the classic loop The loop under discussion: ```cpp for (auto it = c.begin(); it != c.end(); ++it) if (skip(*it)) c.erase(it); ``` looks harmless, and it compiles for every standard container. The problem is the order of events. `c.erase(it)` removes the element and **invalidates** `it`; the loop header then evaluates `++it` on that invalidated iterator, which is **undefined behaviour**. What each container's `erase` invalidates: - `std::vector`: iterators and references at or after the erase point, including `end()`. - `std::deque`: depending on position, only the erased elements, those plus the past-the-end iterator, or every iterator. - `std::list`, `std::map`, `std::set` and the hash containers: the iterators and references to the erased elements only. That is still the one you hold. ## What the undefined behaviour looks like The symptoms differ by container, which is why the bug survives review: 1. **`std::list` and `std::map`.** The erased node is freed, and `++it` reads its link pointer. Under AddressSanitizer this is reported as `heap-use-after-free`, with the read on the loop header and the free at the `erase`. Without a sanitizer it may appear to work, crash, or loop forever. 2. **`std::vector`.** The memory is still inside the buffer, so nothing crashes. Typically the next element shifts into the erased slot and `++it` steps over it, so two adjacent matches leave one behind. If the last element is erased, `it` moves past `end()` and the loop keeps reading beyond the data. None of this is defined; it is what common implementations happen to do. ## The correct pattern Every standard container with an `erase(iterator)` member returns an iterator to the element that followed the erased one, or `end()` if the last element was removed. The loop uses that result and advances in exactly one branch: ```cpp for (auto it = c.begin(); it != c.end(); ) { if (skip(*it)) it = c.erase(it); else ++it; } ``` Three details make it correct: - The `for` header has **no increment**; advancing is the body's job. - After `it = c.erase(it)`, the loop must **not** also `++it`, or it skips an element and may increment `end()`. - `c.end()` is **re-evaluated** on each test, which matters for vector, where erase invalidates the old `end()`. ## History and variants - Since **C++11**, `erase(iterator)` on `std::map`, `std::set`, `std::multimap` and `std::multiset` returns the next iterator; in C++03 it returned `void`. Old code therefore used `c.erase(it++)`, which passes a copy of the old position while `it` has already moved on. That idiom works for node-based containers, but on a `std::vector` it is undefined, because the incremented iterator sits after the erase point and is invalidated too. - **`std::forward_list`** has no `erase(iterator)`, since unlinking a node requires its predecessor. It offers `erase_after(pos)`, which returns the iterator following the erased element; a loop keeps a `prev` iterator starting from `before_begin()`. - Copying an iterator before erasing does not help: a copy refers to the same erased element and is invalidated with it. ## When not to write the loop at all Removing every element that matches a predicate is better written without manual iterators: | tool | standard | note | |---|---|---| | `std::erase_if(c, pred)` | C++20 | free function for the standard containers except `std::array`; returns the count removed | | `std::remove_if` plus `erase` | C++98 | the erase-remove idiom for sequence containers | | `list.remove_if(pred)` | C++98 | member function on `std::list` and `std::forward_list` | For a `std::vector`, the difference is also about cost. Each `erase` in the loop moves every later element one slot left, so removing k of n elements costs roughly k times n moves, while `std::erase_if` compacts the survivors in a single linear pass. The manual loop remains the right tool when each removal needs side effects, such as logging, releasing a resource, or deciding based on neighbouring elements. ## What interviewers listen for A strong answer names the invalidation before the increment, gives the `it = c.erase(it); else ++it` pattern, notes that erase returns the next iterator in all standard containers since C++11, and explains why the vector version silently skips elements while the list version crashes. Mentioning `std::erase_if` for bulk removal, and the forward_list `erase_after` exception, shows breadth.
- How do you erase while iterating a std::forward_list?A `std::forward_list` has no `erase(iterator)`, because removing a node needs its predecessor. Keep a `prev` iterator starting at `before_begin()` and loop while `std::next(prev) != fl.end()`: if the next element should go, call `fl.erase_after(prev)`, otherwise `++prev`. `erase_after` returns the iterator following the erased element. For bulk removal, `fl.remove_if(pred)` is simpler.
- Why is erasing one element at a time from a large std::vector slow even when correct?Each `vector::erase` move-assigns every later element one slot left, so removing k elements from n costs roughly k times n moves. C++20's `std::erase_if(v, pred)`, or the remove-erase idiom before it, compacts the survivors in one pass and erases the tail once, which is linear.
- Says erase(it) leaves it valid as long as the container is a list
- Writes c.erase(it++) on a std::vector
- Advances with ++it after it = c.erase(it) in the same iteration
- Believes std::map::erase(iterator) returns void in modern C++
- Says the vector version is fine because it never crashed