Інсертери: back_inserter / inserter і навіщо вони потрібні

1. Навіщо потрібні інсертери: проблема «куди записувати результат»

Уявіть ситуацію: у нас є контейнер‑джерело, і ми хочемо побудувати новий контейнер‑результат. Наприклад, ви берете список задач і хочете зібрати окремий список «термінових». Або берете список тегів і хочете отримати множину унікальних тегів. На рівні ідеї все звучить просто: «пройдіться вхідними даними й додайте потрібне в новий контейнер».

Але STL‑алгоритми влаштовані так, що вони не «знають» про контейнери напряму. Вони знають лише про ітератори: звідки читати й куди записувати. І ось тут постає головне питання лекції: а що таке «куди записувати», якщо контейнер іще порожній?

Якщо ви спробуєте написати: «Я ж кмітливий, візьму dst.begin()», то дуже швидко зʼясується неприємна правда: у порожнього vector немає елементів, а отже, немає коректного місця, куди можна присвоїти «наступний результат».

Саме для розвʼязання цієї практичної проблеми й існують інсертери: вони перетворюють «запис через ітератор» на «вставку в контейнер».

Мінімодель: як алгоритм записує у вихід

Давайте на 30 секунд уявимо, що ми самі пишемо алгоритм. Робити це всерйоз не будемо, але така модель дуже корисна. Типовий алгоритм, який «видає результат», подумки працює приблизно так:

*out = value;
++out;

Він не зобовʼязаний знати ні про push_back(), ні про size(), ні навіть про тип контейнера. Йому дали вихідний ітератор out — він і записує.

Проблема в тому, що для звичайного ітератора (наприклад, std::vector<int>::iterator) операція *out = value означає «перезаписати наявний елемент». Якщо контейнер порожній, такого елемента немає. Це як спроба покласти книжку на «третю полицю», коли шафи ви ще не купили. У повітрі вона тримається погано.

Дві стратегії запису результату

Є два основні підходи, які забезпечують коректний запис результату.

Перший підхід — заздалегідь створити елементи. Тобто зробити так, щоб «місце для запису» справді існувало. Зазвичай це означає resize(), а не reserve(). Тоді dst.begin() стає коректною точкою запису.

Другий підхід — не створювати елементи заздалегідь, а дозволити контейнеру зростати автоматично. Для цього й потрібні інсертери: 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. Вони й справді схожі… як «замовити стіл» і «запросити гостей». Стіл без гостей — порожній, але місце є.

Коротка таблиця відмінностей

reserve(n)

resize(n)

Пастка: 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? Принаймні варто зупинитися й перевірити намір.

Невелика схема: як інсертер зʼєднує алгоритм і контейнер

Іноді корисно один раз побачити картинку, щоб перестати сприймати це як магічне заклинання.

flowchart LR
    A["Вхідний діапазон<br/>[first, last)"] --> B["Алгоритм STL<br/>(копіює/фільтрує/перетворює)"]
    B --> C["Вихідний ітератор"]
    C -->|operator=| D["Контейнер результату"]

    C -->|back_inserter| E["push_back(...)"]
    C -->|inserter| F["insert(...)"]

Ідея проста: алгоритм виконує «звичайний запис», а інсертер перетворює його на правильний виклик контейнера.

5. Інсертери в навчальному застосунку: мініменеджер задач

Щоб приклади не висіли в повітрі, продовжімо нашу навчальну консольну програму — умовний менеджер задач. Раніше в нас уже були 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. Типові помилки під час роботи з інсертерами

Помилка № 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(...) не зобовʼязаний замінювати наявне значення. Дуже часто він просто нічого не зробить, бо ключ уже зайнятий. Інсертер не змінює правил контейнера: він лише доставляє елементи через правильний метод вставки. Якщо вам потрібно «перезаписати за ключем», це вже інша операція й інший контракт.

1

Опитування

Concepts глибше, рівень 58, лекція 4

Недоступний

Concepts глибше

Concepts глибше

Відкрити