Mapping

« | 29 Nov 2018 | »

Zu den wichtigsten Container-Datenstrukturen zählten in meiner bisherigen Karriere:

• Arrays:
  Lineare Felder von Datentypen, die per Index angesprochen werden
• Maps:
  Felder von Schlüssel-Wert Paaren, die über den Schlüssel angesprochen werden

Maps sind auch als assoziative Arrays, Dictionaries oder Tables bekannt. Jede Programmiersprache bzw. -umgebung lässt sich da offenbar einen anderen Namen einfallen.

---

Auch gibt es unterschiedliche Implementierungen für Mapping-Strukturen, die aber in der Regel alle eines gemein haben: Die Suche nach einem Schlüssel und dem zugehörigen Wert soll mit möglichst wenig Zugriffen und Vergleichen auskommen.

Ein Möglichkeit sind Hashes, aber um die soll es hier nicht gehen.

Eine andere Implementierung nutzt sortierte Baumstrukturen (Tree) und weil Sortierung auch für Anwendungen und UIs wichtig sind, findet man sie relativ häufig.

Es gibt natürlich jede Menge unterschiedliche Ansätze für solche Bäume, aber gerade bei Kernstrukturen wie Maps wird häufig eine Form des Rot-Schwarz-Baums genutzt.

Die Hersteller der Standardbibliotheken von Programmiersprachen legen sich zwar formal auf keine Zugriffsmethode in Maps fest, trotzdem findet man Rot-Schwarz-Bäume in C++, Java und .NET.

Nachdem die Sprache C hier leider nicht wie C++ eine Map-Implementierung bereitstellt, bleibt mir auch im GATE Projekt nichts anderes übrig, als eine beizusteuern.

Nachdem für mich der Grundsatz gilt:

Wenn es auf Wikipedia eine vollständige Beispiel-Implementierung gibt, ist die Materie ‘einfach’ genug, dass man selbst eine Implementierung schaffen und auf Fremdbibliotheken verzichten kann.

Und tatsächlich finden wir in der deutschen und der englischen Version jeweils eine gute Dokumentation samt Beispielcode.

Also dann … ran an die Tasten!