001
27.11.2011, 05:05 Uhr
0xdeadbeef
Gott (Operator)
|
Mir ist nicht ganz klar, was man da mit Vererbung soll; Compositing passt eigentlich deutlich besser. Aber was soll's.
Das Prinzip einer Indexliste ist eigentlich ziemlich simpel. Du hast deine verkettete Liste, und neben der verketteten Liste hast du einen Index. Dieser ist schlicht ein Array von Zeigern, die auf die Listenelemente zeigen. Es ist etwas schwierig, das in ASCII darzustellen, aber ich tu mal mein Bestes:
Code: |
+---+ +---+ +---+ +---+ +---+ | 3 |-->| 1 |-->| 4 |-->| 5 |-->| 2 |--> NULL +---+ +---+ +---+ +---+ +---+ ^ ^ ^ ^ ^ | | | | | +-+ | +---+ | | | | | | | | | | +-------+ | +-------+ | | | | | +---------------------------+ | | | | | | +-|---+ | | | | | | | +---+---+---+---+---+ | | | | | | Index +---+---+---+---+---+
|
Auf die Weise kann man, ohne seine Objekte in der Gegend herumschieben zu müssen, später das drittkleinste Element schnell und einfach auslesen - über Arrayzugriff in den Index halt.
Den Index kann man dann behandeln wie jedes andere sortierte Array. Wird ein neues Element in die Indexliste gebracht, dann wird es an die verkettete Liste einfach angehängt und ein Zeiger auf den Listenknoten an der richtigen Stelle in den Index eingefügt. Die richtige Stelle ist eine, die die Sortierung nicht verletzt; diese lässt sich über eine binäre Suche in O(log(N)) finden, denn der Index ist ja immer sortiert.
Das Entfernen eines Objektes läuft analog: der betroffene Zeiger muss aus dem Index entfernt werden, danach wird das Objekt aus der Liste gelöscht.
Caveat: Es darf nicht passieren, dass die Objekte in der Liste an der Indexstruktur vorbei geändert werden, sonst ist der Index plötzlich nicht mehr sortiert und das alles fliegt böse auseinander. Also nie nicht-konstante Referenzen zurückgeben!
Mehrere Indices zu unterstützen ist ziemlich simpel - du musst dann halt mehrere Arrays verwalten und jede Operation, die du vorher auf einem Index gemacht hast, in allen durchführen. Es ändert sich dann lediglich die Vergleichsfunktion. Wenn ihr Funktionszeiger schon gehabt habt, wäre das eine gute Möglichkeit, sie einzusetzen, um deinen Prof zu beeindrucken. In der Praxis würde man im Zweifel std::(tr1::)function benutzen, aber in Lehrmaterial findet man das eher selten. -- Einfachheit ist Voraussetzung für Zuverlässigkeit. -- Edsger Wybe Dijkstra Dieser Post wurde am 27.11.2011 um 05:15 Uhr von 0xdeadbeef editiert. |