1. Зачем нужна идиома erase-remove
Иногда кажется, что удаление — это самая простая операция в программировании: «ну не нравится элемент — убери его». На практике именно удаление из std::vector часто становится источником странных багов: кто-то пропал, кто-то пропустился, а кто-то вообще удалился «через раз». Причина в том, что vector хранит элементы подряд, и любое массовое удаление — это почти всегда история про сдвиги, инвалидирование итераторов и ненамеренную квадратичную сложность.
Представьте, что у вас есть список задач, и вы хотите убрать все выполненные. Или список строк, и вы хотите убрать все пустые. Или список чисел, и вы хотите удалить все чётные. Это не «удалить один элемент», это «удалить целую категорию» — то есть массовая фильтрация.
И вот здесь нам нужна стандартная, каноническая, узнаваемая всеми C++-программистами идиома:
remove_if + erase — она же erase-remove.
Почему много erase подряд — плохая идея
Сейчас будет важная подводка. Если вы удаляете один элемент из середины vector, то все элементы правее сдвигаются влево на одну позицию. Для одной операции это нормально: да, есть сдвиг, но он предсказуем.
Проблема начинается, когда вы делаете так много раз: «нашёл элемент — erase, нашёл следующий — erase, …». Получается, что вы снова и снова гоняете хвост туда-сюда, как будто двигаете шкаф по комнате, чтобы достать носок за ним, а потом снова двигаете шкаф, чтобы достать второй носок. Работает, но соседи снизу начинают стучать по батарее.
Мини-иллюстрация (не делайте так как основной способ массового удаления):
#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
for (std::size_t i = 0; i < v.size(); ++i) {
if (v[i] % 2 == 0) {
v.erase(v.begin() + static_cast<long long>(i)); // опасная идея
}
}
}
Код выглядит «логично», но на практике тут легко получить пропуски, потому что после erase элементы сдвинулись, а i увеличивается как будто ничего не произошло.
Нам нужен подход, где мы делаем минимум сдвигов и не ломаем обход.
2. Как работает std::remove_if и что такое new_end
std::remove_if — «логическое удаление» без изменения size()
Теперь переходим к центральному персонажу лекции: std::remove_if.
Важно настроить правильную модель в голове:
remove_if не удаляет элементы из контейнера физически. Он не вызывает erase, не меняет размер вектора, не освобождает память. Вместо этого он делает «уплотнение»: перемещает элементы, которые мы хотим оставить, в начало диапазона, а затем возвращает итератор на «новый конец» результата.
То есть, он делает примерно такую идею:
- «Хорошие» элементы — в начало
- «Мусор/хвост» — в конец
- Возвращаем new_end, чтобы вы знали, где заканчиваются «хорошие»
Пример на чётных числах:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
auto new_end = std::remove_if(v.begin(), v.end(),
[](int x) { return x % 2 == 0; });
std::cout << "size = " << v.size() << '\n'; // size = 6
for (auto it = v.begin(); it != new_end; ++it) {
std::cout << *it << ' ';
}
std::cout << '\n'; // 1 3 5
}
Обратите внимание: size() остался прежним. Это и есть ключевой признак, что удаление «логическое».
new_end и «хвост», который нельзя считать данными
Сейчас будет важный момент, из-за которого у новичков чаще всего рождаются баги уровня «оно работало… пока я не поменял компилятор».
new_end — это итератор, который указывает на позицию сразу после последнего оставшегося элемента. То есть диапазон результата — это строго:
[v.begin(), new_end)
А вот диапазон:
[new_end, v.end())
— это уже не «ваши данные». Там могут быть старые значения, перемешанные значения, какие-то moved-from объекты (в случае сложных типов). Это не ошибка, это нормальная часть контракта: remove_if не обязан делать хвост красивым. Его задача — собрать «хорошие» элементы в начале и вернуть границу.
Чтобы почувствовать это руками, можно вывести весь вектор после remove_if и отдельно вывести «полезную часть»:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
auto new_end = std::remove_if(v.begin(), v.end(),
[](int x) { return x % 2 == 0; });
for (int x : v) std::cout << x << ' ';
std::cout << '\n'; // например: 1 3 5 4 5 6 (хвост не обязателен “логичный”)
for (auto it = v.begin(); it != new_end; ++it) std::cout << *it << ' ';
std::cout << '\n'; // 1 3 5
}
Первую строку вывода не пытайтесь «интерпретировать» как результат фильтрации. Результат — только до new_end.
4. Шаг №2: erase(new_end, end) — физическое удаление
Раз remove_if только «подготовил» вектор (уплотнил), нам нужен второй шаг — реально уменьшить размер вектора, отрезав хвост.
И вот здесь появляется erase в своей лучшей форме: удаление целого диапазона.
Выглядит это так:
v.erase(new_end, v.end());
Если соединить всё вместе:
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1, 2, 3, 4, 5, 6};
auto new_end = std::remove_if(v.begin(), v.end(),
[](int x) { return x % 2 == 0; });
v.erase(new_end, v.end());
for (int x : v) std::cout << x << ' ';
std::cout << '\n'; // 1 3 5
}
Теперь это уже настоящее удаление: размер изменился, «мусорного хвоста» нет, вектор содержит ровно нужные элементы.
5. Идиома erase-remove как готовый шаблон
В C++ есть конструкции, которые читаются как слова. Увидели — и сразу понимаете смысл. erase-remove — как раз такая конструкция.
Обычно она пишется компактно:
v.erase(
std::remove_if(v.begin(), v.end(), pred),
v.end()
);
То есть remove_if возвращает new_end, и мы тут же отдаём его в erase.
В реальном коде вы будете встречать именно такую форму, и важно, чтобы мозг не паниковал, а говорил: «А, это массовое удаление по условию».
Иногда ради читаемости делают в две строки (особенно в учебном коде и у новичков — это нормально):
auto new_end = std::remove_if(v.begin(), v.end(), pred);
v.erase(new_end, v.end());
Оба варианта корректны. Двухстрочный часто проще отлаживать и объяснять.
6. Предикат в remove_if: true означает «удалить»
Сейчас будет момент, где люди ошибаются особенно стабильно. В remove_if предикат отвечает на вопрос:
«Этот элемент нужно удалить?»
Если предикат вернул true, элемент считается удаляемым (то есть «плохим»). Если false — остаётся.
Из-за этого, если вы думаете в стиле «условие чтобы оставить», вы автоматически пишете наоборот.
Пример: «удалить пустые строки» — значит предикат должен быть s.empty():
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> v{"hi", "", "cpp", "", "ok"};
auto new_end = std::remove_if(v.begin(), v.end(),
[](const std::string& s) { return s.empty(); });
v.erase(new_end, v.end());
for (const auto& s : v) std::cout << "[" << s << "]\n";
// [hi]
// [cpp]
// [ok]
}
Здесь всё читается почти как русский язык: «remove_if… если строка пустая».
7. Схема двухшагового удаления
Иногда проще один раз увидеть процесс в виде схемы, чем десять раз прочитать «new_end, хвост, диапазон». Давайте визуализируем.
flowchart TD
A["vector: [1 2 3 4 5 6]"] --> B["remove_if: уплотняем 'оставшиеся' в начало"]
B --> C["new_end указывает на конец результата: [1 3 5 | ...хвост...]"]
C --> D["erase(new_end, end): отрезаем хвост"]
D --> E["vector: [1 3 5]"]
Идея именно такая: сначала «сжали», потом «отрезали».
8. Практика: мини-трекер задач
Сейчас сделаем самый практичный кусок лекции: применим erase-remove не на абстрактных числах, а на данных, похожих на реальные. Представим, что в предыдущих лекциях у нас уже появился простой трекер задач: мы храним задачи в std::vector, у задачи есть текст и флаг «выполнено».
Пусть модель (у вас она могла называться иначе) выглядит так:
#include <string>
struct Task {
std::string title;
bool done = false;
};
Теперь хотим реализовать «удалить все выполненные задачи». Это ровно массовое удаление по условию, а значит — erase-remove.
Функция получится короткой и приятной:
#include <algorithm>
#include <vector>
void remove_done_tasks(std::vector<Task>& tasks) {
auto new_end = std::remove_if(tasks.begin(), tasks.end(),
[](const Task& t) { return t.done; });
tasks.erase(new_end, tasks.end());
}
Обратите внимание на несколько вещей. Мы передаём tasks по ссылке, потому что хотим менять вектор. В предикате берём const Task&, потому что нам не нужно копировать задачу ради проверки. И читается это естественно: «удали, если done».
Можно сделать и однострочную форму (она тоже часто встречается в продакшене):
#include <algorithm>
#include <vector>
void remove_done_tasks(std::vector<Task>& tasks) {
tasks.erase(std::remove_if(tasks.begin(), tasks.end(),
[](const Task& t) { return t.done; }),
tasks.end());
}
Если вы пока не уверены, что ваш мозг комфортно читает такую «матрёшку», смело используйте двухстрочный вариант: он дружелюбнее к отладке и к человеку.
9. Полезные нюансы
Таблица-подсказка: что происходит с вектором на каждом шаге
Чтобы закрепить ощущение «где данные настоящие», полезно держать такую таблицу в голове:
| Состояние | Что в vector | Какой диапазон «валидных данных» |
|---|---|---|
| До remove_if | все элементы в исходном порядке | |
| После remove_if | «оставшиеся» сгруппированы в начале, хвост — мусор/остатки | |
| После erase(new_end, end) | вектор реально укорочен, хвоста нет | |
Вам не нужно помнить детали перестановок в хвосте. Вам нужно помнить только: после remove_if результат — до new_end.
Про std::erase_if и почему всё равно учим erase-remove
В современном C++ действительно существуют удобные «обёртки», которые делают удаление ещё короче (например, свободные erase/erase_if для контейнеров). Это обсуждалось и стандартизировалось отдельными предложениями в комитет C++ — например, идея «free erase[_if]» упоминается в отчётах/материалах WG21.
Но в учебной практике важно сначала освоить именно erase-remove, потому что это фундамент: вы начнёте узнавать его в чужом коде, понимать, что происходит с итераторами, и не путаться с «логическим» и «физическим» удалением. А уже потом любые сокращения будут восприниматься как приятный сахар сверху, а не как магия.
10. Типичные ошибки при remove_if и erase-remove
Ошибка №1: думать, что remove_if уже всё удалил.
Это самая частая логическая ошибка: программист вызывает remove_if, выводит вектор, видит «какую-то кашу» и решает, что алгоритм «сломался». На самом деле он сделал ровно то, что должен: сгруппировал оставшиеся элементы в начале и вернул new_end. Если вы не сделали erase(new_end, end), размер контейнера останется прежним, а хвост будет содержать значения, которые нельзя трактовать как часть результата.
Ошибка №2: стирать не тот диапазон: erase(begin, new_end) вместо erase(new_end, end).
Эта ошибка особенно обидная, потому что код компилируется и работает «вроде бы нормально», но делает противоположное: вы удаляете то, что хотели оставить. Модель здесь простая: new_end — это конец «хорошей» части, значит стирать нужно всё после него, то есть [new_end, end).
Ошибка №3: написать предикат «кого оставить», а не «кого удалить».
В remove_if true означает «удалить». Если вы по привычке пишете условие в стиле «оставь только положительные» и пишете x > 0, вы удалите как раз положительные. Лечится это либо переименованием (мысленно: should_remove(x)), либо честным вопросом к себе: «если я верну true, это улетит в мусор?».
Ошибка №4: использовать элементы из хвоста [new_end, end) как будто это данные.
Иногда после remove_if хочется «быстренько посмотреть весь вектор» или «пройтись по нему range-for». И вот тут появляется ложное ощущение, что хвост «что-то означает». Он не обязан означать ничего. Единственная граница смысла — new_end. Если вам нужно дальше работать со всем вектором как с корректным контейнером, сразу делайте erase(new_end, end).
Ошибка №5: смешать erase-remove с ручным удалением и получить нечитаемый код.
Очень частая эволюция новичка: сначала он делает erase-remove, потом добавляет ещё одно условие, потом ещё одно, потом внутри предиката появляются побочные эффекты, и всё превращается в мини-детектив. Если условия становятся сложными, лучше вынести их в отдельную функцию-предикат с понятным названием или хотя бы в аккуратную лямбду, которая отвечает только за «удалять/не удалять», а не за половину бизнес-логики приложения.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ