Как удалить элементы из вектора in-place, сохраняя порядок без копирования и релокации?

Что проверяют

Знаете ли вы идиому erase-remove и понимаете ли, что происходит с элементами внутри. Формулировка «без копирования и релокации» содержит ловушку: элементы всё равно сдвигаются, но перемещением внутри того же буфера, без перевыделения памяти. Следом спрашивают сложность и про std::erase_if.

Как отвечать

В C++20 это одна строка:

std::erase_if(v, [](int x) { return x == 3; });

До C++20 идиома erase-remove:

v.erase(std::remove_if(v.begin(), v.end(), pred), v.end());

Что происходит внутри:

• std::remove_if: один проход, оставляемые элементы переносятся вперёд через move-присваивание. Порядок сохраняется, сложность O(n), предикат вызывается ровно n раз;
• хвост: после remove_if элементы в [new_end, end) находятся в валидном, но неопределённом состоянии, а размер вектора пока прежний;
• erase: уничтожает хвост и уменьшает size(). capacity() не меняется, буфер не перевыделяется, итераторы до точки удаления остаются валидными;
• цена перемещения: для std::string или std::unique_ptr это перестановка указателей без копирования данных, для тривиальных типов вроде int просто запись в память.

Если интервьюер настаивает, что остальные элементы трогать нельзя вообще, честный ответ: у вектора с сохранением порядка так не бывает, непрерывный буфер обязан сдвигаться. Варианты: без сохранения порядка менять удаляемый элемент с последним и делать pop_back, это O(1) на элемент; либо взять std::list, где remove_if перевешивает узлы и значения не двигает.

Где спотыкаются

Вызывают v.erase(it) в цикле для каждого подходящего элемента. Каждый вызов сдвигает весь хвост, итог O(n²), а без it = v.erase(it) ещё и работа с инвалидированным итератором.

Забывают erase после remove_if и удивляются, что размер вектора не изменился, а в конце лежат непонятные значения. Алгоритм знает только итераторы и уменьшить контейнер не может.

Ждут, что память освободится. capacity() остаётся прежней, вернуть лишнее можно через shrink_to_fit(), и это лишь необязывающий запрос к реализации.