Три стратегии удаления в std::vector

1. Введение

Когда человек говорит «удали элемент», мозг рисует что-то простое: взял — и удалил. Но std::vector — это не магическая коробка, где элементы висят в воздухе. Это плотный ряд ячеек памяти. Удаление почти всегда означает «подвинуть хвост», а значит — влияет на итераторы, индексы и даже на читаемость кода. Поэтому у нас не одна задача, а как минимум три разных сценария.

Первый сценарий — точечный: «удалить один конкретный элемент» (например, задачу по id). Второй — массовый: «удалить все элементы, которые подходят под условие» (например, все выполненные задачи). Третий — функциональный по духу: «построить новый список по правилам, не трогая исходный» (например, сделать список активных задач или список строк для печати). В каждом сценарии правильный инструмент будет разным — и именно это экономит вам часы отладки и делает код предсказуемым.

Чтобы это было не абстракцией, продолжим наш мини-проект: консольный трекер задач. Храним задачи в std::vector, у каждой есть id, title и статус.

#include <string>

enum class TaskStatus { Todo, Done };

struct Task {
    int id{};
    std::string title;
    TaskStatus status{TaskStatus::Todo};
};

2. Стратегия №1: точечное удаление через erase

Если вам нужно удалить ровно один элемент, чаще всего самый читаемый вариант — это найти его и стереть. Звучит тривиально, но тут важна дисциплина: мы удаляем не по «индексу, который где-то запомнили», а по итератору, который получили прямо сейчас. Это снижает шанс случайно стереть «не то» после других операций со списком.

Начнём с функции поиска. Мы уже умеем std::find_if, и лямбды тоже знакомы — значит, читается это вполне по-человечески.

#include <algorithm>
#include <vector>

bool remove_task_by_id(std::vector<Task>& tasks, int id) {
    auto it = std::find_if(tasks.begin(), tasks.end(),
                           [id](const Task& t) { return t.id == id; });

    if (it == tasks.end()) return false;
    tasks.erase(it);
    return true;
}

Обратите внимание на важную мелочь: мы проверяем it != end(). Это не «перестраховка», это нормальный контракт STL: end() разыменовывать нельзя, стирать через него нельзя, и вообще это граница, а не элемент.

Иногда у новичков возникает желание сделать так: «ну я же знаю индекс, давайте erase(begin() + idx)». Оно действительно работает, но ровно до того момента, пока индекс не станет вычисляться «по старым данным». В проекте это часто выглядит так: вы нашли индекс, потом где-то между делом удалили другой элемент, а затем стираете по старому индексу. Получается удаление «с сюжетом»: вроде просили убрать задачу "Buy milk", а исчезла "Pay rent". И, как ни странно, компилятор не возражает.

Если вы всё-таки работаете с индексом, то хотя бы переводите его в итератор непосредственно перед удалением и держите это в одной функции, чтобы не было «индекса-путешественника».

#include <vector>

bool remove_task_by_index(std::vector<Task>& tasks, std::size_t idx) {
    if (idx >= tasks.size()) return false;
    tasks.erase(tasks.begin() + static_cast<std::ptrdiff_t>(idx));
    return true;
}

Здесь мы сознательно проверяем границы, и да, приведение типа выглядит чуть «канцелярски». Это как раз намёк, что вариант с find_if часто проще и безопаснее.

Ещё один важный момент про «стоимость по интуиции». Одна операция erase(it) в vector почти всегда означает, что элементы правее удалённого сдвинутся на одну позицию влево. То есть это не O(1) «щелчок», а операция со сдвигом хвоста. Но если вы делаете это один раз — это нормально. Проблемы начинаются, когда вы делаете это сотни раз в цикле. Тогда добро пожаловать в следующий раздел.

3. Стратегия №2: массовое удаление через erase-remove

Когда нужно удалить все элементы по условию, «наивный» путь выглядит так: пройтись циклом и делать erase каждый раз, когда условие истинно. Иногда это ещё и пытаются писать в range-for (что совсем грустно). И даже если вы правильно напишете итераторный цикл, у вас остаётся вторая проблема: вы будете делать много сдвигов хвоста. Чем больше удалений — тем больше «перетасовки» элементов, а значит, тем ближе вы к скрытому O(N²) по ощущениям.

Идиома erase-remove решает это аккуратно: сначала мы одним проходом группируем «хорошие» элементы в начале, а потом одним erase отрезаем хвост. То есть вместо десятков/сотен сдвигов мы делаем один «массовый сдвиг» (на деле — перемещения/присваивания элементов) и одно реальное уменьшение размера.

Представим задачу: удалить все задачи со статусом Done.

#include <algorithm>
#include <vector>

int remove_done_tasks(std::vector<Task>& tasks) {
    auto new_end = std::remove_if(tasks.begin(), tasks.end(),
                                  [](const Task& t) {
                                      return t.status == TaskStatus::Done;
                                  });

    int removed = static_cast<int>(tasks.end() - new_end);
    tasks.erase(new_end, tasks.end());
    return removed;
}

Заметьте важную «философию» предиката: remove_if спрашивает не «кого оставить», а «кого удалить». Если лямбда возвращает true, элемент считается «плохим» и будет вытеснен в хвост.

Очень полезно держать в голове картинку:

До remove_if:
[ A ][ B ][ C ][ D ][ E ][ F ]

После remove_if (логически):
[ A ][ C ][ E ][ ? ][ ? ][ ? ]
                ^ new_end

После erase(new_end, end):
[ A ][ C ][ E ]

Знаки вопроса — это не мусор в смысле «сломанная память», но это точно не «ваши актуальные данные». Там могут быть старые значения, дубликаты, что угодно, и читать их как результат нельзя.

Ещё одна бытовая тонкость: после remove_if размер tasks.size() не меняется. Если вы забыли второй шаг erase, то на печати вы можете увидеть «странные хвосты». И студент обычно говорит: «у меня remove_if не работает». На самом деле он работает, просто вы остановились на полпути.

Если хотите сделать печать результата сразу после remove_if, то печатайте только диапазон [begin, new_end).

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

void debug_print_prefix(const std::vector<Task>& tasks) {
    auto new_end = std::remove_if(tasks.begin(), tasks.end(),
                                  [](const Task& t) {
                                      return t.status == TaskStatus::Done;
                                  });

    for (auto it = tasks.begin(); it != new_end; ++it) {
        std::cout << it->id << ": " << it->title << '\n';
    }
}

Да, это «отладочный» стиль: мы временно используем знание о new_end, чтобы убедиться, что логика работает.

4. Стратегия №3: rebuild — собрать новый результат

Иногда самая большая проблема удаления — не скорость и не инвалидирование, а читабельность. Особенно когда вокруг удаления появляются дополнительные правила: «удали выполненные, но только если они старше…», «удали пустые названия», «удали дубликаты…». Вы начинаете мутировать vector, параллельно следите за итератором, и в какой-то момент понимаете, что код выглядит как «осторожно, стекло» (и это ещё в хороший день).

Rebuild-подход означает: мы не трогаем исходный контейнер, а строим новый. Это похоже на то, как вы переписываете аккуратный конспект: старый лист не рвёте, а просто переносите нужное.

Фильтрация: copy_if и активные задачи

Допустим, нам нужен список только активных задач (статус Todo), а исходный список мы хотим сохранить как есть (например, для истории).

#include <algorithm>
#include <vector>

std::vector<Task> build_active_tasks(const std::vector<Task>& tasks) {
    std::vector<Task> active(tasks.size());

    auto out_end = std::copy_if(tasks.begin(), tasks.end(), active.begin(),
                                [](const Task& t) {
                                    return t.status == TaskStatus::Todo;
                                });

    active.erase(out_end, active.end());
    return active;
}

Да, здесь есть «двухшаговость», похожая на erase-remove, но смысл другой. Мы не «удаляем из старого», мы «собираем новое». А второй шаг erase(out_end, end) — это просто укоротить active, потому что мы заранее выделили максимум места.

Новички часто хотят написать std::vector<Task> active; и затем copy_if(..., active.begin(), ...). Но begin() у пустого вектора не указывает на место, куда можно писать. Поэтому мы либо заранее делаем нужный размер, либо используем техники записи через inserter-ы (но это будет отдельная тема в другом месте курса, сейчас не расползаемся).

Преобразование: transform и строки для печати

std::transform — это не про удаление, а про превращение одного набора данных в другой. Но в нашем «выборе стратегии» он идёт рядом с rebuild, потому что часто реальная задача звучит не «удали», а «сделай представление».

Например, хотим получить список строк для печати задач в формате "[id] title".

#include <algorithm>
#include <string>
#include <vector>

std::vector<std::string> build_task_lines(const std::vector<Task>& tasks) {
    std::vector<std::string> lines(tasks.size());

    std::transform(tasks.begin(), tasks.end(), lines.begin(),
                   [](const Task& t) {
                       return "[" + std::to_string(t.id) + "] " + t.title;
                   });

    return lines;
}

Здесь нет уменьшения размера, потому что transform делает «один к одному». Это чистое преобразование: сколько задач было — столько строк и стало.

Иногда очень удобно сочетать фильтрацию и преобразование в два шага: сначала build_active_tasks, потом build_task_lines. Это часто читается лучше, чем «один огромный цикл на 40 строк с if-ами».

5. Как выбрать стратегию: читаемость и «стоимость по интуиции»

Когда вы знаете три стратегии, хочется спросить: «а какая из них правильная?» Ответ слегка раздражающий, но честный: правильная та, которая соответствует задаче и делает код проще, а не хитрее. Мы не пишем код ради олимпиады по трюкам с итераторами. Мы пишем код, который через неделю прочитает человек (возможно, вы же, но уже уставший).

Ниже — таблица, которая обычно спасает от метаний «а вдруг надо erase-remove всегда?»:

Полезно также иметь в голове простую блок-схему выбора. Она не заменит мышление, но иногда спасает в момент «я уже запутался».

flowchart TD
    A[Нужно 'удалить'] --> B{Удаляем ровно 1 элемент?}
    B -- Да --> C["find_if + erase(it)"]
    B -- Нет --> D{"Нужно мутировать исходный vector?"}
    D -- Да --> E["remove_if + erase(new_end, end)"]
    D -- Нет --> F[rebuild: copy_if / transform]

Теперь пара слов про «сложность по интуиции». Если вы удаляете элементы по одному много раз, vector будет много раз двигать хвост. Это похоже на ситуацию, когда вы пытаетесь вытащить из середины книжной полки каждую третью книгу, но после каждого вытаскивания аккуратно сдвигаете остальные, чтобы не было дырки. Можно, но получится долго и нервно.

Поэтому «много одиночных erase» — это запах кода. Иногда он оправдан (например, удаляем пару элементов по пользовательским командам), но если вы массово чистите контейнер — идиома erase-remove обычно выигрывает и по скорости, и по выразительности.

6. Мини-проект: команды удаления в TaskTracker

Чтобы закрепить выбор стратегии, представим, что у нашего TaskTracker есть три команды: удалить по id, очистить выполненные, и показать только активные (не удаляя их из базы).

Ниже — маленькие функции, которые можно вызывать из вашего меню/цикла обработки команд (сам цикл мы здесь не расписываем, он у вас уже был в предыдущих днях).

Удаление одной задачи по id (точечная стратегия):

#include <iostream>
#include <vector>

void cmd_delete_by_id(std::vector<Task>& tasks, int id) {
    if (remove_task_by_id(tasks, id)) {
        std::cout << "Deleted task id=" << id << "\n";
    } else {
        std::cout << "No task with id=" << id << "\n";
    }
}

Массовая очистка выполненных (erase-remove):

#include <iostream>
#include <vector>

void cmd_clear_done(std::vector<Task>& tasks) {
    int removed = remove_done_tasks(tasks);
    std::cout << "Removed done tasks: " << removed << "\n";
}

Показать активные (rebuild через copy_if):

#include <iostream>
#include <vector>

void cmd_show_active(const std::vector<Task>& tasks) {
    auto active = build_active_tasks(tasks);
    for (const auto& t : active) {
        std::cout << t.id << ": " << t.title << "\n";
    }
}

И, если хочется «красивый вывод» отдельным списком строк (rebuild через transform):

#include <iostream>
#include <vector>

void cmd_print_lines(const std::vector<Task>& tasks) {
    auto lines = build_task_lines(tasks);
    for (const auto& line : lines) {
        std::cout << line << "\n";
    }
}

Обратите внимание на приятный эффект: каждая команда читается как одна мысль. Внутри — вызов правильной стратегии. Это и есть цель сегодняшней лекции: не “знать remove_if”, а уметь выбирать форму решения так, чтобы код был спокойным.

7. Типичные ошибки при выборе стратегии удаления

Ошибка №1: использовать точечный erase в массовой задаче и получить “скрытый квадратичный ад”.
Когда нужно удалить половину элементов, а вы делаете erase много раз, vector снова и снова сдвигает хвост. Код может выглядеть коротко и «логично», но работать будет всё хуже по мере роста данных. Как лечится: если удаляете много по условию — почти всегда это erase-remove (remove_if + erase).

Ошибка №2: считать, что remove_if “уже удалил” элементы из vector.
После remove_if реальный результат — только в префиксе [begin, new_end), а size() прежний. Если забыть erase(new_end, end), вы увидите “хвост” и решите, что алгоритм сломан. Как лечится: помнить двухшаговость — сначала логически сжали, потом физически укоротили.

Ошибка №3: путать “кого удалить” и “кого оставить” в предикате remove_if.
В remove_if предикат возвращает true для тех, кто должен уйти. Новички часто пишут «условие оставить», а потом удивляются, что удалилось ровно нужное. Как лечится: проговаривать предикат словами: “return true, если элемент плохой”.

Ошибка №4: строить новый vector через copy_if, но не подготовить место под запись.
std::copy_if пишет в выходной диапазон. Если вы сделали std::vector<Task> dst; и передали dst.begin(), запись идёт “в никуда”. Как лечится в рамках текущих тем курса: заранее делать dst(src.size()), затем dst.erase(out_end, dst.end()).

Ошибка №5: смешивать мутацию и чтение так, что логика становится хрупкой.
Очень типичный “комбайн”: в одном цикле вы печатаете, удаляете, считаете статистику, и ещё где-то обновляете индексы. Это трудно тестировать и легко сломать. Как лечится: разделить задачи. Если нужно именно удалить — используйте одну из трёх стратегий, а сбор статистики/печать делайте отдельным проходом или через отдельные функции.