Indeksowanie danych: id → obiekt, tag → lista

1. Indeksy danych

Wyobraźcie sobie, że przechowujecie zadania w std::vector<Task> i za każdym razem, gdy trzeba znaleźć zadanie po id, uczciwie przebiegacie cały wektor pętlą. To działa… dopóki zadań nie zrobi się dużo, a zapytań — jeszcze więcej. Indeks to struktura danych, która przyspiesza typowe zapytanie: „znajdź obiekt po kluczu”. W praktycznym rozwoju to właśnie indeksy sprawiają, że aplikacje są „zwinne”, ale równocześnie dodają nowy ból głowy: trzeba je utrzymywać w zgodzie.

Zróbmy prostą, codzienną analogię. Biblioteka ma książki na półkach (to „prawdziwe obiekty”), a także katalog według autorów i katalog według tytułów (to „indeksy”). Jeśli bibliotekarz dodał książkę na półkę, ale zapomniał wpisać ją do katalogu — czytelnik uzna, że książki nie ma. Jeśli odwrotnie, w katalogu jest wpis, a książki na półce nie ma — czytelnik będzie szukać „widma”. To właśnie jest rozbieżność indeksów.

Mini-model danych: Task i „źródło prawdy”

Żeby mówić konkretnie, wprowadzimy mały model danych. Niech mamy mini-aplikację TaskBook: przechowujemy zadania, każde ma numeryczne id, tekstowy title i zestaw tagów (np. "cpp", "study", "home"). Nie stosujemy skomplikowanej architektury: żadnych klas i „magii”, tylko struct i kontenery STL, tak jak już umiemy.

Ważne, by wcześniej ustalić jedną zasadę: jedno źródło prawdy. Oznacza to, że prawdziwy obiekt Task przechowujemy w jednym miejscu, a w indeksie trzymamy tylko informacje referencyjne (np. id). Dzięki temu przy zmianie zadania nie trzeba „synchronizować dwóch kopii obiektu”, a jedynie zaktualizować indeksy, które do niego wskazują.

Zacznijmy od modelu:

#include <string>
#include <vector>

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

Tutaj tags to właśnie vector, bo to wygodne do wyświetlania i iteracji. Unikalność tagów zapewnimy osobno (później), żeby nie przechowywać "cpp", "cpp", "cpp" — tak, to się zdarza, zwłaszcza jeśli użytkownik wpisuje tagi ręcznie.

2. Indeksy: podstawowy i wtórny

Indeks podstawowy id → Task: szybki dostęp do obiektu

Indeks podstawowy to miejsce, gdzie leżą „prawdziwe” obiekty. Najbardziej oczywista opcja: std::unordered_map<int, Task> tasksById; Wtedy po id otrzymujemy zadanie szybko i bez przeszukiwania liniowego. Nie będziemy rozważać „idealnych” złożoności i wnętrza hashtable — ważne jest, że sens operacji zmienia się z „przebiec wszystko” na „znaleźć po kluczu”.

Wprowadźmy typy (kod czyta się lepiej, oczy mniej się męczą):

#include <unordered_map>

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

Pokażemy teraz podstawowy wzorzec odczytu: find → sprawdzić → użyć. Zwróćcie uwagę: to odczyt bez efektów ubocznych (nie tworzymy niczego przypadkowo).

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

I osobno warto podkreślić ważną myśl (to realnie oszczędza godziny debugowania): jeśli chcesz tylko przeczytać — używaj find/contains. operator[] używaj, gdy naprawdę chcesz „utworzyć lub zaktualizować”.

Indeks wtórny tag → lista id: szybkie wyszukiwanie po kategorii

Teraz zrobimy drugi rodzaj zapytań: „pokaż wszystkie zadania z tagiem cpp”. Jeśli mamy tylko tasksById, trzeba by przeszukać wszystkie zadania i sprawdzić, czy dany tag jest w Task::tags. To znowu liniowe przejście po wszystkich zadaniach, i na dużych danych będzie smutno.

Dlatego wprowadzamy indeks wtórny: tag → lista id. Dlaczego nie tag → lista Task? Bo ustaliliśmy jedno źródło prawdy: Task żyje w tasksById, a indeks przechowuje tylko referencje do niego w postaci id.

Wybór kontenera dla „listy id” zależy od wymagań. W wersji edukacyjnej wygodnie użyć std::unordered_set<int>: automatycznie usuwa duplikaty, a sprawdzenie „czy id jest w zbiorze” jest szybkie. Gdyby zależał nam na kolejności lub potrzebne były duplikaty — można by użyć std::vector<int>, ale wtedy trzeba by ręcznie czyścić duplikaty. Na początek wybieramy „solidny” wariant.

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

Dane aplikacji wyglądają teraz tak (konceptualnie):

flowchart LR
    subgraph Primary["Indeks podstawowy (źródło prawdy)"]
        A["tasksById: id → Task"]
    end

    subgraph Secondary["Indeks wtórny (referencje)"]
        B["tagToIds: tag → {id, id, id}"]
    end

    B -->|"id"| A

Psychologicznie warto pamiętać: w indeksie wtórnym nie przechowujemy zadania, przechowujemy „kartę” wskazującą na nie przez id. To jak karta katalogowa, a nie książka.

4. Operacje bez rozstrojenia

Gdy pojawia się drugi indeks, każda operacja „utwórz obiekt” zamienia się w „utwórz obiekt + zaktualizuj indeksy”. I tu pojawiają się typowe błędy: student dodał zadanie do tasksById, ale zapomniał dodać jego id do tagToIds, a potem dziwi się, dlaczego wyszukiwanie po tagu „nic nie zwraca”.

Aby nie rozsiać takich błędów po całym kodzie, wprowadzamy prostą dyscyplinę: wszystkie zmiany danych przechodzą przez jedną funkcję. Niech to będzie AddTask(...). Tak, brzmi to nudno. Ale nudny kod zwykle działa, a zabawny kod często bawi tylko kompilator.

Najpierw przygotujemy małą funkcję, która usuwa duplikaty tagów. Zrobimy to przez chwilowy unordered_set, a potem wrócimy do vector. Kod jest krótki, ale sens ważny: wewnątrz Task tagi będą schludne.

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

Skoordynowane dodawanie: aktualizujemy oba indeksy

Zwróćcie uwagę: najpierw próbujemy wstawić do tasksById. Jeśli id jest już zajęte — wychodzimy, nic więcej nie zmieniamy. Jeśli wstawienie się powiodło — aktualizujemy tagToIds. Tutaj operator[] używany jest świadomie: jeśli tag nie istnieje, chcemy utworzyć dla niego pusty zbiór.

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

Zauważcie przyjemny efekt: kod wywołujący w ogóle nie musi pamiętać, że mamy „dwa indeksy”. Po prostu wywołuje AddTask, a funkcja robi całą nudną pracę. To mały krok w stronę dobrej architektury, bez wielkich słów i religii.

Skoordynowane usuwanie: usuwamy tak, żeby nie zostały „widma”

Usuwanie jest jeszcze bardziej niebezpieczne niż dodawanie. Błąd zwykle wygląda tak: usunąłeś zadanie z tasksById, ale zapomniałeś usunąć jego id z tagToIds. Potem robisz „pokaż po tagu” — dostajesz id, którego już nie ma w indeksie podstawowym. I wtedy spotykasz „widmowe zadanie”: indeks mówi, że jest, a rzeczywistość mówi „nie ma”.

Usuwanie powinno składać się z dwóch kroków: usunąć odnośniki z indeksów wtórnych, potem usunąć sam obiekt. Porządek jest właśnie taki: najpierw czyścimy „katalogi”, potem zdejmujemy „książkę z półki”. Ponownie opakowujemy to w jedną funkcję, aby nie powielać logiki w dziesięciu miejscach.

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

Tu jest mała estetyka: jeśli po usunięciu id zbiór stał się pusty, usuwamy sam tag z indeksu. To nie jest konieczne, ale zwykle upraszcza strukturę: nie będzie „tagów, które nie mają zadań”.

Modyfikacja danych: jak bezpiecznie zmieniać tagi i tytuł

Modyfikacja to część, w której indeksy szczególnie lubią się rozstroić. Tytuł (title) można zmieniać bez problemu: nie uczestniczy w naszym indeksie (na razie). Natomiast tagi są podstawą indeksu wtórnego. Jeśli zmienisz Task::tags, ale nie zaktualizujesz tagToIds, indeks wtórny natychmiast stanie się „fałszywy”.

Prawidłowy model aktualizacji tagów jest taki: trzeba usunąć id ze starych tagów, potem dodać id do nowych tagów, i dopiero zapisać nowe tagi w Task. W istocie to „przeprowadzka” z jednego zbioru do drugiego. Znowu tworzymy oddzielną funkcję, żeby nie rozmazywać logiki po całej aplikacji.

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

Jeśli pomyśleliście teraz: „O rany, dla tagów tyle kodu…” — to normalna reakcja. Indeksy dają szybkość zapytań, ale pobierają „podatek” w postaci starannej aktualizacji przy zmianach. W dużych systemach ten podatek płaci się architekturą i dyscypliną, a u nas — schludnymi funkcjami.

5. Zapytania i walidacja

Indeksy nie są budowane dla piękna, lecz dla zapytań. Zróbmy więc dwie małe funkcje drukujące: jedna wyświetla zadanie po id, druga wypisuje wszystkie zadania dla danego tagu. Ustalmy od razu: nie tworzymy ładnego „fancy” outputu, ważne jest pokazanie, jak używać indeksów.

Zapytania: „pokaż po id” i „pokaż po tagu”

Wyświetlenie jednego zadania:

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

Zapytanie „pokaż po id” to po prostu find w indeksie podstawowym:

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

Natomiast zapytanie „pokaż po tagu” używa indeksu wtórnego. Zwróć uwagę: indeks wtórny daje nam zbiór id, a następnie dla każdego id odwołujemy się do tasksById i pobieramy obiekt. To właśnie „jedno źródło prawdy” w praktyce.

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

Zwróćcie uwagę na „paranoję”: nawet jeśli indeks powinien być zgodny, i tak sprawdzamy tasksById.find(id). W idealnym świecie można by tego nie robić, ale w edukacyjnym kodzie ta weryfikacja pomaga „przeżyć” błąd rozstrojenia i zauważyć problem, zamiast upaść w nieznane.

Sprawdzanie spójności: inwarianty i prosta walidacja

Gdy indeksów jest więcej niż jeden, warto sformułować „żelazne reguły”, które zawsze powinny być prawdziwe. W programowaniu takie reguły często nazywa się inwariantami. Bez formalnej matematyki, po ludzku:

Jeśli w tagToIds["cpp"] jest 42, to w tasksById musi istnieć zadanie z id 42. I odwrotnie: jeśli zadanie 42 zawiera tag "cpp", to tagToIds["cpp"] powinien zawierać 42.

W projektach edukacyjnych bardzo pomaga prosta funkcja-walidator, którą można wywołać po serii operacji i sprawdzić, czy indeksy „się nie rozjechały”. Tak, to dodatkowe przejście po danych, ale to jak latarka: nie przyspiesza chodzenia, lecz pomaga nie wpaść na słup.

Zrobimy prostą weryfikację „z wtórnego do podstawowego” (w praktyce wykrywa większość błędów):

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

Jeśli chcecie, można dodać także odwrotną weryfikację (z podstawowego do wtórnego), ale nawet jedna kontrola już dyscyplinuje: zaczynacie traktować indeksy jako coś, co trzeba utrzymywać, a nie jako „magiczne” przyspieszenie.

6. Typowe błędy przy pracy z wieloma indeksami

W tym temacie większość błędów nie jest „składniowa”, lecz architektoniczna: kod się kompiluje, czasem nawet działa, ale dane stopniowo zamieniają się w kryminał. Dlatego błędy lepiej rozpoznawać po symptomach i przyzwyczajeniach, nie tylko po komunikatach kompilatora.

Błąd nr 1: dwa źródła prawdy (duplikowanie obiektów w indeksach).
Często kusi, by zrobić tag → vector<Task> „bo wtedy wygodniej drukować”. Pierwsze pół godziny rzeczywiście jest wygodnie. Potem zmieniasz title zadania w tasksById, zapominasz zaktualizować kopię w drugim miejscu — i nagle masz dwie różne rzeczywistości. Zdecydowanie bezpieczniej trzymać obiekt w jednym miejscu, a w indeksach tylko id.

Błąd nr 2: zaktualizowano jeden indeks, zapomniano o drugim.
Klasyka gatunku: dodałeś zadanie do tasksById, ale nie dodałeś jego id do tagToIds; albo usunąłeś z tasksById, ale nie wyczyściłeś tagToIds. Objawy proste: „po id znajduje, po tagu — nie” lub „po tagu znajduje id, ale po id zadania nie ma”. Leczy się dyscypliną: wszystkie operacje przez funkcje typu AddTask/RemoveTask/UpdateTaskTags.

Błąd nr 3: odczyt przez operator[] i przypadkowe tworzenie pustych wpisów.
Na przykład zapis tagToIds[tag] w trybie „odczytu” utworzy nowy tag z pustym zbiorem id, a potem zaczniesz się zastanawiać, skąd wzięły się te dziwne puste tagi. Jeśli czytasz — używaj find/contains. operator[] zostaw na sytuacje, gdy utworzenie przy braku jest pożądane (jak w AddTask).

Błąd nr 4: nie czyszczą „pustych” kluczy w indeksie wtórnym.
Jeśli po usunięciu id z tagToIds[tag] zbiór stał się pusty, a Ty zostawiłeś pusty wpis — logika zwykle nie pęka, ale struktura zaczyna się „zapychać”: pojawiają się tagi bez zadań. To szczególnie widoczne w aplikacjach, gdzie tagi pokazywane są użytkownikowi w liście. Sprzątanie pustych kluczy czyni zachowanie schludnym i przewidywalnym.

Błąd nr 5: tagi w środku Task mają duplikaty i indeks zaczyna żyć „dziwnie”.
Jeśli zadanie ma tagi {"cpp", "cpp"}, to przy aktualizacji indeksów robisz zbędną pracę, a przy drukowaniu użytkownik widzi duplikaty i zaczyna podejrzewać intrygę. Normalizacja tagów (przynajmniej usuwanie duplikatów) to drobna rzecz, ale znacząco podnosi jakość danych i zmniejsza liczbę „magicznych” błędów.