Indizes und Datenkonsistenz

1. Quelle der Wahrheit und Invarianten

Wenn man gerade erst mit Programmierung beginnt, wirkt die Idee „alles per Schleife durchlaufen und das Gesuchte finden“ nicht nur normal, sondern verdächtig angenehm. Das ist ehrlicher, gut lesbarer Code: öffnen, schauen, verstehen. Die Probleme entstehen nicht allein durch das Durchsuchen, sondern durch Anforderungen an die Anwendung: häufig suchen, nach verschiedenen Feldern suchen, Daten löschen und aktualisieren — und das alles ohne plötzliche Verzögerungen und ohne Logikfehler.

Stellen Sie sich vor, wir haben eine kleine CLI-Anwendung „Mini-Adressbuch“. Der Benutzer kann einen Kontakt hinzufügen, per email finden, per Tag finden (z. B. "work"), einen Kontakt löschen, den Namen aktualisieren. Wenn es 5 Kontakte gibt, ist die lineare Suche im vector ideal. Bei 50 000 Kontakten wird die lineare Suche zu Ihrer persönlichen Meditation über „warum habe ich das Programm überhaupt geöffnet“.

Ein Index ist eine Struktur, die den Zugriff beschleunigt. Die einfachste Definition:

Index — eine Abbildung vom Typ „Schlüssel → wo liegt das Objekt“.

Als Schlüssel kann id, email oder tag dienen, und „wo das Objekt liegt“ ist schon eine Architektursache, an der die Diskussion beginnt.

Quelle der Wahrheit: die Regel, die den Verstand rettet

Wenn Sie nur eine Idee aus dieser Vorlesung mitnehmen, dann diese: ein Objekt sollte an genau einem Ort leben, und dieser Ort ist die „Quelle der Wahrheit“. Alles andere sind abgeleitete Strukturen zur Beschleunigung.

Warum ist das wichtig? Weil die typische Anfänger-„Optimierung“ oft so aussieht: „Oh! Ich will schnell nach Email und Tags suchen. Machen wir ein unordered_map<string, Contact> für Email und zusätzlich ein unordered_map<string, vector<Contact>> für Tags“. Damit beginnen Sie, Kontakte zu kopieren in mehrere Container.

Das Problem ist nicht primär, dass Kopien teuer sind (obwohl manchmal teuer). Das Problem ist:

• Sie haben den Namen eines Kontakts an einer Stelle geändert;
• vergessen, ihn an der zweiten Stelle zu ändern;
• dann finden Sie die „alte Version“ über eine andere Suche;
• und schon existieren zwei Realitäten, wie in einer schlechten Sci‑Fi‑Serie.

Architektonisch gesunde Schemas sehen daher so aus:

• es gibt einen einzigen Container, in dem die „wahren“ Objekte liegen;
• es gibt Indizes, die keine Kopien der Objekte speichern, sondern eine „Referenz“ (im weiten Sinne) auf das Objekt: id, Position oder Ähnliches.

Schemahaft lässt sich das so darstellen:

flowchart LR
  A[Quelle der Wahrheit: vector<Contact>] --> B[Index byId: id -> position]
  A --> C[Index byEmail: email -> id]
  A --> D[Index byTag: tag -> set<id>]

Was gilt als „Referenz“ auf ein Objekt

Wenn wir sagen „Schlüssel → wo das Objekt liegt“, will man oft antworten: „Die Adresse! Wir speichern einen Zeiger auf das Element im vector.“ Und C++ sagt dann: „Klar. Bis der vector eine Reallokation macht und dein Zeiger ein hübsches Souvenir wird: sieht aus wie Adresse, führt aber ins Nirgendwo.“

Lassen Sie uns die Varianten einer „Referenz auf das Objekt“ und ihre Eigenschaften sorgfältig betrachten. Es gibt keine Magie, nur Kompromisse.

id -> size_t pos

email -> id

email -> Contact*

email -> vector<Contact>::iterator

email -> Contact

Im Rahmen dieses Kurses halten wir uns an einen praktischen und sicheren Ansatz: stabile id + Speicherung der Objekte im vector + Index id -> Position. Das klingt nach „zwei Indizes“, ist aber normal: einer für Stabilität, der andere für schnellen Zugriff.

Invarianten: was stets eingehalten sein muss

Das Wort „Invariant“ klingt, als käme jetzt Analysis mit einer Tafel voller Symbole. In Wirklichkeit ist es eine einfache Idee: was immer wahr sein muss, wenn das System in einem korrekten Zustand ist.

Für unser Adressbuch lauten die Invarianten:

• Für jeden Kontakt contacts[i] muss gelten: posById[contact.id] == i.
• Für jede Email muss gelten: idByEmail[email] == id des Kontakts mit dieser Email.
• Für jeden Tag muss idsByTag[tag] alle ids der Kontakte enthalten, die diesen Tag haben.
• Email ist eindeutig (wenn dies die Regel der Anwendung ist). Dann kann es in idByEmail nicht zwei verschiedene ids für dieselbe Email geben.

Das klingt nach „viel Zeugs“, aber die gute Nachricht ist: Invarianten lassen sich am bequemsten durch zentralisierte Operationen pflegen: Hinzufügen/Löschen/Aktualisieren verteilt sich nicht über den ganzen Code, sondern lebt in wenigen Funktionen.

3. Modell und Indizes der Anwendung

Damit die Beispiele nicht „über sphärische Pferde im Vakuum“ bleiben, führen wir die App-Idee fort: einfache Speicherung von Models (struct) in einem vector und CRUD‑Operationen.

Angenommen, wir haben einen Kontakt:

#include <string>
#include <vector>

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

Hier ist id ein stabiler Identifikator. Er hängt nicht von der Position im Container ab und ändert sich nicht, selbst wenn wir Kontakte vertauschen.

Jetzt definieren wir den „Store“ und die Indizes:

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

struct PhoneBook {
    std::vector<Contact> contacts; // Quelle der Wahrheit

    std::unordered_map<int, std::size_t> posById;                     // id -> position
    std::unordered_map<std::string, int> idByEmail;                   // email -> id
    std::unordered_map<std::string, std::unordered_set<int>> idsByTag; // tag -> Menge von id

    int nextId{1};
};

Beachten Sie die Philosophie:

• contacts — der einzige Ort, an dem das Objekt vollständig gespeichert ist.
• posById, idByEmail, idsByTag — Hilfsstrukturen, die mit contacts konsistent sein müssen.

Ja, das ist „zusätzliche Arbeit“. Aber genau diese Arbeit investieren Sie entweder bewusst oder später in Form von Bugs.

4. Hinzufügen und Suchen

Hinzufügen: zuerst die „Wahrheit“, dann die Indizes

Hinzufügen ist das angenehmste Szenario: ein neues Objekt erscheint, wir legen es in contacts ab und aktualisieren danach die Indizes.

Beginnen wir mit der Prüfung der Eindeutigkeit der Email. Hier ist es wichtig, nicht den operator[] von unordered_map zu verwenden, weil dieser einen Schlüssel anlegen kann. Wir brauchen 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;
}

Beachten Sie den Stil: Die Funktion gibt ein optional<int> zurück. Falls hinzugefügt — die id zurückgeben. Falls nicht (Email belegt) — nullopt. Genau der Fall, wo optional ideal ist: uns interessiert „Erfolg/Misserfolg“, nicht ein komplexes Fehler‑Modell.

Für Tags machen wir vorerst nichts: der Kontakt wird ohne Tags angelegt. Das Hinzufügen von Tags kapseln wir separat.

Suche: schneller Weg über die Indizes, Objekt im vector

Die Suche per Email ist in dieser Architektur zweistufig:

1) email -> id über idByEmail
2) id -> pos über posById
3) contacts[pos] — das reale Objekt

Wir schreiben eine Funktion, die einen Zeiger (nullable API) zurückgibt: wenn nicht gefunden — 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];
}

Warum hier at zulässig ist, statt find? Weil wenn idByEmail eine id enthält, aber posById diese nicht enthält, dann ist das bereits eine Inkonsistenz — ein interner Bug. In Lehrcode ist es akzeptabel, „laut zu fallen“, um Fehler früher zu entdecken. In produktivem Code würden Sie überlegen, wie man diesen Zustand handhabt; der Grundsatz bleibt: Erwartenes Fehlen behandeln wir sanft (find), unmögliches Fehlen laut.

5. Löschen: die schwierigste Stelle

Löschen ist der Punkt, an dem Indizes Ihnen am häufigsten schlechte Laune machen. Der Grund ist einfach: vector ist ein dichter Array. Bei einem erase verschieben sich Elemente, Positionen ändern sich und positionsbasierte Indizes werden veraltet.

Es gibt mehrere Strategien. Wir wählen die praktische und weit verbreitete: swap-erase.

Die Idee: um ein Element aus dem vector schnell zu löschen, tun wir:

• die Position des zu löschenden Kontakts pos ermitteln,
• das letzte Element des vector an die Stelle pos verschieben,
• pop_back() aufrufen.

So vermeiden wir das Verschieben eines ganzen Tails von Elementen. Der Preis: die Reihenfolge im vector wird „wie es kommt“. Für ein Adressbuch ist Reihenfolge meist unwichtig (ist sie kritisch — dann ist das ein anderes Anforderungsprofil und eine andere Architektur).

Warum „einfach löschen“ nicht ausreicht

Hier eine naive Version von Löschen per 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 (move)
    book.contacts.pop_back();
    book.posById.erase(id);
    return true;
}

Diese Version ist unvollständig, weil wir den Index posById für den Kontakt, der vom last-Index nach pos gezogen wurde, nicht aktualisiert haben. Ebenso wurden idByEmail und idsByTag nicht angepasst. Klassische Falle: Objekt löschen ist einfach, Indizes konsistent zu halten ist schwieriger.

Korrektes Löschen: Bewahren, bevor überschrieben wird

Wir müssen die für Indizes relevanten Daten des zu löschenden Kontakts vor der Überschreibung sichern: Email und Tags. Und unbedingt die Position des verschobenen Elements aktualisieren.

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

    // Wichtig: sichern VOR dem Überschreiben (swap-erase würde das zu löschende Objekt zerstören)
    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();

    // Spuren des gelöschten Kontakts aus den Indizes entfernen
    book.posById.erase(id);
    book.idByEmail.erase(removedEmail);
    for (const auto& tag : removedTags) book.idsByTag[tag].erase(id);

    // Falls wir das letzte Element verschoben haben — hat dessen Position sich geändert
    if (pos != last) {
        int movedId = book.contacts[pos].id;
        book.posById[movedId] = pos;
    }

    return true;
}

Ja, diese Version ist länger. Dafür macht sie genau das, was erforderlich ist: sie aktualisiert alle Indizes, sodass die Invarianten wieder gelten.

6. Indexrebuild und Diagnose

Wann es einfacher ist, einen Index komplett neu aufzubauen

Wenn die Anzahl der Indizes wächst, kann die Pflege jedes einzelnen „bei Ereignis“ eine einfache Operation in eine lange Liste kleiner Schritte verwandeln, wie wir beim Löschen gesehen haben. Manchmal ist das in Ordnung. Manchmal wird es zu komplex und riskant.

Deshalb gibt es eine sehr praktische Strategie:

Für manche Indizes ist es einfacher, sie periodisch komplett aus der Quelle der Wahrheit neu aufzubauen.

Beispielsweise lässt sich der Tag‑Index idsByTag vollständig in einem Durchlauf über contacts neu aufbauen. Das ist O(N * tags), aber der Code wird kompakt und zuverlässig. Bei kleinen Datensätzen ist das oft die bessere Wahl.

Wir implementieren eine rebuild-Funktion:

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

Beachten Sie, wie stark die Wahrscheinlichkeit sinkt, „einen Tag zu vergessen“. Wir aktualisieren den Index nicht stückweise — wir bauen ihn neu auf.

In realen Projekten kombiniert man oft Ansätze: idByEmail wird strikt und sofort aktualisiert (klein und kritisch), während „komplexe sekundäre Indizes“ gelegentlich komplett neu aufgebaut werden.

Invariantprüfungen mit assert

Wenn Sie Indizes haben, sehen Bugs häufig so aus: „manchmal gibt die Suche die falsche Person zurück“ oder „nach dem Löschen ist die Email noch auffindbar“. Diese Bugs sind unangenehm, weil sie sich nicht sofort zeigen und oft von einer Folge von Operationen abhängen.

Deshalb ist eine Funktion zur Basis‑Konsistenzprüfung nützlich. In Lehrcode kann man das mit assert machen.

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

Ja, das ist keine vollständige Prüfung (Email und Tags haben wir nicht geprüft). Doch selbst diese Prüfung fängt viele Fehler wie „ich habe vergessen, eine Position zu aktualisieren“ ab.

Hier steckt eine wichtige Ingenieursidee: Indizes sind Optimierung. Optimierung ohne Prüfungen verwandelt sich oft in einen „Beschleuniger für Bugs“.

7. Mehrere Indizes und Änderungsdisziplin

Wenn Indizes zwei oder drei werden, entsteht die Versuchung, sie „wo immer es passt“ zu aktualisieren: ein bisschen in einer Funktion, ein bisschen in einer anderen, irgendwo im main, irgendwo in einem Command‑Handler. Das führt nahezu garantiert zu Inkonsistenzen.

Eine praktische Architekturregel klingt langweilig, funktioniert aber ausgezeichnet:

Machen Sie Datenänderungsoperationen zu einem einzigen Entry‑Point, und aktualisieren Sie darin die Indizes vollständig.

Konkret also:

• addContact(...) — die einzige Möglichkeit, einen Kontakt hinzuzufügen
• removeById(...) — die einzige Möglichkeit, zu löschen
• updateEmail(...), addTag(...), removeTag(...) — die einzigen Möglichkeiten, Felder zu ändern, die Indizes betreffen

Beispiel: Tag hinzufügen:

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

Der Code ist kurz, aber die Idee ist erwachsen: Quelle der Wahrheit und Index werden am gleichen Ort geändert.

8. Typische Fehler

Fehler Nr. 1: das Objekt in mehreren Containern „zur Bequemlichkeit“ speichern.
Sie denken, das beschleunige die Suche: Sie legen Contact in den vector, in ein unordered_map und noch in Tag‑Listen. Nach ein paar Änderungen haben Sie verschiedene Versionen desselben Kontakts. Architektonisch richtiger: eine Quelle der Wahrheit und Indizes, die nur id/Position speichern.

Fehler Nr. 2: den vector nach Positionen indexieren und vergessen, dass erase Elemente verschiebt.
Das Mapping id -> pos wirkt einfach, bis ein Element aus der Mitte entfernt wird. Nach einem erase verschieben sich alle rechten Elemente, während der Index veraltet bleibt. Entweder nutzen Sie swap-erase, oder Sie aktualisieren Positionen für einen großen Bereich, oder Sie rebuilden den Index.

Fehler Nr. 3: Zeiger/Iteratoren auf Elemente des vector als „Index“ speichern.
Das ist besonders heimtückisch, weil es „zu funktionieren scheint“ bis zur ersten Reallokation des vector. Nach einem push_back, das eine Reallokation verursacht, werden Ihre Zeiger/Iteratoren dangling. Wer unbedingt solche Bindungen speichern möchte, muss einen Container mit stabilen Adressen verwenden — das ist aber ein anderes Thema mit anderen Kompromissen.

Fehler Nr. 4: einen Teil der Indizes aktualisieren und einen Teil vergessen.
Klassiker: Kontakt gelöscht, posById aktualisiert, aber vergessen, die Email aus idByEmail zu entfernen — die Suche nach Email findet einen „Geist“. Lässt sich durch Disziplin beheben: Änderungen nur über spezialisierte Funktionen und (idealerweise) Invariantprüfungen.

Fehler Nr. 5: operator[] bei unordered_map verwenden, wenn man nur auf Existenz prüfen wollte.
Der operator[] erzeugt den Schlüssel, falls er nicht existiert. In Indizes kann das unbemerkt Mülleinträge anlegen. Zur Überprüfung verwenden Sie find; nur wenn Sie tatsächlich einfügen möchten, nutzen Sie operator[] oder insert.

1

Aufgabe

C++ SELF, Level 61, Lektion 0

Gesperrt

Lagerkarte

Lagerkarte

Öffnen

1

Aufgabe

C++ SELF, Level 61, Lektion 0

Gesperrt

E-Mail-Registrierung

E-Mail-Registrierung

Öffnen

1

Aufgabe

C++ SELF, Level 61, Lektion 0

Gesperrt

Datenbankbereinigung

Datenbankbereinigung

Öffnen

1

Aufgabe

C++ SELF, Level 61, Lektion 0

Gesperrt

Neukonstruktion der Tags

Neukonstruktion der Tags

Öffnen