gibt es eine sortierte container Klasse in C++?
-
danke euch beiden
-
@SeppJ sagte in gibt es eine sortierte container Klasse in C++?:
Löschen eines Iterators in konstanter Zeit.
Ich dachte eigentlich immer, dass auch wenn man den Knoten nicht erst noch suchen muss, sich immer noch das Rebalancing mit niederschlägt. Auf cppreference sind die Iterator-basierten
erase-Funktionen allerdings tatsächlich mit "Amortized constant" angegeben. Ich glaube da muss ich nochmal was recherchieren und meine Kenntnisse auffrischen
-
Da war ich ein bisschen ungenau, ja es ist O(1), mit gelegentlicher Möglichkeit O(log N) zu brauchen, aber so dass es im Durchschnitt immer noch O(1) ist. Das Rebalancing braucht man ja immer seltener, je größer N ist, so dass sich die gelegentlich längeren Laufzeiten im Durchschnitt weg heben.
-
@countryclub2 sagte in gibt es eine sortierte container Klasse in C++?:
Gibt es eine container klasse, die O(log n) zugriff auf elemente bietet, O(log n) einfügen und O(1) löschen? Also quasi eine immer sortierte Liste?
Darf ich fragen, wo deine Anforderungen herkommen? Du scheinst ja zu erfordern, dass Löschen schneller sein soll als Zugriff. Hast du also eine große Menge an Dingen und willst oft etwas löschen? Gibt es vielleicht andere Möglichkeiten wie Filterkriterien zu bestimmen und deine Ursprungsliste einmalig zu filtern?
Neben den rein technischen Dingen wäre es für mich interessant, den Usecase zu verstehen. Meistens ist ja der schnelle Zugriff viel wichtiger als schnelles Löschen und ich hatte (glaube ich) noch nie den Fall, dass schnelles Löschen für mich wichtig war.
-
Mir fällt jetzt keine Anwendung ein, wo die Kombination aus O(log N) einfügen und O(1) löschen Sinn macht. Man kann nur so viel löschen, wie man eingefügt hat. Also O(log N) einfügen und löschen, oder O(1) einfügen und löschen. Letzteres kann man mit einer hash map haben. Und wenn nur selten iteriert werden muss, könnte es vielleicht OK sein einfach ad-hoc zu sortieren - weil die hash map ja nicht sortiert ist.
-
Forenerfahrung sagt XY-Problem. Oder eine leichte Abwandlung davon, wo man zwar eigentlich O(1) Einfügen möchte, aber denkt das wäre unmöglich, und daher schon vorauseilend nur nach O(log N) fragt.
-
@hustbaer sagte in gibt es eine sortierte container Klasse in C++?:
Mir fällt jetzt keine Anwendung ein, wo die Kombination aus O(log N) einfügen und O(1) löschen Sinn macht. Man kann nur so viel löschen, wie man eingefügt hat. Also O(log N) einfügen und löschen, oder O(1) einfügen und löschen. Letzteres kann man mit einer hash map haben. Und wenn nur selten iteriert werden muss, könnte es vielleicht OK sein einfach ad-hoc zu sortieren - weil die hash map ja nicht sortiert ist.
Ich kann mir da auch nur was aus den Fingern saugen, wie ein System, bei dem nur das "aufräumen" (bzw. Löschen) in einem Prozess passiert, der z.B. Echtzeitanforderungen zu erfüllen hat. Dann wären aber auch alle "amortisiert O(1)"-Lösungen hinfällig und man würde für eine so spezielle Anforderung eh etwas eigenes bauen - zumal da auch noch einiges an Synchronisation nötig wäre.
Ich denke auch wie @SeppJ sagt ein XY-Problem oder eine Übungsaufgabe, bei der es vornehmlich darum geht, sich eben solche Gedanken zu machen. Oder O(1) ist gar nicht wirklich wichtig und die Antwort lautet schlicht
std::map
-
@hustbaer sagte in gibt es eine sortierte container Klasse in C++?:
Mir fällt jetzt keine Anwendung ein, wo die Kombination aus O(log N) einfügen und O(1) löschen Sinn macht.
In der Komplexitaetstheorie wird man die bestmoeglichen Laufzeiten fuer eine gegebene Datenstruktur erreichen wollen um bestimmte bounds einzuhalten (siehe bspw. Fibonacci Heaps fuer Dijkstra Komplexitaet). Da wir hier in einem C++ Kontext sind wird das nicht die Motivation des TEs sein, aber trotzdem erwaehnenswert.
Man kann einfach stumpf O(N * log N) als bauen eines flat-sets betrachten, d.h. N mal in ein Array inserieren und am Ende (oder laufend) sortieren, dann ist das loeschen trivial O(1), und zwar worst-case. Klingt aber irgendwie unsinnig und ich stimme bzgl. X/Y zu.
-
@Columbo sagte in gibt es eine sortierte container Klasse in C++?:
Man kann einfach stumpf O(N * log N) als bauen eines flat-sets betrachten, d.h. N mal in ein Array inserieren und am Ende (oder laufend) sortieren, dann ist das loeschen trivial O(1), und zwar worst-case. Klingt aber irgendwie unsinnig und ich stimme bzgl. X/Y zu.
Verstehe ich nicht ganz. Wie soll das Löschen dabei O(1) sein? Man muss dann ja alle Elemente die danach (oder davor) kommen verschieben. Also O(N). Es sei denn man markiert das Element nur als gelöscht. Das geht aber mit jeder Datenstruktur. Und wie gesagt: ich frage mich wozu man das brauchen würde.
-
@hustbaer sagte in gibt es eine sortierte container Klasse in C++?:
Verstehe ich nicht ganz. Wie soll das Löschen dabei O(1) sein? Man muss dann ja alle Elemente die danach (oder davor) kommen verschieben. Also O(N).
Wenn man Listen oder Baumstrukturen hat, ist das Löschen O(1). Was die O-Notation so gerne unterschlägt ist die Konstante, die man für die Durchführung benötigt. Sprich Dein O(N) ist wahrscheinlich schneller als das O(1) Löschen in einem anderem Fall.
-
@hustbaer sagte in gibt es eine sortierte container Klasse in C++?:
@Columbo sagte in gibt es eine sortierte container Klasse in C++?:
Man kann einfach stumpf O(N * log N) als bauen eines flat-sets betrachten, d.h. N mal in ein Array inserieren und am Ende (oder laufend) sortieren, dann ist das loeschen trivial O(1), und zwar worst-case. Klingt aber irgendwie unsinnig und ich stimme bzgl. X/Y zu.
Verstehe ich nicht ganz. Wie soll das Löschen dabei O(1) sein? Man muss dann ja alle Elemente die danach (oder davor) kommen verschieben. Also O(N). Es sei denn man markiert das Element nur als gelöscht. Das geht aber mit jeder Datenstruktur. Und wie gesagt: ich frage mich wozu man das brauchen würde.
Ich hab die Frage falsch verstanden. Ich dachte es geht hier nur um delete-min (das waere einfach pop_*). Offensichtlich funktioniert ein flat-set auch nicht fuer worst-case O(log n) insertion.
Das geht aber mit jeder Datenstruktur.
Mit trees schiebst Du das rebalancing auf, womit Du dann wiederum die insertion Komplexitaet beeinflusst.
Die andere Frage waere ob das loeschen per key oder per Iterator passiert, weil man natuerlich das Element praktisch nie in worst-case O(1) finden kann. Da kaeme ehestens eine hash map in Frage.
-
@john-0 sagte in gibt es eine sortierte container Klasse in C++?:
Wenn man Listen oder Baumstrukturen hat, ist das Löschen O(1).
Ausbalancierten Bäume?
-
@Quiche-Lorraine sagte in gibt es eine sortierte container Klasse in C++?:
@john-0 sagte in gibt es eine sortierte container Klasse in C++?:
Wenn man Listen oder Baumstrukturen hat, ist das Löschen O(1).
Ausbalancierten Bäume?
Immer noch O(1), amortisiert eben.
-
@SeppJ sagte in gibt es eine sortierte container Klasse in C++?:
@Quiche-Lorraine sagte in gibt es eine sortierte container Klasse in C++?:
@john-0 sagte in gibt es eine sortierte container Klasse in C++?:
Wenn man Listen oder Baumstrukturen hat, ist das Löschen O(1).
Ausbalancierten Bäume?
Immer noch O(1), amortisiert eben.
Im englischen Wikipedia-Artikel zum Rot-Schwarz-Baum ist die Argumentation, dass Rebalancing nach Löschen höchstens 3 Rotationen benötigt, das umfärben der Knoten sich aber im Worst Case bis zur Wurzel fortpflanzen kann (). Dazu heisst es dort:
The loop is where the problem of rebalancing is escalated level higher in the tree in that the parent P becomes the new current node N. So it takes maximally h iterations to repair the tree (where h is the height of the tree). Because the probability of escalation decreases exponentially with each iteration the total rebalancing cost is constant on average, indeed amortized constant.
Das ist vielleicht eine interessante Hintergrundinformation. Ich kratze mich zwar gerade noch am Kopf, weshalb die Wahrscheinlichkeit exponentiell abnimmt, aber wenn das gilt, ist amortisiert nachvollziehbar (muss noch etwas draufstarren, es sind dort alle möglichen Konfigurationen in einer Ebene aufgelistet und werden behandelt).
-
@Columbo sagte in gibt es eine sortierte container Klasse in C++?:
Ich hab die Frage falsch verstanden.
Oder auch nicht. Fest steht: wir haben die Frage unterschiedlich verstanden
