Ich habe eine Liste, und die soll bitte immer sortiert sein

[Namenloser]

Zitat von stahli:

Würde sich ein binärer Suchbaum anbieten? Gibt es nutzbare Implementierungen (@Namenloser, Deine inzwischen?)?

Ich habe das Projekt, wofür ich es brauchte, mehr oder weniger abgebrochen, und seitdem meine Implementierung nicht weiterverfolgt. Prinzipiell funktioniert sie, wirkt aber noch etwas unfertig. Ich wollte den Code eigentlich noch auf Generics umschreiben, wollte aber auch die Unterstützung für ältere Compiler ohne Generics nicht verlieren. Es stellte sich dann aber leider heraus, dass es selbst mit den cleversten Include-Hacks, die mir einfallen, wohl unmöglich ist, beides gleichzeitig zu supporten, ohne den Code zu duplizieren. Ungefähr da habe ich dann die Lust verloren

Aber wie dem auch sei, ich schmeiße es jetzt einfach mal so wie es ist auf Github: https://github.com/Isopod/ABTrees. Wie gesagt, ich sehe es nicht als fertig an und übernehme keine Gewährleistung, aber vielleicht kann ja jemand was damit anfangen.

In src/abtrees kann man sehen, wie man sich einen eigenen Baum definiert. Wenn du Strings als Keys verwenden willst, müsstest du dann aber wohl TABKey als record definieren und den Vergleichsoperator überladen. Man kann natürlich mehrere Arten von Bäumen in einem Projekt haben, also z.B. einen, der Integers als Keys verwendet, einen, der Strings als Keys verwendet etc., man muss dann nur für jeden eine neue Unit anlegen.

Wichtig zu beachten:
- Ein Key muss eindeutig sein, er darf nicht mehrfach im Baum vorkommen. Das heißt natürlich nicht, dass nicht mehrere Leute „Hans“ mit Vornamen heißen dürfen, man muss sich nur überlegen, wie man den Key definiert. Man könnte z.B. zu dem Record noch eine eindeutige ID hinzufügen, die man vergleicht, wenn die Vornamen gleich sind.
- Seek gibt immer den Eintrag zurück, der am nächsten am gesuchten Key liegt und dessen Key kleiner oder gleich dem gesuchten Key ist. Es ist also kein "Find". Wenn die Einträge im Baum 1, 2, 3, 5, 6 lauten, dann gibt Seek(4) den Eintrag 3 zurück. Wenn man einen ganz bestimmten Eintrag sucht, muss man daher hinterher noch prüfen, ob der Key wirklich gleich ist.

Zitat von stahli:

Oder ist eine binäre Suche in einer Liste ohnehin fast gleich schnell?

Die Suche an sich ist schnell, aber wenn du viele Einträge löscht oder hinzufügst, könnte es langsam werden, da ja im Schnitt jedes mal die halbe Liste umkopiert wird.

[Dejan Vu]

Wieso speicherst Du die Daten nicht in einer DB, z.B. SQLite? Bei 100k Datensätzen wäre das zumindest eine Alternative.
Wenn Du das allerdings nicht willst, dann würde ich so vorgehen.
1. Die Liste bleibt, wie sie ist.
2. Für jede Sortieroption pflegst Du einen eigenen Index, d.h. einfach eine Liste der Referenzen, in der entsprechenden Sortierreihenfolge. Das kann ein Baum oder eine einfache Liste sein
3. Jede Operation (einfügen, ändern, löschen) bedingt (u.U.), das der Index korrigiert wird.

Dein Index benötigt also zwei Methoden: Remove und Add. Remove entfernt das Element aus dem Index, Add fügt es neu ein.

Deine Datenliste hat mindestens drei Methoden: Remove, Add und Update. Bei 'Remove' rufst Du einfach 'Remove' aller Indexe auf, bei 'Add' einfach 'Add' und bei Update erst 'Remove' und dann 'Add'. Beim Update wird klar, das Du dir den alten und den neuen Wert jeweils merken musst.
Mit dem alten Wert entfernst Du das Element aus allen Indexen und mit dem neuen Wert fügst Du das Element wieder in die Indexe ein.

Na ja, oder eben doch SQLLite, Access, Firebird etc etc etc.

PS: Kann man mit einer Memtable auch Indexe aufbauen? Geht, oder? Dann kann man sich das wirklich alles sparen.

[stahli]

@Namenloser

Danke für die Hilfe.
Ich werde aber doch erst mal eine Liste benutzen, da ich dort auch weiß, was wann wie passiert.
Wen ich es brauche und mir zutraue, schaue ich mir dann mal Deinen Baum an. Die benötigten Funktionen wären dann ja gleich/ähnlich, nur die innere Funktionalität würde dann ja anders ablaufen.

@Deja Vu

Ich habe diverse Interfaces, auf die ich auf unterschiedliche Weisen zugreife. Der Datenzugriff soll immer über Objekte erfolgen.
Ein ORM ist geplant, aber eine Datenbank soll dann auch nur über den ORM angesprochen werden. Der User soll davon letztlich nichts merken.
Kleinere Datenmengen sollen aber nur in Objekten verwaltet werden.

Deine Vorschläge 1-3 sehe ich auch so. Nur, statt Indizes in einer Liste zu sammeln, kann ich auch direkt die Pointer sammeln, sofern alle Objekte persistent im Speicher liegen.
Die gleiche Funktion unter Benutzung eines ORM müsste die Objekt-GUIDs heraus geben, da die Objekte dann anhand der GUID instanziiert werden.

Das Löschen und Einfügen von Objekten in der Hauptliste wird unproblematisch zu berücksichtigen sein. Ich muss dann halt in den angehängten Sortierlisten die Änderungen nachführen. Kein Problem.
Aber wenn ein Vor- oder Nachname eines Personenobjektes geändert wird, dann wird es schon deutlich schwieriger.
Eine Liste kann sich ja schlecht bei 1Mio Objekten als Überwacher anmelden. Dann müssten sich letztlich auch mehrere Listen bei jedem Objekt registrieren können. Ich werde wohl eine zentrale Stelle schaffen, in der sich Listen anmelden können und über Objektänderungen informiert werden. Dann können sie prüfen, ob eins ihrer Einträge von einer Änderung betroffen ist.