Generische Bibliotheken in C++

Nicht jede Bibliothek, die C++ Templates benutzt (oder die entsprechenden generischen Konstrukte in anderen Sprachen), kann schon das Attribut generisch für sich in Anspruch nehmen. In dieser subjektiven Auswahl schaue ich vor allem danach, wie allgemein die zugrundeliegenden mathematischen Konzepte in der Software widergespiegelt werden (und ob diese Konzepte überhaupt explizit behandelt werden). Mein Kernkriterium lautet daher:

Dies ist offensichtlich ein sehr hoher Anspruch. Ihm nahezukommen, setzt eine sorgfältige Analyse der grundlegenden Konzepte voraus. Bei praktischen Implementierungen muss immer der Aufwand gegen den Nutzen abgewogen werden. Damit ist Generizität der Software in der Praxis auch keine absolute Eigenschaft, sondern weist verschiedene Abstufungen auf. Letzten Endes unterscheiden sich ja auch mathematische Konzepte in ihrem Grad der Abstraktion.

Allerdings kann man zumindest verlangen, dass eine Anwendung auf Nutzer-definierte Argumente nicht an den Zufälligkeiten der Implementierung scheitert (wir verlangen array::size(), aber der Nutzer hat array::length()). Wegen solcher Freiheiten beim Umsetzen abstrakter Konzepte in konkrete Software kann man zwar offensichtlich nicht verlangen, dass alle "prinzipiell" geeigneten Argumente direkt in die generische Komponente eingesetzt werden können. Es sollte jedoch (zumindest prinzipiell) mit vertretbarem Aufwand möglich sein, geeignete Adaptoren zu entwerfen, wenn die Abstraktion "stimmt" (und die generische Komponente sollte das so einfach wie möglich machen).

Und nun, zu den konkreten Beispielen ...

Diese Zusammenstellung ist sortiert nach Anwendungsgebieten: lineare Sequenzen, Graphen, Geometrie und Bildverarbeitung.

Bibliotheken für lineare Sequenzen: Die Standard Template Library & Co

Der bekannteste Vertreter einer generischen Bibliothek ist die Standard Template Library (STL), seit 1998 Bestandteil der C++ Standard Library. Die STL ist im Wesentlichen das Werk von Alexander Stepanov, aufbauend auf früheren Arbeiten mit David Musser. Sie abstrahiert Sequenz-Datentypen (wie Array, Listen) und entsprechende Algorithmen, wie Suchen, Vergleichen, und Sortieren. Das Bindeglied zwischen Sequenz-Datenstrukturen und Algorithmen bilden Iteratoren, die im wesentlichen die Funktionen Navigation und Wertzugriff unterstützen. Verschiedene Untertypen von Sequenzen (wie bidirektionale oder wahlfreie Navigation) werden durch Unterkategorien von Iteratoren erfasst, um ggf. effizientere Algorithmen auszuwählen. Es hat sich gezeigt, dass man hier mit nur 5 Kategorien auskommt.

Streng genommen ist "die" STL keine Bibliothek, sondern eine Spezifikation (im C++ Standard beschrieben), von der es mehrere Implementierungen gibt. Zunächst einmal kommt mit jedem Standard-konformen C++ Compiler eine Standard-Bibliothek, die die STL enthält. Zudem gibt es einige populäre Implementierungen, wie die SGI STL und STLport, die einen Debug-Modus unterstützt.

Die STL wird in vielen Büchern und Online-Dokumentationen ausführlich beschrieben. Eine gute (mittlerweile etwas veraltete) Online-Dokumentation ist die STL Dokumentation von SGI aus der Zeit um 1998, als Alexander Stepanov dort gearbeitet hat. Eine gute Einführung ist das Buch von Nicolai Josuttis:

• Nicolai Josuttis The C++ Standard Library - A Tutorial and Reference 2nd Edition. Addison Wesley 2012
  Die 2. Auflage deckt auch die Erweiterungen in C++11 ab.
  Support Seite

Bibliotheken für Graphen

Die Boost Graph Library deckt den Bereich von Graphen und Graph-Algorithmen ab. Die Abstraktionen der BGL bauen auf denjenigen der STL auf. So gibt es Iteratoren im STL-Sinne über Konten und Kanten, aber auch lokale Iteratoren über die eingehenden und ausgehende Kanten eines Knotens. Daten, die den Knoten oder Kanten zugeordnet sind, werden mit sogenannten property maps modelliert. Iteration bzw. Navigation wird hier also getrennt von der Wertezuordnung (im Gegensatz zur STL, die beides mit dem Iterator-Konzept "erschlägt".) Die BGL ist ausführlich dokumentiert und in dem Buch von Jeremy Siek beschrieben:

• Jeremy Siek, Lie-Quan Lee, Andrew Lumsdaine The Boost Graph Library. User Guide and Reference Manual. Addison Wesley 2002

Es gibt ebenfalls von Boost auch eine parallele Erweiterung der BGL.

Bibliotheken für geometrische Datenstrukturen und Algorithmen

Mit geometrischen Datenstrukturen und Algorithmen arbeiten unter anderem die Computational Geometry Algorithms Library (CGAL) und Grid Algorithms Library (GrAL).

Die (sehr große) Computational Geometry Algorithms Library CGAL befasst sich mit geometrischen Datenstrukturen und Algorithmen. Allerdings scheinen mir viele nicht-triviale Algorithmen auf die mitgelieferten Datenstrukturen zugeschnitten. So funktioniert die Berechnung von 2D Polygon-Schnitten nur für die eingebauten Datenstrukturen wie Polygon_2. Diese sind zwar parametrisiert, aber Nutzer-definierte Datentypen können letztlich nur um den Preis einer Kopie benutzt werden.

Meine eigene Entwicklung, die Grid Algorithms Library GrAL, ist thematisch etwas eingeschränkter als CGAL und konzentriert sich auf Datenstrukturen und Algorithmen für geometrische Gitter (Meshes, Netze) beliebiger Dimension (mathematisch sind das zelluläre Komplexe, ein einfaches Beispiel sind Dreiecksgitter oder Triangulierungen). Für 2-dimensionale Gitter hat man es mit den grundlegenden Elementen Knoten, Kanten und Zellen (Flächen) zu tun. Auch hier werden die sequentiellen STL-Iteratoren erweitert um lokale Iteratoren, die jeweils die Nachbar-Elemente durchlaufen. Daten auf diesen Elementen werden durch Gitterfunktionen modelliert (dies entspricht in etwa den properties in der Boost Graph Library). GrAL unterstützt mit verteilten Gittern auch die parallele Programmierung. Ein wichtiger Spezialfall sind kartesische Gitter, für die einige Algorithmen effizienter implementiert werden können (analog zum Fall von random access Sequenzen bei der STL).

Bibliotheken für die Bildverarbeitung

Im Bereich der Bildverarbeitung gibt es ebenfalls mehrere generische Ansätze, wie VIGRA, Generic Image Library (GIL) und ITK (Imaging Toolkit).

Die von Ulrich Koethe entwickelte Bibliothek VIGRA (Vision with Generic Algorithms) arbeitet mit Bild-Datenstrukturen beliebiger Dimension und bietet eine Vielzahl generisch formulierter Algorithmen an. Die wesentlichen Abstraktionsmechanismen sind Iteration mit mehrdimensionalen Differenz-Typen (Offsets) und Daten-Accessoren, die den Zugriff auf die Bilddaten kapseln (um z.B. auch Multiband-Datenstrukturen generisch bearbeiten zu können). Die Accessoren spielen eine ähnliche Rolle wie BGL's property maps oder GrAL' grid functions. In der Tat können die kartesischen Gitter von GrAL mit einer geeigneten Gitterfunktion recht einfach auf ein Modell eines VIGRA Image abgebildet werden.

Ursprünglich von Adobe entwickelt, ist die Generic Image Library (GIL) mittlerweile in Boost integriert. Hier heißen die mehrdimensionalen Iteratoren locators, da sie i. A. nicht die Bedingungen der (1-dimensionalen) STL-Definitionen erfüllen (Inkrement und Dekrement können nicht bzw. sind nicht definiert). GIL definiert formale concepts, d.h. Anforderungen an die Template-Parameter, die bei der Instantiierung vom Compiler geprüft werden. Allerdings sind nicht sehr viele Algorithmen implementiert, da der Fokus eher auf einem sauberen und effizientem generischen Interface zu Bild-Datenstrukturen lag. Seit 2007 ist hier auch nicht viel hinzugekommen.

Sehr weit verbreitet ist der ITK (Insight Toolkit) der US National Library of Medicine. ITK bietet eine sehr große Auswahl an Bildverarbeitungsalgorithmen. Die Bild-Datenstrukturen sind mit Templates parametrisiert und dimensions-unabhängig. Allerdings ist die Implementierung der Algorithmen auf diese Datenstrukturen spezialisiert, der Grad der Generizität von ITK ist damit eher eingeschränkt.