Gesucht: sortierte queue oder priority_queue oder ???
-
Hallo,
ich brauche eine Datenstruktur, in der die Elemente einer Ordnung folgen. D.h. die Elemente werden mit einem fortlaufenden Zähler an eine Liste angefügt; idR. stimmt die Reihenfolge, wenn sie nicht stimmt soll die queue dies automatisch sortieren, d.h. das Element soll in der richtigen Reihenfolge in der queue landen (bzw. an richtiger Position vorn rauskommen).
Nur bietet das ja eigentlich die priority_queue, nur verkehrt herum -- bei mir sollen die kleinsten Zähler vorne rauskommen und die größten immer am Ende hängen. Würde es dafür reichen einfach den Vergleichsoperator operator< verkehrt herum zu implementieren?
Gleichzeitig, und das wird mit der Queue wohl schwieriger, soll sichergestellt sein, daß in der Queue beim Rausnehmen keine Lücke in den Zählern ist. D.h. ich möchte die Liste an dem Punkt trennen, so daß ich eine Queue mit Element n habe, für die gilt ((n->id)+1)==(++n)->id. Ich denke es gibt keinen Container, der einem sowas direkt bietet, oder? Auf welchem Container würde man sowas denn am Besten implementieren?
Die Bedienung von außen erfolgt weiterhin wie eine Queue. Hinten anfügen, vorne wegnehmen - entweder die Struktur wird getrennt in sortiert und unsortiert oder es wird auch weiterhin in richtiger Reihenfolge ohne Lücken vorne entnommen.
wie geht man da am Besten vor? danke
-
Dem prio_queue-Konstruktor kann man eine Funktion mitgeben anhand der sortiert werden soll.
Den zweiten Punkt habe ich nicht ganz verstanden. Du willst an einer beliebigen Stelle die Queue in zwei Queues aufteilen? Oder wie?
-
Danke. Das mit dem prio_queue Ctor hat auf Anhieb noch nicht geklappt, aber da werde ich weiter reinschauen.
Das Problem ist, daß ich gleichzeitig sicherstellen möchte, daß wenn ich vorne ein pop() mache, dies auch ein Element ist, welches eine id hat, die genau um einen höher ist als beim pop des vorherigen Element -- also jedes Element, was ich raushole hat einen um 1 größeren Zähler. Natürlich nur, wenn dies auch möglich ist, d.h. so ein Element bereits eingefügt wurde. Wenn dem nicht der Fall, darf vorne nichts rauskommen, was diese Bedingung nicht einhält.
Meine Idee, war entweder zwei Queues/Listen/etc. von Vorne ausgehend an dem Punkt zu teilen, wo die Reihe ihre erste Lücke hat. Die erste Liste kann verarbeitet werden. Beim nächsten Teilen wird gehofft, daß inzwischen Elemente hinten angefügt wurden, die durch ihre id in die Lücke rutschen, sonst ist die erste Liste leer. D.h. eine Liste teilen an dem Punkt, wo zwischen zwei Elementen eine bestimmte Bedingung nicht mehr gilt.
Die andere Idee war vorne die ganze Zeit pop()s zu machen und wenn das nächste Paket die eben genannte Bedingung nicht erfüllt, meldet sich die Liste als z.B. leer.
Eine von meiden Möglichkeiten möchte ich implementieren, da es wohl keine Struktur gibt, die dies von Haus bietet. Ich frage mich daher auf welcher Struktur ich dies am Besten implementiere? Die einfache Sortierung müßte mir die priority_queue bieten, allerdings kann man die wohl nicht so einfach teilen.
-
Warum willst du Listen teilen?
Reicht dir es nicht die Liste regelmäßig zu fragen ob das oberste Element die verlangte ID hat...?