| 3.4. Geordnete Folgen (Klasse sortseq) | ||
|---|---|---|
|
Kapitel 3. Assoziative Containertypen |  |
| 3.4. Geordnete Folgen (Klasse sortseq) | ||
|---|---|---|
|
|
Kapitel 3. Assoziative Containertypen | |
Lernziele
| Geordnete Folgen |
Eine geordnete Folge (im Sinne von LEDA) ist eine Folge von Containern, bei der jeder Container aus einem Schlüssel eines linear geordneteten Schlüsseltyps und einem Wert eines beliebigen Wertetyps besteht. Die Container sind dabei in aufsteigender Reihenfolge ihrer Schlüssel geordnet. Abbildung 3.6 zeigt eine geordnete Folge.
Abbildung 3.6. Eine geordnete Folge
Eine geordnete Folge mit 6 Containern. Der Schlüsseltyp ist string, der Wertetyp ist int. Die Container sind nach den Schlüsseln (lexikographisch) geordnet, nicht nach den Werten.
Geordnete Folgen werden in LEDA durch die Klasse sortseq angeboten, die eine breite Palette von Operationen anbietet. Diese umfasst nahezu alle Operationen, zu denen lineare Listen, Wörterbücher und Prioritäts-Warteschlangen fähig sind, und noch Vieles mehr. Eine sortseq leistet dies sogar asymptotisch mit demselben Zeitaufwand.
Geordnete Folgen sind somit der „eierlegende Wollmilchsau-Containertyp“ von LEDA.[33] Jedoch sollte man die Klasse sortseq nicht bedenkenlos verwenden: Der Preis für ihre Vielfältigkeit sind ein erhöhter Platzaufwand für das Speichern der Struktur und größere Konstanten in den asymptotischen Laufzeiten der einzelnen Operationen.
[33] Ein dem Autor bekannter LEDA-Adepte antwortete auf die Frage, wozu er denn geordnete Folgen hauptsächlich einsetze, mit den Worten „Wenn ich nicht weiß, welchen spezialisierten Containertyp ich im Endeffekt wirklich brauche, oder zu faul bin, mir das zu überlegen, dann fange ich erst einmal mit einer sortseq an, und wenn am Ende alles läuft, und ich noch Lust habe, dann ersetze ich sie durch das, was ich wirklich brauche.“
|
|
 |
|
| 3.3.3. Maps (Klasse map) |  |
3.4.1. Grundfunktionalität |