Індексація даних: id → обʼєкт, тег → список

1. Індекси даних

Уявіть, що ви зберігаєте задачі у std::vector<Task> і щоразу, коли потрібно знайти задачу за id, просто перебираєте весь вектор циклом. Це працює… але лише доти, доки задач не стане багато, а запитів — ще більше. Індекс — це структура даних, яка пришвидшує типовий запит: «знайди мені обʼєкт за ключем». У реальній розробці саме індекси роблять застосунки швидкими, але водночас додають новий головний біль: їх потрібно підтримувати узгодженими.

Уявімо просту побутову аналогію. У бібліотеці є книги на полицях — це «справжні обʼєкти», а ще є каталог за авторами і каталог за назвами — це «індекси». Якщо бібліотекар додав книгу на полицю, але забув внести її до каталогу, читач вирішить, що книги немає. Якщо ж навпаки: запис у каталозі є, а книги на полиці немає, — читач піде шукати «привида». Саме так і виникає неузгодженість індексів.

Модель даних: Task і «джерело правди»

Щоб говорити предметно, візьмімо невелику модель даних. Нехай у нас є мінізастосунок TaskBook: ми зберігаємо задачі, і кожна має числовий id, текстовий title і набір тегів, наприклад "cpp", "study", "home". Ми не будуємо складної архітектури: жодних зайвих класів і «магії», лише struct та контейнери STL, з якими ви вже вмієте працювати.

Важливо заздалегідь домовитися про один принцип: одне джерело правди. Це означає, що справжній обʼєкт Task ми зберігаємо в одному місці, а в індексі — лише посилання на нього, наприклад id. Тоді під час зміни задачі не доведеться «синхронізувати дві копії обʼєкта»: достатньо лише оновити індекси, які на нього посилаються.

Почнімо з моделі:

#include <string>
#include <vector>

struct Task {
    int id{};
    std::string title;
    std::vector<std::string> tags;
};

Тут tags — саме vector, бо так зручніше виводити й перебирати теги. Їхню унікальність ми забезпечимо окремо, трохи згодом, щоб не зберігати "cpp", "cpp", "cpp" — таке справді трапляється, особливо якщо користувач уводить теги вручну.

2. Індекси: первинний і вторинний

Первинний індекс id → Task: швидкий доступ до обʼєкта

Первинний індекс — це місце, де зберігаються «справжні» обʼєкти. Найпростіший і найзрозуміліший варіант: std::unordered_map<int, Task> tasksById; Тоді за id ми швидко отримуємо задачу без лінійного пошуку. Ми не обговорюємо «ідеальну» складність і внутрішню будову геш-таблиці — зараз нам важливіше інше: замість «пробігти все» ми переходимо до «знайти за ключем».

Запровадьмо типи — так код читається краще, і очі менше втомлюються:

#include <unordered_map>

using TaskId = int;
using TaskById = std::unordered_map<TaskId, Task>;

Тепер покажімо базовий шаблон читання: find → перевірити → використати. Зверніть увагу: це читання без побічних ефектів — ми нічого випадково не створюємо.

#include <iostream>
#include <unordered_map>

int main() {
    TaskById tasks;
    tasks.emplace(1, Task{1, "Вивчити C++", {"cpp", "study"}});

    if (auto it = tasks.find(1); it != tasks.end()) {
        std::cout << it->second.title << '\n'; // Вивчити C++
    }
}

І ще окремо проговорімо важливу думку — вона справді заощаджує години налагодження: якщо ви хочете прочитати, використовуйте find/contains. operator[] застосовуйте тоді, коли ви точно хочете «створити або оновити».

Вторинний індекс tag → список id: швидкий пошук за категорією

Тепер додаймо ще один тип запитів: «покажи всі задачі з тегом cpp». Якщо в нас є лише tasksById, доведеться перебрати всі задачі й перевірити, чи є потрібний тег усередині Task::tags. Це знову лінійний прохід по всіх задачах, і на великих даних він працюватиме повільно.

Тому вводимо вторинний індекс: tag → список id. Чому не tag → список Task? Тому що ми домовилися про одне джерело правди: Task живе в tasksById, а індекс зберігає лише посилання на нього у вигляді id.

Вибір контейнера для «списку id» залежить від вимог. Для навчального прикладу зручно взяти std::unordered_set<int>: він автоматично прибирає дублікати, а перевірка «чи є id у множині» теж буде швидкою. Якби для нас був важливий порядок або потрібні були повтори, можна було б взяти std::vector<int>, але тоді довелося б вручну прибирати дублікати. Для початку оберемо надійний варіант.

#include <string>
#include <unordered_map>
#include <unordered_set>

using Tag = std::string;
using IdSet = std::unordered_set<TaskId>;
using TagIndex = std::unordered_map<Tag, IdSet>;

Структури даних нашого застосунку тепер концептуально виглядають так:

flowchart LR
    subgraph Primary["Первинний індекс (джерело правди)"]
        A["tasksById: id → Task"]
    end

    subgraph Secondary["Вторинний індекс (посилання)"]
        B["tagToIds: tag → {id, id, id}"]
    end

    B -->|"id"| A

Корисно памʼятати: у вторинному індексі ми не зберігаємо задачу, ми зберігаємо «вказівник» на неї через id. Це як картка каталогу, а не сама книга.

3. Операції без розсинхронізації

Коли зʼявляється другий індекс, будь-яка операція «створити обʼєкт» перетворюється на «створити обʼєкт і оновити індекси». І саме тут починаються типові помилки: студент додав задачу в tasksById, але забув додати її id у tagToIds, а потім дивується, чому пошук за тегом «нічого не знаходить».

Щоб не розмножувати такі помилки по всьому коду, введімо просту дисципліну: усі зміни даних проходять через одну функцію. Нехай це буде AddTask(...). Так, це звучить нудно. Але нудний код зазвичай працює, а веселий зазвичай веселить лише компілятор.

Спочатку підготуємо невелику функцію, яка прибирає дублікати тегів. Зробимо це через unordered_set ненадовго, а потім повернемося до vector. Код невеликий, але зміст важливий: усередині Task теги будуть охайними.

#include <string>
#include <unordered_set>
#include <vector>

std::vector<std::string> MakeUniqueTags(const std::vector<std::string>& tags) {
    std::unordered_set<std::string> uniq(tags.begin(), tags.end());
    return std::vector<std::string>(uniq.begin(), uniq.end());
}

Узгоджене додавання: оновлюємо обидва індекси

Зверніть увагу: спочатку ми намагаємося вставити задачу в tasksById. Якщо id уже зайнятий, виходимо й більше нічого не змінюємо. Якщо вставка вдалася, оновлюємо tagToIds. Тут operator[] використовується свідомо: якщо такого тегу ще немає, ми хочемо створити для нього порожню множину.

#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>

bool AddTask(TaskById& tasksById, TagIndex& tagToIds, Task task) {
    task.tags = MakeUniqueTags(task.tags);

    auto [it, inserted] = tasksById.emplace(task.id, task);
    if (!inserted) return false;

    for (const std::string& tag : it->second.tags) {
        tagToIds[tag].insert(it->first);
    }
    return true;
}

Тут є приємний ефект: коду, який викликає цю функцію, взагалі не потрібно памʼятати, що в нас «два індекси». Він просто викликає AddTask, а функція виконує всю нудну роботу. Це і є маленький крок до хорошої архітектури — без гучних слів.

Узгоджене видалення: видаляємо так, щоб не залишилося «привидів»

Видалення — ще небезпечніша операція, ніж додавання. Бо помилка зазвичай виглядає так: ви видалили задачу з tasksById, але забули прибрати її id із tagToIds. Потім ви виконуєте запит «показати за тегом» — і отримуєте id, якого вже немає в первинному індексі. У цей момент ви натрапляєте на «примарну задачу»: індекс каже, що вона є, а реальність каже «ні».

Видалення має складатися з двох кроків: прибрати посилання з вторинних індексів, а потім прибрати сам обʼєкт. Порядок саме такий: спочатку чистимо «каталоги», а вже потім викидаємо «книгу з полиці». Ми знову оформлюємо це як одну функцію, щоб не повторювати логіку в десяти місцях.

#include <string>
#include <unordered_map>
#include <unordered_set>

bool RemoveTask(TaskById& tasksById, TagIndex& tagToIds, TaskId id) {
    auto it = tasksById.find(id);
    if (it == tasksById.end()) return false;

    for (const std::string& tag : it->second.tags) {
        if (auto jt = tagToIds.find(tag); jt != tagToIds.end()) {
            jt->second.erase(id);
            if (jt->second.empty()) tagToIds.erase(jt);
        }
    }
    tasksById.erase(it);
    return true;
}

Тут є маленька естетика: якщо після видалення id множина стала порожньою, ми видаляємо сам тег з індексу. Це не обовʼязково, але зазвичай робить структуру чистішою: не буде «тегів, у яких немає задач».

Зміна даних: як безпечно змінювати теги й назву

Найчастіше індекси розсинхронізовуються саме під час змін. Назву (title) можна змінювати без проблем: вона поки що не бере участі в нашому індексі. А от теги — це основа вторинного індексу. Якщо ви змінили Task::tags, але не оновили tagToIds, вторинний індекс одразу стає хибним.

На практиці безпечне оновлення тегів виглядає так: ми прибираємо id зі старих тегів, нормалізуємо нові, записуємо їх усередину Task, а потім додаємо id до нових тегів. По суті, це «переїзд» з однієї множини в іншу. Знову робимо окрему функцію, щоб не розмазувати логіку по застосунку.

#include <string>
#include <vector>

bool UpdateTaskTags(TaskById& tasksById, TagIndex& tagToIds,
                    TaskId id, std::vector<std::string> newTags) {
    auto it = tasksById.find(id);
    if (it == tasksById.end()) return false;

    for (const std::string& tag : it->second.tags) {
        if (auto jt = tagToIds.find(tag); jt != tagToIds.end()) {
            jt->second.erase(id);
            if (jt->second.empty()) tagToIds.erase(jt);
        }
    }

    newTags = MakeUniqueTags(newTags);
    it->second.tags = newTags;

    for (const std::string& tag : it->second.tags) {
        tagToIds[tag].insert(id);
    }
    return true;
}

Якщо ви зараз подумали: «Ого, заради тегів стільки коду…» — це нормальна реакція. Індекси пришвидшують запити, але беруть «податок»: під час змін усе потрібно оновлювати охайно. У великих системах цей податок сплачують архітектурою й дисципліною, а в нас — акуратними функціями.

4. Запити та валідація

Індекси створюють не заради краси, а заради запитів. Тож зробімо дві невеликі функції виведення: одна показує задачу за id, інша — усі задачі за тегом. Одразу домовмося: ми не будуємо складне «красиве» виведення, нам важливо показати, як використовувати індекси.

Запити: «покажи за id» і «покажи за тегом»

Виведення однієї задачі:

#include <iostream>

void PrintTask(const Task& t) {
    std::cout << "#" << t.id << " " << t.title << " [";
    for (std::size_t i = 0; i < t.tags.size(); ++i) {
        std::cout << t.tags[i] << (i + 1 == t.tags.size() ? "" : ", ");
    }
    std::cout << "]\n";
}

Запит «покажи за id» — це просто find у первинному індексі:

#include <iostream>

void PrintById(const TaskById& tasksById, TaskId id) {
    if (auto it = tasksById.find(id); it != tasksById.end()) {
        PrintTask(it->second);
    } else {
        std::cout << "немає такої задачі\n"; // немає такої задачі
    }
}

А от запит «покажи за тегом» використовує вторинний індекс. Зверніть увагу: вторинний індекс дає нам множину id, а потім для кожного id ми звертаємося до tasksById і беремо обʼєкт. Це і є «одне джерело правди» в дії.

#include <iostream>
#include <string>

void PrintByTag(const TaskById& tasksById, const TagIndex& tagToIds,
                const std::string& tag) {
    auto it = tagToIds.find(tag);
    if (it == tagToIds.end()) {
        std::cout << "немає такого тегу\n"; // немає такого тегу
        return;
    }

    for (TaskId id : it->second) {
        if (auto jt = tasksById.find(id); jt != tasksById.end()) {
            PrintTask(jt->second);
        }
    }
}

Зверніть увагу на цю «параною»: навіть якщо індекс має бути узгодженим, ми однаково перевіряємо tasksById.find(id). В ідеальному світі можна було б цього не робити, але в навчальному коді така перевірка допомагає «пережити» баг розсинхронізації й побачити проблему, а не провалитися в невідомість.

Перевірка узгодженості: інваріанти та проста валідація

Коли індексів стає більше ніж один, корисно сформулювати «залізні правила», які завжди мають залишатися істинними. У програмуванні такі правила часто називають інваріантами. Якщо без формальної математики, то людською мовою:

Якщо в tagToIds["cpp"] лежить 42, то в tasksById обовʼязково має існувати задача з id 42. І навпаки: якщо задача 42 містить тег "cpp", то tagToIds["cpp"] теж має містити 42.

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

Зробімо просту перевірку «із вторинного в первинний» — на практиці вона виявляє більшість помилок:

#include <iostream>
#include <string>

bool ValidateTagIndex(const TaskById& tasksById, const TagIndex& tagToIds) {
    for (const auto& [tag, ids] : tagToIds) {
        for (TaskId id : ids) {
            if (!tasksById.contains(id)) {
                std::cout << "Пошкоджений індекс: тег '" << tag
                          << "' посилається на відсутній id=" << id << '\n';
                return false;
            }
        }
    }
    return true;
}

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

5. Типові помилки під час роботи з кількома індексами

У цій темі більшість помилок не синтаксичні, а архітектурні: код компілюється, інколи навіть працює, але дані поступово перетворюються на детектив. Тому помилки краще впізнавати за симптомами та звичками, а не лише за повідомленнями компілятора.

Помилка № 1: два джерела правди — дублювання обʼєктів в індексах.
Часто хочеться зробити tag → vector<Task>, «щоб було зручніше друкувати». Перші пів години справді зручно. Потім ви змінюєте title у задачі в tasksById, забуваєте оновити копію в другому місці — і раптом у вас дві різні реальності. Значно надійніше зберігати обʼєкт в одному місці, а в індексах — лише id.

Помилка № 2: оновили один індекс, забули про другий.
Це класика жанру: додали задачу в tasksById, але не внесли id у tagToIds; або видалили її з tasksById, але не вичистили tagToIds. Симптоми прості: «за id знаходиться, за тегом — ні» або «за тегом знаходиться id, але за id задачі немає». Лікується дисципліною: усі операції виконуються через функції на кшталт AddTask/RemoveTask/UpdateTaskTags.

Помилка № 3: читають через operator[] і випадково створюють порожні записи.
Наприклад, код tagToIds[tag] у режимі читання створить новий тег із порожньою множиною id, і потім ви думатимете, звідки взялися ці дивні порожні теги. Якщо ви читаєте — використовуйте find/contains. operator[] залишайте для випадків, коли створення за відсутності — бажана поведінка, як у AddTask.

Помилка № 4: не прибирають «порожні» ключі у вторинному індексі.
Якщо після видалення id з tagToIds[tag] множина стала порожньою, а ви залишили порожній запис, логіка зазвичай не ламається, але структура даних починає «засмічуватися»: зʼявляються теги, у яких немає задач. Це особливо помітно в застосунках, де теги показуються користувачу списком. Очищення порожніх ключів робить поведінку охайнішою й передбачуванішою.

Помилка № 5: теги всередині Task містять дублікати, і індекс починає жити «дивно».
Якщо в задачі теги {"cpp", "cpp"}, то під час оновлення індексів ви виконуєте зайву роботу, а під час друку користувач бачить дублікати й починає підозрювати вас у змові. Нормалізація тегів, бодай видалення дублікатів, — маленька річ, але вона помітно підвищує якість даних і зменшує кількість «магічних» багів.