1. Зачем нужны inserter‑ы: проблема «куда писать результат»
Представьте ситуацию: у нас есть контейнер‑источник, и мы хотим построить новый контейнер‑результат. Например, мы берём список задач и хотим собрать отдельный список «срочных». Или берём список тегов и хотим получить множество уникальных тегов. На уровне идеи это звучит просто: «пройди по исходным данным и добавь подходящее в новый контейнер».
Но STL‑алгоритмы устроены так, что они не «знают» про контейнеры напрямую. Они знают только про итераторы: откуда читать и куда писать. И вот тут появляется главный вопрос лекции: а что такое “куда писать”, если контейнер ещё пустой?
Если вы попробуете написать «ну я же умный, возьму dst.begin()», то очень быстро выяснится неприятная правда: у пустого vector нет элементов, а значит нет валидного места, куда можно присвоить «следующий результат».
Именно для решения этой практической проблемы существуют inserter‑ы: они превращают «запись через итератор» в «вставку в контейнер».
Мини‑модель: как алгоритм пишет в выход
Давайте на 30 секунд представим, что мы пишем алгоритм сами (мы не будем делать это всерьёз, но модель очень полезная). Типичный алгоритм, который «выдаёт результат», мысленно делает примерно такое:
*out = value;
++out;
Он не обязан знать, что такое push_back(), где size(), и какой у контейнера тип. Ему дали выходной итератор out — он и пишет.
Проблема в том, что для обычного итератора (например, std::vector<int>::iterator) операция *out = value означает «перезаписать существующий элемент». А если контейнер пустой, «существующего элемента» нет. Это как попытаться положить книгу на «третью полку», когда шкаф вы ещё не купили. В воздухе держится плохо.
Две стратегии записи результата
Есть два больших подхода, как обеспечить корректную запись результата.
Первый подход — заранее создать элементы, то есть сделать так, чтобы «место для записи» реально существовало. Обычно это означает resize(), а не reserve(). Тогда dst.begin() становится валидным выходом.
Второй подход — не создавать элементы заранее, а позволить контейнеру расти автоматически. Для этого и нужны inserter‑ы: std::back_inserter и std::inserter.
В этой лекции мы сфокусируемся именно на втором подходе, потому что он чаще всего проще для новичка и даёт очень хороший «STL‑стиль»: алгоритм не заботится о росте контейнера, а контейнер растёт через свой нормальный интерфейс.
2. std::back_inserter: запись в конец через push_back()
Когда вы пишете:
std::back_inserter(dst)
вы получаете специальный объект‑итератор (по сути, адаптер), который при «присваивании через *it = value» делает dst.push_back(value).
То есть вместо «перезаписать элемент по адресу» получается «добавить новый элемент».
Самый короткий пример: ручная запись через back_inserter
Важно почувствовать механику, поэтому сначала без алгоритмов — просто руками:
#include <iostream>
#include <iterator>
#include <vector>
int main() {
std::vector<int> dst;
auto out = std::back_inserter(dst);
*out = 10; // эквивалентно dst.push_back(10)
*out = 20; // эквивалентно dst.push_back(20)
std::cout << dst.size() << '\n'; // 2
}
Обратите внимание на «магический» момент: у dst не было элементов, но *out = 10 всё равно сработал, потому что это не обычный итератор vector, а «вставляющий» итератор.
Типичная ситуация: скопировать в пустой vector
Теперь, когда у нас есть «куда писать», мы можем подключить алгоритм. Например, std::copy:
#include <algorithm>
#include <iterator>
#include <vector>
int main() {
std::vector<int> src{1, 2, 3};
std::vector<int> dst;
std::copy(src.begin(), src.end(), std::back_inserter(dst));
}
Если бы мы написали dst.begin() вместо std::back_inserter(dst), то код был бы либо ошибочным логически, либо приводил бы к неопределённому поведению (в зависимости от конкретного случая). back_inserter делает намерение явным: «результат дописывается в конец».
reserve() vs resize() рядом с back_inserter
Когда вы впервые сталкиваетесь с back_inserter, очень легко перепутать две похожие по названию операции: reserve и resize. Они действительно похожи… как «заказать стол» и «пригласить гостей». Стол без гостей — пусто, но место есть.
Короткая таблица различий
| Операция | Что меняется | Что НЕ меняется | Когда использовать |
|---|---|---|---|
|
capacity() (обычно) | size() не меняется | Чтобы push_back()/back_inserter делали меньше перевыделений |
|
size() меняется, появляются элементы | capacity() может вырасти, но смысл не в этом | Когда хотите писать в begin()/по индексам в уже существующие элементы |
Ловушка: reserve не создаёт элементы
Смотрите на пример — он очень короткий, но ловит половину начинающих:
#include <algorithm>
#include <vector>
int main() {
std::vector<int> src{1, 2, 3};
std::vector<int> dst;
dst.reserve(src.size()); // место есть, элементов нет
// std::copy(src.begin(), src.end(), dst.begin()); // НЕЛЬЗЯ: dst.begin() не указывает на существующие элементы
}
reserve полезен, но он не делает dst.begin() «местом для записи». Если вы хотите писать в begin(), нужен resize. Если вы хотите писать через back_inserter, reserve — это приятный бонус для производительности, но не обязательная часть корректности.
Правильная пара: reserve + back_inserter
Вот так — корректно и обычно быстро:
#include <algorithm>
#include <iterator>
#include <vector>
int main() {
std::vector<int> src{1, 2, 3};
std::vector<int> dst;
dst.reserve(src.size()); // меньше перевыделений
std::copy(src.begin(), src.end(), std::back_inserter(dst));
}
3. std::inserter: вставка через insert()
std::back_inserter хорош, но он работает только там, где есть push_back. А теперь маленький сюжетный поворот: у std::set и std::map нет push_back. Потому что это не «последовательность», а «структура с правилами» (упорядочивание, уникальность ключей, балансировка дерева и т.д.).
И вот тут появляется std::inserter(container, pos).
Он создаёт итератор, который при «записи» делает container.insert(value) (в варианте «с подсказкой позиции», но для начинающего можно думать как «вставь в контейнер»).
Кстати, в стандартной библиотеке inserter и insert_iterator находятся в namespace std — это не «какая-то магия компилятора», а обычные сущности STL.
Пример: собрать уникальные числа в std::set
#include <algorithm>
#include <iterator>
#include <set>
#include <vector>
int main() {
std::vector<int> src{3, 1, 2, 2, 3};
std::set<int> uniq;
std::copy(src.begin(), src.end(), std::inserter(uniq, uniq.end()));
}
Здесь std::set сам решит, что делать с дублями (в set они просто не добавятся). А алгоритм остаётся простым: «скопируй всё».
Пример: залить пары в std::map
Очень типичный случай: у нас есть пары «ключ→значение», и мы хотим собрать map.
#include <algorithm>
#include <iterator>
#include <map>
#include <string>
#include <utility>
#include <vector>
int main() {
std::vector<std::pair<int, std::string>> items{
{2, "two"},
{1, "one"}
};
std::map<int, std::string> m;
std::copy(items.begin(), items.end(), std::inserter(m, m.end()));
}
Если ключи повторятся — map применит свои правила вставки (не всегда «перезапишет»). Важно понимать: inserter отвечает за способ доставки элемента, но не меняет семантику контейнера.
4. Как выбирать: back_inserter или inserter
Сейчас хочется дать «простое правило на все случаи», но честный ответ: правило простое, а жизнь — нет. Тем не менее, для начинающего есть очень рабочая эвристика.
Если контейнер умеет push_back и вам подходит порядок «как получится из алгоритма», то back_inserter — почти всегда лучший старт. Он читается так, как вы бы сказали вслух: «добавляй в конец».
Если контейнер не имеет push_back (например, set/map) или по смыслу вставка должна идти через insert (потому что контейнер сам решает место элемента), то берём inserter.
А если вы видите std::inserter(v, v.end()) для vector, то это обычно не ошибка, но часто странно: зачем insert, если есть push_back? Как минимум стоит остановиться и проверить намерение.
Небольшая схема: как inserter соединяет алгоритм и контейнер
Иногда полезно один раз увидеть картинку, чтобы мозг перестал пытаться запомнить это как магическое заклинание.
flowchart LR
A["Диапазон входа<br/>[first, last)"] --> B["Алгоритм STL<br/>(копирует/фильтрует/преобразует)"]
B --> C["Выходной итератор"]
C -->|operator=| D["Контейнер результата"]
C -->|back_inserter| E["push_back(...)"]
C -->|inserter| F["insert(...)"]
Идея простая: алгоритм делает «обычную запись», а inserter превращает её в правильный вызов контейнера.
5. Inserter‑ы в учебном приложении: мини‑менеджер задач
Чтобы примеры не были «в вакууме», давайте продолжим нашу учебную консольную программу — условный менеджер задач. Ранее у нас уже появлялись struct, vector, строки и простая логика. Сегодня добавим две функции: собрать срочные задачи в отдельный список и собрать множество тегов.
Модель задачи
#include <string>
#include <vector>
struct Task {
std::string title;
int priority = 0; // чем больше — тем важнее
std::vector<std::string> tags; // например: "study", "home"
};
Собираем срочные задачи: back_inserter
Здесь результат — это новый vector<Task>, и мы хотим просто дописывать в конец.
#include <iterator>
#include <vector>
std::vector<Task> CollectUrgent(const std::vector<Task>& tasks, int minPriority) {
std::vector<Task> urgent;
urgent.reserve(tasks.size()); // верхняя оценка, не точный размер
for (const auto& t : tasks) {
if (t.priority >= minPriority) {
*std::back_inserter(urgent) = t; // urgent.push_back(t);
}
}
return urgent;
}
Да, здесь можно было написать urgent.push_back(t) напрямую. Но мы сознательно показываем мысль: «у меня есть выход, куда можно писать единым способом». Это мышление сильно помогает, когда вместо цикла появится алгоритм, или когда «выход» будет переключаться между vector и set.
Собираем уникальные теги: inserter + set
С тегами нам важна уникальность, значит контейнер‑результат — std::set<std::string>.
#include <iterator>
#include <set>
#include <string>
#include <vector>
std::set<std::string> CollectAllTags(const std::vector<Task>& tasks) {
std::set<std::string> tags;
for (const auto& t : tasks) {
for (const auto& tag : t.tags) {
*std::inserter(tags, tags.end()) = tag; // tags.insert(tag);
}
}
return tags;
}
Опять же, можно было бы вызвать tags.insert(tag) напрямую. Но теперь код подчёркивает общий паттерн: «пишем результат через итератор». А когда вы начнёте активно использовать алгоритмы, эта привычка станет вашим «анти‑костылём».
6. Типичные ошибки при работе с inserter‑ами
Ошибка №1: писать в dst.begin(), когда dst пустой.
Это классическая проблема «путаю контейнер с памятью». Итератор begin() — это не «портал в будущее», он указывает на существующий элемент или на end() у пустого контейнера. Если элементов нет, присваивать некуда. В таких ситуациях либо делайте resize (создавая элементы), либо используйте std::back_inserter/std::inserter.
Ошибка №2: думать, что reserve() создаёт элементы.
reserve лишь увеличивает запас памяти под будущий рост. size() от этого не меняется, а значит «мест для записи» не появляется. Из-за этого появляются странные баги: «я же сделал reserve, почему копирование в begin() падает?». Ответ: потому что вы подготовили парковку, но не припарковали ни одной машины.
Ошибка №3: использовать back_inserter для контейнера без push_back.
У std::set и std::map нет push_back, поэтому std::back_inserter(set) просто не скомпилируется. Это не «каприз STL», а правильная защита от неверной модели данных: такие контейнеры не поддерживают «дописать в конец», потому что у них нет понятия «конца по порядку вставки».
Ошибка №4: передавать в std::inserter позицию от другого контейнера.
std::inserter(c, pos) требует, чтобы pos был итератором именно контейнера c. Если случайно передать итератор от другого контейнера (или устаревший итератор), получите либо ошибку компиляции, либо очень неприятное поведение. Самый безопасный и читаемый вариант для старта — почти всегда std::inserter(c, c.end()).
Ошибка №5: ожидать, что inserter перезапишет значение в map, если ключ уже есть.
map.insert(...) не обязан заменять существующее значение. Очень часто он просто ничего не сделает, потому что ключ уже занят. Inserter не меняет правила контейнера: он лишь доставляет элементы через правильный метод вставки. Если вам нужно «перезаписать по ключу», это уже другая операция и другой контракт.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ