gibt es eine sortierte container Klasse in C++?
-
@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.
