Datenstruktur gesucht

Wie greifst du auf die Datenstruktur zu, über einen Index oder brauchst du nur das erste/letzte Element? Und wie fügst du Elemente in die Datenstruktur ein?
Hoff ich hab die Anforderungen nicht ganz falsch verstanden, aber wenn du bei einem std::vector immer nur am Anfang oder am Ende einfügst, hättest du eine implizite Ordnung, über die Element-Speicheradresse könntest du damit für zwei Elemente auch die Reihenfolge auswerten.

Zuerst ein paar grundsätzliche Fragen:
- Was bedeutet "feststellen, welches von 2 Elementen zuerst eingefügt wurde"? 2 beliebige Elemente nach einem Schlüssel suchen und deren Einfügezeit vergleichen?
- Wie viele Elemente sind denn so durchschnittlich in der Datenstruktur?
- So effizient wie möglich? Wie wäre es dann mit etwas selbst implementiertem und auf das Wesentliche reduzierte? Etwas vorgefertigtes ist halt meist etwas allgemein gehalten. Oder geht es nur um die Laufzeitkomplexität?

Variante I: Nur wenn es eher wenige Elemente sind (bei im Schnitt <=10 Elemente ist das sicher die beste Lösung, über 20 Elemente ist das sicher nicht mehr das Optimum)
Variante II: Nur wenn es sich um einen balancierten Baum handelt (Rot-Schwarz, AVL, oder so)

Meine Empfehlung:
Eine Hashtabelle. Einfügen konstant, löschen konstant, 2*suchen und vergleichen ebenfalls konstant. Zahlt sich auch erst ab vielen Elementen aus.
Ein Einfügeindex ist hier auch nötig.

Einfügeindex: Wie weit liegen minimaler und maximaler Index maximal auseinander (< MAX_INT)? Weiß man wo ungefähr der minimale Index liegt, kann man diesen von beiden Indizes abziehen und erst danach vergleichen. Dann sind beide immer positiv und der Vergleich immer korrekt, selbst wenn man immer hinaufzählt.

Zitat von Christoph R.

Von der Hashtabelle alleine kann ich noch nicht ableiten was zuerst drin war. Nachdem die Schlüssel keine Daten anhängen haben, geht es genau genommen nur um den Einfügeindex.

Von der Hashtabelle alleine nicht, aber wenn jedes Element einen Schlüssel (zur Suche) und einen Einfügeindex enthält, dann können die 2 Elemente gesucht und anschließend die Reihenfolge verglichen werden.

Zitat

Das verstehe ich jetzt nicht ganz.

Meine Idee war diese: Bei jedem add(e) wird dem e der aktuelle Zähler zugewiesen und dieser anschließend erhöht. Wenn ich wissen will ob a vor b eingefügt wurde, dann muss ich nur die beiden Zähler vergleichen. Das funktioniert selbst dann wenn zwischendurch Elemente (samt ihrem Zähler) wieder gelöscht wurden. Problem ist halt dass ich einen Index niemals wiederverwenden darf weil sonst die Ordnung zerstört wird.

Ja, davon geht man aus und erweitert dieses Konzept so, dass für die ganze Datenstruktur (egal ob Hashtabelle oder Baum) ein minimaler Index midx mitgespeichert wird. Vergleicht man nun a und b, so vergleicht man nicht a < b, sondern (a - midx) < (b - midx), wobei midx <= dem kleinsten aller Indizes sein muss.
Beispiel: Angenommen der Überlauf ist bei 999, der aktuelle Einfügeindex e = 999 und die Datenstruktur ist gefüllt mit { m:820, k:834, p:846, d:990, w:995 }
midx ist 820 (im Idealfall, evtl. auch etwas kleiner)
Vergleich man m mit d, so vergleicht man (820-820) < (990-820), also 0 < 170 und damit ist m kleiner.

Fügt man nun ein weitere Elemente ein: z und g
{ m:820, k:834, p:846, d:990, w:995, z:999, g:0 }
So gibt es einen Überlauf auf 0 (ich gehe mal von unsigned aus, geht aber auch bei signed).
Vergleicht man nun m mit g, so funktioniert das mit 820 < 0 nicht. Jedoch mit (820 - 820) < (0 - 820), also 0 < 180 schon. Wobei 0-1 eben 999 ist.

Wichtig dabei ist, dass der Wertebereich aller Indizes nie 1000 erreichen darf (wenn midx immer genau dem kleinsten Einfügeindex entspricht). Ist midx eine etwas schlechtere Abschätzung (also etwas kleiner als 820), muss der Bereich halt entsprechend kleiner sein.

Geht man von einem Zahlenbereich von long (32 Bit) aus (4 Mrd Zahlen) und weiß man, dass ein Element spätestens nach 2 Mrd. Einfügeoperationen wieder entnommen worden ist, so reicht es, wenn man midx auf e - 2 Mrd. setzt und man muss nie die Indizes durchlaufen und neu nummerieren. In diesem Fall muss man midx nicht mal als Variable mitspeichern, sondern könnte sie immer bei Bedarf berechnen.

Wie schaut's denn eigentlich aus wenn ein Element gelöscht wird und wieder später eingefügt wird? Ist dieses als neues Element (Event) zu behandeln (sprich letztes in der Ordnung)? Sonst, wird's relativ schwierig.

Naja, eine Alternative wären vllt. noch Skiplisten um die Ordnung abzuspeichern (mehr Speicher).

Sonst könntest du dir die separat in einer double linked List speichern. Die Hashmap hat den key + Eintrag in der Liste. Wenn du aus den Pointern ablesen kannst ob es vorher oder nachher eingefügt wurde passt's. Sonst hast du die gleichen Probs wie vorher.

Alternativ könnte man versuchen die Ordnung in einen Binärbaum abzubilden, wobei der "idx" in diesem Fall die Entscheidung gibt ob ein Knoten links
oder rechts hin kommt. Nachteil: Man sollte den Baum balanced halten (Einfügen / Löschen)