ProblemsSTL MasteryThe erase-remove idiom
NoviceSTL Mastery

The erase-remove idiom

Context

An intern's PR landed in your review queue: removing vector elements with erase inside an index loop. It works on his laptop with five elements, therefore 'tested'. You commented 'look up erase-remove'; he reacted 👍 and changed nothing. Show him how it's done: one line instead of a quadratic loop.

Task

Remove every occurrence of a value from a std::vector<int> in place, using the erase-remove idiom — not a hand-written shifting loop. The relative order of the remaining elements must be preserved.

Constraints

  • Must use std::remove (or std::remove_if) together with vector::erase
  • Must modify the vector in place; preserve the order of the kept elements
  • No raw element-shifting loop, no second vector
  • Removing a value that is absent leaves the vector unchanged

Before you code

  • Why does std::remove not actually change the container's size?
  • What does the iterator returned by std::remove mark?
  • Why is erase-in-a-loop O(n²) while erase-remove is O(n)?

Tests

  • #1Removes all occurrences, keeps order
  • #2Adjacent matches handled
  • #3Absent value leaves vector unchanged

Hints

Hint 1

One line: v.erase(std::remove(v.begin(), v.end(), value), v.end());

Editorerase-remove.cpp
Results

Hit Submit (or ⌘/Ctrl + ↵) — test results will show up here.