Индексация данных: 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, "Learn C++", {"cpp", "study"}});

    if (auto it = tasks.find(1); it != tasks.end()) {
        std::cout << it->second.title << '\n'; // Learn 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. Это как “карточка каталога”, а не книга.

4. Операции без рассинхронизации

Когда появляется второй индекс, любая операция “создать объект” превращается в “создать объект + обновить индексы”. И вот здесь начинаются типичные ошибки: студент добавил задачу в 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 из старых тегов, потом добавить id в новые теги, и только потом записать новые теги внутрь Task. По сути это “переезд” из одного набора в другой. Снова делаем отдельную функцию, чтобы не размазывать логику по приложению.

#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;
}

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

5. Запросы и валидация

Индексы строятся не ради красоты, а ради запросов. Поэтому давайте сделаем две маленькие функции печати: одна печатает задачу по 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 << "no such task\n"; // no such task
    }
}

А вот запрос “покажи по тегу” использует вторичный индекс. Заметьте: вторичный индекс даёт нам набор 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 << "no such tag\n"; // no such tag
        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 << "Broken index: tag '" << tag
                          << "' refers to missing id=" << id << '\n';
                return false;
            }
        }
    }
    return true;
}

Если хочется, можно добавить и обратную проверку (из первичного в вторичный), но даже одна проверка уже дисциплинирует: вы начинаете воспринимать индексы как то, что нужно поддерживать, а не как “магическую оптимизацию”.

6. Типичные ошибки при работе с несколькими индексами

В этой теме большинство ошибок не “синтаксические”, а архитектурные: код компилируется, даже иногда работает, но данные постепенно превращаются в детектив. Поэтому ошибки лучше узнавать по симптомам и привычкам, а не только по сообщениям компилятора.

Ошибка №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"}, то при обновлении индексов вы делаете лишнюю работу, а при печати пользователь видит дубли и начинает подозревать вас в заговоре. Нормализация тегов (хотя бы удаление дублей) — маленькая вещь, но она сильно повышает качество данных и снижает количество “магических” багов.