Индексы и согласованность данных

1. Источник правды и инварианты

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

Представьте, что у нас есть маленькое CLI-приложение «мини-адресная книга». Пользователь может добавить контакт, найти по email, найти по тегу (например, "work"), удалить контакт, обновить имя. Если контактов 5 — линейный поиск по vector идеален. Если контактов 50 000 — линейный поиск станет вашей персональной медитацией на тему «а зачем я вообще открыл программу».

Индекс — это структура, которая ускоряет доступ. Простейшая формулировка:

Индекс — это отображение вида «ключ → где лежит объект».

Ключом может быть id, email, tag, а «где лежит объект» — это уже тонкий вопрос, потому что тут и начинается архитектура.

Источник правды: правило, которое спасает психику

Если вы запомните из этой лекции только одну мысль — пусть будет эта: объект должен жить в одном месте, и это место — «источник правды». Всё остальное — лишь производные структуры для ускорения.

Почему это важно? Потому что новичковая «оптимизация» обычно выглядит так: «О! Я хочу быстро искать по email и по тегам. Давайте сделаем unordered_map<string, Contact> для email и ещё unordered_map<string, vector<Contact>> для тегов». То есть вы начинаете копировать контакты в несколько контейнеров.

Проблема не в том, что копия — это дорого (хотя иногда и дорого). Проблема в том, что:

• вы изменили имя контакта в одном месте;
• забыли изменить его во втором;
• потом нашли «старую версию» через другой поиск;
• и вот у вас уже две реальности, как в плохом фантастическом сериале.

Поэтому архитектурно здоровая схема такая:

• есть один контейнер, где лежат «настоящие» объекты;
• есть индексы, которые хранят не копии объектов, а «ссылку» (в широком смысле) на объект: id, позицию, что-то ещё.

Схематично это можно представить так:

flowchart LR
  A[Источник правды: vector<Contact>] --> B[Индекс byId: id -> position]
  A --> C[Индекс byEmail: email -> id]
  A --> D[Индекс byTag: tag -> set<id>]

Что считать «ссылкой» на объект

Когда мы говорим «ключ → где лежит объект», хочется ответить: «Ну адрес же! Давайте хранить указатель на элемент vector». И тут C++ такой: «Конечно. А потом vector сделает reallocation, и твой указатель станет прекрасным сувениром: выглядит как адрес, но ведёт в никуда».

Давайте аккуратно разберём варианты «ссылки на объект» и их свойства. Здесь нет магии: есть компромиссы.

id -> size_t pos

email -> id

email -> Contact*

email -> vector<Contact>::iterator

email -> Contact

В рамках нашего курса будем придерживаться практичного и безопасного подхода: стабильный id + хранение объектов в vector + индекс id -> позиция. Звучит как «два индекса», но это нормально: один — для стабильности, другой — для быстрого доступа.

Инварианты: что обязаны поддерживать

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

Для нашей адресной книги инварианты такие:

• Для каждого контакта contacts[i] должен существовать posById[contact.id] == i.
• Для каждого email должен выполняться idByEmail[email] == id контакта с этим email.
• Для каждого тега idsByTag[tag] должен содержать id всех контактов, у которых этот тег есть.
• Email уникален (если мы так решили по правилам приложения). Тогда в idByEmail не может быть двух разных id для одного email.

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

3. Модель и индексы приложения

Чтобы примеры не были «про сферических коней в вакууме», продолжим идею приложения: простое хранилище моделей (struct) в vector и операции CRUD.

Пусть у нас будет контакт:

#include <string>
#include <vector>

struct Contact {
    int id{};
    std::string name;
    std::string email;
    std::vector<std::string> tags;
};

Здесь id — стабильный идентификатор. Он не зависит от позиции в контейнере и не меняется, даже если мы переставили контакты местами.

Теперь заведём «хранилище» и индексы:

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

struct PhoneBook {
    std::vector<Contact> contacts; // источник правды

    std::unordered_map<int, std::size_t> posById;                     // id -> позиция
    std::unordered_map<std::string, int> idByEmail;                   // email -> id
    std::unordered_map<std::string, std::unordered_set<int>> idsByTag; // tag -> множество id

    int nextId{1};
};

Обратите внимание на философию:

• contacts — единственное место, где хранится объект целиком.
• posById, idByEmail, idsByTag — вспомогательные структуры, которые должны быть согласованы с contacts.

Да, это «лишний труд». Но это тот самый труд, который вы либо вкладываете сознательно, либо потом платите процентами в виде багов.

4. Добавление и поиск

Добавление: сначала «истина», потом индексы

Добавление — самый приятный сценарий: у нас появляется новый объект, мы кладём его в contacts, затем обновляем индексы.

Начнём с проверки уникальности email. Здесь важно не использовать operator[] у unordered_map, потому что он может создать ключ. Нам нужен find.

#include <optional>
#include <string>

std::optional<int> addContact(PhoneBook& book, std::string name, std::string email) {
    if (book.idByEmail.find(email) != book.idByEmail.end()) return std::nullopt;

    int id = book.nextId++;
    book.contacts.push_back(Contact{id, std::move(name), std::move(email), {}});
    book.posById[id] = book.contacts.size() - 1;
    book.idByEmail[book.contacts.back().email] = id;
    return id;
}

Обратите внимание на стиль: функция возвращает optional<int>. Если добавили — вернём id. Если не добавили (email занят) — вернём nullopt. Это ровно тот случай, где optional идеален: нам важно «успех/неуспех», а не сложная модель ошибок.

С тегами пока ничего не делаем: контакт добавляется без тегов. Добавление тегов вынесем отдельно.

Поиск: быстрый путь через индексы, объект — в vector

Поиск по email в такой архитектуре двухшаговый:

1) email -> id через idByEmail
2) id -> pos через posById
3) contacts[pos] — настоящий объект

Сделаем функцию, которая возвращает указатель (nullable API): если не нашли — nullptr.

#include <string>

const Contact* findByEmail(const PhoneBook& book, const std::string& email) {
    auto it = book.idByEmail.find(email);
    if (it == book.idByEmail.end()) return nullptr;

    int id = it->second;
    std::size_t pos = book.posById.at(id);
    return &book.contacts[pos];
}

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

5. Удаление: самое сложное место

Удаление — это то место, где индексы чаще всего ломают вам настроение. Причина простая: vector — плотный массив. Если вы делаете erase, элементы сдвигаются, позиции меняются, а индексы «по позициям» устаревают.

Есть несколько стратегий. Мы выберем практичную и популярную: swap-erase.

Идея: чтобы удалить элемент из vector быстро, мы:

• берём позицию удаляемого контакта pos,
• переносим последний элемент vector на место pos,
• делаем pop_back().

Так мы избегаем сдвига целого хвоста элементов. Цена — порядок в vector становится «как получится». Для адресной книги порядок обычно не критичен (а если критичен — это отдельное требование и отдельная архитектура).

Почему «просто удалить» недостаточно

Вот наивная версия удаления по id:

#include <cstddef>

bool removeById(PhoneBook& book, int id) {
    auto itPos = book.posById.find(id);
    if (itPos == book.posById.end()) return false;

    std::size_t pos = itPos->second;
    std::size_t last = book.contacts.size() - 1;

    book.contacts[pos] = book.contacts[last]; // swap-erase (перенос)
    book.contacts.pop_back();
    book.posById.erase(id);
    return true;
}

Она неполная, потому что мы не обновили индекс posById для контакта, который «переехал» с last на pos. И не обновили idByEmail, и не обновили idsByTag. То есть — классическая ловушка: удалить объект легко, согласовать индексы сложнее.

Корректное удаление: сохраняем нужное до перезаписи

Нам нужно заранее сохранить данные удаляемого контакта, которые участвуют в индексах: email и теги. И обязательно обновить позицию элемента, который переехал.

#include <vector>
#include <string>

bool removeById(PhoneBook& book, int id) {
    auto itPos = book.posById.find(id);
    if (itPos == book.posById.end()) return false;

    std::size_t pos = itPos->second;
    std::size_t last = book.contacts.size() - 1;

    // Важно: сохраняем ДО перезаписи (swap-erase затрёт нам удаляемый объект)
    std::string removedEmail = book.contacts[pos].email;
    std::vector<std::string> removedTags = book.contacts[pos].tags;

    book.contacts[pos] = book.contacts[last];
    book.contacts.pop_back();

    // Удаляем следы удалённого контакта из индексов
    book.posById.erase(id);
    book.idByEmail.erase(removedEmail);
    for (const auto& tag : removedTags) book.idsByTag[tag].erase(id);

    // Если мы переносили последний элемент — его позиция изменилась
    if (pos != last) {
        int movedId = book.contacts[pos].id;
        book.posById[movedId] = pos;
    }

    return true;
}

Да, эта версия длиннее. Зато она делает ровно то, что обязана: обновляет все индексы так, чтобы инварианты снова стали истинными.

6. Перестройка индексов и диагностика

Когда проще перестроить индекс целиком

Когда индексов становится несколько, поддержка каждого «по событию» может превратить простую операцию в длинный список мелких шагов, как мы видели в удалении. Иногда это нормально. Иногда — это слишком сложно и рискованно.

Поэтому существует очень практичная стратегия:

Для некоторых индексов проще периодически перестраивать их заново из источника правды.

Например, индекс по тегам idsByTag можно полностью перестроить за один проход по contacts. Это O(N * tags), но код становится компактным и надёжным. На небольших данных это часто лучший выбор.

Сделаем функцию rebuild:

void rebuildTagIndex(PhoneBook& book) {
    book.idsByTag.clear();
    for (const auto& c : book.contacts)
        for (const auto& tag : c.tags)
            book.idsByTag[tag].insert(c.id);
}

Обратите внимание, как резко уменьшается шанс «забыть обновить один из тегов». Мы не обновляем индекс «по чуть-чуть» — мы его пересоздаём.

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

Проверки инвариантов через assert

Когда у вас есть индексы, баги часто выглядят так: «иногда поиск возвращает не того человека» или «после удаления email всё ещё находится». Это неприятные баги, потому что они проявляются не сразу и часто зависят от последовательности действий.

Поэтому полезно иметь функцию, которая проверяет базовую согласованность. В учебном коде это можно делать через assert.

#include <cassert>

void checkBasicInvariants(const PhoneBook& book) {
    assert(book.posById.size() == book.contacts.size());
    for (std::size_t i = 0; i < book.contacts.size(); ++i)
        assert(book.posById.at(book.contacts[i].id) == i);
}

Да, это не полная проверка (email и теги мы не проверили). Но даже такая проверка поймает огромное количество ошибок «я забыл обновить позицию».

Тут есть важная инженерная мысль: индексы — это оптимизация. Оптимизация без проверок часто превращается в «ускоритель производства багов».

7. Несколько индексов и дисциплина изменений

Когда индексов становится два-три, появляется соблазн обновлять их «где придётся»: чуть-чуть в одной функции, чуть-чуть в другой, где-то в main, где-то в обработчике команды. Это почти гарантированно приводит к рассинхронизации.

Практическое правило архитектуры звучит скучно, но работает отлично:

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

То есть условно:

• addContact(...) — единственный способ добавлять контакт
• removeById(...) — единственный способ удалять
• updateEmail(...), addTag(...), removeTag(...) — единственные способы изменять поля, влияющие на индексы

Например, добавление тега:

bool addTag(PhoneBook& book, int id, std::string tag) {
    auto it = book.posById.find(id);
    if (it == book.posById.end()) return false;

    Contact& c = book.contacts[it->second];
    c.tags.push_back(tag);
    book.idsByTag[c.tags.back()].insert(id);
    return true;
}

Код небольшой, но идея взрослая: изменение источника правды и индекса делаются в одном месте.

8. Типичные ошибки

Ошибка №1: хранить объект в нескольких контейнерах «для удобства».
Это выглядит как быстрый путь к ускорению поиска: положили Contact и в vector, и в unordered_map, и ещё в список тегов. Но через пару изменений вы получите разные версии одного и того же контакта. Архитектурно правильнее: один источник правды и индексы, которые хранят только id/позиции.

Ошибка №2: индексировать vector по позициям и забывать, что erase сдвигает элементы.
Индекс id -> pos кажется простым, пока вы не удалили элемент из середины. После erase все правее сдвинулись, а индекс остался старым. Либо используйте стратегию swap-erase, либо будьте готовы обновлять позиции для большого диапазона, либо перестройте индекс.

Ошибка №3: хранить указатели/итераторы на элементы vector как “индекс”.
Это особенно коварно, потому что «вроде работает» до первого серьёзного изменения размера vector. После push_back, который вызвал перераспределение памяти, ваши указатели и итераторы становятся висячими. Если очень хочется хранить такие “привязки”, нужно иметь контейнер со стабильными адресами, но это уже другой разговор и другие компромиссы.

Ошибка №4: обновлять часть индексов, а про часть забывать.
Классика жанра: удалили контакт, обновили posById, но забыли убрать email из idByEmail, и поиск по email начинает находить «призрака». Лечится дисциплиной: изменения только через специальные функции и (в идеале) проверкой инвариантов.

Ошибка №5: использовать operator[] у unordered_map там, где вы хотели “просто проверить наличие”.
operator[] не «смотрит», а «создаёт, если нет». В индексах это может незаметно наделать мусорных записей. Для проверки используйте find, и только если действительно хотите вставить — тогда уже operator[] или insert.

1

Задача

C++ SELF, 61 уровень, 0 лекция

Недоступна

Карта склада

Карта склада

Открыть

1

Задача

C++ SELF, 61 уровень, 0 лекция

Недоступна

Регистрация почты

Регистрация почты

Открыть

1

Задача

C++ SELF, 61 уровень, 0 лекция

Недоступна

Чистка базы

Чистка базы

Открыть

1

Задача

C++ SELF, 61 уровень, 0 лекция

Недоступна

Пересборка тегов

Пересборка тегов

Открыть